Складання розкладу для графів синхронних потоків даних
Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту виконання відповід...
Saved in:
| Published in: | Системні дослідження та інформаційні технології |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2016
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131700 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-131700 |
|---|---|
| record_format |
dspace |
| spelling |
Сергієнко, А.М. Сімоненко, В.П. 2018-03-27T19:50:04Z 2018-03-27T19:50:04Z 2016 Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр. 1681–6048 DOI: doi.org/10.20535/SRIT.2308-8893.2016.1.06 https://nasplib.isofts.kiev.ua/handle/123456789/131700 004.383 Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом 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. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Складання розкладу для графів синхронних потоків даних Составление расписания для графов синхронных потоков данных Method of synchronous dataflow scheduling Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Складання розкладу для графів синхронних потоків даних |
| spellingShingle |
Складання розкладу для графів синхронних потоків даних Сергієнко, А.М. Сімоненко, В.П. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| title_short |
Складання розкладу для графів синхронних потоків даних |
| title_full |
Складання розкладу для графів синхронних потоків даних |
| title_fullStr |
Складання розкладу для графів синхронних потоків даних |
| title_full_unstemmed |
Складання розкладу для графів синхронних потоків даних |
| title_sort |
складання розкладу для графів синхронних потоків даних |
| author |
Сергієнко, А.М. Сімоненко, В.П. |
| author_facet |
Сергієнко, А.М. Сімоненко, В.П. |
| topic |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| topic_facet |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| publishDate |
2016 |
| language |
Ukrainian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Составление расписания для графов синхронных потоков данных Method of synchronous dataflow scheduling |
| description |
Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом 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.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/131700 |
| citation_txt |
Складання розкладу для графів синхронних потоків даних / А.М. Сергієнко, В.П. Сімоненко // Системні дослідження та інформаційні технології. — 2016. — № 1. — С. 51-62. — Бібліогр.: 26 назв. — укр. |
| work_keys_str_mv |
AT sergíênkoam skladannârozkladudlâgrafívsinhronnihpotokívdanih AT símonenkovp skladannârozkladudlâgrafívsinhronnihpotokívdanih AT sergíênkoam sostavlenieraspisaniâdlâgrafovsinhronnyhpotokovdannyh AT símonenkovp sostavlenieraspisaniâdlâgrafovsinhronnyhpotokovdannyh AT sergíênkoam methodofsynchronousdataflowscheduling AT símonenkovp methodofsynchronousdataflowscheduling |
| first_indexed |
2025-12-07T15:22:50Z |
| last_indexed |
2025-12-07T15:22:50Z |
| _version_ |
1850863486495621120 |