Оптимизация инварианта цикла в языке Пифагор

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

1. Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д., Компиляторы: принципы, технологии и инструментарий, 2-е изд., Вильямс, М., 2008, 1184 с.

2. Дортман П. А., “Подходы к оптимизации программ в системе SFP”, Программные средства и математические основы информатики, Новосибирск, 2004, 43– 49

3. Легалов А. И., Матковский И. В., Кропачева М. С., Удалова Ю. В., Васильев В. М., “Технологические аспекты создания, преобразования и выполнения функциональнопотоковых параллельных программ”, Научный сервис в сети Интернет: все грани параллелизма: Труды Международной суперкомпьютерной конференции, Изд-во МГУ, M., 2013, 443–447

4. Легалов А. И., Васильев В. С., Матковский И. В., Ушакова М. С., “Инструментальная поддержка создания и трансформации функционально-потоковых параллельных программ”, Труды Института системного программирования РАН, 29:5 (2017), 165– 184

5. Легалов А. И., “Функциональный язык для создания архитектурно-независимых параллельных программ”, Вычислительные технологии, 10:1 (2005), 71–89