Баркалов, К М Єфіменко - Розділення кодів при синтезі композиційного пристрою керування з оптимальною адресацією микрокоманд - страница 1

Страницы:
1  2 

УДК 004.274

0.0. Баркалов1, К.М. Єфіменко2 University of Zelena Gora, Poland1

Донецький національний технічний університет, м. Донецьк A.Barkalov@iie.uz.zgora.pl1

РОЗДІЛЕННЯ КОДІВ ПРИ СИНТЕЗІ КОМПОЗИЦІЙНОГО ПРИСТРОЮ КЕРУВАННЯ З ОПТИМАЛЬНОЮ АДРЕСАЦІЄЮ МИКРОКОМАНД

Запропоновано метод, що дозволяє спростити схему адресації композиційного мікропрограмного при­строю керування з оптимальною адресацією мікрокоманд, яка реалізована на FPGA. Метод заснований на використанні процедури елементаризації операторних лінійних ланцюгів з розділенням кодів і опти­мальним кодуванням операторних лінійних ланцюгів. Застосування даного методу забезпечує зменшення числа LUT-елементів в FPGA мікросхемі.

Ключові слова: КМПК, ГСА, ОЛЛ, FPGA, логічна схема, оптимальне кодування

 

Вступ

Спостережуваний в останні роки стрімкий розвиток комп'ютерної техніки неухильно веде до її впровадження практично в усі сфери діяльності людини, що у свою чергу, пред'являє усе більш високі вимоги до характеристик проектованих пристроїв. При цьому основна увага при­діляється як збільшенню швидкодії, так і зниженню апаратурних витрат, що в остаточному під­сумку впливає на зниження собівартості виробів цифрової техніки. Це ставиться як до універ­сальних, так і до спеціалізованих обчислювальних систем, при реалізації яких широко викорис­товуються ПЛІС типу «система-на-кристалі» (SoFC - system-on-a-programmable-chip) [1-4]. До складу SoPC входять засоби для реалізації довільної логіки (FPGA або CPLD), засоби для реалі­зації пам'яті, вбудовані мікропроцесори, вбудовані засоби реконфігурування. Продуктивність таких ПЛІС визначається ефективністю взаємодії всіх вбудованих компонентів [5].

Найважливішою складовою частиною будь-якої цифрової системи є пристрій керування [1,5], який може бути реалізований як композиційний мікропрограмний пристрій керування(КМПК) [6]. При реалізації КМПК в складі SoРС схема адресації мікрокоманд будується на FPGA (field-programmable gate array) - програмувальних користувачем матрицях вентилів, що складаються з мільйонів елементів табличного типу (LUT-елементів) [7,8], а система мікроопе-рацій реалізується на вбудованих блоках пам'яті DMB (dedicated memory block). Обмежене (до 6) число входів LUT-елементів призводить до необхідності декомпозиції булевих функцій [8], що збільшує число LUT-елементів (і їх рівнів) у схемі адресації КМПК. У зв'язку з цим актуа­льною залишається задача розробки нових і удосконалювання відомих методів синтезу КМПК. У даній роботі пропонується удосконалення методу синтезу КМПК з оптимальною адресацією мікрокоманд [10], яке засноване на використанні процедури елементаризації операторних лі­нійних ланцюгів (ОЛЛ) із розділенням кодів.

 

 

Загальні теоретичні положення

Нехай алгоритм керування цифрової системи заданий у вигляді граф-схеми алгоритму (ГСА) Г [6], яка містить початкову b0, кінцеву bE, операторні й умовні вершини. Операторні вершини утворюють множину B1, що має М елементів. У вершинах bqeB1 записуються мікро-команди YqcY, де Y = {y1, yN} - множина мікрооперацій. В умовних вершинах, які утво­рюють множину B2, записуються елементи множини логічних умов X = {x1, xL}. Вершини ГСА утворюють множину B = B1u B2 u {b0, bE}, елементи якої зв'язані дугами з множини E.

Запровадимо ряд визначень [7], необхідних для подальшого викладу матеріалу.

Визначення 1. Операторним лінійним ланцюгом ГСА Г називається кінцева послідов­ність операторних вершин ag = ^bg1,...,bgF ^, для будь-якої пари сусідніх компонентів якої іс­нує дуга (bgi, bgi+1)eE, де i=1,.. .,Fg-1 - номер компонента.

Визначення 2. Вершина bq є Dg, де DgcB1 - множина вершин, які входять в ОЛЛ ag, на­зивається входом ОЛЛ ag, якщо існує дуга <bt, bq) є E, де bt ї Dg.

Визначення 3. Вершина bq є Dg, називається виходом ОЛЛ ag, якщо існує дуга (bq, bt) є E, де bt ї Dg.

Визначення 4. Вхід ОЛЛ називається головним входом, якщо буде відсутнім зв'язок цьо­го входу з виходами операторних вершин.

Визначення 5. Операторні лінійні ланцюги ai, aj є С називаються псевдоеквівалентними ОЛЛ, якщо їхні виходи пов'язані із входом однієї й тієї ж вершини ГСА Г, і утворюють множи­ну класів псевдоеквівалентних ОЛЛ ПС = {В1,     Ві}. I = |ПС|.

Нехай для ГСА Г знайдена розбивка C={ a1, ., aG} множини B1 на операторні лінійні ла-нцюги й нехай для кожної пари сусідніх вершин ОЛЛ a^C виконується умова A(bgi+1) = A(bgi) +1 (i = 1,Fg -1), (1)

де A(bg) - адреса мікрокоманди, яка відповідає вершині b^Bb У цьому випадку пристрій керу­вання цифрової системи може бути реалізовано у вигляді КМПК U1 з оптимальною адресацією мікрокоманд (рис. 1) [10], синтез якого заснований на наявності в ГСА псевдоеквівалентних

ОЛЛ.

По сигналу Start у лічильник СТ заноситься адреса першої мікрокоманди алгоритму, який інтерпретується, а тригер читання ТЧ встановлюється в одиницю (Fetch=1), що дозволяє вибірку мікрокоманд Y із керуючої пам'яті КП. Керуюча пам'ять КП зберігає набори мікроопе-рацій Yq, де Yq с Y = {y1, ..., yN} - мікрооперації, які записані у вершині bq є В1 ГСА Г, і скла­дається з 2R-(N+2) біт. Перший додатковий розряд використовується для зберігання сигналу у0, що забезпечує природну адресацію компонентів ОЛЛ ag є C. Другий - для організації режиму зупинення КМПК (сигнал уЕ). Комбінаційна схема адресації мікрокоманд (САМ) завдяки опти­мальній адресації мікрокоманд, має R1 = ] log2I [ £ R сигналів зворотного зв'язку і реалізує систему функцій

Ф = Ф СТ', Х), (2) які формують у лічильнику СТ адресу A(Igj) j-го вхіду ОЛЛ a^C
Оптимальна адресація мікрокоманд виконується за допомогою модифікованої карти Кар­но. Модифікація карти полягає в тім, що по вертикалі записуються двійкові набори, які ідуть у природному порядку.

Карта Карно, що містить адреси мікрокоманд, надає Л = 2R - M1 клітин для адресації мік­рокоманд ОЛЛ ag є С', тут C' с С - множина ОЛЛ, виходи яких не пов'язані із входом вершиниbE; М1 - число компонентів в ОЛЛ a^C. При виконанні умови

л>Ел i

і=1

адреси компонентів будь-якого ОЛЛ ag є С' можуть бути розташовані в сусідніх клітинах карти Карно, причому компоненти всіх ОЛЛ, що належать i-му класу псевдоеквівалентних ОЛЛ Bi, будуть розташовані в одному кубі розмірності Di.

Запропонований метод оптимальної адресації мікрокоманд [10] дозволяє зменшити число сигналів зворотного зв'язку в схемі адресації мікрокоманд за рахунок зменшення числа аргуме­нтів і числа термів у системі функцій (2). Однак його застосування не завжди можливо. Для до­цільності використання методу необхідне виконання ряду умов [10].

У даній роботі пропонується для вдосконалення методу синтезу КМПК з оптимальною адресацією мікрокоманд використовувати процедуру елементаризації ОЛЛ із розділенням ко­дів. При цьому елементарним ОЛЛ будемо вважати ОЛЛ, який має тільки один вхід [6].

 

 

Основна ідея методу
Тут комбінаційна схема САМ формує систему функцій

Ф = Ф(Т', X), (4)

які задають у регістрі РК код K(ag) поточного ОЛЛ ag є C. Адреса мікрокоманди представлена

у вигляді конкатенації кодів [6]A(Yq) = K(ag) * K(bq),

де A(Yq) - адреса мікрокоманди Yq, яка записана у вершині bq, що входить в ОЛЛ ag і зберіга­ється в керуючій пам'яті КП;

K(ag) - код ОЛЛ ag є C = {a1, ...,aG} розрядності R11=]log2G[; K(bq) - код вершини bq кортежу ag є C розрядності

R12 = ]log2 Fmax[, (5)

де Fmax - максимальне число компонентів ОЛЛ у множині С.

Розрядність адреси мікрокоманди складає R = R11 + R12 і для її подання використовується множина внутрішніх змінних

T = {T    T   T        T }

Використання елементарних ОЛЛ дозволяє подавати на вхід лічильника СТ нульовий код, розрядності R12, який відповідає коду першого компонента поточного ОЛЛ ag є C.

При такому підході коди ОЛЛ і коди їхніх компонентів є взаємно незалежними і на вхід комбінаційної схеми САМ подаються тільки R11 змінних зворотного зв'язку, які утворюють множину T' = {T1,...,TR11} . Це дозволяє зменшити кількість LUT-елементів, які використову­ються для реалізації схеми САМ, в порівнянні з КМПК U1.

Функціонування КМПК U2 відбувається в такий спосіб. По сигналу Start вміст СТ і РК встановлюється в нуль, що є кодом першого компонента першого ОЛЛ ag є C, тобто адресою першої мікрокоманди відповідної ГСА Г. Тригер читання ТЧ встановлюється в одиничний стан і відбувається зчитування мікрокоманди з КП.

Якщо адреса A(Yq) компоненти не є адресою виходу поточного ОЛЛ a^C, те одночасно з мікроопераціями Y^Y формується сигнал y0 = 1. Таким чином, вміст лічильника збільшуєть­ся на 1 і відбувається перехід до наступного компонента Yt поточного ОЛЛ a^C.

Якщо адреса A(Yq) компоненти є адресою виходу Og поточного ОЛЛ, то сигнал y0 = 0, лі­чильник встановлюється в нуль, і схема САМ формує код K(aq) наступного ОЛЛ aq є C відпо­відно до системи (4). Для подання коду використовуються змінні jr є Ф = {ф1,      фR }. При

формуванні сигналу yE тригер ТЧ скидається й функціонування КМПК U2 завершується. Метод синтезу КМПК U2 включає наступні етапи:

1.    Формування C = {a1, ., aG} множини операторних лінійних ланцюгів вхідної

ГСА Г [7].

Розбивка ОЛЛ ag є C вхідної ГСА Г на елементарні ОЛЛ і формування множини еле­ментарних ОЛЛ CE = {a1,      aG }. При цьому розбивка ag є C на елементарні ОЛЛ має сенстільки у випадку, якщо |МІ(Г)| < |І(Г)|.

У загальному випадку, число елементарних ОЛЛ більше числа вхідних ОЛЛ, що збіль­шує довжину таблиці переходів КМПК, але у свою чергу, дозволяє зменшити число змінних зворотного зв'язку на величину

]log2(|I(r)|-|MI(r)|)[.

Для кодування елементарних ОЛЛ ag є CE буде потрібно R11 змінних Tr є T.

3.  Формування розбивки ПCe = {B1,      BI} множини ОЛЛ СЕ на класи псевдоеквівалент-

них ОЛЛ. При цьому розбивка на класи псевдоеквівалентних ОЛЛ виконується тільки для ag є СЕ таких, що вихід цього ОЛЛ не пов'язаний з кінцевою вершиною ГСА. Формування розбив­ки множини ОЛЛ С'Е на класи псевдоеквівалентних ОЛЛ дає П'C = {B1,      BI }, де І1=|П'C, |.

4.  Оптимальне кодування елементарних ОЛЛ ag є CE двійковими кодами K(ag) розрядно-сті R11 = ]log2GE[ і кодування компонентів bq ОЛЛ agєCE двійковими кодами K(bq) розрядності R12 (5). При цьому оптимальне кодування елементарних ОЛЛ ag є C'E виконується за допомо­гою модифікованої карти Карно, аналогічно кодуванню псевдоеквівалентних станів автомата Мура [9]. Кожному елементарному ОЛЛ a^C'E ставиться у відповідність Rn-розрядний код і всі ОЛЛ ag є Ві повинні розташовуватися в одному кубі булева простору, це дозволяє отримати коди однозначно ідентифікуючі класи псевдоеквівалентних ОЛЛ Bi є П' C' . Такий підхід при-

CE

водить до зменшення числа змінних зворотнього зв'язку Tr є T' від значення R11 до R13 = ]log2I[.

5.  Формування вмісту керуючої пам'яті КП.

6.  Формування таблиці переходів КМПК. Для побудови таблиці переходів КМПК U2 (Г) виконується формування системи формул переходу, у яких виходи ОЛЛ ag є Bi заміняються відповідними класами Bi є П C' , а входи ОЛЛ заміняються ОЛЛ aq є CE, у які відбувається пе-

CE

рехід. При цьому не використовуються формули для класів Bi є       , у які входять ОЛЛ

 

aq ї C'e.

Таблиця переходів КМПК U2 (Г) містить наступні колонки: Bi, K(Bi), aq, K(aq), Xh, Fh, h, де Bi є П' C' ; K(Bi) - код класу псевдоеквівалентних ОЛЛ однозначно ідентифікуючий клас Bi

CE

є П' C, ; aq - ОЛЛ aq є CE, у який є перехід з виходу ОЛЛ ag є Ві під дією сигналу Xh; K(aq) -

Страницы:
1  2 


Похожие статьи

Баркалов, К М Єфіменко - Розділення кодів при синтезі композиційного пристрою керування з оптимальною адресацією микрокоманд