Реализация дистиллятора для простого функционального языка на 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
Постановка задачи 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], реализующая этот подход, предоставляет набор простых операций, хорошо подвергающихся соединению, с помощью которых можно составлять более сложные операции над коллекциями. Подобные решения достаточно популярны и реализованы для различных языков. Например, для 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, но она не является стабильной. Поэтому не существует программы, демонстрирующей возможности дистилляции в качестве оптимизатора программ, использующих операции линейной алгебры. Реализация подхода дистилляции для базового функционального языка, обладающего хорошим тестовым покрытием и набором примеров работы подхода, помогла бы исследовать применимость подхода дистилляции для оптимизации программ, использующих операции линейной алгебры.
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.
• Проведено тестирование полученной реализации и выявлены неточности в описании алгоритма, приводящие к проблемам, актуальным для любой его реализации:
— Неконсистентное введение новых функций алгоритмом;
— Некорректное распространение информации между разными уровнями алгоритма.
Все изложенные проблемы для полученной реализации были решены.
Таким образом, в рамках выпускной квалификационной работы была реализована упрощенная версия алгоритма дистилляции и проведено комплексное тестирование полученного дистиллятора.
• Интерфейс общения с пользователем был отделен от существующей реализации и разработана архитектура для новой реализации алгоритма. Различные шаги алгоритма выделены в отдельные модули, добавлены новые типы — тип метки и тип помеченной системы переходов для реализации сопоставления с образцом в алгоритме.
• В соответствии с разработанной архитектурой реализован и интегрирован в проект упрощенный алгоритм дистилляции на языке Haskell. Реализация модуля Generalizer была упрощена с целью обеспечения стабилизации остальных модулей алгоритма.
• В рамках подготовки к тестированию алгоритма была настроена тестовая инфраструктура - добавлена непрерывная интеграция исходного кода проекта с использованием Github Actions, а так же настроена и подключена тестовая платформа Tasty.
• Проведено тестирование полученной реализации и выявлены неточности в описании алгоритма, приводящие к проблемам, актуальным для любой его реализации:
— Неконсистентное введение новых функций алгоритмом;
— Некорректное распространение информации между разными уровнями алгоритма.
Все изложенные проблемы для полученной реализации были решены.
Таким образом, в рамках выпускной квалификационной работы была реализована упрощенная версия алгоритма дистилляции и проведено комплексное тестирование полученного дистиллятора.
Подобные работы
- Реализация дистиллятора для простого функционального языка на Haskell
Бакалаврская работа, информационные системы. Язык работы: Русский. Цена: 4360 р. Год сдачи: 2022