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

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2008
Автор: Николайчук, Я.М.
Формат: Стаття
Мова:Українська
Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 2008
Теми:
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/7482
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора / Я.М. Николайчук // Штучний інтелект. — 2008. — № 4. — С. 387-394. — Бібліогр.: 3 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859559163745533952
author Николайчук, Я.М.
author_facet Николайчук, Я.М.
citation_txt Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора / Я.М. Николайчук // Штучний інтелект. — 2008. — № 4. — С. 387-394. — Бібліогр.: 3 назв. — укр.
collection DSpace DC
description Викладені теоретичні основи систем числення та цифрових перетворень у різних теоретико-числових базисах. Розроблена структура супершвидкодіючих мультибазисних процесорів.
first_indexed 2025-11-26T15:07:31Z
format Article
fulltext «Штучний інтелект» 4’2008 387 4Н УДК 681.215 Я.М. Николайчук Інститут проблемно-орієнтованих комп’ютерних систем, м. Тернопіль, Україна ozm@yandex.ru Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора Викладені теоретичні основи систем числення та цифрових перетворень у різних теоретико-числових базисах. Розроблена структура супершвидкодіючих мультибазисних процесорів. Вступ Світовий досвід створення процесорів для комп’ютерних систем за останні 50 років, поряд із застосуванням теоретико-числового базису (ТЧБ) Радемахера, який породжує двійкову систему числення, демонструє тенденцію все ширшого застосування інших ТЧБ, в тому числі: унітарного, Хаара, Крейга, Крестенсона, Уолша та Галуа. Реалізація спеціалізованих, сигнальних, комутаційних та проблемно-орієнтованих процесорів циф- рової обробки даних часто виконується на базі сумісного використання комбінацій наз- ваних ТЧБ, наприклад Уолша – Хаара, Крестенсона – Галуа та ін. Перспективним напрямком розвитку теорії та технологій побудови універсальних комп’ютерних засобів є реалізація супершвидкодіючих мультибазисних RCG-процесо- рів на основі базисів Радемахера, Крестенсона і Галуа. Відомі успішні спроби розвитку теорії та техніки побудови матричних процесорів на основі двовимірних базисів Радемахера та Галуа, а також конвеєрних спецпроцесорів у базисі Галуа. Спостережувані тенденції розвитку теорії методології та техніки процесорів комп’ютерних систем обумовлені теоретичним та ідейним насиченням можливостей застосування базису Радемахера для побудови арифметико-логічних компонентів процесорів, до яких ставляться все жорсткіші вимоги щодо швидкодії, покращення регулярності структури та розширення функціональних можливостей. У зв’язку з цим існує проблема глобального дослідження характеристик «нераде- махівських» ТЧБ та граничних можливостей їх застосування для реалізації компонентів як спеціалізованих, так і універсальних процесорів. При цьому перспективним викорис- танням, крім найбільш сьогодні масового одновимірного (векторного) представлення чисел та виконання арифметико-логічних операцій у базисі Радемахера, є застосування двовимірних систем числення, вертикальної інформаційної технології у базисі Галуа та різних форм багатовимірного представлення чисел у вигляді залишків різних форм системи залишкових класів базису Крестенсона. 1. Теоретико-числові базиси та їх характеристики Далі приведені кодові матриці відомих ТЧБ, а в табл. 1 їх характеристики у вигляді оцінок сумарного числа елементів відповідних кодових матриць та числа активних елементів. Николайчук Я.М. «Искусственный интеллект» 4’2008 388 4Н 10...000 11...000 .................. 11...100 11...110 11...111 01...111 .................. 00...011 00...001 00...000 LibCrM n n Cres aaa PPP M ... ............ 6...10 5...02 4...41 3...30 2...22 1...11 0...00 ... 21 21  0 0 1 0 1 1 1 GalM Таблиця 1 Базис Коди N V Унітарний Унітарні N = n V = n2 Хаара Розрядно-позиційні N = n V = n2 Крейга Лібова – Крейга N = 2n 2 2NV  Радемахера Двійкові N = 2n V = Nlog2 N Радемахера Грея N = 2n V = Nlog2 N Радемахера Уолша N = 2n V = Nlog2 N Крестенсона СЗК    m i iPN 1 )(log 1 2 i m i PV    Галуа М-послідовності N = 2n – 1 V = N Галуа Галуа N = 2n V = N Дані названих таблиць свідчать про те, що однаковими кодовими матрицями володіють базиси Уолша, Грея, Радемахера та Крестенсона, а найбільш компактною матрицею, яка вироджується у вектор, володіє базис Галуа. 2. Системи числення, які породжуються ТЧБ Фундаментальні теоретичні дослідження ТЧБ показують, що тільки в базисах Уолша та Грея не породжені доступні для практики системи числення, а системи числення, породжені іншими базисами, знайшли широке застосування в теорії та техніці побудови процесорів різних рівнів комп’ютерних систем. 10...000 01...000 .................. 00...100 00...010 00...001 00...000 harM 11...111 01...111 .................. 01...001 10...001 00...001 .................. 11...000 01...000 10...000 000000 RadM 000...001 ..................... 110...111 011...111 111...111 ..................... 110...000 100...000 000...000 GrM 11...111 01...111 ................... 00...111 00...011 00...001 00...000 MUni  101010 001110 110011 111010 111000 000000   WalM Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора «Штучний інтелект» 4’2008 389 4Н Унітарна система числення, незважаючи на значну інформаційну надлишковість, знайшла успішне застосування в унітарних кореляційних процесорах та в галузі цифро- вої обробки зображень, особливо опто-електронними процесорами, цифровій голографії, томографії, а також широкого спектру формувачів та перетворювачів форм інформації на рівні сенсорів, мікроконтролерів та телекомунікаційних процесорів. Система числення базису Хаара знайшла виключно масове застосування в стан- дартних засобах взаємодії оператор – дисплей, виборчих бюлетневих системах, лото, тестах. Модифікації системи числення базису Хаара широко використані для захисту даних від помилок, наприклад, одновимірних та двовимірних кодах парності та ін. Система числення базису Крейга знайшла застосування для реалізації найбільш швидкодіючих операційних пристроїв на базі лічильників Джонсона. Система числення базису Радемахера, виключно її модифікація – двійкова система числення, знайшла на сьогодні найширше застосування для побудови універсальних мікропроцесорів комп’ютерних систем. Значно вужче досягнуто застосування двійково- десяткової, трійкової, двійково-вісімкової, мінус-двійкової та інших її модифікацій. Система числення залишкових класів (СЗК) базису Крестенсона, розроблена І.Я. Акушським та Д.І. Юдицьким, особливо її цілочисельна форма, широко використо- вувалась починаючи з 70-х років минулого століття для побудови швидкодіючих спеці- алізованих процесорів систем повітряної оборони колишнього Радянського Союзу, а також за той же період реалізована автором у системі контролю та управління процесами буріння «АТОС-Б» та інших цифрових пристроях низових рівнів комп’ютерних систем. Відомі модифікації СЗК над комплексними числами академіка Р.А. Амербаєва не були масово реалізовані у промислових системах. Нормалізована форма СЗК, запропонована нами, використана тільки в телеко- мунікаційних процесорах інформаційних систем нафтогазової промисловості. Перспективними модифікаціями СЗК, які в даний час глибоко досліджуються на кафедрі спеціалізованих комп’ютерних систем Тернопільського національного еконо- мічного університету науковою школою автора, є розроблена досконала цілочисельна та особливо її нормалізована форма, а також запропонована розмежована форма СЗК. Система числення в базисі Галуа знайшла потужне застосування при реалізації вертикальної інформаційної технології у розподілених комп’ютерних системах конт- ролю та обліку витрати енергоносіїв «ALFIYA», а також реалізації швидкодіючих кон- веєрних спецпроцесорів. В даний час виконуються активні дослідження двовимірних (матричних) форм систем числення базисів Радемахера та Галуа. Особливий інтерес в світі отримали дослідження багаторівневих форм системи числення базису Галуа, наприклад, по mod 4, що відповідає четвірці нуклеотидів амінокислот А, Т, G, С і може бути фундаментальною теоретичною основою інфор- маційної теорії молекули ДНК, яка характеризується багатьма подібними ознаками з рекурентними послідовностями (ланцюгами) Галуа. Ще чекає своїх фундаментальних досліджень циліндрична форма кодів двій- кової та четвіркової систем числення Галуа. Перспективу ефективного застосування мають коди Галуа для захисту інформації, стиснення даних та реалізації багато- рівневих рекурентних структур баз даних. Николайчук Я.М. «Искусственный интеллект» 4’2008 390 4Н 3. Структура супершвидкодіючих мультибазисних процесорів На рис. 1 показана структура мультибазисного RCG-процесора із зірково-магіст- ральною архітектурою. Рисунок 1 – Структура RCG-процесора: R – процесор Радемахера; С – процесор Крестенсона; G – процесор Галуа; ПКД – асоціативна пам’ять колективного доступу у базисі Галуа Дана структура використана в якості високопродуктивного комутаційного про- цесора системи «Оптіма телеком» і, як показано Н.Д. Круцкевичем, характеризується максимальною емерджентністю і забезпечує підвищення швидкодії обробки даних на 1 – 2 порядки відносно до існуючих процесорів у базисі Радемахера. Особливістю реалізації пам’яті арифметичного пристрою RCG-процесора є її виконання на основі використання базису Крестенсона – Галуа, що суттєво зменшило об’єм та структурну складність мікроелектронного обладнання. 4. Теорія цифрових перетворень у базисі Крестенсона 4.1. Теоретичні основи цілочисельної форми системи залишкових класів В основу цілочисельного перетворення СЗК покладена Китайська теорема про залишки [1]. Суть прямого перетворення цілочисельної форми СЗК полягає в тому, що згідно з теоремою про залишки будь-яке ціле число можна однозначно перетво- рити набором найменших невід’ємних залишків в системі взаємопростих модулів, що відповідає рішенню діафантового рівняння )(mod iik pbN  , яке відповідає ціло- чисельному рішенню лінійного рівняння: iiik bpaN  , де ai – ранг, bi – найменший невід’ємний залишок. При цьому діапазон кодування чисел Nk дорівнює:    k i ipP 1 ; 0  Nk  P . Таким чином ціле число Nk однозначно представляється набором залишків bi. Зворотне перетворення цілочисельної форми СЗК виконується згідно з аналі- тичним виразом [2]    k i iik PresN Bb 1 )(mod , (1) Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора «Штучний інтелект» 4’2008 391 4Н де Bi – базисні числа СЗК, які обчислюються згідно з діафантовим рівнянням: ).(mod1 ii i i Pm p PB  (2) Теорія виконання алгоритму операцій додавання, віднімання та множення в цілочисельній формі СЗК детально викладена в роботах [2], [3]. В основу арифме- тики залишкових класів покладено глибоке розпаралелювання обробки даних, яке виконується по кожному модулю pi окремо з виключенням міжрозрядних переносів. Недоліком цілочисельної форми перетворення СЗК є практична відсутність простої операції порівняння чисел, що суттєво ускладнює реалізації алгоритмів та відповідних процесів ділення. В той же час переваги однотактного матричного вико- нання інших арифметичних операцій забезпечують широкі перспективи застосування теоретичних основ цілочисельного перетворення СЗК для створення та широко- масштабного впровадження супершвидкісних процесорів в комп’ютерних мережах. 4.2. Теорія нормалізованої форми СЗК Теоретичною основою утворення нормалізованої форми СЗК (НСЗК) є норма- лізація по модулю Р обох частин рівняння зворотнього перетворення цілочисельної форми СЗК (1):     k i iik P PBb res P N 1 )(mod , звідки    k i i ik P B bresN 1 0 )1(mod][ , де 1][0 0  PN k ; i i pP B 1  , а з врахуванням виразу (2) отримаємо: )1(mod][ 1 0    k i i i ik p mbresN або    k i iik mbresN 1 00 ),1(mod][][ (3) де i i i p bb 0][ , а .1][0 0  ib Для забезпечення однозначного кодування даних в НСЗК необхідно викону- вати умову: Pp 1  . Дана формула визначає необхідне число розрядів після коми, у відповідній системі числення при представлені величини 1/Р в нормалізованій формі, тобто  pi gggggggg p n i  ,01  , де g – цифри у відповідній системі числення, ni – число розрядів, до яких заокруглю- ється результат ділення з преведенням до меншого цілого, а δр – дробова частина, яка визначає величину похибки δр, якою нехтують. Таким чином аналітичний вираз з НСЗК в СЗК отримує вигляд: PNN kk  0]int[ , де int – символ операції виділення цілої частини. Перевагою НСЗК є виконання операцій над залишками в нормалізованій формі, що спрощує реалізацію процесорів на основі даного базису за рахунок виключення нелінійних операцій отримання залишку по кожному з модулів процесора, а також заміни операції по «mod P» на операцію по «mod1», яка виконується шляхом простого відкидання цілої частини результату згідно з операцією int. Николайчук Я.М. «Искусственный интеллект» 4’2008 392 4Н 4.3. Теорія досконалої форми СЗК Аналіз формули перетворення СЗК (1) може бути представлений в наступному вигляді:    k i i i ik Pm p PbresN 1 )(mod , де 10  ii pm . (4) Очевидно, що наявність коефіцієнтів mi в формулі (4) ускладнює реалізацію алгоритму виконання цілочисельного перетворення СЗК. Дослідження різних набо- рів pi, яким відповідають набори коефіцієнтів mi в теоретико-числовому аспекті показали, що існують такі набори модулів р1, p2,...,pk, які відповідають умовам взаєм- ної простоти з одиничними коефіцієнтами mi(m1 = m2 = ... = m i = ... = mk = ... = 1) . Пошук наборів модулів, що породжують ДСЗК, є окремою актуальною задачею фундаментального рівня, яка досліджувалась в роботі [1]. 4.4. Аналітика досконалої нормалізованої форми СЗК (НДСЗК) Для створення повної функціонально-ефективної СЗК потрібно спростити існуючі алгоритми виконання операцій порівняння чисел. Умову створення швидкісного прист- рою в РСЗК задовольняють алгоритми обчислення всіх арифметичних операцій, крім ділення. Для реалізації операції ділення потрібна НДСЗК. Теоретичною основою даної форми є рівняння (3), підставивши в яке m1 = m2 = mk = 1, отримаємо базове рівняння перетворення НДСЗК у вигляді:    k i ik bresN 1 00 ).1(mod][][ (5) З рівняння (5) видно, що з перетворення HДСЗК виключена операція множення і саме перетворення виконується у вигляді сумування нормалізованих залишків [bi]0 по mod1, що відповідає операції int відкидання цілої частини результату. 5. Теорія розмежованої форми СЗК Теоретично основою РСЗК є цілочисельна форма СЗК, рівняння якої представ- лено у вигляді суми: ,......21 nkikkkk NNNNN  де Nik – m-розрядний (розмежований) фрагмент числа Nk, яке представлене у двій- ковій системі числення, числового базису Радемахера. Наприклад 32-розрядний про- цесор СЗК може бути розмежований на 4 фрагменти по 8 біт (рис. 2). Рисунок 2 – Процес розмежування 32-розрядного процесора 1 8 9 16 179 24 25 32 N1k N2k N3k N4k Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора «Штучний інтелект» 4’2008 393 4Н Таким чином, пряме перетворення РСЗК отримає вигляд: При цьому математичні операції над числами в РСЗК можуть бути розмежовані по кожному із фрагментів процесора, що забезпечує ще більш глибокий рівень розпа- ралелювання обробки інформації, а відповідно підвищення швидкодії процесора СЗК. Таким чином, у загальному вигляді зворотне перетворення РСЗК аналітично описується виразом: .modmod)......( 1 1 21    n r ii k i niriiik PBPbbbbresresN Реалізація процесора на основі даної формули у вигляд РСЗК може бути вико- нана з суттєвим зменшенням апаратних засобів за кожним з модулів. 6. Теорія перетворень у базисі Галуа Операція сумування кодів у базисі Галуа для суматорів в діапазоні 2k – 1 вико- нується шляхом виконання логічних операцій над бітами коду Галуа першого з доданків згідно з таблицею логічних рівнянь, що описують другий доданок. В табл. 2.12 подані фор- мули логічного опису бітів другого доданку, на прикладі 4-розрядного коду Галуа для су- маторів в діапазоні 2k, що досягається введенням додаткової комбінації «0000» в позиції 12. Таблиця 2 Формула суматора Десят- кове значен. Код Галуа b4 b3 b2 b1 0 1111 4b 3b 2b 1b 1 1110 3b 2b 1b 341 bbb  2 1101 3b 1b 2b 41 bb  3 1010 2b 2b 41 bb  421 bbb  4 0101 1b 41 bb  421 bbb  4321 bbbb  5 1011 41 bb  421 bbb  4321 bbbb  321 bbb  6 0110 421 bbb  4321 bbbb  321 bbb  432 bbb  7 1100 4321 bbbb  321 bbb  432 bbb  31 bb  8 1001 321 bbb  432 bbb  31 bb  42 bb  9 0010 432 bbb  31 bb  42 bb  431 bbb  10 0100 31 bb  42 bb  431 bbb  21 bb  11 1000 42 bb  431 bbb  21 bb  32 bb  12 0000 431 bbb  21 bb  32 bb  43 bb  13 0001 21 bb  32 bb  43 bb  4b 14 0011 32 bb  43 bb  4b 3b 15 0111 43 bb  4b 3b 2b Nk = b1 = (b11+ b21+...+ br1+...+ bn1) modp1 ... bi = (b1i+ b2i+...+ bri+...+ bni) modpi ... bk b2 = (b1k+ b2k+...+ brk+...+ bnk) modpk. b2 = (b12+ b22+...+ br2+...+ bn2) modp2 Николайчук Я.М. «Искусственный интеллект» 4’2008 394 4Н Такий спосіб опису функцій суматора в базисі Галуа передбачає емуляцію його роботи виключно програмним шляхом, що не дозволяє перейти до його апаратної реалізації. В роботі запропоновано метод виконання операції сумування на основі матриці коефіцієнтів dij (табл. 2.13), яка використовується для логічного формування бітів коду Галуа суми доданків згідно з виразом: 11,11,, ... bdbdbdb ikkikkii   . Таблиця 3 Формула суматора Десяткове значення Код Галуа dj4 dj3 dj2 dj1 0 1111 1000 0100 0010 0001 1 1110 0100 0010 0001 1001 2 1101 0010 0001 1001 1011 3 1010 0001 1001 1011 1111 4 0101 1001 1011 1111 0111 5 1011 1011 1111 0111 1110 6 0110 1111 0111 1110 0101 7 1100 0111 1110 0101 1010 8 1001 1110 0101 1010 1101 9 0010 0101 1010 1101 0011 10 0100 1010 1101 0011 0110 11 1000 1101 0011 0110 1100 12 0000 0011 0110 1100 1000 13 0001 0110 1100 1000 0100 14 0011 1100 1000 0100 0010 15 0111 0111 1110 1101 0011 Розглянемо приклад виконання операції додавання двох чисел в базисі Галуа на основі матриці коефіцієнтів dij. Нехай Х(10) = 2; Y(10) = 5, тоді ХG = 1101; YG = 1011. Тобто ХG відповідає коду b4 = 1; b3 = 1; b2 = 0; b1 = 1, а код YG згідно з табл. 2.13 відповідає логічним операціям над бітами XG: 421 bbb  ; 4321 bbbb  ; 321 bbb  ; 432 bbb  , що відповідає кодам dij 1011; 1111; 0111; 1110 з табл. 2.14. Тобто результат сумування даних чисел виконується за допомогою логічної обробки кодів XG та коефіцієнтів dij, які відпо- відають коду YG: 4 4 3 2 11 0 1 1 1 1 0 1 1 0 1 1 1G b b b b                 ; 3 4 3 2 11 1 1 1 1 1 1 1 1 0 1 1 1G b b b b                 ; 2 4 3 2 10 1 1 1 0 1 1 1 1 0 1 1 0G b b b b                 ; 1 4 3 2 11 1 1 0 1 1 1 1 1 0 0 1 0G b b b b                 . Отримана система логічних рівнянь дозволяє синтезувати структуру 4-бітового суматора Галуа. Висновки В даній роботі викладені основні теоретичні засади побудови супершвидкодію- чих мультибазисних процесорів, які обґрунтовують перспективний напрям розвитку супершвидкодіючих мультибазисних процесорів, в першу чергу спеціалізованого, а в майбутньому ефективного універсального застосування. Література 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных класах. – М: Сов. радио, 1968. – 440 с. 2. Николайчук Я.М., Волинський О.І., Кулина С.В. Теоретичні основи побудови спецпроцесорів у базисі Крестенсона // Вісник Хмельницького національного університету – 2007. – Т.1(93), №3. – С. 85-90. 3. Бухштаб А.А.Теория чисел. – М.: Просвещение, 1966. – 384 с. Стаття надійшла до редакції 29.07.2008.
id nasplib_isofts_kiev_ua-123456789-7482
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1561-5359
language Ukrainian
last_indexed 2025-11-26T15:07:31Z
publishDate 2008
publisher Інститут проблем штучного інтелекту МОН України та НАН України
record_format dspace
spelling Николайчук, Я.М.
2010-03-31T15:27:50Z
2010-03-31T15:27:50Z
2008
Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора / Я.М. Николайчук // Штучний інтелект. — 2008. — № 4. — С. 387-394. — Бібліогр.: 3 назв. — укр.
1561-5359
https://nasplib.isofts.kiev.ua/handle/123456789/7482
681.215
Викладені теоретичні основи систем числення та цифрових перетворень у різних теоретико-числових базисах. Розроблена структура супершвидкодіючих мультибазисних процесорів.
uk
Інститут проблем штучного інтелекту МОН України та НАН України
Распознавание образов. Системы цифровой обработки сигналов и изображений
Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
Article
published earlier
spellingShingle Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
Николайчук, Я.М.
Распознавание образов. Системы цифровой обработки сигналов и изображений
title Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
title_full Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
title_fullStr Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
title_full_unstemmed Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
title_short Теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
title_sort теорія цифрових перетворень мультибазисного супершвидкодіючого процесора
topic Распознавание образов. Системы цифровой обработки сигналов и изображений
topic_facet Распознавание образов. Системы цифровой обработки сигналов и изображений
url https://nasplib.isofts.kiev.ua/handle/123456789/7482
work_keys_str_mv AT nikolaičukâm teoríâcifrovihperetvorenʹmulʹtibazisnogosuperšvidkodíûčogoprocesora