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

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

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

Разработанный подход может применяться для таких языков функционально-потокового программирования, как Пифагор и 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.