ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ

КРУЦКЕВИЧ НАЗАР ДМИТРОВИЧ

УДК 681.3

ПРОЦЕСОРИ ФОРМУВАННЯ ТА ЦИФРОВОЇ ОБРОБКИ ДАНИХ

ЗІРКОВО-МАГІСТРАЛЬНИХ КОМП’ЮТЕРНИХ СИСТЕМ

Спеціальність 05.13.05 – елементи та пристрої обчислювальної техніки та систем керування

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Тернопіль – 2007

Дисертацією є рукопис.

Робота виконана в Тернопільському національному економічному університеті

Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор

Николайчук Ярослав Миколайович,

Тернопільський національний економічний університет,

завідувач кафедри спеціалізованих комп’ютерних систем.

Офіційні опоненти: доктор технічних наук, професор

Широчин Валерій Павлович,

Національний технічний університет “Київський політехнічний інститут”,

професор кафедри обчислювальної техніки

кандидат технічних наук, доцент

Глухов Валерій Сергійович,

Національний університет “Львівська політехніка”,

доцент кафедри електронно-обчислювальних машин

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України,

відділ мікропроцесорної техніки

Захист відбудеться “ 31 ” _травня 2007 р. о _1400__годині на засіданні спеціалізованої вченої ради К 58.082.02 при Тернопільському національному економічному університеті за адресою: 46000, м. Тернопільвул. Львівська, 11,

(зал засідань вченої ради)

3 дисертацією можна ознайомитись у науково-технічній бібліотеці Тернопільського національного економічного університету за адресою:

46000, м. Тернопіль, вул. Львівська, 11.

Автореферат розісланий “ 28 ” квітня 2007 р.

Вчений секретар

спеціалізованої вченої ради,

к. т. н., доцент Яцків В. В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Досягнутий рівень сучасних технологій створення елементної бази мікропроцесорних систем по багатьох системних характеристиках інтегральних компонентів (швидкодії, габаритам, надійності) відповідає вимогам широкого класу застосувань спеціалізованих пристроїв та мікропроцесорів для оперативної обробки сигнальної інформації, яка формується, передається, обробляється, накопичується і зберігається в автоматизованих інформаційних системах.

Важливість наукових та прикладних задач, які вирішуються за допомогою процесорів цифрової обробки даних (ПЦОД), зумовлюють незмінну увагу до досліджень та розробок альтернативних арифметико-логічних пристроїв для сигнальних процесорів та відповідних теоретико-числових базисів (ТЧБ). Широко відомі розробки стандартних послідовних процесорів ЦОД в базисі Радемахера (Conventional DSP) та поліпшеної архітектури (Enhanced-Conventional DSP) таких фірм, як Texas Instruments, Motorola та інших. Елементи конвеєрної обробки даних внесені в архітектури сучасних ПЦОД, наприклад, TMS320C6X може виконувати паралельно до восьми команд (принцип VLIW – very long instruction word).

В той же час, очевидним стає відставання розвитку теорії та схемотехніки побудови швидкодіючих процесорів формування та цифрової обробки даних на основі теоретико-числових базисів, які відрізняються від базису Радемахера. Наукові роботи, що базуються на комплексному використанні переваг ТЧБ не в повній мірі відображені в спеціальній літературі. Наприклад, така проста операція, як інкрементування, тобто збільшення коду числа на одиницю, в базисі Радемахера потребує виконання n тактів наскрізного переносу, де n – розрядність операційного пристрою сумування. Запропонована в ряді робіт реалізація суматорів з міжрозрядними переносами дозволила частково розв’язати цю задачу і підвищити швидкодію суматорів. В той же час, дана операція в базисі Галуа за рахунок рекурентних властивостей упаковки кодів чисел виконується за один такт зсуву.

При виконанні операцій сумування та множення в базисі Крестенсона, які виконуються за один системний такт, досягається висока швидкодія, але збільшуються апаратні затрати при використанні 3D типу пам’яті. Особливо громіздкою є реалізація пірамідальних дешифраторів в базисі Радемахера, число елементів яких зростає квадратично при збільшенні розрядності вхідних кодів. В той же час, процесори сумування та множення в базисі Галуа, які характеризуються нелінійними характеристиками, реалізуються достатньо громіздкими мікропрограмними та апаратними засобами.

Дисертаційна робота присвячена розв’язанню важливої науково-технічної задачі: створенню арифметико-логічних компонентів процесорів, що реалізовані на основі комплексного використання окремих переваг різних ТЧБ, успішне рішення якої забезпечить можливості суттєвого збільшення швидкодії процесорів при виконанні арифметико-логічних операцій та спростити їх апаратну реалізацію.

Значний внесок в розвиток теорії та застосування в галузі обчислювальних машин в різних теоретико-числових базисів зробили Акушський І.Й., А. Крестенсон, Глушков В.М., Палагін О.В., Брюхович О.С., Романов С.І., Тарасенко В.П., Николайчук Я.М., Мельник А.О., Петришин Л.Б., Черняков В.П. та інші.

Вдосконалення та комплексне використання позитивних характеристик різних ТЧБ є актуальною теоретичною та практичною науково-технічною задачею для побудови засобів обчислювальної техніки. Завдяки створенню арифметико-логічних компонентів, що реалізовані в різних ТЧБ з використанням їх окремих переваг, можна добитися суттєвого збільшення швидкодії при виконанні арифметико-логічних операцій.

Зв’язок роботи з науковими програмами, планами, темами. Представлені в дисертації дослідження виконані в рамках плану наукових досліджень, які проводяться продовж 2004-2007 років на факультеті комп’ютерних інформаційних технологій кафедрою спеціалізованих комп’ютерних систем Тернопільського національного економічного університету за темою НДР “Розробка теорії, методології та побудови технічних засобів спеціалізованих комп’ютерних систем”, № U00576A, СКС–63–02 “К”. Науково-дослідна робота “Співпраця між Україною та Румунією в галузі розподілених систем (CobURDiS)” за першим етапом (03.2006-12.2006 р.) (номер державної реєстрації 0106U005307). Вищеназвані роботи виконувались за безпосередньою участю автора.

Мета і задачі дослідження. Метою роботи є підвищення швидкодії процесорів ФЦОД та зменшення апаратних затрат при реалізації матричних операційних пристроїв додавання та множення за рахунок комплексного використання теоретико-числових базисів Радемахера, Крестенсона, Галуа (RCG).

У відповідності з поставленою метою дисертаційна робота включає розв’язання таких задач:

1) порівняльний аналіз структур та системних характеристик процесорів цифрової обробки та формування даних;

2) теоретичний аналіз та дослідження ефективності використання теоретико-числових базисів для побудови процесорів ФЦОД з врахуванням характеристик комунікаційних середовищ;

3) формалізація операцій та розробка цифрових операційних пристроїв у базисі Крестенсона-Галуа;

4) розробка структури та дослідження схемо-технічних характеристик компонентів багатоядерного RCG – процесора на базі зірково-магістральної топології;

5) розробка та імплементація високошвидкісного RCG – процесора, дослідження продуктивності та ефективності застосування RCG процесорів в багаторівневих комп’ютерних мережах та системах.

Об’єктом дослідження є процеси кодування даних та цифрового оброблення інформації цифровими пристроями, побудованими на базі процесорів в базисі Крестенсона-Галуа.

Предмет дослідження – методи та засоби формування та цифрового оброблення даних, що реалізують алгоритми процесорних операцій: кодування, дешифрації, додавання та множення в ТЧБ Крестенсона-Галуа.

Методи дослідження базуються на використанні теорії інформації, теорії кодування, прикладній теорії цифрових автоматів, теорії систем, теорії цифрової обробки сигналів, а також методів проектування, моделювання та імплементації в сучасних середовищах САПР схемо- та системотехніки.

Наукова новизна одержаних результатів полягає в наступному:

1. Запропоновано новий підхід до створення мультибазисної архітектури ПФЦОД, який будується на одночасному використанні трьох теоретико-числових базисів Радемахера, Крестенсона, Галуа та на об’єднанні процесорів у зірково-магістральну топологію, що дозволяє зменшити апаратні затрати при реалізації великих замовних інтегральних схем мультиядерних процесорів.

2. Обґрунтовано та удосконалено метод сумісного застосування теоретико-числових базисів Крестенсона-Галуа для побудови операційних пристроїв, що дозволило підвищити швидкодію, покращити регулярність структур, зменшити число вентильних елементів в операційних пристроях виконання базових арифметичних операцій цифрової обробки та формування даних.

3. Розроблено метод формування залишків базису Крестенсона рекурентними послідовностями базису Галуа, що дозволяє ефективно використати властивості компактного, рекурсивного кодування даних у базисі Галуа і можливості представлення результатів арифметичних операцій у відповідних кодових матрицях одним старшим бітом кодону Галуа.

4. Розроблені та запропоновані алгоритми швидкодіючого однотактного виконання операцій додавання та множення в базисі Крестенсона-Галуа на основі пам’яті з 2D структурою, які у порівнянні з існуючими реалізаціями на основі з 3D структурою пам’яті дозволяють зменшити об’єми необхідної регістрової пам’яті матричних процесорних елементів.

Практичне значення одержаних результатів:

1. Розроблена архітектура RCG – процесора з зірково-магістральною топологією, яка реалізує мультибазисні операції в теоретико-числових базисах Радемахера, Крестенсона, Галуа, що підвищує швидкодію та продуктивність процесора на 30-40% по відношенню до існуючих процесорів в базисі Радемахера.

2. Запропоновані принципові схемотехнічні рішення та їх імплементація на ПЛІС операційних пристроїв RCG – процесора з використанням досліджених компонент базових примітивів виконання арифметичних операцій додавання та множення в базисі Крестенсона-Галуа, а також базових примітивів регулярного середовища пам’яті колективного доступу.

3. Експериментальний зразок високошвидкісного матричного RCG – процесора, реалізованого на платі IOG-PCI C3-033-1, впроваджено у виробництво і використано в якості швидкодіючого комунікаційного процесора абонентської бази даних ТОВ "Оптіма Телеком" м. Івано-Франківськ.

4. Запропонована методика та засоби проектування спеціалізованих процесорів Інститутом мікропроцесорних систем керування об’єктами в електроенергетиці Карпатського державного центру інформаційних засобів і технологій НАН України, а також впроваджені в навчальному процесі на факультеті комп’ютерних інформаційних технологій ТНЕУ при проведенні лекційних, лабораторних занять та при виконанні курсових робіт з курсів: “Основи побудови спеціалізованих комп’ютерних систем”, “Теорія проектування комп’ютерних систем”, “Вбудовані комп’ютерні системи”.

Особистий внесок здобувача. Всі основні результати дисертаційного дослідження отримано автором особисто. У друкованих працях, опублікованих у співавторстві, автору належить: критерії доцільності реконфігурації архітектур процесорних пристроїв на основі оцінки емерджентності [5, 9, 14]; розроблені теоретичні основи та алгоритми виконання процедур формування даних та арифметичних операцій в базисі Крестенсона-Галуа [1-3,10]; формулювання основних аспектів та принципів виконання арифметичних операцій в базисі Крестенсона-Галуа [5, 7, 8]; аналіз структур процесорних елементів, що працюють у різних теоретико-числових базисах[4-8, 12]; розробка структурних та принципових схем процесорних елементів в базисі Крестенсона-Галуа [11, 13].

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались на:

- міжнародній науково-практичній конференції “Автоматизація виробничих процесів” МНПК АВТ-2002 – Хмельницький, 2002;

- VII міжнародній конференції CADSM 2003 “Досвід розробки та застосування приладо-технологічних САПР в мікроелектроніці”,Львів-Славське, 2003;

- міжнародній науково-практичній конференції “Автоматизація виробничих процесів” МНПК АВТ-2003 – Хмельницький, 2003;

- II міжнародній науково-практичній конференції International Workshop on Intelligent Data Acqustion and Advanced Computing Systems: Technology and Applicatins, IDAACS, Lviv, Ukraine, 2003;

- міжнародній конференції “Сучасні проблеми радіоелектроніки, та телекомунікацій та комп’ютерної інженерії” TSET’ 2004, Львів-Славське, 2004;

- VIII міжнародній конференції CADSM 2005 “Досвід розробки та застосування приладо-технологічних САПР в мікроелектроніці” Львів-Свалява, 2005;

- міжнародній науково-практичній конференції “Автоматизація виробничих процесів” МНПК АВТ-2005 – Хмельницький, 2005;

- міжнародній конференції “Сучасні проблеми радіоелектроніки, та телекомунікацій та комп’ютерної інженерії” TSET’ 2006, Львів-Славське, а також доповідалось та обговорювалось на наукових конференціях професорсько-викладацького складу та наукових семінарах кафедри спеціалізованих комп’ютерних систем Тернопільського національного економічного університету.

Публікації. Матеріали дисертаційної роботи в повному обсязі висвітлені в 14 друкованих працях автора, в тому числі в 8 статтях у фахових виданнях, з них 5 - одноосібних та 3 статті у співавторстві, а також у матеріалах 6 доповідей на міжнародних науково-практичних конференціях, по результатах досліджень подана заявка на винахід.

Структура дисертації. Дисертаційна робота складається із вступу, п’яти розділів, висновків, списку використаних джерел і 5 додатків. Загальний обсяг роботи становить 211 сторінки, з них 134 сторінки основного тексту, 103 рисунки та 6 таблиць. Список використаних джерел включає 171 найменування, додатки представлені на 32 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність роботи, визначено її зв’язок з науковими програмами, темами. Сформульовано наукову новизну та практичне значення одержаних результатів, а також показана їх апробація і публікації.

У першому розділі проведено аналіз архітектур та системних характеристик процесорів формування та цифрової обробки даних, зокрема, в сучасних паралельних та високопродуктивних обчислювальних системах (CRAY-1, CYBER 205, ILLIAC IV, Butterfly, ICL DAP), де широко використовуються ПФЦОД, які забезпечують технічну реалізацію, як традиційних так спеціалізованих задач цифрової обробки сигналів. Найбільша увага придається алгоритмам швидкої обробки складних сигналів. Сучасні обчислювальні засоби дозволяють виконувати в режимі реального часу задачі багатовимірної цифрової фільтрації за допомогою сигнальних процесорів або багатопроцесорних систем.

Доказано, що зірково-магістральні архітектури є базовими для проектування та побудови швидкодіючих спецпроцесорів залежно від класу задач та системних вимог.

Встановлено, що перспективними комунікаційними середовищами є середовища, які дозволяють легко нарощувати елементи системи заданої топології і забезпечувати високошвидкісний обмін даними.

Виконана постановка задачі досліджень по темі дисертації, яка полягає у комплексному дослідженні архітектури, компонентів та схемотехніки процесорів обчислювальних машин, реалізованих на основі зірково-магістральної архітектури та ТЧБ Крестенсона-Галуа.

У другому розділі проведено аналіз ТЧБ: Унітарного, Хаара, Крейга, Уолша, Радемахера, Крестенсона та Галуа, що використовуються для побудови елементів та засобів обчислювальної техніки.

Важливою характеристикою кожного базису є кількість кодових комбінацій N та об'єм V кодової матриці, що визначає надлишковість представлення інформації.

Проведений аналіз показує, що найбільш ефективними для кодування і представлення даних є ТЧБ Галуа, оскільки має коефіцієнт ефективності Кефект=1. Високо швидкодіючим є базис Крестенсона, який породжує систему числення залишкових класів, забезпечує розпаралелення та відсутність переносів між розрядами модульної системи числення.

Аналіз ТЧБ та їх кодових матриць дозволили встановити та обґрунтувати переваги характеристик кодових базисів Крестенсона та Галуа для побудови ПФЦОД.

В результаті проведених теоретико-системних досліджень зроблений висновок, що ефективним рішенням створення високопродуктивних ПФЦОД є реалізація сумісного використання ТЧБ Радемахера, Крестенсона, Галуа, а зірково-магістральну топологію такого процесора на базі пам’яті колективного доступу можна класифікувати як мультиядерний RCG – процесор.

У третьому розділі проведено формалізацію операцій та розробку цифрових операційних пристроїв у базисі Крестенсона-Галуа.

Основним принципом створення RCG – процесора зірково-магістральної топології є одночасне використання теоретико- числових базисів Радемахера, Крестенсона, Галуа та управління перерозподілом виконання операцій, які вони виконують найефективніше.

Запропонована структура такого процесора має наступний вигляд (рис. 1).

Рис.1. Структурна схема RCG процесора зірково-магістральної топології : R – процесорний елемент в базисі Радемахера; С – процесорний елемент в базисі Крестенсона; G – процесорний елемент в базисі Галуа; ПКД – пам’ять колективного доступу

В якості блоку виконання арифметичних операцій у базисі Радемахера використовується ядро класичного швидкодіючого арифметико-логічного пристрою в двійковій системі числення.

Запропонований принцип спільного використання кодового базису Крестенсона та Галуа при реалізації блоку виконання арифметичних операцій у базисі Крестенсона, в якому найефективніше виконуються операції модульного додавання та множення, причому кодове представлення залишків здійснюється не в двійковій системі числення, а в рекурентних послідовностях Галуа.

Для реалізації операції матричного додавання чисел в базисі Крестенсона-Галуа застосовується алгоритм сумування чисел в системі залишкових класів, який описується системою матриць по відповідних модулях Р1, Р2, Рn (рис. 2).

Рис. 2. Матриця додавання по модулю :a1-ak і b1-bk – операнди; C – результат операції; k = Pi-1

Запропонована формалізація операції матричного сумування в базисі Крестенсона-Галуа по модулю Р, яка реалізується згідно виразу:

, (1)

де залишки ai, bj, Cij повинні бути r – розрядними числами, де r розраховується за формулою:

,

де - округлення до більшого цілого.

Рекурсивні особливості базису Галуа дозволяють виконати матриці результатів сумування у вигляді рекурентних послідовностей.

Операція додавання здійснюється над операндами аі та bi в базисі Хаара на основі операції логічного множення, в результаті якої виокремлюється старший біт виконання операції n – розрядного рекурентного коду Галуа, що відповідає коду результату операції сумування (1).

, (2)

де ij від 0 до k, Cij – біти рекурентного коду Галуа.

Отже, для зберігання результату операції використовується один елемент бінарної матриці. Структурна схема матричного суматора по модулю в базисі Крестенсона-Галуа представлена на рис. 3.

Рис. 3. Матричний суматор по модулю 7: Аі та Ві – операнди; Сij – результат виконання операції; 1 і 2 – дешифратори рядків і стовпчиків; 3 – вихідний буфер |

Рис. 4. Матриця асоціативного суматора Крестенсона-Галуа по модулю : Аі та Ві – операнди; Сij – результат виконання операції

Операція сумування (2) виконується наступним чином. Двійкові коди залишків аі та bi подаються на входи відповідних адресних дешифраторів 1, 2, розрядно-позиційні виходи яких підключені до відповідних адресних шин ПЗП.

В результаті виконання логічної операції множення кільцевий кодон результату, початок якого визначається старшим бітом кодової матриці ПЗП, поступає на вхід буфера 3.

Використання кодового базису Галуа дозволяє проводити асоціативну вибірку результатів сумування у вигляді даних, які є одночасно адресами. Це можливо при заміні адресних дешифраторів прямокутного типу на дешифратори Галуа, що дозволяє виконувати асоціативну вибірку даних, принцип якої представлений матрицею асоціативного суматора на рис. 4.

З рис.8 видно, що дані, які записані в пам’яті, одночасно можуть виступати і як адреси операндів, що дозволяє значно спростити структуру матричного суматора шляхом заміни адресних дешифраторів на асоціативні.

При цьому операція сумування по модулю Р описується наступним логічним виразом:

, (3)

де ai та bj - бітові потоки операндів, Ai та Bj код чисел Cij.

З виразу (3) видно, що дешифрація відбувається асоціативним способом і базовий елемент матричного асоціативного суматора реалізовується операційним пристроєм (рис.5).

Рис. 5. Базовий елемент асоціативного суматора Крестенсона-Галуа: 1 – елемент пам’яті розміром 1біт; 2 – Галуа дешифратор стовпчика; 3 – Галуа дешифратор рядків; 4 – вихідний елемент “І”

Залежності числа елементів пам’яті від значень модулів Крестенсона-Галуа (рис. 6), яка розраховується на основі аналітичних виразів :

в базисі Крестенсона:

,

в базисі Крестенсона-Галуа:

,

де V – число елементів пам’яті матричного суматора по модулях P1, P2,…, Pn , Pi – модуль залишку і-го розряду числа представленого в СЗК.

Рис. 6. Графік залежності числа елементів пам’яті від модулів Рі матричних суматорів в базисах Крестенсона та Крестенсона-Галуа: 1 – базис Крестенсона; 2 – базис Крестенсона-Галуа |

Рис. 7. Графік ефективності суматора в базисі Крестенсона-Галуа: P – модулі; Кефект – коефіцієнт ефективності

Порівняння ефективності методу побудови матричного процесора сумування в річних ТЧБ виконано на основі виразу:

,

що виходячи з формул (2-3) набуде вигляду:

.

При реалізації операційного пристрою сумування в базисі Крестенсона-Галуа, порівняно з суматором в базисі Крестенсона, коефіцієнт ефективності при зростанні розрядної сітки процесорів зростає пропорційно із збільшенням значень модулів (рис. ), що демонструє ефективність кодування даних в базисі Крестенсона-Галуа.

Таким чином, використання особливих властивостей кодів Галуа, рекурентності та циклічності дозволяє здійснювати обчислення суми по модулю Р, використовуючи при цьому 2D пам’ять, а не 3D, як при класичній реалізації таких процесорів в системі числення базису Радемахера.

Операції множення у базисі Крестенсона-Галуа здійснюються на основі аналітичного виразу (1) та кодової матриці (рис.5), що повинна бути розширена виразом (2).

Суть розширення аналітичного виразу (2) полягає в тому, що кожний елемент результату сумування доповнюється різницевим кодом Sij, який виконує рекурсивну корекцію кодів сумування по модулю у відповідність кодів залишків множення

, (4)

де Sij – зсув кодових значень Галуа у матриці сумування (рис. 2).

Відповідно до виразу (4), матрицю множення можна представити наступним чином (рис.8):

Рис. 8. Матриця множення по модулю: a1-ak і b1-bk – операнди; C – результат операції; Sij – різницевий код, k = Pi-1 | Рис. 9. Матриця коректуючих значень Sij: Sij – різницевий код; k = Pi-1

При цьому реалізація множення виконується шляхом розширення матриці сумування коректуючою матрицею значень Sij (рис.9), в результаті проведення якого утворюються результати множення (рис.10).

а) б) в)

Рис. 10. Матриці процесу виконання операції множення по модулю 7: а - матриця сумування по модулю 7; б - коректуюча матриця; в - матриця множення операндів по модулю 7

При цьому значення 0 відповідає відсутності необхідності корекції результату, тобто однаковості кодів модульного додавання та множення; “+” – зсув результату матриці додавання праворуч, “-” – відповідно ліворуч.

Як видно з рис. 10б, процесори в СЗК при виконанні операції матричного множення в базисі Крестенсона-Галуа можуть мати місце три випадки:

1.) існують такі пари операндів ai та bi, які мають однакові результати модульного сумування та множення, тобто:

,

що відповідає елементу ”0” коректуючої матриці (рис. 10б);

2.) пари операндів ai та bi, в яких виконується умова:

,

що відповідає позитивному значенню Sij;

3.) пари операндів ai та bi, в яких виконується умова:

,

що відповідає негативному значенню Sij.

На рис. 11 показано приклади реалізації операції множення в розглянутих трьох випадках.

а) б) в)

Рис. 11. Приклади виконання операції множення по модулю 7: а – при нульовому значенню; б – при позитивному значенні; в – при негативному результаті

Проведенні дослідження дозволили запропонувати структуру та визначити системні характеристики процесора множення в базисі Крестенсона-Галуа (рис. 12).

Рис. 12. Структура процесора матричного множення Крестенсона-Галуа

Аналіз даної структури показав, що для розрахунку характеристик процесора матричного множення Крестенсона-Галуа по модулю слід враховувати подвійне зростання пам’яті та відповідне зниження швидкодії (рис.13).

Рис. 13. Графік залежності числа елементів пам’яті від модулів Рі матричних помножувачів в базисах Крестенсона та Крестенсона-Галуа:1 – базис Крестенсона; 2 – базис Крестенсона-Галуа |

Рис. 14. Графік ефективності пристрою множення в базисі Крестенсона-Галуа: P – модулі; Кефект – коефіцієнт ефективності

З рис. 13 видно, що матричні помножувачі по модулю в базисі Крестенсона-Галуа при різних модулях потребують значно меншого об’єму обсягу пам’яті порівняно з аналогічним пристроями в базисі Крестенсона.

Об’єм пам’яті пристрою множення по модулю Рі в базисі Крестенсона-Галуа розраховується згідно виразу:

.

Наприклад при реалізації пристрою матричного множення в базисі Крестенсона-Галуа при різних модулях порівняно з пристроєм матричного множення в Крестенсоні коефіцієнт ефективності набуде такого вигляду (рис. 14).

В результаті проведених теоретичних та схемо-технічних досліджень: створено принципово новий процесорний елемент швидкого множення та сумування по модулю, що використовує спільне обчислювальне середовище; реалізовано асоціативний метод дешифрації, що дозволяє використовувати комірки пам’яті як дешифруючі елементи і виключити класичний дешифратор, який присутній в стандартних процесорах; RCG - процесор на основі циклічної та рекурентної властивості кодів Галуа, використовує 2D пам’ять в той час, як процесори в базисі Радемахера - 3D пам’ять, що дозволяє значно скоротити об’єм кристалу при однаковій розрядності та швидкодії.

У четвертому розділі розроблено та досліджено компоненти RCG – процесора.

Рис. 15. Структурна схема пам’яті колективного доступу 3/1

Структурна схема пам’яті колективного доступу (рис.15), являє собою пам'ять загального користування для трьох процесорних елементів (А1,А2,АЗ).

Для аналізу запропонованої структури розглядалися параметри продуктивності і часу відповіді системи обробки інформації, які найбільш повно і точно визначають можливості системи при обробці відповідної кількості вхідних задач за одиницю часу:

,

де n - кількість задач, що обробляються системою за час t. В результаті інтенсивність вихідного потоку , досягнувши крайнього значення х, надалі залишається постійною при будь яких значеннях > х. Значення х визначає максимальну продуктивність системи для заданого класу задач і є характеристикою самої системи, яка не залежить від інтенсивності вхідного потоку задач (рис. 16).

а) б)

Рис. 16. Графік порівняння зіркової та зірково-магістральної топологій: а – залежність продуктивності систем від інтенсивності вхідного потоку задач; б - залежність часу відповіді системи від інтенсивності вхідного потоку задач

Таким чином, як показав аналіз, продуктивність і час відповіді системи в першу чергу залежать від структури і технічних характеристик загальносистемних ресурсів. Проте на значення продуктивності і часу відповіді системи важливу роль відіграють засоби, що забезпечують доступ незалежних процесорних елементів до загальних ресурсів.

Проведено розробку і аналіз модулів виконання арифметичних операцій RCG – процесора які являють собою незалежні спеціалізовані процесори призначені для швидкого виконання арифметичних операцій у відповідних теоретико-числових кодових базисах (рис.17).

а) |

б)

в)

Рис. 17. Структурна схема арифметичних модулів: а – Радемахера; б – Крестенсона; в – Галуа

Проаналізувавши час виконання мікропрограм арифметичного модуля в ТЧБ Радемахера (рис. 18а) можна зробити висновок, що для найменший час є для функцій множення на 2, операцій зсуву та логічних операцій, а мікропрограма операції ділення займає найбільший час виконання.

а) б)

в)

Рис. 18. Час виконання мікропрограм арифметичних модулів: а - ТЧБ Радемахера; б - ТЧБ Крестенсона; в - ТЧБ Галуа: 1 – процес ініціалізація арифметичного модуля; 2 – процес контролю та обміну даними з ПКД та магістраллю; 3 – процес виконання операцій регістру обміну даними; 4 – процес виконання операцій пристрою керування; 5 – процес виконання арифметичних операцій

Для ТЧБ Крестенсона (рис. 18б.) виконання мікропрограм для функцій множення та сумування виконується за однаковий час, оскільки ці операції найефективніше і найпростіше реалізуються в СЗК. Оцінюючи характеристики арифметичного модуля Галуа (рис. 18в.) видно, що час виконання мікропрограм для функцій інкрементування та декрементування виконується за один системний такт в базисі Галуа.

У п’ятому розділі розроблено апаратні та програмні засоби RCG – процесора: адресний дешифратор пам’яті колективного доступу та матричний асоціативний суматор-помножувач.

Проведені дослідження при реалізації адресного дешифратора Галуа на різних сімействах ПЛІС показали простоту реалізації даного типу елементів цифрової техніки. Завдяки регулярній структурі даний тип дешифраторів дозволяє легко нарощувати кількість каналів адресації, що відкриває перспективу подальшого дослідження та розвитку елементів даного типу.

Здійснено розрахунок продуктивності паралельної системи на базі пам’яті колективного доступу. Отримані показники створюють концептуальну основу для оцінки функціонування обчислювальних систем в процесі експлуатації і при дослідженнях за допомогою моделей продуктивності.

Проаналізовано ефективність використання RCG – процесорів в промисловості в якості сопроцесора сервера діагностики стану каналів зв’язку.

На рис.19 представлено гістограму, що демонструє продуктивність RCG – процесорів формування та цифрової обробки даних, яка на 30-40% вища при виконанні операції швидкого перетворення Фур’є з вибіркою 1024 точки та розрядністю 8, 16, 32 біти у порівнянні з існуючими типами процесорів в ТЧБ Радемахера.

Рис.19. Продуктивність процесорів цифрової обробки даних при виконанні швидкого перетворення Фур’є для 1024 точок

Запропоновано архітектуру процесорних пристроїв, що володіють більшою ефективністю порівняно з існуючими аналогами, реалізованими на універсальних ПЕОМ.

У додатках подано документи, що підтверджують впровадження результатів наукових досліджень по темі дисертації, приведено тексти програм, електричні принципові схеми, що розроблені в ході дисертаційного дослідження.

ВИСНОВКИ ТА ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ

У дисертаційній роботі розв’язано комплекс науково-технічних задач в напрямку подальшого розвитку теорії побудови процесорів формування та цифрової обробки даних (ПФЦОД) з покращеними системними характеристиками за рахунок комплексного використання теоретико-числового базису Крестенсона-Галуа. При цьому отримано такі наукові результати:

1. Досліджено системні характеристики архітектур та комунікаційних середовищ ПФЦОД на основі оцінки емерджентності, що дозволило встановити критерії доцільності забезпечення реконфігуративності та створення новітніх архітектур процесорних пристроїв.

2. Запропоновано новий підхід до створення мультибазисної архітектури ПФЦОД, який будується на одночасному використанні теоретико-числових базисів Радемахера, Крестенсона, Галуа та на об’єднанні процесорів в зірково-магістральній топології, що дозволяє зменшити об’єми апаратних затрат при реалізації великих замовних інтегральних схем мультиядерних процесорів.

3. Обґрунтовано та удосконалено метод сумісного застосування теоретико-числових базисів Крестенсона-Галуа для побудови операційних пристроїв, що дозволило підвищити швидкодію, покращити регулярність структур, зменшити в раз, (Р – канальний модуль процесора Крестенсона) число вентильних елементів в операційних пристроях виконання базових арифметичних операцій цифрової обробки та формування даних;

4. Розроблено метод формування залишків базису Крестенсона рекурентними послідовностями базису Галуа, що дозволяє ефективно використати властивості компактного, рекурсивного кодування даних у базисі Галуа і можливості представлення результатів арифметичних операцій у відповідних кодових матрицях одним старшим бітом кодону Галуа.

5. Розроблені та запропоновані алгоритми швидкодіючого однотактного виконання операцій додавання та множення в базисі Крестенсона-Галуа на основі пам’яті з 2D структурою, які у порівнянні з існуючими реалізаціями на основі з 3D структурою пам’яті дозволяють зменшити на 00 елементів об’єми необхідної регістрової пам’яті матричних процесорних елементів.

6. Запропоновані моделі базових примітивів та синтезована архітектура RCG – процесорів, що реалізовують мультибазисні операції, які забезпечують суттєве покращення системних характеристик та швидкодії на 30-40% у порівнянні з існуючими типами процесорів, які реалізовані у базисі Радемахера.

7. Розроблено функціональні та принципові схеми асоціативного адресного дешифратора, асоціативного арифметичного процесору з розширеними системними можливостями. Основні модулі імплементовані на ПЛІС, що забезпечило підвищення надійності та зменшення габаритів при реалізації процесорних елементів. Створені дослідні взірці процесорів впроваджені в телекомунікаційних систем контролю стану каналів зв’язку для ТОВ “Оптіма-Телеком” м. Івано-Франківськ.

СПИСОК ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Яцків В.В., Круцкевич Н.Д., Перспективи застосування базису Галуа в системах контролю доступу на прикладі безконтактної аутентифікацїі // Вісник Технологічного університету Поділля, -Хмельницький. -2002. - №3, -Т2 - С. 201-205.

2. Николайчук Я.М.,Сегін А.І., Круцкевич Н.Д., Возна Н.Я. Теорія проектування комп’ютерних систем на базі аналогії системних об’єктів енергетики // Вісник Національного університету ”Львівська політехніка” “Комп’ютерні системи проектування. Теорія і практика”, -Львів, -2003, -№ 470, -С. 48 – 55.

3. Круцкевич Н.Д. Принципи паралелізму при побудові багаторівневих розподілених комп’ютерних мереж // Вісник “Радіоелектроніка та телекомунікації” Національного університету ”Львівська політехніка”, -Львів, -2003, -№ 477, -С. 185 – 191.

4. Круцкевич Н.Д., Дослідження взаємодії системи асинхронних абонентів з паралельною пам’яттю колективного доступу // Вісник Технологічного університету Поділля, -Хмельницький, -2003, -№3, -Т1, -С. 108 – 112.

5. Круцкевич Н.Д., Николайчук Я.М., Синтез і проектування асоціативного суматора системи залишкових класів в базисі Галуа // Вісник “Радіоелектроніка та телекомунікації” Національного університету ”Львівська політехніка”, -Львів, -2006, -№ 557, -С. 15 – 19.

6. Круцкевич Н.Д. Перспективи розвитку комп’ютерних мереж з реконфігурацією архітектури на базі пам’яті колективного доступу // Вісник “Радіоелектроніка та телекомунікації” Національного університету ”Львівська політехніка”, Львів, 2004, №508, С. 240 – 245.

7. Круцкевич Н.Д. Принципи побудови дешифраторів кодів Галуа пам’яті колективного доступу // Вісник Технологічного університету Поділля, -Хмельницький, -2004,- №2, -Ч.1, Т2, -С. 113 – 116.

8. Круцкевич Н.Д. Системні характеристики лічильників в різних теоретикочислових базисах // Вісник Хмельницького національного університету, -Хмельницький, -2005, -Ч.1, Т2, -С. 219-223.

9. N. Krutskevych, Y.Nykolaychuk, Theoretical Bases of Construction and technology of design on Programmable Logic Arrays of Address decoder of memory of Multiple Access for Star-Main Network // Proc. of the International Conf. CADSM 2005. - Lviv-Slavsko (Ukraine). - 2005. - P. 214 -215.

10. Николайчук Я.М., Круцкевич Н.Д. Перспективи використання зірково - магістральної архітектури з пам'ятю колективного доступу в комп'ютерних мережах з глибоким розпаралелюванням // Вимірювальна та обчислювальна техніка в технологічних процесах: Збірник наукових праць- Хмельницький: ТУ/7 - 2002. - №9, -Т2. - С. 122 –126.

11. Круцкевич Н.Д.,. Николайчук Я. М Принципи побудови RCG процесора// Тези міжнародної науково - технічної конференції. “Контроль і управління в складних системах” (КУСС - 2003). – Вінниця: “УНІВЕРСУМ – Вінниця”. – 2003. – С. 73.

12. Круцкевич Н.Д., Николайчук Я.М. Структура та функції пам'яті колективного доступу на базі кодів Галуа. II Вимірювальна та обчислювальна техніка в технологічних процесах: Збірник наукових праць.- Хмельницький: ТУП -2002. - №9, -Т2. -С. 126 – 129.

13. Y.Nykolaychuk, N. Krutskevych Zastavniy O.М, .Architecture and System Characteristic of Distributed Computer Network with Autonomous Sensor Equipment// Proc. of the International Conf. TCSET 2006. – Lviv-Slavsko (Ukraine). – 2006. – P. 394 – 398.

14. Y. Nykolaychuk, N. Krutskevych O. Zastavniy, T. Grinchyshyn, Perspective Architecture and Components of Computer Networks // Proc. Of the Second IEEE International Workshop on Intelligent Data Acqustion and Advanced Computing Systems: Technology and Applicatins, IDAACS, Lviv, Ukraine, 2003.

АНОТАЦІЯ

Круцкевич Н. Д. Процесори формування та цифрової обробки даних зірково-магістральних комп’ютерних систем. – Рукопис.

Круцкевич Н. Д. Процесори формування та цифрової обробки даних зірково-магістральних комп’ютерних систем. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – елементи та пристрої обчислювальної техніки та систем керування. – Тернопільський національний економічний університет, Тернопіль, 2007.

Проведено аналіз процесорів цифрової обробки даних, особливостей їх структурної організації, а також проведено аналіз теоретико-числових кодових базиcів, що використовуються для побудови процесорів та їх елементів.

Запропоновано і обґрунтовано ефективність та застосування ТЧБ Крестенсона-Галуа для побудови процесорів формування та цифрової обробки даних з покращеними системними характеристиками (швидкодії, регулярності, зменшення числа логічних елементів).

Розроблені теоретичні основи та алгоритми виконання процедур формування даних та арифметичних операцій в базисі Крестенсона-Галуа на основі запропонованих RCG процесорних елементів.

Запропоновані принципи реалізації елементної бази та розроблена архітектура RCG – процесора, що реалізовує мультибазисні операції, які забезпечують покращення системних характеристик (підвищення швидкодії на 30-40%).

Ключові слова: процесори цифрової обробки даних, система залишкових класів, базис Галуа, базисні функції, проблемно-орієнтовані комп’ютерні системи, теоретико-числові базиси.

АННОТАЦИЯ

Круцкевич Н. Д. Процессоры формирования и цифровой обработки данных звездно-магистральных компьютерных систем. – Рукопись.

Диссертация на соискание научной степени кандидата технических наук за специальностью 05.13.05 – элементы и устройства вычислительной техники и систем управления. – Тернопольский национальный экономический университет, Тернополь, 2007.

Проведен анализ процессоров цифровой обработки данных, особенностей их структурной организации, а также проведен анализ теоретико-числовых кодовых базисов, что используются для построения процессоров и их элементов.

На основе критериев целесообразности реконфигурации архитектур процессорных устройств, исследовано их системные характеристики и созданы новые архитектуры процессоров формирования и цифровой обработки данных и компьютерных сред на основе оценки эмерджентности;

Предложена и обоснована эффективность применения ТЧБ Крестенсона-Галуа для построения процессоров формирования и цифровой обработки данных с улучшенными системными характеристиками(быстродействия, регулярности, уменьшения числа логических элементов);

Разработаны теоретические основы и алгоритмы выполнения процедур формирования данных и арифметических операций в базисе Крестенсона-Галуа на основе предложенных RCG процессорных элементах.

Предложены принципы реализации элементной базы и разработана архитектура RCG – процессора, который реализует мультибазисные операции, которые обеспечивают улучшение системных характеристик (повышение быстродействия на 30%-40%).

Разработаны принципы построения формирования и цифровой обработки данных со звездно-магистральной архитектурой и повышенным быстродействием по сравнению с процессорами в базисе Радемахера реализованных на одинаковой элементной базе с повышенным быстродействием.

Предложена реализация мультиядерного RCG – процессора на ПЛИС, который выполняет операции матричного умножения, и может быть использован в качестве быстродействующего процессора цифровой обработки данных, а также сопроцессора цифровых телекоммуникационных станций.

Ключевые слова: процессоры цифровой обработки данных, система остаточных классов, базис Галуа, базисные функции, проблемно ориентированные компьютерные системы, теоретико-числовые базисы.

ABSTRACT

Krutskevich N. D. Processors of forming and digital processing of star-main computer systems. - Manuscript.

The thesis for a Ph.D. (candidate of science) degree on specialty 05.13.05 - Elements and Devices of Computing Engineering and Control Systems, Ternopil National Economic University, Ternopil, 2007.

The analysis of processors of the digital processing of data, features of their structural organization is conducted, and also the analysis of theoretical-numerical bases (TNB) of codes, which are used for the construction of processors and their elements, is conducted.

It is proved the efficiency and application of TNB Christenson-Galois is offered for the construction of processors of forming and digital processing of data with improving descriptions (fast-acting, regularity, diminishing of number of logical elements) of the systems;

Theoretical bases and algorithms of implementation of procedures of forming of information and arithmetic operations are developed in the base of Christenson-Galois on the basis of offered RCG of elements of processors.

Principles of realization of element base are offered and architecture of RCG is developed - processor, which realizes multibases operations which provide the improvement of descriptions of the systems (an increase of fast-acting is on 30-40%).

Keywords: processors of the digital processing of data, system of remaining classes, base of Galois, functions of bases, problem oriented computer systems, theoretical-numerical bases.