Аннотация результатов, полученных в 2022 году
Данная работа направлена на создание распараллеливающих компиляторов для вычислительных систем с распределенной памятью. Попытки создания таких компиляторов рассматривались во многих публикациях. Известный специалист в области автоматического распараллеливания U. Bondhugula отмечает, что компиляция для параллельной архитектуры с распределенной памятью считается очень сложной задачей никакого практического и эффективного решения (в момент публикации) не существует (U. Bondhugula. Automatic distributed-memory parallelization and codegeneration using the polyhedral framework, Technical report, ISc-CSA-TR-2011-3, 2011, 10 pp.). Для вычислительной системы с распределенной памятью самой длительной операцией становится межпроцессорная пересылка данных. Накладные расходы, связанные с пересылками данных, приходится учитывать при отображении программ на распределенную память. Это не только затрудняет создание распараллеливающего компилятора для таких компьютеров, но и существенно сужает множество эффективно распараллеливаемых программ. Однако в последнее время появляются многоядерные процессоры, иногда называемые «суперкомпьютер на кристалле», с десятками, сотнями и тысячами ядер. Пересылка данных между процессорными ядрами на микросхеме требует значительно меньше времени, чем на коммуникационной сети, хотя, по-прежнему остается самой длительной операцией. Это означает расширение множества эффективно распараллеливаемых программ и делает целесообразным разработку распараллеливающих компиляторов. Более того, без распараллеливающих компиляторов сдерживается развитие таких высокопроизводительных микросхем. Авторами данного исследования предлагается ограничивать множество размещений данных в распределенной памяти и множество межпроцессорных пересылок данных. Авторы используют блочно-аффинные размещений данных (известные из предыдущих работ), которые описываются небольшим множеством параметров, что удобно для преобразования последовательной программы в параллельную для ВС с распределенной памятью. В качестве межпроцессорных пересылок данных рассматриваются циклические и «широковещательные» рассылки данных broadcast (данные из одного процессорного элемента пересылаются в несколько или все). В литературе приводится много задач линейной алгебры и задач математической физики, для параллельного решения которых на вычислительной системе с распределенной памятью используются частные случаи блочно-аффинных размещений данных и такие пересылки. Авторами проекта показано, что представленным ограничениям также удовлетворяют задачи обработки изображений и др. Авторами получены алгоритмы блочно-аффинных размещений массивов в распределенной памяти с минимизацией межпроцессорных пересылок. В частности, построена используемая для минимизации межпроцессорных пересылок новая графовая модель программного цикла – граф операторы-переменные (ГОП). Этим самым внесен вклад в развитие теории преобразования программ. Получены оценки сложности алгоритмов поиска минимального множества необходимых межпроцессорных пересылок. Получены алгоритмы распараллеливания рекуррентных циклов на целевые компьютеры с распределенной памятью. Получены методы автоматического ускорения алгоритмов итерационного типа с помощью размещения массивов в распределенной памяти с перекрытиями. Выполнена экспериментальная реализация в Оптимизирующей распараллеливающей системе многих разработанных в данном проекте алгоритмов: строится граф ГОП, определяются в программе места и параметры межпроцессорных пересылок (в код программы вставляются псевдокомментарии), для простых случаев автоматически генерируется параллельный MPI-код. Главный вывод выполненных работ: доказана принципиальная возможность создания эффективного распараллеливающего компилятора на компьютер с распределенной памятью и показаны пути его создания, в том числе, на основе Оптимизирующей распараллеливающей системы www.ops.rsu.ru . Некоторые из полученных результатов доступны в Сети Интернет: • Доклад на XXIV Всероссийской научной конференции (19-22 сентября 2022 г., он-лайн) "Научный сервис в сети Интернет". https://keldysh.ru/abrau/2022/video/17.mp4 • Доклад на Национальном суперкомпьютерном форуме НСКФ-2022 https://yandex.ru/video/preview/9312471263749518126 • Журнал «Инженерный вестник Дона» № 12 http://www.ivdon.ru/

Аннотация результатов, полученных в 2023 году
В отчетном периоде выполнения проекта развивалась теория преобразования программ для вычислительных систем с распределённой памятью. На данном этапе доказано, что задача поиска наименьшего множества межпроцессорных пересылок является NP-трудной. Поскольку во многих практически значимых случаях пространство циклических векторов графа «операторы-переменные» может иметь не очень большую размерность, для поиска минимального множества пересылок могут использоваться не только эвристические алгоритмы, но и точные, основанные на методе ветвей и границ. На данном этапе на примере практически важных задач рассматриваются задачи распараллеливания более сложных циклов, чем прежде, которые могут содержать другие циклы. Получен список оптимизирующих преобразований программ, которые должны быть в оптимизирующем распараллеливающем компиляторе для вычислительной системы с распределенной памятью. Приведем список таких преобразований: 1. Размещение данных в распределенной памяти. 2. Поиск оптимального множества циклических пересылок с помощью ГОП (граф операторы-переменные). 3. Транспонирование матриц, размещенных в распределенной памяти и его обобщение на многомерные массивы. 4. Размещение массивов данных кратными с перекрытиями. 5. Группировка пересылок. 6. Определение оптимального количества ПЭ (процессорных элементов). 7. Оптимизация преобразований размещенных в распределенной памяти многомерных массивов: транспонирование и скашивание. Приводятся также преобразования, которые могут быть полезны для вычислительных систем как с распределенной памятью, так и с общей памятью. К таким преобразованиям циклов следует отнести слияние, разбиение, гнездование, развертка, расщепление, … Это преобразования, которые традиционно выполняются для самых глубоко вложенных циклов (innermost loop), но условия эффективного применения этих преобразований к не самым глубоко вложенным циклам недостаточно разработаны и эти преобразования компиляторами не выполняются. Есть описанные в литературе преобразования, которые не выполняются в компиляторах, такие как ретайминг (сдвиги операторов между итерациями циклов). Разработан проект СПП – системы преобразования программ. Приводятся условия реализации системы преобразования программ для вычислительных систем нового типа, в том числе, для вычислительных систем с распределенной памятью. Приводятся обоснования того, что реализацию целевых преобразований выгоднее делать на основе высокоуровневого внутреннего представления программ. Приводятся обоснования того, что, несмотря на высокую эффективность высокопроизводительных библиотек, создание инструментов автоматизированного распараллеливания и оптимизации целесообразно. Отсутствие инструментов создания параллельных программ на вычислительные системы с распределенной памятью будет сдерживать развитие вычислительной техники новых поколений, поскольку без программного обеспечения, адекватно использующего такую технику, теряется смысл в создании такой техники. По результатам научных исследований за истекший период опубликовано 6 научных статей и сделано 5 научных докладов на российских и международных конференциях. Основные результаты изложены в докладах 1 ) Штейнберг Б.Я. О создании распараллеливающих компиляторов на вычислительные системы с распределенной памятью. Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», 18-22 сентября 2023 г., он-лайн., ИПМ им. Келдыша, г. Москва, 11 с., https://keldysh.ru/abrau/2023/temp/23.pdf 2 ) Bagliy A.P., Krivosheev N.M., Steinberg B.Ya., Steinberg O.B. Automation of Parallelization of Loops with Minimization of Data Transfers // Параллельные вычислительные технологии - XVII всероссийская конференция с международным участием, ПаВТ'2023, г. Санкт-Петербург, 28-30 марта 2023 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2023. С. 7-16. http://omega.sp.susu.ru/pavt2023/short/104.pdf 3 ) Штейнберг Б.Я. О создании системы преобразований программ для создания распараллеливающих компиляторов на вычислительные системы с распределенной памятью. Национальный суперкомпьютерный форум НСКФ-2023, г. Переславль-Залесский 28 ноября – 1 декабря 2023 г. https://www.youtube.com/watch?v=xo3DV0kWmVw