Язык программирования FPTL и средства работы с ним (547977), страница 2
Текст из файла (страница 2)
Этонеобязательная практика. Описание переменной в секции Application имеет вид:Тип переменной : имя переменной = значение переменной;Полный пример программыFunctional Program factorialScheme factorial{factorial = P -> F1, F2;P = (id*<0>).eq;F1 = <1>;F2 = (id * DEC.@) . mult;DEC = (id*<1>).minus;}Application%factorial(6)Интерпретатор и компилятор языка FPTLЦелью нашей работы является максимальное использование возможностей, данных намструктурой языка FPTL в области автоматического анализа и распараллеливания программ.Мы параллельно ведем два проекта:Кластерный интерпретатор программ FPTLКомпилятор языка FPTLКластерный интерпретаторКластерный интерпретатор позволяет выполнять программы FPTL на любом кластеремашин, на которых установлен JRE 1.5 и пакеты среды выполнения языка FPTL.
Связьмежду машинами осуществляется посредством сокетов. Мы не используем какие-либостандартные библиотеки для параллельных вычислений (OpenMP, MPI, и т.д.) из-заразличных ограничений, накладываемых ими. Интерпретатор пользуется особенностямиязыка FPTL для поиска параллельно вычисляемых функциональных переменных (далее –ФП). Явной возможности указать параллельно вычисляемые ФП в языке нет.Интерпретатор имеет следующие отличительные черты:Поддержка сетей любого размера (по кол-ву машин)Поддержка любой пропускной способности сетиПоддержка любого кол-ва процессоров/ядер на машине (далее в статье считаем ихмногопроцессорными)Автоматический поиск ФП с достаточной вычислительной сложностью (переносимыхмежду машинами)Функционал по поиску и использованию в процессе вычислений мемоизуемых ФП(ФП таких, что если f(a) уже было ранее вычислено, то при следующей попыткевычисления f(a) будет сразу использован сохраненный с предыдущего вызоварезультат)Работа на куче, а не на стеке, что упрощает выполнение рекурсивных алгоритмовИспользование информации о загруженности как отдельной машины, так и кластера впроцессе вычислений для оптимизации переноса вычисляемых ФПВозможность динамического добавления новых машин в кластер в процессевычисления (они сразу же смогут быть использованы системой)В интерпретаторе реализована система динамического управления выполнениемфункций в зависимости от загруженности машин кластера (отдельныевнутримашинное и кластерное управление)В наших планах добавление в интерпретатор следующих функций:Оптимизация алгоритма поиска пересылаемых ФП (дает теоретическое увеличениемаксимального размера кластера за счет нахождения большего кол-ва задач, которыемогут исполняться одновременно)Подключение вызовов откомпилированных ФП (по сути, аналог JIT-компилятора, новся программа компилируется в начале работы программы на серверной машине)Оптимизации, ведущие к понижению кол-ва используемой памяти внутри одноймашины (актуально на многопроцессорных машинах, где параллельно исполняетсянесколько интерпретаторов и нагрузка на память заметно выше).Как достигается автоматический поиск переносимых ФП?Как было указано в описании языка, оператор звездочка является основным источникомпараллелизма в языке.
Все его аргументы могут вычисляться параллельно. Нахождениевызова ФП в операторе звездочка является необходимым условием того, что этот вызовбудет переносимым. То есть у нас переносимыми являются не ФП вообще, а именно ихвызовы из конкретных мест в программе.Вторым необходимым условием для переносимости ФП является ее достаточная сложность врезультате анализа структурной сложности программы. Алгоритм оценки структурнойсложности здесь приводится не будет (он еще находится в доработке), но гарантируется, чтоструктурная сложность будет возрастать в таком порядке (F(G) – ФП F зависит от ФП G):1.2.3.4.F()F(G), где G()F(F)F(G), где G(G)И так далее.
Фактически сложность ФП вычисляется по формуле «сложность самой сложнойиз ФП, от которой зависит данная» + 1, если данная ФП не рекурсивная или +2, если даннаяФП рекурсивная (рекурсия любого типа – как саморекурсивная – F(F), так и взаимнорекурсивная – F(G), G(F) или F1(F2), F2(F3), F3(F1) – для любого кол-ва ФП в цепочкезависимостей).ФП считается переносимой, если ее сложность не меньше какой-то части от сложностисамой сложной ФП в программе (ФП входа в программу).
На данный момент эта часть равна80% от максимальной сложности.Как мы находим мемоизуемые ФП?По определению, мемоизуемая функция – это такая функция, которая за время работыпрограммы хотя бы дважды вызывалась с одним и тем же значением ее аргумента. Вфункциональных программах необходимость поддержки мемоизации заметно возрастает,т.к. множественные рекурсивные вызовы функции часто приводят ко многим вызовамфункции с одним и тем же ее аргументом. Одним из известных примеров функций, которыеочень выгодно мемоизовать, является вычисление чисел Фибоначчи по формуле fib(n) =fib(n-1) + fib(n-2), при которой у нас будет fib(1) вызовов fib(n), fib(2) вызовов fib(n-1) и т.д.Другим менее известным, но еще более показательным примером является вычислениефункции Аккермана, при котором мемоизация дает возможность программам на медленныхскриптовых языках обходить реализации «в лоб», написанные на Си (заметим, что если языкдает мемоизацию задаром, то мы можем считать ее как оптимизацию сгенерированного кода,и, следовательно как преимущество над другими компиляторами).Для поиска мемоизуемых ФП интерпретатор имеет режим работы, в котором, одновременнос вычислением значения программы, ведется накопление истории вызовов всех ФП впрограмме.
По окончании работы программы строится таблица, в которой для каждой ФПсохраняется общее кол-во ее вычислений и кол-во различных аргументов, с которымивызывалась данная ФП. Чем больше отношение первого числа ко второму, тем выше оценка,получаемая ФП. Также на окончательное решение мемоизовать ФП или нет влияет оценка ееструктурной сложности.
Чем выше эта оценка, тем больше шансов у ФП быть мемоизуемой.В данный момент интерпретатор записывает предлагаемые для мемоизации названия ФП вфайл настроек funcs.xml.При работе в режиме поиска мемоизуемых ФП рекомендуется использовать не слишкомбольшие, но и не слишком маленькие значения начальных аргументов программы. В этомслучае время поиска мемо-ФП будет относительно небольшим, но в тоже время алгоритмпоиска мемо-ФП будет считать их кол-во повторяющихся вызовов достаточным дляопределения ФП как мемо-ФП.Как мы поддерживаем любое кол-во машин в кластере и процессоров намашине?Теоретически, наша система действительно может поддерживать большое кол-вопараллельно выполняющихся интерпретаторов на разных машинах и процессорах в сети. Этодостигается за счет минимизации кол-ва обменов в сети, благодаря тому, что пересылаютсятолько ФП с достаточной вычислительной сложностью.
Время выполнения этих ФП сбольшой долей вероятности заметно больше времени, затрачиваемого на пересылки ФП.В реальности кол-во одновременно работающих на разных узлах (как компьютерах, так ипроцессорах) интерпретаторов на данный момент ограничивается алгоритмом поискапересылаемых ФП и свойствами самой программы (закон Амдала). Задача нахожденияоптимального порога оценки стоимости структурной сложности ФП как функции отимеющегося кластера пока стоит открытой.В нашем видении в идеале интерпретатор языка должен стать средой управления длякомпилируемых программ.
Интерпретатор должен в интерпретируемом режиме набиратьфронт работ, а затем передавать его в компилируемый код для максимально быстроговыполнения. За счет того, что и интерпретатор, и компилируемый код есть классы Java, ихвзаимодействие должно иметь минимальные накладные расходы.Массивы в языке FPTLНа данный момент у нас есть реализация встроенной в язык поддержки работы с массивамина одномашинном одноядерном интерпретаторе.
Мы планируем перенести эту возможностьи в сетевой интерпретатор.Компилятор программ языка FPTLОсновной целью проекта по созданию компилятора с языка FPTL является поископтимизаций для интерпретатора языка. Компилятор переводит программы с языка FPTL наисходный код на языке Java. Затем он вызывает компилятор, поставляемый в комплекте JDKдля окончательной обработки программы.В рамках проекта компилятора были разработаны (или все еще разрабатываются) следующиеподпроекты:Оптимизирующий компилятор на язык Java (строит по данным языка FPTL классыJava, делает наиболее очевидные оптимизации кода)Преобразователь функций, имеющих хвостовую рекурсию (tail recursive functions) изрекурсивного вида в итеративныйПреобразователь программ FPTL, подставляющий inline все простые ФП в программе(с очень низкой вычислительной сложностью)Поиск переносимых и мемоизуемых ФП программы за счет анализа структурнойсложности программыМеханизм компиляции, переноса на удаленные машины и загрузки и выполнения тамоткомпилированных классовМеханизм автоматического вывода типов программы«Клей» между компилированными и интерпретируемыми программами (генерациякода, трансформирующего данные в виде, используемом интерпретатором, в вид,используемый в данной компилированной программе) (частично реализован)Добавление возможности генерации многопоточного кода в компилятор (нереализовано)Добавление функционала по работе с массивами в компилятор (не реализовано)Поддержка мемо-функций в компилируемом коде (не реализовано)Генерация программ на языке FPTL на основе математических формул.
Планируется,что форматом формул будет являться формат набора TeX.Разработка компилятора имеет перед собой по крайней мере две цели:Создание standalone компилятора, генерирующего многопоточный код, нацеленныйна использование в отдельных многоядерных машинах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
