научная статья по теме ГРАФ-СХЕМНОЕ ПОТОКОВОЕ ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ: ЯЗЫК, ПРОЦЕССНАЯ МОДЕЛЬ, РЕАЛИЗАЦИЯ НА КОМПЬЮТЕРНЫХ СИСТЕМАХ Кибернетика

Текст научной статьи на тему «ГРАФ-СХЕМНОЕ ПОТОКОВОЕ ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ: ЯЗЫК, ПРОЦЕССНАЯ МОДЕЛЬ, РЕАЛИЗАЦИЯ НА КОМПЬЮТЕРНЫХ СИСТЕМАХ»

Москва, МЭИ (технический ун-т) Поступила в редакцию 14.07.11 г.

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

Введение. Современная компьютерная индустрия способна производить компьютерные системы (КС), количество вычислительных компонентов которых уже сегодня насчитывает сотни тысяч единиц с предельным быстродействием 1015—1016 оп/с [1]. Однако создание и эффективное использование больших КС требует решения целого комплекса проблем помимо чисто технических, связанных с охлаждением и потреблением энергии.

Во-первых, это касается новых архитектурных решений, которые должны обеспечить возможность простого увеличения масштаба КС и уменьшить среднее время передачи данных между размещенными в пространстве компонентами КС при заданной пропускной способности каналов обмена. Во-вторых, это создание методов, аппаратных и программных средств для эффективного управления КС, которое реализует планирование процессов, оптимальное распределение ресурсов и реагирование на отказы. Для этого нужны не только аппаратные измерительные и контролирующие средства с малой реакцией, но и включение в архитектуру КС в качестве ее надстройки системы управления, способной расширяться и модифицироваться в связи с изменением масштаба и архитектуры КС [2—4]. В-третьих, необходимо создание комплекса интегрированных и в некотором смысле универсальных программных средств, существенно повышающих эффективность разработки сложных параллельных программ, их анализа, оптимизации и выполнения на КС [5—9].

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

Хотя параллелизм в его начальном смысле понимается как множество одновременно протекающих и взаимодействующих процессов, его экспликация на задачном уровне, т.е. при переходе от задачи к параллельной программе, лежит в сфере декомпозиции задачи и установления информационной зависимости между ее компонентами. Информационная зависимость между компонентами определяется как транзитивное замыкание непосредственной информационной зависимости. При этом два компонента информационно независимы, если между ними отсутствует информационная зависимость. Это фундаментальное условие возможности параллельного или одновременного выполнения действий, предписанных независимым компонентам [5, 6].

Язык граф-схемного потокового параллельного программирования (ЯГСПП) изначально создавался таким образом, чтобы его средствами можно было естественно представлять декомпозиционную структуру задачи в виде граф-схемы программы, явно указывая зависимости по данным между ее компонентами и только их [7, 9].

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

* Работа выполнена при финансовой поддержке РФФИ (проект № 11-01-00232-а).

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

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

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

Возможность программирования компонентов граф-схемной программы на языках последовательного программирования решает другую задачу — обеспечение возможности использования уже хорошо опробованных средств разработки, анализа и оптимизации последовательных программ. В системе граф-схемного потокового параллельного программирования управление процессами параллельного выполнения программы на КС представляет собой самостоятельную подсистему, предназначенную для планирования параллельных процессов и распределения ресурсов без участия программиста [3, 4]. Программист может достигать большей эффективности выполнения программы (уменьшения времени ее выполнения и увеличения использования ресурсов КС), варьируя при разработке параллельной программы степень (глубину) ее распараллеливания, вводя или исключая упреждающие процессы, наконец, принципиально изменяя композиционную структуру программы [5, 6]. Это позволяет приблизить средства параллельного программирования к заданному уровню, исключить участие программиста в планировании процессов и назначении ресурсов, как это предполагается в системах процессного программирования MPI и MULTITHREADING.

1. Язык граф-схемного потокового параллельного программирования. ЯГСПП формально можно представить в виде пары языков (ЯГС, ЯИ), где ЯГС — язык представления граф-схем, ЯИ — язык интерпретации. Таким образом, граф-схемная параллельная программа (ГСПП) задается в виде двух компонентов (ГС, I), где ГС — граф-схема программы на ЯГС, отражающая в модульной форме декомпозиционную структуру задачи, и I — интерпретация, сопоставляющая каждому модулю ГС подпрограмму на одном из ЯИ.

1.1. Определение ГС. Пусть М = — не более чем счетное множество модулей (базисное множество), где mi — имя модуля, ini и outi — упорядоченные множества или кортежи входных точек (входов) и выходных точек (выходов) модуля mi.

В общем случае у модуля может быть несколько групп входов. В связи с представлением в ГСПП условных конструкций входные и выходные точки модулей разделяются на две группы, образуя два кортежа безусловных и условных входов. Точки кортежа безусловных входов изображаются в виде круглых точек, а точки безусловного кортежа — в виде квадратных точек. Данные, поступающие на входные точки модуля безусловного кортежа его входов, однозначно связываются с кортежем входных параметров подпрограммы, сопоставляемой модулю в интерпретации (см. далее). По данным булевского типа, поступающим на условные входы модуля, определяется необходимость применения сопоставленной ему подпрограммы к кортежу данных на безусловных входах модуля. Условием этого является значение "истина" на всех условных входах модуля.

На рис. 1 приведено графическое изображение модуля с i-м количеством групп входов, у каждой из них по два кортежа входных точек, один из которых представляет безусловные входы, а другой — условные.

ГС в базисе M определяется в виде четверки (М', C, Рвх, Рвых). Здесь M' — конечное подмножество модулей из M, C — функция-предикат, задающая связи между выходными и входными точками модулей: C: OUT х IN ^ , где IN и OUT — множества всех входных и выходных точек модулей из M'. Для in е IN и out е OUT C(out, in) = 1, если существует связь между выходной

mj 1 2 ki 12 m; 1 2 kj •• □—^ -• ••• •—□-□ ••• □—

группа входов 1 группа входов i

1 2 n Рис. 1. Графическое изображение модуля

точкой out некоторого модуля ГС и входной точкой in другого (возможно, того же самого) модуля; в противном случае C(out, in) = 0,

В определении ГС Рвх е IN* и Рвых е OUT* обозначают кортежи входных (безусловных) и выходных (безусловных) точек ГС Кортежи входных точек ГС используются для задания данных, к которым должна применяться ГСПП, а кортеж выходных точек идентифицирует выходные точки модулей ГС, на которые поступают результаты выполнения ГСПП

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

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

📎📎📎📎📎📎📎📎📎📎