ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 3, с. 46-60
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 519.687
РЕАЛИЗАЦИЯ ЯЗЫКА ФУНКЦИОНАЛЬНОГО ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ FPTL НА МНОГОЯДЕРНЫХ
КОМПЬЮТЕРАХ* © 2014 г. В. П. Кутепов, П. Н. Шамаль
Москва, МЭИ (национальный исследовательский ун-т) Поступила в редакцию 18.07.13 г., после доработки 29.01.14 г.
Дается описание функционального языка программирования, поддерживающего неявное распараллеливание программ. Язык основан на четырех операциях композиции, три из которых позволяют выполнить распараллеливание вычислений. Рассмотрено схемное представление функциональных программ, позволяющее применить динамический алгоритм распараллеливания. Реализованные алгоритмы позволяют динамически распределять нагрузку между процессорами и контролировать зернистость распараллеливания. Приведены экспериментальные данные эффективности реализованной системы на примерах типовых задач.
БО1: 10.7868/8000233881403010Х
Введение. Понятие функции является фундаментальным как в математике, так и в программировании. Поэтому всегда был велик интерес к созданию языков функционального программирования. Задачи вычислительной математики, сортировки данных, трансляции языков и многие другие имеют функциональную природу, и методы их решения могут быть достаточно просто описаны на функциональных языках. Кроме того, общепринятая в математике композиционная форма задания функций с использованием привычных операций подстановки, суперпозиции и рекурсии позволяет строить простые и эффективные алгоритмы для реализации параллельного вычисления значений функций. Язык FPTL (Functional Parallel Typified Language) создавался на этой основе [1—4]. Другое направление создания языков функционального программирования базируется на теоретической модели ^-абстракций Черча [5], которая была изначально нацелена на решения проблемы контекстуального разделения переменных с одними и теми же именами, используемыми в разных местах текстов, в частности математических выражений. Операции ^-связывания переменных и подстановки ^-выражений без явного использования рекурсии (она представляется неявно) уже достаточны для того, чтобы этими средствами можно было выразить любую вычислимую функцию. Простые правила редукции ^-выражений, всегда приводящие к одному и тому же результату, если он существует, дают основания рассматривать процессы приведения ^-выражений к нормальной форме как функциональные. Эта особенность ^-исчисления, а также способность единообразно путем применения операции ^-связывания переменных в выражениях строить таким косвенным путем функции любого порядка, по-видимому, сыграли определяющую роль в создании серии языков ^-основанного функционального программирования. LISP [6], ML [7], Haskell [8], F# [9] — примеры известных языков этого направления. Однако реальная практика заставила использовать рекурсию для упрощения задания функций, вводить систему базисных типов и функций для построения других функций (в LISP, например, введен набор базисных функций для выполнения операций над списками: CAR, CDR, CONS, APPEND, EQ и др.).
Сравнивая языки функционального программирования обоих направлений, следует отметить, что на стороне ^-основанных языков более универсальные средства задания функций высших порядков. Минусы этого типа функциональных языков — в их часто неоправданно усложненной форме программы, функциональная природа которой выражается неявно и является следствием уже выше отмеченной однозначности ее выполнения. Проблема автоматического распараллеливания функциональных программ на этих языках трудно разрешима как до выполнения программы, так и в процессе ее выполнения. Поэтому распараллеливание программ на
* Работа выполнена при финансовой поддержке РФФИ (проект № 13-07-00810).
этих языках выполняет сам программист, используя специально вводимые в язык примитивы задания параллелизма [9].
Язык FPTL [3, 4] построен на композиционной основе, он достаточно прост в освоении, поскольку сохраняет общепринятую форму задания функций посредством использования четырех простых операций композиции функций и рекурсивных определений, задаваемых в виде систем функциональных уравнений. Он строго типизирован и позволяет однообразно, как и функции, определять абстрактные типы данных в виде систем уравнений. FPTL самодостаточен в том смысле, что не требует введения, как в LISP, множества базисных функций; они непосредственно извлекаются из определения типов данных аргументов и результатов функций, как конструкторы этих данных и обратные к ним деструкторы. Кроме того, в FPTL в качестве базисных функций можно использовать арифметические и другие уже реализованные в компьютере функции. Но самое важное с точки зрения построения параллельных программ состоит в том, что для задания параллелизма в них не требуется использование каких-либо специальных примитивов и он автоматически легко распознается при выполнении программы. Это является следствием того, что три из четырех операций композиции функций являются параллельными. Эти особенности FPTL создали основу для разработки качественных параллельных программ, не прибегая к применению других средств задания параллелизма в программе [3].
В описываемой в статье реализации FPTL на многоядерных компьютерных системах использовались операционные средства MULTITHREADING для управления параллельными процессами. Теоретическая основа языка FPTL подробно описана в [1—4], в данной статье будут рассмотрены только те внесенные в язык изменения, которые были направлены на его более простую и эффективную параллельную реализацию на многоядерных компьютерных системах. Далее кратко опишем теоретическую модель FPTL и модель параллельного вычисления значений функций, а затем реализацию языка и экспериментальные данные эффективности параллельного выполнения FPTL-программ на многоядерных компьютерах.
В разд. 1 статьи приведена основа языка FPTL, в разд. 2 — реализация FPTL на многоядерных компьютерах, в разд. 3 — результаты экспериментального исследования эффективности параллельного выполнения FPTL-программ. В приложение вынесены исходные тексты FPTL-про-грамм, используемых в экспериментах.
1. Теоретическая основа языка FPTL. Язык FPTL, как было отмечено во Введении, создавался как прообраз общепринятой в математической практике формы задания функций в общем случае в виде систем рекурсивных функциональных уравнений, в которых используется операция подстановки функций вместо функциональных переменных и условный оператор.
В FPTL введены четыре простые бинарные композиции функций, которые позволяют легко отразить композиционное представление функции и, что более важно в данном контексте, явно отразить параллелизм.
Функции в FPTL рассматриваются, как типизированные t[ х t'2 х ... х t'm ^ t" х 12 х ... х t'n (m, n)-
арные соответствия (m > 0, n > 0) между кортежами данных, где t'¡, i = 1, m и t", j = 1, n — типы элементов входного и выходного кортежей, m — длина кортежа на входе функции, n — на выходе. Функции арности (0, 1) рассматриваются в FPTL как константы. Для m и n, равных 0, имеем кортеж нулевой длины, обозначаемый X, со свойствами Ха = аХ = а, где а — произвольный кортеж. Кортеж данных в языке представляется в виде последовательной записи его элементов.
В FPTL в отличие от общепринятой формы задания функций с явным указанием ее аргументов (так называемая форма задания общего значения функции) строго различается собственно функция как отображение одного множества в другое и ее аппликация к конкретным данным. Роль переменных в задании функций в FPTL выполняют функции выбора необходимого элемента из кортежа данных. Формально функция выбора аргумента, обозначаемая I(i, m) (в языке — просто [i]), при применении к кортежу произвольного типа данных длины m (m > 0) выбирает его
i-й элемент, i = 0, m, m > 0. Для i = 0 выбираемое значение есть X. Функции в FPTL являются в общем случае частичными, причем неопределенное значение функции может быть выражено либо как неограниченный процесс вычисления ее значения, либо как специальное вычисленное неопределенное значение, обозначаемое ю, со свойствами иа = аю = ю для любого кортежа а.
Формально функции определяются как системы функциональных уравнений Fi = т, i = 1, n, где т, — функциональные термы, построенные из заданных (базисных) функций и функциональных переменных Fi путем применения четырех операций композиции функций: +, *, ♦. Для функций и функциональных переменных задана их арность, а для базисных функций — также их
тип. Тип функциональных переменных однозначно определяется из задания типов базисных функций и правил вывода типов для функций, построенных путем применения операций композиции.
Пусть f {m'n) — (m, я)-арная функция,f(a) — результат ее применения к кортежу a, /1, / — заданные функции, а, в, у — обозначение кортежей. Синтаксис и семантика операций композиции определяются следующим образом.
1. Последовательная композиция (♦):
r(m, n) def (m, к) Ak, n)
J — f 1 'f 2 ; f(a) —f f2(f (a)),
где a = a1 a2 a3 ... am — кортеж данных типа t1 x t2 x ... x tm; ti — тип данных /-го аргумента функции. Здесь и далее сначала задается синтаксис операции композиции, а затем ее семантика, определяемая через применение функций к кортежу данных. Предполагается, что типы кортежа значений функции /1 и кортежа аргументов функции /2 одинаковы.
Заметим, что в FPTL используется префиксная форма записи операции последовательной композиции, задающая последовательный характер вычисления значений функций/1 и/2 и эквивалентная последовательному характеру задания следования операторов при выполнении последовательных программ.
2. Операция конкатенации кортежей значений функций (*):
(m, ni + П2) def „(m, ni) (m, П2)
f — f 1 * f 2 ;
f(a) —effi(a)f2(a).
Предполагается, что типы аргументов функций f1 и f2 одинаковы.
3. Операция условной композиции:
r(m, n) def Am, k) r(m, n) f — fi ^ f 2 ;
def if2(a), если f1 (a) отлично от значения "ложь" или ю, f(a) — \
[ю иначе.
Предполагается, что типы кортежей аргументов функций f1 и f2 одинаковы.
4. Операция объединения (
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.