7.5. Використання графа алгоритму при побудові арифметико-логічного пристрою

Щоб виявити ефективні підходи до реалізації алгоритму виконання складної опера­ції в АЛП, необхідно представити його в формі, яка розкриває його базові обчислюваль­ні та структурні характеристики. Обчислювальні характеристики описуються повним набором функціональних операторів алгоритму і відповідними їм обчислювальними затримками. Структурні характеристики описуються зв'язками між функціональними операторами алгоритму і 'їх взаємозалежністю.

Однією із можливих форм представлення алгоритму є графічна. На рис. 7.6а пред­ставлений граф деякого алгоритму.

Кожна вершина графа представляє функціональний оператор алгоритму, кожна дуга - зв'язок між функціональними операторами. Вершина, яка відповідає функціонально­му оператору Фі, з'єднується з вершиною, яка відповідає функціональному оператору

245

Фj, тільки в тому випадку, коли результат, одержаний після виконання оператора Фі, є одним із аргументів для оператора Фj. Описана графічна форма представлення алгорит­му дозволяє оцінити його обчислювальні характеристики, тому широко використову­ється при синтезі АЛП.

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

Виявити в алгоритмі паралелізм і навіть керувати ним, забезпечуючи тим самим мож­ливість знаходження компромісних просторово-часових співвідношень, що є головним при виборі структури обчислювального пристрою, дозволяє представлення графа алго­ритму в потоковій (ярусно-паралельній) формі. Таке представлення графа означає розді­лення всіх його вершин по ярусах таким чином, що в і-му ярусі розміщені тільки функ­ціональні оператори, які залежать хоча б від одного функціонального оператора (і-І)-го яруса і не залежать від функціональних операторів, які не входять в яруси з меншими ніж і номерами. Всередині яруса функціональні оператори між собою не мають з'єднань. Описаний граф називають потоковим графом (ПГ) алгоритму. На рис. 7.6b представлено ПГ раніше розглянутого алгоритму, де штриховими лініями розділені яруси графа.

ПГ алгоритму характеризується набором функціональних операторів Фі] (і=1, 2,...,Р; j=l,2,...,Li), де і - номер яруса, Р - кількість ярусів, j - номер функціонального оператора в ярусі, Li - їх кількість в ярусі, а також набором каналів Kij зв'язку між функціональни­ми операторами.

При розгляді питань проектування пристрою для виконання деякого алгоритму у вигляді надвеликої інтегральної схеми (НВІС), використовують його конкретизований потоковий граф. В конкретизованому потоковому графі алгоритму всі функціональні оператори входять до бібліотеки функціональних елементів НВІС, на- базі якої реалі­зується алгоритм. Тобто кожному функціональному оператору алгоритму може бути поставленигї у відповідність як мінімум один функціональний елемент із бібліотеки функціональних елементів НВІС. Таке представлення алгоритму забезпечує можливість пошуку найефективнішого варіанту його апаратурної реалізації.