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

Введение 4
Постановка задачи 8
1. Обзор 9
1.1. Метавычисления 9
1.2. Подход дистилляции 10
1.3. Обзор существующего решения 27
2. Перепроектирование существующего решения 34
3. Разработка дистиллятора 37
3.1. Упрощение шагов алгоритма дистилляции 37
3.2. Реализация нового алгоритма дистилляции 37
4. Тестирование дистиллятора 44
4.1. Интеграционное тестирование 44
4.2. Функциональное тестирование 47
4.3. Тестирование на основе свойств программ 48
Заключение 51
Список литературы 53
Купить

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

Купить