Пристрій для моделювання графів

Пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить два регістри зсуву, комутатор, два тригери, першу групу з m тригерів, де m - кількість гілок вузла графа, чотири групи з m елементів І, чотири елементи І, групу з m елементів АБО, чотири елементи АБО, два елементи індикації і два ключі, причому перша група виходів блока керування з'єднана з першими входами першої, другої і четвертої груп елементів І, інформаційні входи з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І, виходи яких з'єднані з входами першого елемента АБО, перший і другий інформаційні входи комутатора з'єднані з виходами першого і другого регістрів зсуву, другий вихід блока керування з'єднаний з першим входом другого елемента АБО, третій вихід блока керування з'єднаний з першим входом першого елемента І, другий вхід якого з'єднаний з виходом першого елемента АБО, четвертий вихід блока керування з'єднаний з першим входом другого елемента І, п'ятий вихід блока керування з'єднаний з керуючими входами першого і другого регістрів зсуву, вихід першого регістра зсуву з'єднаний зі своїм інформаційним входом, шостий вихід блока керування з'єднаний з першим входом першого ключа, перший вихід якого з'єднаний з першим входом третього елемента АБО, сьомий вихід блока керування з'єднаний з встановлювальними входами першого і другого регістрів зсуву, входи синхронізації першого і другого регістрів зсуву з'єднані з восьмим виходом блока керування, виходи з першого по m-й другої групи елементів І з'єднані відповідно з встановлювальними входами першої групи тригерів, прямі виходи яких з'єднані відпові 2 (19) 1 3 75209 4 першого елемента І, другий вихід першого ключа індикації і з другими входами третьої групи елемез'єднаний з другим входом другого елемента АБО, нтів І, другий вхід третього елемента І з'єднаний з вихід якого з'єднаний з входом скидання третього третім виходом першого ключа, третій вхід якого тригера, вихід третього елемента АБО з'єднаний з з'єднаний з виходом шостого елемента І, перший встановлювальним входом третього тригера, прявихід розподільника імпульсів з'єднаний з другими мий вихід якого з'єднаний з першими входами шовходами другої групи елементів І і з другим входом стого елемента І і сьомого елемента АБО, прямий третього елемента АБО, другий вихід розподільвихід другого тригера з'єднаний з другим входом ника імпульсів з'єднаний з другими входами четсьомого елемента АБО, вихід якого з'єднаний з вертої групи елементів І і з другим входом шостого входом другого ключа і з інформаційним виходом елемента АБО, інверсні виходи першої групи тримоделі вузла, вихід четвертого елемента АБО герів з’єднані відповідно з третіми входами першої з'єднаний з другими входами четвертого і шостого групи елементів І, встановлювальна шина моделі елементів І, вихід четвертого елемента І з'єднаний вузла з'єднана з керуючим входом комутатора, з входом першого елемента індикації і з другими встановлювальним входом розподільника імпульвходами п'ятої групи елементів І, вихід шостого сів і з другим виходом першого ключа. елемента І з'єднаний з входом другого елемента Винахід відноситься до обчислювальної техніки і може бути використаний для моделювання обчислювальних мереж з метою рішення задач маршрутизації при передачі даних між ЕОМ. Відомий пристрій для моделювання графів, який містить блок завдання списків вхідних дуг, блок перевірки параметрів списку, блок пам'яті міток звершення вершин, блок завдання списків вихідних дуг, багатоканальний таймер, блок синхронізації та блок пам'яті логічної функції вершин [1]. Основний недолік відомого пристрою полягає в складності його реалізації. Відомий пристрій для моделювання графів, який містить блок синхронізації, блок перерахування маршрутів, блок перевірки виконання умови вибору маршруту і блок реєстрації [2]. Основний недолік цього відомого пристрою полягає в виборі на графі маршрутів із заданими параметрами, які в задачі маршрутизації невідомі. Найбільш близьким до винаходу є пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить чотири регістри зсуву, два суматора, віднімач, комутатор, два тригери, групу з m тригерів, де m - кількість гілок вузла графа, чотири групи з m елементів І, чотири елемента І, групу з m елементів АБО, чотири елемента АБО, групу елементів індикації і два ключі [3]. Основний недолік прототипу викликаний вузькими функціональними можливостями, які дозволяють знайти лише один найкоротший шлях в мережі, яка моделюється. В задачі двохшляхової маршрутизації необхідно знайти між початковим і кінцевим вузлами мережі два найбільш коротші шляхи, які не мають загальних гілок графа. В основу винаходу поставлена задача вдосконалення пристрою для моделювання мережі у вигляді графів за допомогою двохшляхової маршрутизації, яка дозволяє знайти між початковим і ' кінцевим вузлами мережі два найбільш коротші шляхи, які не мають загальних гілок графа. Поставлена задача вирішується тим, що в пристрій для моделювання графів, який містить блок керування і модель мережі, яка містить моделі вузлів, що з'єднані відповідно з топологією графа, причому модель вузла містить два регістри зсуву, комутатор, два тригери, першу групу з m тригерів, де m - кількість гілок вузла графа, чотири групи з m елементів І, чотири елементи І, групу з m елементів АБО, чотири елементи АБО, два елемента індикації і два ключі, причому перша група виходів блоку керування з'єднана з першими входами першої, другої і четвертої груп елементів І, інформаційні входи з першого по m-й моделі вузла з'єднані відповідно з другими входами першої групи елементів І, виходи - яких з'єднані з входами першого елемента АБО, перший і другий інформаційні входи комутатора з'єднані з виходами першого і другого регістрів зсуву, другий вихід блоку керування з'єднаний з першим входом другого елемента АБО, третій вихід блоку керування з'єднаний з першим входом першого елемента І, другий вхід якого з'єднаний з виходом першого елемента АБО, четвертий вихід блоку керування з'єднаний з першим входом другого елемента І, п'ятий вихід блоку керування з'єднаний з керуючими входами першого і другого регістрів зсуву, вихід першого регістра зсуву з'єднаний зі своїм інформаційним входом, шостий вихід блоку керування з'єднаний з першим входом першого ключа, перший вихід якого з'єднаний з першим входом третього елемента АБО, сьомий вихід блоку керування з'єднаний з встановлювальними входами першого і другого регістрів зсуву, входи синхронізації першого і другого регістрів зсуву з'єднані з восьмим виходом блоку керування, виходи з першого по m-й другої групи елементів І з'єднані відповідно з встановлювальними входами першої групи тригерів, прямі виходи яких з'єднані відповідно з першими входами третьої групи елементів І, встановлювальний вхід першого тригера з'єднаний з виходом третього елемента І, прямий вихід другого тригера з'єднаний з першим входом четвертого елемента І, входи з першого по m-й четвертого елемента АБО з'єднані відповідно з індикаційними входами моделі вузла, вихід другого ключа з'єднаний з m+1-м входом четвертого елемента АБО, у відповідності з винаходом додатково введені роз 5 75209 6 подільник імпульсів, півсуматор, друга група з m групи елементів І, встановлювальна шина моделі тригерів, де m - кількість гілок вузла графа, третій вузла з'єднана з керуючим входом комутатора, тригер, п'ята група з m елементів І, п'ятий і шостий встановлювальним входом розподільника імпульелементи І, п'ятий, шостий і сьомий елементи сів і з другим виходом першого ключа. АБО, елемент НЕ і елемент затримки, причому На Фіг.1 представлена структурна схема приперший і другий входи півсуматора з'єднані відпострою для моделювання графів і функціональна відно з виходом комутатора і з виходом п'ятого схема моделі вузла. На Фіг.2 представлена функелемента АБО, інформаційний вхід другого регістціональна схема блоку керування. На Фіг.3 навера зсуву з'єднаний з виходом суми півсуматора, дено приклад моделювання графа на моделях вихід переносу якого з'єднаний з другим входом чотирьох вузлів. другого елемента I і з входом елемента затримки, Цифрами в скобках, які слідують за номером перший і другий входи п'ятого елемента АБО з'єдпозиції без скобки, позначені порядкові номера нані відповідно з виходом першого елемента I і з однакових по технічному виконанню і призначенню виходом п'ятого елемента І, другий вихід блоку блоків, вузлів і елементів. Цифрами в скобках, які керування з'єднаний з входами скидання першої, розташовані у контурі відповідного блока вузла другої груп тригерів і з входом скидання розподіабо елемента, зображені порядкові номери входів льника імпульсів, інформаційний вхід якого з'єднаі виходів цього блока, вузла або елемента. ний з виходом другого елемента І, виходи четверПристрій (Фіг.1) моделює m гілок графа, які затої групи елементів І з'єднані відповідно з ходять у-вершину графа, в моделі 1(i) вузла, де встановлювальними входами четвертої групи триi=7,2,3,...,N. Модель мережі, яка містить N вершин, герів, прямі виходи яких з'єднані відповідно з перформується з'єднанням N моделей вузлів відповішими входами п'ятої групи елементів І, перший і дно до топології графа, який моделюється. Прикдругий входи групи елементів АБО з'єднані відполад моделювання графа на моделях чотирьох відно з виходами третьої і п'ятої груп елементів І, вузлів зображений на Фіг.3. З'єднання моделей виходи групи елементів АБО з'єднані відповідно з вузлів відповідно до топології графа виконується індикаційними виходами моделі вузла, дев'ятий таким чином, що інформаційні входи 38(I) - 38(m) вихід блоку керування з'єднаний з першим входом моделей одних вузлів з'єднуються з інформаційтретього елемента І і з входом скидання першого ними виходами 39 моделей попередніх вузлів, тригера, прямий вихід якого з'єднаний з першим індикаційні входи 40(I) - 40(m) яких з'єднуються ч входом шостого елемента АБО і з другим входом індикаційними виходами 41(I) - 41(m) наступних першого ключа, третій вихід блоку керування з'єдмоделей вузлів. Невикористанні індикаційні входи наний з входом елемента НЕ, вихід якого з'єдна40(I) - 40(m) з'єднуються з шиною 59 логічного нуний з першим - входом п'ятого елемента І, другий ля пристрою. Встановлювальна шина 42 усіх мовхід якого з'єднаний з виходом елемента затримделей вузлів з'єднуються між собою. Блок 2 керуки, другий вихід блоку керування з'єднаний з вховання є загальним для всіх моделей вузлів. дом скидання другого тригера, встановлювальний Пристрій для моделювання графів Фіг.1 місвхід якого з'єднаний з виходом шостого елемента тить моделі 1(i) вузлів, де i=1,2,3,...,N, N - кількість АБО, інверсні виходи другого і третього тригерів вершин графа та блок 2 керування. Модель і(I) з'єднані відповідно з третім і четвертим входами вузла (Фіг.1) містить регістри 3 і 4 зсуву, півсумапершого елемента ї, другий вихід першого ключа тор 5, комутатор 6, тригери 7-9, першу групу триз'єднаний з другим входом другого елемента АБО, герів 10(I) -10(m), другу групу тригерів 11(I) - 11(m), вихід якого з'єднаний з входом скидання третього розподільник 12 імпульсів, п'ять груп елементів І тригера, вихід третього елемента АБО з'єднаний з 13(I) - 13(m), 14(I) - 14(m), 15(I) -15(m), 16(I) - 16(m), встановлювальним входом третього тригера, пря17(I) - 17(m), шість елементів І 18 - 23, групу елемий вихід якого з'єднаний з першими входами шоментів АБО 24(I) - 24(m), сім елементів АБО 25 стого елемента І і сьомого елемента АБО, прямий 31, елемент НЕ 32, елемент 33 затримки, два вихід другого тригера з'єднаний з другим входом елементи 34 і 35 індикації, два ключі 36 і 37, інфосьомого елемента АБО, вихід якого з'єднаний з рмаційні входи 38(I) - 38(m) моделі 1 вузла, інфорвходом другого ключа і з інформаційним виходом маційний вихід 39 моделі 1 вузла, індикаційні вхомоделі вузла, вихід четвертого елемента АБО ди 40(I) -40(m) моделі 1 вузла, індикаційні виходи з'єднаний з другими входами четвертого і шостого 41(I) - 41 (m) моделі 1 вузла і встановлювальну елементів І, вихід четвертого елемента І з'єднаний шину 42 моделі 1 вузла. з входом першого елемента індикації і з другими Перша група виходів (I.I)-(I.m) блоку 2 керувходами п'ятої групи елементів ί, вихід шостого вання з'єднана з першими входами першої, другої елемента І з'єднаний з входом другого елемента і четвертої груп елементів І 13(I) -13(m), 14(I) індикації і з другими входами третьої" групи еле14(m), 16(I) - 16(m), інформаційні входи 38(I) ментів !, другий вхід третього елемента І з'єднаний 38(m) з першого по m-й моделі 1 вузла з'єднані з третім виходом першого ключа, третій вхід якого відповідно з другими входами першої групи елез'єднаний з виходом шостого елемента І, перший ментів 1 13(I) - 13(m), виходи яких з'єднані з вховихід розподільника імпульсів з'єднаний з другими дами першого елемента АБО 25, перший і другий входами другої групи елементів І і з другим входом інформаційні входи комутатора 6 з'єднані з вихотретього елемента АБО, другий вихід розподільдами першого і другого регістрів 3,4 зсуву, другий ника імпульсів з'єднаний з другими входами четвихід блоку 2 керування з'єднаний з першим вховертої групи елементів І і з другим входом шостого дом другого елемента АБО 26, третій вихід блоку елемента АБО, інверсні виходи першої групи три2 керування з'єднаний з першим входом першого герів з'єднані відповідно з третіми входами першої елемента І 18, другий вхід якого з'єднаний з вихо 7 75209 8 дом першого елемента АБО 25, четвертий вихід другого елемента АБО 26, вихід якого з'єднаний з блоку 2 керування з'єднаний з першим входом входом скидання третього тригера 9, вихід - тредругого елемента 1 19, п'ятий вихід блоку 2 керутього елемента АБО 27 з'єднаний з встановлювавання з'єднаний з керуючими входами першого і льним входом третього тригера 9, прямий вихід другого регістрів 3, 4 зсуву, вихід першого регістра якого з'єднаний з першими входами шостого еле3 зсуву з'єднаний зі своїм інформаційним входом, мента І 23 і сьомого елемента АБО 31, прямий шостий вихід блоку 2 керування з'єднаний з первихід другого тригера 8 з'єднаний з другим входом шим входом першого ключа 36, перший вихід якосьомого елемента АБО 3 і, вихід якого з'єднаний з го з'єднаний з пґершим входом третього елемента входом другого ключа 37і з інформаційним вихоАБО 27, сьомий вихід блоку 2 керування з'єднаний дом 39 моделі 1 вузла, вихід четвертого елемента з встановлювальними входами першого і другого АБО 28 з'єднаний з другими входами четвертого і регістрів 3, 4 зсуву, входи синхронізації першого і шостого елементів і 21, 23, вихід четвертого еледругого регістрів 3, 4 зсуву з'єднані з восьмим вимента 121 з'єднаний з входом першого елемента ходом блоку 2 керування, виходи з першого по m-й 34 індикації і з другими входами п'ятої групи " еледругої групи елементів І 14(I) — 14(m) з'єднані відментів І і 7(I) i7(m), вихід шостого елемента І 23 повідно з встановлювальними входами першої з'єднаний з входом другого елемента 35 індикації і групи тригерів 10(I) - 10(m), прямі виходи яких з другими входами третьої групи елементів 1 15(I) з'єднані відповідно з першими входами третьої - 15(m), другий вхід третього елемента І 20 з'єднагрупи елементів 1 15(I) — 15(m), встановлювальний з третім виходом першого ключа 36, третій ний вхід першого тригера 7 з'єднаний з виходом вхід якого з'єднаний з виходом шостого елемента І третього елемента І 20, прямий вихід другого три! 23, перший вихід розподільника 12 імпульсів з'єдера 8 з'єднаний з першим входом четвертого еленаний з другими входами другої групи елементів I мента І 21, входи з першого по m-й четвертого 14(I) - 14(m) і з другим входом третього елемента елемента АБО 28 з'єднані відповідно з індикаційАБО 27, другий вихід розподільника 12 імпульсів ними входами 40(I) - 40(m) моделі 1 вузла, вихід з'єднаний з другими входами четвертої групи еледругого ключа 37 з'єднаний з m+1-м входом четментів І 16(I) - 16(m) і з другим входом шостого вертого елемента АБО 28, перший і другий входи елемента АБО 30, інверсні виходи першої групи півсуматора 5 з'єднані відповідно з виходом комутригерів 10(I) - 10(m) з'єднані відповідно з третіми татора 6 і з виходом п'ятого елемента АБО 29, входами першої групи елементів І 13(I) - 13(m), інформаційний вхід другого регістру 4 зсуву з'єдвстановлювальна шина 42 моделі 1 вузла з'єднана наний з виходом суми півсуматора 5, вихід перез керуючим входом комутатора 6, встановлювальносу якого з'єднаний з другим входом другого ним входом розподільника 12 імпульсів і з другим елемента І 19 і з входом елемента 33 затримки, виходом першого ключа 36. перший і другий входи п'ятого елемента АБО 29 Блок 2 керування (Фіг.2) містить генератор 43 з'єднані відповідно з виходом першого елемента І імпульсів, розподільники 44 і 45 імпульсів, генера18 і з виходом п'ятого елемента 1 22, другий вихід тор 46 одиночного імпульсу, комутатори 47 - 51, блоку 2 керування з'єднаний з входами скидання тригер 52, елементи І 53 і 54, елементи АБО 55 і першої, другої груп тригерів 10(I) - 10(m), 11(I) 56, елемент НЕ 57, елемент 58 затримки, шина 59 11(m) і з входом скидання розподільника 12 імпулогічного нуля, групу перших виходів 60(I) - 60(m), льсів, інформаційний вхід якого з'єднаний з вихогрупу п'ятих виходів 64(I) - -64(m), другий, третій, дом другого елемента І 19, виходи четвертої групи четвертий, шостий, сьомий, восьмий, дев'ятий елементів 1 16(I) - 16(m) з'єднані відповідно з виходи 61, 62, 63, 65, 66, 67, 68 відповідно. встановлювальними входами другої групи тригерів Вихід генератора 43 імпульсів з'єднаний з вхо11(I) - 11(m), прямі виходи яких з'єднані відповідно дом розподільника 44 імпульсів, виходи якого з з першими входами п'ятої „ групи елементів I 17(I) першого по n-й, де n-кількість розрядів представ- 17(m), перший і другий входи групи елементів лення ваги гілок, з'єднані через комутатор 47 з АБО 24(I) - 24(m) з'єднані відповідно з виходами входами елемента АБО 55. Вихід n-го розряду третьої і п'ятої груп елементів 1 15(I) - 15(m), 17(I) розподільника 44 імпульсів з'єднаний з входом 17(m), виходи групи елементів АБО 24(I) - 24(m) розподільника 45 імпульсів, виходи якого з першоз'єднані відповідно з індикаційними виходами 41(I) го по m - й, де m - кількість гілок, які моделюються, - 41(m) моделі 1 вузла, дев'ятий вихід блоку 2 кез'єднані через комутатор 48 з входами елемента рування з'єднаний з першим входом третього АБО 56. Тактовий вхід генератора 46 одиночних елемента І 20 і з входом скидання першого тригеімпульсів з'єднаний з виходом елемента І 53, перра 7, прямий вихід якого з'єднаний з першим вхоший і другий входи якого з'єднані відповідно через дом шостого елемента АБО 30 і з другим входом елемент 58 затримки з виходом m -го розряду ропершого ключа 36, третій вихід блоку 2 керування зподільника 44 імпульсів і - з виходом m-го розряз'єднаний з - входом елемента НЕ 32, вихід якого ду розподільника 45 імпульсів. Вихід генератора з'єднаний з першим входом п'ятого елемента І 22, 46 одиночних імпульсів з'єднаний з входом комудругий вхід якого з'єднаний з виходом елемента 33 татора 49, перший вихід якого з'єднаний і входом затримки, другий вихід блоку 2 керування з'єднавстановлювання в одиничний стан тригера 52, вхід ний з входом скидання другого тригера 8, встановстановлювання в нульовий стан якого, з'єднаний влювальний вхід якого з'єднаний з виходом шостоз виходом елемента 1 53. Прямий вихід тригера 52 го елемента АБО 30, інверсні виходи другого і з'єднаний з першим входом елемента I 54, другий третього тригерів 8, 9 з'єднані відповідно з третім і вхід якого з'єднаний з виходом елемента АБО 56. четвертим входами першого елемента І 18, другий Керуючий вхід генератора 46 одиночних імпульсів вихід першого ключа 36 з'єднаний з другим входом з'єднаний через комутатор 51 з виходом елемента 9 75209 10 НЕ 57, вхід якого з'єднаний з шиною 59 логічного могою комутатора 51, виконаного, наприклад, у нуля пристрою. Другий вихід комутатора 49 з'єдвигляді кнопкового перемикача. Комутатор 51 наний з шостим виходом 65 блоку 2 керування. з'єднує вихід елемента НЕ 57 з керуючим входом Інформаційний вхід комутатора 50 з'єднаний з генератора 46 одиночного імпульсу. Сигнал логічвиходом елемента І 54. Виходи комутатора 50 ної одиниці з виходу елемента НЕ 57, вхід якого являються п'ятими виходами 64(I) - 64(N) блоку 2 з'єднай з шиною 59 логічного нуля, запускає генекерування. Перший вихід комутатора 49 з'єднаний ратор 46 одиночного імпульсу, який формує на з другим виходом 6! блоку 2 керування, третій висвоєму виході одиночний імпульс з послідовності хід 62 блоку 2 керування з'єднаний з виходом імпульсів, яка діє на виході елемента І 53 блоку 2 першого розряду розподільника 44 імпульсів. Викерування. Елемент I 53 формує послідовність хід n-го розряду розподільника 44 імпульсів з'єдімпульсів з послідовності імпульсів n-го розряду наний з четвертим виходом 63 блоку 2 керування. розподільника 44 імпульсів, яка затримується Виходи з першого по m-й розподільника 45 імпуелементом 58 затримки на час рівний половині льсів з'єднані з групою перших виходів ' 60(I) періоду тактової частоти f, і з послідовності імпу60(т?2) блоку 2 керування. Вихід елемента АБО 55 льсів m-го розряду розподільника 45 імпульсів. з'єднаний з сьомим виходом 66 блоку 2 керування. Імпульси з виходу елемента І 53 через дев'ятий Восьмий вихід 67 блоку 2 керування з'єднаний з вихід 68 блоку 2 керування встановлюють тригер 7 виходом генератора 43 тактових імпульсів. Дев'яу нульовий стан. Одиночний імпульс з виходу гетий вихід 68 блоку 2 керування з'єднаний з вихонератора 46 одиночного імпульсу через комутатор дом елемента І 53. 49 встановлює S - тригер 52 у одиничний стан на Пристрій для моделювання графів працює тачас рівний m*n/f тому, що наступний імпульс поским чином. Спочатку відмічається початкова верлідовності імпульсів з виходу елемента І 53, який шина графа. Для цього замикають ключ 36 в монадходить на вхід скидання S - тригера 52, поверделі 1 вузла, яка моделює початкову вершину не його у нульовий стан. Одиночний імпульс з виграфа. Початковий стан пристрою задається за ходу генератора 46 одиночних імпульсів проходопомогою " комутатора 49 блоку 2 керування. В дить через комутатор 49 на другий вихід 61 блоку початковому стані комутатор 49, виконаний у ви2 керування, з якого він надходить на всі моделі гляді перемикача, з'єднує вихід генератора 46 1(I) вузла, i=1,2,3,...,N, де встановлює у нульовий одиночного імпульсу з встановлювальним входом стан тригери 8, 9, 10(I) - 10(m), 11(I) - 11(m) та розтригера 52 і з другим виходом 61 блоку 2 керуванподільник 12 імпульсів. Тригер 52 в одиничному ня. Генератор 43 імпульсів блоку 2 керування вистані відкриває одиничним сигналом прямого виробляє послідовність тактових імпульсів частоти f ходу елемент І 54, через який на керуючі входи яка поступає на вхід розподільника 44 імпульсів. З регістрів 3 і 4 зсуву моделі I(i) вузла поступає одипослідовності тактових імпульсів розподільник 44 ночний імпульсний сигнал з виходу елемента АБО імпульсів формує по я паралельним каналам м 56, який задає помер моделі гілки графа. Комутапослідовностей імпульсів частотнім, де n-кількість тор 50 з'єднує вихід елемента I 54 з одним із виходвійкових розрядів зображення ваги моделей гілок дів 64(I) - 64(N), блоку 2 керування, що - забезпеграфа. Послідовність імпульсів з n-го розряду розчує вибір потрібної моделі I(i) вузла, i=1,2,3,...,N. подільника 44 імпульсів поступає на вхід розподіПід дією тактових імпульсів генератора 43 імпульльника 45 імпульсів, який формує по m паралельсів блоку 2 керування, які діють на восьмому вихоним каналам m послідовностей імпульсів ді 67 блоку 2 керування, послідовний додатковий тривалістю n/f які діють з частотою f/m*n і зсунуті двійковий код ваги моделі гілки поступає з виходу друг відносно друга на час n/f. За допомогою комуелемента АБО 55 на сьомий вихід 66 блоку 2 кетаторів 47 і 48 блоку 2 керування задають відповірування і записується послідовно у часі, починаюдно додатковий двійковий код ваги моделі гілки і чи з молодшого розряду, в регістри 3 і 4 зсуву у номер цієї гілки. Комутатори 47 i 48 виконуються, час дії на виході елемента АБО 56 імпульсу номенаприклад, як клавішні перемикачі. Регістри 3 і 4 ра моделі гілки графа. Аналогічним чином в регісзсуву мають m*n двійкових розрядів і можуть затри 3 і 4 зсуву усіх моделей I(i) вузлів, i=1,2,3,...,N, пам'ятовувати динамічним способом m двійкових записуються додаткові двійкові коди ваги усіх мокодів по n розрядів в кожнім. В початковому стані в делей гілок графа з першої по m-ту в усіх моделях регістри 3 і 4 зсуву кожної моделі I вузла треба I(i) вузлів, i=1,2,3,...,N. У початковому стані сигнал записати вагу m гілок графа, які моделюються, у логічного нуля з прямого виходу тригера 7 моделі вигляді додаткового двійкового коду їх ваги. Вибір I(i) вузла, в якій замкнено ключ 36, що відмічає моделі I(i) вузла, де i=1,2,3,...,N, здійснюється за початкову вершину графа, надходить по встановдопомогою комутатора 50 блоку 2 керування, який лювальній шині 42 пристрою у всі моделі I(i) вузможе бути виконаний, наприклад, у вигляді клавілів, f=1,2,3,...,N. Цей сигнал логічного нуля, який шного перемикача на N напрямків, де N-кількість діє на встановлювальній шині 42 усіх моделей 1(I) моделей l(i) вузлів. Комутатор 50 блоку 2 керуванвузлів, i=1,2.3,...,N, перемикає комутатор 6 у стан, ня з'єднує керуючий вхід регістрів 3 і 4 зсуву модев якому вихід регістра 4 зсуву з'єднується через лі I(i) вузла з виходом елемента I 54 блоку 2 керукомутатор 6 з першим входом півсуматора 5. Це вання. Після вибору моделі I(I) -вузла за забезпечує циркуляцію під дією тактових імпульсів допомогою комутатора 50 блоку 2 керування на додаткових двійкових кодів, записаних в регістр 4 комутаторі 47 задають додатковий двійковий код зсуву, з його виходу через комутатор 6 і півсумаваги гілки графа, а комутатором 48 здійснюють тор 5 на інформаційний вхід регістра 4 зсуву. Тавибір номера гілки графа. Запис додаткового двійким чином, у початковому стані в регістрах 3 і 4 кового коду ваги гілки графа здійснюють за допозсуву під дією тактових імпульсів, які формуються 11 75209 12 генератором 43 імпульсів блоку 2 керування, цирде на вхід півсуматора для додавання в наступнокулює ш додаткових двійкових я розрядних кодів му розряді додаткового двійкового коду ваги моваги гілок графа. Слід зазначити, що запис інфорделі першої гілки. Через час, рівний Р1*m*n/f де Р/ мації ваги гілок графа може здійснюватися через - вага моделі першої гілки, на виході переносу півелектронні комутатори 47-51 блоку 2 керування під суматора 5 формується сигнал переносу і n-го дією сигналів керування з ЕОМ. Після запису інрозряду двійкового коду моделі першої гілки. Цей формації у регістри 3 і 4 зсуву в моделі I(i) вузла, сигнал переносу проходить через елемент І 19, яка моделює кінцеву вершину графа, замикають який синхронізується послідовністю імпульсів n-го ключ 37. розряду розподільника 44 імпульсів на четвертому У режимі моделювання комутатором 49 блоку виході 63 блоку 2 керування, імпульс переносу з 2 керування вихід генератора 46 одиночного імпувиходу елемента І 19 надходить на перший вихід льсу з'єднується з шостим виходом 65 блоку 2 розподільника 12 імпульсів і далі через елемент керування і через ключ 36 - з першим входом елеАБО -27 встановить RS- тригер 9 у одиничний стан мента АБО 27 в моделі I(i) вузла, яка моделює та через елемент І 14(I) встановить у одиничний початкову вершину графа. Пуск пристрою здійсстан RS- тригер 10(I), який запам'ятовує номер нюється комутатором 51 за допомогою якого, на першої гілки графа. Сигнал переносу з m-го розкеруючий вхід генератора 46 одиночного імпульсу ряду двійкового коду першої гілки з виходу переподається сигнал логічної одиниці з виходу еленосу півсуматора 5 затримується елементом 33 мента НЕ 57. Одиночний імпульс генератора 46 затримки на період I/f тактової частоти, але через одиночного імпульсу блоку 2 керування надходить елемент І 22 не пройде тому, що в цей час на вичерез комутатор 49, ключ 36 і елемент АБО 27 на ході елемента НЕ 32 діє нульовий сигнал, який встановлювальний вхід тригера 9 моделі I(i) вузла, формується з сигналу виходу першого розряду яка моделює початкову вершину графа. Сигнал розподільника 44 імпульсів блоку 2 керування. логічної одиниці з прямого виходу тригера 9 через Після встановлення тригера 9 в одиничний елемент АБО 31 надходить на інформаційний вистан на його прямому виході формується сигнал хід 39 моделі !(;*) вузла, яка моделює початкову логічної одиниці, який через елемент АБО 31 надвершину графа. Цей сигнал з виходу 39 моделі ходить на інформаційний вихід 39 моделі I(i) вузла початкового вузла надходить, згідно з топологією і далі, згідно з топологією графа, на інформаційні графа, на інформаційні входи 38(I) - 38(m) інших входи 38(I) - 38(m) інших моделей вузлів. Припусмоделей вузлів. Кожна модель 1(I) вузла реалізує тимо, що сигнал логічної одиниці і виходу 39 мов процесі моделювання часову аналогію, згідно з делі I(i) вузла надійшов на всі інформаційні входи якою, кожна модель гілки графа затримує сигнал 38(I) - 38(m) наступної моделі I(i+1) вузла. У цьому логічної одиниці, яка надходить на інформаційні випадку через всі елементи I 13(i) - 13(m) пройдуть входи 38(I) - 38(m), на час пропорційний ваги цієї послідовності імпульсів з виходів усіх розрядів гілки графа. Дійсно, припустимо, що на перший розподільника 45 імпульсів блоку 2 керування, а інформаційний вхід 38(I) першої моделі гілки грана виході елемента АБО 25 сформується сигнал фа прийшов сигнал логічної одиниці з виходу 39 логічної одиниці, який відкриває елемент І 18. Попопередньої моделі вузла, яка моделює початкову слідовність імпульсів першого розряду розподільвершину графа, В цьому випадку через елемент І ника 44 імпульсів з третього виходу 62 блоку 2 13(I) надходить послідовність імпульсів першого керування проходить через елементи І 18 та АБО розряду розподільника 45 імпульсів, яка діє на 29 на вхід півсуматора 5, додаючи одиницю молопершому виході першої групи виходів 60(I) блоку 2 дшого розряду додаткових кодів ваги усіх гілок керування. Ця послідовність імпульсів проходить моделі вузла, які поступають через комутатор 6 з через елемент АБО 25 на другий вхід елемента І виходу регістра 4 зсуву. Кожні m*n тактів додаткові 18, на першому вході якого діє послідовність імпукоди ваги яз моделей гілок послідовно у часі збільсів першого розряду розподільника 44 імпульсів льшуються на одиницю молодшого розряду і з через третій вихід 62 блоку 2 керування. Тому повиходу суми півсуматора 5 записуються в регістр 4 слідовність імпульсів першого розряду розподільзсуву під дією тактових імпульсів восьмого виходу ника 44 імпульсів з третього виходу 62 блоку 2 67 блоку 2 керування. Через час, рівний Р1*m*n/f, керування надходить через елементи [ J8 і АБО 29 де Р1-найменша вага з усіх ваг моделей гілок, на на вхід півсуматора 5. У цей час, під дією тактових виході суми півсуматора 5 сформується сигнал імпульсів, з виходу регістра 4 зсуву послідовно у переносу з n-го розряду двійкового коду моделі l-ої часі, починаючи з молодшого розряду, надходить гілки. Цей сигнал переносу з виходу елемента І 19 через комутатор 6 додатковий двійковий код ваги надходить через розподільник 12 імпульсів на його першої гілки графа. За час, рівний m*n/f, додаткоперший вихід. Імпульс з першого виходу розподівий двійковий код ваги моделі першої гілки збільльника 12 імпульсів через елемент АБО 27 всташується півсуматором 5 на одиницю молодшого новить тригер 9 в одиничний стан та через елерозряду і результат з виходу суми півсуматора 5 мент І 14(I) встановить в одиничний стан тригер записується під дією тактових імпульсів генерато10(I), який запам'ятовує l-й номер гілки найкоротра 43 імпульсів блоку 2 керування в регістр 4 зсушого шляху. Тригер 9 в одиничному стані блокує ву. Якщо в процесі додавання одиниці молодшого елемент 1 18 нульовим сигналом його інверсного розряду к додатковому двійковому коду ваги мовиходу. Це припиняє процес моделювання в розгделі першої гілки сформується сигнал переносу на лянутій моделі вузла. Сигнал логічної одиниці з виході переносу півсуматора 5, то цей сигнал чепрямого виходу тригера 9 надходить через елерез елемент 33 затримки на один період I/f тактомент АБО 31 на інформаційний вихід 39 розглянувої частоти f та через елементи І 22, АБО 29 пройтої моделі вузла і надходить, згідно з топологією 13 75209 14 графа, на інформаційні входи 38(I) - 38(m) інших встановлення пристрою у початковий стан. Це моделей вузлів. Таким чином, процес моделюванвиконується таким чином. Сигнал логічної одиниці ня поширюється на інші моделі I(i) вузлів, прямого виходу тригера 7 моделі початкового вузi=1,2,3,...,N. Через деякий час в моделі I(i) вузла, ла череї ключ 36 формує одиничний сигнал на яка моделює кінцеву вершину графа, встановитьвстановлювальній шині 42, яка зв'язана з усіма ся в одиничний стан тригер 9. Сигнал логічної моделями 1(I) вузлів, i=1,2,3,...,N. Цей сигнал логіодиниці з прямого виходу тригера 9 пройде через чної одиниці надходить на керуючий вхід комутаелемент АБО 31 і ключ 37 на вихід елемента АБО тора б усіх моделей вузлів пристрою. У цьому ста28. В цьому випадку на виході елемента АБО 28 ні комутатор 6 з'єднує вихід регістра 3 зсуву через моделі I(i) кінцевого вузла сформується одиничний півсуматор 5 з інформаційним входом регістра 4 сигнал індикації найкоротшого шляху. зсуву. Під дією тактових імпульсів восьмого виходу Процес індикації найкоротшого шляху поши67 блоку 2 керування додаткові двійкові коди ваги рюється на інші моделі I(i) вузлів, i=1,2,3,...,N, нагілок графа переписуються за час m-й тактів з виступним чином. Сигнал логічної одиниці виходу ходу регістра З зсуву в регістр 4 зсуву. Таким чиелемента АБО 28 проходить через елемент І 23 на ном, в регістрі 4 зсуву відновлюються додаткові елемент 35 індикації і далі через елемент І 15(l), двійкові коди ваги гілок графа. Крім цього, сигнал який відчинений одиничним сигналом прямого логічної одиниці з встановлювальної шини 42 надвиходу тригера 10(l), і елемент АБО 24(l) на індиходить на встановлювальний вхід розподільника каційний вихід 41(I) моделі 1(k) вузла, яка моде12 імпульсів усіх моделей вузлів пристрою і всталює кінцеву вершину графа. Далі сигнал логічної новлює перший розряд усіх розподільників 12 імодиниці з виходу 41 (l) моделі i(l) кінцевого вузла пульсів в одиничний стан. пройде в зворотному напрямку вздовж найкоротПроцес формування другого маршруту найкошого шляху до моделі 1(I) вузла, яка моделює поротшого шляху здійснюється пристроєм таким же чаткову вершину графа. Під час поширення сигначином, яким пристрій знайшов перший маршрут лу логічної одиниці вздовж найкоротшого шляху, найкоротшого шляху. Дійсно, сигнал логічної одивін надходить з індикаційного входу 40(l) через ниці з прямого виходу тригера 8 надходить через елементи АБО 28. I 23, І 15(I) і АБО 24(I) на індиелемент АБО 31 на інформаційний вихід 39 моделі каційний вихід 41 (l), де l - номер гілки графа I(i) початкового вузла. Далі він надходить на інфовздовж найкоротшого шляху. рмаційні входи 38(I) - 38(m) інших моделей вузлів, Процес індикації першого маршруту найкороякі з'єднані згідно з топологією графа з вершиною тшого шляху закінчується, коли сигнал логічної моделі початкового вузла. Але в моделях інших одиниці сформується на виході елемента АБО 28 вузлів один з тригерів 10(I) - 10(m) може знаходимоделі I(I) вузла, яка моделює початкову вершину тися в одиничному стані, якщо перший найкоротграфа. У цій моделі 1(I) вузла сигнал логічної одиший шлях проходив через модель гілки, номер ниці з виходу елемента АБО 28 через елемент І 23 якої запам'ятував цей тригер. В цьому випадку та ключ 36 відкриє елемент І 20. Через елемент І тригер 10 номера гілки першого маршруту найко20 пройде перший імпульс послідовності імпульсів ротшого шляху сигналом логічного нуля його інведіючої на дев'ятому виході 68 блоку 2 керування з рсного виходу блокує відповідний елемент І 13, що виходу елемента І 53. Перший імпульс цієї послівиключає цю модель гілки графа з процесу фордовності з виходу елемента І 20 встановить S мування другого маршруту найкоротшого шляху. тригер 7 в одиничний стан до приходу наступного Припустимо, що сигнал логічної одиниці з виходу імпульсу цієї послідовності, який поверне S - три39 моделі I(i) вузла надходить на всі інформаційні гер 7 у нульовий стан. Дійсно, після встановлення входи 38(I) - 38(w) наступної моделі 1(i+1) вузла. У тригера 7 в одиничний стан, сигнал логічної одицьому випадку через всі елементи I 13(i) - 13(m), ниці його прямого виходу через ключ 36 і елемент крім елемента І 13(/), який заблоковано інверсним АБО 26 встановить тригер 9 у нульовий стан. На виходом тригера 10(l), надходять послідовності прямому виході тригера 9 сформується сигнал імпульсів усіх розрядів, крім i-го розряду розподілогічного нуля, який закриє елемент І 23. Сигнал льника 45 імпульсів блоку 2 керування. Послідовлогічного нуля виходу елемента І 23 через ключ 36 ність імпульсів першого розряду розподільника 44 закриє елемент ( 20, що дозволяє другому імпульімпульсів, яка діє на третьому виході 62 блок 2 су послідовності імпульсів з дев'ятого виходу 68 керування, надходить через елементи I 18 та АБО блоку 2 керування встановити S - тригер 7 у ну29 на вхід півсуматора 5 додавая одиницю молольовий стан. Тому тригер 7 перебуває в одиничдшого розряду до додаткових кодів ваги усіх моному стані m*n-періодів тактової частоти f. За цей делей гілок, крім l-ої моделі гілки. Через час, рівчас сигнал логічної одиниці з прямого виходу триний Ps*m*n/f, де Рs — найменша вага з усіх ваг гера 7 через ключ 36 поступить на встановлювамоделей гілок за винятком l-ої моделі гілки, на льну шину 42 пристрою та через елемент АБО 26 виході суми півсуматора 3 сформується сигнал встановить у нульовий стан тригер 9. Крім того, переносу з n-го розряду двійкового коду моделі S-ї сигнал логічної одиниці прямого виходу тригера 7 гілки. Цей сигнал переносу з виходу елемента І 19 через елемент АБО 30 встановить в одиничний надходить через розподільник 12 імпульсів на його стан RS - тригер 8. Встановлення тригера 8 в одидругий вихід тому, що перший розряд усіх розподіничний стан в моделі 1(I) вузла, яка моделює польників 12 імпульсів знаходиться в одиничному чаткову вершину графа, свідчить про початок простані. Імпульс з другого виходу розподільника 12 цесу формування другого маршруту найкоротшого імпульсів через елемент АБО 30 встановлює тришляху, який не має загальних гілок з попереднім гер 8 в одиничний стан і через елемент І 16(s) найкоротшим шляхом. Цей процес починається з встановлює в одиничний стан тригер і 1(s), який 15 75209 16 запам'ятовує номер моделі гілки другого найкоропрямого виходу тригера 9 в усіх моделях вузла тшого маршруту. Тригер 8 в одиничному стані -. пристрою. блокує елемент І 18 нульовим сигналом його інвеТаким чином, пристрій дозволяє знайти два рсного виходу. Це припиняє процес побудови друнайкоротші маршрути між початковою і кінцевою гого найкоротшого маршруту в розглянутій моделі вершинами графа. Ці найкоротші маршрути не вузла. Сигнал логічної одиниці з прямого виходу мають загальних гілок графа і характеризуються тригера 8 надходить через елемент АБО 31 на найкоротшою довжиною в порівнянні з іншими інформаційний вихід 39 розглянутої моделі вузла і допустимими маршрутами на графі. Функціональні надходить згідно з топологією графа на інформаможливості прототипу [3] не дозволяють вирішити ційні входи 38(I) - 38(m) інших моделей вузлів. Тазадачу двохшляхової маршрутизації, яка має важким чином, процес формування другого маршруту ливе значення для передачі великих - об'ємів данайкоротшого шляху поширюється на інші моделі них у обчислювальних мережах. 1(j) вузлів, де j=1,2, ...,N. Через деякий час в модеНаведемо приклади реалізації основних блоків лі 1(k) вузла, яка моделює кінцеву вершину графа, пристрою. Регістри 3,4 зсуву є послідовними запа- встановиться в одиничний стан тригер 8. Сигнал м'ятовуючими пристроями [4]. Приклади реалізації логічної одиниці з прямого виходу тригера 8 пройпівсуматора 5 наведені в [5]. Приклади реалізації де через елемент АБО 31, ключ 37, елемент АБО генератора 43 імпульсів, генератора 46 одиночно28 на вихід елемента І 21. Це свідчить, що почався го імпульсу і розподільників 12, 44, 45 імпульсів процес індикації другого маршруту найкоротшого наведені в [6]. шляху. Сигнал логічної одиниці з виходу елемента Джерела інформації: І 21 надходить на вхід елемента 34 індикації дру1. Авторское свидетельство СССР №1837314, кл. гого маршруту та через елемент І 17(s), який відкG06F15/20, Бюл. №32, 1993. ритий одиничним сигналом прямого виходу триге2. Авторское свидетельство СССР №1832309, кл. ра 11(s), і елемент АБО 24(s) надходить на G06F15/419, Бюл.№29, 1993. індикаційний вихід 41 (s) моделі 1(k) вузла, яка 3. Авторское свидетельство СССР №1709346, кл. моделює кінцеву вершину графа. Далі сигнал логіG06F15/419, Бюл.№4, 1992. чної одиниці з виходу 41(s) моделі 1(k) кінцевого 4. Клингман Э. Проектирование микропроцессорвузла пройде в зворотному напрямку вздовж друных систем. - М.. Мир, 1980. - 575 с. (с.75, гого маршруту найкоротшого шляху до моделі 1(;') рис.3.21). вузла, яка моделює початкову вершину графа. Під 5. Справочник по цифровой вычислительной техчас поширення сигналу логічної одиниці вздовж нике (процессоры и память) / Под ред. Б.Н. Малидругого маршруту найкоротшого шляху він надхоновского. - К.: Техника, 1979. -366 с. дить з індикаційного входу 40(s) через елементи (с.183,рис.4.48). АБО 28, 1 21, І 17(s) і АБО 24(s) на індикаційний 6. Справочник по интегральным микросхемам вихід 41(s), де s - номер гілки графа вздовж друго/Под ред. Б.В. Тарабрина.-М.: Энергия, 1977, го маршруту найкоротшого шляху. В цей час еле(с.521, рис.5-42; с.540, рис.5-70; с.524, рис.5-48). менти І 23 заблоковані сигналом логічного нуля 17 Комп’ютерна верстка О.Воробєй 75209 Підписне 18 Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП ―Український інститут промислової власності‖, вул. Глазунова, 1, м. Київ – 42, 01601