Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ
СИНЕГУБ Микола Іванович
УДК 004.315
МЕТОДИ СТРУКТУРНОГО СИНТЕЗУ БАЗОВИХ АРИФМЕТИЧНИХ ФУНКЦІОНАЛЬНИХ ПРИСТРОЇВ З ПІДВИЩЕНОЮ ШВИДКОДІЄЮ
Спеціальність 05.13.05 —Елементи та пристрої обчислювальної техніки
та систем керування
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Одеса –
Дисертацією є рукопис.
Робота виконана на кафедрі “Системне програмне забезпечення”
Одеського національного політехнічного університету Міністерства освіти
і науки України.
Науковий керівник кандидат технічних наук, доцент
Паулін Олег Миколайович,
Одеський національний політехнічний
університет, професор кафедри системного
програмного забезпечення
Офіційні опоненти: доктор технічних наук, професор
Лужецький Володимир Андрійович,
Вінницький державний технічний
університет, завідувач кафедри “Захист
інформації”;
доктор технічних наук, професор
Ситніков Валерій Степанович,
Одеський національний політехнічний
університет, професор кафедри “Комп’ютерні
системи”
Захист відбудеться “27” вересня 2007 року о 13 на засіданні
спеціалізованої вченої ради Д 41.052.01 в Одеському національному
політехнічному університеті за адресою: 65044, м. Одеса, проспект
Шевченка, 1, ауд. 400-А.
З дисертацією можна ознайомитись в бібліотеці Одеського національного
політехнічного університету за адресою: 65044, м. Одеса, проспект
Шевченка, 1.
Автореферат розісланий “ 25 ” серпня 2007 р.
Вчений секретар
спеціалізованої вченої ради Ямпольський Ю.С.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Безперервне ускладнення задач, які необхідно вирішувати на сучасному етапі при науково-технічних розрахунках, при автоматизації проектування і моделювання складних об’єктів та систем, при складанні прогнозу погоди та інше, потребує обробки даних значного обсягу. Це, в свою чергу, вимагає постійного зростання продуктивності цифрових обчислювальних систем, що може бути забезпечено, зокрема, підвищенням швидкодії їх операційних пристроїв.
Відомі апаратні методи алгоритмізації, поєднання в часі мікрооперацій, заготовлення попередніх результатів, розпаралелення підпроцесів обробки даних є потужними засобами підвищення швидкодії операційних пристроїв і цифрових систем в цілому. Ці методи успішно застосовуються при побудові більш швидкодіючих пристроїв, призначених для підсумовування двох операндів.
Сучасним напрямком підвищення швидкодії операційних пристроїв є також багатооперандна обробка масивів даних; при цьому пристрої можуть виконувати як відносно прості операції типу підсумовування/віднімання, так і більш складні операції типу множення і множення/підсумовування.
Для адекватного опису процесу багатооперандної обробки даних найбільш прийнятним є апарат симетричних булевих функцій (СФ), оскільки цей процес має природню симетрію відносно біт операндів розряду, який розглядається.
Важливий внесок в розвиток теорії проектування цифрових операційних пристроїв внесли як вітчизнянні вчені: Лебедєв С.А., Глушков В.М., Майоров С.О., Черкаський М.В., Дрозд О.В., Тарасенко В.П., так і закордонні вчені: Джон фон Нейман, К.С. Уоллес, А.Б. Глассер і інш.
Однак спроектовані на основі відомих методів цифрові операційні пристрої вже не задовольняють все зростаючим вимогам по швидкодії. Тому проблема розробки нових методів проектування цих операційних пристроїв, а також розробки нових та вдосконалення відомих методів виконання арифметичних операцій є досить важливою і актуальною.
Зв’язок роботи з науковими програмами, планами, темами. Напрямки дисертаційної роботи, пов’язані з розробкою пакету прикладних програм для автоматизації проектування арифметичних пристроїв, виконувалися в межах планових науково-дослідницьких робіт кафедри системного програмного забезпечення Одеського національного політехнічного університету (ОНПУ): № 329-73 ІПрограмні засоби автоматизованих систем. Розробка та дослідження методів та засобів автоматизованих системІ (держ. рег. № 0100U001400); № 539-73 Методи та засоби побудови автоматизованих систем переробки інформації і управління.
Мета роботи та задачі дослідження. Метою дисертаційної роботи є розробка методів структурного синтезу базових арифметичних функціональних пристроїв (АП) цифрової обчислювальної техніки, а саме: підсумовуючих, помножуючих і помножуючих/підсумовуючих пристроїв для підвищення їх швидкодії на основі алгоритмізації різних варіантів операцій підсумовування та помноження на базі розпаралелювання мікрооперацій, попередньої підготовки результатів та використання апарату СФ. Для досягнення поставленої мети розв’язуються наступні задачі:
Об'єктом дослідження є процес обробки даних в пристроях цифрової обчислювальної техніки.
Предметом дослідження є методи структурного синтезу і шляхи підвищення швидкодії арифметичних пристроїв цифрової обчислювальної техніки.
Методи досліджень. Розробка алгоритмічного та табличноалгоритмічного методів структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою базується на прикладній теорії цифрових автоматів; основах схемотехнічного проектування цифрових схем.
Розробка алгоритмічних методів структурного синтезу помножувачів цілих чисел, помножувачів/суматорів цілих чисел базується на прикладній теорії цифрових автоматів; основах схемотехнічного проектування цифрових схем; булевій алгебрі, включаючи розділ симетричних функцій.
Наукова новизна одержаних результатів роботи полягає в наступному:
Практичне значення одержаних результатів. На основі запропонованого алгоритмічного методу запроектована низка швидкодіючих підсумовуючих пристроїв чисел з плаваючою комою, у яких швидкодія збільшена на 40 % в порівнянні з відомими рішеннями.
На основі запропонованого алгоритмічного методу запроектована низка швидкодіючих помножувачів цілих чисел, у яких в залежності від розрядності операндів швидкодія операції помноження збільшується до 15 % в порівнянні з відомими рішеннями.
Розроблені методи структурного синтезу арифметичних пристроїв дозволяють формалізувати та автоматизувати низку етапів проектування найбільш поширених класів цих пристроїв підсумовуючих пристроїв і помножувачів, а також помножувачів/суматорів підвищеної швидкодії.
Пристрої за авторськими свідоцтвами № 1290300 “Устройство для суммирования двух чисел с плавающей запятой” і № 1348825 “Устройство для суммирования чисел с плавающей запятой” упроваджено на підприємстві п/с Р6533.
Основні положення, виводи та рекомендації, що наведені у дисертаційній роботі, планується використати в НДЕКР по розробці та створенню програмно-технічних комплексів на ВАТ “Елемент”, та використовуються у навчальному процесі ОНПУ в дисципліні “Паралельні обчислювальні процеси”, що викладається на кафедрі “Системне програмне забезпечення” для студентів фаху 8.080403 “Програмне забезпечення автоматизованих систем”.
Особистий внесок здобувача. Автору належать наступні наукові розробки: алгоритмічний метод структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою [4, 5, 7, 8], викладений в авторських свідоцтвах та патентах [12, 13, 16, 18, 20]; табличноалгоритмічний метод структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою, викладений в авторському свідоцтві [15]; алгоритмічний метод структурного синтезу помножувачів цілих чисел [3], викладений в патенті [21]. В співавторстві розроблено: алгоритмічний метод структурного синтезу швидкодіючих помножувачів/суматорів цілих чисел [1, 6, 9, 11], викладений в авторському свідоцтві і патентах [14, 17, 19]; метод перемноження двох цілих чисел на основі нарізного підсумовування сум часткових добутків і виникаючих при цьому перенесень на всіх рангах, за винятком останнього [2, 10].
Апробація роботи. Результати роботи доповідалися та обговорювалися на міжнародних конференціях: “Автоматика –” (Львів, 2000 р.), “Автоматика –” (Одеса, 2001 р.), “Розвиток наукових досліджень “2005”” (Полтава, 2005 р.).
Публікації. За темою дисертації опублікована 21 друкована робота, із них 5 –в спеціалізованих виданнях відповідно списку ВАК України; у тому числі 10 авторських свідоцтв і патентів на винаходи.
Структура й обсяг дисертації. Дисертаційна робота складається із вступу, 4 розділів, висновків та 6 додатків. Обсяг дисертації 116 стор., додатків 20 стор. Дисертація містить 64 рисунки і 3 таблиці та посилання до 88 літературних джерел.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обгрунтована актуальність теми дисертації; сформульована мета роботи і задачі досліджень; наведені основні положення, що виносяться на захист; викладені основні наукові та практичні результати роботи.
В першому розділі АНАЛІЗ ВІДОМИХ МЕТОДІВ І ТЕХНІЧНИХ РІШЕНЬ, ЩО ЗАСТОСОВУЮТЬСЯ ПРИ ПРОЕКТУВАННІ ОПЕРАЦІЙНИХ ПРИСТРОЇВ наведено огляд відомих методів і технічних рішень, що застосовуються при проектуванні цифрових операційних пристроїв.
Розглянуті апаратні методи проектування пристроїв цифрової обчислювальної техніки, які діляться на три класи: алгоритмічні, табличні і табличноалгоритмічні.
В розділі розглядаються і аналізуються відомі структури операційних пристроїв процесорів. Приводяться способи підвищення продуктивності арифметичних пристроїв. Розглядаються питання апаратно-програмної реалізації обчислень і засобів автоматичного проектування пристроїв обчислювальної техніки.
Відомим класичним прикладом обчислювальної системи з конвеєрним операційним пристроєм є ЕОМ Star100 фірми CDC. В розділі розглянуто спрощену структуру пристрою ЕОМ Star100, що виконує з використанням двословного комбінаційного суматора мікрооперації макрооперації підсумовування чисел з плаваючою комою послідовно. Даний пристрій при несуттєвих апаратних витратах має невисоку швидкодію, що є його вадою.
В розділі проаналізований фрагмент відомого, одного із найбільш швидкодіючих серед матричних помножувачів, багатошарового матричного помножувача з використанням однорозрядних повних суматорів. Згортання значень початкової матриці в даному помножувачі відбувається за
υ = logn (1)
етапів (шарів) (n число розрядів у співмножниках).
Один із відомих методів перемноження в доповняльних кодах, що розглянутий в розділі, базується на зображенні доповняльного коду у вигляді позиційного числа з додатними вагами у всіх його коефіцієнтів, окрім знакового розряду, що має від’ємний ваговий коефіцієнт:
Адоп = an2n + . (2)
В розділі наведені короткі теоретичні відомості про симетричні булеві функції, і представлена структура n-розрядного чотириоперандного суматора, спроектованого на базі СФ. Різні за структурою багаторозрядні багатооперандні суматори можуть використовуватися для покриття матриці часткових добутків при перемноженні цілих чисел.
В розділі розглянута низка арифметико-логічних пристроїв (АЛП) ЕОМ. Якщо в АЛП кожна макрооперація виконується окремим операційним пристроєм, то кількість операційних пристроїв в такому АЛП збігається з числом макрооперацій, які виконуються ним, що є його вадою. При апаратному суміщенні декількох функцій число операційних пристроїв в АЛП зменшується, і це спрощує структуру АЛП.
Із проведеного в розділі аналізу робиться висновок, що існуючі методи проектування пристроїв певного класу, а саме: підсумовуючих пристроїв чисел з плаваючою комою, помножувачів та помножувачів/суматорів цілих чисел, не в повній мірі забезпечують їх швидкодію. Тому для подальшого підвищення швидкодії обчислювальних систем необхідна постійна розробка нових ефективних методів проектування даних пристроїв.
Також на основі проведеного аналізу в розділі поставлені задачі для дослідження з метою підвищення швидкодії даних пристроїв.
В другому розділі МЕТОДИ СТРУКТУРНОГО СИНТЕЗУ ШВИДКОДІЮЧИХ ПІДСУМОВУЮЧИХ ПРИСТРОЇВ в якості критерію ефективності спроектованих в дисертації АП запропоновано вважати їх високу швидкодію за умови прийнятих апаратних витрат.
На основі запропонованого в співавторстві табличного методу, що використовує таблиці значень розрядних індексів СФ, в розділі спроектовано М-слівний N-розрядний суматор типу MN з паралельним переносом. При цьому оригінальна таблиця значень розрядних індексів СФ для переносів Рi, де i номер розряду, 2 i N + K; К кількість додаткових переносів, К визначається рівнянням
М = 2К+1 К 1, (3)
складається наступним чином. В кожному рядку повинні бути такі значення розрядних індексів, що їх двійково-зважена сума дає число, в двійковому еквіваленті якого з’являється “1” в i-ому (інколи, крім того, в (i+1)-ому) розряді. Особливим випадком є СФ S = F(1, 3, ..., R), тобто часткова сума складових i-го розряду. При цьому, якщо М парне, то
R = (4)
якщо М непарне, то R = M для всіх розрядів. Функції S є функціями непарності.
На рис. 1 наведена узагальнена структура пристрою для підсумовування М N-розрядних чисел типу MN. Даний пристрій реалізує паралельний спосіб підсумовування і по числам, і по розрядам, виробляючи одночасно перенесення в усі розряди, які додаються на суматорах по модулю 2 з порозрядними сумами.
Рис. 1. Структура суматора M N-розрядних чисел
На входи перетворювачів кодів (ПК) X/Yi i-го розряду (i = ) даного пристрою надходять коди М складових Аi. Окрім того, на ПК перших К розрядів надходять коди вхідних однорозрядних перенесень Еi (для i К). ПКi виробляє Li кодів симетричних функцій, що створюють сукупність Ci, в тому числі код часткової суми Si’. Коди Ci з виходів ПКi одночасно надходять до відповідних входів елементів І-АБО відповідних логічних схем (ЛС). На виходах ЛС створюються коди перенесень Р в 2-й, ..., N-й розряди, а також вихідних перенесень Q в (N+1)-й, ..., (N+K)-й розряди. Коди Pi і Si’додаються на суматорі за модулем 2 (=1), так що на його виході створюється код результуючої суми Si даного розряду.
Рис. 2. Структура трисловного n-розрядного суматора Глассера
Розглянуто запропонований в співавторстві табличний метод синтезу трислівного багаторозрядного суматора з наскрізним перенесенням Глассера. Особливістю перенесення Глассера є його представлення двома бітами одинакової ваги Ci і C'i. На рис. 2 наведена m-каскадна структура такого суматора для трьох n-розрядних складових. Функціонування каскаду описується модернізованою автором таблицею, в якій представлена однознача відповідність сумарної ваги складових (СВС)Q каскаду значенням його порозрядних біт суми і біт вихідних перенесень. Особливість таблиці полягає в тому, що ці значення згруповані таким чином, що при одному значенні СВС розглядається 3 варіанти кодування біт вхідного перенесення: 00, 01, 11.
В розділі запропоновано алгоритмічний метод структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою, який характеризується наступними властивостями:
паралелизмом деяких мікрооперацій макрооперації підсумовування чисел з плаваючою комою;
підготовкою визначених проміжних результатів "класичної" процедури знаходження суми двійкових чисел з плаваючою комою;
вибором потрібного результату за ознакою.
В розділі запропонована низка структур підсумовуючих пристроїв чисел з плаваючою комою, спроектованих на основі даного методу.
Найбільш швидкодіючим із запропонованих підсумовуючим пристроєм двох чисел з плаваючою комою, побудованому на комбінаційних суматорах цілих чисел, є пристрій СУ1, структура котрого наведена на рис. 3. В ньому підвищення швидкодії досягається за рахунок поєднання в часі мікрооперацій знаходження модуля вирівнюючої різниці (ВР) і підготовки усіх можливих попередніх 2n-розрядних сум мантис складових в кількості (2n + 2) (де n розрядність мантис складових). Розрахунки показують, що підсумовуючий пристрій, який розглядається, на 40 % швидше підсумовуючого пристрою ЕОМ Star100.
Рис. 3. Структура підсумовуючого пристрою СУ1
В розділі запропоновано таблично-алгоритмічний метод структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою на основі таблиць значень попередніх сум. Даний метод полягає в:
складанні таблиць значень попередніх сум в різних кодах;
розбиванні ПЗП на блоки для зберігання таблиць (об’єм ПЗП пропорційний n 2n, де n розрядність мантис складових);
виборі необхідної попередньої суми за ознакою.
Застосування блоків ПЗП дозволяє, завдяки зберігаємих в них складених необхідним чином таблицям значень попередніх сум, розширити функціональні можливості підсумовуючого пристрою. Наприклад, в залежності від заданого режима роботи даний пристрій може виконувати одну із операцій: А В, В А (де А, В –операнди, що обробляються) як в прямому, так і в зворотному або доповняльному кодах. Структура спроектованого на основі даного методу пристрою, що вміщує (2n + 2) (n розрядність мантис складових) блоків ПЗП, показана на рис. 4. В даному пристрої мантиси чисел А і В надходять на перші та другі адресні входи блоків ПЗП №№ 5 (2n + 6) відповідно. Код, що встановлений на управляючих входах пристрою, дешифрується в блоці 3 та надходить на треті адресні входи всіх блоків ПЗП, задаючи таким чином режим роботи пристрою. Вибрана в блоці (2n + 7) за значенням знаку і модуля ВР попередня сума мантис в блоці (2n + 8) нормалізується і видається на вихід пристрою. В цьому ж блоці корегується і порядок результату підсумовування.
Рис. 4. Структура підсумовуючого пристрою на основі ПЗП
В пристрої можливе подальше секціонування блоків ПЗП з метою підвищення їх швидкодії.
Запропоновані в розділі підсумовуючі пристрої чисел з плаваючою комою порівнюються за часовими характеристиками і апаратними витратами. Так, при розрядності мантиси числа, що дорівнює 24 розрядам, і розрядності порядка числа, що дорівнює 8 розрядам, апаратні витрати, визначені за методом Квайна, у підсумовуючого пристрою СУ1 приблизно в десять разів більше, ніж у підсумовуючого пристрою ЕОМ Star100. Інші запропоновані підсумовуючі пристрої потребують менше апаратних витрат.
В просторі критеріїв “Затримка –Апаратні затрати” запропоновані пристрої розташовуються згідно з принципом оптимальності за Парето.
В третьому розділі МЕТОДИ СТРУКТУРНОГО СИНТЕЗУ ШВИДКОДІЮЧИХ ПОМНОЖУВАЧІВ І ПОМНОЖУВАЧІВ З СУМІЩЕННЯМ ОПЕРАЦІЙ запропоновано удосконалений алгоритмічний метод перемноження двох цілих чисел. Він полягає в роздільному підсумовуванні у відповідних каналах матричного помножуючого блоку
часткових добутків і перенесень, що одержуються при підсумовуванні часткових добутків, а також
сум і перенесень, що формуються при підсумовуванні перенесень, в усіх рангах блоку, за винятком останнього.
В результаті можлива паралельна робота суматорів, що обробляють паралелограм часткових добутків, в усіх рангах блоку, за винятком останнього, на якому виконується кінцеве підсумовування результуючої суми часткових добутків і результуючої суми перенесень.
В розділі запропоновано алгоритмічний метод структурного синтезу швидкодіючих помножувачів, який полягає в:
декомпозиції паралелограма часткових добутків на регулярні і нерегулярні фрагменти;
обробці фрагментів відповідними багаторозрядними багатооперандними суматорами (ББС);
обробці в пристрої перенесень, що виникають при підсумовуванні чисел в ББС, також і в разі роздільного підсумовування часткових сум і перенесень, одержаних при підсумовуванні результатів на попередньому ранзі.
Рис. 5. Паралелограм часткових добутків 4n4n
При проектуванні швидкодіючого помножувача на основі даного методу і при застосуванні суматора 44 (окремий випадок суматора MN), розглянутого в другому розділі, паралелограм часткових добутків цілих чисел 4n4n (n = 2f, f = 1, 2, 3, ...) розбивається так, як це наведено на рис. 5. Тут 1, 2, . . . , 4n 4n-розрядні часткові добутки; 1, . . . , n групи по чотири складових.
Рис. 6. Структура модифікованого помножувача 4n4n
На рис. 6 запропонована узагальнена пятирангова структура модифікованого помножувача цілих чисел 4n4n (n = 2f, f = 1, 2, 3, ...), який обробляє даний паралелограм часткових добутків і реалізує запропонований в дисертації метод перемноження. В даному пристрої одночасно додається до чотирьох складових, які обробляються потетрадно, а перенесення, що одержуються при додаванні операндів, підсумовуються з сумами лише в останньому блоці пристрою блоці суматорів результуючих, в інших блоках окремо від сум. На рисунку позначено: А, В 4n-розрядні множене і множник відповідно; БК блок кон’юнкторів, в якому формуються часткові добутки; СС1 блок суматорів сум 2-го рангу; СП1 блок суматорів перенесень 2-го рангу; СС2 блок сумматорів сум 3-го рангу; СП2 блок суматорів перенесень 3-го рангу; СП3 блок суматорів перенесень 4-го рангу; СР блок суматорів результуючих; F(1 : 8n) виходи пристрою помноження с 1-го по 8n-ий відповідно.
В розділі приводяться в якості прикладів структури модифікованих помножувачів 3232 (f = 3, n = 8) і 6464 (f = 4, n = 16).
Розрахунки, що наведені в розділі, показують, що пристрої помноження, спроектовані згідно з структурою, наведеною на рис. 6, мають виграш у швидкодії при перемноженні двох 16-розрядних чисел, який дорівнює 10 %; при перемноженні двох 32-розрядних чисел 22 %; при перемноженні двох 64-розрядних чисел 26 % і двох 128-розрядних чисел 29 % в порівнянні з аналогічними по розрядності пристроями, спроектованими згідно з відомою швидкодіючою структурою матричного помножувача цілих чисел на основі повних однорозрядних суматорів і з стічним розповсюдженням перенесень. При цьому в блоці СР (рис. 6) використовуються двословні суматори.
В розділі запропоновано алгоритмічний метод структурного синтезу помножувачів/суматорів, який полягає в:
декомпозиції паралелограму часткових добутків на регулярні і нерегулярні фрагменти;
обробці фрагментів відповідними ББС;
введені в паралелограм часткових добутків біт додаткового доданку;
обробці в пристрої перенесень, що виникають при підсумовуванні чисел в ББС, також і в разі роздільного підсумовування часткових сум і перенесень, одержаних при підсумовуванні результатів на попередньому ранзі.
Розширивши паралелограм часткових добутків цілих чисел 4n4n (n = 2f, f = 1, 2, 3, ...) за рахунок введення справа біт цілого доданку С в кожен рядок (рис. 7), одержуємо можливість реалізувати операцію F = А В + С над цілими числами одинакової розрядності.
Рис. 7. Паралелограм часткових добутків: а розбивка паралелограма; б, в варіанти введення бітів доданку С
На рис. 7,б і 7,в наведені два із можливих варіанти введення додаткових біт доданку С. На рисунках ці біти позначені поміткою “*”.
Рис. 8. Структура помножувача/суматора
На рис. 8 запропонована узагальнена структура помножувача/суматора цілих чисел, що обробляє паралелограм часткових добутків цілих чисел, наведеного на рис. 7,а,б, та реалізує операцію F = А В + С. На рисунку позначено: A, B 4n-розрядні множене та множник (n = 2f, f = 1, 2, 3, ...) відповідно; С, С розряди доданку С; F(1 : 8n) розряди с 1-го по 8n-ий відповідно до виходу пристрою. Призначення і функціонування блоків БК, СС1, СС2, СП1, СП2, СП3, СР аналогічні, як і у помножувача 4n4n (рис. 6). При цьому в блоці СР використовується чотирирозрядний трисловний суматор з розподілом доданків по розрядам: 2, 2, 2, 3.
Розрахунки, що наведені в розділі, показують, що швидкодія запропонованого помножувача/суматора при розрядності співмножників та доданку С, яка дорівнює 64, на 19 % вища, ніж у пристрої помноження з стічним розповсюдженням перенесень тієї ж розрядності.
В розділі запропонована структура пристрою, який реалізує операцію F = (A) (B) C з цілими числами в доповняльному коді на основі (2).
Наприклад, при розрядності співмножників m = n = 5, з врахуванням знакових розрядів, одержуємо
P = А В = ab2 + + 2(2 + 2 + 2 + b + ) + (5)
+ 2(2 + 2 + 2 + a + ).
Рис. 9. Варіант введення додаткових бітів доданку С
Варіант введення додаткових бітів цілого доданку С в доповняльному коді в одержаний паралелограм часткових добутків для реалізації операції F = (A) (B) C запропоновано на рис. 9 (тут С = 10 розрядів). На рисунку ці біти позначені поміткою “*”; стрілками вниз позначені розряди доданку С, що надходять відразу до блоку СР (рис. 8) на відповідний вхід чотирирозрядного трисловного суматора з розподілом доданків по розрядам: 2, 2, 2, 3.
Розрахунки, які наведені в розділі, показують, що швидкодія пристрою, який реалізує функцію F = (A) (B) C над цілими числами в доповняльному коді і при умові, що А = В = 65 розрядів, включаючи знаковий, а С = 130 розрядів (подвійний формат), вища швидкодії помножувача із стічним розповсюдженням перенесень при перемножуванні цим помножувачем цілих чисел в доповняльному коді розрядністю, яка дорівнює 64, на 21 %.
Операція F = (A) (B) C достатньо універсальна. Так, її частковий випадок F = (+A) (+1) C є фрагментом макрооперацій ділення та добутку квадратного кореня.
Розрахунки також показують, що пристрої помноження, що спроектовані згідно зі структурою, наведеною на рис. 6, мають виграш у швидкодії при перемноженні двох 16-розрядних чисел, який дорівнює 13 %; при перемноженні двох 32-розрядних чисел 15 %; при перемноженні двох 64-розрядних чисел 14 % і двох 128-розрядних чисел 11 % в порівнянні з аналогічними по розрядності пристроями, спроектованими згідно зі структурою матричного помножувача з логарифмічною характеристикою (1). При цьому в блоці СР (рис. 6) використовуються суматори 44 і структури АЛП з паралельним перенесенням.
Швидкодія спроектованих на основі запропонованих методів помножувачів та помножувачів/суматорів цілих чисел в порівнянні з класичними матричними помножувачами зростає тому, що
а) час обчислення ББС, що використовуються в нових пристроях, дорівнює О(logn), на відміну від однорозрядного повного суматора, час обчислення котрого дорівнює О(n) (де n розрядність співмножників);
б) використання великого числа операндів зменшує число рангів в структурі пристрою, що також приводить до збільшення швидкодії.
Апаратні витрати при проектуванні запропонованих помножувачів і помножувачів/суматорів можуть бути розраховані з частковим використанням формул, що визначають швидкодію даних пристроїв.
Так, число підрангів в блоці СС1 визначається як
= 1 + logn, (6)
де n розрядність співмножників.
Загальне число підрангів в блоці СП1 дорівнює = 1. При f = 1, 3, 5, . . . на виході S блока СС1 формуються дві результуючі суми, вони підсумовуються на лінійці суматорів єдиного підрангу блока СС2 та обробляються потетрадно. При f = 2, 4, 6, . . . на виході S блока СС1 формується одна результуюча сума, вона передається на вихід S блока СС2 без змін. Усі перенесення і суми перенесень, що надходять на входи блока СП2, підсумовуються в ньому на лінійці суматорів єдиного підрангу. При f = 1, 3, 5, . . . число підрангів в блоці СП3 дорівнює = 2; при f = 2, 4, 6, . . . = 3. В блоці СР число підрангів дорівнює двом. Далі визначається число паралельно функціонуючих лінійок суматорів в кожному підранзі перелічених блоків і число суматорів 44, що обробляють тетради даних, в кожній лінійці суматорів. Загальне число суматорів 44, з врахуванням апаратних витрат блока БК, і визначає апаратні витрати помножувачів і помножувачів/суматорів, що розглядаються.
В четвертому розділі МОДЕЛЮВАННЯ ПІДСУМОВУЮЧИХ ПРИСТРОЇВ ЧИСЕЛ З ПЛАВАЮЧОЮ КОМОЮ В СЕРЕДОВИЩІ ACTIVE –HDL, ЇХ ВЕРИФІКАЦІЯ ТА ОЦІНКА ПАРАМЕТРІВ запропоновано Verilog –опис функціональної моделі підсумовуючого пристрою двох чисел A і B з плаваючою комою на вищому рівні абстракції Adder_With_Floating_Comma.
Теоретичні дослідження в другому розділі дисертації показали, що пристрій, наведений на рис. 3, повинен мати на 40 % більшу швидкодію проти підсумовуючого пристрою ЕОМ Star100. Для підтвердження результатів дослідження в четвертому розділі проводиться моделювання даних підсумовуючих пристроїв в середовищі Active - HDL. Одержані при цьому часові характеристики порівнюються між собою.
Рис. 10. Структура підсумовуючого пристрою СУ2
В якості першого пристрою для моделювання і структурної декомпозиції моделі Adder_With_Floating_Comma в розділі розглянуто підсумовуючий пристрій чисел з плаваючою комою СУ2, що наведений на рис. 10, який реалізує процедуру підсумовування шляхом послідовного виконання в часі мікрооперацій “класичної” макрооперації підсумовування, аналогічно ЕОМ Star100. Тут Рг1, Рг2 регістри 1, 2 доданків А, В відповідно; ВП блок віднімання порядків; К1, К2 блоки комутаторів 1, 2; Ф блок формувача модуля різниці порядків (ВР); ДН блок денормалізації; СМ блок суматорів мантис; Н блок нормалізації; mа, mb, mс мантиси чисел А, В, С відповідно; Ра, Рb, Рс порядки чисел А, В, С відповідно; СИ синхроімпульси (CLK).
Перед синтезом і моделюванням функціональної моделі пристрою СУ2, була створена бібліотека функціональних моделей всіх блоків, що входять до його складу. Із Verilog - описів функціональних моделей блоків пристрою СУ2 з використанням оголошених сигналів формуєтся Verilog –опис функціональної моделі пристрою СУ2.
Рис. 11. Часова діаграма роботи СУ2
На рис. 11 наведена одержана в результаті моделювання в середовищі Active - HDL пристрою СУ2 часова діаграма його роботи. Тут інформація представлена в шістнадцятирічному коді: mа (Ma_In) = 96, Ра (Pa_In) = 3, mb (Mb_In) = 96, Рb (Pb_In) = 1, mc (MRes_Out) = BB, Pc (PRes_Out) = 3.
Пристрій СУ2 запускається переднім фронтом синхросигналу CLK (на діаграмі позначений вертикальною лінією), і із часової діаграми випливає, що час спрацьовування СУ2 дорівнює: 430 –= 280 (нс).
В якості другого пристрою для моделювання розглянуто підсумовуючий пристрій СУ3, функціональна модель якого наведена на рис. 12. Пристрій реалізує процедуру підсумовування шляхом паралельного виконання в часі мікрооперацій обчислення модуля різниці порядків і підготовки (2n + 2) часткових n-розрядних сум мантис доданків (n = 8) з наступним потім вибором необхідної часткової суми аналогічно пристрою на рис. 3.
Рис.12. Функціональна модель пристрою СУ3
Рис. 13. Часова діаграма роботи СУ3
На рис. 13 зображена часова діаграма роботи пристрою СУ3, при цьому СУ3 запускається переднім фронтом синхросигналу CLK. Із часової діаграми випливає, що час спрацьовування СУ3 дорівнює 180 нс.
Порівняння часів затримок пристроїв СУ2 і СУ3 показує, що пристрій СУ3 приблизно на 35 % швидше підсумовуючого пристрою СУ2.
Таким чином, одержані результати моделювання розглянутих підсумовуючих пристроїв підтверджують вірність розрахунків часових параметрів підсумовуючих пристроїв, представлених в другому розділі.
Створені Verilog - описи функціональних моделей блоків для функціональних моделей пристроїв СУ2 і СУ3 можуть застосовуватися для формування Verilog –описів різних інших функціональних моделей підсумовуючих пристроїв.
ВИСНОВКИ
В дисертаційній роботі досліджені та проаналізовані існуючі методи проектування цифрових операційних пристроїв; розроблені методи структурного синтезу арифметичних пристроїв цифрової обчислювальної техніки, які забезпечують підвищення їх швидкодії. При цьому одержані наступні основні результати.
2. Розроблені нові алгоритмічні методи структурного синтезу помножувачів і помножувачів/суматорів на основі використання багаторозрядних багатооперандних суматорів різних структур. Швидкодія синтезованих на основі даних методів помножувачів цілих чисел в порівнянні з класичним матричним помножувачем зростає на 15 %.
3. Удосконалено алгоритмічний метод перемноження двох цілих чисел на основі роздільного підсумовування часткових сум і перенесень, одержаних при підсумовуванні результатів на попередньому ранзі.
4. Синтезовані нові швидкодіючі структури суматорів цілих чисел і підсумовуючих пристроїв чисел з плаваючою комою. Запропоновані підсумовуючі пристрої чисел з плаваючою комою розташовуються за часовими характеристиками і апаратними витратами згідно з принципом Парето.
. Синтезовані нові швидкодіючі структури помножувачів і помножувачів/суматорів цілих чисел, побудованих на базі ББС різних структур. Апаратні витрати при синтезі запропонованих помножувачів і помножувачів / суматорів можуть бути розраховані з частковим використанням формул, яківизначають швидкодію даних пристроїв.
6. Створена низка функціональних моделей на мові Verilog структур підсумовуючих пристроїв чисел з плаваючою комою різного рівня абстракції з метою їх моделювання і визначення основних характеристик за швидкодією і апаратними витратами. Підтверджена вірність розрахунків часових параметрівпідсумовуючих пристроїв, представлених у другому розділі.
7. Розглянуті в дисертації підсумовуючі пристрої, помножувачі і помножувачі/суматори, виконані у вигляді ПЛІС, можуть знайти широке застосування при проектуванні засобів цифрової обчислювальної техніки, зокрема, в спецпроцесорах, що виконують швидке перетворення Фур’є. Вони можуть бути також вбудовані в мікропроцесори, що підвищить швидкодію останніх.
. Розроблені алгоритмічні методи структурного синтезу помножувачів і помножувачів/суматорів можуть бути використані для проектування пристроїв помноження і помноження/підсумовування чисел з фіксованою комою.
9. Основні положення, виводи та рекомендації, що наведені у дисертаційній роботі, планується використати в НДЕКР по розробці та створенню програмно-технічних комплексів на ВАТ “Елемент”, та використовуються у навчальному процесі ОНПУ в дисципліні “Паралельні обчислювальні процеси”, що викладається на кафедрі “Системне програмне забезпечення” для студентів фаху 8.080403 “Програмне забезпечення автоматизованих систем”.
СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
Синегуб М.І. Методи структурного синтезу базових арифметичних функціональних пристроїв з підвищеною швидкодією. Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 —Елементи та пристрої обчислювальної техніки та систем керування. Одеський національний політехнічний університет, Одеса, 2007 р.
Дисертація присвячена розробці нових та удосконаленню відомих методів виконання арифметичних операцій і методів структурного синтезу арифметичних пристроїв цифрової обчислювальної техніки, а саме: підсумовуючих пристроїв чисел з плаваючою комою, помножувачів і помножувачів/суматорів на базі багаторозрядних багатооперандних суматорів різних структур, що підвищують швидкодію даних пристроїв.
Розроблені нові алгоритмічний і табличноалгоритмічний методи структурного синтезу підсумовуючих пристроїв чисел з плаваючою комою, що дозволяють синтезувати підсумовуючі пристрої високої швидкодії, а також з розширеними функціональними можливостями. Так, в порівнянні з відомимирішеннями швидкодія у запропонованих підсумовуючих пристроях може бути збільшена до 40 %. Пристрої за авторськими свідоцтвами № 1290300 “Устройство для суммирования двух чисел с плавающей запятой” і № 1348825 “Устройство для суммирования чисел с плавающей запятой” упроваджено на підприємстві п/с Р6533.
Подальший розвиток набув метод перемноження двох цілих чисел на основі роздільного підсумовування на кожному ранзі, окрім останнього, сум і перенесень, одержаних при підсумовуванні результатів на попередньому ранзі.
Розроблені нові алгоритмічні методи структурного синтезу помножувачів і помножувачів/суматорів на основі використання багаторозрядних багатооперандних суматорів різних структур. Швидкодія синтезованих на основі даних методів помножувачів цілих чисел в залежності від розрядності операндів може збільшитися до 15 % в порівнянні з відомими рішеннями. Апаратні витрати при синтезі запропонованих помножувачів і помножувачів/суматорів можуть бути розраховані з частковим використанням формул, які визначають швидкодію даних пристроїв.
Сформована низка функціональних моделей на мові Verilog структур підсумовуючих пристроїв чисел з плаваючою комою різного рівня абстракції з метою їх моделювання і визначення основних характеристик за швидкодією і апаратними витратами.
Ключові слова: алгоритмічні методи проектування; таблично алгоритмічні методи проектування; табличні методи проектування; підсумовуючі пристрої чисел з плаваючою комою; помножувачі цілих чисел; помножувачі/суматори цілих чісел; багаторозрядні багатооперандні суматори; Verilog - опис функціональної моделі.
Sinegub N.I. Structural synthesis methods of the basic arithmetical functional high performance devices. Manuscript.
The thesis for a scientific degree of the candidate of technical sciences on specialty 05.13.05 Elements and computing devices and control systems. The Odessa National Polytechnic University, Odessa, 2007.
Dissertation is devoted to the design of new enhancing known methods of processing arithmetical operations and structural synthesis methods of arithmetical devices of digital computing namely adding devices of numbers with floating comma, multipliers / adders on the basis of multicarry and multioperand adders of different structures, increasing high performance of these devices.
New algorithmic and table algorithmic methods structural synthesis of adding devices of numbers with floating comma permitting synthesize adding high performance devices and also ones with improved functional possibilities have been developed. Thus, high performance of the offered adding devices may be increased up to 40 % in comparison with the known solutions.
The method of multiplication of two integers on the basis of separate adding sums and carry digits in each layer but the last, received on adding results on previous layer obtained further development.
New algorithmic methods of structural synthesis of multipliers and multipliers / adders on the basis of using multicarry and multioperand adders of different structures have been developed. High performance of the multipliers of integers synthesized on the basis of these methods in dependence of the operand capacity may be increased up to 15 % in comparison with the known solutions. Apparatus expenses on the synthesis of offered multipliers and multipliers/adders may be computed with partly using formulae defining high performance of these devices.
A series of functional models of structures of adding devices of numbers with floating comma of different level of abstraction in the language Verilog on purpose of their modeling and defining basic characteristic on high performance and apparatus expenses has been formed.
Key words: algorithmic methods of design; table algorithmic methods of design; table methods of design; adding devices of numbers with floating comma; multipliers of integers; multipliers/adders of integers; multicarry and multioperand adders; Verilog is a description of functional model.
Синегуб Н.И. Методы структурного синтеза базовых арифметических функциональных устройств с повышенным быстродействием. Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 Элементы и устройства вычислительной техники и систем управления. Одесский национальный политехнический университет, Одесса, 2007 г.
Диссертация посвящена разработке новых и усовершенствованию известных методов выполнения арифметических операций и методов структурного синтеза арифметических устройств цифровой вычислительной техники, а именно: суммирующих устройств чисел с плавающей запятой, умножителей целых чисел и умножителей/сумматоров, совмещающих функции умножения, суммирования и вычитания целых чисел одинаковой разрядности как в прямом, так и в дополнительном кодах на базе многоразрядных многооперандных сумматоров различных структур, повышающих быстродействие данных устройств.
Разработаны новые алгоритмический и табличноалгоритмический методы структурного синтеза суммирующих устройств чисел с плавающей запятой, усовершенствующие “классическую” макрооперацию суммирования чисел с плавающей запятой, и позволяющие синтезировать суммирующие устройства высокого быстродействия, у которых быстродействие может быть увеличено до 40 % в сравнении с известными решениями, а также с расширенными функциональными возможностями на основе таблиц значений предварительных сумм.
Синтезированы новые быстродействующие структуры сумматоров целых чисел и суммирующих устройств чисел с плавающей запятой. При этом за основу берется алгоритмизация различных вариантов операций суммирования на базе распараллеливания микроопераций, предварительной подготовки результатов, с использованием аппарата симметрических функций. Устройства по авторским свидетельствам № 1290300 “Устройство для суммирования двух чисел с плавающей запятой” и № 1348825 “Устройство для суммирования чисел с плавающей запятой” внедрены на предприятии п/я Р6533.
Дальнейшее развитие получил метод перемножения двух целых чисел на основе раздельного суммирования на каждом ранге, кроме последнего, сумм и переносов, полученных при суммировании результатов на предыдущем ранге.
Разработаны новые алгоритмические методы структурного синтеза умножителей и умножителей/сумматоров на основе использования многоразрядных многооперандных сумматоров различных структур. Быстродействие синтезированных на основе данных методов умножителей целых чисел по сравнению с классическим матричным умножителем возрастает на 15 %.
Синтезированы новые быстродействующие структуры умножителей и умножителей/сумматоров целых чисел, построенных на базе многоразрядных многооперандных сумматоров различных структур. Аппаратные затраты предложенных умножителей и умножителей/сумматоров могут быть рассчитаны с частичным использованием формул, определяющих быстродействие данных устройств.
Сформирован ряд функциональных моделей на языке Verilog структур суммирующих устройств чисел с плавающей запятой разного уровня абстракции с целью их моделирования и определения основных характеристик по быстродействию и аппаратным затратам.
Основные положения, выводы и рекомендации, приведенные в диссертационной работе, планируется использовать в НИОКР по разработке и созданию программно-технических комплексов на ОАО “Элемент”, и используются в учебном процессе ОНПУ в дисциплине “Параллельные вычислительные процессы”, которая читается на кафедре системного программного обеспечения для студентов по специальности 8.080403 “Программное обеспечение автоматизированных систем”.
Ключевые слова: алгоритмические методы проектирования; таблично алгоритмические методы проектирования; табличные методы проектирования; суммирующие устройства чисел с плавающей запятой; умножители целых чисел; умножители/сумматоры целых чисел; многоразрядные многооперандные сумматоры; Verilog - описание функциональной модели.