Складання розкладу для графів синхронних потоків даних

Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту виконання відповід...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автори:	Сергієнко, А.М., Сімоненко, В.П.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2016
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/131700
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-131700
record_format	dspace
spelling	irk-123456789-1317002018-03-28T03:02:35Z Складання розкладу для графів синхронних потоків даних Сергієнко, А.М. Сімоненко, В.П. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту виконання відповідних операторів алгоритму. На координати просторового ГСПД накладено обмеження: оператори, які виконуються в одному процесорному елементі, не повинні мати однакові такти свого виконання, які взято за модулем L. Завдяки цьому ГСПД відображається у спеціалізований обчислювач, який виконує алгоритм у конвеєрному режимі з оптимізованою завантаженністю ресурсів. Показано алгоритм пошуку субоптимального розкладу на основі просторового ГСПД. Рассмотрена задача составления расписания для алгоритма, заданного графом синхронных потоков данных (ГСПД). Предложен метод составления расписания ГСПД с периодом L тактов, основанный на преобразовании его в пространственный ГСПД, вершины которого имеют координаты места и момента выполнения соответствующих операторов алгоритма. На координаты пространственного ГСПД наложены ограничения: операторы, исполняемые в дном процессорном элементе, не должны иметь одинаковые такты своего исполнения, взятые по модулю L. Благодаря этому ГСПД отображается в специализированный вычислитель, исполняющий алгоритм в конвейерном режиме с оптимизированной загруженностью ресурсов. Показан алгоритм поиска субоптимального расписания на основе пространственного ГСПД. The scheduling problem for the synchronous dataflow graph (SDF) is considered. A method of the SDF scheduling is proposed which is based on transforming SDF into spatial SDF. The circular schedule has the period of L cycles. Each spatial SDF node has the coordinates of space and time of an event, where and when the respective algorithm steps were performed. A set of restrictions, which the SDF nodes have, helps to derive the circular schedule with the optimum load balancing. So, the nodes, which are mapped into a single resource, must not have the same clock cycles modulo L, and the number of such nodes has to approach L. The resulting schedule is implemented in the pipelined datapath. The algorithm for computing the suboptimal schedule is proposed based on the spatial SDF. 2016 Article Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр. 1681–6048 DOI: doi.org/10.20535/SRIT.2308-8893.2016.1.06 http://dspace.nbuv.gov.ua/handle/123456789/131700 004.383 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
spellingShingle	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Сергієнко, А.М. Сімоненко, В.П. Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології
description	Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту виконання відповідних операторів алгоритму. На координати просторового ГСПД накладено обмеження: оператори, які виконуються в одному процесорному елементі, не повинні мати однакові такти свого виконання, які взято за модулем L. Завдяки цьому ГСПД відображається у спеціалізований обчислювач, який виконує алгоритм у конвеєрному режимі з оптимізованою завантаженністю ресурсів. Показано алгоритм пошуку субоптимального розкладу на основі просторового ГСПД.
format	Article
author	Сергієнко, А.М. Сімоненко, В.П.
author_facet	Сергієнко, А.М. Сімоненко, В.П.
author_sort	Сергієнко, А.М.
title	Складання розкладу для графів синхронних потоків даних
title_short	Складання розкладу для графів синхронних потоків даних
title_full	Складання розкладу для графів синхронних потоків даних
title_fullStr	Складання розкладу для графів синхронних потоків даних
title_full_unstemmed	Складання розкладу для графів синхронних потоків даних
title_sort	складання розкладу для графів синхронних потоків даних
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2016
topic_facet	Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах
url	http://dspace.nbuv.gov.ua/handle/123456789/131700
citation_txt	Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT sergíênkoam skladannârozkladudlâgrafívsinhronnihpotokívdanih AT símonenkovp skladannârozkladudlâgrafívsinhronnihpotokívdanih
first_indexed	2025-07-09T15:59:26Z
last_indexed	2025-07-09T15:59:26Z
_version_	1837185649694736384
fulltext	© А.М. Сергієнко, В.П. Сімоненко, 2016 Системні дослідження та інформаційні технології, 2016, № 1 51 TIДC ПРОБЛЕМИ ПРИЙНЯТТЯ РІШЕНЬ І УПРАВЛІННЯ В ЕКОНОМІЧНИХ, ТЕХНІЧНИХ, ЕКОЛОГІЧНИХ І СОЦІАЛЬНИХ СИСТЕМАХ УДК 004.383 DOI: 10.20535/SRIT.2308-8893.2016.1.06 СКЛАДАННЯ РОЗКЛАДУ ДЛЯ ГРАФІВ СИНХРОННИХ ПОТОКІВ ДАНИХ А.М. СЕРГІЄНКО, В.П. СІМОНЕНКО Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодич- ного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту ви- конання відповідних операторів алгоритму. На координати просторового ГСПД накладено обмеження: оператори, які виконуються в одному процесор- ному елементі, не повинні мати однакові такти свого виконання, які взято за модулем L. Завдяки цьому ГСПД відображається у спеціалізований обчислю- вач, який виконує алгоритм у конвеєрному режимі з оптимізованою заванта- женністю ресурсів. Показано алгоритм пошуку субоптимального розкладу на основі просторового ГСПД. ВСТУП У персональних комп’ютерах, засобах мобільного зв’язку, пристроях цифро- вого оброблення сигналів та багатьох інших реалізовано програми і спецпро- цесори, які виконують обчислювальні процеси, що повторюються з періодом, який збігається з інтервалом надходження вхідних даних. Ці процеси вико- нуються за алгоритмами, які обробляють дані, організовані у потоки. Такі ал- горитми доцільно задавати на моделі графу потоків даних. Граф потоку даних — це напрямлений граф, вершини якого — актори — виражають операції, а дуги — потоки, через які передаються дані. У праці [1] запропоновано кла- сифікацію різних моделей графу потоку даних, серед яких виділяються графи синхронних потоків даних (ГСПД, Synchronous Dataflow — SDF). У ГСПД кожним актором під час виконання алгоритму генерується і використовується кількість змінних, які є незмінними від циклу до циклу [2, 3]. Розрізняють однорідні ГСПД (homoheneous SDF) і неоднорідні ГСПД (multirate SDF). В останніх кількість змінних, які використані та згенеровані кожною вершиною протягом одного циклу, може бути більшою за одиницю, унаслідок чого вони мають більш компактну форму задання алгоритму [4]. Для спрощення аналізу неоднорідного ГСПД та на його основі синтезу об- числювальних пристроїв граф найчастіше перетворюють в еквівалентний однорідний ГСПД [4, 5]. У роботі розглядаються лише однорідні ГСПД. Граф синхронних потоків даних має пряму аналогію з певним обчислю- вальним пристроєм. Логічні блоки такого пристрою відповідають вершинам А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 52 ГСПД, лінії зв’язку — дугам графу, а регістри операндів — затримкам у дугах. Тому ГСПД часто використовують для одиничного відображення алгоритму у структуру спеціалізованого обчислювального пристрою, яка час- то буває неоптимальною. Для пошуку оптимального структурного або про- грамного розв’язку необхідно скласти розклад виконання алгоритму в моделі ГСПД. У роботі розглядається метод складання розкладу на основі просторо- вого ГСПД, який забезпечує швидкий пошук як ефективного розкладу, так і структури обчислювального пристрою. СКЛАДАННЯ РОЗКЛАДУ ДЛЯ ГСПД Розглянемо приклад тестового алгоритму обчислення диференціального рів- няння 0=+′+′′ cyybxy [6,7]. Його розв’язують за алгоритмом: i = 0; while (xi < a) do xi+1 = xi + dx; ui+1 = ui − bxiuidx − cyidx; (1) yi+1 = yi + uidx; i = i + 1; end; де i — номер ітерації; dxcba ,,, — константи. Алгоритм зупиняється, тобто переривається запис у регістри змінних ix , iu , iy із досягненням межі .axi ≥ Цей алгоритм зображено як ГСПД на рис. 1. На ньому знаками «+», «×», кружечком і товстою крапкою позначено вершини множення на коефі- цієнт, додавання, подання )1( +i -х та i -х змінних відповідно. Пунктирними стрілками позначено дуги міжітераційної залежності, які навантажені за- тримками, позначеними товстими відрізками. Змінні у ГСПД позна- чаються мітками. Виконання алгоритму в ГСПД полягає у переміщенні міток уздовж дуг, спрацюванні вершин, якщо на їх входах є мітки, та видачі цих міток на виходи вершин. Мітка в дузі, яка навантажена затримками, затримується в ній на відпо- відну кількість ітерацій. Чер- гова ітерація закінчується в момент, коли мітки повер- таються у початкові верши- ни, наприклад, позначені на рис. 1 порожнім кружечком. За одиничного відобра- ження ГСПД у структуру пристрою цикл виконання однієї ітерації дорівнює од- 76 5 4 3 1 8 9 10 1 13 15 11 14 2 4 5 6 14 8 9 11 12 18 7 15 b c dx xi+1 16 ui+1 yi+1 dx 10 17 12 13 ui yi xi+1 dx 19 Рис. 1. Граф синхронних потоків розв’язання диференціального рівняння Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології, 2016, № 1 53 ному такту. При цьому розклад виконання алгоритму визначається поведін- кою ГСПД та затримками логічних схем, у які відображаються вершини графу. Але через велику довжину критичного шляху і великі апаратні ви- трати такий розклад не є раціональним. У цьому прикладі довжина критич- ного шляху дорівнює AMC ttT += 3 , де Mt , At — затримки помножувача та суматора відповідно. Пошук можливих розкладів виконання ГСПД є одним з етапів задачі синтезу конвеєрного обчислювального пристрою, який найчастіше розв’язують шляхом виконання, крім етапу розкладу, етапів вибору множи- ни ресурсів, призначення операцій на ресурси, побудови структури обчис- лювача і його блока керування, а також вибору обчислювального пристрою, який є оптимальним за заданим критерієм. Найбільш відомі та вживані методи складання розкладу, які мають об- меження на ресурси або час виконання з урахуванням ациклічного алгорит- му, що виконується одноразово. У розгляданому випадку — це ациклічний підграф ГСПД. Це такі методи, як метод спискового планування [9], скла- дання розкладу напрямленим зусиллям [10]. Для конвеєрних обчислюваль- них пристроїв у працях [11, 12] запропоновано методи, у яких після списко- вого складання розкладу призначаються оператори на конвеєрні ресурси з урахуванням циклічного характеру обчислень. Використовують також ме- тод відображення гнізда циклів у неконвеєрний обчислювальний пристрій з подальшим перетворенням його у конвеєрний пристрій [13]. Розклад заван- таження регістрів обчислювального пристрою ефективно складати згідно з евристикою Тсенга [14] та методом лівої межі (left-edge sheduling) [15]. Для урахування циклічності виконання алгоритму розклад часто скла- дають з використанням інтервального графу з циклічними дугами [16]. Для спрощення розв’язання задачі планування використовують різні евристики [17, 18] та методи ресинхронізації (retiming) [18, 19]. У праці [20] запропо- новано побудувати періодичний граф залежності за даними, розмістити його у багатовимірному просторі як напрямлений граф і знаходити розклад як проекцію графу на часову вісь. Складність багатоетапного синтезу обчислювального пристрою полягає в тому, що різні аспекти синтезу і етапи розроблення обчислювального при- строю — етапи вибору множини ресурсів, складання розкладу і призначення операцій на ресурси — істотно залежать один від одного. Кожен з етапів проектування не може бути виконаний незалежно так, щоб не зменшити можливості глобальної оптимізації обчислювального пристрою. Наприклад, мінімізація апаратних витрат при виборі ресурсів суперечить мінімізації тривалості циклу алгоритму для складання розкладу. Крім того, якщо за одиничного відображення алгоритму в структуру складність синтезу обчис- лювального пристрою оцінюється поліномом, то при відображенні з уповільненням у L разів задача синтезу стає NP-повною [8]. ПРОСТОРОВИЙ ГСПД ТА ЙОГО РОЗКЛАД Задання розкладу для ГСПД означає призначення його вершинам моментів спрацювання. Структуру обчислювального пристрою можна отримати шля- хом гомоморфного перетворення ГСПД у граф структури. Таке перетворення А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 54 означає склеювання вершин, оператори яких виконуються в одному проце- сорному елементі (ПЕ) пристрою, але в різні моменти часу [20]. Гомоморфне перетворення графу виконують, призначивши вершинам теги з номерами вершин ПЕ, де вони будуть виконуватися. Тоді у вершину ПЕ склеюються вершини з однаковими номерами. Отже, вершина ГСПД повинна мати тег з номером ПЕ, а також з моментом виконання оператора та його типом. Теги вершин зображаються цілочисловими багатовимірними векторами iK . При цьому момент спрацювання задається як номер такту. Тоді ГСПД буде поданий в багатовимірному цілочисловому просторі. Відображення алгоритму полягає у призначенні елементам матриці K цих векторів певних значень і побудові структури пристрою з обчисленням критерію його опти- мальності. Тоді оптимізація обчислювального пристрою полягає в побудові множини матриць K і виборі найбільш пріоритетної матриці за критерієм оптимальності. У праці [21] описано метод синтезу обчислювального пристрою, у яко- му ГСПД подано у тривимірному цілочисловому просторі у вигляді конфі- гурації алгоритму ,),,( ADKKG = де K — матриця векторів-вершин iK , що відповідають операторам алгоритму; D — матриця векторів-дуг jD , які виражають безпосередні інформаційні зв’язки між операторами; A — мат- риця інцидентності ГСПД. У векторі-вершині T),,( iiii tsk=K координати iii tsk ,, відповідають типу оператора, номеру процесорного елемента, де виконується цей оператор, і такту, у якому записується в регістр результат цього оператора. Отже, вектори iK являють собою теги, що кодують влас- тивості вершин ГСПД, і такий граф називається просторовим ГСПД. Просторовий ГСПД розщеплюється на просторову конфігурацію ),,( ADKK SSGS = і конфігурацію подій ),,( ADKK TTGT = , яким відпові- дають структура обчислювача та розклад виконання операторів. При цьому вектори T),,( iiii tsk=K розкладаються на вектори ,),( T iiS sk i =K що від- повідають координатам ПЕ, і вектори ,iT t i =K які означають моменти ви- конання відповідних операторів у ПЕ iSK . Тоді часова складова jT t j =D вектора залежності jD дорівнює затримці jt пересилання або оброблення відповідної змінної. Розклад виконання алгоритму — конфігурація подій, а його пошук — знаходження значень . iTK Можна вважати, що матриця K кодує деякий допустимий розв’язок, оскільки матриця D обчислюється за рівнянням .KAD = (2) Пошук оптимального структурного рішення полягає у знаходженні та- кої матриці ,K яка мінімізує заданий критерій якості, наприклад, такий, як у праці [21]. Для цього спочатку задаються координати векторів матриці OD , що забезпечують умови мінімального значення ,CT а координати век- торів iK знаходяться із співвідношення 1−= OO ADK , (3) Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології, 2016, № 1 55 де OD — матриця векторів-дуг; OA — матриця інцидентності кістяка ГСПД. Для пошуку ефективних структурних рішень необхідно керуватися та- кими закономірностями. Просторовий ГСПД є коректним, якщо в матриці K немає двох одна- кових векторів, тобто ji KK ,∀ ),( jiji ≠≠ KK . (4) Розклад виконання алгоритму з тривалістю ітерації в L тактів є корек- тним, якщо оператори, які відображаються в один і той самий ПЕ, викону- ються в різних тактах, тобто ji KK ,∀ ⇒== ),( jiji sskk it ≢ jt .mod L (5) Причому наступний оператор виконується не раніше за попередній, тобто ,)0( ≥≠∀ iDj t j DD (6) де jDD — вектор-дуга межітераційної залежності T),,( wLsk iiD j −=D , яка означає затримку на w циклів (ітерацій). Однотипні оператори необхідно відображати в ПЕ одного й того само- го типу, тобто LKqsspkkK qpjijiqpji ≤====∈ ,, ),,(,KK , (7) де qpK , — множина векторів-вершин операторів p-го типу, що відобража- ються в q-й ПЕ p-го типу .),,2,1( max pqq K= Дорівнювати нулю має також сума векторів-дуг jD , що входять у будь-який із циклів графу, включаючи дуги межітераційної залежності . jDD Тоді для i-го циклу ,)0,0,0( T , =∑ j j jib D (8) де ijb ― елемент i-го рядка цикломатичної матриці ГСПД. Дуги межітера- ційної залежності T),,( wLsk iiD j −=D означають затримку на w циклів (іте- рацій). Отже, просторовий ГСПД являє собою об’єднання ациклічного графу, який виконує обчислення однієї ітерації, і множини дуг , jDD які означають межітераційну затримку змінних на wL тактів. У простому випадку кожен оператор алгоритму виконується за один такт. Такий випадок є натуральним у проектуванні конвеєрних обчислюваль- них пристроїв на рівні регістрових передач. Складні оператори можуть ви- конуватись за кілька тактів. Але, працюючи у конвеєрному режимі, відпові- дні їм ПЕ мають вигляд ланцюжка конвеєрних ступенів, кожний з яких виконує однотактову затримку. А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 56 За цих умов пошук розкладу алгоритму полягає у такому. Необхідно призначити всім векторам-дугам Oi D∈D координату ,1=it тобто встано- вити затримку в один такт і знайти TK з відношення (3). Решту елементів матриці TD знаходять з рівнянь (2) і (8). Якщо для деяких з них не справ- джується нерівність (6), то збільшують координату it певних векторів Oi D∈D і повторюють пошук. Решту координат векторів iK знаходять з умов (4)−(8). Таким чином, буде побудовано найбільш швидкий розклад, оскільки кожен оператор ви- конується за один такт і немає зайвих затримок. Якщо побудована матриця K не задовольняє критерій оптимальності, наприклад якихось ресурсів не- обхідно надто багато, то змінюють деякі вектори iD , які пов’язані з цими ресурсами або змінюють L і повторюють пошук розкладу. Цілочислова оптимізація розкладу полягає в побудові ряду оптимізова- них рішень та виборі найбільш переважного з них за заданим критерієм оп- тимальності. Кожне з таких рішень взаємно однозначно кодується матрицею .K Початкове оптимізоване рішення можна обчислити як розклад, отрима- ний за правилами, описаними вище. Решту оптимізованих рішень знаходять завдяки еквівалентним перетвореннням просторового ГСПД, наприклад, за допомогою локальної перестановки векторів iK у просторі та взаємної пе- рестановки таких векторів з урахуванням умов (4)−(8). Таким чином, відбу- вається сканування простору ефективних рішень. При цьому доречно вико- ристовувати відомі методи оптимізації, такі як метод гілок і меж, генетичний метод та ін. ДОСКОНАЛИЙ КІСТЯК ГСПД Під час формування розкладу ГСПД за методом просторового ГСПД під час пошуку решти векторів jTD з рівняння (2) дуже ймовірна поява некоректно- го розкладу за умовою (6). Тому пошук розкладу залишається складною за- дачею комбінаторної оптимізації. Успішне складання розкладу за цим мето- дом істотно залежить від вибору кістяка ГСПД. Щоб вибрати кістяк, який би забезпечував швидкий пошук оптимального розкладу, розглянемо факто- ри, що викликають появу некоректного розкладу. По-перше, у графі може бути стягувальна дуга, тобто така, що замикає маршрут з кількох інших дуг, як наприклад, .3214 DDDD ++= . При цьому, якщо стягувальна дуга входить у кістяк, можлива неприпустима ситуація, коли часові складові векторів-дуг, які з’єднує ця дуга, можуть бути від’ємними. Приклад такого випадку показано на рис.2, а, з якого видно, що якщо взяти вісь ot за вісь часу, то часова складова вектора 3D виявиться від’ємною. По-друге, у графі є поперечні дуги, тобто такі дуги, які не є стягуваль- ними, але додавання яких до кістяка утворює у графі контури, тобто вони не входять у кістяк за визначенням [23]. На рис. 2, б дуги iD , kD є альтернатив- ними поперечними дугами. При цьому дуга iD входить до довшого марш- Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології, 2016, № 1 57 руту. Якщо iD не входить до кістяка ГСПД, то після визначення розкладу за рівнянням (3) з виразу (2) випливає, що ,0< iTD тобто такий розклад буде хибним. Отже, потрібно зважати на поперечні дуги, що входять у коротші маршрути, і вилучати їх з графу під час побудови кістяка. Розглянемо такі поперечні дуги, наявність яких може призвести до хиб- ного розкладу. Таку дугу назвемо критичною поперечною дугою. У графі можуть бути рівнозначні маршрути з однієї вершини в іншу, наприклад, як на рис. 2, в, де 654321 DDDDDD ++=++ . Тут критичною поперечною ду- гою є така, що замикає рівнозначний маршрут в контур, тобто 3D або 6D . Також критичною поперечною дугою є така дуга, яка належить до контуру, котрий формує підграф з декількома вершинами-витоками. Типовий такий підграф зображено на рис. 1, г, для якого критичними дугами є всі дуги, які входять у стоки підграфу, тобто .,, 41 DD K В обох випадках розглянуті підграфи належать до класу узгоджених графів. Узгодженим графом називають граф, у кожному циклі якого кіль- кість дуг є парною, а сума цих векторів-дуг дорівнює нулю [20]. У кістяк необхідно включити повністю хоча б один з рівнозначних маршрутів. Тому, якщо в початковому графі відмітити всі критичні поперечні дуги, то частина їх обов’язково потрапить у результуючий кістяк, що може призвести до хиб- ного розкладу. Тоді, щоб отримати коректний розклад, необхідно в кістяку відмітити вершини, у які заходять критичні поперечні дуги, і в процесі по- шуку розкладу перевіряти і корегувати часові складові дуг, які заходять у відмічені вершини. Критичні поперечні дуги ускладнюють задачу складання розкладу для ГСПД. Якщо у ГСПД немає таких дуг, то складність пошуку розкладу оці- нюється трудністю обчислення формул (2) і (3), тобто як .)( 2nO Кожна до- даткова критична поперечна дуга ускладнює цю задачу в середньому в 2/L разів, тобто за великої кількості таких дуг задача перетворюється у NP-повну. Для виконання комбінаторної оптимізації розкладу слід відмі- тити критичні поперечні дуги або вершини, у які вони входять. По-третє, якщо алгоритм є циклічним, то цикли в ньому замикаються дугами міжітераційних залежностей , jDD причому, наприклад, для графу, показаному на рис. 2, д, )( 321 DDDD ++−= jD і .L iDT −=D Тобто для та- D4 D1 D2 D3 о t a Dі б Dk D1 DDj D2 D3 д D1 D2 D3 D4 D5 D6 в D1 D2 D3 D4 г Рис. 2. Приклади підграфів для побудови кістяка А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 58 кої дуги часова складова відома заздалегідь і вона не може бути змінена. Оскільки ця дуга замикає цикли, недоцільно залишати її у кістяку ГСПД. Наведені фактори необхідно враховувати під час складання розкладу. Щоб таких урахувань було якомога менше, доцільно використовувати такий кістяк ГСПД, який спеціально підібраний для знаходження розкладу. На- звемо такий кістяк досконалим. Таким чином, можна сформулювати таке визначення. Досконалий кістяк — це кістяк ГСПД, у якому: а) немає стягувальних дуг, б) немає дуг міжітераційних залежностей, в) дуги входять у найдовші маршрути, г) відмічені вершини, у які заходять критичні поперечні дуги. У праці [23] запропоновано алгоритм побудови досконалого кістяка ГСПД і доведено такі твердження. Твердження 1. До досконалого кістяка належить критичний шлях ал- горитму. Твердження 2. Розклад, побудований на основі досконалого кістяка і рівняння (3), належить до розкладу, складеного за принципом найшвидшо- го призначення операторам моментів виконання (ASAP). ПРИКЛАД ПОШУКУ РОЗКЛАДУ ГСПД Щоб оцінити дієвість методу, розглянемо пошук розкладу для ГСПД (див. рис. 1). У досконалому кістяку цього ГСПД (рис. 3) вектор-дуга BD з’єднує початок системи координат з довільною вершиною. Вона штучно додана для того, щоб кількість дуг у кістяку збігалась з кількістю вершин. Це є умовою того, що рівняння (3) є невиродженим. У цьому прикладі, як у тестовому, використовуються суматори, що мають затримку в один такт, та конвеєрні блоки множення із затримкою у два такти. З урахуванням цього складається матриця затримок дуг кістяка: ( ) ,012212221 T 654321 181716141311109765431 xxxxxxD B OT = DВ 7654 3 3 1 8 9 10 1 13 15 11 14 2 4 5 6 14 9 11 12 7 xi 16 ui yi 10 17 13 19 Рис. 3. Досконалий кістяк для ГСПД (див. рис. 1) Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології, 2016, № 1 59 де 51 ,, xx K — невідомі величини, які залежать від векторів з рівнянь циклів (8), кількість яких дорівнює кількості дуг, які доповнюють кістяк до ГСПД. Тобто кожен цикл графу повинен мати принаймні одну змінну. У цьому ГСПД п’ять циклів і відповідно система складається з п’яти рівнянь: ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ =−++−++ =+−−++ =++ =+++++ =++ .0 ,0 ,0 ,0 ,0 1819179131110 17912654 181514 1787654 321 DDDDDDD DDDDDD DDD DDDDDD DDD (9) Розв’язавши систему рівнянь (9), знаходимо ;61 =x ;52 =x ;53 =x ;05 =x .66 =x Змінна 64 =x вибирається довільно. Період алгоритму 7=L вибирається як довжина критичного шляху: .)( 1776548 DDDDDD ++++−= За рівнянням (2) знаходимо матрицю TK : KT = OA ( )T B 060415225122261 181716141311109765431 = = ( )T76097541110864298 . Перевіряємо справедливість вимоги (5). Решту координат матриці K отримуємо згідно з вимогою (4), беручи до уваги, що кількість вершин, розміщених в одному рядку, паралельному осі ох, для мінімізації апаратних витрат має прямувати до L: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 76097541110864298 413122341222341 324211432111432 151413121110987654321 K . Графічне зображення побудованого просторового ГСПД показано на рис. 4. За цим графом формальним чином за методикою, викладеною Рис. 4. Просторовий ГСПД, який обчислює рівняння (1) t0 1 2 3 4 5 6 7 8 9 10 5 3 4 2 10 4 3 2 1 8 71 11 12 6 91 14 15 S А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 60 у праці [24], можна скласти опис обчислювального пристрою мовою VHDL. Структуру відповідного пристрою показано на рис. 5. Іншим тестовим прикладом є синтез хвильового рекурсивного фільтра п’ятого порядку [6]. У таблиці наведено результати такого синтезу з вико- ристанням простого та конвеєрного блоків множення із затримкою на два такти. Їх порівняння з відомими результатами, отриманими за іншими мето- дами, показує, що запропонований метод дає мінімальні апаратні витрати у кількості блоків множення, суматорів та регістрів за рахунок збільшеної кількості мультиплексорів. Результати синтезу обчислювального пристрою для обчислення еліптичного фільтра п’ятого порядку Просторовий ГСПД, блок множення SPAID [25], блок множення HAL[6], блок множення Параметр простий конвеєрний простий конвеєрний простий конвеєрний Блоки множення 2 1 1 3 2 2 3 2 1 Суматори 3 3 2 3 3 2 3 3 2 Входи мультиплексорів 55 41 36 37 35 24 36 37 28 Регістри 11 11 10 21 21 21 12 12 12 Період обчислень L 17 17 19 17 17 19 17 17 19 Цей метод був застосований для синтезу конвеєрних процесорів швид- кого перетворення Фур’є, дискретного косинусного перетворення, рекурси- вних фільтрів. Деякі з них як віртуальні модулі, що описані мовою Verilog, MPU RG RG MUX MUX SM RG dx RGU RGY RGX MUX M U X dx b c Рис. 5. Структура пристрою, що відповідає просторовому ГСПД (див. рис. 4) Складання розкладу для графів синхронних потоків даних Системні дослідження та інформаційні технології, 2016, № 1 61 зберігаються у спільноті opencores.org і є доступними для порівняння, як наприклад, рекурсивний фільтр високого порядку, що динамічно перебу- довується [26]. ВИСНОВКИ У роботі запропоновано формальний метод складання розкладу для графу синхронних потоків даних, який забезпечує синтез конвеєрних обчислюваль- них пристроїв з регламентовано великою пропускною здатністю та мінімі- зованими апаратними витратами. Приклад розроблення пристрою для розв’язання диференціального рів- няння свідчить, що для невеликих графів можливе знаходження точного розв’язку задачі синтезу. Досвід розроблення більш складних проектів, та- ких як процесори швидкого перетворення Фур’є, рекурсивні фільтри висо- кого порядку, показує, що метод варто застосовувати з комбінаторною оп- тимізацією. Але така оптимізація менш складна, ніж з використанням інших методів через велику кількість обмежень, які накладаються на просторовий граф синхронних потоків даних. Метод може бути застосований не тільки для розроблення конвеєрних спеціальних процесорів, але і для програмування паралельних мультипроце- сорних систем. ЛІТЕРАТУРА 1. Сергиенко А.М. Алгоритмические модели обработки потоков данных / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2008. — Т. 30. — № 6. — С. 49−60. 2. Lee E.A. Synchronous Datafow / E.A. Lee, D.G. Messerschmitt // Proc. IEEE. — 1987. — V. 75. — N 9. — P. 1235–1245. 3. Edwards S. Design of Embedded Systems: Formal Models, Validation, and Synthesis / S. Edwards, L. Lavagno, E.A. Lee, A. Sangiovanny-Vincentelli // Proc. IEEE. — 1997. — V. 85. — N 3. — P. 366−390. 4. Lee E.A. Static scheduling of synchronous data flow programs for digital signal processing / E.A. Lee, D.G. Messerschmitt // IEEE Trans. on Computers. — 1987. — V. 36. — N 1. — P. 24−35. 5. O’Neil T.W. Retiming synchronous data-flow graphs to reduce execution time / T.W. O’Neil, E.H.M. Sha // IEEE Trans. on Signal Processing. — 2001. — 49, N 10. — P.2397–2407. 6. Paulin P. G. HAL: A multi-paradigm approach to automatic data path synthesis / P.G. Paulin, J.P. Knight, E.F. Girczyc // Proc. 23-rd IEEE Design Automation Conf, Las Vegas, NV, July 1986. — 1986. — P. 263−270. 7. Chao L. Rotation scheduling: A loop pipelining algorithm / L. Chao, A. LaPaugh, E. Sha // Proc 30-th Design Automation Conf., DAC’93, June 1993. — 1993. — P. 566–572. 8. The Systhesis Approach to Digital System Design / Editors P. Micheli, U.Lauther, P. Duzy. — Kluwer Academic Pub, 1992. — 415 p. 9. ЭВМ и теория расписаний / Под ред. И.Г. Кофмана. — М.: Мир, 1979. — 460 с. 10. Paulin P.G. Force – Directed Sheduling for the Behavioral Synthesis of ASICs / P.G. Paulin, J.P. Knight // IEEE Trans. CAD. —1988. — 7, N 3. — P. 356–370. А.М. Сергієнко, В.П. Сімоненко ISSN 1681–6048 System Research & Information Technologies, 2016, № 1 62 11. Park N. Module Assignment and Interconnect Sharing in Register-Transfer Synthesis of Pipelined Data Paths / N. Park, F.J. Kurdahi // Proc. IEEE Int. Conf. on Computer Aided Design. — Santa Clara, Calif. — 1989. — P. 16−19. 12. Hwang K. S. Scheduling and hardware sharing in pipelined data paths / K.S. Hwang, A.E. Casavant, C.T. Chang, M.A. d’Abreu // Proc. Int’l Conf. on Computer Aided Design. — 1989. — P. 24–27. 13. Catthoor F. Application-specific architectural methodologies for high-throughput digital signal and image processing / F. Catthoor, H. De Man // IEEE Trans. on Acoustics, Speech and Signal Processing. — 1990. — 38, N 2. — P. 339−349. 14. Tseng C. Automated Synthesis of Data Paths in Digital Systems / C. Tseng, D. Siewiorek // IEEE Trans. on Computer-Aided Design. — 1986. — N 7. — P. 379−395. 15. Kurrdahi F.J. REAL: A Program for Register Allocation / F.J. Kurrdahi, A.C. Parker // Proc. 24-th ACM/ IEEE Design Automation Conf. DAC-87. — 1987. — P. 210−215. 16. Tucker A. Coloring a family of circular arcs / A. Tucker // SIAM J. Appl. Math. — 1975. — 29, N 3. — P. 493−502. 17. Springer D.L. Exploiting the Special Structure of Conflict and Compatibility Graphs in High-Level Synthesis / D.L. Springer, D.E. Thomas // Proc. Int. Conf. Computer Aided Design (ICCAD). — 1990. — P. 254−257. 18. Robert Y. Introduction to Scheduling / Y. Robert, F. Vivien − Ed-s. CRC Press, Taylor and Francis Group. — 2010. — 310 p. 19. Lee E.A. Static scheduling of synchronous data flow programs for digital signal processing / E.A. Lee, D.G. Messerschmitt // IEEE Trans. on Computers. — 1987. — 36, N 1. — P. 24−35. 20. Воеводин В.В. Математические модели и методы в параллельных процесах / В.В. Воеводин. — М: Наука. — 1986. — 296 с. 21. Сергиенко А.М. Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2007. — 29, № 2. — С. 49−61. 22. Евстигнеев В.А. Применение теории графов в программировании / В.А. Евстигнеев; под ред. А.П. Ершова. — М: Наука, 1985. — 352 с. 23. Сергієнко А.М. Досконалий кістяк графe алгоритму / А.М. Сергієнко // Інфор- матика і обчислювальна техніка: зб. наук. праць. — 2007. — № 46. — С. 62−67. 24. Сергиенко А.М. VHDL для проектирования вычислительных устройств / А.М. Сергиенко. — К.: ДиаСофт, 2003. — 210 с. 25. Haroun B.S. SPAID: An Architectural Synthesis Tool for DSP Custom Applications / B.S. Haroun, M.I. Elmasry // Proc. IEEE Custom Integrated Circuits Conf. — Rochester, N.Y. — May 16–19. — 1988. — P. 14.4/1−14.4/5. 26. Sergiyenko A. Low-Pass IIR Filter / A. Sergiyenko, O. Uzenkov. — 2010. — Available at http://opencores.org/project,lp_iir_filter Надійшла 25.08.2015

Складання розкладу для графів синхронних потоків даних

Репозитарії

Схожі ресурси