Содержание к диссертации
Введение
1. Математическая модель распределенной обработки конкурирующих процессов 11
1.1. Обзор литературы по параллельным вычислениям 11
1.2. Конструктивные элементы распределенной обработки 14
1.3. Концепция структурирования в параллельном программировании 18
1.4. Математическая модель распределенной обработки конкурирующих процессов и режимы их взаимодействия 22
2. Время реализации конкурирующих процессов при распределенной обработке 25
2.1. Минимальное общее время выполнения конкурирующих процессов в асинхронном режиме 25
2.2. Синхронный режим с непрерывным выполнением блоков программного ресурса каждым из процессов 38
2.3. Синхронный режим распределенных конкурирующих процессов с непрерывным переходом по процессам 48
2.4. Анализ режимов организации распределенных конкурирующих процессов 56
3. Задачи оптимальной организации конкурирующих процессов при распределенной обработке 61
3.1. Критерии существования эффективных одинаково распределенных систем конкурирующих процессов 61
3.2. Эффективность одинаково распределенных систем в условиях ограниченного параллелизма 66
3.3. Оптимальность одинаково распределенных систем конкурирующих процессов 70
4. Приемы ускорения вычислений при распределенной обработке параллельных процессов 74
4.1. Приемы ускорения вычислений и их эффективность 74
4.2. Краевая задача для оператора Лапласа 80
Заключение 84
Библиография
- Конструктивные элементы распределенной обработки
- Синхронный режим с непрерывным выполнением блоков программного ресурса каждым из процессов
- Эффективность одинаково распределенных систем в условиях ограниченного параллелизма
- Краевая задача для оператора Лапласа
Введение к работе
Постоянное существование вычислительных задач, таких как моделирование климата, генная инженерия, проектирование интегральных схем и др., требуют для своего анализа и решения ЭВМ с террафлопсной производительностью. Одним из путей решения данных задач является применение параллельных многопроцессорных вычислительных систем сложной архитектуры.
Параллельное программирование возникло в 1960-е годы в сфере операционных систем. Причиной стало изобретение аппаратных модулей, названных каналами, или контроллерами устройств, позволявших центральному процессору выполнять новую прикладную программу одновременно с операциями ввода-вывода других программ. Вскоре после изобретения каналов началась разработка многопроцессорных машин, которые позволили разрешить проблемы, связанные с использованием однопроцессорных компьютеров, что нашло свое отражение в расчетном времени и в качестве результатов исследования. В настоящее время все крупные машины (супер—ЭВМ), называемые машинами с массовым параллелизмом (massively parallel processors), являются многопроцессорными, а самые большие имеют сотни процессоров.
Следует отметить, что до сих пор применение параллелизма не получило-широкого распространения. До недавнего времени одной из причин являлась, высокая стоимость создания параллельных вычислительных систем. Современные тенденции построения параллельных вычислительных комплексов, многопроцессорных систем и компьютеров из типовых конструктивных элементов, массовый выпуск которых освоен промышленностью, снизили влияние этого фактора. Другая и, пожалуй, основная причина сдерживания массового распространения параллелизма состоит в том, что для проведения параллельных вычислений необходимо "параллельное" обобщение традиционной последовательной технологии решения задач на ЭВМ. Так, численные методы должны проектироваться как системы параллельных и взаимодействующих между собой процессов, применяемые алгоритмические языки и системное программное обеспечение должны обеспечивать создание параллельных программ, организовывать синхронизацию и взаимоисключение асинхронных процессов и т. п.
Отметим набор причин, в силу которых в настоящее время параллельные вычисления являются перспективной областью теоретических исследований и их практических применений [13]:
несмотря на подтверждаемый на практике закон Гроша (Grosch), согласно которому производительность компьютера возрастает пропорцио-
пально квадрату его стоимости, следует учесть, что рост быстродействия последовательных ЭВМ не может продолжаться бесконечно, кроме того, компьютеры подвержены быстрому моральному старению;
согласно гипотезе Минского (Minsky), ускорение, достигаемое при' ис
пользовании параллельной системы, пропорционально двоичному лога
рифму от числа процессоров, но подобная оценка ускорения может
иметь место при распараллеливании определенных алгоритмов, вместе с
тем, существует большое количество задач, при параллельнолі решении
которых достигается 100% использование всех имеющихся процессоров
параллельной вычислительной системы;
в соответствии с законолі Мура (Moore) происходит постоянное совер
шенствование-последовательных компьютеров, мощность которых воз-'
растает практически в 2 раза каждые 18-24 месяца, на это замечание
можно отметить, что аналогичное развитие свойственно и параллельным
системам, кроме того, применение параллелизма позволяет получать
э/селаелюе ускорение вычислений без какого—либо ожидания новых более
быстродействующих процессоров;
согласно закона Амдаля (Amdahl), ускорение процесса вычислений при
использовании р процессоров ограничивается величиной
1 d+(1 -d)/p'
где d есть доля последовательных вычислений в применяемом алгоритме, однако часто доля последовательных операций характеризует не невозможность параллельного решения задач, а. последовательные свойства применяемых алгоритмов, как результат, доля последовательных вычислений люжет быть существенно снижена при выборе подходящих для распараллеливания алгоритмов;
параллельные системы отличаются существенным разнообразием архи
тектурных принципов построения, и получить максимальный эффект от
использования параллелизма бывает затруднительно, но в последова- ;
тельных ЭВМ тоже присутствуют способы параллелизма, такие как кон
вейерные вычисления, многопроцессорные системы и т. п., кроме того,
инвариантность создаваемого програлшного обеспечения может быть
обеспечена и при помощи использования типовых программных средств
поддержки параллельных вычислений типа программных библиотек MPI,
PVM и др.;
существующее программное обеспечение ориентировано в основном на.
последовательные ЭВМ, переработка которого не является необходимой,
если оно обеспечивает решение поставленных задач, однако если после
довательные программы не позволяют получать решения задач за при
емлемое время или же возникает необходимость решения новых задач,
то необходимой становится разработка нового программного обеспе
чения в параллельном выполнении.
Подведя итог вышесказанному, можно заключить, что организация па
раллельных вычислений представляет собой довольно сложную научно-
техническую проблему, решение которой подразделяется на следующие на
правления деятельности: '
разработка распределенных вычислительных систем [11, 14, 41, 50,.61-62, 66-67];
анализ эффективности и оптимальности распределенных вычислений для оценивания получаемого ускорения вычислений и степени использования всех возможностей компьютерного оборудования при параллельных способах решения задач [2-3, 8, 10-11, 15, 19, 22-38, 52-58, 73, 76,81,83];
создание и развитие распределенных алгоритмов и специальных численных методов для решения прикладных задач в разных областях практических приложений [3, 8, 11, 40, 45, 76-77, 81-83];
разработка распределенных программных систем, связанных с математическим моделированием для анализа и обеспечения правильного функционирования параллельных программ [42, 51, 74, 78, 84];
создание и развитие системного программного обеспечения для распределенных вычислительных систем является основой для обеспечения мобильности создаваемого прикладного программного обеспечения [1, 6,42,51,69-71,74,78,84].
При организации параллельных вычислений различают следующие режимы выполнения независимых частей программы:
многозадачный режим (режим разделения времени), при котором для выполнения процессов' используется единственный процессор, данный режим является' псевдопараллельным, так как исполняемым может быть только один единственный процесс, а все остальные процессы находятся в состоянии ожидания своей очереди на использование процессора;
режгьч параллельного выполнения, когда в один и тот же момент времени может выполняться несколько команд обработки данных, данный ре-
!
жим вычислений может быть обеспечен как при наличии нескольких процессоров, так и при помощи конвейерных и векторных обрабатывающих устройств;
'режим распределенной обработки - параллельная обработка данных, при которой используется множество вычислительных устройств достаточно удаленных друг от друга,-эффективная обработка данных при таком способе организации вычислений возможна только для параллельных алгоритмов с низкой интенсивностью потоков межпроцессорных передач данных.
С появлением сетевых многопроцессорных вычислительных систем, сетевых вычислительных комплексов, многопроцессорных вычислительных систем кластерного типа усиливаются позиции именно распределенного программирования. Сейчас стала заметной необходимость распределенной обработки с массовым параллелизмом, использующая технологии клиент-сервер, возможности сети Internet и World Wide Web. Именно сеть Internet можно рассматривать как самый большой параллельный компьютер — мета-компьютер, который объединяет колоссальные вычислительные ресурсы, обеспечивает высокую скорость обработки большого потока задач, это огромное хранилище данных [11]. Вопросы эффективности, пиковой и реальной производительности распределенных систем выходят на передний план, поскольку последние являются эффективным инструментом для проведения научных, социологических и бизнес-исследований.
Направлением диссертационного исследования является третья форма параллелизма - распределенная обработка, принципы которой прослеживаются практически во всех архитектурах параллельных вычислительных систем. В связи с распространением распределенной обработки, актуальными являются задачи построения и исследования математических моделей именно этого вида параллелизма, определения потенциальных возможностей ускорения и эффективности вычислений, поиска условий оптимальной реализации заданных объемов вычислений. Один из подходов на пути решения указанных задач основывается на структурировании программных ресурсов на параллельно выполняемые блоки с их последующей конвейеризацией по процессам и процессорам. В данном направлении получен ряд результатов для различных классов систем распределенных конкурирующих процессов. В то же время остаются нерешенными такие задачи как: с учетом дополнительных системных расходов определения временных характеристик реализации распределенных конкурирующих процессов; проведение сравнительного анализа организации выполнения распределенных процессов; в условиях неограниченного и ограниченного параллелизма по-
лучения условий эффективности и оптимальной реализации распределенных конкурирующих процессов в базовых режимах их взаимодействия.
Исследования в указанном направлении являются чрезвычайно актуальными. Особая активность характерна для Объединенного института проблем информатики Национальной Академии наук Беларуси, Института системного программирования Российской Академии наук, Института кибернетики имени В. М. Глушкова Национальной Академии наук Украины, факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Связь работы с крупными научными программами и темами
Тема диссертационной работы «Эффективность и оптимальность одинаково распределенных систем конкурирующих процессов» утверждена на заседании Совета факультета менеджмента БГЭУ, протокол № 1 от 27 августа 2004 года. Тема диссертации соответствует отрасли физико-математических наук по специальностям 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» и 05.13.18 - «Теоретические основы математического моделирования, численные методы и комплексы программ».
Диссертационная работа выполнялась в рамках Белорусского республиканского фонда фундаментальных исследований по теме «Разработка новых подходов к распараллеливанию численных методов математической физики на основе анализа тонких свойств графов», проект № Ф04Р-156, время выполнения с 01.05.2004 г. по 01.06.2006 г.
Цель и задачи исследования
Целью диссертационной работы является дальнейшее развитие математической' модели организации распределенных вычислений над структурированными программными ресурсами и решение на ее основе дискретно-комбинаторных оптимизационных задач, возникающих при выполнении одинаково распределенных конкурирующих процессов, проведение сравнительного анализа их временной сложности для асинхронного и двух синхронных режимов.
В соответствии с поставленной целью в диссертации детально исследованы следующие задачи:
определения минимального общего времени реализации одинаково-распределенных конкурирующих процессов в различных режимах взаимодействия процессов, процессоров и блоков программного ресурса с учетом дополнительных системных расходов;
сравнительного анализа временных характеристик реализации одинаково распределенных конкурирующих процессов;
определения условий, критериев эффективности и оптимальности одинаково распределенных систем конкурирующих процессов. Объектом исследования диссертационной работы является математиче-
екая модель организации распределенных конкурирующих процессов.
Положения, выносимые на защиту
Решены задачи определения минимального общего времени выполнения одинаково распределенных конкурирующих процессов в базовых режимах с учетом дополнительных системных расходов, связанных с организацией па-
раллельного использования блоков структурированного программного ресурса множеством конкурирующих процессов при распределенной обработке.
Проведен сравнительный анализ временных характеристик для класса одинаково распределенных конкурирующих процессов при достаточном числе процессоров.
В случае неограниченного параллелизма получено условие существования для любой эффективной более эффективной одинаково распределенной системы конкурирующих процессов.
Для всех трех базовых режимов в случае достаточного числа процессоров, а для асинхронного и второго синхронного режимов взаимодействия конкурирующих процессов в общем случае, получены достаточные условия эффективности одинаково распределенных систем конкурирующих процессов.
Определены критерии существования эффективных систем одинаково распределенных конкурирующих процессов в зависимости от величины дополнительных системных расходов.
В условиях неограниченного и ограниченного параллелизма получены критерии оптимальности одинаково распределенных систем конкурирующих процессов.
Проведенные исследования позволяют давать практические рекомендации по оптимальной организации неоднородных, однородных и одинаково-распределенных процессов, конкурирующих за использование общих программных ресурсов в различных режимах их взаимодействия применительно к вычислительным системам с распределенной обработкой данных с учетом накладных расходов.
Результаты диссертации могут быть использованы при проектировании сетевых вычислительных систем, сетевых вычислительных комплексов, вычислительных систем кластерного типа, вычислительных систем с технологией клиент-сервер, при создании системного и прикладного программного обеспечения для них.
Личный вклад соискателя
Все основные результаты, включенные в диссертационную работу, получены автором лично. Соавторы совместных публикаций приняли участне.в постановке задач, обсуждении полученных результатов.
Апробация результатов диссертации
Материалы, вошедшие в диссертационную работу, докладывались и обсуждались на научных семинарах в отделе рекурсивных вычислений Института кибернетики АН Украины и Институте математики НАН Беларуси, а также на 10 научно-практических конференциях: третьей международной
конференции «Информационные системы и технологии 1ST'2006», секция «Параллельная и распределенная обработка данных» (Минск, 2006); республиканской научной конференции «Социально-экономическое и гуманитарное развитие белорусского общества в XXI веке», секция «Информационные технологии и математические методы в экономике» (Минск, 2004); научно-практической конференции «Экономический механизм формирования национальной модели развития экономики РБ», секция «Развитие информационных технологий в Республике Беларусь» (Пинск, 2005); ІГ научно-практической конференции «Актуальные проблемы рыночной экономики», секция «Статистические и математические методы в экономике» (Бобруйск, 2005); международной научной конференции «Экономическое развитие Беларуси в контексте расширения Европейского Союза», секция «Информационные технологии в экономических процессах» (Гродно, 2005); II научно-практической конференции «Исследования молодых ученых Пинщины», секция «Информационных технологий и компьютерные коммуникации» (Пинск, 2005); научно-практической конференции «Механизм формирования социально-экономического развития регионов Республики Беларусь в условиях перехода к рыночной экономике», секция «Внедрение информационных технологий в повышение эффективности социально-экономического развития Белорусского Полесья» (Пинск, 2006); международной научно-практической конференции «Механизмы устойчивого развития инновационных социально-экономических систем», секция «Статистические и математические методы в экономике» (Бобруйск, 2006); международной научно-практической конференции «Социально-экономическое и историко-культурное развитие Полесского региона в XXI веке», секция «Техника, информационных технологий и компьютерные коммуникации» (Пинск, 2006); VII международной конференции «Проблемы прогнозирования и государственного регулирования социально-экономического регулирования», секция «Математическое регулирование экономических процессов» (Минск, 2006).
Опубликованность результатов
Основные результаты диссертации опубликованы в 16 работах. Статей в научных и научно-теоретических журналах 6. Количество опубликованных в них материалов 1,42 авторских листа. Тезисов докладов и выступлений на международных и республиканских научных конференциях 10.
Структура и объем диссертации
Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения и библиографического списка из 85 наименований. Объем диссертационной работы составляет 91 страниц машинописного текста, включая 10 рисунков.
1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ КОНКУРИРУЮЩИХ ПРОЦЕССОВ
Распределенные вычисления - перспективная и динамично развивающая
ся область организации параллелизма. Данный термин обычно используется
для указания параллельной обработки данных, при которой используется
множество обрабатывающих устройств, достаточно удаленных друг от друга,
и в которых передача данных по линиям связи приводит к существенным
временным задержкам. Как результат, эффективная обработка данных при
таком способе организации вычислений возможна только для алгоритмов с
низкой интенсивностью потоков межпроцессорных передач данных. Пере
численные условия являются характерными, например, при организации вы
числений в многомашинных вычислительных комплексах,
высокопроизводительных вычислительных кластерах, локальных или гло
бальных информационных сетях [11, 70]. В связи с этим, производительность
при распределенной обработке параллельных процессов может существенно
колебаться в зависимости от целого ряда факторов в достаточно широком
диапазоне, а ускорение вычислений может быть достигнуто более богатым
набором приемов.
1.1. Обзор литературы по параллельным вычислениям
В "качестве фундаментальных работ последних лет, посвященных совре- менным параллельным вычислениям, можно выделить монографию Воеводиных [11], книги К. Ю Богачева [3], А. А. Букатова, В. Н. Дацюк, А. И. Жегуло [6], Г. Р. Эндрюса [70], С. Немнюгина, О. Стесик [51], Н. С. Коваленко, С. А. Самаль [38], В: Столингс [62], В. В. Корнеева [42], учебные пособия А. С. Антонова [1], В. П. Гергель, Р. Г. Стронгина [13], Г. И. Шпаковского [69] и др.
В [11] с единых позиций рассматриваются архитектуры параллельных вычислительных систем, технологии параллельного программирования, численные методы решения задач. Вместе со строгим описанием основных положений теории информационной структуры программ и алгоритмов, книга содержит богатый справочный материал, необходимый для организации эффективного решения больших задач на компьютерах с параллельной архитектурой.
Книги [5, 13-14, 42, 50, 61-62] посвящены мультипроцессорным и многомашинным системам, позволяющим создавать высокопроизводительные и надежные вычислительные комплексы. Рассматриваются как аппаратный, так и программный аспекты таких систем. В [50] значительное внимание
уделено обстоятельному описанию ряда реально существующих мультипроцессорных систем, используемых в различных областях человеческой деятельности. Многомашинные, многопроцессорные, магистральные, матричные, ассоциативные, с комбинаторной и перестраиваемой структурой и некоторые другие вычислительные системы параллельной обработки информации рассмотрены в [14]. Системы таких типов отличаются повышенной гибкостью и обладают высокими характеристиками. В [41] основное внимание уделено особенностям построения и программирования массивно-параллельных систем. Проводится сравнительный анализ промышленных реализаций коммуникационных технологий SCI, Myrinet, Raceway и других. Кратко изложены некоторые подходы к параллельному программированию, в частности, MPI и ОрепМР. Приведено описание архитектуры и/или идей построения SGI Power Challenge, SUN Ultra Enterprise, кластеров от DEC, CRAY ТЗЕ и семейства отечественных массивно-параллельных ЭВМ МВС— 100/ МВС-1000. Следует отметить книгу [13] издательства Нижегородского университета им. Н. И. Лобачевского. Данное учебное пособие предназначено для изучения и практического использования параллельных компьютерных систем. В книге подробно рассмотрены: принципы построения параллельных вычислительных систем, их классификация; моделирование и анализ параллельных вычислений; оценка коммуникационной трудоемкости параллельных алгоритмов; параллельные численные методы для решения типовых задач вычислительной математики; модели функционирования параллельных программ. Новые результаты в области параллельных и распределенных систем за рубежом содержатся в работах [61, 70, 74, 83].
Одним из направлений параллельных вычислений является создание и развитие параллельных алгоритмов [3, 8, 40, 45]. Книга [40] представляет собой учебник по курсу построения и анализа эффективных алгоритмов. В ней разрабатываются важнейшие классы быстрых алгоритмов и приемы их построения. В [8] рассматриваются вопросы автоматического распараллеливания алгоритмов и программ для последующего их исполнения на многопроцессорных вычислительных комплексах. Вводятся и изучаются с математических позиций параллельные вычислительные процессы. Рассмотрены вопросы максимального распараллеливания операторных схем для различных отношений эквивалентности. Даны методы организации динамического распараллеливания программ. Построены конкретные алгоритмы распараллеливания. Рассмотрены вопросы параллельной реализации циклических участков программ. Приведены примеры и обзор действующих векторизаторов и распараллеливающих программ. Более широко сведения о существующих параллельных методах вычислений для различных классов задач представлены в [3, 11, 76-77, 81-83].
Практическими руководствами для разработки прикладного программного обеспечения параллельных многопроцессорных систем являются книги [1, 6, 51, 69—71]. Пособия [1, 69] предназначены для освоения практического курса параллельного программирования с использованием технологии MPI. В настоящее время технология MPI является основным средством программирования для кластерных систем и компьютеров с распределенной памятью, но может применяться также и на вычислительных системах других типов; Приведено описание большинства основных процедур стандарта MPI— 1.1 с примерами их применения и практические сведения, которые могут потребоваться при написании реальных программ. Основное описание ведется с использованием вызовов процедур MPI из программ на языке Фортран, однако указаны также основные отличия в использовании вызовов аналогичных функций из программ на языке Си. Приводятся примеры небольших законченных параллельных программ. В практическом руководстве [6] основное внимание уделено системам с распределенной памятью для решения объемных вычислительных задач. Данная книга посвящена рассмотрению среды параллельного программирования MPI, а также представляет собой методическое руководство по работе с библиотеками параллельных программ ScaLAPACK и Aztec. В книге [51] приводятся сведения не только об архитектуре высокопроизводительной системы параллельного программирования MPI (Message Passing Interface), но и о системах PVM (Parallel Virtual Machine), HPF (High Performance Fortran). Излагается методика параллельного программирования для создания своих эффективных параллельных и векторизованных программ. Представленные примеры помогут разобраться в тонкостях работы многопроцессорных систем. Очень полезна в области разработки программного обеспечения книга Г. Р. Эндрюса [70]. В книге рассматриваются важнейшие концепции многопоточного, параллельного и распределенного программирования. Все обсуждаемые концепции и методы тщательно проиллюстрированы многочисленными примерами, написанными на основных языках программирования с использованием наиболее распространенных библиотек. В книге освещаются общие механизмы параллельного программирования с использованием разделяемых переменных, основные концепции распределенного программирования и механизмы взаимодействия и синхронизации процессов с помощью обмена сообщениями.
В связи с широким распространением принципов параллельных вычислений актуальными являются проблемы построения и исследования математических моделей [2, 10, 19, 22-38, 52-58]. В работах введена и исследована математическая модель сосредоточенной и распределенной обработки конкурирующих процессов и режимы их взаимодействия. Получены математические соотношения для вычисления минимального общего времени при
реализации заданных объемов вычислений в различных режимах взаимодействия процессов, процессоров и блоков программного ресурса. Проведен анализ режимов взаимодействия сосредоточенных конкурирующих процессов. Рассмотрены задачи оптимальной организации конкурирующих процессов при сосредоточенной обработке. Получены критерии эффективности и оптимальности структурирования программных ресурсов при ограниченном числе процессоров. В работе [38] рассмотрены конкурирующие процессы при ограниченном числе копий структурированного программного ресурса. Прогресс в решении задач был достигнут за счет применения методов дискретной оптимизации [59], теории графов [17-18], теории расписаний [39, 63-65].
Много работ, посвященных различным проблемам параллельных вычислений можно найти в специализированных журналах [4, 20-37, 44, 47, 60, 72, 75, 79-80, 85], материалах конференций [9, 12, 54-58], интернет-ресурсах ().
1.2. Конструктивные элементы распределенной обработки
Основой для построения моделей функционирования программ, реализующих методы распределенной обработки решения задач, являются понятия прогресса и программного ресурса как конструктивных единиц построения параллельной программы.
Понятие процесса является одним из основополагающих в теории и практике распределенного программирования. В' [5, 16, 62, 66] приводится ряд известных в литературе определений процесса. Разброс в трактовке данного понятия является достаточно широким, но в целом большинство определений сводится к пониманию процесса как "некоторой совокупности набора исполняющихся команд, ассоциированных с ним ресурсов и текущего момента его выполнения, находящуюся под управлением операционной системы ".
Конкретизация понятия процесса зависит от целей исследования. При решении задач организации выполнения процессов [16, 70, 72], процесс в работе рассматривается как последовательность наборов команд (блоков) Is =(1, 2, ..., s). С целью наиболее эффективного решения задач синхронизации процессов, существенной минимизации системных затрат и простоев обрабатывающих устройств, для процессов строятся расписания моментов запуска и окончания каждого из блоков. Моменты времени начала выполнения каждого блока определяются последовательностью (г,, t2, ..., ts). Пред-
полагая, что блоки выполняются строго последовательно, в ходе своей реализации являются неделимыми и имеют длительности выполнения d,>\, j = l,s, получим, что моменты времени завершения наборов команд определяются последовательностью вида (/, + dl, t2+d2, ..., ts+ds).
Для ускорения вычислений процессы могут исполняться псевдопарал-лельно на одном вычислительном устройстве или параллельно на разных вычислительных устройствах, взаимодействуя между собой. Процессы, которые влияют на поведение друг друга путем обмена информацией, называют кооперативными или взашюдействующъши процессами [50]. В связи с этим, понятие процесса может быть использовано в качестве основного конструктивного элемента для построения параллельных программ в виде совокупности взаимодействующих процессов.
В ходе своего выполнения состояние процесса может многократно изменяться. Возможные варианты смены состояний показаны на рис. 1.1.
. Выполнение*"
Ожидание* ~j< С Блокировка
Рис. 1.1 -Диаграмма переходов процесса из состояния в состояние
Говорят, что процесс является активным и находится в состоянии выполнения, если достигается равенство tJ+l = t} + dj, т. е. для выполнения процесса выделено вычислительное устройство, и после завершения выполнения очередного блока процесса сразу же начинается выполнение следующего блока. Соотношение t х >t]+d} означает, что после выполнения очередного блока процесс приостановлен и ожидает возможности для продолжения своего выполнения. Данная приостановка может быть вызвана необходимостью разделения использования единственного вычислительного устройства между одновременно исполняемыми процессами. В этом случае приостановленный процесс находится в состоянии ожидания момента предоставления устройства для своего выполнения. Кроме того, приостановка процесса может быть вызвана и временной неготовностью процесса к дальнейшему вы-
полнению. В подобных ситуациях говорят, что процесс является блокированным и находится в состоянии блокировки.
Итак, параллельную программу можно рассматривать как некоторый агрегированный процесс, получаемый путем параллельного объединения составляющих кооперативных процессов. При разработке таких программ существует ряд особенностей одновременного выполнения нескольких процессов, которые могут быть сформулированы в виде ряда принципиальных положений [13]:
моменты выполнения командных последовательностей разных процессов могут чередоваться по времени;
между моментами исполнения блоков разных процессов могут выполняться различные временные соотношения, характер этих соотношений зависит от количества и быстродействия обрабатывающих устройств и загрузки многопроцессорной вычислительной системы и, тем самым, не может быть определен заранее;
временные соотношения между моментами исполнения блоков могут различаться при разных запусках программ на выполнение, т. е. одной и той же программе при одних и тех же исходных данных могут соответствовать разные командные последовательности вследствие разных вариантов чередования моментов работы разных вычислительных устройств;
доказательство правильности получаемых результатов должно проводиться для любых возможных временных соотношений процессов;
для исключения зависимости результатов выполнения программы от порядка чередования блоков разных процессов необходим анализ ситуаций взаимовлияния процессов и разработка методов для их исключения.
Перечисленные моменты свидетельствуют о существенном повышении сложности параллельного программирования по сравнению с разработкой "традиционных" последовательных программ.
Понятие ресурса обычно используется для обозначения любых объектов вычислительной системы, которые, могут быть использованы процессом для своего выполнения. В качестве ресурса может рассматриваться процессор, память, программы, данные и т. п. По характеру использования могут различаться следующие категории ресурсов [13]:
выделяемые (монопольно используемые, ^перераспределяемые) ресурсы
характеризуются тем, что выделяются процессам в момент их возникно-
вения и освобождаются только в момент завершения процессов (устройства чтения или записи);
повторно распределяемые ресурсы отличаются возможностью динамического запрашивания, выделения и освобождения в ходе выполнения процессов (оперативная память);
Конструктивные элементы распределенной обработки
Основой для построения моделей функционирования программ, реализующих методы распределенной обработки решения задач, являются понятия прогресса и программного ресурса как конструктивных единиц построения параллельной программы.
Понятие процесса является одним из основополагающих в теории и практике распределенного программирования. В [5, 16, 62, 66] приводится ряд известных в литературе определений процесса. Разброс в трактовке данного понятия является достаточно широким, но в целом большинство определений сводится к пониманию процесса как "некоторой совокупности набора исполняющихся команд, ассоциированных с ним ресурсов и текущего момента его выполнения, находящуюся под управлением операционной системы ".
Конкретизация понятия процесса зависит от целей исследования. При решении задач организации выполнения процессов [16, 70, 72], процесс в работе рассматривается как последовательность наборов команд (блоков) Is =(1, 2, ..., s). С целью наиболее эффективного решения задач синхронизации процессов, существенной минимизации системных затрат и простоев обрабатывающих устройств, для процессов строятся расписания моментов запуска и окончания каждого из блоков. Моменты времени начала выполнения каждого блока определяются последовательностью (г,, t2, ..., ts). Пред полагая, что блоки выполняются строго последовательно, в ходе своей реализации являются неделимыми и имеют длительности выполнения d, \, j = l,s, получим, что моменты времени завершения наборов команд определяются последовательностью вида (/, + dl, t2+d2, ..., ts+ds).
Для ускорения вычислений процессы могут исполняться псевдопарал-лельно на одном вычислительном устройстве или параллельно на разных вычислительных устройствах, взаимодействуя между собой. Процессы, которые влияют на поведение друг друга путем обмена информацией, называют кооперативными или взашюдействующъши процессами [50]. В связи с этим, понятие процесса может быть использовано в качестве основного конструктивного элемента для построения параллельных программ в виде совокупности взаимодействующих процессов.
В ходе своего выполнения состояние процесса может многократно изменяться. Возможные варианты смены состояний показаны на рис. 1.1.
Говорят, что процесс является активным и находится в состоянии выполнения, если достигается равенство tJ+l = t} + dj, т. е. для выполнения процесса выделено вычислительное устройство, и после завершения выполнения очередного блока процесса сразу же начинается выполнение следующего блока. Соотношение t х t]+d} означает, что после выполнения очередного блока процесс приостановлен и ожидает возможности для продолжения своего выполнения. Данная приостановка может быть вызвана необходимостью разделения использования единственного вычислительного устройства между одновременно исполняемыми процессами. В этом случае приостановленный процесс находится в состоянии ожидания момента предоставления устройства для своего выполнения. Кроме того, приостановка процесса может быть вызвана и временной неготовностью процесса к дальнейшему вы полнению. В подобных ситуациях говорят, что процесс является блокированным и находится в состоянии блокировки.
Итак, параллельную программу можно рассматривать как некоторый агрегированный процесс, получаемый путем параллельного объединения составляющих кооперативных процессов. При разработке таких программ существует ряд особенностей одновременного выполнения нескольких процессов, которые могут быть сформулированы в виде ряда принципиальных положений [13]:
моменты выполнения командных последовательностей разных процессов могут чередоваться по времени;
между моментами исполнения блоков разных процессов могут выполняться различные временные соотношения, характер этих соотношений зависит от количества и быстродействия обрабатывающих устройств и загрузки многопроцессорной вычислительной системы и, тем самым, не может быть определен заранее;
временные соотношения между моментами исполнения блоков могут различаться при разных запусках программ на выполнение, т. е. одной и той же программе при одних и тех же исходных данных могут соответствовать разные командные последовательности вследствие разных вариантов чередования моментов работы разных вычислительных устройств;
доказательство правильности получаемых результатов должно проводиться для любых возможных временных соотношений процессов;
для исключения зависимости результатов выполнения программы от порядка чередования блоков разных процессов необходим анализ ситуаций взаимовлияния процессов и разработка методов для их исключения.
Перечисленные моменты свидетельствуют о существенном повышении сложности параллельного программирования по сравнению с разработкой "традиционных" последовательных программ.
Понятие ресурса обычно используется для обозначения любых объектов вычислительной системы, которые, могут быть использованы процессом для своего выполнения
Синхронный режим с непрерывным выполнением блоков программного ресурса каждым из процессов
Рассмотрим первый базовый синхронный режим взаимодействия процессов, процессоров и блоков, обеспечивающий непрерывное выполнение блоков программного ресурса каждым из процессов [19, 23, 30-31]. Как и для базового асинхронного режима, исследование проведем для множества конкурирующих неоднородных, однородных и одинаково распределенных процессов с учетом дополнительных системных расходов є 0.
Будем рассматривать п, п 2, конкурирующих процессов, использующих программный ресурс, структурированный на s, s 2, линейно-упорядоченных блоков 0}, 02, ..., О,.. При этом все п процессов используют только одну копию программного ресурса. Предполагается, что выполнение процессов осуществляется в вычислительной среде с р, р 2, процессорами, т. е. каждый из процессов является распределенным.
Неоднородные процессы
Задача состоит в нахождении минимального общего времени Tl(p,n,s,s) выполнения п неоднородных распределенных конкурирующих процессов в многопроцессорной системе с р процессорами в первом синхронном режиме взаимодействия процессов, процессоров и блоков с учетом параметра є 0, характеризующего время дополнительных системных расходов, связанных с организацией параллельного использования s блоков структурированного программного ресурса множеством конкурирующих процессов при распределенной обработке. Пусть Те =[t ] — я х s-матрица времен выполнения блоков программного ресурса Ох, 02, ..., Qs п процессами с учетом накладных расходов є, при этом tc4 — время выполнения Оу — го блока і-м процессом, / = 1, п, j = l,s.
Рассмотрим случай, когда число процессоров многопроцессорной системы является достаточным, т. е. s = р. Для вычисления величины Тхн {р,п,s,є) имеет место формула: У=1. каждого из последующих процессов, начиная со второго, а длительность выполнения последнего процесса.
При s р для выполнения п процессов достаточно использовать s процессоров, а остальные р процессоров не будут задействованы. Тогда для вычисления T (p,n,s,s) имеет место формула, которая может быть получена и из функционала многостадийной задачи теории расписаний с п требованиями и s приборами, при условии, что каждое требование обслуживается непрерывно одним прибором за другим [64]:
Для общего случая, когда s = кр, к \, выполняется разбиение множества блоков на к групп по р блоков в каждой, что равносильно разбиению исходной матрицы времен выполнения блоков ТЕ на к подматриц по р столбцов в каждой. Взаимодействие процессов, процессоров и блоков с учетом времен их выполнения для /-й группы, I = l,k, можно изобразить в виде линейной диаграммы Ганта. Каждая из этих диаграмм будет отображать во времени выполнение очередных/? блоков программного ресурса нар процессорах всеми п процессами. Заметим, что при s р непрерывность выполнения блоков структурированного программного ресурса может нарушаться Далее взаимодействие процессов, процессоров и блоков, с учетом условий 1-4, 6 параграфа 1.4, которые определяют рассматриваемый синхронный режим, введенных обозначений величин Tt 1, 8е/, 8/ и разбиения исходной матрицы времен выполнения блоков [/ ], і - l,n, j = l,s на к подматриц, отображается в виде сетевого дуго-взвешенного графа G[ [19]. Вершины графа расположены в узлах прямоугольной решетки размерности пх{к + \), при этом каждая из вершин графа, за исключением вершин (k+JJ-го уровня, определяет момент начала выполнения очередных р блоков /-го процесса в /— й группе процессов. Пронумерованы эти вершины парой чисел (/,/), i = \,n, I = l,k. Вершины (к+1)—го уровня определяют моменты выполнения процессов и являются висячими. Вершины в графе соединены дугами трех типов: "горизонтальными дугами соединяют вершины (/,/) и (/,/ + 1), i = l,n, I = 1,Аг, которые отражают продолжительность выполнения очередных/? блоков /-го процесса в 7-й группе блоков (формула 2.4); вертикальными дугами соединяют вершины (/,/) и (/ + 1,/), / = 1,л —1, / = 1,&, они в графе отражают времена задержек начала выполнения первого блока (і+1)-то процесса относительно начала выполнения первого блока /-го процесса в 1-й группе блоков (формула 2.5); наклонными (диагональными) дугами соединим вершины (п,1) и (1,/ +1), / = 1,к -1, отражающие времена задержек начала выполнения первого блока первого процесса в (1+1)—и группе блоков по отношению к первому блоку п-го процесса в 1-й группе (формула 2.6).
Построенный таким образом сетевой дуго-взвешенный граф G,c, полностью отображает во времени выполнение п неоднородных распределенных конкурирующих процессов нар процессорах в первом синхронном режиме с непрерывным выполнением s блоков структурированного программного ресурса каждым из процессов с учетом параметра є О, характеризующего время дополнительных системных расходов.
В случае, когда s-крл-г, к \, 1 г р, минимальное общее время выполнения п распределенных процессов на р процессорах определяется аналогичным образом, как и при s = кр, к \. Отличие состоит в том, что при разбиении исходной матрицы времен выполнения блоков [ ], i = \,n, j =l,s, на подматрицы по р столбцов получится к+1 подматрица, причем последняя (к+1)-я подматрица содержит только г столбцов. Формулы вычисления Т, ! и S. 1 аналогичны, с той лишь разницей, что I = 1,к + 1, причем при 1-к+\ в формуле для вычисления TteJ, j изменяется от 7 до г, т. е
Эффективность одинаково распределенных систем в условиях ограниченного параллелизма
Эффективная одинаково распределенная система называется оптимальной, если величина А достигает наибольшего значения.
В 3.1 показано, что оптимальную одинаково распределенную систему достаточно искать среди эффективных одинаково распределенных систем. Более того, в силу теоремы 3.1 оптимальную одинаково распределенную систему следует искать среди стационарных одинаково распределенных систем. Тогда с учетом (3.4) имеем: A(s p) = (s- 1)Г(1 -\/n)-{n + s- \)є. Введем функцию действительного аргумента х вида: Ae(x) = (s-l)Tn\l--)-(x + s-\)e, х 1.
Решение задачи об оптимальности одинаково распределенной системы, состоящей из п конкурирующих процессов, для достаточного числа процессоров для всех трех базовых режимов следует из теоремы.
Теорема 3.6. Для того, чтобы эффективная одинаково распределенная система конкурирующих процессов была оптимальной при заданных 2 s p, Т", є 0, необходимо и достаточно, чтобы она была стационарной и число процессов п0 в системе равнялось одному из чисел \{s-\)Tn \{s-\)T" + С\ [2, я], в котором функция А{х) достигает наибольшего значения. Здесь [х] означает наибольшее целое, не превосходящее х, п —заданное число.
Доказательство. Необходимость. Рассмотрим введенную функцию: As(x) = {s \)T"{\--]-(x + s-\), х \.
Согласно определению 3.3 одинаково распределенная система будет оптимальной в той точке х, где функция А(х) достигает своего наибольшего значения. Покажем, что функция АЕ(х) достигает своего наибольшего зна l(s-l)T" . чения в точке х = , - -— . Действительно, — (s-Y)T" 2Tn(s-l) х Д(х) = - - є, А(х) = з—- 0, так как 2, х 0.
Следовательно, функция А{х) достигает максимума в точке, где первая ее производная обращается в нуль А (х) = 0, т. е. х =. ( -1)Г Целочисленными точками, в которых достигается наибольшее значение функции Ае(х), будут п0 = [х ] или /70 = [х ] + 1. Следовательно, в качестве ( -1)Г (s-l)Tn по можно выбрать одно из чисел функция Ae(s p) принимает наибольшее значение Если же окажется, что ни одна из точек + 1, в которых + 1, в l(s-l)T" которой функция АЕ(Х) принимает наибольшее значение не принадлежит [2,п], то в качестве оптимальной выбираем эффективную одинаково распределенную систему с числом процессов п0= п.
В силу отрицательности второй производной, исследуемая функция выпукла. Следовательно, точка максимума всегда существует, а значит и существует эффективная одинаково распределенная система конкурирующих процессов в случае, когда п -» со.
Достаточность следует из свойств выпуклости функции А(х) при s р на отрезке [2, п].
Для решения задачи об оптимальности одинаково распределенной системы конкурирующих процессов в случае ограниченного параллелизма в асинхронном и втором синхронном режимах введем функции действительного аргумента х вида: - (р-1)Тп A(x) = (s-\)Tn- ——- (Ах + р-1)є, при s = кр, к \, (3.14) A(x) = (s-k-\)T"-(r Г—((к + \)х + (г-\))є, х при s = кр + г, к \, \ г р. (3.15)
Теорема 3.7. Для того, чтобы эффективная одинаково распределенная система конкурирующих процессов в случае ограниченного параллелизма в асинхронном и втором синхронном режимах была оптимальной при заданных р 2, Т", є 0, необходимо и достаточно, чтобы она была стационарной и число процессов п0 в системе равнялось одному из чисел: 1) (р-\)Г кє \{р-\)Г кє + п[2,и], при s = кр, к \, 2) (г-1)Г (к + \)є jQ-i)r (к + \)є + п [2,п], при s = кр + r, к \, \ г р, в котором функция А(х) достигает наибольшего значения, где [х] -наибольшее целое, не превосходящее х, п —заданное число.
Краевая задача для оператора Лапласа
Рассмотрим функцию у = f{x). Пусть E(l) cz Е(2) а... а Е{п) z... есть строго возрастающая последовательность наборов конечных областей определения аргументов, т. е. Е{п)-{Ех{п), ..., Er(nJ). Обозначим через г Q(n) = {jE,(n) множество всех точек, в которых определены аргументы, а значит, и значения вычисляемой функции. Пусть имеется ровно р процессоров. Изучим возможности их параллельной работы для таких п, что р \0(п)\, т. е. при ограниченном числе процессоров. Для каждого п при фиксированном числе процессоров построим разбиение области Q{ri) на р непересекающихся областей R(p,ri) - {Q, (p,n)}i=r-. Предположим, что число входных и выходных каналов каждого процессора ограничено числом, не зависящим от р и«, причем связи между процессорами могут быть переменными.
Рассмотрим так называемую синхронную организацию работы процессоров. Каждый шаг вычислений состоит из двух этапов: На первом этапе все процессоры обмениваются информацией. Переход ко второму этапу происходит лишь тогда, когда произведены все необходимые обмены, т. е. к началу второго этапа А:-го шага вычислений каждый процессор имеет всю информацию, которая необходима ему для вычислений на этом шаге. Второй этап состоит в том, что все процессоры производят вычисления, соответствующие данному шагу. Переход к следующему шагу вычислений (его первому этапу) происходит после того, как все процессоры завершили выполнение предыдущего шага.
Найдем верхнюю оценку для времени работы р процессоров на одном шаге вычислений. Обозначим через ик максимальный объем обмена между двумя процессорами на к—м шаге. Тогда величина и — maxL A характеризует максимальный объем обмена между двумя процессорами на одном шаге.
На множестве классов О, = О, (р, п), i = l,p, определим симметричное отношение информационной зависимости, полагая, что два класса информационно зависят один от другого, если значение функции у в точке одного класса зависит от значения у или х в точке другого класса. Отношение информационной зависимости можно представить с помощью неориентированного графа. Обозначим Як хроматический индекс графа, соответствующего
Ar-му шагу вычислений. Пусть Я = тахЯА. Обозначая тх время передачи единичного объема данных, получаем, что величина тхиХ есть верхняя оценка для времени первого этапа на одном шаге вычислений.
Обозначив г2 среднее время выполнения одной вычислительной операции, представим величину времени, в течение которого процессор р, производит вычисления на к м шаге в виде т2и, где и — максимальный объем вычислений на одном процессоре на одном шаге. Через %{п) обозначить число шагов, которое необходимо сделать для решения у = f{x). Таким образом, оценка для времени работы р процессоров имеет вид Тр(п) х(п){тхиЛ + т2и).
Если обозначить через / среднее значение времени вычисления компоненты функции у в одной точке, то общее время последовательного вычисления функции у = f(x) примет вид Тх(п) = 1\Е{п)\, где I f = ХИ/» \Щ - мощность множества Е. Средний объем вычислений на одном процессоре на одном шаге определим из формулы: Шп)\ Х(п)т2р
Обозначая т = т1/т2 И используя формулу Tx(n) = t\E{n)\, определяем нижнюю оценку эффективности использования р процессоров: /ЗЛп) - \ . и Таким образом, доказано утверждение.
Утверждение 4.3. Для любых п и p \Q(n)\, значение у - f{x) может быть вычислено с эффективностью рЛп) — и . Лтх и
При решении краевой задачи для оператора Лапласа сеточным методом используется итерационная процедура. Область расположения структур данных, т. е. узлы сетки, есть подмножество Н целочисленной решетки Z2. Область данных - действительные числа. На к—й итерации в каждой точке находится значение структуры Хк:
Рассмотрим выполнение /с-й итерации при условии, что (/с-1)-я итерация завершена, т. е. структура Хк 1 определена во всех точках Н. Очевидно, что в этом случае необходим лишь один шаг вычислений. Пусть р — заданное количество процессоров. Для удобства в качестве Н выберем квадрат со стороной из п точек. Рассмотрим два варианта разбиения Н по процессорам.
1) Разбиение горизонтальными (вертикальными) полосами равной ширины. На этапе обменов все процессоры, кроме первого, принимают значения структуры данных Хк 1 в 2п точках, и все процессоры, кроме последнего, передают соседним значения Хк ] в 2п точках, рис. 4.5. В этом случае т = 2п, Я = 2.
