СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

ISSN (печатн.): 2782-2001          ISSN (онлайн): 2782-215X
English | Русский

Последний выпуск
№1(81) Январь - Март 2021

Оптимизация графов потока управления в промежуточных представлениях языка функционально-потокового параллельного программирования

Выпуск № 4 (80) Октябрь - Декабрь 2020
Авторы:

Васильев Владимир Сергеевич,
Легалов Александр Иванович
DOI: http://dx.doi.org/10.17212/1814-1196-2020-4-37-46
Аннотация

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



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



Разработанный подход может применяться для таких языков функционально-потокового программирования, как Пифагор и Smile.


Ключевые слова: оптимизация кода, граф потока управления, анализ управляющих зависимостей, функционально-потоковое программирование, управление вычислениями, параллельное программирование, анализ программ, задержанные вычисления

Список литературы

1. Легалов А.И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии. – 2005. – Т. 10, № 1. – С. 71–89.



2. Легалов А.И., Савченко Г.В., Васильев В.С. Событийная модель вычислений, поддерживающая выполнение функционально-потоковых параллельных программ // Системы. Методы. Технологии. – 2012. – № 1 (13). – С. 113–119.



3. Динамически изменяющийся параллелизм с асинхронно-последовательными потоками данных / А.И. Легалов, И.В. Матковский, М.С. Ушакова, Д.С. Романова // Моделирование и анализ информационных систем. – 2020. – Т. 27, № 2. – С. 164–179. – DOI: 10.18255/1818-1015-2020-2-164-179.



4. Дордопуло А.И., Левин И.И. Ресурсонезависимое программирование гибридных реконфигурируемых вычислительных систем // Суперкомпьютерные дни в России: труды международной конференции, 25–26 сентября 2017 г., г. Москва. – М.: Изд-во МГУ, 2017. – C. 714–723.



5. Левин И.И., Дордопуло А.И., Гудков В.А. Программирование реконфигурируемых вычислительных узлов на языке COLAMO. – Таганрог: ЮФУ, 2011. – 114 p.



6. Легалов А.И., Легалов И.А., Матковский И.В. Добавление статической типизации в язык функционально-потокового параллельного программирования // Электронные библиотеки. – Т. 23, № 4. – С. 788–807. – DOI: 10.26907/1562-5419-2020-23-4-788-807.



7. Непомнящий О.В., Рыженко И.Н., Легалов А.И. Метод архитектурно-независимого высокоуровневого синтеза СБИС // Известия ЮФУ. Технические науки. – 2018. – № 8 (202). – С. 38–47.



8. Непомнящий О.В., Рыженко И.Н., Легалов А.И. Методы, алгоритмы и программные инструменты архитектурно независимого высокоуровневого синтеза однокристальных цифровых систем // Суперкомпьютерные технологии (СКТ-2018). – Ростов н/Д., 2018. – Т. 1. – С. 104–109.



9. Удалова Ю.В. Верификация функционально-потоковых параллельных программ с помощью интервальных формул // Образовательные ресурсы и технологии. – 2016. – № 2 (14). – С. 259–262.



10. Ушакова М.С., Легалов А.И. Верификация программ со взаимной рекурсией на языке Пифагор // Моделирование и анализ информационных систем. – 2018. – Т. 25, № 4. – С. 358–381.



11. Васильев В.С. Оптимизация программ функционально-потокового языка Пифагор // Перспективы развития информационных технологий. – 2014. – № 20. – С. 7–14.



12. A toolkit for the development of data-driven functional parallel programmes / A.I. Legalov, V.S. Vasilyev, I.V. Matkovskii, M.S. Ushakova // Parallel Computational Technologies, PCT 2018 / ed. by L. Sokolinsky, M. Zymbler. – Cham: Springer, 2018. – DOI: 10.1007/978-3-319-99673-8_2.



13. Легалов А.И. Об управлении вычислениями в параллельных системах и языках программирования // Научный вестник НГТУ. – 2004. – № 3 (18). – С. 63–72.



14. Рыбаков A.A. Анализ алгоритмов оптимизации расположения в памяти линейных участков программы // Известия высших учебных заведений. Электроника. – 2013. – № 1. – С. 47–53.



15. Битнер В.А., Заборовский Н.В. Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов // Моделирование и анализ информационных систем. – 2013. – Т. 20, № 2. – С. 166–177. – DOI: 10.18255/1818-1015-2013-2-166-177.

Для цитирования:

Васильев В.С., Легалов А.И. Оптимизация графов потока управления в промежуточных представлениях языка функционально-потокового параллельного программирования // Научный вестник НГТУ. – 2020. – № 4 (80). – С. 37–46. – DOI: 10.17212/1814-1196-2020-4-37-46.

 

For citation:

Vasilev V.S., Legalov A.I. Optimizatsiya grafov potoka upravleniya v promezhutochnykh predstavleniyakh yazyka funktsional'no-potokovogo parallel'nogo programmirovaniya [Control flow graphs optimization in intermediate representations of the functional dataflow parallel programming language]. Nauchnyi vestnik Novosibirskogo gosudarstvennogo tekhnicheskogo universiteta = Science bulletin of the Novosibirsk state technical university, 2020, no. 4 (80), pp. 37–46. DOI: 10.17212/1814-1196-2020-4-37-46.

Просмотров: 153