Программирование Параллельное

Раздел программирования, связанный с изучением и разработкой методов и средств для: а) адекватного описания в программах естественного параллелизма моделируемых в ЭВМ и управляемых ЭВМ систем и процессов, б) распараллеливания обработки информации в многопроцессорных и мультипрограммных ЭВМ с целью ускорения вычислений и эффективного использования ресурсов ЭВМ. В отличие от программирования последовательных вычислений, концептуальную основу к-рого составляет понятие алгоритма, реализуемого по шагам строго последовательно во времени, в П. п. программа порождает совокупность параллельно протекающих процессов обработки информации, полностью независимых или связанных между собой статическими или динамическими пространственно-временными или причинно-следственными отношениями. Вычислительный параллелизм выступает в разных конкретных формах в зависимости от этапа программирования, от сложности параллельных фрагментов и характера связей между ними. В текстах, описывающих задачи и программы, можно выделить уровни сложности фрагментов, для к-рых задача распараллеливания, т. е. составления параллельной программы, решается по-разному: выражения со скалярными данными; выражения над структурными данными (векторы, матрицы, деревья и т. п.), записываемые в алгоритмич. языках с помощью операторов цикла; подзадачи и подпрограммы; независимые задачи и программы в мультипроцессорных системах. Предпосылкой для распараллеливания выражений служит тот факт, что входящие в них операции и функции удовлетворяют нек-рым соотношениям, индуцирующим на всем множестве выражений отношение эквивалентности по результатам (например, для арифметич. операций — ассоциативность, коммутативность, дистрибутивность). Задача распараллеливания состоит в построении по заданному выражению Еэквивалентного выражения 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], при исполнении к-рых тело цикла копируется по определенным правилам на параллельно исполняемые итерации. Эти языки снабжаются также более развитыми средствами описания структурных данных и средствами управления размещением их в памяти для обеспечения быстрого параллельного доступа к структурным данным. Дальнейшее повышение уровня языков программирования состоит в использовании групповых операций над структурными данными таких, как покомпонентное умножение и сложение векторов и матриц, скалярное и векторное произведение, обращение матриц и т. п. Применение таких языков позволяет заменить автоматич. распараллеливание последовательных циклов, к-рое на практике осуществимо, но относительно сложно, на непосредственное задание параллельных групповых операций. Параллельные выражения могут исполняться асинхронно или синхронно. В первом случае не фиксируется связь между временами выполнения параллельных операций, во втором случае времена их выполнения должны вкладываться в жесткие рамки тактированного расписания. Если операции имеют фиксированные длительности и известно число процессоров, доступных в любой момент исполнения, то целесообразно применять синхронный метод вычислений, в противном случае — более гибкий асинхронный. Управление асинхронным исполнением выражений основано на потоковом принципе: операция может выполняться в любой момент времени после того, как для нее подготовлены операнды. Распараллеливание на уровне подзадач и подпрограмм существенно сложнее. В этом случае параллельные процессы могут иметь сложную внутреннюю структуру. длительность их выполнения не фиксирована; процессы взаимодействуют, обмениваясь данными и обращаясь к общим ресурсам (общие данные и программы в памяти, внешние устройства и т. п.). Автоматич. распараллеливание на этом уровне требует сложных алгоритмов анализа задач и учета динамич. ситуаций в системе. В связи с этим особое значение имеет создание языков П. п., позволяющих программисту непосредственно описывать сложные взаимодействия параллельных процессов. В большинстве языков и систем П. п. принята частично асинхронная организация вычислений. В языках П. п. имеются средства выделения (порождения) параллельных процессов и средства их синхронизации, к-рые в аппаратуре поддерживаются механизмами прерываний — принудительных остановок процессов с запоминанием их текущих состояний и с последующей активацией или возобновлением др. процессов. Наиболее известными и простыми программными механизмами синхронизации являются семафоры и события. Семафор — это специальная управляющая переменная, принимающая целочисленные значения. Семафор обычно связан с нек-рым конфликтным ресурсом. К семафору применимы только две операции Ри V. Если в ходе исполнения процесса встретится операция P(s), где s — семафор, то процесс может продолжаться с уменьшением значения s на 1 только в том случае, когда значение s положительно; в противном случае он приостанавливается и занимает место в очереди q(s).процессов, ждущих соответствующего ресурса. Операция Vувеличивает значение s на 1 и возобновляет первый в очереди q(s).процесс. Механизм семафоров широко используется в языках управления процессами в операционных системах ЭВМ и в ряде универсальных языков программирования (напр., алгол-68). Механизм событий включает управляющие переменные, текущие значения к-рых отмечают наступление каких-либо программных или системных событий (завершение процессов, прерывания и т. п.), и специальные операторы ожидания событий. Семафоры и события являются универсальными средствами синхронизации, но они слишком примитивны, и неправильное их использование может привести к аварийным ситуациям таким, как взаимная блокировка процессов (напр., два процесса требуют для своего продолжения по два ресурса и каждый "захватил" по одному). Стремление повысить надежность программирования приводит к появлению более сложных механизмов синхронизации: "почтовые ящики" — особые структуры для обмена сообщениями, для к-рых фиксированы правила работы с ними параллельных процессов; мониторы — наборы процедур и данных, к к-рым процессы могут обращаться только поочередно и к-рые содержат заданные программистом правила организации взаимодействий. Чисто асинхронное П. п. используется для организации вычислений в распределенных вычислительных системах, в к-рых полностью исключены конфликты по ресурсам. Стремление упростить организацию взаимодействий между процессами с общими ресурсами привлекает внимание к асинхронным методам вычислений, в к-рых разрешен нерегламентированный доступ параллельных процессов к общим ресурсам. Напр., разрабатываются асинхронные алгоритмы, в к-рых параллельные процессы обмениваются данными с общей памятью, причем неупорядоченный доступ к памяти не мешает достижению однозначного результата. В теории П. п. разрабатываются формальные модели параллельных программ, процессов и систем и с их помощью исследуются различные аспекты П, п.: автоматич. распараллеливание последовательных алгоритмов и программ; разработка параллельных методов вычислений для разных классов задач и разных классов параллельных вычислительных систем- оптимальное планирование параллельных вычислений и распределение ресурсов между параллельными процессами; формальное описание семантики программ и языков П. п. Среди таких моделей — схемы параллельных программ, отражающие с разной степенью детализации структурные свойства программ; графовые модели и асинхронные сети ( Петри сети), являющиеся математич. абстракциями дискретных процессов и систем. Лит.:[1] Котов В. К., "Кибернетика", 1974, № 1, с. 1-16; №2, с. 1-18; [2] Нариньяни А. С., там же, № 3, с. 1-15; № 5, с. 1 — 14; [3] Фаддеева В. Н., Фаддеев Д. К., там же, 1977, № 6, с. 28-40; [4] Кuсk D. J., "Сотр. Surveys", 1977, v. 9, Mi 1, p. 29-59. В. Е. Котов.