Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
24
Одеський державний політехнічний університет
Дрозд Юлія Володимирівна
УДК 681.325.5
Методи та пристрої для виконання
вертикальних арифметичних операцій
.13.05 Елементи та пристрої обчислювальної техніки
та систем керування
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Одеса 2000
Дисертацією є рукопис.
Робота виконана в Одеському державному політехнічному університеті міністерства освіти та науки України.
Науковий керівник
кандидат технічних наук, доцент
Паулін Олег Миколаєвич,
Одеський державний політехнічний університет,
доцент кафедри “Системне програмне забезпечення”
Офіційні опоненти:
доктор технічних наук, професор Власенко Віктор Олексійович Одеський державний політехнічний університет, завідувач кафедри “Інформаційно-вимірювальна техніка”
доктор технічних наук, професор Романкевич Олексій Михайлович, Національний технічний університет “КПІ”, професор кафедри “Спеціалізовані комп’ютерні системи”, лауреат Державної премії України
Провідна установа
Інститут проблем математичних машин та систем НАН України, м. Київ
Захист відбудеться “29”_червня_ 2000 р. о _ на засіданні спеціалізованої вченої ради Д 41.052.01 Одесьского державного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.
З дисертацією можна ознайомитись у бібліотеці Одеського державного політехнічного університету за адресою: 65044, м. Одеса, пр. Шевченка, 1.
Автореферат розісланий “__” _червня_ 2000 р.
ВТО вченого секретаря
спеціалізованої вченої ради Становський О.Л.
Загальна ХАРАКТЕРИСТИКА РоБОТи
Актуальність теми. Високі вимоги, що пред’являються до продуктивності сучасних арифметичних пристроїв (АП), виділяють як найважливіші питання розпаралелювання обчислень, що вирішуються з використанням матричних та конвейєрних структур у межах горизонтальної та вертикальної організації.
горизонтальна організація обчислень, що історично склалася як головна, передбачає обробку даних послідовно по числах та паралельно за розрядами. При цьому апаратний паралелізм матричних структур, з одного боку, вимагає великих витрат обладнання, які часто знаходяться у квадратичній залежності від розрядності операндів, а з іншого не забезпечує відповідний часовий паралелізм обчислень, необхідний для продуктивної обробки даних. Конвейєризація обчислень виконується із використанням матричних пристроїв за ділянки конвейєра та недоцільна у самій матричній структурі з великої кількості зв’язків між їх елементами, що запобігає ефективному розбиттю пристрою на ділянки конвейєра. Це обмежує можливості досягнення високої продуктивності при горизонтальній обробці даних.
Вертикальна організація обчислень передбачає обробку даних послідовно по розрядах та паралельно за числами. В основу цієї організації покладене збігання за часом процесів обробки різних розрядів чисел на різних ділянках конвейєра. Відповідність, яка встановлюється при цьому між апаратним, що вводиться, та часовим, що досягається, паралелізмами обчислень, визначає високі потенційні можливості вертикальної обробки для побудови продуктивних АП.
Однак у наш час методи та засоби вертикальної обробки даних не знайшли достатнього розвитку. Не досліджена структурна організація вертикальних АП. Недостатньо вивчені питання матричного розпаралелювання у порозрядних структурах. Перелік пристроїв, що вживаються для вертикальної обробки чисел, обмежений використанням двійкової системи числення (СЧ).
Таким чином, розробка методів проектування АП із вертикальною обробкою даних є важливою задачею, що визначає актуальність теми дисертаційної роботи.
Зв’язок роботи із науковими програмами, планами, темами. Дисертація виконувалась відповідно до завдань науково-дослідницької роботи кафедри системного програмного забезпечення ОДПУ № 329-73 “Програмні засоби автоматизованих систем. Розробка та дослідження методів та засобів автоматизованих систем”.
Мета та задачі дослідження. Метою дисертаційної роботи є підвищення якості проектування АП із вертикальною обробкою даних за рахунок дослідження, розробки та впровадження методів проектування, що базуються на формалізації та розпаралелюванні обчислень у двійково-кодованих СЧ, використанні особливостей організації пристроїв на різних рівнях структури та забезпечують оцінку відомих АП і одержання нових рішень з підвищеною швидкодією та (або) зниженими витратами обладнання.
Для досягнення цієї мети в дисертаційній роботі розв’язані такі задачі:
проаналізовані відомі рішення по вертикальній обробці даних із структуризацією обчислень до рівня елементарних операцій та вивченням можливостей узагальнення рішень і шляхів зпрощення та прискорення обчислень на різних рівнях обчислювального процесу;
створено багаторівневу математичну модель виконання вертикального додавання із використанням способів переведення чисел із однієї СЧ в іншу, що забезпечує єдиний підхід до проектування вертикальних АП, визначені операції повнорозрядного та елементарного ділення кількості одиниць, впорядкування та довпорядкування одиниць, які виконуються на рівнях моделі, та розроблені способи виконання цих операцій;
обгрунтовано вибір пірамідальних структур операцій впорядкування одиниць та повноразрядного ділення, що забезпечує підвищення швидкодії АП без додаткових витрат обладнання;
розроблені способи спрощення АП для впорядкування одиниць, елементарного та повноразрядного ділення кількості одиниць, а також вертикального додавача за рахунок наслідування впорядкованості кодів;
розроблені способи збільшення та об’єднання операцій, що забезпечують розпаралелювання обчислень із підвищенням їх обсягу та проектування АП із найбільшою швидкодією;
запропоновано методику одержання множини альтернативних рішень, які виключають варіанти АП, що поступаються за витратами обладнання і швидкодією;
розроблені методи проектування АП для виконання вертикальних операцій, а також програмна реалізація методів, що визначають АП із найменшими витратами обладнання при заданій швидкодії та найбільшою швидкодією при заданих витратах обладнання.
Наукова новизна одержаних результатів полягає в розвитку та поглибленні теоретичних та методологічних основ проектування АП з виконанням вертикальних операцій. Новими науковими результатами диссертації є:
визначено єдиний підхід до проектування вертикальних АП, який базується на запропонованій моделі виконання вертикального додавання за способами переведення чисел із однієї СЧ в іншу із використанням операцій повнорозрядного та елементарного ділення кількості одиниць, впорядкування та довпорядкування одиниць;
виявлена незалежність обсягу обчислень від їх структури для операцій впорядкування одиниць та повноразрядного ділення, що обгрунтовує вживання найбільш швидких пірамідальних структур АП при фіксованих витратах обладнання;
визначена часткова впорядкованість кодів, виявлена її наявність у вертикальних операціях та одержано способи їх спрощення за рахунок використання часткової впорядкованості кодів;
запропоновано механізм підвищення швидкодії АП за рахунок збільшення операцій: введено багатомісцеву операцію довпорядкування одиниць, визначено спосіб виконання операції та розроблено методику її оцінки, одержано єдині операції елементарного та повноразрядного ділення, а також вертикальне додавання із підвищеною основою СЧ;
виявлено механізм одержання множини альтернативних рішень, яка виключає вертикальні АП, що поступаються іншим за витратами обладнання і швидкодією;
розроблені методи проектування АП для впорядкування одиниць, ділення кількості одиниць та вертикального додавання, що дозволяють оцінювати належність відомих рішень до множини альтернативних та будувати нові АП, які перевищують відомі за показниками швидкодії та (або) витрат обладнання.
Практичне значення одержаних результатів. Застосування розроблених методів проектування АП із вертикальним виконанням обчислень у вигляді програмної реалізації дало змогу розширити перелік альтернативних рішень та значно покращити показники швидкодії та витрат обладнання.
Результати роботи впроваджено у навчальний процес в ОДПУ в дисциплінах “Методи паралельних обчислень”, “Арифметичні основи обчислювальної техніки“ та “Спеціалізовані архітектури ЕОМ”.
В Українському НДІ радіо та телебачення (м. Одеса) програмна реалізація методу проектування вертикального додавача використана для розробки цифрового фільтру системи сполучення аналогових радіорелейних ліній з цифровими системами передавання, що дало змогу підняти швидкодію цифрового блоку на 40%.
Особистий внесок здобувача полягає в дослідженні існуючих та розробці нових методів проектування АП для вертикальної обробки даних.
Дисертант розробила математичну модель операції вертикального додавання та на її основі запропонувала методи проектування АП для виконання вертикальних операцій, довела їх до рівня програмної реалізації та впровадження у навчальний процес і виробництво.
Апробація результатів роботи. Результати роботи докладалися та обговорювались на щорічних наукових конференціях молодих дослідників ОДПУ (Одеса, 1997 1999), на міжнародному школі-семинарі “Перспективні системи управління на залізничному, промисловому та міському транспорті” (Алушта, 1997) та міжнародній науково-технічній конференції “Приладобудування 98” (Євпаторія, 1998).
Публікації. за темою дисертації опубліковано 9 наукових робіт, у том числі 3 авторських свідоцтва на винаходи.
Структура дисертації. Дисертаційна робота складається із вступу, п’яти розділів, висновків і додатків. Повний обсяг дисертації 182 стор., з них додатків 24 стор. Дисертація містить 35 рисунків, 16 таблиць і посилання до 81 використаного джерела.
Основний зміст роботи
У вступі обгрунтовано актуальність теми дисертації, сформульовані мета та задачі досліджень, викладені основні научні та практичні результати роботи.
У першому розділі розглянуто сучасний стан схемотехніки АП із вертикальним виконанням обчислень.
Схемотехніка АП вдосконалюється у напрямку підвищення їх продуктивності шляхом розпаралелювання обчислювальних процесів.
З переходом до виконання операцій над паралельними кодами затвердилася горизонтальна обробка чисел. Під неї склалася елементна база інтегральні схеми, які містять в собі функціонально-завершені вузли, що нарощуються у напрямку збільшення розрядності чисел. Розробляються алгоритми та структури виконання бінарних арифметичних операцій над паралельними кодами чисел у однотактних АП. Подальший розвиток обчислювальної техніки пов’язаний з проектуванням систем для обробки масивів даних, які можуть ефективно використовувати вертикальну організацію обчислень. Сучасні великі інтегральні схеми базові матричні кристали, програмовані логічні матриці та програмовані логічні інтегральні схеми (ПЛІС) дозволяють здолати бар’єр елементної бази, вирівнюють можливості реалізації обох організацій обчислень та створюють умови для розвитку вертикальної обробки даних. Її вигідно відрізняє однорідність структури операнда у базовій арифметичній операції додаванні. Ця операція виконується над паралельним кодом, що складається з розрядів однієї ваги множини чисел, та полягає у підрахуванні кількості одиниць коду. Однорідність розрядів коду дозволяє виконувати над ними операцію у будь-якій послідовності, що створює природні умови для розпаралелювання обчислювального процесу.
Серед відомих підходів до виконання вертикального додавання найбільше поширення набули рішення, які реалізують безпосереднє рахування одиниць на повних двійкових додавачах та півсуматорах. В останній час розробляються методи функціонально-логічного синтезу багатооперандних додавачів на базі симетричних функцій. Вони значно підвищують швидкодію вертикальних додавачів для малорозрядних кодів. Однак із збільшенням розрядності коду методи різко втрачають ефективність, оскількі зростання швидкодії затримується внаслідок обмежень елементної бази, а витрати обладнання збільшуються у степеневій залежності від розрядності операндів, що складають паралельний код.
відомі рішення дозволяють говорити про складну структуру операції вертикального додавання, її подання через простіші вертикальні операції та виконання на блоках та вузлах, які є вертикальними АП. У АП, що виконують безпосереднє рахування одиниць, такими вузлами є повні додавачі та півсуматори. Вони об’єднуються у блоки, що зменшують кількість одиниць початкового коду. У швидкодіючих АП можна виділити блоки, що змінюють розміщення одиниць коду.
Потреба у вертикальних додавачах із різною швидкодією, а також зростання витрат обладнання АП, що значно випереджає підвищення швидкодії, роблять доцільним пошук множини альтернативних рішень, які вигідно відрізняються або швидкодією, або витратами обладнання, тобто множини, з якої виключаються рішення, що поступаються іншим одночасно і за швидкодією і за витратами обладнання. Розглядаються однотактні АП, для яких витрати обладнання оцінюються по квайну обсягом обчислень (кількостю бінарних логічних операцій ТА, АБО) а швидкодія кількостю рівнів схеми, тобто рівнів логічних операцій ТА, АБО.
Проектування вертикальних АП істотньо ускладнено відсутністю процедури вибору кращого рішення за заданою швидкодією чи витратам обладнання внаслідок різноманітності структур та обмеженого кола рішень, що витікає з недостатнього вивчення їх структурної организації, питань розпаралелювання обчислень у вертикальних операціях, а також обмеженнями рішень можливостями елементної бази та використанням двійкової СЧ.
Аналіз обмежень на розробку швидкодіючих вертикальних АП, а також структуризація та формалізація обчислень у відомих решеннях показали необхідність та можливість:
У другому розділі виконана декомпозиція операції вертикального додавання у двійково-кодованій СЧ до рівня елементарних операцій.
Запропоновано виконання операції вертикального додавання за способами переведення кількості одиниць u операнда у СЧ із основою k.
Спосіб визначення результату, починаючи із молодших розрядів, наведений на рис. 1 та містить у блоці 4 операцію ділення кількості одиниць паралельного коду на k, що обчислює частку u=E(u/k) та залишок ai=umod k, де E(х) ціла частина числа х.
Рис. 1 Схема алгоритму першого способу
Операція ділення виконується спочатку над операндом, а потім над часткою, що обчислюється на попередній ітерації циклу. Цикл організується блоками 3, 6 та виконується до одержання частки uk. У блоці 5 виводиться залишок від ділення кількості одиниць, який є черговою цифрою ai результату. остання, старша цифра результату (частка u) виводиться блоком 7.
Алгоритм визначення результату, починаючи зі старших розрядів, наведений на рис. 2 та виконує v=E(logkn) ітерацій (n розрядність паралельного коду). операція ділення кількості одиниць коду на ki (у блоці4)виконується спочатку над операндом, а потім над залишком, що обчислюється нею на попередній ітерації циклу.
Рис. 2 Схема алгоритму другого способу
У блоці 5 виводиться частка від ділення кількості одиниць, яка є черговою цифрою ai результату. Остання, молодша цифра результату (залишок u) виводится блоком 7.
Для одержання результату у двійково-кодованій СЧ необхідно кожну його цифру замінити на кількість її одиниць, що підраховується у двійковій СЧ.
Ділення кількості одиниць можна виразити через елементарну операцію.
Визначення .1. Елементарне ділення (кількості одиниць) на k обчислює один розряд частки.
Із визначення витікає обмежена розрядність n операнда елементарної операції, яка складається із k розрядів, що заміщується одиничним значенням частки та k-1 розрядів, які відповідають максимальному значенню залишка, який складає n=2k-1 біт.
Визначення .2. Операція ділення кількості одиниць на k, що виконується над операндом довільної розрядності, називається повнорозрядним діленням.
Визначення .3. Операція, що переміщує всі одиниці коду у його початок, а нулі в кінець, називається впорядкуванням одиниць коду, а одержаний код впорядкованим.
Теорема 2.1. Елементарне ділення на k впорядкованого коду a{12k-1} визначає частку q=a[k] та залишок r{1k-1}=a{1k-1}, якщо q=0 та r{1k-1}=a{k+12k-1}, якщо q=1.
Із теореми витікає спосіб виконання операції елементарного ділення на k, який містить в собі:
впорядкування одиниць коду a{12k-1} із одержанням впорядкованого коду a{12k-1} та частки q=a[k];
вибір залишку r{1k-1} за часткою q із молодшої a{1k-1} або старшої a{k+12k-1} частини впорядкованого коду.
Впорядкування одиниць коду виконується із використанням операцій довпорядкування одиниць.
Визначення .4. Бінарна операція DЕ(Ax, By) довпорядкування одиниць виконується над x- та y-розрядними впорядкованими кодами Ax=A{a, ... , ax}, By=B{b, ... , by}, xy та визначає впорядкований (x+y)-розрядний код Cx+y=C{c,...,cx+y} із сумарною кількостю одиниць кодів Ax, By: Cx+y= DЕ(Ax, By).
Теорема 2.2. Нехай Cx+y=DЕ(Ax, By), тоді розряд ciприймає одиничне значення у тому і тільки у тому випадку, якщо існує хоча б один із одиничних розрядів ai,bi або пара одиничних розрядів aj, bi-jкодів Ax, By із сумою індексів i:
ci = aix biy (aj bi-j),
де z=min(x, i-1, x+y-i+1) визначає верхню межу j кількість кон’юнкцій розрядів aj, bi-j для кожного значення i.
Теорема визначає спосіб виконання операції довпорядкування одиниць.
Операція вибору залишку із впорядкованого коду виконується порозрядно, j-й розряд залишку обчислюється за формулою
r{j}= q a{j} a{j+k}, j=1k-1, (1)
що для всієї операції вибору потребує 2(k-1) бінарних логічних операцій.
Таким чином, одержана багаторівнева модель вертикального додавання, у якій операція виконується за способами переведення чисел із однієї СЧ у іншу з використанням повнорозрядного ділення кількості одиниць. Повнорозрядна операція складається із елементарних ділень, елементарні операції із впорядкування одиниць та вибору залишку, а операція впорядкування із операцій довпорядкування одиниць, що виконуються на системах диз’юнктивних нормальних форм (ДНФ). Модель забезпечує єдиний підхід до проектування вертикальних АП, включаючи операції безпосереднього рахування одиниць діленням їх кількості на основу СЧ та операції, що переміщують одиниці їх впорядкуванням у паралельному коді.
У третьому розділі вдосконалюється операція впорядкування одиниць та розробляється метод проектування АП для впорядкування одиниць.
Теорема 3.1. Обсяг обчислень у операції впорядкування одиниць, що виконується над x-розрядним кодом через бінарні операції довпорядкування одиниць, не залежить від структури обчислювального процесу та складає
VUЕ(x) = x(x-1).
теорема обгрунтовує використання найшвидшої пірамідальної структури операції впорядкування одиниць при зберіганні обсягу обчислень.
Подальше розпаралелювання обчислень потребує використання багатомісцевої операції довпорядкування одиниць.
Визначення 3.1. Багатомісцева операція довпорядкування одиниць множини впорядкованих кодів обчислює впорядкований код сумарної розрядності та сумарної кількості одиниць кодів операндів.
спосіб виконання бінарної операції, що обгрунтований теоремою 2.2, поширюється на багатомісцеву операцію довпорядкування одиниць методом математичної індукції. Розряд ci результуючого коду обчислюється як диз’юнкція розрядів ai кодів операндів (при їх наявності) та всіх кон’юнкцій розрядів кодів операндів із сумою індексів i. У кон’юнкцію включається не більше одного розряду від одного операнда.
У багатомісцевій операції довпорядкування одиниць із збільшенням кількості операндів значно підвищується кількість термів ДНФ, для яких індекси розрядів залишаються незмінними, а змінюється із повним переліком їх належність до операндів. Множина таких термів позначена кодом термів, що складається із впорядкованих за зростанням номерів розрядів, з індексом, який дорівнює кількості термів.
Розроблена методика оцінки операції довпорядкування z впорядкованих x-розрядних операндів А.1x, ... , А.zx, що обчислює код Dzx= DE(А.1x, ... , А.zx).
Для оцінки обсягу обчислень:
визначається структура коду термів із використанням його розрядності tnz та двох множин параметрів: кількостей ai розрядів в i-й множині однакових індексів розрядів, i=1m1, m1z; кількостей bjмножин із однаковими ненульовими значеннями ai, i=1m2; m2 кількість таких множин, m2z. Наприклад, для коду термів 112 має місце розрядність tn=3, два параметри ai: a=2, a=1, та два параметри bj. b=1, b=1.
обчислюється індекс ta коду термів та кількість tb кодів термів заданої структури за формулами:
ta = , tb = ,
де , ,
знаходиться обсяг обчислень VDE як сума добутків tt=tntatb, що обчислюються для усіх різних структур кодів термів розрядностей tn=1z, за виключенням zx.
знаходиться обсяг обчислень у операції DE(А.1x, ..., А.zx, А.z+1g) довпорядкування z x-розрядних та g-розрядного впорядкованих кодів
VDE zx+g = VDE zx + g VDE zx+1,
де VDE zx+1 = (VDE (z+1)x - VDE zx)/x визначається при g=x.
методика дозволяє виводити формули для оцінки обсягу обчислень багатомісцевих операцій. Одержано формули для 3- та 4-місцевих операцій:
VDE x= 3x(x+2),
VDE x= 4x(x+3x+3).
Кількість рівнів логічних операцій оцінюється за формулою LДУ = ]loghf hd[+]loghf hc[,
де hc та hd максимальна кількість змінних у термі та термів у ДНФ, відповідно,
hc = tn, hd = VDE/(2(z-1)(x-1));
hf допустима кількість змінних, що об’єднуються по ТА, або у один рівень логічних елементів.
Визначений спосіб одержання множини альтернативних рішень, що передбачає використання операцій довпорядкування одиниць із ненаростаючою від рівня до рівня кількістю операндів.
Одержані способи виконання операцій впорядкування та довпорядкування одиниць визначають структуру однотактних АП впорядкувачів (ВО) та довпорядкувачів (ДО) одиниць, а також метод їх проектування. Початковими даними до проектування є розрядність коду, що впорядковується, параметр hf, що характеризує можливості елементної бази, а також показник витрат обладнання V або швидкодії L, який необхідно забезпечити у ВО. Програмна реалізація метода визначає множину структур ВО із ненаростаючою від рівня до рівня кількістю операндів ДО, дає оцінку цих ВО за витратами обладнання та швидкодією, впорядковує їх за зростанням витрат обладнання та відбраковує ВО при порушенні зростання швидкодії. Із одержаної множини альтернативних рішень виділяється кращий ВО за заданим показником V або L та видаються структури цього ВО та його ДО.
Метод дозволяє оцінювати відомі АП на належність до множини альтернативних рішень. Відомі АП впорядковують одиниці коду або на бінарних операціях довпорядкування одиниць, або на однім ДО, що реалізує крайній випадок багатомісцевої операції довпорядкування одиниць, коли операндами є окремі розряди коду. Метод виключає із розглядання АП на бінарних операціях довпорядкування одиниць, оскільки вони або мають повільну непірамідальну структуру, або виконують ДО із більшими витратами обладнання, та пропонує рішення, що поєднує в собі швидкодію пірамідальної структури із найбільш простою реалізацією ДО.
Впорядкування одиниць 16-розрядного коду при hf=20 виконується на ВО у 7 рівнів схеми на 240 двохвходових елементах ТА, АБО. У крайньому випадку, багатомісцева операція довпорядкування одиниць виконується у 5 рівнів, однак це відоме рішення потребує більше ніж 0,510 двохвходових елементів ТА, АБО. Метод виключає це рішення, пропонуючи таке ж підвищення швидкодії у ВО, що виконує 6-місцеву та дві 5-місцеві, а також на наступному рівні 3-місцеву операції довпорядкування одиниць на 956 двохвходових елементах ТА, АБО.
У четвертому розділі вдосконалюється операція ділення кількості одиниць на k та розроблюється метод проектування АП для ділення кількості одиниць.
Визначення .1. Код є частково-впорядкованим, якщо не є впорядкованим кодом та містить в собі нетривіальний (неоднорозрядний) впорядкований код.
Залишок від ділення кількості одиниць на k наслідує впорядкованість коду. У повнорозрядній операції ділення залишок використовується як частина операнда наступного елементарного ділення. такий операнд є частково-впорядкованим кодом, та у відношенні до нього доцільно використовувати операцію довпорядкування одиниць, яка більш проста за обсягом обчислень, що необхідний для часткового впорядкування коду. При використанні бінарних операцій довпорядкування обсяг обчислень елементарного ділення на k знижується вдвічі від 4k(k-1) до 2(k+2)(k-1). Зменшується кількість рівнів схеми. При використання багатомісцевої операції обсяг обчислень скорочується багаторазово.
Подальше розпаралелювання обчислень забезпечується виконанням елементарного ділення як єдиної операції без її розбиття на операції впорядкування одиниць та вибору залишку, що виконуються послідовно. Єдина операція описується множиною ДНФ, які виконуються одночасно та виводяться підстановкою формул для обчислення розрядів впорядкованого коду багатомісцевою операцією довпорядкування одиниць у формулу (1) для обчислення розрядів залишку, а також ДНФ для визначення частки.
Обсяг обчислень єдиної операції елементарного ділення визначається за формулою
VЕП.є = ((+ )(k+i)) - k- k.
Виконання єдиної операції елементарного ділення у два рівні логічних операцій можливо при hdhf, де
hd = + .
Наприклад, для k=2 обсяг обчислень складає VЕП.є=11 бінарних логічних операцій. Виконання операції у два рівні обмежується hd=4, тобто можливо при hf4. у єдиній операції елементарного ділення на k=3 VЕП.є=182, а hd=25.
У повнорозрядному діленні кількості одиниць на k>2 перший рівень виконується на елементарних операціях над довільними операндами, а наступні рівні над частково-впорядкованими операндами, що включають до себе впорядковані залишки попередніх елементарних ділень. Повне використання впорядкованості залишків знижує обсяг обчислень повнорозрядного ділення на 25% при впорядкуванні одиниць на бінарних операціях довпорядкування та багаторазово на багатомісцевих операціях. При виконанні на першому рівні xxa елементарних операцій, xa=(n+1)/(2k) досягається повне використання впорядкованності залишків та незмінний обсяг обчислень у різних структурах повнорозрядного ділення. При x>xa досягається найменша кількість рівнів схеми, але розряди частини залишків (не більше ніж xb-xa, xb=n/(2k-1)) розподіляються між різними операндами, що призводить до несуттєвого збільшення обсягу обчислень.
Теорема 4.1. Обсяг обчислень у повнорозрядній операції ділення кількості одиниць n-розрядного коду на k не залежить від структури обчислювального процесу при x xa та не суттєво залежить при x>xa.
Теорема обгрунтовує вибір найшвидщої пірамідальної структури із максимальним значенням xпри практично фіксованому обсязі обчислень.
Найменша кількість рівнів у повнорозрядному діленні досягається при виконанні єдиної операції без її розбиття на елементарні ділення. Спосіб виконання єдиної операції передбачає впорядкування одиниць операнда із визначенням коду частки q{1x}, x=E(n/k) та вибір із впорядкованого коду a{1n} розрядів коду залишку за формулою
r{j}= (a{j+(i-1)k}q{i}) a{j+xk}.
Розроблені способи виконання операцій елементарного та повнорозрядного ділення визначають АП для реалізації цих операцій елементарні (ЕП) та повнорозрядні (ПП) поділювачі кількості одиниць на k та метод їх проектування.
Елементарний поділювач кількості одиниць на k ЕП/k, що виконує операцію над довільним операндом на ВО 1 і вузлі вибору 2 (комутатор К), а також ПП на ЕП/k 1, 2 і 3 показані на рис. 3, а і б, відповідно.
а) б)
Рис. 3. поділювачі кількості одиниць на k :
а елементарний поділювач ЕП/k, б повнорозрядний поділювач ПП/k
Способи одержання альтернативних рішень по елементарному та повнорозрядному діленнях кількості одиниць полягають у формуванні множини операцій на основі альтернативних рішень попереднього рівня моделі вертикального додавання та доповненні єдиними операціями. Для повнорозрядного ділення кожний попередній рівень структури виконується у порівнянні з наступним рівнем на тих же або більш простих елементарних операціях.
Розроблений метод проектування ПП та його програмна реалізація дозволяють перевіряти відомі пристрої на їх належність до множини альтернативних рішень та одержувати нові альтернативні рішення з підвищеною швидкодією.
півсуматор та повний двійковий додавач є ЕП на 2. Метод дає відомі схеми цих АП, використовуючи ВО та ДО, або єдину операцію елементарного ділення, що підтверджує його справедливість.
У п’ятому розділі вдосконалюється виконання операції вертикального додавання. Запропоновано дві головні структури вертикального додавача, що виконуються за першим та другим способами, а також три структури двійкового вертикального додавача, що виходять з головних структур.
вертикальний додавач, що працює за першим способом, містить послідовно об’єднані ПП кількості одиниць на k. Основний обсяг обчислень операції вертикального додавання збігається у першому ПП. Кількість рівнів ЕП визначається за їх кількостю у першому ПП та кількостю наступних ПП.
Досліджено вертикальний додавач, що працює за першим способом із використанням єдиних операцій повнорозрядного ділення. Показано, що він збігається із пристроєм, що виконується за другим способом та спрощується до структури, яка містить ВО операнда та блок вибору. Впорядкування одиниць всього операнда суттєво підвищує швидкодію при значному збільшенні витрат обладнання у порівнянні із вертикальним додавачем на ЕП.
Перша структура двійкового вертикального додавача безпосередньо витікає з першої головної структури при k=2. Ця структура відома і має найменші витрати обладнання та швидкодію.
У двох наступних структурах двійкового вертикального додавача запропоновано розпаралелювання обчислень підвищенням основи СЧ.
У другій структурі знижується кількість рівнів схеми виконанням операції за першим способом у двійково-кодованих СЧ. Для n=15 використання двійково-четвіркової СЧ зменшує кількість рівнів схеми на 10% при збільшенні обсягу обчислень у 2,94 разів.
Третя структура двійкового вертикального додавача виконується за другим способом, що стосовно двійковій СЧ перетворює ПП до ЕП, та, як і у головній структурі, зводиться до двох блоків: ВО операнда та блока вибору.
Виконання ВО за розробленим методом проектування ВО із використанням запропонованих багатомісцевих операцій довпорядкування одиниць приводить до значного підвищення швидкодії за межі відомих рішень. Для операнда із розрядностю n=15 кількість рівнів схеми зменшується на 40% (при зростанні обсягу обчислень у 6,4 разів).
Спосіб одержання альтернативних рішень для вертикального додавання, що виконується на ЕП, грунтується на зменшенні кількості рівнів схеми у останніх рівнях ЕП при виконанні АП за першою головною структурою та доповненні і відбракуванні рішень, що складаються за другою головною структурою на базі альтернативних рішень по проектуванню ВО.
Сукупність способів одержання альтернативних рішень, що розроблені для всіх рівнів моделі вертикального додавання об’єднується у методику одержання альтернативних рішень, яка використовується у методах проектування вертикальних АП.
Оптимізація вертикального додавання виконана на всіх рівнях моделі, забезпечує розпаралелювання обчислень та спрощення операцій, що базуються на:
доказаних теоремах про незалежність обсягу обчислень від структури обчислювального процесу;
використанні наслідування впорядкованості одиниць кодів;
збільшенні та об’єднанні операцій;
методиці одержання альтернативних рішень.
Різноманітність форм та напрямків оптимізації вертикальних операцій визначають ефективність розроблених методів проектування вертикальних АП.
У експериментальній частині досліджуються ВО, що використовуються в усіх вертикальних АП та визначають їх витрати обладнання і швидкодію.
Для множини рішень на основі пірамідальної структури ВО утворено 5 моделей для проектування на ПЛІС FPGA ХС4000 фірми Xilinx. У результаті моделювання їх роботи одержані оцінки реальних витрат обладнання та швидкодії. Порівняння розрахункових та експериментальних оцінок ВО підтвердило достовірність використання розрахункових оцінок для визначення альтернативних рішень у розроблених методах проектування вертикальних АП.
Висновки
. Проектування вертикальних АП суттєво ускладнено труднощами вибору найкращого рішення за заданою швидкодією або витратам обладнання внаслідок різнорідності структур та обмеженого переліку рішень, що витікає з недостатнього вивчення їх структурної організації, питань розпаралелювання обчислень у вертикальних операціях із урахуванням можливостей елементної бази та обмеження рішень використанням двійкової СЧ.
2. запропоновано багаторівневу модель виконання вертикального додавання за способами переведення чисел із однієї СЧ в іншу, що забезпечує єдиний підхід до проектування вертикальних АП. Визначено операції повнорозрядного та елементарного ділення кількості одиниць, впорядкування та довпорядкування одиниць, що виконуються на рівнях моделі. Розроблено способи їх виконання.
3. Для операцій впорядкування одиниць на бінарних ДО та повнорозрядного ділення на ЕП доказана незалежність обсягу обчислень від їх структури, що забезпечило підвищення швидкодії ВО та ПП при фіксованих витратах обладнання за рахунок обгрунтованого вибору швидких пірамідальних структур.
4. Визначено багатомісцеву операцію довпорядкування одиниць, що підвищує швидкодію ВО при збільшенні обсягу обчислень. Розроблено спосіб виконання операції та методику оцінки її показників. Для 15-розрядного коду швидкодія підвищена у 1,4 рази. Із зростанням розрядності коду виграш у швидкодії збільшується. Впорядкування одиниць є основним змістом ЕП, ПП та вертикального додавача, визначає їх показники та переносить на них виграш у швидкодії.
5. Визначено та виявлено у вертикальних АП часткову впорядкованість кодів, використання якої спрощує ПП та вертикальний додавач на 25% при використанні бінарних ДО та багаторазово на багатомісцевих ДО.
6. Розроблено способи виконання єдиних операцій елементарного та повнорозрядного ділень, що знижує кількість рівнів у структурах операцій та підвищує швидкодію ЕП та ПП.
7. запропоновано вертикальне додавання, що виконується у СЧ із підвищеною основою. У двійково-четвірковій СЧ швидкодію підвищено на 10%, а за другим способом виконання вертикального додавання на ВО та блока вибору на 40%.
8. Розроблено методику одержання множини альтернативних рішень, що виключає варіанти АП, які поступаються іншим одночасно і за витратами обладнання і за швидкодією.
9. Розроблено методи проектування ВО, ПП та вертикального додавача, а також програмну реализацію методів, що дозволяють оцінювати відомі рішення на їх належність до множини альтернативних рішень та будувати нові АП, що перевищують відомі за показниками швидкодії та (або) витрат обладнання.
10. Результати роботи впроваджені у навчальний процес ОДПУ, програмна реалізація методів проектування вертикальних АП використана в Українському НДІ радіо та телебачення для розробки цифрового фільтру системи сполучення аналогових радіорелейних ліній з цифровими системами передавання.
Список праць, що опублІковані автором за темою дисертації
1. Дрозд А.В., Паулин О.Н., Дрозд Ю.В. выполнение операции вертикального сложення в арифметических устройствах // Тр. Одес. политехн. ун-та. Одесса, 1997. № 2 С. 30 - 32.
2. Дрозд Ю.В. Операция упорядочения единиц в параллельном коде // Тр. Одес. политехн. ун-та. Одесса, 1998. Вып. 2. С. 38 - 39.
3. Дрозд Ю.В. Выполнение вертикальных арифметических операций в двоично-кодированных системах счисления // Тр. Одес. политехн. ун-та. Одесса, 1999. Вып. 1. С. 211 - 213.
4. Паулин О.Н., Дрозд Ю.В. К вопросу о синтезе вертикального сумматора // Научные тр. молодых ученых Одес. политехн. ун-та. Одесса, 1997. С. 117 - 119.
5. Паулин О.Н., Дрозд Ю.В. О синтезе логических модулей, описываемых симметрическими функциями // Ученые записки Симфероп. гос. ун-та. Винница Симферополь, 1998. Спецвып. С. 189 - 192.
6. Дрозд Ю.В., Паулин О.Н., Дрозд А.В. Синтез и обнаружение отказов в вертикальном сумматоре // Информационно-управляющие системы на железнодорожном транспорте 1997 №4. С. 27.
7. А. с. 1751746 СССР, МКИ G 06 F 7/38. Устройство для упорядочения единиц / А.В. Дрозд, Е.Л. Полин, Т.П. Мельничук, Ю.В. Дрозд (СССР). №4885626; Заявлено 26.11.90; Опубл. 30.07.92, Бюл. № 28. 6 с.
8. А. с. 1751749 СССР, МКИ G 06 F 7/52. Устройство для подсчета количества единиц в двоичном числе / А.В. Дрозд, Е.Л. Полин, Т.П. Мельничук, Ю.В. Дрозд (СССР). №4905767; Заявлено 10.12.90; Опубл. 30.07.92, Бюл. № 28. 4 с.
9. А. с. 1829119 СССР, МКИ Н 03 М 7/04. Устройство для подсчета количества единиц/А.В.Дрозд, Е.Л.Полин, Т.П.Мельничук, Ю.В.Дрозд (СССР). №4878857; Заявлено 30.10.90; Опубл. 23.07.93, Бюл. № 27. 8 с.
Дрозд Юлія Володимирівна. Методи та пристрої для виконання вертикальних арифметичних операцій. Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальностю 05.13.05 Елементи та пристрої обчислювальної техніки та систем керування. Одеський державний політехнічний університет, Одеса, 2000.
Дисертацію присвячено питанням проектування арифметичних пристроїв для вертикальної обробки даних. У дисертації розроблено багаторівневу модель виконання операції вертикального додавання, що підсумовує кількість одиниць паралельного коду з використанням способів перекладу чисел із однієї системи числення в іншу. Визначено операції ділення кількості одиниць та впорядкування одиниць, а також способи їх виконання на рівнях моделі. На підставі моделі запропоновані методи проектування пристроїв для впорядкування одиниць, ділення кількості одиниць та вертикального додавання. Ці методи дозволяють оцінювати відомі рішення та одержувати нові, що перевищують відомі за швидкодією та (або) витратами обладнання. Результати роботи використані у розробці арифметичного блоку системи цифрової обробки сигналів та впроваджені у навчальний процес університету.
Ключові слова: арифметичні пристрої, вертикальна обробка даних, проектування, системи числення.
Drozd Julia Vladimirovna. Methods and devices for Execution of vertical arithmetic operations. Manuskript.
Dissertation on competition of scientific degree of Ph. D by spesiality 05.13.05 Elements and devices of computer’s equipment and control systems. Odessa state polytechnical university. Odessa, 2000.
The dissertation is devoted to design of arithmetic devices for vertical data processing.Multilevel model of vertical addition execution that computes number of one’s with use of methods the number translation from each numerical system to other is elaborated. one’s number division and one’s sequencing operations and their execution methods are defined. the methods of design the devices for one’s sequencing, one’s number dividers and vertical adder on the base of the model are suggested. That methods permit to estimate known solution and to design a new devices which improov known solutions by highspeed and (or) hardware amount. The results of the work are used in arithmetic block of digital signal processing system and application into university education process.
Key words: arithmetic devices, vertical data processing, design, numerical systems.
Дрозд Юлия Владимировна. Методы и устройства для выполнения вертикальных арифметических операций. Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 Элементы и устройства вычислительной техники и систем управления. Одесский государственный политехнический университет, Одесса, 2000.
Диссертация посвящена вопросам проектирования арифметических устройств (АУ) для вертикальной обработки данных.
основной вертикальной операцией является вертикальное сложение, заключающееся в подсчете количества единиц в параллельном коде, составленном из разрядов одного веса множества чисел. Анализ известных подходов к ее выполнению выявил две группы решений: осуществляющие подсчет единиц непосредственно и путем изменения расположения единиц кода. Использование вертикальных сумматоров с различным быстродействием, а также рост затрат оборудовання АУ, значительно обгоняющий повышение быстродействия, определили целесообразность поиска множества альтернативных решений, выгодно отличающихся друг от друга или быстродействием или затратами оборудования.
В диссертации разработана многоуровневая модель выполнения операции вертикального сложения по способам перевода чисел из одной системы счислення (СС) в другую с использованием операции деления количества единиц на основание, обеспечивающая единый подход к проектированию вертикальных АУ. Определены операции элементарного (ЭД) и полноразрядного (ПД) деления количества единиц на основание k, вычисляющие один разряд или код частного соответственно при ограниченной 2k-1 и произвольной разрядности операнда. Определена операция упорядочения единиц (УЕ), перемещающая единицы кода в его начало, и бинарная операция доупорядочения единиц (ДЕ), объединяющая в упорядоченный код два упорядоченных кода. Доказана теорема, определяющая способ выполнения ЭД на k путем УЕ операнда и выбора остатка. Разработан способ выполнения ПД на ЭД, операндами которых являются разряды исходного кода или разряды остатков предыдущих ЭД. Доказана теорема, определяющая способ выполнения бинарной операции ДЕ на системе дизъюнктивных нормальных форм.
Доказана теорема о независимости объема вычислений от структуры операции УЕ, что обосновало выбор наиболее быстрой пирамидальной структуры в пределах фиксированных затрат оборудования.
Для дальнейшего повышения быстродействия введена многоместная операция ДЕ. Разработан способ ее выполнения и методика оценки, позволяющая выводить формулы для определения объема вычислений и способ получения множества альтернативных решений.
Разработан метод проектирования АУ для упорядочения единиц, использующий многоместные операции ДЕ. Программная реализация метода позволяет оценивать известные АУ на их принадлежность ко множеству альтернативных решений и получать новые АУ с лучшими показателями. Для 15-разрядного кода быстродействие повышено в 1,4 раза. С увеличением разрядности кода выигрыш в быстродействии повышается.
Операция УЕ является основным содержанием других вертикальных операций (деление количества единиц, вертикальное сложение), определяет их показатели и переносит на них выигрыш в быстродействии.
Доказана теорема, обосновывающая использование быстрой пирамидальной структуры ПД.
Остатки деления наследуют упорядоченность кодов, из которых они выделяются, и образуют частично-упорядоченный код операнда следующего деления. За счет частичной упорядоченности кодов снижены затраты оборудовання вертикальных сумматоров на 25% и многократно соответственно при использовании бинарных и многоместных операций ДЕ.
Для повышения быстродействия разработаны ЭД, объединяющее УЕ и выбор остатка, и единая операция ПД (без разбиення на ЭД).
Предложен способ получения альтернативных решений и программно реализованный метод проектирования АП для деления количества единиц, позволяющий выбрать из множества альтернативных решений лучшее по заданным затратам оборудовання или быстродействию. Метод оценивает известные решения и дает известные схемы полусумматора и полного сумматора, выполняющие ЭД на 2, что подтверждает его справедливость,
Предложено вертикальное сложение, выполняемое в СС с повышенным основанием. в двоично-четверичной СС быстродействие увеличено на 20%. Использование единой операции ПД повышает быстродействие на 40% при большем увеличении затрат оборудовання.
В экспериментальной части проведено исследование VHDL –моделей АУ для упорядочения единиц при проектировании на FPGA ХС4000 фирмы Xilinx. Моделирование показало совпадение расчетных и экспериментальных данных по получению множества альтернативных решений.
Результаты работы внедрены в учебный процесс университета и использованы в разработке арифметического блока системы цифровой обработки сигналов.
Ключевые слова: арифметические устройства, вертикальная обработка данных, проектирование, системы счисления.
1