Математическая энциклопедия - программирование параллельное

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

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

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

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

Предпосылкой для распараллеливания выражений служит тот факт, что входящие в них операции и функции удовлетворяют нек-рым соотношениям, индуцирующим на всем множестве выражений отношение эквивалентности по результатам (например, для арифметич. операций ассоциативность, коммутативность, дистрибутивность). Задача распараллеливания состоит в построении по заданному выражению Еэквивалентного выражения E', к-рое может быть исполнено за наименьшее число параллельных шагов, где параллельный шаг это совокупность действий, выполняемых одновременно на разных вычислителях (процессорах). Напр., выражение

преобразуется в эквивалентное выражение

исполнение к-рого осуществляется за 3 параллельных шага. Отношение числа параллельных шагов исполнения к числу последовательных шагов наз. ускорением распараллеливания. Любое арифметич. выражение с поперандами может быть вычислено параллельно за О(log n).шагов с использованием п процессоров. Относительная простота алгоритмов распараллеливания выражений позволяет реализовать их автоматически в ЭВМ с помощью специальных программ или аппаратными средствами.

Большее ускорение может быть получено за счет распараллеливания обработки структурных данных. В алгоритмич. языках типа алгол или фортран выражения над структурными данными программируются с помощью операторов цикла вида FOR I=A, В, С,DO S, где I целочисленный параметр цикла, А - его начальное значение, В - конечное значение, С - шаг изменения параметра, S - тело цикла, задающее действия, выполнимые на одном шаге итерации. Для распараллеливания системы вложенных циклов рассматривается n-мерное целочисленное пространство итераций с координатными осями I1, I2, . . ., In. Выполнение K1 -й итерации по параметру Il, K2- йитерации но параметру I2, . . ., К п- йитерации по параметру I п изображается точкой (K1, . . ., К n).этого пространства. В пространстве итераций ищется семейство поверхностей, удовлетворяющих условию: все итерации ( К 1, . . ., К п), лежащие на любой из этих поверхностей, могут выполняться параллельно. Для программного представления параллельной обработки структурных данных необходимы специальные языковые средства. С этой целью разработаны модификации существующих языков программирования (в основном фортрана), в к-рые вводятся параллельные операторы циклов, напр., вида

FOR ALL (I, J, K)/[1:N; 1:L; 1:M],

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

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

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

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