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

Размещено на http://www.allbest.ru/

Київський університет імені Тараса Шевченка

Медведєв Михайло Геннадійович

УДК 681.3

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

01.05.03 - математичне та програмне забезпечення обчислювальних машин та систем

Автореферат

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

Київ-1999



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

Робота виконана на кафедрі математичної інформатики факультету кібернетики Київського університету імені Тараса Шевченка.

Науковий керівник - кандидат фізико-математичних наук, доцент

Глибовець Микола Миколайович

Офіційні опоненти:

1. доктор технічних наук Цейтлін Георгій Овсійович (Міжнародний Соломонів університет, професор факультету комп'ютерних наук)

2. кандидат фізико-математичних наук, доцент Проценко Володимир Семенович (Київський університет імені Тараса Шевченка, доцент)

Провідна організація - Інститут Кібернетики ім. В.М. Глушкова НАН України, відділ цифрових автоматів, м. Київ.

Захист відбудеться 25 березня 1999 р. на засіданні спеціалізованої вченої ради Д 26.001.09 Київського університету імені Тараса Шевченка, Київ, пр. Глушкова, 2, корп.6, ф-т кібернетики, ауд. 40 о 14 годині. (Тел.252-58-83. Факс 266-12-49, E-mail: rada@cyber.univ.kiev.ua)

З дисертацією можна ознайомитися у Науковій бібліотеці Київського університету імені Тараса Шевченка, Київ, вул. Володимирська, 58

Автореферат розісланий 17 лютого 1999 р.

Вчений секретар спеціалізованої вченої ради В.П.Шевченко



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

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

Актуальність цих питань визначав ще в своїх роботах В.М.Глушков. Питання раціонального конструювання або синтезу схем цифрових машин з програмним керуванням В.М.Глушков розглядав в контексті синтезу цифрових автоматів Глушков В.М. Синтез цифровых автоматов, М. Физматгиз , 1962, 216с., оскільки довільна ЕОМ є прикладом одного з найбільш поширеного типу перетворювачів дискретної інформації - дискретних автоматів.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи пов'язана з науково-технічними роботами, що виконувалися в Київському університеті імені Тараса Шевченка:

“Створення технології програмування для перспективних паралельних обчислювальних комплексів”, тема № 97058.

“Дослідження та теоретичне обгрунтування принципів проведення на ЕОМ логіко - алгебраїчних побудов у формальних теоріях”, тема №97060.

“Розробка комутаційних структур для паралельних обчислень”, тема №97058.

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

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

Наукова новизна роботи.

- В роботі вперше введено поняття КЕ, запропоновано його математичну модель та детально досліджено його функціональні властивості.

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

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

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

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

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

Матеріали дисертаційної роботи використовувалися при читанні спецкурсу ”Алгоритми на мережах”.

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

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

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

Міжнародній науково - технічній конференції “Сучасні методи цифрової обробки сигналів в системах вимірювання, діагностики та керування ОС-98”, м. Мінськ;

Міжнародному семінарі “The Information Technology Contribution to the building of a Safe Regional Environment”, AFCEA, EUROPE, Kiev Seminar;

Семінарах кафедри МІ та САТР Київського університета імені Тараса Шевченка;

Наукових конференціях НаУКМА “Наука. Людина. Суспільство.” у 1997 - 1999 роках.

Публікації. За темою дисертації опубліковано 3 статті.

Структура та об'єм роботи. Дисертація складається зі вступу, трьох глав, висновків, списку літератури та програм. Загальний об'єм роботи складає 110 сторінок, список літератури нараховує 89 найменувань.

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

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

В першій главі даються основні поняття часової логіки [1] та засоби доведення властивостей схем (коректності, взаємного виключення, безпеки та інші). Наводиться структура КЕ, досліджуються його функціональні можливості. Для побудови схем на КЕ розглядається поняття комутаційної мережі. Наведено схеми базових цифрових пристроїв (асинхронний RS - тригер, D - тригер, суматор, перетворювачі кодів - шифратор та дешифратор, мультиплексор, лічильник) на КЕ з доведенням коректності їх роботи за допомогою часової логіки.

В параграфі 1.1. даються основні поняття часової логіки, яка є основним інструментом для доведення коректності роботи схем, побудованих на КЕ.

Означення 1.1.1. Дією будемо називати бінарне відношення A М S ґ S (- множина станiв системи що досліджується).

Означення 1.1.2. Дія A називається завжди вiрною, якщо вона має мiсце для будь-яких станів: [[A]] = " s, t О S: A(s, t).

Означення 1.1.3. Нехай P, Q - предикати, A - дiя. Трійка {PAQ} називається трiйкою Хоара, якщо має місце: P Щ A ® Q, тобто, якщо дія є A - дiею та P вiрне, тодi пiсля виконання A - дії Q також стане вірним.

Означення 1.1.4. Обчисленням (або поведiнкою) програми (системи) P називається скiнченна або нескiнченна послiдовнiсть станiв та переходiв:

r0 r1 r2

s : s0 ® s1 ® s2 ®..., що задовольняє таким умовам:

iнiцiалiзацiя : s0 О S;

успадкування: "i (si+1 О ri(si));

закiнчення: s - скiнченна i закiнчується в sk, якщо sk - останнiй стан в s i "r (r О T & r(sk) = 0) .

Означення 1.1.5. Формула F називається вiрною, якщо вона вiрна на всiх поведiнках: [[F]] = "s О SҐ : [[F]](s)

Означення 1.1.6. Часовий логiчний оператор Ђ ("завжди") визначається наступним чином: [[ЂF]](s) = " i і 0: [[F]](s+i ). ЂF - означає, що F має мiсце завжди: зараз i в майбутньому.

Означення 1.1.7. Вiдношенням доступностi R(s,t) будемо називати відношення мiж станами, яке означає можливiсть переходу із стану s до стану t.

Означення 1.1.8. Часовий оператор коли-небудь а визначається наступним чином: аF ШЂШF або |аw|s = $t [R(s, t) & |w|t]. Він означає, що аw буде вiрним в s, якщо w вiрне хоча б в одному R - доступному станi з s.

Означення 1.1.9. Базовими темпоральними операцiями називаються:

Успадкування (Next) , | w|s = (s + 1 < s & |w|s+1); ;

Буде (Until) , |w1Uw2| = ;

Передування (Previous) Е, |Еw|s = (s>0 & |w|s+1);

Було (Since) S, ;

Означення 1.1.10. Двi формули w1 i w2 називаються еквiвалентними (w1 = w2), якщо на будь-якому станi k поведiнки s : |w1|k = |w2|k.

Означення 1.1.11. Двi формули w1 i w2 називаються початково еквiвалентними (w1 = Init w2), якщо: "s : |w1|0 = |w2|0.

Означення 1.1.12. Допоміжними часовими операціями називаються:

Слабке успадкування: , яке означає, що на наступному кроцi або закiнчиться обчислення, або буде w.

||=||

Слабке передування: = , яке означає, що або процес тiльки почався /знаходиться в початковому станi/, або попереднiм було w.

||=||

Поки: w1 U w2 = - i означає, що або w1 буде завжди, або після w1 буде w2.

Слабке поки: w1Sw2 = - i означає, що або завжди w1, або спочатку було w2, а після нього стало w1.

Для доведення формул часової логіки введемо поняття моделі мови та обчислення на ній.

Означення 1.1.13. Моделлю мови називається трійка (I, a, s), де:

I - інтерпретація (можливо глобальна);

a - присвоєння;

s - послідовність станів.

Iнтерпретацiя I специфікує область обчислень, присвоює конкретні елементи, функції, предикати константам, функціям i предикатним символам. Присвоєння a присвоює значення у відповідній області кожної індивідуальної глобальної вільної змінної.

Означення 1.1.14. Формула, яка вірна на будь-якій моделі, називається тотожно вірною i позначається w.

Означення 1.1.15. Формула називається задовiльняючою, якщо існує модель, на якій вона вірна.

Розглянуто властивості часткової коректності, безпеки, повної коректності, гарантованості, обов'язковості, відгуку, постійності, реагування [2].

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

Означення 1.2.1. Комутаційним елементом називатимемо систему (L, R, U, D, S), де L, R, U, D - інформаційні полюси, а S - керуючий полюс.

Означення 1.2.2. Полюси L та D називаються вхідними, а R та U - вихідними.

Твердження 1.2.1. Зв'язок між вихідними (Out1, Out2), вхідними (In1, In2) та керуючим (S) полюсами КЕ можна описати наступними булевими формулами:

Out1 = ШSЩIn1 Ъ SЩIn2

Out2 = ШSЩIn2 Ъ SЩIn1

Твердження 1.2.2. В термінах часової логіки умову безпеки роботи КЕ можна описати формулою:

((S = 1 Й Out1 = In1 Щ Out2 = In2) Ъ (S = 1 Й Out1 = In1 Щ Out2 = In2)).

В параграфі 1.3. розглядаються функціональні властивості КЕ та досліджується можливість реалізації унарних та бінарних функцій на КЕ. Вводиться поняття комутаційної таблиці, за допомогою якої відстежуються функціональні можливості КЕ. Теореми 1.3.1. та 1.3.2. є основним результатом цього параграфа.

Означення 1.3.1. Вхід будемо називати зв'язаним, якщо його зафіксовано в 0 чи 1, інакше - вільним.

Означення 1.3.2. Комутаційною таблицею будемо називати таблицю, яка складається з N стовпчиків. N = Bound + Nout, де Bound - кількість зв'язаних входів, Nout - кількість виходів (далі Nout завжди буде дорівнювати 2). Стовпчики, які вдповідають зв'язаним входам, містять всі можливі значення з 0 та 1. Стовпчики, які відповідають виходам, містять функції, які утворюються між ними та вільними входами.

Теорема 1.3.1. На одному КЕ можна реалізувати тільки одну унарну функцію - заперечення.

Теорема 1.3.2. На одному КЕ можна реалізувати лише чотири бінарних булевих функції: диз'юнкцію OR, кон'юнкцію AND, імплікацію Й та обернену антиімплікацію М .

В параграфі 1.4. розглядається можливість утворення схем, які складаються з декількох КЕ, наводиться поняття комутаційної мережі. Розглядається алгоритм функціонування комутаційної мережі, вводиться поняття такту.

Означення 1.4.1. Комутаційною мережею будемо називати трійку <G, Pol, Sgn>, де G = G (K,E) - комутаційний граф, в якому K - множина КЕ, а E - множина зв'язків між ними, Pol = Pol (In,Out) -множина вхідних In та вихідних Out полюсів. На вхідні полюси In подаються сигнали Sgn = {0, 1}, а на вихідних полюсах Out знімаються сигнали. На деякі полюси дозволяється подавати сталі сигнали, але ці полюси не будемо відносити ані до вхідних, ані до вихідних.

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

Таким чином значення сигналу на будь-якому вихідному полюсі залежить від значень сигналів на вхідних полюсах, тобто для будь-якої схеми на КЕ існує певна функціональна залежність кожного виходу від входів. Утворюється m булевих функцій від n аргументів, де n = |In|, m = |Out|. Аргументами функцій є значення сигналів на вхідних полюсах.

Важливою характеристикою комутаційної мережі є час її роботи або комутації.

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

В теоремах 1.4.1. та 1.4.2. представлено дві схеми на КЕ, які реалізують булеві функції штрих Шефера та стрілку Пірса. Час роботи першої схеми складає 3 такти, другої схеми - два такти.

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

Означення 1.5.1. Тригером називається пристрій з двома стійкими станами рівноваги, які призначені для зберігання інформації.

Теорема 1.5.1. Асинхронний RS тригер може бути реалізовано на двох КЕ. Безпеку роботи схеми забезпечує істинність наступної часової формули:

((S = 1 Щ R = 0 Й (Q = 1)) Ъ (S = 0 Щ R = 1 Й (Q = 0)) Ъ

Ъ (S = 0 Щ R = 0 Щ Q = i Й (Q = i)), i О {0,1}.

Теорема 1.5.2. D - тригер можна реалізувати на трьох КЕ. Безпеку роботи D - тригера забезпечує істинність наступної часової формули:

((C = 1 Й (Q = D)) Ъ (C = 0 Щ Q = i Й (Q = i)), i О {0,1}

Теорема 1.5.3. На n КЕ можна побудувати схеми n - арної диз'юнкції, кон`юнкції та додавання за модулем два, причому час їх роботи дорівнює двом тактам.

Теорема 1.5.4. Генератор прямокутних імпульсів можна побудувати на одному КЕ, безпека роботи якого описується формулою:

((Q = i) Й (Q = Шi)) , i О {0,1}.

Означення 1.5.2. Коміркою пам'яті називається пристрій, в який можна записувати та з якого можна читати одиницю інформації.

Теорема 1.5.5. Комірку пам'яті можна реалізувати на двох КЕ. Якщо через A позначати значення, записане до комірки, то безпеку роботи схеми можна описати часовою формулою:

((K = 1 Й A = D) Ъ (K = 0 Й D = A)).

Серед схем, які реалізують перетворення кодів, розглянуті схеми дешифратора та шифратора.

Означення 1.5.3. Дешифратором називається схема, яка перетворює код, який поступає на входи в сигнал лише на одному з його виходів.

Теорема 1.5.6. Для реалізації дешифратора, що має n входів та 2n виходів необхідно використати 2n - 1 КЕ. Кількість КЕ в схемі лінійно залежить від кількості виходів дешифратора.

Означення 1.5.4. Шифратором або кодером називається пристрій, який перетворює одиничний сигнал в n розрядний двійковий код.

Теорема 1.5.7. Схему шифратора на n входів можна побудувати на КЕ, причому кількість КЕ, використаних у схемі, не більша за n * log2n / 2. Час роботи шифратора дорівнює двом тактам.

Означення 1.5.5. Суматором будемо називати схему, яка складається з n входів та n+1 виходів, а функціонування якої відбувається наступним чином: якщо на і входів поступить сигнал 1 (немає значення на які конкретно), а на інших входах буде 0, тоді на і-ому виході повинен з'явитися сигнал 1, а на всіх інших виходах - 0. Зокрема, якщо на жодному із входів не буде сигналу 1, то суму будемо вважати рівною нулем і на нульовому виході повинен бути сигнал 1.

Теорема 1.5.8. Схему суматора з n входами та n виходами можна реалізувати на (n+1)*n/2 КЕ. Час роботи суматора дорівнює двом тактам.

Означення 1.5.6. Схемою логічного порогу будемо називати схему з n входами та одним виходом, яка приймає на входи сигнали 0 чи 1, а на виході видає сигнал 1 лише в тому випадку, коли кількість одиничних сигналів, що надійшла на входи, більша або дорівнює за деяке наперед задане натуральне число M Ј n. Число M називається пороговим числом.

Означення 1.5.7. Схемою мажоритарності будемо називати схему з n входами та одним виходом, яка приймає на входи сигнали 0 чи 1, а на виході видає сигнал 1 лише в тому випадку, коли кількість одиничних сигналів, що надійшла на входи, більша за кількість вхідних нульових сигналів.

Використовуючи схему суматора можна отримати схеми логічного порогу та мажоритарності.

Теорема 1.5.9. Схеми логічного порогу та мажоритарності вимірності n можуть бути реалізовані на КЕ. Час роботи таких схем дорівнює двом тактам.

Означення 1.5.8. Мультиплексором називається пристрій, який перетворює паралельні цифрові коди в послідовні.

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

Теорема 1.5.10. Схему мультиплексора з n входами можна реалізувати на n.log2n КЕ. Час роботи побудованої схеми дорівнює двом тактам. Безпеку роботи мультиплексора можна описати часовою формулою:

($! i: 1 Ј i Ј n Щ Out = i)

(в кожний момент часу вихід сполучено тільки з одним входом).

Означення 1.5.9. Лічильником називається схема, яка підраховує кількість імпульсів, поданих на вхід.

Теорема 1.5.11. Схему лічильника з n виходами можна побудувати на КЕ, причому кількість КЕ, задіяних у схемі, дорівнює 3.n.

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

Параграф 2.1. присвячено алгоритмові побудови схеми обчислення довільної арифметико-логічної функції на КЕ. Складність наведеної схеми за кількістю КЕ є експоненційною, час роботи схеми - 2 такти.

Теорема 2.1.1. Для довільної n-арної булевої функції існує схема на КЕ, яка обчислює значення цієї функції за 2 такти. Кількість КЕ, задіяних у схемі, не більша за n.2n.

Твердження 2.1.1. Якщо n-арна булева функція f приймає істинне значення на p двійкових наборах, то кількість КЕ, з яких складається схема що реалізує функцію f, дорівнює p.2p.

Твердження 2.1.2. Складність схеми на КЕ, яка реалізує булеву функцію f, експоненційно залежить від арності функції f.

В параграфі 2.2. дається алгоритм побудови схеми сумування двох багаторозрядних чисел з лінійною складністю за кількістю КЕ, використаних в ній.

Теорема 2.2.1. Два багаторозрядних числа можна просумувати за два такти.

Теорема 2.2.2. Існує схема додавання двох багаторозрядних чисел на КЕ, час роботи якої дорівнює двом тактам, а кількість КЕ, використаних у схемі, лінійно залежить від вимірності чисел. В параграфі 2.3. наведено два алгоритми побудови схеми множення двох багаторозрядних чисел. Складність схеми, побудованої за першим алгоритмом (теорема 2.3.1.), є експоненційною, час її обчислення дорівнює двом тактам. Складність другої схеми (теорема 2.3.2.) квадратично залежить від розрядності чисел, які перемножаються, але її час роботи лінійно залежить від розрядності чисел.

Теорема 2.3.1. Схему добутку двох багаторозрядних чисел можна реалізувати на КЕ, при чому кількість КЕ, використаних у схемі, експоненційно залежить від розрядності чисел що перемножаються, а час обчислення схеми дорівнює двом тактам.

Теорема 2.3.2. Схему добутку двох n - розрядних чисел можна реалізувати на КЕ, при чому кількість КЕ, використаних у схемі, дорівнює O(n2), а час обчислення схеми лінійно залежить від n.

В параграфі 2.4 дається алгоритм побудови схеми порівняння двох багаторозрядних чисел на КЕ.

Теорема 2.4.1. На КЕ можна побудувати схему порівняння двох багаторозрядних чисел з 2n входами та одним виходом. На входи будуть подані двійкові задання чисел що порівнюються, а на виході буде одиниця якщо A>B та 0 інакше. Кількість КЕ лінійно залежить від вимірності чисел, які порівнюються.

В третій главі розглядається застосування КЕ в мережах.

В параграфі 3.1. вводяться основні поняття багатостанових мереж.

Означення 3.1.1. Дводольним графом називається неорієнтований граф G(V1, V2, E), де V1 та V2 - множини вершин, V1 З V2 = Ж, а E - множина ребер. Для кожного ребра eОE, e = (v1,v2), має місце: v1ОV1 та v2ОV2 або v1ОV2 та v2ОV1,.

Означення 3.1.2. Тридольним графом називається граф G(V1, V2, V3, E1, E2), де Vi, i=1,3 - множини вершмн, а Ei, i=1,2 - множини ребер. Ребра з множини Ei сполучають вершини, які з находяться в множинах Vi та Vi+1. При цьому для будь-яких i, j , i № j, i, j О {1, 2, 3} має місце рівність Vi З Vj = Ж.

Означення 3.1.3. n-дольним графом називається граф G(V1, …, Vn, E1, .., En-1), де Vi З Vj = Ж, та для будь-якого eОEi, e = (x,y) або xОVi та yОVi+1, або xОVi+1 та yОVi.

Означення 3.1.4. Багатостановою мережею називається n - дольний граф G = (V, E), в якому V={Vin, Vout, Vpr}, де Vin - виділені n вхідних вершин, Vout - n вихідних вершин, Vpr - проміжні вершини, які являють собою перемикачі.

Означення 3.1.5. k - передачею для n - мережі будемо називати таке встановлення положень перемикачів, що існує зв'язок між k входами та k виходами (з'єднаний вхід та вихід будемо називати парою), при чому кожний вихід з'являється хоча б в одній парі.

Означення 3.1.6. Передача називається один до одного (або однозначною), якщо кожний вхід з`являється хоча б в одній парі.

Означення 3.1.7. Перестановкою для n - мережі будемо називати однозначну передачу.

Далі на основі КЕ подано реалізацію наступних багатостанових мереж: Гама мережі, Омега мережі, мережі Біні, Клос мережі та мережі метелика.

В параграфі 3.2. розглядаються методи передачі даних та досліджуються алгоритми маршрутизації на наведених в параграфі 3.1. топологіях багатостанових мереж.

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

Теорема 3.2.1. Довільну перестановку можна реалізувати на мережі Біні.

Параграф 3.2.2. присвячено можливості реалізації Гама мережі на КЕ. Алгоритми побудови схем перемикачів Гама мережі даються в доведенні теореми 3.2.2.1.. В теоремі 3.2.2.2 дається формула знаходження кількості всіх можливих шляхів від заданих входу до виходу, наводиться алгоритм їх знаходження.

Теорема 3.2.2.1. Перемикачі Гама мережі, а отже і вся Гама мережа, можуть бути реалізовані на КЕ.

Теорема 3.2.2.2. Всі можливі шляхи в Гамма розміру n мережі від входу X до виходу Y визначаються різницею S = (Y - X) mod 2n, при чому їх кількість Rn визначається формулою:

Rn =

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

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

Теорема 3.2.3.1. Передача даних із входу S до виходу D на омега мережі розміру n, побудованої на звичайних перемикачах, відбувається за log2n тактів.

Теорема 3.2.3.2. Передача даних із входу S до виходу D на Омега мережі розміру n, побудованої на КЕ, відбувається за 2 такти.

Означення 3.2.3.1. Два повідомлення називаються конфліктними, якщо вони мають спільне вікно Wi, тобто вони повинні пройти по одному каналу i-им та i+1 - им станами.

Означення 3.2.3.2. Множину повідомлень будемо називати неконфліктуючою, якщо жодні два повідомлення з цієї множини не конфліктують між собою.

Теорема 3.2.3.3. Множина з m повідомлень може бути розбита на неконфліктуючі множини, причому кількість останніх не менша ніж m / log2n, де n - розмір мережі (у випадку повної завантаженості мережі) та не більша ніж m (якщо кожне повідомлення конфліктує з кожним). Останній випадок можливий, наприклад, якщо треба передати m однакових повідомлень.

Теорема 3.2.3.4. Якщо на Омега мережі розміру n, побудованої на КЕ, можна передати m повідомлень за T тактів, то m / log2n Ј T Ј m.

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

В параграфі 3.3. досліджується побудова сортуючих мереж на КЕ.

Означення 3.3.1. Компаратором будемо називати схему порівняння двох чисел.

Твердження 3.3.1. n - розрядний компаратор можна реалізувати на КЕ, кількість яких лінійно залежить від n. Час роботи n - розрядного компаратора лінійно залежить від n.

Твердження 3.3.2. Схема злиття двох відсортованих послідовностей може бути побудована на КЕ.

Твердження 3.3.3. Сортуюча мережа Бетчера може бути побудована на КЕ.

В додатку 1 наводиться програма моделювання комутаційної мережі.

В додатку 2 наводиться програма моделювання передачі даних на Омега та Гама мережах.



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

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

Побудовано функціональні схеми цифрових пристроїв.

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

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

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



Основний зміст дисертації опубліковано в наступних працях

1. Глибовець М.М., Медведєв М.Г. Опис складних систем інформації за допомогою часових логік // Вісник Київського університету, Серія фіз.-мат. наук, Випуск №2, Київ, 1996 р., стор. 106-114.

2. Глибовець М.М., Медведєв М.Г. Використання апарату часових логік для дослідження основних властивостей програм // Вісник Київського університету, Серія фіз.-мат. наук, Випуск №1, Київ, 1996 р., стор. 187-191.

3. Медведєв М.Г. Взаємне виключення // Вісник Київського університету, Серія фіз.-мат. наук, Випуск №2, Київ, 1998 р., стор.214-221.



анотації

комутаційний елемент логічний цифровий

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

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин та систем. -- Київський університет імені Тараса Шевченка, Київ, 1999.

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

Ключові слова: комутаційний елемент, арифметичні та логічні схеми, багатостанові мережі, сортуючі мережі.

Медведев М.Г. Исследование и разработка вычислительных схем, базирующихся на коммутационных элементах. -- Рукопись.

Диссертация на приобретение научной степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. -- Киевский университет имени Тараса Шевченка, Киев, 1999.

Диссертация ориентирована на исследование и разработку вычислительных схем, базированных на коммутационных элементах (КЭ) и их применение при разработке функциональных моделей аппаратных схем. В диссертации вводится понятие коммутационного элемента, исследуются его функциональные свойства, доказываются преимущества использования КЭ вместо логических элементов при разработке цифровых схем. Предложен алгоритм построения вычислительной схемы на КЭ, которая реализует произвольную арифметическую или логическую функцию. Исследуется работа схем многоразрядного сложения, умножения и сравнения на КЭ. Приводится использование КЭ при построении сетей со многими состояниями и решении задач маршрутизации.

Диссертация состоит из 7 разделов: вступления, трех глав (параграфов), заключения, списка литературы и дополнения.

Во вступлении рассматривается современное состояние развития научных достижений в области разработки схем цифровых устройств, архитектур ЭВМ и топологий сетей, алгоритмов маршрутизации, верификации.

В параграфе 1.1 вводится понятие коммутационного элемента (далее - КЭ) на функциональном уровне, рассматривается его структура, правила коммутации и передачи сигналов. Даются основные определения и вводятся основные понятия. Построены булевы формулы, описывающие работу КЭ и приведены их таблицы истинности.

Параграф 1.2 исследует функциональные возможности КЭ. Строятся все возможные унарные и бинарные булевы функции, которые могут быть реализованы на одном КЭ.

В параграфе 1.3. вводится понятие коммутационной сети. Рассматриваются возможности соединения разных КЭ для образования сложных схем. При помощи математической логики исследуется работа коммутационных сетей.

В параграфе 1.4. представлены схемы основных цифровых устройств на КЭ с доказательством корректности их работы.

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

В параграфе 2.1. дается алгоритм построения схемы для произвольной булевой функции. Несмотря на то, что скорость ее работы составляет всего два такта, количество задействованных в схеме КЭ экспоненциально зависит от количества аргументов.

Основным результатом параграфа 2.2. является построение схемы суммирования двух многоразрядных чисел, складывающая числа за два такта.

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

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

В третьей главе рассматривается употребление КЭ в сетях. Часто один процессор соединяется с несколькими другими, а при передаче информации необходимо выбрать тот путь, который ведет к решению задачи. Как правило, передаваемые данные содержатся в некотором регистре (или множестве регистров - памяти). При помощи коммутационных механизмов маршрутизатора происходит соединение выходов регистра одного процессорного элемента (ПЭ) со входами регистра другого ПЭ шиной. Мы покажем, что коммутационные механизмы соединения одного ПЭ с другим можно реализовать на КЭ для произвольной топологии. С ростом степени топологии сети возрастает и сложность коммутационных схем.

В параграфе 3.1 рассматриваются сетей со многими состояниями и их основные коммутационные механизмы с реализацией последних на КЭ.

В параграфе 3.2 исследуются проблемы маршрутизации в сетях. Рассматривается основная задача маршрутизации - передача пакета данных от одного к другому ПЭ, описаны алгоритмы передачи информации на разных топологиях и указаны правила коммутации.

В параграфе 3.3. описывается общий подход к построению схем сортирующих сетей, основой которых является КЭ.

Основными результатами диссертационной работы является создание математической модели КЭ, исследование работы коммутационных сетей и представление алгоритмов реализации основных вычислительных схем цифровой техники на КЭ. На основе КЭ:

Построено функциональные схемы цифровых устройств.

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

Построены коммутационные схемы сложения, умножения и сравнения двух многоразрядных чисел с разными количественными и временными характеристиками.

Предложено использование и реализацию переключателей сетей со многими состояниями.

Ключевые слова: коммутационный элемент, арифметические и логические схемы, сети со многими состояниями, сортирующие сети.

Medvedev M.G. Investigation and development of calculation circuits using commutation elements. -- Manuscript.

Thesis for the Degree of Candidate of Physics-Mathematical Science in Speciality 01.05.03 - Computer Software. -- Taras Shevchenko Kyiv University, Kyiv, 1999.

The thesis is devoted to investigation and design of computing schemes, based on commutation element (CE), its usage in functional models development for hardware. The idea of CE, its functional properties, the advantages of using CE instead of logic elements in hardware circuits design are dealt within the thesis. The algorithm for arithmetic or logic function realization is proposed, based on CE. Polydigital addition, multiplication and comparation schemes are considered. A great attention is paid to the CE usage in multistage interconnection networks construction and routing tasks solution.

Keywords: commutation element, arithmetic and logic schemes, multistage interconnection networks, sorting networks.

Размещено на Allbest.ru

...