Тема: Реализация дистиллятора для простого функционального языка на Haskell

Несмотря на мощность вычислительных устройств в настоящее вре­мя, операции обращения к памяти при исполнении программ до сих пор являются дорогостоящими. Обращения к памяти создаются за счет промежуточных структур данных, генерируемых во время исполнения программы, которые загружаются в память и выгружаются из нее. Трансформация программы таким образом, чтобы она во время ис­полнения использовала меньшее количество промежуточных структур, уменьшит количество обращений к памяти, а в идеальном случае со­кратит их количество до одного обращения, осуществляющего выгруз­ку результата программы. В качестве примера функции, исполнение которой повлечет создание промежуточной структуры данных, можно рассмотреть последовательность операций, написанную на неформаль­ном языке, состоящую из двух применений функции map к массиву:
Array.map g (Array.map f arr)
Данный код естественен для программиста при наличии библио­теки функций для работы с коллекциями, однако, без наличия опти­мизаций, в нём будет создаваться промежуточный массив — резуль­тат применения функции f к массиву arr. Можно еоединить исходную последовательность функций в одну таким образом, что вместо двух последовательных применений map к массиву arr будет применен один map с композицией исходных функций:
Array.map (g о f) arr
Трансформированный код промежуточных структур данных не по­рождает и требует обращения к памяти только для записи результа­та. В общем случае не все последовательности функций, используемые для работы с коллекциями, могут быть соединены в одну очевидны­ми преобразованиями. Для решения данной проблемы был разработан подход Stream Fusion. Библиотека strymonas, описанная в [13], реали­зующая этот подход, предоставляет набор простых операций, хорошо подвергающихся соединению, с помощью которых можно составлять более сложные операции над коллекциями. Подобные решения доста­точно популярны и реализованы для различных языков. Например, для Haskell1 [2], Java [12], OCaml [13]. Недостатком этого подхода является то, что не все операции могут быть выражены через предоставляемый набор простых операций.
Проблема большого количества обращений к памяти, вызванных ис­пользованием промежуточных структур, актуальна не только для кол­лекций. Она свойственна для областей, в которых работа над данными осуществляется с помощью комбинирования набора простых операций: каждая из этих операций будет порождать результат, который будет передан в качестве входных данных следующей в последовательности операции. Такой подход используется в библиотеках для машинного обучения, например в Tensorflow, описанной в [16]. Проблема порожде­ния промежуточных структур данных простыми функциями этой биб­лиотеки также решается с помощью соединения этих функций, эту оп­тимизацию осуществляют инструменты XLA и MLIR, описанные в [1] и [11].
Работа с разреженными данными также часто осуществляется с по­мощью набора простых операций, последовательное исполнение кото­рых приводит к созданию промежуточных структур данных во время исполнения. Такой подход реализовывают, например, библиотеки опе­раций разреженной линейной алгебры. Они предоставляют набор при­митивных операций для работы с разреженными данными (например, умножение двух матриц или их сложение), с помощью которых могут быть выражены более сложные операции.
Одним из перспективных направлений в данной области является стандарт GraphBLAS API2 [4], описывающий набор примитивов разре­женной линейной алгебры (матрицы, вектора) и операций над ними, необходимый для выражения алгоритмов анализа графов. Алгоритмы, таким образом, являются последовательностью элементарных опера­ций линейной алгебры, что и в данном случае приводит к проблеме промежуточных данных, которая для больших графов становится осо­бенно критичной.
Операции над разреженными данными трудно поддаются соедине­нию ввиду сложности используемых структур данных и алгоритмов их обработки, поэтому соединения комбинаций простых операций реали­зовываются вручную, как, например, в GraphBlas:SuiteSparse [3]. Клас­сическим примером ручного объединения операций является операция muliplyAdd — объединение сложения и умножения матриц, или приме­нение маски после бинарной операции, часто используемое в GraphBLAS для фильтрации результата операции. Недавнее исследование [19], про­ведённое при реализации GraphBLAS на GPGPU, показало, что совре­менные подходы к оптимизациям программ не справляются с объеди­нением операций разреженной линейной алгебры, а значит требуются более мощные подходы.
Stream Fusion как подход, позволяющий сократить использование промежуточных списков, часто излагается в контексте дефорестации — более мощного подхода, сокращающего использование промежуточных списков и деревьев, описанного в [18]. Суперкомпиляция [17], частич­ные вычисления [8] и дистилляция [5] также являются родственными дефорестации подходами, более мощными, чем Stream fusion. Поэтому в качестве подходов, которые потенциально могут быть использованы для оптимизации программ, содержащих операции разреженной линей­ной алгебры, естественно начать с исследования возможностей супер­компиляции, частичных вычислений или дистилляции. Хотя суперком­пиляция, дефорестация и частичные вычисления достаточно распро­странены, дистилляция позволяет сократить использование промежу­точных структур данных в большем множестве программ по сравнению с остальными существующими подходами согласно [5]. Другим преиму­ществом дистилляции является то, что применение этого подхода в некоторых случаях производит суперлинейное ускорение программ, ко­торое не может быть достигнуто с помощью других подходов [5]. В ма­гистерской работе [15] было показано, что суперкомпиляция, являюща­яся более мощной, чем частичные вычисления и дефорестация, может достигать только линейного ускорения. Ввиду этих достоинств иссле­дование возможностей дистилляции в качестве подхода к оптимизации программ представляет особенный интерес.
Хотя подход дистилляции позволяет трансформировать большее мно­жество программ, чем остальные подходы, в силу своей трудоемкости он не так распространен, как суперкомпиляция, частичные вычисле­ния и дефорестация. На данный момент существует единственная реа­лизация подхода дистилляции — проект Distiller3, но она не являет­ся стабильной. Поэтому не существует программы, демонстрирующей возможности дистилляции в качестве оптимизатора программ, исполь­зующих операции линейной алгебры. Реализация подхода дистилляции для базового функционального языка, обладающего хорошим тестовым покрытием и набором примеров работы подхода, помогла бы исследо­вать применимость подхода дистилляции для оптимизации программ, использующих операции линейной алгебры.
Купить

В ходе выпускной квалификационной работы в проекте Distiller10 были достигнуты следующие результаты.
• Интерфейс общения с пользователем был отделен от существую­щей реализации и разработана архитектура для новой реализации алгоритма. Различные шаги алгоритма выделены в отдельные мо­дули, добавлены новые типы — тип метки и тип помеченной си­стемы переходов для реализации сопоставления с образцом в ал­горитме.
• В соответствии с разработанной архитектурой реализован и инте­грирован в проект упрощенный алгоритм дистилляции на языке Haskell. Реализация модуля Generalizer была упрощена с целью обеспечения стабилизации остальных модулей алгоритма.
• В рамках подготовки к тестированию алгоритма была настроена тестовая инфраструктура - добавлена непрерывная интеграция исходного кода проекта с использованием Github Actions, а так же настроена и подключена тестовая платформа Tasty.
• Проведено тестирование полученной реализации и выявлены неточ­ности в описании алгоритма, приводящие к проблемам, актуаль­ным для любой его реализации:
— Неконсистентное введение новых функций алгоритмом;
— Некорректное распространение информации между разными уровнями алгоритма.
Все изложенные проблемы для полученной реализации были ре­шены.
Таким образом, в рамках выпускной квалификационной работы бы­ла реализована упрощенная версия алгоритма дистилляции и проведе­но комплексное тестирование полученного дистиллятора.
Купить