автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка и исследование методов и программных средств параллельного выполнения функциональных программ на многоядерных компьютерах

На правах рукописи

■* П

V- VI

Шамаль Павел Николаевич

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных

сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

005559405

Москва 2014

005559405

Работа выполнена на кафедре Прикладной математики ФГБОУ ВПО Национальный исследовательский университет «МЭИ»

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор

Кутепов Виталий Павлович.

Лебедев Валентин Григорьевич

доктор технических наук, профессор,

ФГБУН «Институт проблем управления им. Трапезникова РАН», ученый секретарь,

Селегей Марина Борисовна

кандидат технических наук, ООО «Аби ИнфоПоиск», руководитель группы.

ФГБОУ ВПО «МГУ им. Ломоносова».

Защита состоится 26 декабря 2014 г. в 14 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при ФГБОУ ВПО НИУ «МЭИ» по адресу 111250, Москва, Красноказарменная ул., дом 13, ауд. М 704.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО НИУ «МЭИ».

Автореферат разослан » ноября 2014 г. Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, ,

доцент М. В. Фомина

J

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для того чтобы максимально использовать ресурсы компьютерных систем, в частности многоядерных компьютеров, требуется решение целого ряда проблем. Это создание языковых средств описания параллелизма в программе, определение оптимальной степени ее распараллеливания, а также разработка и реализация методов и алгоритмов управления параллельными процессами и ресурсами при выполнении программ. Широко используемые в промышленном программировании современные объектно-ориентированные языки программирования, такие как Java и С++, основаны на императивной парадигме и не имеют встроенных в язык программирования средств для распараллеливания программ, «прозрачных» для программиста, а лишь предоставляют набор низкоуровневых средств задания параллелизма. Практическое использование этих средств часто приводит к тому, что программа получается плохо масштабируемой и привязанной к конкретной операционной системе, языку программирования или архитектуре вычислительной системы.

Одним из подходов решения этой проблемы применительно к многоядерным компьютерам является использование функциональных языков программирования, которые позволяют абстрагироваться от особенностей используемой вычислительной системы и сложной задачи управления параллельными процессами, сконцентрироваться только на решении поставленной задачи и разрабатывать эффективные параллельные программы.

Язык FPTL (Functional Parallel Typified Language), реализации которого на многоядерных компьютерах посвящена диссертация, создавался с целью эффективной разработки функциональных программ и последующего их параллельного выполнения на многоядерных компьютерных системах с общей памятью и кластерах. В отличие от известных языков функционального программирования, таких как LISP, ML, Haskell, которые в большой степени основаны на ^-исчислении, FPTL основан на использовании традиционной математической формы определения функций путем их композиции с помощью конечного множества операций и общей формы их задания в виде систем функциональных уравнений. Операции композиции функций просты и позволяют описывать параллелизм на семантическом уровне, не используя специальные процессные примитивы, как это делается в других функциональных языках. Однако реализация такого «чисто» функционального языка программирования требует разработки методов и алгоритмов, которые могут обеспечить эффективное

параллельное выполнение программ на многоядерных компьютерах. Это создает необходимые предпосылки создания соответствующей системы выполнения языка РРТЬ на современных многоядерных компьютерных системах.

Цель диссертационной работы. Целью диссертационной работы является разработка и исследование эффективности системы выполнения функциональных параллельных программ на языке РРТЬ на многоядерных компьютерах. Для достижения этой цели в диссертации решаются следующие задачи:

1. Сравнительный анализ методов распараллеливания вычислений в современных функциональных языках программирования.

2. Разработка и исследование методов и алгоритмов эффективного параллельного выполнения функциональных РРТЬ-программ на многоядерных компьютерах.

3. Разработка методов контроля типовой корректности РРТЬ-программ.

4. Создание интегрированной системы параллельного выполнения РРТЬ-программ на многоядерных компьютерах, которая включает следующие подсистемы:

- интерпретатор РРТЬ-программ,

- управление параллельными процессами выполнения функциональных программ,

- статический анализ типовой корректности программ.

5. Экспериментальное исследование эффективности созданной системы.

Методы исследования. В диссертационной работе использовались методы и понятия теории графов, теории алгоритмов, теории рекурсивных функций, теории языков и формальных грамматик и операционных систем. Для практической реализации системы использовались методы объектно-ориентированного и параллельного программирования.

Научная новизна. Научная новизна работы заключается в следующем:

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

2. Предложена модель и на основе ее реализован алгоритм вывода типов в языке РРТЬ.

3. Разработано внутреннее представление функциональных программ и метод организации работы с данными в процессе вычисления значений функций, увеличивающие эффективность реализации параллелизма.

4. Реализован интерпретатор языка РРТЬ, позволяющий динамически осуществлять распараллеливание программ.

5. Разработан алгоритм эффективного управления параллельным выполнением функциональных программ на многоядерных компьютерах.

6. Проведено исследование эффективности созданной системы и сравнение с имеющимися аналогами.

Практическая ценность. Созданная система функционального программирования в настоящее время применяется в обучении методам и средствам параллельного программирования студентов и аспирантов кафедры прикладной математики Московского энергетического института, подготовлена необходимая документация по использованию системы, направлены документы для регистрации программной системы.

Апробация. Положения диссертационной работы докладывались на конференциях: «Параллельные вычисления и задачи управления», Россия, Москва, 2012 г.; XIX ежегодная международная научно-техническая конференция студентов и аспирантов "РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА", Россия, Москва, 2013 г.

Публикации. По теме диссертационной работы опубликовано 5 научных работ, 3 из них в изданиях, включенных в перечень ВАК.

Объем и структура работы. Диссертация состоит из введения, пяти глав и заключения. Список использованной литературы содержит 52 наименования. Текст диссертации содержит 100 страниц машинописного текста, включая 20 рисунков и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Одним из рассмотренных подходов к распараллеливанию функциональных программ является применение средств многопоточности (multithreading). Эти средства основаны на использовании нитей -низкоуровневых процессных средств операционной системы, которые берут свое начало из императивных языков программирования (С, С++, Java и т.д.) и требуют при разработке параллельных программ использования средств для описания взаимодействия между параллельными процессами, которые сложны и приводят к многочисленным трудно обнаруживаемым ошибкам.

Другим подходом к распараллеливанию функциональных программ, применяемым в таких языках, как Haskell и F#, является использование специальных операторов, позволяющих выделять функции, значения которых следует вычислять параллельно. Реализация параллелизма при данном подходе осуществляется средствами т.н. параллельных платформ, которые берут на себя всю работу по планированию параллельных вычислений. Это позволяет избавить программиста от реализации протоколов взаимодействия между параллельными процессами. Однако, программист сам должен определить необходимую степень распараллеливания, соотнося ее как с количеством ресурсов (ядер), так и с особенностями задачи.

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

Во второй главе дается описание языка FPTL. Формально функции в языке определяются как системы функциональных уравнений Ft = rt-, i = l,7i, где Tj - функциональные термы, построенные из заданных (базисных) функций, функциональных переменных Ft и функции выбора к- го элемента из кортежа данных (обозначаются как [к]) путем применения четырех бинарных операций композиции функций: —>, +, *, •. В FPTL различаются собственно обозначение функции (имя функции) / и ее аппликация к кортежу данных a: f(a). Функции в языке FPTL являются в общем случае частичными и существует два вида неопределенного значения: вычислимое

неопределенное значение, которое ооозначается &>, и неопределенное значение функции, связанное с бесконечным процессом вычислений.

Пусть f(,n-") - (jn, п)-арная функция, где m > О и п> О - длины входного и выходного кортежей данных соответственно, fb /2 - заданные функции. Синтаксис и семантика операций композиции определяется следующим образом.

1. Последовательная композиция (•): f(m,n) ^ т.к) . jr^k.n).

/(«) = /2(/l(«)).

2. Операция конкатенации кортежей значений функций (*):

fia) =

3. Операция условной композиции:

. - м (/2(а), если /i(a) определено и отлично от значения «ложь», ' — ( иначе значение не определено.

4. Операция объединения (графиков) ортогональных функций:

!/i(a), если значение ^(а:) определено, /2(а), если значение /2(а) определено, иначе значение не определено. Напомним, что функции и /2считаются ортогональными, если для всякого кортежа данных определена не более чем одна из них.

В FPTL можно представлять любой структурный тип данных, называемый абстрактным типом данных (АТД), определяя его по аналогии с определением функций в общем случае через систему рекурсивных уравнений. При определении абстрактных типов данных используются функции-конструкторы и обратные к ним функции-деструкторы, которые вместе с функциями выбора аргумента образуют полный набор базисных функций в том смысле, что любая вычислимая функция над данными рассматриваемого типа может быть выражена средствами языка FPTL. Кроме того, в языке FPTL можно также использовать встроенные типы: bool, real, int, string и др. вместе с определенными в конкретной компьютерной системе операциями над ними. Приведем пример пользовательского типа. Определим тип «стек комплексных чисел»:

data StackOfOomplex{

Complex = (real * real). c_complex\

StackOfOomplex = c_empty + (StackOfComplex * Complex). c_head;

}

В приведенном выше определении имеется три конструктора c_complex, c_empty, и c_head, имеющие арности (2,1), (0,1) и (2,1) соответственно. В паре с каждым определенным конструктором определяется соответствующий ему деструктор. Деструктор обозначается добавлением ~ к имени конструктора.

(~c_complex(x) — у, если х = c_complex(y), ( <у, иначе;

(~c_empty(x) ' Я, если х = c_empty, 1 со, иначе;

(~c_head(x) = у, если х = c_head(y), 1 о), иначе.

Здесь X — кортеж нулевой длины со свойствами: Ха = аХ = X, где а -любой кортеж данных. В язык FPTL добавлена возможность задания параметризованных типов и функций. Приведем пример определения параметризованного стека, используя параметр Ч (в FPTL обозначение типового параметра предваряется апострофом):

data Stack['t] {

Stack = c_empty + (Stack[4\ * '/). c_head\

}•

Структурно программа на языке FPTL представляет собой схему и ее интерпретацию. Схема используется для задания функций, представленных в виде системы функциональных уравнений. При этом некоторые функции могут не иметь явного определения в схеме, и определяться выбранной интерпретацией. Меняя интерпретацию, программист может получать разные функциональные программы.

В рамках диссертационной работы в язык FPTL были внесены следующие модификации.

1. Бинарные операции композиции —>, + были заменены на одну тернарную операцию. Ее семантика может быть описана следующим образом.

fr(m,n) jjf jr^fm.k)

ff . _ Г/2(а),если Д(а) определено и отлично от значения «ложь»,

иначе/3 (а).

Введение тернарной условной композиции возвращает программиста в более традиционную «if-then-else» нотацию представления условных

конструкций и необходимо для повышения эффективности процессов управления параллельным выполнением программы.

2. Добавлена поддержка работы с массивами данных. Для этого введен встроенный параметризованный тип данных Arrayf't], где Ч - тип элемента массива, и три базисных функции:

- arrayCreate - функция создания массива заданной длины,

- arrayAssign - функция присваивания элементу массива заданного значения,

- arrayRead - функция получения элемента массива. Допускается создание массивов любого уровня вложенности.

3. Добавлена возможность работы с «внешними» функциями. Внешние функции импортируются в FPTL-программу из библиотек, написанных на языках программирования, таких как С и С++, что существенно упрощает процесс разработки FPTL-программ.

4. Для отладки программ добавлена возможность трассировки последовательности вычисления значений заданной функции.

В качестве примера приведем следующую простую программу на языке FPTL, вычисляющую сумму мнимых или вещественных частей списка комплексных чисел, data ListOJComplex {

Complex = (real * real ).с_сотр1ех\

ListOJComplex = c_empty + (ListOJComplex * Complex).c_list;

}

scheme Accumulate {

Accumulate = ~c_empty -> 0.0, ~c list.{[Y\Accumulate * [2].Part).add',

}

interpretation

Real { Part = ~c_complex.[l]; } Img { Part = ~c_complex.[2]; } application

stack = {{{c_empty * ((0.1*0.1 ).c_complexj).cJiead)* ((0.2*0.2).c_complex)).c_head; 0/oAccumulate{stack)',

В приведенном примере в секции scheme описывается рекурсивное функциональное уравнение Accumulate, секция interpretation задает 2 интерпретации с именами Real и Img (которые определяют функцию Part в схеме), извлекающие значение вещественной или мнимой части соответственно.

В третьей главе дается описание разработанного метода и реализованного алгоритма проверки типовой правильности РРТЬ-программы. Постановка задачи типового контроля заключается в следующем. Для извлекаемых из программы:

1. общего представления функций в виде системы рекурсивных уравнений ^ = г¡, [' = 1, п,

2. заданных типов базисных функций, входящих в г(,

необходимо определить, существуют ли такие типы функциональных переменных Т7;, £ = 1 ,п, что выполняются равенства

Суре(^) = type(тi), г = 1 ,п, где ¿уре(х) - тип терма х.

В диссертации разработан алгоритм, который позволяет определять является или не является система функциональных уравнений правильно типизированной. Алгоритм основан на известном результате о возможности явного представления минимального решения (минимальных фиксированных точек) для системы функциональных уравнений. Применение данного алгоритма позволило в среднем на 30% сократить время выполнения функциональных программ на языке ИРТЬ в сравнении с предыдущей реализацией, основанной на проверке типов непосредственно во время выполнения программы.

В четвертой главе описана реализация программной системы, созданной для эффективного выполнения функциональных программ на многоядерных компьютерах. Описание архитектуры системы выполнения РРТЬ-про грамм приведено на рис. 1. Она состоит из следующих компонентов (подсистем): лексического анализатора, синтаксического анализатора, подсистемы семантической проверки, подсистемы поиска рекурсивных функций, генератора сетевого представления, интерпретатора, подсистемы управления параллельным выполнением, библиотеки базисных функций, подсистемы вызова внешних процедур и подсистемы управления памятью.

Рис. 1. Архитектура и взаимодействие компонентов системы выполнения

РРТЬ-программ.

Для повышения эффективности анализа программы с точки зрения выявления параллелизма при ее выполнении введено сетевое представление функциональных программ. Формально сеть - это графическое представление термов т15 задающих функцию в виде системы: Р; = I = 1 ,п. Сетевое представление строится для каждого терма т; индуктивно следующим образом.

1. Если терм т есть базисная функция или функциональная переменная, то ее представление имеет:

- т -

2. Если т = тг * т2, то графическое представление т имеет вид:

3. Если г = т-! -» г2,т3, то графическое представление т имеет вид:

Для вычисления значения функций, представленных в виде сетей, в системе выполнения РРТЬ-программ используется интерпретатор. Интерпретатор обходит сеть «слева направо» и в зависимости от типа конкретного узла производит вычисление значений базисной функции, выполняет переход к схеме, представляющий правую часть функциональной переменной, порождает новый параллельный процесс вычислений (*-узел) или принимает решение о выборе пути продолжения вычислений (-»-узел).

Реализация системы управления параллельными процессами использует средства нитевого программирования. Каждая нить, далее называемая рабочей нитью (РН), выполняет задание - процесс вычисления значения функции, представленной в сети. При этом во время прохождения интерпретатором *-узлов сети могут порождаться другие задания. Каждому заданию будет соответствовать один из параллельных процессов вычислений, порожденных в программе операцией *. По сути, соединенные операцией * два терма эквивалентны порождению двух процессов вычислений, первый из которых будет выполняться в контексте текущего задания, а для второго порождается новое задание. Порожденные задания добавляются в специальную рабочую очередь (РО), существующую отдельно для каждой рабочей нити. Кроме того, в системе выполнения РРТЬ-программ имеется планировщик заданий, который производит поиск новых заданий для рабочей нити, если она простаивает.

Количество рабочих нитей задает программист перед выполнением функциональной программы и в процессе выполнения оно не изменяется.

Для того чтобы полностью использовать имеющиеся в компьютере процессоры (ядра), число РН должно быть не меньше, чем количество физических ядер в компьютере. Применение такого подхода позволяет избежать работы с большим числом одновременно выполняющихся нитей, которая неизбежно привела бы к большим накладным расходам.

РН берет новое задание для выполнения из конца своей очереди по принципу LIFO (рис. 2а). Однако если эта очередь пуста, то нить вынуждена искать новое задание в очереди другой нити, которое извлекается из очереди по принципу FIFO (рис. 26). Это, во-первых, позволяет осуществлять миграцию более сложных с вычислительной точки зрения заданий на другие нити и, во-вторых, локализовать данные при выполнении заданий, взятых из собственной очереди. Заметим, что можно было бы использовать общую очередь для заданий, сохраняя описанную логику управления их выполнением. Однако обращение к общей очереди множества нитей требует синхронизации доступа к ней, которая является достаточно затратной по времени операцией.

Рис. 2. Организация взаимодействия РН с РО.

Способность любой системы управления параллельными процессами динамически регулировать сложность (зернистость) порождаемых процессов является чрезвычайно важной проблемой для достижения минимального времени выполнения параллельных программ. Для управления сложностью заданий в реализованной системе был использован подход, при котором для параллельного выполнения назначаются только участки сетей, содержащие две и более рекурсивные функции по каждому из путей, порожденных операцией *. Например, на рис. 3 в случаях а) и б) вычисления будут производиться последовательно, в то время, как в ситуации в) для вычисление значений функций, задаваемых уравнениями Р и С, будет порождаться новое задание.

Рис. 3. Возможные варианты сетей с оператором *. Здесь fug- базисные функции; F и G - функциональные переменные, правые части которых содержат рекурсию.

Для увеличения эффективности работы интерпретатора важное значение имеет форма внутреннего представления данных и кортежей в системе. По характеру реализации и работы с данными в языке FPTL введено разделение типов данных на две группы.

• Элементарные типы данных. Элементарным типом данных будем называть такой тип данных, который может быть представлен одной неделимой областью памяти. К этим типам данных относятся int, real и bool.

• Составные типы данных. К составным типам данных в FPTL относятся string, Array и АТД. Эти типы данных не могут быть представлены как неделимые области памяти и их реализация требует учитывать некоторые аспекты работы интерпретатора (например, систему сборки мусора). Составные типы данных реализуются через промежуточную структуру данных - дескриптор составного типа данных.

Кортежи данных в системы выполнения FPTL-программ реализованы на основе динамически расширяемых массивов. Данная реализация концептуально напоминает работу с локальными переменными в стеке, применяемую в императивных языках программирования. В языке FPTL в качестве локальных переменных выступают кортежи данных на входе функций. Организация работы с кортежами данных с помощью стека позволяет добиться следующих преимуществ.

1. Снижается количество запросов к системе управления памятью, поскольку обращения к ней производятся только при заполнении стека.

2. Сохраняется локальность данных: память выделяется большой непрерывной областью и элементы данных кортежей располагаются «поблизости». Такое размещение данных хорошо сочетается с принципами организации работы кэш-памяти процессора. В главе также описаны решения принятые для реализации управления памятью к работы с внешними процедурами. В процессе выполнения функциональной программы возникает потребность динамически выделять и освобождать области памяти. В реализациях большинства современных программных систем динамическая память выделяется из области, называемой кучей. Большая интенсивность запросов к куче приводит к увеличению накладных расходов на обеспечение синхронизации. Для решения этой проблемы используется механизм локального по отношению к нити выделения памяти (thread-local allocation). Другой задачей системы управления памятью является контроль над временем жизни выделенной памяти. Поскольку язык FPTL, как и большинство высокоуровневых функциональных языков программирования, не предоставляет средства для ручного управления памятью, то эта функция выполняется с помощью отслеживающего сборщика мусора.

В пятой главе представлены результаты вычислительных экспериментов по оценке эффективности разработанной системы выполнения FPTL-программ на многоядерных компьютерах, а также сравнение результатов экспериментов с аналогичными для системы параллельного выполнения GHC, созданной для языка Haskell. В таблице 1 дается описание наборов программ, которые были использованы в экспериментах.

Программа Описание

Fib Вычисление 42-го числа Фибоначчи по рекурсивной схеме.

Integ Вычисление интеграла функции f{x) = 1 /{х * ех) на отрезке [10 6, 10] с точностью 10"5 адаптивным методом трапеций.

Sorti Быстрая сортировка односвязных списков размером в 1000000 случайных вещественных чисел, равномерно распределенных на отрезке [-1, 1]

Sort2 Быстрая сортировка массивов размером в 1000000 случайных вещественных числе, равномерно распределенных на отрезке [-1, 1]

Mull Умножение матриц размерности 600 (реализация на базе массивов).

Mul2 Умножение матриц размерности 600 (реализация на базе списков).

FFT Быстрое преобразование Фурье суммы трех синусоидальных сигналов, заданных списком значений функции на 217 точках.

Таб. 1. Описание тестовых программ на языке БРТЬ.

В качестве критериев для оценки эффективности применялись зависимости времени выполнения параллельной программы и относительного ускорения от количества ядер компьютера.

На рис. 4-7 приведены результаты вычислительных экспериментов с использованием системы выполнения языка ИРТЬ и описанных тестовых программ.

Рис. 4. Время выполнения программ Integ и Fib в зависимости от количества

ядер.

Рис. 5. Относительное ускорение выполнения программ Integ и Fib в зависимости от количества ядер.

Рис. 6. Время и относительное ускорение выполнения программ умножения матриц в зависимости от количества ядер.

Рис. 7. Время и относительное ускорение выполнения сортировок в зависимости от количества ядер.

В таблице 2 приведено описание набора тестовых программ на языке Haskell.

Программа Описание

H_Fib Вычисление 42-го числа Фибоначчи по рекурсивной схеме.

H_Integr Вычисление интеграла функции f{x) = 1/{х * ех) на отрезке [10~6, 10] с точностью 10"5 адаптивным методом трапеций.

H_Sort Быстрая сортировка односвязных списков размером 106 случайных вещественных чисел, равномерно распределенных на отрезке [-1, 1].

H_Mul Умножение матриц порядка 600. Реализация матриц на базе вложенных списков.

Таб. 2. Тестовые программы на языке Haskell.

На рис. 8-9 приведены результаты экспериментов с использованием описанных тестовых программ на языке Haskell.

Рис. 8. Время выполнения тестовых программ на языке Haskell в зависимости

от количества ядер.

Рис. 9. Относительное ускорение выполнения тестовых программ на языке Haskell в зависимости от количества ядер.

Проведенные эксперименты приводят к следующим заключениям.

1. FPTL-программы в общем случае неплохо масштабируются на небольшом числе ядер (< 4), с увеличением числя ядер ускорение замедляется из-за увеличения накладных расходов на управление.

2. По критерию ускорения реализация FPTL не уступает реализации Haskell, а в некоторых случаях дает лучшие результаты. Это говорит о том, что разработанные механизмы управления параллельным выполнением программ реализованы в FPTL не менее эффективно, чем в Haskell. Однако, если сравнивать реализацию FPTL с Haskell по времени выполнения программ, то заметно очевидное преимущество реализации языка Haskell в силу того, что перед выполнением программы на языке Haskell компилируются. Это преимущество особенно заметно на задачах вычислительного характера и менее заметно для программ, оперирующих абстрактными типами данных. Естественным вариантом устранения этого недостатка является замена в FPTL затратного по времени режима интерпретации на режим компиляции.

3. При работе со сложными списковыми структурами данных сборка мусора вносит серьезные накладные расходы, что существенно влияет на ускорение времени параллельного выполнения программ. Это наблюдается как в реализации языка FPTL, так и в реализации языка Haskell.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Перечислим основные результаты диссертационной работы:

1. Проведен сравнительный анализ методов распараллеливания вычислений в современных функциональных языках программирования и способов их реализации.

2. Разработаны и исследованы методы и алгоритмы эффективного параллельного выполнения функциональных программ на многоядерных компьютерах.

3. Разработан и реализован алгоритм контроля типовой корректности программ.

4. Создана интегрированная система параллельного выполнения FPTL-программ на многоядерных компьютерах, которая включает следующие подсистемы:

— интерпретатор FPTL-программ,

— управление параллельными процессами выполнения ФП,

- статический анализ типовой корректности программы.

5. Проведено экспериментальное исследование эффективности созданной системы, которое доказало правильность принятых проектных решений и конкурентоспособность всей системы в целом.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ:

1. Кутепов В.П., Шамаль П.Н Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах. // Известия РАН. Теория и Системы Управления, 2014, № 3, с. 46-60.

2. Бочаров И.А., Кутепов В.П., Шамаль П.Н Система типового контроля программ на языке функционального программирования FPTL. // Программные продукты и системы, 2014, № 2, с. 11-17.

3. Kutepov V.P., Shamal P.N. Implementation of Functional Parallel Typified Language (FPTL) on Multicore Computers. // Journal Of Computer and Systems Sciences International. 2014. Vol. 53(3). P. 345-358.

Материалы конференций:

1. Кутепов В.П., Шамаль П.Н Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах. // Радиотехника, электротехника и энергетика: 19 Международная научно-техническая конференция студентов и аспирантов, Москва, 28 февр. - 1 марта 2013: Тезисы докладов. Т. 2. Изд. дом. МЭИ, 2013, с. 46-46.

2. Кутепов В.П., Шамаль П.Н Реализация языка функционального параллельного программирования FPTL на многоядерных вычислительных системах. // Труды конференции «Параллельные вычисления и задачи управления», ИПУ РАН, 24-26 октября 2012, URL: http://paco2012.ipu.ru/procdngs/E201.pdf (дата обращения: 30.09.2014)

Подписано в печать: 19.11.14

Объем: 1,0 п.л. Тираж: 100 экз. Заказ X» 543 Отпечатано в типографии «Реглет» г. Москва, Ленинский проспект, д.2 (495) 978-66-63, www.reglet.ru