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

[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]

© 2002-2003 А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин, Д.В. Привалихин

Введение

История языков параллельного программирования насчитывает не один десяток лет. За это время были придуманы и апробированы разнообразные методы написания программ и способы их отображения на архитектуры параллельных вычислительных систем (ПВС). Существуют различные варианты классификации решений, полученных в этой области, одним из простых среди которых является выделение трех различных способов задания параллелизма [Алгоритмы, Хоар, Легалов-1994]:

1. Использование последовательного программирования с дальнейшим автоматическим распараллеливанием разработанных программ.
2. Применение языка программирования, обеспечивающего явное формирование потоков параллельного управления. Такой язык по существу является расширением традиционных последовательных языков за счет добавления операторов распараллеливания. При этом уровень параллелизма, достигаемый при программировании, полностью контролируется разработчиком и может меняться в зависимости от конкретных условий.
3. Опора на язык, описывающий максимальный параллелизм, что обеспечивается заданием только информационных связей. Предполагается, что программа будет выполняться на ВС с бесконечными ресурсами, а выполнение операторов будет происходить немедленно по готовности данных. Адаптация программы к архитектуре конкретной ПВС осуществляется автоматически путем сжатия параллелизма в соответствии с ресурсными ограничениями.

Каждый из перечисленных подходов обладает своими достоинствами и недостатками.

Параллелизм и последовательное программирование

Последовательное программирование выглядит весьма привлекательным, так как, на первый взгляд, позволяет:

• применять опыт, накопленный в течение многолетней эксплуатации вычислительных машин с традиционной архитектурой;
• разрабатывать программы, совершенно не зависящие от особенностей параллельной вычислительной системы;
• использовать продукты, накопленные за многие годы создания программного обеспечения.
• не заботиться о параллельной организации программы, полагаясь в дальнейшем на то, что система автоматического распараллеливания решит все вопросы по эффективному переносу программ на любую параллельную систему [Вальковский].

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

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

Архитектурно-зависимые языки параллельного программирования

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

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

Языки параллельного программирования, использующие явное управление, позволяют описать максимальный параллелизм задачи, но обеспечивают это не самым удобным способом, так как:

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

Функциональные и потоковые языки

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

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

В качестве одного из вариантов решения предлагается функциональный язык параллельного программирования (ФЯПП) "Пифагор", обладающий следующими характеристиками:

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

Фундамент работы

Нельзя сказать, что работа проводилась без учета знаний, накопленных в данной предметной области. Издавна существует ряд функциональных и потоковых моделей параллельных вычислений и языков программирования, построенных на их основе. К ним можно отнести схемы потока данных Денниса [Dennis, Деннис], функциональный язык программирования FP Бэкуса [Backus], язык LAU [Gelly] и другие [Arvind, Dennis, Алгоритмы, Хендерсон]. В каждый из этих языков и его модель заложены определенные методы порождения и синхронизации параллельных процессов, не позволяющие, в то же время, обеспечить максимальный параллелизм ряда задач из-за присущих ограничений механизма описания параллельных процессов.

Одним из факторов, ограничивающих параллелизм, является наличие в модели вычислений (МВ) языка элементов управления, тем или иным образом приводящих к разделению процессами общих вычислительных ресурсов. В частности, в схемах потока данных (СПД) Денниса таким ресурсом является узел слияния потоков данных. При одновременной обработке нескольких независимых потоков, поступающих на вход такой СПД, происходит задержка вновь поступающих данных на узлах слияния перед входом в разделяемый ресурс, например циклический фрагмент программы. Проблема решается введением специальных ресурсно-независимых моделей, в которых предполагается, что для каждого вновь формируемого процесса выделяется свой ресурс, а их максимальное число неограниченно. На уровне языковых и модельных средств описание неограниченности задается отказом от конвейерного параллелизма за счет предоставления своих программных и аппаратных ресурсов каждому новому набору данных, использованием рекурсии вместо циклов или описание циклических процессов с применением механизма раскраски, как это сделано в МВ Арвинда-Гостелоу [Арвинд].

Другой причиной, ограничивающей параллелизм функциональных языков является их набор функций и программно-формирующих операций, специально ориентированный на последовательные вычисления или ограниченный параллелизм. В частности, в ЛИСП операторы для работы с данными обеспечивают выборку только одной компоненты. FP [Backus] не предусматривает распараллеливание на уровне независимых операторов. Для того чтобы язык программирования мог поддерживать параллелизм любого типа, он должен содержать операторы размножения информационных потоков, их группирования в списки данных различного уровня вложенности, одновременного выделения из списков нескольких независимых и разнородных по составу групп. Обычно такие возможности заложены в потоковые МВ и построенные на их основе языки.

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

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

Цели и задачи работы

Цель работы

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

Задачи:

1. Разработка и исследование функциональной модели параллельных вычислений.
2. Разработка функционального языка параллельного программирования, обеспечивающего описание решаемой задачи путем задания только ее информационного графа.
3. Разработка транслятора с функционального языка параллельного программирования.
4. Разработка интерпретирующей системы, позволяющей выполнять написанные функциональные параллельные программы в последовательном режиме (на однопроцессорных системах).
5. Апробация ФЯПП, заключающаяся в написании тестовых программ и проведении экспериментов с языковыми конструкциями.

[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]