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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение Вычислительный центр

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

Панкратов Сергей Александрович

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

05.13.11. - Математическое и программное

обеспечение вычислительных мззин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 1992

Работа выполнена в Вычислительном центре СО РАН. Научный руководитель : доктор физико-математических

наук, профессор H.H. Миренков

Официальные оппоненты: доктор физико-математических

наук, профессор, P.M. Нуриев кандидат технических наук, доцент, A.B. Гаврилов

Ведущая организация : Институт математики СО РАН

Защита состоится ^-etij 1992 г.

в час. мин. на заседании специализированного совета

К 003.93.01 по присуждению степени кандидата наук при Институте систем информатики СО РАН по адресу: 630090, Новосибирск-90, пр. академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале отделения ГПНТБ СО РАН ( пр. ак. Лаврентьева, 6 ).

Автореферат разослан "3" 1992 г.

Ученый секретарь Специализированного Совета К 003.93.01 к.ф.-м.н.

М.А. Бульонков

, . "" j ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

¡V-лГ ■

Актуальность темы, в настоящее время разработка перспективной высокопроизводительной, вычислительной тб^Зоси, в частности супер-ЭВМ, характеризуется широким проникновением в аппаратное и программное обеспечение фундаментальных принципов параллельной обработки. Одним из направлений развития современных супер-ЭВМ является создание многопроцессорных вычислительных систем (МВС).

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

В настоящее время концептуальные работы по крупноблочному конструированию проблемно-ориентированных МВС развиваются как у нас в стране, так и за рубежом. Опыт создания подобных систем есть в Болгарии (ИЗОТ I703E), в нашей стране (МВС на основе СП ЕС-2706 в ИКИ РАН, ECI068.Í7 в НИЦЭВТ, МВС СИБИРЬ в ВЦ СО РАН), США (МВС на основе процессоров фирм ibm, fps, apollo, например, системы icaf и lepics) и др. Сказанное выше позволяет сделать вывод, что разработка методов и инструментальных средств параллельного программирования для таких МВС является весьма актуальной задачей.

з

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

Основными задачами, решаемыми в,диссертации, являются:

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

• разработками реализация операционных сред МАРЕХ для МВС ЕС-1068 Л7 и ОБЬ для МВС СИБИРЬ; '

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

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

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

На основе анализа архитектуры МВС сформулированы требования к разрабатываемым операционным средам, предложены эвристические алгоритмы для оптимизации распределения и использования ресурсов. Данные требования и алгоритмы положены в основу реализации операционных сред МАРЕХ и ОБЬ, позволяпцих разрабатывать и выполнять параллельные программы, динамически настраивающиеся на число доступных СП и топологию связи между ними, при необходимости использующие все ресурсы МВС

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

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

Практическая ценность. Предложенные алгоритмы распределения ресурсов МВС, а такке развиваемый подход к интеграции математического обеспечения отдельных СП крупноблочной МВС в единую программную среду могут быть использованы при разработке операционных сред для МВС нового поколения, создаваемых на базе микропроцессоров и транспьютерных систем. ОСПП МАРЕХ и ОБЬ находятся в промышленной и опытной эксплуатации в ряде организаций и применяются для конструирования параллельных программ и пакетов программ в геофизике, обработке сигналов, электрофизике, молекулярной физике и других областях. Опыт их использования показывает, что время решения прикладных задач в МВС с 8-ю СП ЕС-2705 может быть уменьшено в 25-100 раз по сравнению со счетом в EC-I066. На основе операционной среды МАРЕХ в ВЦ СО АН СССР разработана Фортран-система параллельного программирования ИНЯ.

Реализация результатов исследования. Разработанные ОСПП внедрены и используются для разработки параллельных программ в КЦИИТ (София), ЦГЭ Миннефтепрома (Москва).

Публикации и апробация. По теме диссертации опубликовано 9 работ. Основные результаты диссертационной работы докладывались на Втором региональном семинаре "Распределенная обработка информации" (Новосибирск, 1937), на I Всесоюзной конференции "Супер-ЭВМ" (Минск,I98?), 8-м Всесоюзном семинаре "Параллельное программирование и высокопроизводительные структуры" (Алушта, 19881, 8-ой Сибирской школе по ППП "Программное обеспечение ЭВМ новых поколений" (Иркутск, 1989), Школе-семинаре "ЕС ЭВМ-89" (Киев,1989), Всесоюзной конференции "Высокопроизводительные МВС для комплексных центров математического моделирования" (Новосибирск,1989), Х-ом Всесоюзном семинаре "Параллельное программирование и высокопроизводительные системы: методы представления знаний в - информационных технологиях (Уфа,1990), Всесоюзной школе-семинаре "Многоуровневое структурное проектирование программных систем" (Планерское, 1991).

Структура и объем работа. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 98 наименований. Общий объем работы - 134 страниц.

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

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

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

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

В детерминированной теории расписаний рассматривается модель операций с заранее известными параметрами . (время выполнения, количество передаваемых данных). Большинство задач детерминированной теории расписаний являются ^-полными. В практическом плане представляет интерес те

частные постановки задач, для которых известны полиномиальные алгоритмы. В главе сделан обзор полиномиальных алгоритмов детерминированного планирования. Идеи, лежащие в их основе, широко используются при разработке приближенных, эвристических алгоритмов планирования. Непосредственное использование на практике известных полиномиальных алгоритмов затрудлительно из-за жестких ограничений, накладываемых на модель системы операций, например, требования равенства времени выполнения (uet- системы). Оптимальные алгоритмы для np-полных задач являются по своей сути направленным перебором и используются в тех. приложениях, где возможно статическое планирование, например, в компиляторах с параллельных языков. Их использование '-для динамического планирования в МЕС проблематично из-за больших накладных расходов. Однако, с увеличением вычислительной мощности МВС значение этих алгоритмов для практического применения будет возрастать.

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

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

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

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

Ряд исследований по структурам параллельных алгоритмов показывает, что существует большое число важных задач, для реализации которых достаточно линейных коммуникационных связей между процессорами. Это позволяет выделить для исследования в диссертации подкласс . крупноблочных иерархических МВС, конструируемых по следующей схеме: к управляющему универсальному вычислителю (УВ), например, ЕС ЭВМ, 1вм рс, по радиальной схеме подключаются подчиненные процессоры, в качестве которых могут рассматриваться СП, микропроцессоры и даже универсальные ЭВМ. Однородные процессоры образуют подсистему и могут объединяться общим интерфейсом. Этот интерфейс должен, как минимум, ,обеспечить связь каждого СП с двумя ближайшими соседями. В качестве интерфейса могут быть использованы каналы, с помощью которых собирается линейка или кольцо из процессоров, общая шина или память. УВ кроме обычных вычислительных функций выполняет также управлящие функции, передает в подчиненные процессоры данные, программы, инициирует счет, выполняет синхронизацию. Любой подчинеБШый процессор может рассматриваться как

управляющий для своих подчиненных СП и т.д.

В главе рассмотрена номенклатура и способы соединения СП для построения конкретных МВС. Для организациии вычислений в МВС рассматриваемого класса предложена иерархическая модель типа "старший - подчиненные взаимодействующие процессы", определяющая метод конструирования и выполнения параллельных программ. В этой модели процесс, выполняющийся на í-tom уровне иерархии МВС (старыий процесс), может динамически порождать, в общем случае, неоднородные подчиненные процессы i+i -го уровня. Подчиненные процессы могут взаимодействовать между собой и со старшим процессом как синхронно, так и асинхронно. Под процессом понимается программный фрагмент вместе с данными, которые он обрабатывает. Предложенная модель учитывает особенности архитектуры МВС, а так:.-е сохраняет преемственность последовательного программирования, обеспечивая плавный переход от последовательного программирования к параллельному.

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

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

ОСПП должна обеспечивать распределение вычислительных

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

В главе формулируется задача динамического распределения ресурсов в МВС и предлагаются, эвристические алгоритмы для ее решения. Одна из технологий выполнения прикладных программ в МВС состоит в следующем. Программы в процессе выполнения в УВ запрашивают в монопольное пользование (захватывают) на определенное время некоторое количество ресурсов (СП). После того как все вычисления на СП выполнены, процессоры освобождаются и могут быть использованы другими программами. Захват/освобоидение ресурсов выполняется каздой программой многократно. Среднее или максимальное время, на которое захватываются ресурсы, может быть оценено в динамике средствами ОСПП. Тогда задача распределения, ресурсов формулируется следущим образом.

Задано: т ресурсов г(, п независимых заданий т , п^ -количество ресурсов, запрашиваемых т и ^ - время, на которое захватываются ресурсы, 1=1,...,т, ¿=1,...,п. Под расписанием понимается список заданий, упорядоченный по убыванию приоритета на распределение ресурсов. Реализация расписания заключается в выборе задания т с наибольшим приоритетом к выделение ей первых п^ освободившихся ресурсов. Необходимо найти алгоритм построения расписания, с минимальным временем простоя ресурсов. ' .

Определение 1. Пусть б некоторое расписание, 11 и моменты времени освобожения ресурса г( соответственно до и после выполнения всех заданий из расписания - множество

индексов тех заданий, которые используют ресурс г( при реализации б. Тогда время простоя ресурсов определяется как

Для решения задачи предложен эвристический алгоритм с

параметрами <1 и ь, а=1....... ь=1,...,а. Рассмотрим алгоритм

для случая ь=1. При построении упорядоченного списка заданий на к-том шаге, к=1,2,... ,п-(<1-1), выбирается задание т с минимальным значением г1(т ,к). Если таких заданий несколько

используются дополнительные стратегии, определяемые минимумом f,(T.) и максимумом f,(T,). Если и после этого

Z J J J

остается неоднозначность выбора - выбирается любое задание,

f t (Tj,к) определяет основную стратегию выбора и вычисляется следующим образом. Рассматриваются все расписания вида s =(т ,...), составленные из d невыбранных на предыдущих шагах заданий. Тогда по определению f (т ,k)=min f(s ). Для

вычисления f, может быть использован" любой алгоритм, например, полный перебор. В диссертации показано, что для d=2

минимум достигается на расписании s =(т,,т ), где т любое

j j р р

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

f, и f, определяются как f„(T,)=t , t_(т )=m,. Интуитивное

3 2 J J 3 J J

обоснование стратегии 2 состоит в том, что задание с меньшим временем использования ресурсов меньше ухудшает (а часто улучшает) баланс загрузки ресурсов. Стратегия 3 осноЕвна на том, что задание с большим числом ресурсов наиболее вероятно приведет к вынужденному простою ресурсов и поэтому при прочих равных условиях его надо выбирать как можно раньше.

Описанный алгоритм имеет сложность nd при фиксировг-<яом п. При h > 1 алгоритм расширяется следующим образом. Стратегия f определяется аналогично случаю h=i, но выбирает не одно задание, а сразу список sh из h первых заданий в том расписании длины d, на котором достигается минимум функции F. Так как выбор может быть неоднозначным, далее к спискам sb применяются стратегии f и f , определенные как: f (sh)=max tj, f3(sh)=max nij, где максимум берется по всем заданиям из sw.

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

il

В третьей главе описываются операционные среды МАРЕХ и ОБЬ для крупноблочных МВС EC-I068.I7, СИБИРЬ.

EC-I068.17 состоит из управляющей ЭВМ EC-I068 и подключенных к ней по радиальной схеме через стандартный интерфейс от 1-го до 24-х СП ЕС-2706 - 38-и разрядных векторно-конвейерных процессоров с архитектурой типа "широкая команда", пиковой производительностью 12 Мфлопса, объемом памяти данных 4 Мбайта. СП могут■быть связаны между собой в линейку каналами юр-38 с пропускной способностью 6 Мбайт/с. До 8 СП могут быть подключены к устройству общей электронной памяти. МВС СИБИРЬ является развитием EC-I068.I7 и дополнительно включает в свой состав ассоциативный процессор ЕС-2720 , simd процессор ПС2000, а в перспективе и другие вычислители.

Операционная среда МАРЕХ била разработана как развитие метода доступа AiEX, входящего в состав базового математического обеспечения ЕС-2706. С точки зрения прикладного программиста APEX - это специальная библиотека подпрограмм, вызываемых оператором call из пользовательской Фортран программы в ЕС ЭВМ. APEX позволяет одной задаче захватить в монопольное пользование лишь один СП ЕС-2706, не позволяя тем cavMM организовывать параллельные вычисления на нескольких СП. В структуре МАРЕХ можно выделить монитор распределения СП между задачами, обращение к которому осуществляется подпрограммой mpinxt, и подсистему организации параллельных вычислений на распределенных СП, включающей средства формирования, запуска, взаимодействия и синхронизации процессов.

В обращении к монитору можно запросить конкретное число СП либо определить требуемое число СП диапазоном, к примеру, не менее 3 и не более 6, установить режим использования СП -монопольный или разделяемый. Число фактически распределенных СП возвращается в выходном параметре mpxnit, что позволяет в разрабатываемых программах динамически настраиваться на число доступных СП и обеспечивать переносимость программ между различными МВС. С целью обеспечения независимости от ОС ЕС (mvt,svs,os/vsi,mvs) разработка алгоритма распределения ресурсов в МАРЕХ основана на использовании общих для всех ОС ЕС макросредствах enq/deq(r) - распределить/освободить

абстрактный ресурс с именем п. Если ресурс занят, задача, выдавшая ehq, ставится в очередь с обслуживанием по алгоритму fifo. С каждым СП связывается абстрактный ресурс с уникальным именем. Специальный ресурс rinit используется для закрытия доступа к планировщику. При обращении к mpinit выполняются следующие действия:

(1) enq(rinit) - получить доступ к планировщику;

(2) распределить свободные ресурсы - enq(r_free);

(3) если не распределено -минимальное число требуемых СП, обратится к enq(r), где r - имя абстрактного ресурса, соответствующего произвольно выбранному занятому СП. После распределения r, перейти к (2);

(4) deq(rinit) - открыть доступ к планировщику.

Поскольку в кавдой программе имеется своя копия mpinit,

описанный алгоритм является децентрализованным, в нем не доступна информация о количестве задач, стоящих в очереди к каждому СП. Последнее особенность не позволяет управлять распределением ресурсов, в частности, предупреждать блокировки процессов. Для предотвращения блокировок все требуемые ресурсы должны распределяться одним запросом , т.е. дозахват ресурсов запрещен. Использование enq/deq в алгоритме помимо отрицательны:? имеет и положительное стороны: алгоритм существенно упрощается, так как, сложные проблемы синхронизации и обслуживания очередей решаются средствами ОС. •Время распределения одного СП в МАРЕХ в эз раза меньше чем в APEX. Ваэдой особенностью монитора МАРЕХ является отбраковка неисправных СП в процессе их распределения, что существенно повышает надежность прикладных программ.

В соответствии с принятой моделью вычислений программа в среде МАРЕХ выполняется в последовательно-параллельном режиме. Один из распределенных СП объявляется текущим с помощью подпрограммы mpset. Для текущего СП формируется подчиненный интерфейсный процесс, включающий пересылку данных в/из СП (подпрограммы apput, apget), пересылку и запуск микропрограмм в СП (обращение к библиотечным и пользовательским программам), синхронизацию интерфейс-СП (apwr). Выполнение сформированного процесса инициируется подпрограммой арехс. Далее

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

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

Операционная среда ОБЬ реализована в ОС муб, является развитием среды МАРЕХ, совместима с ней на уровне прикладной, программы и предоставляет ряд новых возможностей, таких как:

• централизованное распределение неоднородных СП, структур из СП (линейка, кольцо) на основе динамически изменяемых приоритетов;

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

• определение виртуальных СП;

• контроль за зацикливанием вычислительных процессов;

• автоматическое тестирование СП, и др. Компонентами ОБИ являются: программа инициализации и тестирования СП, подпрограммы пользовательского уровня, планировщик ресурсов (супервизорная программа), программа диалоговой связи с оператором, очередь запросов на захват ресурсов.

Программы операционных сред МАРЕХ и ОБЬ написаны на Фортране и ассемблере, вызываются из любого языка программирования ЕС ЭВМ. МАРЕХ состоит из 80 фортран-программ, (1500 операторов фортрана), 50 программ на ассемблере, (3200 операторов ассемблера).

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

В большинстве приложений применяются два основных метода распараллеливания. Первый основан на рабиении данных на части и проведения параллельных вычислений над этими частями в

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

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

В результате численного эксперимента на одном СП ЕС-2706 было получено ускорение в 12 раз. С ростом числа СП время решения уменьшалось практически линейно. В частности, на 4-ех СП задача решалась в 47 раза быстрее.

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

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

На одном СП было получено ускорение в 4.2. раза. С ростом числа СП уменьшение времени было близко к линейному при небольшом количестве процессоров. Дальнейшее увеличение количества СП приводило ко все более сильному отклонению от линейного закона. На 2-ух СП задача решалась примерно в 7.з раза быстрее, а на 4-ех СП. - только в 13.2 раза. Такой результат. объясняется прежде всего задержками считывания входных данных с диска, в результате чего параллельные процессы в СП запускаются с временным сдвигом. В главе рассмотрены возможные пути устранения этого эффекта.

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

При решении задачи на одном СП было получено ускорение в 4-и раза. С ростом числа СП уменьшение времени было близко к линейному. На 2-ух СП задача решалась в 7.7 раза быстрее, на 4-ех СП - в 14 раз. Анализ результатов эксперимента позволил сделать вывод, что при наличии прямой связи между СП (не через УВ) даже такой же пропускной способности как связь СП-ЕС ЭВМ, при решении данной задачи будет наблюдаться линейное ускорение. Вывод основан на экспериментальном факте: основной причиной отклонения от линейного закона является рост времени выполнения управляющей программы в ЕС ЭВМ, что в свою очередь связано с расходами на запуск параллельных процессов на каждую итерацию. Эти расходы будут отсутствовать при наличии прямой связи СП-СП.

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

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

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

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

3. Разработаны и реализованы операционные среды МАРЕХ и ОБЬ для вычислительных систем ЕС-Ю68.17 и СИБИРЬ, обеспечивающие динамическую настройку программ на число доступных ресурсов и предоставляющие средства порождения процессов, управления ими, сервисной и эксплуатационной поддержки устойчивого функционирования вычислителей.

4. Разработаны технологические рекомендации по параллельному программированию в операционных средах, позволяпцие при решении задач молекулярной физики, обработки изображений, краевых задач электрофизики получать линейное или почти линейное ускорение счета с увеличением числа процессоров в пределах 1-20. На вычислительной системе из 4-ех процессоров ЕС-2706 было получено ускорение счета в 13-47 раз по сравнению со счетом в ЕС-1066.

По теме диссертации опубликованы следупцие работы:

I. Кучин Н.В., Панкратов С.А. Средства поддержки параллельной работы специализированных процессоров МВК ЕС. // Тез. докл. II Регионального семинара "Распределенная обработка информации".- Новосибирск, 1987. - с. 38.

2. Кучин H.B., Малышкин В.Э., Панкратов С.А. Управление распределением спецпроцессоров в МВК ЕС.//Тез.докл. I Всесоюз. конференции "Супер-ЭВМ".- Минск, 1987.- чЛ, с.161-162.

3.Кучин Н.В., Малышкин В.Э., Панкратов С.А. Управление ресурсами спецпроцессоров в МВК ЕС. // Высокопроизводительные вычислительные системы и' их программное обеспечение.-Новосибирск: ВЦ СО АН СССР, 1987. - С. 29-37.

4. Кучин Н.В., Малышкин В.Э., Панкратов С.А. 'Параллельный монитор для многопроцессорного вычислительного комплекса. //Тез. докл. viii Всес. семинара "Параллельное программирование и высокопроизводительные структуры".-Киев,1988.-с.107-108.

5. Панкратов С. А. Монитор управления вычислительными ресурсами неоднородных специализированных вычислителей. //Тез. докл. viii Сибирской школы по ППП "Программное обеспечение ЭВМ новых поколений".- Иркутск, 1989. - с.72.

6. Панкратов С.А. Параллельный монитор для управления вычислительными ресурсами высокопроизводительной вычислительной системы. // Тез.докл. Всесоюз. школы-семинара "ЕС ЭВМ-89".- Киев, 1989.- с. 250-251.

7. Кучин Н.В., Малышкин В.Э., Панкратов С.А. Параллельный монитор для управления ресурсами высокопроизводительной вычислительной системы Сибирь. // Математическое и архитектурное обеспечение параллельных вычислений.-Новосибирск: ВЦ СО АН СССР, 1989. - С. 120-128.

8. Панкратов С.А. Принципы управления вычислительными ресурсами крупноблочных МВК в параллельных программах.//Тез.докл. 10 Всесоюз. семинара "Параллельное программирование и высокопроизводительные системы: методы представления знаний в информационных технологиях". - Уфа, 1990. - с. 165-166.

9. Панкратов С.А. Управление вычислительными ресурсами б крупноблочном МВК. - Новосибирск, 1990.- 36 с. -(Препринт/ АН СССР. Сиб. отд-ние. ВЦ; 905).