Оптимизация и трансформация функционально-потоковых параллельных программ тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Васильев Владимир Сергеевич
Васильев Владимир Сергеевич
кандидат наук
2023
- Специальность ВАК РФ00.00.00
- Количество страниц 166
Оглавление диссертации кандидат наук Васильев Владимир Сергеевич
Введение
1 Особенности задачи оптимизации программ
1.1 Оптимизация программ на разных уровнях организации вычислительных систем
1.1.1 Использование параллелизма вычислительной системы
1.1.2 Использование более быстрых видов памяти
1.1.3 Методы оптимизации на физическом уровне архитектуры
1.1.4 Методы оптимизации на уровне языков программирования
1.1.4.1 Удаление общих подвыражений
1.1.4.2 Распространение и подстановка констант
1.1.4.3 Снижение стоимости операций
1.1.4.4 Удаление неиспользуемого кода
1.1.4.5 Подстановка тела функции вместо вызова
1.1.4.6 Оптимизация хвостовых вызова и рекурсии
1.1.4.7 Вынос инварианта за тело цикла
1.1.4.8 Замена индуктивных переменных цикла
1.2 Промежуточные представления, используемые при анализе и оптимизации программ
1.2.1 Граф потока управления
1.2.2 Цепочки определение-использование
1.2.3 Граф зависимостей по данным
1.2.4 Форма статического единственного присваивания
1.2.5 Граф программных зависимостей
1.2.6 Граф вызова подпрограмм
1.2.7 Абстрактное синтаксическое дерево
1.3 Особенности существующих систем оптимизации кода
1.4 Особенности применения существующих подходов к оптимизации функционально-потоковых параллельных программ
1.5 Методы оптимизации функционально-потоковых программ
1.6 Выводы по главе
2 Оптимизация функционально-потоковых параллельных программ
2.1 Обозначения, используемые при описании алгоритмов
2.2 Алгоритмы оптимизации функционально-потоковых параллельных программ
2.2.1 Вынос инварианта из повторяющихся вычислений
2.2.1.1 Оптимизация инварианта рекурсивной функции
2.2.1.2 Оптимизация инварианта в вычислениях над списками
2.2.2 Удаление неиспользуемого кода
2.2.3 1пНпе-подстановка функции
2.2.4 Удаление общих подвыражений
2.2.5 Оптимизация на основе эквивалентных преобразований
2.2.5.1 Удаление списков из одного элемента
2.2.5.2 Предварительная интерпретация параллельных списков
2.2.5.3 Раскрытие параллельных списков, вложенных в список данных
2.2.6 Методы оптимизации управляющего графа
2.2.6.1 Удаление лишних прямых управляющих зависимостей
2.2.6.2 Удаление лишних задержанных управляющих зависимостей
2.2.6.3 Замена управляющих автоматов упрощенными версиями
2.2.7 Замена хвостовой рекурсии циклом
2.3 Выводы по главе
3 Инструментальная поддержка оптимизирующих преобразований функционально-потоковых параллельных программ
3.1 Выбор формы представления программы в оптимизаторе
3.1.1 Операции над представлением программы при оптимизации
3.1.1.1 Поиск, удаление, вставка, изменение узла/дуги
3.1.1.2 Обходы графа, поиск следующего узла
3.1.1.3 Поиск подграфа определенного вида
3.1.2 Анализ вариантов внутреннего представления программ
3.1.2.1 Анализ вариантов внутреннего представления информационного графа
3.1.2.2 Анализ вариантов реализации внутреннего представления управляющего графа
3.1.3 Структуры данных системы оптимизации
3.2 Инструментальная поддержка методов оптимизации ФПП программ
3.2.1 Использование системы оптимизации
3.2.2 Примеры оптимизации программ языка Пифагор, результаты
3.2.3 Порядок применения оптимизирующих преобразований
3.3 Выводы по главе
4 Преобразование промежуточных представлений функционально-потовых языков в последовательные императивные программы
4.1 Проблемы разработки системы преобразования программ
4.2 Трансформация в императивные конструкции операторов функционально-потоковой модели вычислений
4.2.1 Задержанные списки
4.2.2 Списки данных, аргументы функции
4.2.3 Параллельные списки
4.2.4 Операторы
4.2.4.1 Оператор транспонирования
4.2.4.2 Оператор дублирования
4.2.4.3 Оператор получения длины списка
4.2.4.4 Арифметические операторы
4.2.4.5 Оператор генерации
4.3 Типизация функционально-потоковых параллельных программ
4.4 Реализация системы преобразования программ
4.4.1 Разметка узлов графа программных зависимостей типами
4.4.2 Подготовка и трансформация узлов
4.5 Инструментальная поддержка преобразования функционально-потоковых программ в императивную форму
4.6 Выводы по главе
Заключение
Список литературы
Список сокращений
Приложение А Примеры оптимизируемых программ
Приложение А.1 Функции сравнения значений любых типов
Приложение А.2 Древовидная свертка списка
Приложение А.3 Функция тар
Приложение А.4 Умножение матриц
Приложение А.5 Скрипт применения оптимизирующих преобразований для
тестового набора функций
Приложение Б Тестовые наборы системы трансформации функционально-
потоковых программ в последовательную императивную форму
Приложение Б.1 Примеры программ для тестирования трансформации
отдельных конструкций языка
Приложение Б.2 Комплексные примеры входных данных для системы
трансформации программ
Приложение В Акты о внедрении
Введение
В настоящее время для программирования параллельных вычислительных систем (ПВС) используются разнообразные подходы. Во многом это обуславливается необходимостью создания эффективных программных продуктов при большом разнообразии архитектур ПВС, каждая из которых имеет свои особенности написания кода. В связи с этим параллельные программы часто оказываются архитектурно-непереносимыми.
При параллельном программировании широко используются методы и инструментальные средства, учитывающие особенности существующих архитектурных решений. Например для систем с общей памятью часто применяют такие библиотеки как OpenMP [1], программирование распределенных систем осуществляется с использованием MPI [2], программы для графических ускорителей пишутся с применением CUDA или OpenCL [3, 4]. Перенос программы с одной параллельной архитектуры на другую является сложной задачей и в основном осуществляется вручную. Еще более трудоемким является программирование гетерогенных систем. Тем не менее предпринимались попытки автоматизации этого процесса. Например система OMP2MPI [5] позволяет выполнить преобразование параллельной программы, разработанной для архитектуры с общей памятью, в параллельную программу для кластерной архитектуры, а система OMP2HMPP [6] формирует на ее же основе аналогичную программу для гетерогенного кластера, использующего графическое ускорители. Нередко задача обеспечения переносимости возлагается на интерпретатор или компилятор времени исполнения (JIT-компилятор), например такой подход используется в языках Java и Python [7].
Из-за отличия в организации параллельных вычислений программы, эффективно выполняемые на одной архитектуре, могут оказаться неэффективными на другой. Зачастую вместо прямого преобразования программ между ПВС целесообразнее преобразовывать последовательные программы. Существует ряд инструментов, обеспечивающих автоматическое распараллеливание последовательных
программ, однако основная их часть ориентирована на системы с общей памятью. Например такое преобразование выполняет открытая распараллеливающая система, заменяющая циклы в последовательной программе на их параллельные версии [8]. Существуют также экспериментальные версии этой системы, выполняющие распараллеливание для систем с распределенной памятью [9] и графических ускорителей [10]. Такого рода инструменты сталкиваются с проблемами выявления параллелизма, разделяемых ресурсов и обеспечения эффективного распределения этих ресурсов между вычислителями с учетом особенностей архитектуры. На примере системы АиюРаг показано [11], что данная задача решается проще для языков функционального программирования.
Наряду с этими подходами возможно изначальное написание программистом архитектурно-независимых параллельных программ с использованием концепции неограниченного параллелизма [12], это позволяет отойти от необходимости распараллеливания и привязки к конкретным архитектурам. В рамках этой концепции развивается направление, ориентированное на функционально-потоковое параллельное (ФПП) программирование [13, 14]. Функционально-потоковая модель вычислений описывает программу как информационный граф с управлением по готовности данных [15, 16]. В модели определен ряд конструкций, позволяющих описывать неявный параллелизм, обеспечивающий поддержку как синхронных, так и асинхронных параллельных вычислений. Программа, имеющая лишь информационные зависимости, находится в максимально параллельной форме [17], где все потенциально параллельные фрагменты уже выделены. За счет этого возможна более гибкая трансформация программы в другие параллельные архитектурно-зависимые языки.
Несмотря на то, что в настоящее время для ФПП парадигмы разработан ряд инструментальных средств, позволяющих выполнять такие программы [103, 104], их отладку и верификацию [18, 19], задачи, связанные с различными трансформациями ФПП программ, обеспечивающими перенос на реальные архитектуры, до конца не решены. В частности отсутствуют инструменты анализа, оптимизации и
трансформации этих программ в другие языки программирования. Существующие системы анализа и оптимизации кода не могут напрямую использоваться в связи с различием подходов к управлению вычислениями, а используемые в них методы требуют переосмысления с учетом особенностей функционально-потоковой парадигмы параллельного программирования.
Повышение эффективности как трансформации, так и выполнения ФПП программ может быть обеспечено за счет использования методов оптимизации и преобразования, многие из которых аналогичны методам, используемым в других парадигмах. Особенности ФПП программирования накладывают на реализацию этих методов свою специфику. Кроме того, возможна оптимизация кода за счет применения приемов, которые непосредственно вытекают из особенностей данной парадигмы. Не проработаны вопросы преобразования операторов функционально-потоковой модели параллельных вычислений в эквивалентные операторы императивных языков программирования, типичных для современных последовательных и параллельных архитектур. В связи с этим разработка методов оптимизации и преобразования ФПП программ, является актуальной задачей.
Целью работы повышение эффективности выполнения функционально-потоковых параллельных программ за счет разработки новых методов их оптимизации и трансформации.
Для достижения указанной цели в работе решались следующие задачи:
- анализ существующих методов оптимизации программ и возможности их применения в ФПП парадигме;
- разработка методов и алгоритмов оптимизации программ с учетом специфики ФПП парадигмы;
- исследование и разработка методов и алгоритмов преобразования ФПП программ в императивные;
- разработка инструментальных средств, обеспечивающих комплексную поддержку анализа, оптимизации и преобразования ФПП программ в программы, выполняемые на реальных вычислительных системах.
Предмет и объект исследования. Объектом исследования является функционально-потоковая модель параллельных вычислений. Предмет исследования -методы оптимизации и трансформации ФПП программ в императивную форму.
Методы исследования. Поставленные задачи решались посредством элементов теории графов, теории языков программирования, математической логики, теории конечных автоматов, технологии трансляции и теории алгоритмов.
При разработке основных положений диссертации применялись методы системного анализа вычислительных систем, функционально-потокового и объектно-ориентированного проектирования и программирования.
Разработанное программное обеспечение реализовано на языке С++.
Научная новизна.
1. Предложены методы и алгоритмы оптимизирующих трансформаций информационных графов функционально-потоковых параллельных программ, обеспечивающие сокращение времени выполнения и объема используемой памяти.
2. Разработаны методы преобразования управляющих графов функционально-потоковых языков программирования, позволяющие оптимизировать стратегию управления вычислениями в таких языках за счет устранения избыточных управляющих зависимостей, что позволяет ускорить выполнение функционально-потоковых параллельных программ.
3. Предложен и реализован метод трансформации функционально-потоковых параллельных программ в эквивалентные императивные программы, позволяющий более эффективно исполнять их на существующих вычислительных системах за счет представления программы на уровне системы команд.
Положения, выносимые на защиту.
1. Разработанные методы оптимизации информационных графов функционально-потоковых параллельных программ обеспечивают ускорение вычислений и сокращают необходимый для этого объем памяти.
2. Применение методов оптимизации управляющих графов ускоряет вычисления за счет устранения избыточных управляющих зависимостей.
3. Предложенный метод трансформации функционально-потоковых параллельных программ в императивную форму позволяет формировать эквивалентное представление программы на уровне системы команд и обеспечивает более эффективное ее выполнение на существующих вычислительных системах.
Теоретическая и практическая значимость.
1. На основе предложенных алгоритмов и методов оптимизации ФПП программ и их трансформации в императивную форму разработаны инструментальные средства, интегрированные в существующую систему разработки программ на языке функционально-потокового параллельного программирования Пифагор [105, 106].
2. Результаты работы использовались:
- при выполнении научно-исследовательских работ в рамках федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" по теме "Инструментальная поддержка архитектурно-независимой разработки параллельных программ на основе функционально-потоковой парадигмы параллельного программирования", № 14.A18.21.0396 в 2013-2014гг.;
- при выполнении Грантов РФФИ: № 13-01-00360 "Методы и средства эволюционной разработки программного обеспечения с применением процедурно-параметрической парадигмы программирования", №17-07-00288 "Архитектурно-независимая разработка параллельных программ на основе функционально-потоковой парадигмы" в 2017-2020гг.;
- при подготовке магистров по направлению 09.04.01 - "Информатика и вычислительная техника", при изучении дисциплин "Технологии разработки программного обеспечения", "Параллельное программирование" и при выполнении выпускных квалификационных работ.
Все результаты практического применения диссертационного исследования подтверждены соответствующими актами и свидетельствами о регистрации программного обеспечения и актами о внедрении (Приложение В).
Достоверность полученных результатов подтверждается корректным использованием математического аппарата, работоспособностью разработанного программного обеспечения (ПО), применением разработанного ПО в научной деятельности по развитию представленных методов оптимизации и трансформации программ в учебном процессе.
Рекомендованный список диссертаций по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Использование многоуровневого внутреннего представления в автоматическом распараллеливании программ для многопроцессорных ЭВМ2000 год, кандидат технических наук Лазарева, Светлана Александровна
Методы асинхронного управления функционально-потоковыми параллельными вычислениями2009 год, кандидат технических наук Редькин, Андрей Владимирович
Языковые средства систем программирования, ориентированные на создание переносимых, эволюционно расширяемых параллельных программ2005 год, доктор технических наук Легалов, Александр Иванович
Математическое и алгоритмическое обеспечение создания компиляторов предметно-ориентированных языков для специализированных вычислительных машин2020 год, кандидат наук Советов Петр Николаевич
Исследование и разработка методов выполнения функционально-параллельных программ2004 год, кандидат технических наук Кузьмин, Дмитрий Александрович
Введение диссертации (часть автореферата) на тему «Оптимизация и трансформация функционально-потоковых параллельных программ»
Апробация работы.
Основные положения и результаты исследований докладывались и обсуждались на открытых межкафедральных семинарах ИКИТ СФУ, восьми отраслевых, всероссийских и международных конференциях и семинарах, в том числе: "МНСК-2015: Информационные технологии" (Новосибирск, 2015); "Научный сервис в сети Интернет" (Новороссийск, 2017); "Суперкомпьютерные дни в России" (Москва, 2018).
По теме диссертации опубликовано 24 работы, из которых: 7 статей в изданиях, рекомендуемых ВАК, 2 статьи в журналах базы данных Scopus и 7 свидетельств о государственной регистрации программ для ЭВМ.
Соответствие специальности. По своему научному содержанию диссертационная работа соответствует паспорту специальности 2.3.5 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»: пункту №1 (Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования); пункту № 2 (Языки программирования и системы программирования, семантика программ); пункту № 8 (Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования).
Личный вклад автора. Основные результаты являются новыми и получены лично автором. Вклад автора в научные работы, опубликованные в соавторстве с
научным руководителем, заключается в следующем: анализе особенностей ФПП парадигмы в контексте задачи оптимизации; разработке методов и алгоритмов оптимизации функционально-потоковых параллельных программ; разработке методов и алгоритмов преобразования ФПП программ в императивную форму; создании инструментальных средств трансформации ФПП программ и их интеграции с существующими инструментальными средствами программирования. Все выносимые на защиту результаты принадлежат лично автору.
Совместно с научным руководителем автор осуществлял постановку целей и задач, выбор методов для реализации, анализ полученных результатов.
В совместных публикациях автора с Матковским И.В., Ушаковой (Кропаче-вой) М.С., Савченко Г.В., Постниковым А.И., Непомнящим О.В. изложены теоретические идеи дополнения функционально-потоковой модели вычислений и ее промежуточных представлений, используемых элементами инструментальной среды программирования. Практическим результатом выполненных совместных исследований являются свидетельства о регистрации программ для ЭВМ, в них вклад автора пропорционален вкладу в соответствующие теоретические исследования.
Представление изложенных в диссертации и выносимых на защиту результатов, полученных в совместных исследованиях, согласованно с соавторами.
Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка сокращений и трех приложений. Работа содержит 143 страницы основного текста, 69 рисунков и 6 таблиц. Список использованных источников содержит 120 наименований.
Во введении приводится общая характеристика работы и дается краткий обзор содержания диссертации.
В первом разделе работы приводится обзор методов оптимизации программ и промежуточных представлений программ, используемых инструментами оптимизации. Описываются особенности функционально-потоковой модели параллельных вычислений, имеющие отношение к процессу оптимизации кода,
предложены связанные с этими особенностями, специфические для ФПП языков, методы оптимизации. На основе проведенного анализа сделан вывод о целесообразности использования ряда методов для оптимизации и трансформации ФПП программ.
Второй раздел посвящен разработке алгоритмов оптимизации ФПП программ. Для каждого алгоритма оптимизации кода приведен пример программы, формальное описание выполняемых трансформаций и ожидаемые от их применения результаты.
В третьем разделе описана реализация системы оптимизации кода. Выполнен анализ возможных вариантов представления программ внутри оптимизатора, для каждого из них определены оценки трудоемкости критичных операций, на основании которых выбрано наиболее подходящее представление. Предложена структура оптимизатора, а также примеры и результаты его использования. Реализованы: два метода оптимизации инварианта, один из которых специфичен для ФПП парадигмы; удаление неиспользуемого кода; тНпе-подстановка; оптимизация хвостовой рекурсии; удаление общих подвыражений; эквивалентное преобразование программ на основе функционально-потоковой модели параллельных вычислений; удаление избыточных дуг управляющего графа.
В четвертом разделе проведен анализ проблем трансформации ФПП программ в императивную форму, обоснована необходимость подобных преобразований. Выбраны структуры данных внутреннего представления программы в системе трансформации и подмножество конструкций языка, использование которых допустимо в программах, подаваемых на вход системы. Приведены алгоритмы, используемые в процессе трансформации, а также примеры входных и выходных данных, на которых проводилось тестирование.
В заключении представлены научные и практические результаты, а также возможные пути дальнейших научных исследований.
В приложении А приведены исходные коды ФПП программ, используемые в качестве примеров в основном тексте диссертации, их промежуточные представления. Описаны принципы работы программ.
В приложении Б приведены примеры программ, используемые при тестировании разработанного программного обеспечения.
1 Особенности задачи оптимизации программ
Оптимизация представляет собой процесс эквивалентного преобразования, в результате которого устраняются избыточные вычисления, не влияющие на ход выполнения программы, а следовательно улучшаются требуемые характеристики. На любом языке программирования может быть написана неоптимальная программа, то есть программа, характеристики которой можно улучшить. Часть неоп-тимальностей может быть устранена с помощью автоматизированных программных средств — оптимизаторов [20]. Они выполняют часть рутинной работы за программиста, а значит снижают стоимость разработки.
Ряд исследователей не рекомендует выполнять оптимизацию вручную, особенно на ранних этапах разработки. Мейерс предостерегает от преждевременной оптимизации, в частности Ыте-подстановки [21], Томпсон и Чезарини советуют оптимизировать код только в случаях, когда производительность стала проблемой [22], Роберт Мартин и Мартин Фаулер рекомендуют предпочитать простоту и понятность кода его эффективности, делегировав задачу оптимизации компилятору [23, 24].
В зависимости от источника возникновения все неоптимальности можно условно разделить:
- внесенные программистом;
- созданные семантическим разрывом (во многих языках высокого уровня поддерживается механизм сопоставления с образцом, выполняется автоматическая сборка мусора, отсутствует оператор разрушающего присваивания [25, 26]);
- обусловленные особенностями вычислительной среды (разработка программ чаще всего ведется без учета особенностей вычислительного устройства на котором она будет исполняться).
1.1 Оптимизация программ на разных уровнях организации
вычислительных систем
Методы оптимизации, направленные на устранение неоптимальностей, связанных с особенностями конкретной архитектуры вычислительной системы, являются непереносимыми на другие архитектуры. Ниже приведены подходы к оптимизации программ, работающие на разных уровнях организации вычислительной системы и использующие архитектурные особенности соответствующего уровня.
1.1.1 Использование параллелизма вычислительной системы
За счет использования компонентов вычислительной системы, способных работать параллельно, может быть сокращено время вычислений, то есть программа может быть оптимизирована.
Параллельные системы сильно отличаются друг от друга, поэтому распараллеливание часто выполняется вручную. При этом широко распространены следующие подходы:
- при программировании систем с общей памятью применяются такие библиотеки, как OpenMP или POSIX Threads [1];
- для программирования массивно-параллельных систем используются инструменты типа MPI [2] и PVM [27];
- системы с неоднородным доступом к памяти программируются аналогично SMP-системам, но учитывается, что доступ к локальным данным вычислительного узла осуществляется гораздо быстрее, чем доступ к данным других узлов [28];
- для программирования графических ускорителей применяют OpenCL [3] и CUDA [4];
- отдельные узлы MPP-системы могут обладать внутренним параллелизмом. При этом для передачи сообщений между узлами можно использовать MPI, а для использования параллелизма внутри узла - OpenMP и CUDA. Такая система называется гетерогенной, при ее программировании учитывается, что отдельные вычислительные узлы могут отличаться составом аппаратных средств [29];
- открытая распараллеливающая система может выполнять автоматическое распараллеливание императивных программ для архитектуры с общей памятью [8], распределенной памятью [9] и графических ускорителей [10]. Ее частью является система автоматического распараллеливания ДВОР [30], которая визуализирует информацию о зависимостях в программе и дает советы по оптимизации, однако выбор о применении преобразования остается за программистом. Система AutoPar [11] выполняет автоматическое распараллеливание программ языка Haskell.
1.1.2 Использование более быстрых видов памяти
Память современных вычислительных систем построена по иерархическому принципу. Наиболее быстрые виды памяти имеют небольшой объем, поэтому в них размещают лишь те данные, которые будут многократно использоваться программой в ближайшее время.
Самым быстрым видом памяти являются регистры процессора. Оптимизирующие компиляторы решают задачу оптимального размещения большого количества переменных по маленькому числу регистров, учитывая особенности целевого процессора [31]. Похожая задача стоит и перед JIT-компиляторами [32], но выполняется ими непосредственно во время исполнения программы. Особенно остро проблема оптимального размещения регистров стоит при компиляции программ для суперскалярных процессоров. Для архитектуры VLIW задача распределение регистров является NP-полной [33], в работе [34] предложен алгоритм статического распределения регистров для такой архитектуры. Специфические опти-
мизации, связанные с планированием использования ресурсов для архитектуры УЬШ' рассмотрены в [35].
Многие системы при оптимизации кода позволяют учитывать параметры процессорного кэша. В [36] освещаются различные варианты организации кэша, а также вопросы оптимального, с точки зрения статистики кэш-попаданий, кодирования видео в мобильных приложениях. Показано [37], что для улучшения статистики кэш-попаданий могут применяться такие методы оптимизации как разбиение и объединение циклов.
Выделенная операционной системой для программы область памяти делится на стек и кучу, которые используются программой по-разному. Существует среда автоматизации выбора стратегии размещения пользовательских переменных в статической и стековой памяти [38], которая на основе параметров памяти вычислительной системы переносит часть стековых переменных в статическую область памяти.
1.1.3 Методы оптимизации на физическом уровне архитектуры
Архитектура систем на кристалле сильно отличается от архитектуры уровня системы команд, поэтому отличается и набор применяемых методов оптимизации. Различные ПЛИС отличаются друг от друга набором аппаратных средств, обзор особенностей отдельных систем и соответствующих методов оптимизации приведен в [39, 40]. Для таких систем разрабатываются специфические методы оптимизации, так как дополнительными ограничениями и целями оптимизации могут являться: площадь кристалла [41], число проводников в каналах ПЛИС [42], энергопотребление [43] и другие, не характерные для традиционных архитектур.
Существуют экспериментальные архитектуры процессоров, позволяющие выполнять специфические оптимизации. В частности, архитектуры процессоров с отключаемыми компонентами позволяет оптимизировать энергопотребление [44].
1.1.4 Методы оптимизации на уровне языков программирования
Программы на любом языке программирования могут содержать неоптимальности, не зависящие от архитектуры вычислительной системы. Например, когда программа выполняет вычисление, результат которого не используется, или вычисляет одно и тоже значение дважды. Устранить такие неоптимальности можно переписыванием исходного кода программы, например удалением или перемещением отдельных операторов, однако обычно оптимизация проводится на уровне промежуточного представления, а не исходного кода.
1.1.4.1 Удаление общих подвыражений
Удаление общих подвыражений (Common subexpression elimination) заключается в поиске выражений, выполняющих одинаковые операции над одинаковыми наборами значений [45]. Если в некоторой точке программы доступны результаты вычисления нескольких таких выражений, то одно из них можно оставить, а остальные — удалить. Результат вычисления оставленного выражения должен быть подставлен вместо использования удаленных. Такое преобразование приводит к сокращению времени работы программы, так как получение вычисленного ранее значения из памяти требует меньше времени, чем повторное его вычисление. Кроме того, может сокращаться объем памяти, потребляемый программой, так как часть кода удаляется. В качестве примера рассмотрим код, приведенный в левой части рисунка 1.1, в нем дважды вычисляется значение функции от одного и того же значения аргумента. Если эта функция не имеет побочных эффектов, - то повторный вызов можно устранить, подставив на его место полученный ранее результат. В правой части рисунка приведен оптимизированный на уровне исходного кода вариант.
1. 2.
3.
4.
5.
6. 7.
a = foo(123);
if (condition) {
a = foo(123);
if (condition) {
b = Value + 3;
b = Value + 3;
}
else {
=>
}
else {
b += foo(123);
}
b += a;
}
Рисунок 1.1 - Пример программы с общими подвыражениями
Эффективность метода может быть повышена предварительным применением алгоритма упрощения выражений или нумерации значений (Value Numbering). Нумерация значений - это вид анализа, позволяющий выявить в программе переменные, имеющие одинаковые значения в определенные моменты времени, часто выполняется над программой, представленной в форме статического единственного присваивания - SSA (Static Single Assignment) [45]. Нумерация значений может быть локальной (Local Value Numbering) и глобальной (Global Value Numbering) в зависимости от того выполняется внутри одного базового блока или нескольких. В [46] предлагается улучшенный метод нумерации значений, учитывающий то, что одинаковые значения могут вырабатываться разными операциями.
Константные выражения часто вносятся программистом преднамеренно, с целью улучшения читаемости кода. На рисунке 1.2 приведены две записи одной и той же формулы, выполняющей перевод радиан в градусы, при этом более простой для восприятия, хотя и более медленной, является запись, приведенная в левой части.
1.1.4.2 Распространение и подстановка констант
grad = rad * 180 / 3.14 => grad = rad * 57.3248
Рисунок 1.2 - Фрагмент программы с константным выражением
В результате оптимизации часть вычислений переносится с этапа выполнения программы на этап компиляции, замедляя его, однако, это не всегда целесообразно, в [47, 48] отмечается что в системах динамической оптимизации такое преобразование целесообразно применять только для наиболее часто используемых функций и выражений, находящихся на типичном пути исполнения программы (common path).
В случаях, когда константа используется в качестве аргумента функции возможна генерация отдельной версии функции, где все использования этого аргумента заменены на соответствующую константу. Такое преобразование называется распространением констант (constant propagation) и повышает эффективность других преобразований — например, удаления кода, недоступного по управлению или свертки констант [49]. При подстановке констант в функции возможно увеличение размера исполняемого файла, что также может приводить к ухудшению других критериев качества программы.
Оптимизация сверткой констант (constant folding) заключается в замене выражений (или их частей), обрабатывающих константы результатом их выполнения. Реализовано такое преобразование например в компиляторе gcc [50]. Свертка констант является архитектурно зависимым преобразованием, если разрядность обрабатываемых чисел зависит от платформы.
1.1.4.3 Снижение стоимости операций
Снижение стоимости операций (strength reduction) заключается в замене операций программы на более простые (быстрые). Такие преобразования чаще всего используются на уровне машинной архитектуры, они могут также применяться и на уровне языков программирования. Преобразование можно проводить над любым представлением потоков данных программы, однако необходимо иметь информацию о целевой платформе, так как на различных архитектурах операции могут иметь разную трудоемкость. Например умножение и деление на 2 мо-
жет заменяться сложением или сдвигом, возведение в квадрат — умножением
[51].
В работе [52] отмечается возможность применения преобразования к индуктивным переменным цикла. В качестве примера рассмотрим рисунок 1.3, на нем слева приведен фрагмент кода, выполняющий увеличение всех элементов массива на единицу, а справа эквивалентный оптимизированный код.
float *a; float *a;
float *end = a+n; for (int i = 0; i < n; ++i) for (*p = a; p < end; ++p)
a[i] = a[i] + 1; => *p = (*p) + 1;
Рисунок 1.3 - Пример оптимизации стоимости операций
В данном случае оптимизация заключается в замене операции доступа к элементу массива по индексу на адресную арифметику. Преобразование возможно, потому что элементы массива перебираются последовательно и для получения следующего элемента достаточно увеличить адрес предыдущего, в то время как доступ к элементу по индексу сводится к выполнению одного сложения и умножения.
1.1.4.4 Удаление неиспользуемого кода
Неиспользуемый код (dead code, "мертвый" код) представляет собой группу операторов программы, выполнение которых не влияет на результат работы. Также, к нему относят код, недостижимый по управлению, то есть такой, выполнение которого не начнется ни при каких условиях. Такой вид преобразования сокращает общий объем кода, а значит и требуемый для программы объем памяти.
На рисунке 1.4 приведен пример оптимизации неиспользуемого кода. При этом операции выделения памяти и присваивания переменной unused_variable значения являются неиспользуемым кодом, так как в дальнейшем к этой переменной не выполняются обращения. Условие 1 всегда ложно, так как квадрат числа не
может быть меньше нуля, а условие 2 ложно, так как число не может быть одновременно меньше нуля и больше 10.
int dead_code(int x) { int unused_variable = 1; if (x * x < 0) { // Условие return x+1;
}
if (x < 0) {
int dead_code(int x) {
1
=> if (x < 0) {
if (x > 10) { // Условие 2 return 1;
return -x; }
}
return 1;
}
return 0; return 0;
} }
Рисунок 1.4 - Пример оптимизации неиспользуемого кода
Для удаление неиспользуемого кода может применяться любая форма представления потоков данных программы, при этом производится обход графа в направлении противоположном движению данных, начиная с конечной вершины. Все вершины, в которые не существует пути из конечной, являются неиспользуемым кодом.
Для удаления кода, недоступного по управлению, дополнительно нужна информация о значениях переменных в разных частях программы и диапазонах их допустимых значений. Поэтому такое преобразование зачастую проводится над представлением программы в форме SSA [53]. В ШУМ, помимо такого варианта, используется агрессивное удаление неиспользуемого кода, при этом на этапе анализа полагается, что код является неиспользуемым если не доказано обратное [54].
1.1.4.5 Подстановка тела функции вместо вызова
Подстановка функции вместо ее вызова (тНпе-подстановка) относится к классу межпроцедурных методов оптимизации и заключается в замене вызова
функции ее телом. В результате преобразования устраняется трудоемкая операция вызова функции, выполнение которой сопряжено с необходимостью сохранения локальных параметров в стеке, а затем их восстановления. Преобразование позволяет сократить время выполнения программы, в некоторых случаях inline-подста-новка может улучшить качество других оптимизаций, например удаление общих подвыражений. Однако, тело подставляемой функции многократно копируется, значит растет размер программы, в связи с этим оптимизация проводится только для маленьких функций, при этом желательно, чтобы вызов функции находился внутри цикла. Подставляемая функция не должна иметь побочных эффектов или являться рекурсивной.
К.Д. Купер сравнивал реализации подстановки функции в различных компиляторах и для различных архитектур, исследовал взаимодействие inline-подста-новки и других методов оптимизации [55]. А.Н. Филиппов отмечает, что при оценке эффекта, получаемого подстановкой функции, нужно учитывать возможность применения других методов оптимизации. В частности, после inline-подста-новки может более эффективно производиться сбор общих подвыражений [46].
1.1.4.6 Оптимизация хвостовых вызова и рекурсии
Вызов функции помимо передачи управления выполняет ряд операций со стеком. Вызов функции называется хвостовым, если его результаты передаются на выход функции без изменения. Такой вызов может быть заменен длинным переходом (long jump), соответствующее преобразование называется оптимизацией хвостового вызова (tail-call elimination^ и позволяет сократить время выполнения программы.
В примере, приведенном на рисунке 1.5, все три вызова функции являются хвостовыми, так как их результаты не обрабатываются, поэтому они могут быть заменены длинным переходом.
1. d = b*b - 4*a*c;
2. if (d < 0)
3. return no_roots();
4. else if (d = 0)
5. return one_roots(a, b);
6. else
7. return two_roots(a, b, c);
Рисунок 1.5 - Пример фрагмента программы на С++ с хвостовыми вызовами
В работе [56] описывается реализация оптимизации хвостового вызова для функционального языка Funnel, транслируемого в байткод виртуальной машины Java (JVM). Отмечаются проблемы, связанные с отсутствием поддержки такой оптимизации непосредственно в JVM, хотя ряд реализаций JVM поддерживает оптимизацию хвостовой рекурсии.
Если хвостовой вызов функции является рекурсивным, то он может быть заменен не длинным переходом, а циклом. Такое преобразование называется оптимизацией хвостовой рекурсии (tail-recursion elimination) и дает такой же результат, что и оптимизация хвостового вызова, однако явное выделение циклической конструкции в ряде случаев упрощает применение дополнительных оптимизаций. Замена рекурсии циклом является обязательной в большинстве функциональных и логических языков программирования, так как в них отсутствует возможность явного задания циклов [57].
1.1.4.7 Вынос инварианта за тело цикла
Вычисление называется инвариантом цикла (loop-invariant computation), если на каждой итерации цикла дает одинаковый результат. При оптимизации такие вычисления выносятся из тела цикла и размещаются перед ним, за счет этого сокращается объем вычислений [20]. На рисунке 1.6 приведен пример выполнения такого преобразования. До оптимизации многократно, на каждой итерации цикла, выполнялись вычисления над переменным n и p, но так как значения этих переменных внутри цикла не изменяются, то результаты вычислений будут одинаковы.
i. 2.
3.
4.
5.
6. 7.
int s = 0; int i = 0;
while (i < n-2) { s += p*3; ++i;
=>
int s = 0; int i = 0; int inv_n = n-2; int inv_p = p*3; while (i < inv_n) { s += inv_p; ++i;
8. } }
Рисунок 1.6 - Фрагмент программы с инвариантом цикла и его оптимизация (пример 1)
В работе [58] рассматривается вынос инварианта из цикла для функционального языка Sisal в системе SFP, при этом рекомендуется производить это преобразование перед сбором общих подвыражений.
В некоторых случаях инвариантом называется нерекуррентный оператор присваивания, левая часть которого не зависит от счетчика цикла и не содержит вызовов функций [59]. Если другие операторы в цикле не зависят от инварианта, то он может быть вынесен из цикла, при этом необходимо заменить счетчик цикла на его конечное значение. Пример выполнения такого преобразования приведен на рисунке 1.7. В этом случае на каждой итерации цикла переменной d присваивается новое значение, зависящее от счетчика цикла, однако отсутствуют зависимости между переменной d и другими переменными, изменяемыми в цикле. Конечное значение переменной d будет сформировано последней итерацией, поэтому вычисление можно вынести за тело цикла, как показано в правой части рисунка.
for(int i = 0; i < 100; ++i) { for(int i = 0; i < 100; ++i) {
d = x[i]*2; => y[i] = x[i];
y[i] = x[i]; }
} d = x[99] * 2;
Рисунок 1.7 - Фрагмент программы с инвариантом цикла и его оптимизация (пример 2)
Выполнение такого преобразования осложняется, если итерации цикла могут быть завершены досрочно (используются конструкции типа break и continue). Перед оптимизацией может выполняться разрезание цикла на максимальное количество частей, а после оптимизации - объединение циклов.
1.1.4.8 Замена индуктивных переменных цикла
Индуктивными называются переменные, изменяющиеся в каждой итерации, являясь функцией счетчика цикла. В ряде случаев удается установить закон по которому они изменяются и изменить функцию таким образом, чтобы убрать зависимость от счетчика. Такая замена называется оптимизацией переменных индукции (induction variable substitution), часто ведет к снижению стоимости операций и улучшению параллелизма [60].
Похожие диссертационные работы по специальности «Другие cпециальности», 00.00.00 шифр ВАК
Разработка методов выполнения функционально-параллельных программ на основе сетей Петри2005 год, кандидат физико-математических наук Калиниченко, Борис Олегович
Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система2004 год, доктор технических наук Штейнберг, Борис Яковлевич
Исследование и реализация непроцедурных преобразований программ для построения расширяемой системы распараллеливания2007 год, кандидат технических наук Жегуло, Ольга Анатольевна
Программные методы повышения производительности архитектуры picoJava-II2002 год, кандидат технических наук Лунев, Сергей Александрович
Методы удаления избыточностей на этапе компиляции программ2009 год, кандидат технических наук Филиппов, Александр Николаевич
Список литературы диссертационного исследования кандидат наук Васильев Владимир Сергеевич, 2023 год
Список литературы
1. The OpenMP API specification for parallel programming. OpenMP Home. - Режим доступа: https://www.openmp.org/
2. High-Performance Portable MPI. MPICH. - Режим доступа: https:// www.mpich.org/
3. Open Standard for Parallel Programming of Heterogeneous Systems. OpenCL Overview - The Khronos Group Inc. - Режим доступа: https:// www.khronos.org/opencl/
4. CUDA Zone. NVIDIA Developer. - Режим доступа: https:// developer.nvidia.com/cuda-zone
5. Saa-Garriga, A. OMP2MPI: Automatic MPI code generation from OpenMP programs / A. Saa-Garriga, D. Castells-Rufas, J. Carrabina // High Performance Energy Efficient Embedded Systems (HIP3ES) Workshop. - arXiv preprint, 2015.
6. Saa-Garriga, A. OMP2HMPP: Compiler Framework for Energy Performance Trade-off Analysis of Automatically Generated Codes / A. Saa-Garriga, D. Castells-Rufas, J. Carrabina // IJCSI International Journal of Computer Science Issues. -2015. - Vol. 12. - P. 9-21.
7. Ishizaki, K. Compiling and Optimizing Java 8 Programs for GPU Execution / K. Ishizaki, A. Hayashi, G. Koblents, V. Sarkar // International Conference on Parallel Architecture and Compilation (PACT). - 2015, P. 419-431.
8. Штейнберг, Б. Я. Распараллеливание программ для суперкомпьютеров с параллельной памятью и Открытая распараллеливающая система: дис. ...д-р. техн. наук: 05.13.11. / Б.Я. Штейнберг - Ростов н/Д, 2004. - 343 с.
9. Кравченко, Е.Н. Автоматическая генерация MPI-кода с размещением данных в диалоговом высокоуровневом автоматическом распараллеливателе / Е.Н. Кравченко // Современные проблемы математического моделирования. - 2011. - С. 193-197
10. Аллазов, А.Н. Автоматическая генерация GPU -кода в диалоговом высокоуровневом оптимизирующем распараллеливателе / А.Н. Аллазов, С.А. Гуда, Р.И. Морылев // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки .— 2015 .— №3 .— С. 6-12.
11. Dever, M. AutoPar: automating the parallelization of functional programs: Thesis for the Degree of Doctor of Philosophy / M. Dever. - Dublin City University, 2015. - 210 p.
12. Воеводин, В. В. Вычислительная математика и структура алгоритмов / В.В. Воеводин. - М.: МГУ, 2006. - 112 с.
13. Легалов, А.И. Функциональная модель параллельных вычислений и соответствующий ей язык программирования / А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин // Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98). - Новосибирск: Институт математики СО РАН, 1998. - С. 8586.
14. Легалов, А.И. Модель функционально-потоковых вычислений и язык программирования "Пифагор" / А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин, Д.В. Привалихин // 2-ая школа семинар. Распределенные и кластерные вычисления. - Красноярск, 2002. - C. 101-120.
15. Легалов, А. И. Функциональный язык для создания архитектурно-независимых параллельных программ / А.И. Легалов // Вычислительные технологии. — 2005. — Т. 10. — № 1. — С. 71-89.
16. Деннис, Д. Б. Схемы потока данных / Д. Б. Деннис, Д. Б. Фоссин, Д. П. Линдерман // Теория программирования. - 1972. - Т. 2. - С. 7-43.
17. Легалов, А.И. Построение параллельных алгоритмов / А.И. Легалов // Открытые системы. - 2004. - № 9. - С. 64-68.
18. Ушакова, М.С. Свидетельство о государственной регистрации программы для ЭВМ № 2021663755 Российская Федерация. Инструментальное средство для формальной верификации функционально-потоковых параллельных программ на языке Пифагор на основе исчисления Хоара / Ушакова М.С.; заявитель и
правообладатель Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет" (СФУ). — № 2021662716; заявл. 09.08.2021; опубл. 23.08.2021. — 1 с.
19. Удалова, Ю.В. Отладка и верификация функционально-потоковых параллельных программ: дис. ... канд. техн. наук: 05.13.11: защищена 21.05.15 / Ю.В. Удалова — Красноярск, 2015. — 170 с.
20. Ахо, А.В. Компиляторы: принципы, технологии и инструментарий, 2-е изд.: Пер.с англ. / А.В. Ахо, М.С. Лам, Р. Сети, Д.Д. Ульман - М.: Вильямс, 2008. -1184 с.
21. Мейерс, С. Эффективное использование С++. 55 верных способов улучшить структуру и код ваших программ / С. Мейерс — М.: ДМК Пресс, 2006. — 300с.
22. Томпсон, С. Программирование в Erlang / C. Томпсон, Ф. Чезарини. — М.: ДМК Пресс, 2012. — 488с.
23. Мартин, Р. Чистый код. Создание, анализ и рефакторинг. Библиотека программиста / Р. Мартин - СПб.: Питер, 2014. - 464 с.
24. Фаулер, М. Рефакторинг: улучшение существующего кода / М. Фаулер СПб.: Символ-Плюс, 2003. 432 c.
25. Bevemyr, D. J. Simple and ecient copying garbage collection for Prolog, in Programming Language Implementation and Logic Programming / D. J. Bevemyr, T. Lindgren // International Symposium on Programming Language Implementation and Logic Programming - Berlin: Springer, 1994. - С. 88-101.
26. Zhang, C. Research on Algorithm of Parallel Garbage Collection Based on LISP 2 for Multi-core System / C. Zhang, C. Wu, L. Zhao // International Conference on Intelligent Computing - Berlin: Springer, 2010. - С. 469-476.
27. PVM - Parallel Virtual Machine. PVM. - Режим доступа: https:// www.csm .ornl .gov/ pvm/
28. Hollowell, C. The effect of numa tunings on cpu performance / C. Hollowell, C. Caramarcu, W. Strecker-Kellogg, A. Wong, A. Zaytsev //Journal of Physics: Conference Series - IOP Publishing, 2015. - Т. 664. - № 9. - С.1-8.
29. Kale, V. Parallel Computing Architectures and APIs. IoT Big Data Stream Processing. / V. Kale // Parallel Computing Architectures and APIs - Chapman and Hall, 2019. - С. 181-212.
30. Штейнберг, Б.Я. Особенности реализации распараллеливающих преобразований программ в ДВОР / Б.Я. Штейнберг, Е.Н. Кравченко, Р.И. Моры-лев, З.Я. Нис, В.В. Петренко, И.С. Скиба, В.Н. Шаповалов, О.Б. Штейнберг, Р.Б. Штейнберг // Известия высших учебных заведений. Приборостроение. - 2011. - Т. 54. - № 10. - С. 87-89.
31. Караваев, Д.Ю. О реализации метода распределения регистров при компиляции / Д.Ю. Караваев // RSDN MAGAZINE. - 2012. - № 1. - С. 21-28.
32. Батузов, К.А. Задача локального распределения регистров во время динамической двоичной трансляции / К.А. Батузов // Труды ИСП РАН. - 2012. - № 22 - С. 67-74.
33. Мурашитин, Б. К вопросу о кодогенерации для архитектур с ILP / Б. Мурашитин, А. Артюшин // SoftCraft разноликое программирование. - 2005, -Режим доступа: www.softcraft.ru/parallel/vliw/vliw.pdf
34. Иванов, Д.С. Распределение регистров при планировании инструкций для VLIW-архитектур / Д.С. Иванов // Программирование. - 2010. - № 6. - С. 74-80.
35. Chen, W. Using profile information to assist advanced compiler optimization and scheduling / W. Chen, R. Bringmann, S. Mahlke, S. Anik, T. Kiyohara, N. Warter, D. Lavery, W. M. Hwu, R. Hank, J. Gyllenhaal // International Workshop on Languages and Compilers for Parallel Computing - Berlin: Springer. - 1992. - С. 31-48.
36. Asaduzzaman, A. Cache optimization for mobile devices running multimedia applications / A. Asaduzzaman, I. Mahgoub, P. Sanigepalli, H. Kalva, R. Shankar, B. Furht // IEEE Sixth International Symposium on Multimedia Software Engineering -Miami. - 2004. - C. 499-506.
37. Серебрянский, А.И. Обзор распараллеливающих компиляторов / А.И. Серебрянский, Г.А. Сыч // Системное программирование. - 2008. - № 3. - С. 157177.
38. Томаев, М.Х. Средства автоматизации оптимизационных преобразований исходных кодов программных систем / М.Х. Томаев // Программные продукты, системы и алгоритмы. - 2018. - №3. - С. 19-29.
39. Александровская, А.А. Оптимизации кода при использовании средств высокоуровнего синтеза на ПЛИС Altera / А.А. Александровская // Вопросы науки и образования. - 2019. - № 15. - С. 53-58.
40. Алымова, Е.В. О промежуточном представлении программ для автоматического создания конвейерных вычислителей / Е.В. Алымова, А.П. Баглий, Д.В. Дубров, Р.А. Ибрагимов, Ю.В. Михайлуц, В.В. Петренко, Б.Я. Штейнберг, Р.Б. Штейнберг, В.А. Яковлев // Известия вузов. Северо-Кавказский регион. Серия: Технические науки. - 2017. - № 3. - С. 22-28.
41. Баркалов, А.А. Оптимизация схемы автомата Мура в составе системы на кристалле / А.А. Баркалов, С.А. Цоцоло // Радиоэлектроника и информатика. -2007. - № 1. - С. 35-39.
42. Курганский, С. И. Оптимизация емкости трассировочных каналов программируемых логических интегральных схем / С.И. Курганский, Д.В. Матюшин, С.Н. Скуратович // Вестник Воронежского государственного технического университета. - 2011. - Т. 7. - № 7. - С. 80-82.
43. Соловьев, В.В. Методы проектирования на ПЛИС быстродействующих устройств управления с малым энергопотреблением / В.В. Соловьев // Проблемы инфокоммуникаций. - 2016. - № 1. - C. 53-59.
44. Каретин, И. И. Энергосберегающая оптимизация кода за счет использования отключаемых компонентов процессора / И.И. Каретин, В.А. Макаров // Труды Института системного программирования РАН. - 2010. - Т. 19. - С. 187194.
45. Rosen, B.K. Global value numbers and redundant computations / B.K. Rosen, M.N. Wegman, F.K. Zadeck // Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. - 1988. - С. 12-27.
46. Филиппов, А. Н. Метод нумерации значений и использование его результатов при оптимизации программ / А.Н. Филипов // Информационные технологии. - 2009. - № 4. - С. 43-49.
47. Чилингарова, С. А. Методы оптимизации для динамических (just-in-time) компиляторов / С.А. Чилингарова // Компьютерные инструменты в образовании. - 2006. - № 2.
48. Жуйков, Р. Методы предварительной оптимизации программ на языке JavaScript / Р. Жуйков, Е. Шарыгин // Труды Института системного программирования РАН. - 2015. - Т. 27. - № 6. - С. 67-86.
49. Идрисов, Р. И. Методы межпроцедурного анализа / Р.И. Идрисов // Методы и инструменты конструирования программ. - 2007. - С. 38-55.
50. Options That Control Optimization. The GNU Compiler Collection. - Режим до ступа: http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
51. Cooper, K. D. Operator strength reduction / K.D. Cooper, L.T. Simpson, C.A. Vick // ACM Transactions on Programming Languages and Systems (TOPLAS). -2001. - Т. 23. - № 5. - С. 603-625.
52. Битнер, В.А. Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов / В.А, Битнер, Н.В. Заборовский // Моделирование и анализ информационных систем. -2013. - № 20. - С. 166-177.
53. Karer, H.H. Dead code elimination technique in eclipse compiler for Java / H. H. Karer, P. B. Soni // 2015 International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT). - IEEE, 2015. - С. 275-278.
54. LLVM's Analysis and Transform Passes. LLVM documentation. - Режим доступа: https://llvm.org/docs/Passes.html
55. Cooper, K. D. An experiment with inline substitution / K.D. Cooper, M.W. Hall, L. Torczon // Software: Practice and Experience. - 1991. - Т. 21. - № 6. - С. 581601.
56. Schinz, M. Tail call elimination on the Java Virtual Machine / M. Schinz, M. Odersky // Electronic Notes in Theoretical Computer Science. - 2001. - № 59. - С. 158-171.
57. Jones, R. Tail recursion without space leaks / R. Jones // Journal of Functional Programming. - 1992. - Т. 2. - № 1. - С. 73-79.
58. Дортман, П. А. Подходы к оптимизации программ в системе SFP. / П. А. Дортман // Программные средства и математические основы информатики. Новосибирск. - 2004. - С. 43-49.
59. Серебряный, К. С. Методы высокоуровневой оптимизации циклов : дис. ... канд. техн. наук: 05.13.11 / К.С. Серебряный — Москва, 2004. — 91 с.
60. Gerlek, M. P. Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form / M.P. Gerlek, E. Stoltz, M. Wolfe // ACM Transactions on Programming Languages and Systems (TOPLAS). - 1995. - Т. 17. - № 1. - С. 85-122.
61. Click, C. A simple graph-based intermediate representation / C. Click, M. Paleczny // ACM Sigplan Notices. - 1995. - Т. 30. - №. 3. - С. 35-49.
62. Рыбаков, А. А. Анализ алгоритмов оптимизации расположения в памяти линейных участков программы / А.А. Рыбаков // Известия высших учебных заведений. Электроника. - 2013. - №. 1 (99). - С. 47-52.
63. Pingali, K. Dependence flow graphs: An algebraic approach to program dependencies / K. Pingali, M. Beck, R. Johnson, M. Moudgill, P. Stodghill // Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. - 1991. - С. 67-78.
64. Дроздов, А. Ю. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ / А.Ю. Дроздов, С.В. Новиков, А.С. Боханко, А.Б. Галазин // Высокопроизводительные вычислительные
системы и микропроцессоры: сборник трудов ИМВС РАН. - 2005. - № 8. - С. 7887.
65. Heffernan, M. Data-dependency graph transformations for instruction scheduling / M. Heffernan, K. Wilken //Journal of Scheduling - 2005. - Т. 8. - №. 5. -С. 427-451.
66. Stoltz, E. Extended SSA with factored use-def chains to support optimization and parallelism / E. Stoltz, M.P. Gerlek, M. Wolfe // Proceedings of the Twenty-Seventh Hawaii International Conference on System Sciences - 1994. - С. 43-53.
67. Ferrante, J. The program dependence graph and its use in optimization / J. Ferrante, K.J. Ottenstein, J.D. Warren // ACM Transactions on Programming Languages and Systems (TOPLAS). - 1987. - Т. 9. - №. 3. - С. 319-349.
68. Static Single Assignment Book. - Режим доступа: ssabook.gforge.inria.fr/ latest/book.pdf
69. Cytron, R. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph / R. Cytron, J. Ferrante, B. Rosen, M. Wegman, K. Zadeck // ACM Transactions on Programming Languages and Systems (TOPLAS). -1991. - Т. 13. - № 4. - С. 451-490.
70. Касьянов, В. Н. Slicing: Срезы программ и их использование / В. Н. Касьянов, И. Л. Мирзуитова. — Новосибирск: Сибирское отделение РАН, 2002.— 116 c.
71. Johnson, N.P. Fast Condensation of the Program Dependence Graph / N.P. Johnson, O. Taewook, A. Zaks, D.I. August // Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. - 2013. - С. 39-50.
72. Lee, B. Correcting the dynamic call graph using control-flow constraints / B. Lee, K. Resnick M. D. Bond, K. S. McKinley // International Conference on Compiler Construction. - Springer, Berlin, Heidelberg, 2007. - С. 80-95.
73. Saito, H. The Design of the PROMIS Compiler / H. Saito, N. Stavrakos, S. Carrol, C. D. Polychronopoulos, A.Nicolau // International Conference on Compiler Construction. - 1999. - С. 214-228.
74. Introduction to the Clang AST. Clang 13 documentation. - Режим доступа: https://clang.llvm.org/docs/IntroductionToTheClangAST.html
75. Дубров, Д. В. Интеграция компилятора clang со сторонней библиотекой оптимизирующих преобразований / Д.В. Дубров, А.Е. Патерикин // Языки программирования и компиляторы. - 2017. - С. 105-109.
76. Штейнберг, Б.Я. Преобразования программ - фундаментальная основа создания оптимизирующих распараллеливающих компиляторов / Б.Я. Штейнберг, О.Б. Штейнберг // Программные системы: теория и приложения. - 2021. - Т. 12. -№ 1. - С. 21-113.
77. Вьюкова, Н. И. Адаптивная компиляция на основе данных профилирования / Н.И. Вьюкова, В.А. Галатенко, А.С. Малиновский, Н.В. Шмырев // Программные продукты и системы. - 2007. - № 3. - С. 5-9.
78. Wintermeyer, P. P2GO: P4 profile-guided optimizations / P. Wintermeyer, M. Apostolaki, A. Dietmuller, L. Vanbever // Proceedings of the 19th ACM Workshop on Hot Topics in Networks. - 2020. - С. 146-152.
79. PGO: уход и кормление. C++ User Group. - Режим доступа: https:// www.youtube.com/watch?v=YCthpT3cF1U
80. Gal, A. Trace-based just-in-time type specialization for dynamic languages / A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Reitmaier, M. Bebenita, M. Chang, M. Franz //ACM Sigplan Notices. - 2009. - Т. 44. - №. 6. - С. 465-478.
81. Ngen. Native Image Generator. Microsoft Docs. - Режим доступа: http:// msdn.microsoft.com/en-us/library/6t9t5wcf.aspx
82. Аветисян, А. И. Динамическое профилирование программы для системы LLVM / А.И. Аветисян, К.Ю. Долгорукова, Ш.Ф. Курмангалеев // Труды Института системного программирования РАН. - 2011. - Т. 21. - С. 71-82.
83. Курмангалеев, Ш. Ф. Методы оптимизации приложений распространяемых в биткоде LLVM с учетом специфики оборудования / Ш.Ф. Кур-
мангалеев // Труды Института системного программирования РАН. - 2013. - Т. 24.
- С. 127-144.
84. LLVM Overview. The LLVM Compiler Infrastructure. - Режим доступа: https://llvm.org
85. Kasyanov, V. Sisal 3.2: functional language for scientific parallel programming / V. Kasyanov // Enterprise Information Systems. - 2013. - Т. 7. - № 2. -С. 227-236.
86. Дордопуло, А.И. Ресурсонезависимое программирование гибридных реконфигурируемых вычислительных систем / А.И. Дордопуло, И.И. Левин // Суперкомпьютерные дни в России. - 2017. - С. 714-723.
87. Левин, И. И. Подход к архитектурно-независимому программированию вычислительных систем на основе аспектно-ориентированного языка Set@l / И.И. Левин, А.И. Дордопуло, И.В. Писаренко, А.К. Мельников // Известия Южного федерального университета. Технические науки. - 2018. - № 3. - С. 46-58.
88. Легалов, А.И. Динамически изменяющийся параллелизм с асинхронно-последовательными потоками данных / А.И. Легалов, И.В. Матковский, М.С. Ушакова, Д.С. Романова // Моделирование и анализ информационных систем. — 2020. — Т. 27, № 2. — С. 164- 179. — Перевод изд.: Dynamically Changing Parallelism with Asynchronous Sequential Data Flows / A.I. Legalov, I.V. Matkovskii, M.S. Ushakova, D.S. Romanova // Automatic Control and Computer Sciences. — 2021.
— Vol. 55, № 7. — P. 636-646.
89. Легалов, А.И. Свидетельство о государственной регистрации программы для ЭВМ № 2013611618 Российская Федерация. Модуль формирования реверсивного информационного графа / А.И. Легалов, О.В. Непомнящий, Н.Ю. Сироти-нина, И.В. Матковский; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Сибирский федеральный университет" (СФУ). — № 2012660518; заявл. 03.12.2012; опубл 29.01.2013. — 1 с.
90. Легалов, А. И.Особенности хранения функционально-потоковых параллельных программ / А.И. Легалов, И.В. Матковский, А.В. Анкудинов // Сибирский журнал науки и технологий. - 2013. - № 4. - С. 53-57.
91. Ушакова, М.С. Инструментальная поддержка формальной верификации программ, написанных на языке функционально-потокового параллельного программирования / М.С. Ушакова, А.И. Легалов // Вестник Южно-Уральского государственного университета. Серия Вычислительная математика и информатика. — 2015. — Т. 4, № 2. — С. 58-68.
92. Непомнящий, О.В. Метод архитектурно-независимого высокоуровневого синтеза СБИС / О.В. Непомнящий, И.Н. Рыженко, А.И. Легалов // Известия ЮФУ. Технические науки. — 2018. — № 8 (202). — С. 38-47.
93. Непомнящий, О.В. Свидетельство о государственной регистрации программы для ЭВМ RU 2021611582 Российская Федерация. Транслятор архитектурно-независимого описания автоматных и комбинационных схем / О. В. Непомнящий, Д. С. Романова, И. Н. Рыженко, А. И. Легалов; заявитель Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет" (СФУ).; опубл. 01.02.2021. — 1 с.
94. Матковский, И. В. Инструментальная поддержка трансляции и выполнения функционально-потоковых параллельных программ / И.В. Матковский,
A.И. Легалов // Ползуновский вестник. - 2013. - № 2. - С. 49-52.
95. Легалов, А. И. Об управлении вычислениями в параллельных системах и языках программирования / А.И. Легалов // Научный вестник Новосибирского государственного технического университета. - 2004. - № 3. - С. 57-66.
96. Штейнберг, Б. Я. Преобразования программ для открытой распараллеливающей системы / Б.Я. Штейнберг, Д.Н. Черданцев, С.А. Науменко, А.Э. Бутов,
B.В. Петренко // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ - 2003. - № 4. - С. 97.
97. Booshehri, M. An improving method for loop unrolling / M. Booshehri, A. Malekpour, P. Luksch //International Journal of Computer Science and Information Security. - 2013. - Т. 11, № 5, C. 73-76.
98. Mahlke, S. A. The Effect of Compiler Optimizations on Available Parallelism in Scalar Programs / S.A. Mahlke, N.J. Warter, W.Y. Chen, P.P. Chang, W.H. Wen-mei // Proceedings of the 20th Annual International Conference on Parallel Processing. - 1991. - С. 142-145.
99. Баканов, В.М. Программный инструментарий анализа информационной структуры алгоритмов по их информационным графам / В.М. Баканов // Параллельные вычислительные технологии (ПаВТ'2016). - 2016. - С. 432-441.
100. Кропачева, М.С. Формальная верификация параллельных программ / М.С. Кропачева // Труды XII Международной научной конференции "Интеллект и наука". — Красноярск: Центр информатизации, 2012. — С. 130-131.
101. Gabriel, R. P. Performance of Lisp systems / R.P. Gabriel, L.M. Masinter // Proceedings of the 1982 ACM symposium on LISP and functional programming. -1982. - С. 123-142.
102. Ушакова, М.С. Семантика типов данных функционально-потокового языка параллельного программирования Пифагор / М.С. Ушакова // Образовательные ресурсы и технологии. — 2016. — № 2 (14). — C. 263-269.
Список публикаций по теме диссертации
103. Матковский, И.В. Cвидетельство о государственной регистрации программы для ЭВМ 2018666577 Российская Федерация. Программа для трансляции функциональнопотокового языка параллельного программирования / И.В. Матковский, А.И. Легалов, В.С. Васильев, А.И. Постников; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение выс-
шего образования "Сибирский федеральный университет" (СФУ). — № 2018663780; заявл. 03.12.2018; опубл. 18.12.2018г. — 1 с.
104. Матковский, И.В. Свидетельство о государственной регистрации программы для ЭВМ 2018666239 Российская Федерация. Программа для интерпретации функционально-потокового языка параллельного программирования / И.В. Матковский, А.И. Легалов, В.С. Васильев, О.В. Непомнящий; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет" (СФУ). — № 2018663794; заявл. 03.12.2018; опубл. 13.12.2018г. — 1 с.
105. Legalov, A.I. A Toolkit For The Development Of Data-Driven Functional Parallel Programmes / A.I. Legalov, V.S. Vasilyev, I.V. Matkovskii, M.S. Ushakova // Communications in Computer and Information Science. — 2018. — Vol. 910. — P. 1630
106. Легалов, А.И. Инструментальная поддержка создания и трансформации функционально-потоковых параллельных программ / А.И. Легалов, В.С. Васильев, И.В. Матковский, М.С. Ушакова // Труды Института системного программирования РАН. — 2017. — Т. 29, № 5. — С. 165-184.
107. Матковский, И.В. Свидетельство о государственной регистрации программы для ЭВМ RU 2018666240 Российская Федерация. Программа для формирования управляющего графа для функционально-потокового языка параллельного программирования / И. В. Матковский, А. И. Легалов, В. С. Васильев, О. В. Непомнящий; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет" (СФУ); опубл 13.12.2018. — 1 с.
108. Легалов, А.И. Изменение стратегий управления вычислениями при архитектурно-независимом параллельном программировании / А.И. Легалов, В.С. Васильев, И.В. Матковский // Научный сервис в сети Интернет: труды XIX Всероссийской научной конференции. - М.: ИПМ им. М.В.Келдыша, 2017. с. 341-351.
109. Легалов, А.И. Событийная модель вычислений, поддерживающая выполнение функционально-потоковых параллельных программ / А.И. Легалов, Г.В. Савченко, В.С. Васильев // Системы. Методы. Технологии. — 2012. — № 1 (13). — С. 113-119.
110. Васильев, В.С. Свидетельство о государственной регистрации программы для ЭВМ 2018666434 Российская Федерация. Программа для оптимизации функционально-потокового языка параллельного программирования / В. С. Васильев, А. И. Легалов, И. В. Матковский, О. В. Непомнящий; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего образования "Сибирский федеральный университет" (СФУ). — № 2018663789; заявл. 03.12.2018; опубл. 17.12.2018г. — 1 с.
111. Легалов, А.И. Свидетельство о государственной регистрации программы для ЭВМ № 2013611617 Российская Федерация. Модуль формирования графического представления реверсивного информационного графа / А.И. Лега-лов, О.В. Непомнящий, В.С. Васильев, И.В. Матковский; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Сибирский федеральный университет" (СФУ). — № 2012660517; заявл. 03.12.2012; опубл. 29.01.2013г. — 1 с.
112. Васильев, В.С. Оптимизирующие преобразования программ языка "Пифагор" / В.С. Васильев // Перспективы развития информационных технологий: сборник материалов VII Международной научно-практической конференции. -2012. С.13-24.
113. Васильев, В. С. Оптимизация программ функционально-потокового языка Пифагор / В.С. Васильев // Перспективы развития информационных технологий: сборник материалов XX Международной научно-практической конференции. - Новосибирск. - 2014. С. 7-14.
114. Васильев, В. С. Оптимизация инварианта цикла в языке Пифагор / В.С. Васильев, А.И. Легалов // Моделирование и анализ информационных систем. - 2018. - Т. 25. - № 4. - С. 347-357.
115. Vasilev, V.S. Loop-invariant Optimization in the Pifagor Language / V.S. Vasilev, A.I. Legalov // Automatic Control and Computer Sciences. - 2018 . - Vol. 52, P. 843-849.
116. Васильев, В. С. Оптимизация кода функционально-потокового языка программирования Пифагор / В.С. Васильев // Суперкомпьютерные дни в России. - Москва, 2018. - С. 997-998.
117. Васильев, В.С. Оптимизация параллельных списков функционально-потокового языка программирования "Пифагор" / В.С. Васильев, И.Н. Рыженко, И.В. Матковский // Системы. Методы. Технологии. - 2014. - № 3, С. 102-107.
118. Васильев, В.С. Оптимизация графов потока управления в промежуточных представлениях языка функционально-потокового параллельного программирования / В.С. Васильев, А.И. Легалов // Научный вестник Новосибирского государственного технического университета. - 2020. - № 4. - С. 37-46.
119. Васильев, В.С. Оптимизация хвостовой рекурсии ФПЯП Пифагор / В.С. Васильев // Молодежь и наука: сборник материалов IX Всероссийской научно-технической конференции [Электронный ресурс]. — Красноярск: Сибирский федеральный ун-т, 2013. — Режим доступа: http://conf.sfu-kras.ru/sites/ mn2013/section045.html, свободный.
120. Васильев, В. С. Оптимизация хвостового вызова в языке «Пифагор» /
B.С. Васильев // Материалы 53-й Международной научной студенческой конференции МНСК-2015: Информационные технологии. - Новосибирск. - 2015, 297 С.
121. Васильев, В.С. Особенности преобразования хвостовой рекурсии в функционально-потоковом языке параллельного программирования / В.С. Васильев, А.И. Легалов, А.И. Постников // Системы. Методы. Технологии. 2013. №3.
C. 106-111.
122. Васильев, В. С. Свидетельство о государственной регистрации программы для ЭВМ № 2013613531 Российская Федерация. Модуль формирования оптимизационного внутреннего представления программ ФПЯП «ПИФАГОР» / В.С. Васильев, А.И. Легалов, М.С. Кропачева; заявитель и правообладатель Феде-
ральное государственное автономное образовательное учреждение высшего профессионального образования "Сибирский федеральный университет" (СФУ). — № 2013611551; заявл. 21.02.2013; опубл. 10.04.2013г. — 1 с.
123. Васильев, В.С. Внутренние представления в системе оптимизации функционально-потоковых параллельных программ / В.С. Васильев, О.В. Непомнящий // Современное программирование. - Нижневартовск, 2021. - С. 9-15.
124. Васильев, В.С. Использование системы оптимизации функционально потоковых параллельных программ / В.С. Васильев // Приоритетные направления инновационной деятельности в промышленности: сборник научных статей международной научной конференции. - Казань, 2021. - С. 81-85.
125. Васильев, В. С. Трансформация функционально-потоковых параллельных программ в императивные / В.С. Васильев, А.И. Легалов, С.В. Зыков // Моделирование и анализ информационных систем. - 2021. - Т. 28. - №. 2. - С. 198-214.
126. Васильев, В.С. Свидетельство о государственной регистрации программы для ЭВМ № 2021662788 Российская Федерация. Программа преобразования реверсивных информационных графов языка ПИФАГОР в программы на языке С++ / В. С. Васильев, О. В. Непомнящий; заявитель и правообладатель Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Сибирский федеральный университет" (СФУ). — № 2021661762; заявл. 26.07.2021; опубл. 04.08.2021. — 1 с.
Список сокращений
CFG - граф потока управления;
DDG - граф зависимостей по данным;
PDG - граф программных зависимостей;
SSA - форма статического единственного присваивания;
АСД - абстрактное синтаксическое дерево;
ПВС - параллельная вычислительная система;
ПП - промежуточное представление;
РИГ - реверсивный информационный граф;
УГ - управляющий граф;
ФПП - функционально-потоковый параллельный; ЯПФ - ярусно-параллельная форма.
Приложение А Примеры оптимизируемых программ Приложение А.1 Функции сравнения значений любых типов
Функция equals выполняет сравнение двух значений, являющихся либо элементами встроенных типов, либо списками данных. При этом для сравнения списков используется функция vec_equals, на вход которой могут подаваться списки данных произвольной структуры:
1. equals << funcdef X {
2. A << X:1;
3. B << X:2;
4.
5. 6 EqOp << [((X:|,3):[<,=]):?]A(=, X:3);
и . 7. TypeA << A:type;
8. TypeB << B:type;
9. [((TypeA, TypeB):[!=, =]):?]a(
10. false,
11. {
12. block {
13. [((TypeA, datalist):[!=,
14. {(X:1, X:2):=},
15. {X:vec_equals}
16. ) >> break
17. }
18. }
19. ):.:. >> return;
20. }
Для обоих аргументов определяется тип с помощью встроенной операции type, если типы не совпадают — возвращается false. В противном случае, если типы не совпадают с datalist (список данных) — выполняется операция сравнения, а при совпадении — функция vec_equals. Операция сравнения может быть передана в качестве третьего аргумента функции, если он не задан — используется встроенный оператор =.
1. vec_equals << funcdef X {
2. VectorA << X:1;
3. VectorB << X:2;
4.
5. SizeA << VectorA:|;
6. SizeB << VectorB:|;
7. [((SizeA, SizeB):[!=,=]):?]A(
8. false,
9. {
10. block {
11. Pairs << X:#:[];
12. CountEquals << ((Pairs:equals):?):|;
13. [((CountEquals, SizeA):[!=,=]):?]A(
14. false, true
15. ) >> break
16. }
17. }
18. ):. >> return;
19.}
В функции vec_equals для каждого из исходных списков определяется длина — если полученные значения не совпали, функция возвращает false, иначе — список-аргумент функции транспонируется и полученный список преобразуется в параллельный. В результате список "((x1,x2,...xn), (y1, y2, ... yn))" преобразуется сначала в список пар "((x1, y1), (x2, y2), ... (xn, yn))", а затем — в параллельный список пар "[(x1, y1), (x2, y2), ... (xn, yn)]".
Над параллельным списком пар элементов выполняется функция equals, в результате сформируется параллельный список значений логического типа, который помещается внутрь списка данных (при этом раскрывается в соответствии с правилами эквивалентных преобразований). Применение к полученному списку оператора селекции (?) приведет к формированию списка индексов true-значений, то есть номеров пар, значения в которых совпали. Для полученного списка определяется длина (CountEquals), при совпадении которой с длиной одного из исходных списков возвращается true, иначе — false.
Приложение А.2 Древовидная свертка списка
Сверткой списка (х1, х2, ... хп) с функцией ор является операция, результат которой формируется по правилу:
х1 <ор> х2 <ор> ... <ор> хп
В зависимости от порядка выполнения операций (слева или справа) во многих языках программирования существуют функции &Мг и
Однако для ряда операций (сложение, умножение) порядок вычисления не важен и свертка может выполняться параллельно с помощью древовидной структуры. Реализация древовидной свертки на Пифагор:
1. // древовидная свертка списка
2. // ((x1,x2,...,xn), op):foldt -> x1 <op> x2 <op> ... <op> xn
3. foldt << funcdef X {
4. A << X:1;
5. Operation << X:2;
6.
7. Len << A:|;
8. [((Len,2):[<,=,>]):?]A
9. (
10. {
11. A:[]
12. },
13. {
14. A:Operation
15. },
16. {
17. block {
18. OddVec << A:[(1,Len,2):..];
19. EvenVec << A:[(2,Len,2):..];
20. ([(OddVec, Operation),(EvenVec, Operation)]:foldt):Operation >> break
21. } 22. }
23. ):. >> return;
24. }
Функция принимает на вход список "A", длиной Len. Если Len меньше двух, результатом работы функции является исходный список. Если список A содержит ровно два элемента, функция возвращает результат применения к нему заданной операции (Operation). Если Len больше двух, список A разделяется на две части (OddVec и EvenVec), содержащие элементы с четными и нечетными индексами. В результате рекурсивной обработки каждой из частей будет получено два значения, над которыми также выполняется Operation.
Приложение А.3 Функция map
Во многих функциональных языках программирования встроена функция map, принимающая список и операцию, возвращающая новый список, каждый элемент которого получен применением операции к соответствующему элементу исходного списка:
1. // ((x1,x2,...,xn), f):map -> (x1:f, x2:f,...xn:f)
2. map << funcdef X {
3. List << X:1;
4. Operation << X:2;
5. return << (List:[]:Operation);
6. }
Для реализации такой функции на языке Пифагор достаточно исходный список преобразовать в параллельный, а затем применить к нему заданную операцию.
В ряде языков и библиотек можно встретить аналогичную функцию, на вход которой передается несколько списков. При этом операция применяется к парам соответствующих элементов. Реализация на Пифагор:
1. map3 << funcdef X {
2. VectorA << X:1;
3. VectorB << X:2;
4. Operation << X:3;
5.
6. [((VectorA:|, VectorB:|):[!=, =]):?]Л(
7. "badVectorSize",
8. {((VectorA , VectorB):#:[]:Operation)}
9. ):. >> return;
10.}
При несовпадении длин исходных списков возвращается ошибка, иначе с помощью операции транспонирования из исходных векторов формируется параллельный список пар (подробнее такое поведение описано в приложении 1.4) к каждой из которых применяется заданная операция.
С помощью приведенных функций может быть реализовано вычисление суммы и скалярного произведения векторов:
1. // скалярное произведение векторов
2. vec_mul << funcdef X {
3. (X:1, X:2, *):map3 >> return;
4. }
5.
6. // сумма векторов
7. vec_sum << funcdef X {
8. (X:1, X:2, +):map3 >> return;
9. }
Приложение А.4 Умножение матриц
Реализация умножения матриц по методу "строка на столбец" на языке Пифагор:
1. matrix_mul << funcdef X {
2. A << X:1;
3. B << X:2:#;
4.
5. [((X:1:1:|, X:2:|):[!=, =]):?] a (
6. "bad matrix size",
7. {
8. block {
9. N << A:|;
10. M << B:|;
11.
12. ARows << ((A,M):dup:#:[]);
13. BColumns << ((B, N):dup:[]);
14.
15. ResultElements << (ARows, Bcolumns, row_col_mul):map3;
16.
17. ResultElements >> break;
18. } 19. }
20. ):. >> return;
21.} 22.
23. row_col_mul << funcdef X {
24. Row << X:1;
25. Column << X:2;
26.
27. return << ((Row, Column, vec_mul):map3:[]:sum_list);
Функция matrix_mul выполняет:
- получение матриц A и B из списка-аргумента, при этом матрица B переворачивается (транспонируется), так как по алгоритму требуется обрабатывать столбцы этой матрицы;
- проверку возможности умножения (корректности размеров исходных матриц);
- получение количества строк матрицы A (N) и столбцов матрицы B до поворота (M);
- дублирование строк и столбцов исходных матриц для последующего их умножения. При этом матрица A дублируется M раз, а затем полученный список матриц транспонируется и преобразуется в параллельный список. В результате получится список строк матрицы A, в котором каждая строка продублирована. Матрица B уже перевернута, поэтому ее транспонирование не требуется, выполняется только ее дублирование и преобразование в параллельный список;
- над полученными параллельными списками выполняется функция row_col_mul.
Функция row_col_mul принимает на вход список данных, из двух элементов, каждый из которых является двумерным списком данных, задающим строки (Row и Column), которые надо перемножить, а полученные результаты сложить. Для этого над соответствующими элементами строк (с помощью map3) выполняется функция умножения векторов (vec_mul), полученный результат преобразуется в параллельный список, над которым выполняется функция sum_list.
Приложение А.5 Скрипт применения оптимизирующих преобразований для
тестового набора функций
echo "inline optimization" #inline row_col_mul -> sum_list ./optimize --in --what "sin" --where "x_rotate" ./optimize --in --what "cos" --where "x_rotate"
echo "parallel list invariant optimiztion" ./optimize --par_inv --goal "figure_rotate" "x_rotate"
echo "equivalent tranformations optimiztion"
/optimize --eq cos_r
/optimize --eq sin_r
/optimize --eq map3
/optimize --eq vec_mul
/optimize --eq foldt
/optimize --eq figure_rotate
/optimize --eq x_rotate_cst_args_2
/optimize --eq matrix_mul
/optimize --eq row_col_mul
echo "dead code optimization"
./optimize --dc cos_r
./optimize --dc sin_r
./optimize --dc map3
./optimize --dc vec_mul
./optimize --dc foldt
./optimize --dc figure_rotate
./optimize --dc x_rotate_cst_args_2
./optimize --dc matrix_mul
./optimize --dc row_col_mul
echo "tail recursion optimization"
./optimize --eq vec_sum_tail
./optimize --tail_rec vec_sum_tail
./cgen2 "-f" "./repository/map3/00.00/1.rig" "./repository/map3/00.00/1.cg" ./cgen2 "-f" "./repository/vec_mul/00.00/1.rig" "./repository/vec_mul/00.00/1.cg" ./cgen2 "-f" "./repository/foldt/00.00/1.rig" "./repository/foldt/00.00/1.cg" ./cgen2 "-f" "./repository/figure_rotate/00.00/1.rig" "./repository/figure_rotate/ 00.00/1.cg"
./cgen2 "-f" "./repository/x_rotate/00.00/1.rig" "./repository/x_rotate/00.00/1.cg" ./cgen2 "-f" "./repository/x_rotate_cst_args_2/00.00/1.rig" "./repository/ x_rotate_cst_args_2/00.00/1.cg"
./cgen2 "-f" "./repository/matrix_mul/00.00/1.rig" "./repository/matrix_mul/00.00/1.cg" ./cgen2 "-f" "./repository/row_col_mul/00.00/1.rig" "./repository/row_col_mul/00.00/1.cg" ./cgen2 "-f" "./repository/cos_r/00.00/1.rig" "./repository/cos_r/00.00/1.cg" ./cgen2 "-f" "./repository/sin_r/00.00/1.rig" "./repository/sin_r/00.00/1.cg"
#echo "((1,2,3),30)" > arg.pfg #./trans2 -c arg.pfg #./inter2 x_rotate
Приложение Б Тестовые наборы системы трансформации функционально-потоковых программ в последовательную императивную форму
Приложение Б.1 Примеры программ для тестирования трансформации
отдельных конструкций языка
Код на языке Пифагор:
1. //@{@int}->@double
2. ex1 << funcdef X {
3. return << 123.456;
4. }
5.
6. //@{@int}->@int
7. ex2 << funcdef X {
8. [((X, 0):[<, >=]):?]A(
9. {1},
10. {2}
11. ):. >> return;
12. }
13.
14. //@{@double}->@double
15. ex3 << funcdef X {
16. return << (X,34):+;
17. }
18.
19. //@{@double}->@double
20. ex4 << funcdef X {
21. A << (X,2):*;
22. [((X,0):[=<, >]):?]A(
23. {(X,1):+}, {A:-}
24. ):. >> return;
25. }
26.
27. //@{@double, @double}->@double
28. ex5 << funcdef X {
29. A << X:1;
30. B << X:2;
31. return << (A, B):+;
32. }
33.
34. //@{@double}->@double
35. ex6 << funcdef X {
36. A << X:ex4;
37. B << (1,X):ex5;
38. return << (A, B):+;
39. }
40.
41. //@{@int}->@(@double)
42. ex7 << funcdef X {
43. return << (12,34);
44. }
45.
46. //@{@int}->@(@(@double))
47. ex8 << funcdef X {
48. return << ((12,34),(5,б));
49. }
50.
51. //@{@int}->@bool
52. ex9 << funcdef X {
53. return << (X,1):<;
54. }
55.
56. //@{@double, @{@double}->@double,
57. // @{@double, @double}->@double}->@double
58. ex10 << funcdef X {
59. Data << X:1;
60. FuncA << X:2;
61. FuncB << X:3;
62. return << (Data : FuncA,
63. (Data, Data):FuncB):+;
64. }
65.
66. //@{@(@(@int))}->@(@(@int))
67. ex11 << funcdef X {
68. return << X:1:#;
69. }
70.
71. //@{@(@int)}->@(@int)
72. ex12 << funcdef X {
73. Par << X:[];
74. return << Par:ex2;
75. }
76.
77. //@{@(@(@int))}^@(@int)
78. // ((1,2), (3,4)):ex13
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.