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


https://doi.org/10.18255/1818-1015-2018-4-347-357

Полный текст:


Аннотация

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


Об авторах

Владимир Сергеевич Васильев
Сибирский федеральный университет, Институт космических и информационных технологий
Россия
аспирант


Александр Иванович Легалов
Сибирский федеральный университет, Институт космических и информационных технологий
Россия
д-р техн. наук, профессор


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

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


Дополнительные файлы

Для цитирования: Васильев В.С., Легалов А.И. Оптимизация инварианта цикла в языке Пифагор. Моделирование и анализ информационных систем. 2018;25(4):347-357. https://doi.org/10.18255/1818-1015-2018-4-347-357

For citation: Vasilev V.S., Legalov A.I. Loop-invariant Optimization in the Pifagor Language. Modeling and Analysis of Information Systems. 2018;25(4):347-357. (In Russ.) https://doi.org/10.18255/1818-1015-2018-4-347-357

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

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)