BC/NW 2013: №1 (22):2.2

 

РЕАЛИЗАЦИЯ ЯЗЫКА ФУНКЦИОНАЛЬНОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ FPTL НА МНОГОЯДЕРНЫХ КОМПЬЮТЕРАХ

Д.А. Шорникова, И.Е. Куриленко

 

Целью данного исследования является реализация системы выполнения (интерпретатора) функционального языка параллельного программирования FPTL [1] на многоядерных компьютерах. Язык FPTL создан по композиционному принципу и имеет «чистую» функциональную основу, избавляя программиста от необходимости использования средств явного задания параллелизма на процессном уровне, не имеющем связи с функциональной семантикой программы.

В ходе реализации системы было разработано внутреннее представление функциональных программ, оптимально подходящее для их параллельного выполнения — структурированные функциональные схемы. В качестве модели параллельного выполнения была выбрана модель динамического порождения параллельных процессов.

Параллельные процессы порождаются при обработке операций композиции, имеющих явную или неявную параллельную семантику. В качестве алгоритма планирования параллельных процессов был выбран алгоритм work-stealing [2], специально адаптированный для работы с разработанным внутренним представлением функциональной программы. Особое внимание также было уделено таким важным аспектам реализации функциональных языков программирования, как поддержка «глубокой» рекурсии и автоматическому управлению памятью (сборке мусора).

Эффективность реализации примененных решений была проверена на типовых вычислительных задачах (численное интегрирование, быстрое преобразование Фурье) и типовых задачах обработки данных (быстрая сортировка, построение словарей). В ходе экспериментов было выявлено многократное уменьшение времени выполнения тестовых программ на многоядерных (2—4 ядер) системах, а также ряд особенностей системы, которые не были столь очевидными на этапе проектирования.

Литература

1. Бажанов С.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах // Программирование РАН. 2005. С. 237—269.

2. Robert D. Bluemofe, Charles E. Leiserson. Scheduling multithreded computations by work stealing // 35th Annual Symposium on Foundations of Computer Science

(FOCS 1994). P. 356—368.