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

ООЗ16 г1БВ

На правах ру^эттси

Павлов Павел Александрович

ОДИНАКОВО РАСПРЕДЕЛЕННЫЕ СИСТЕМЫ КОНКУРИРУЮЩИХ ПРОЦЕССОВ

Специальность 05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Минск-2008

003167168

Работа выполнена в Учреждении образования «Белорусский государственный экономический университет»

Научный руководитель доктор физико-математических наук,

профессор Коваленко Николай Семенович

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

Кузюрин Николай Николаевич

кандидат физико-математических наук Бахмуров Анатолий Геннадьевич

Ведущая организация Московский энергетический институт

Защита состоится 15 февраля 2008 года в 15 часов на заседании диссертационного совета Д 002 087 01 в Институте системного программирования Российской академии наук по адресу 109004, Москва, ул Большая Коммунистическая, д 25

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН

Автореферат разослан 13 января 2008 года

Ученый секретарь диссертационного совета канд физ -мат. наук

СП Прохоров

Общая характеристика работы

Актуальность темы

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

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

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

■ нахождения минимального общего времени выполнения множества распределенных конкурирующих процессов с учетом дополнительных системных расходов,

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

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

Цель и задачи работы

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

В соответствии с поставленной целью в диссертации детально исследованы следующие задачи

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

■ сравнительного анализа временных характеристик реализации одинаково распределенных конкурирующих процессов в базовых режимах,

■ определения необходимых и достаточных условий эффективности и оптимальности одинаково распределенных систем конкурирующих процессов

Научная новизна

Научной новизной обладают следующие результаты диссертационной работы

■ решены задачи нахождения минимального общего времени выполнения неоднородных, однородных и одинаково распределенных конкурирующих процессов в асинхронном и синхронных режимах с учетом дополнительных системных расходов [1—2, 5, 8-10, 13-14],

■ проведен сравнительный анализ времен реализации в базовых режимах одинаково распределенных конкурирующих процессов при достаточном числе процессоров многопроцессорной системы [3,5-6],

■ в случае неограниченного параллелизма для всех трех базовых режимов установлены достаточное условие эффективности одинаково распределенных систем конкурирующих процессов и необходимое и достаточное условие существования эффективных систем одинаково распределенных конкурирующих процессов в зависимости от величины дополнительных системных расходов [1,3,10, 15],

■ в случае ограниченного параллелизма условия эффективности одинаково распределенных систем конкурирующих процессов получены для асинхронного и второго синхронного режимов [1, 3,10, 15],

■ в условиях неограниченного и ограниченного параллелизма решены задачи оптимальности одинаково распределенных систем конкурирующих процессов [4,7,11]

Практическая значимость

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

Апробация результатов диссертации

Диссертационная работа выполнялась в рамках Белорусского республиканского фонда фундаментальных исследований по теме «Разработка новых подходов к распараллеливанию численных методов

математической физики на основе анализа тонких свойств графов», проект № Ф04Р-156, время выполнения с 01 05 2004 г по 01 06 2006 г Все основные результаты, включенные в диссертационную работу, получены автором лично Соавторы совместных публикаций приняли участие в постановке задач, обсуждении полученных результатов

Материалы, вошедшие в диссертационную работу, докладывались и обсуждались на научных семинарах в отделе рекурсивных вычислений Института кибернетики АН Украины и Институте математики НАН Беларуси, а также на 10 научно-практических конференциях республиканской научной конференции «Социально-экономическое и гуманитарное развитие белорусского общества в XXI веке», секция «Информационные технологии и математические методы в экономике» (Минск, 2004), научно-практической конференции «Экономический механизм формирования национальной модели развития экономики РБ», секция «Развитие информационных технологий в Республике Беларусь» (Пинск, 2005), II научно-практической конференции «Актуальные проблемы рыночной экономики», секция «Статистические и математические методы в экономике» (Бобруйск, 2005), международной научной конференции «Экономическое развитие Беларуси в контексте расширения Европейского Союза», секция «Информационные технологии в экономических процессах» (Гродно, 2005), II научно-практической конференции «Исследования молодых ученых Пинщины», секция «Информационных технологий и компьютерные коммуникации» (Пинск, 2005), научно-практической конференции «Механизм формирования социально-экономического развития регионов Республики Беларусь в условиях перехода к рыночной экономике», секция «Внедрение информационных технологий в повышение эффективности социально-экономического развития Белорусского Полесья» (Пинск, 2006), международной научно-практической конференции «Механизмы устойчивого развития инновационных социально-экономических систем», секция «Статистические и математические методы в экономике» (Бобруйск, 2006), международной научно-практической конференции «Социально-экономическое и историко-культурное развитие Полесского региона в XXI веке», секция «Техника, информационных технологий и компьютерные коммуникации» (Пинск, 2006), VII международной конференции «Проблемы прогнозирования и государственного регулирования социально-экономического развития», секция «Математическое регулирование экономических процессов» (Минск, 2006), третьей международной конференции «Информационные системы и технологии

18Т'2006», секция «Параллельная и распределенная обработка данных» (Минск, 2006)

Опубликованность результатов

Основные результаты диссертации опубликованы в 16 работах Статей в научных и научно-теоретических журналах 6 Количество опубликованных в них материалов 1,42 авторских листа Тезисов докладов и выступлений на международных и республиканских научных конференциях 9

Структура и объем диссертации

Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения и библиографического списка из 85 наименований Объем диссертационной работы составляет 91 страницу машинописного текста, включая 13 рисунков

Краткое содержание работы

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

В первой главе в 1 1 проведен обзор литературы, кратко освещены работы предшественников по задачам, рассматриваемым в работе

В 1 2 конкретизированы понятия процесса и программного ресурса, поскольку именно они являются конструктивными единицами моделей функционирования программ, реализующих методы распределенной обработки решения задач Процесс в работе рассматривается как последовательность команд (блоков) /4 = (1, 2, , 5) При этом процесс называется распределенным, если все блоки или часть из них выполняются на разных процессорах Программный ресурс определяется как многократно выполняемая в многопроцессорной системе программа или ее часть Используя введенные понятия, в диссертации показано, что создание и исследование программ, использующих принципы распределенной обработки, сводится к решению задач организации взаимодействия распределенных процессов, конкурирующих за программный ресурс

Методу структурирования программных ресурсов, который приобретает особенно фундаментальный характер в области распределен-

ного программирования, посвящен 1 3 Основная идея данного метода, состоит в обеспечении структурирования программного ресурса на блоки Q^, Qг, , , с последующей конвейеризацией как блоков по процессам, так и процессов по процессорам многопроцессорной вычислительной системы, что позволяет получать существенный выигрыш по времени реализации заданных объемов вычислений

В 1 4 вводится математическая модель распределенной обработки конкурирующих процессов, которая включает в себя р, р> 2, процессоров многопроцессорной системы, п, п > 2, конкурирующих процессов, 5, л > 2, блоков структурированного на блоки программного ресурса, матрицу Т = [/ ], / = 1,и, у = 1,Л', времен выполнения блоков

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

Предполагается, что взаимодействие процессов, процессоров и блоков программного ресурса подчинено следующим условиям

1) ни один из блоков программного ресурса не может обрабатываться одновременно более чем одним процессором,

2) ни один из процессоров не может обрабатывать одновременно более одного блока,

3) обработка каждого блока программного ресурса осуществляется без прерываний,

4) распределение блоков программного ресурса по процессорам для каждого из процессов осуществляется циклически по правилу блок с номером у = Ар + /, у = 1,.?, / = 1 ,р, к>0 распределяется на процессор с номером 1

Введением дополнительных условий, определяются режимы взаимодействия процессов, процессоров и блоков Условия 1-4 и условие

5) отсутствуют простои процессоров при условии готовности блоков, а также отсутствует невыполнение блоков при наличии процессоров, определяют асинхронный режим

Условия 1-4 и условие

6) для каждого из п процессов момент завершения выполненияу-го блока на /-м процессоре совпадает с моментом начала выполнения

следующего (]+1)-то блока на 0+1)-м процессоре, / = 1, р-1,

) = 1,5-1, определяют первый синхронный режим, который обеспечивает непрерывное выполнение блоков программного ресурса внутри каждого из процессов, а условия 1-4 и условие

7) для каждого из блоков момент завершения его выполнения 1-й процессом совпадает с моментом начала его выполнения (1+1)-\\ процессом на том же процессоре, / = 1, и -1, определяют второй синхронный режим, обеспечивающий непрерывное выполнение каждого блока всеми процессами

Определение 11 Система п распределенных конкурирующих процессов называется неоднородной, если времена выполнения блоков программного ресурса @2, , зависят от объемов обрабатываемых данных и/или их структуры, т е разные для разных процессов Определение 12 Систему распределенных конкурирующих процессов будем называть однородной, если времена выполнения

го блока каждым из 1-х процессов равны, те ^ = I , / = 1, п, } = 1,5

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

блоков , J = \,s, программного ресурса каждым из г-х процессов совпадают и равны для всех / = 1, п, т е справедлива цепочка равенств = /,2 = = ^ = для всех 1 = \,п

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

В 2 1 рассматривается асинхронный режим Минимальное общее время выполнения неоднородных распределенных конкурирующих процессов Тц (р,п,$,в), т е когда времена выполнения блоков программного ресурса разные для разных процессов, в случае достаточного числа процессоров 2 < 5 < р, и с учетом параметра е > О, определяется по формуле

Т^{з,п,з,£) = (п + з-\)е+ тах

4 <Ы1Ч<Л

где и., и2

Задача нахождения Т™ (р,п,я,£) в 2 1 решена и с помощью аппарата сетевых вершинно-взвешеиных графов В частности, минимальное общее время в случае неограниченного параллелизма (2< я < р), определяется длиной критического пути из начальной вершины в конечную Каждой вершине графа соответствует значение = ^ + е ,

/ = 1,и, у = 1,5 Дуги в графе отражают линейный порядок выполнения

блоков Q¡, 7 = 1,5, программного ресурса каждым из процессов, а

также линейный порядок использования одних и тех же блоков разными процессами

В случае ограниченного параллелизма, т е когда .у > р, 5 = кр + г, к> 1, 1 <г < р , исходная матрица времен выполнения блоков с учетом дополнительных системных расходов Те ; = 1,и, 7 = 1 ,кр + г, разбивается на (к+1)-у подматрицу Т[', / = 1, к +1, размерностью п х р каждая По подматрицам Т[', I = 1, к +1, строится результирующая матрица Т* размерностью (к + \)п х (к + \)р , которая является блочной, симметричной, верхнедиагональной относительно второй диагонали, типа Ганкелевой порядка к+1

т;- п т; 'К с,

Ц гр£ 13 гр£ 4 грЕ 1 0

гр£ 1г Т1 гре 5 0 0

п грЕ 1к+1 0 0 0

0 0 0 0

Доказано, что минимальное общее время ТЦс(р,п^,е) выполнения неоднородных распределенных конкурирующих процессов в асинхронном режиме в случае я = кр +г, к> 1, 1 <г<р, определяется

длиной критического пути из начальной вершины в конечную вершину {к+1)р сетевого вершинно-взвешенного графа, веса которого

задаются матрицей Т*

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

равны, т е = ^ , 1=\,п, у = 1,5, минимальное общее время в случае

2<s< р, в асинхронном режиме составляет величину Т^(p,n,s,e) равную

С (А г) = г; + (и -1) шах /*,

l<y<s J

где (tf, te2, , tss) - длительности выполнения каждого из блоков

ч

программного ресурса с учетом накладных расходов, а Г/ = -

длительность выполнения всего программного ресурса

Для системы одинаково распределенных конкурирующих процессов, когда справедлива цепочка равенств = if2 = = t^ = t*,

i(£ = t: + e , для всех / = 1, n, справедлива

Теорема 21 Минимальное общее время выполнения п, п> 2, одинаково распределенных конкурирующих процессов, использующих структурированный на s, s >2, блоков программный ресурс в многопроцессорной системе с р, р > 2 , процессорами и допочнительньши системными расходами s> О, в асинхронном режиме составляет величину Т°ср (р, п,s, е), равную

T"Ap,n,s,e) =

Г"+(,s-l) max/,£, s<p,

1 <1<п

kT" + (р — 1)maxf, s = kp, к> 1,

1<J <п

(к+Щ" + (г-1) max t*, s = kp + r, к> 1, 1 <r<p,

где Т" - суммарное время выполнения каждого из блоков

1=1

()/, 7 = 1,5, всеми п процессами

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

В случае, когда число процессоров многопроцессорной системы является достаточным, те х < р , для вычисления величины минимального общего времени выполнения неоднородных процессов в первом синхронном режиме Т^(р,п,я,е) , имеет место формула

Т'(р,п,.<;,£) = Ушах

1С-К.,

у=1

+2Л

1=1

В случае, когда я = кр, к>\, выполняется разбиение матрицы

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

где

Т.е =Утах

' ¿Г1\<и<р

ЕС-1С

+ , 1 = 1, к — время выполне-

;=1

ния 1-й группы блоков всеми п процессами на р процессорах,

= тт - длина отрезка максимально возможного совме-

щения двух последовательных диаграмм Ганта по оси времени, 8] -разность между моментом начала выполнения у-го блока первым процессом для (/+/)-й группы блоков и моментом завершения выполнения у-го блока последним процессом для 1-й группы блоков, 8] - разность между началом выполнения первого блока /-м процессом для (1+1)-й группы блоков и моментом завершения выполнения р-го блока г-м процессом для 1-й группы блоков, т е

8] = Ш1П

1 й]йр

1С+Е*.

W = J+1

г ;+1 1и<

3] = тл

^Е™* ЕС-ЁС -ёяя ЕС-Еа-Е'Г

/ = 1Д-1

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

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

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

Теорема 22 Если взаимодействие процессов, процессоров и блоков подчинено условиям первого базового синхронного режима, то для любых р> 2, п > 2, л- > 2, е > 0, минимальное общее время выполнения одинаково распределенных конкурирующих процессов определяется по формулам

С + ¿max {?;_,-/;,()}

, s< р,

T'p(p,n,s,e) = \kT^p(p,n,p,e)-(k-l)mm{co1,a)2}, s = kp, k> 1,

kToP (P> n> P'e) + Top (p,n,r,£)-(k-1) mm{<»,, co2} - min {£, £ }, s = kp + r, k> 1, 1 < r < p, где величины (0\={p-\)mm{tl,t£n} и w2 = T' (p, n, p,s)~ p max /f

^ 1<1<П

представляют собой временные отрезки максимально возможного совмещения 1-й и (1+\)-й диаграмм Ганта, а £ =(/■-!)min{t',fn} + (р-r)t'„

и Ь2 = Т!,р (Р> п, р, е) - max (т{ор (р, /, р, е) - top (р, i,r,s) + rt1) - временные

отрезки максимально возможного совмещения по оси времени к-й и (к +1) -й диаграмм

В 2 3 в рамках математической модели организации распределенной обработки конкурирующих процессов, введенной в 1 4, исследуется второй синхронный режим, т е когда для каждого блока структурированного программного ресурса момент завершения его выполнения для /-го процесса совпадает с моментом начала его выполнения для (1+1)-то процесса на том же процессоре В условиях рассматриваемого режима для любых р> 2, п> 2, £ > 2, £>0, получены временные характеристики реализации выполнения неоднородных, однородных и одинаково распределенных конкурирующих процессов Остановимся на одинаково распределенных процессах, так как именно для этого класса в диссертации проведен сравнительный анализ и получены критерии эффективности и оптимальности

Для определения минимального общего времени Т*р(р,п,$,е) выполнения п конкурирующих одинаково распределенных процессов в многопроцессорной системе с р процессорами во втором синхронном режиме взаимодействия процессов, процессоров и блоков с учетом параметра е > 0, имеет место

Теорема 23 Минимальное общее время выполнения множества конкурирующих одинаково распределенных процессов во втором синхронном режиме при любых р> 2, п> 2, л > 2, ¿г > 0, определяется по формулам

ТЧр,п,5,е) =

УУ+С$-1)тах;,\ 5 <р,

I-1

п

к^^ +(р-\)тах^, я = кр, к>1,

П

+ +(/--1)тах/,\ Б = кр + г, к> 1, 1 <г<р

В 24 проведен сравнительный анализ асинхронного и двух синхронных режимов организации одинаково распределенных конкурирующих процессов с точки зрения временных затрат и с учетом параметра £ В 2 1-2 3 для асинхронного и второго синхронного режимов получена формула

т:; (р, п, е) = Тгор (р, п, з, е) = т; + (* - 1)С

а для первого синхронного режима

п

и

где Т" = - суммарное время выполнения каждого из блоков Q¡

-у

7 =1,5', всеми п процессами с учетом накладных расходов е,

1<1<И

В работе набор параметров (/,', , 1сп, Т") одинаково распределенной системы конкурирующих процессов определен как характеристический

чено множество всех допустимых характеристических наборов систем одинаково распределенных конкурирующих процессов, из которого выделено подмножество характеристических наборов вида

нес) = {«:, П, , с, т:)ер I е2 < <// > >/;,/=!,«}

Доказаны следующие утверждения

Теорема 24 Пусть 8 е Н (Т") — характеристический набор любой одинаково распределенной системы с параметрами р, п, 5 и накладными расходами £ > 0 Тогда в случае 2<я<р минимальные

общие времена Т°р , Т'р и выполнения множества одинаково распределенных конкурирующих процессов в асинхронном и базовых синхронных режимах совпадают

Теорема 25 Для любой одинаково распределенной системы с параметрами р, п, з и накладными расходами е > О, допустимый характеристический набор которой б £ Н(Т"), при 2 < £ < р выполняются соотношения Т'р (р, п, е) > Т("р (р, п, 5, е) = (р, п, л, е)

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

взаимодействующих одинаково распределенных конкурирующих процессов в условиях неограниченного и ограниченного параллелизма с учетом накладных расходов по времени их реализации

В 3 1 в классе одинаково распределенных систем конкурирующих процессов выделен специальный подкласс стационарных систем, т е когда г, = /2 = ~ 1п~ I Показано, что для всех трех базовых режимов в случае стационарной одинаково распределенной системы конкурирующих процессов в случае неограниченного параллелизма минимальное общее время их выполнения Те определяется равенством

/>) = (и + 5 -1)/г , где ^ = Т"/п + е, Т" = Ш

Одинаково распределенную систему конкурирующих процессов будем называть эффективной при фиксированных р, .у > 2, если выполняется соотношение Ае(п) = хТ" -Т(р,п^,е)>0, где хТ" - время выполнения блоков всеми п процессами в последовательном режиме При наличии двух эффективных одинаково распределенных систем конкурирующих процессов будем считать, что первая более эффективна, чем вторая, если величина Де(п) первой системы не меньше соответствующей величины второй

Для введенного подмножества одинаково распределенных систем доказано утверждение

Теорема 31 Для любой эффективной одинаково распределенной системы конкурирующих процессов при 2 <я<р и £>0 существует стационарная более эффективная одинаково распределенная система

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

Теорема 32 Одинаково распределенная система конкурирующих процессов с параметрами р, п, .1, в, удовлетворяющая соотношениям 3<я< р, п = йФ 3, яи> 2{п + 5-1) и 0<£< ГП1П ,

1<1<п

является эффективной

Теорема 33 Для существования эффективной одинаково распределенной системы конкурирующих процессов с заданными пара-

метрами Ъ<8<р, Т", £ > 0 необходимо и достаточно, чтобы выполнялись следующие условия

е<

\<p{\+4~s),

если

Ts-

¡max{^(l + [Vs]), 9>(2 + [л/у])}, если-Js-

■ целое, целое,

где ip(x) = ——^ ——, [х] - наибольшее целое, не превосходя-x{x + s-\)

щее х

В 3 2 получены необходимые и достаточные условия эффективности одинаково распределенных систем конкурирующих процессов в случае, когда число процессоров является ограниченным

Теорема 34 Если параметры одинаково распределенной системы п > 3 конкурирующих процессов в многопроцессорной системе с р процессорами удовлетворяют соотношениям s> 3, п = s* 3 и О < е < min t,, то рассматриваемая система будет эффективной, если

1<1<Я

выполняются усчовия

sn >

2{kn + p-\),

если s = kp, k> 1,

2({k + \)n + r-X), если s = kp + r, k > 1, 1 <r<p

Теорема 35 Для существования эффективной одинаково распределенной системы конкурирующих процессов с заданными параметрами р> 3, Т", £ > О необходимо и достаточно, чтобы выполнялись следующие условия 1) при я = кр, к>\,

е<

1+4Р к

шах <

1+4Р

\ г

, <Р1

У

1+4Р

+i

1+УР

если --— -целое,

если--— - нецелое,

где = (р - \)Т"(кх-У)/х(кх + р-\), а [х] - наибольшее целое, не превосходящее х,

2) при 5 = кр + г, Л > 1, 1 < г < р,

е<

<Рг(х),

если х -целое,

тах{#>2([х]), (р2([х\ + \)}, если х -нецелое,

где (рг (.х) =

[(р-!)£* +(г-1)(х-1)] Г х [(¿ + 1)х + г-1]

'И

> М — наибольшее цепое, не

(р-\)к + г-\ к +1

л

превосходящее х, где х =

V

В 3 3 введено определение оптимальной одинаково распределенной системы эффективная одинаково распределенная система называется оптимальной, если величина Ае достигает наибольшего значения

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

Теорема 36 Для того, чтобы эффективная одинаково распределенная система конкурирующих процессов была оптимальной при заданных 2 <я<р, Т", е > 0, необходимо и достаточно, чтобы она была стационарной и число процессов п0 в системе равнялось одному из чисел

в котором функция Л£ (х) достигает наибольшего значения Здесь [х] означает наибольшее целое, не превосходящее х, п - заданное число

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

А,(л:) = (^-1 )Тп-(р —{кх + р-\)е,прп 5 = кр, к>\,

Ае(х) = (5 - к -1 )Г -(г 1)Г—((А + 1)х + (г - 1))е , при 5 = кр + г, к> 1, 1 < г < р

Теорема 37 Для того, чтобы эффективная одинаково распределенная система конкурирующих процессов в случае ограниченного параллелизма в асинхронном и втором синхронном режимах была оптимальной при заданных р> 2, Т", е > 0, необходимо и достаточно, чтобы она была стационарной и число процессов п в системе равнялось одному из чисел

1)

/(р-1)Г 1(р- 1)Г + 1

V ке 9 V ке \

, при з = кр, к> 1,

2)

1(г-1)Г \(Г-\)Т" + 1

V (Л + 1)г \ (к + 1)е

, при я = кр + г, к > 1, 1 < г < р,

в котором функция Ае(х) достигает наибольшего значения, где [х] - наибольшее целое, не превосходящее х

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

Основные результаты работы

1 Решены задачи нахождения минимального общего времени выполнения неоднородных, однородных и одинаково распределенных конкурирующих процессов в асинхронном и синхронных режимах с учетом дополнительных системных расходов, связанных с организацией параллельного использования блоков структурированного программного ресурса множеством конкурирующих процессов при распределенной обработке [1-2, 5, 8-10, 13-14]

2 Проведен сравнительный анализ времен выполнения в базовых режимах одинаково распределенных конкурирующих процессов при достаточном числе процессоров многопроцессорной системы [3,5-6]

3 Для всех трех базовых режимов в случае достаточного числа процессоров, а для асинхронного и второго синхронного режимов взаимодействия конкурирующих процессов в общем случае, получены достаточные условия эффективности одинаково распределенных систем конкурирующих процессов [1,3,10,15]

4 Определены условия существования эффективных систем одинаково распределенных конкурирующих процессов в зависимости от величины дополнительных системных расходов [1,3, 10]

5 В условиях неограниченного и ограниченного параллелизма получены условия оптимальности одинаково распределенных систем конкурирующих процессов [4,7,11]

Список публикаций по теме диссертации

1 Капитонова Ю В , Коваленко Н С., Павлов П А Оптимальность систем одинаково распределенных конкурирующих процессов // Кибернетика и системный анализ -2005 -№6.-С 3-10

2 Коваленко Н С , Павлов П А Эффективность и оптимальность структурирования программных ресурсов при распределенной обработке//Труды минского института управления -2005 -№1 -С 104— 107

3 Коваленко Н С , Павлов П А Эффективность систем конкурирующих процессов с учетом накладных расходов // Доклады НАН Беларус1 Сер ф13-мат навук -2005 -№6 - С 32-36

4 Коваленко Н С , Павлов П А Системы одинаково распределенных конкурирующих процессов в условиях ограниченного параллелизма и их оптимальность // Доклады НАН Беларус1 Сер фв -мат навук.-2006 -№2 - С 25-29

5. Павлов П А Анализ режимов организации одинаково распределенных конкурирующих процессов // Вестник БГУ Сер 1 Физ Мат Информ -2006 -№1 -С 116-120

6 Павлов П А Сравнительный анализ одинаково распределенных конкурирующих процессов с учетом дополнительных системных расходов // Вестник Фонда фундаментальных исследований - 2006 -№1 -С 55-58

7 Коваленко Н С, Павлов П.А Оптимальность одинаково распределенных систем конкурирующих процессов // Информ системы и технологии IST'2006 Материалы третьей Междунар конф Минск, 1-

3 ноября 2006 г / Акад упр при Президенте Респ Беларусь - Минск, 2006 - С 232-235

8 Павлов П А Синхронный режим взаимодействия распределенных конкурирующих процессов с непрерывным выполнением блоков // Сициально-экономическое и гуманитарное развитие белорусского общества в XXI веке Материалы респ науч конф Минск, 16 дек 2004 г /БГЭУ -Минск, 2005 -С 426-427

9 Павлов П А Коэффициенты ускорения и эффективности при распределенной обработке // Экономический механизм формирования национальной модели развития экономики РБ Материалы науч-практ конф Пинск, 22-23 февраля 2005 г / БГЭУ - Минск, 2005 - С 98-100

10 Павлов ПА Эффективность систем одинаково распределенных конкурирующих процессов // Актуальные проблемы рыночной экономики Материалы II науч -практ конф Бобруйск, 7 апр 2005 г / БГЭУ -Минск, 2005 - С 141-144

11 Павлов П А Оптимальность систем одинаково распределенных конкурирующих процессов при достаточном числе процессоров // Экономическое развитие Беларуси в контексте расширения Европейского Союза- Материалы Междунар студ науч конф Гродно, 12-13 мая 2005 г В2ч ч 2/ГрГУ -Гродно, 2005 -С 27-28

12 Павлов П А Приемы ускорения вычислений // Исследования молодых ученых Пинщины Материалы II науч -практ конф Пинск, 14 мая 2005 г / БГЭУ - Пинск, 2005 - С 106-110

13 Павлов ПА Минимальное общее время выполнения распределенных конкурирующих процессов в асинхронном режиме в случае неограниченного параллелизма // Механизм формирования социально-экономического развития регионов Республики Беларусь в условиях перехода к рыночной экономике Материалы науч -практ конф Пинск, 21-22 февраля 2006 г / БГЭУ -Минск, 2006 - С 103-104

14 Павлов ПА Минимальное общее время выполнения неоднородных распределенных конкурирующих процессов в первом синхронном режиме // Механизмы устойчивого развития инновационных социально-экономических систем Материалы международной науч -практ конф Бобруйск, 30 марта 2006 г / БГЭУ - Минск, 2006 - С 162-164

15 Павлов ПА Критерии эффективности организации выполнения множества распределенных конкурирующих процессов // Социально-экономическое и историко-культурное развитие Полесского региона в XXI веке Материалы международной науч -практ конф Пинск, 5-6 мая 2006 г / КУП, - Пинск, 2006 - С 163-165

Подписано в печать 14 01 2008 г Исполнено 14 01 2008 г Печать трафаретная

Заказ №381 Тираж 100 экз

Отпечатано в редакционно-издательском отделе Полесского государственного университета 225710, г Пинск, ул Днепровской флотилии, 23

Введение.

Общая характеристика работы

1. Математическая модель распределенной обработки конкурирующих процессов.

1.1. Обзор литературы по параллельным вычислениям.

1.2. Конструктивные элементы распределенной обработки

1.3. Концепция структурирования в параллельном программировании

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

2. Время реализации конкурирующих процессов при распределенной обработке.

2.1. Минимальное общее время выполнения конкурирующих процессов в асинхронном режиме.

2.2. Синхронный режим с непрерывным выполнением блоков программного ресурса каждым из процессов.

2.3. Синхронный режим распределенных конкурирующих процессов непрерывным переходом по'процессам.

2.4. Анализ режимов организации распределенных конкурирующих процессов.

3. Задачи оптимальной организации конкурирующих процессов при распределенной обработке.

3.1. Критерии существования эффективных одинаково распределенных систем конкурирующих процессов.

3.2. Эффективность одинаково распределенных систем в условиях ограниченного параллелизма.

3.3. Оптимальность одинаково распределенных систем конкурирующих процессов.

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

4.1. Приемы ускорения вычислений и их эффективность.

4.2. Краевая задача для оператора Лапласа.

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

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

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

Отметим набор причин, в силу которых в настоящее время параллельные вычисления являются перспективной областью теоретических исследований и их практических применений [13]: я несмотря на подтверждаемый на практике закон Гроша (Grosch), согласно которому производительность компьютера возрастает пропорционально квадрату его стоимости, следует учесть, что рост быстродействия последовательных ЭВМ не может продолжаться бесконечно, кроме того, компьютеры подвержены быстрому моральному старению', согласно гипотезе Минского (Minsky), ускорение, достигаемое при использовании параллельной системы, пропорционально двоичному логарифму от числа процессоров, но подобная оценка ускорения может иметь место при распараллеливании определенных алгоритмов, вместе с тем, существует большое количество задач, при параллельном решении которых достигается 100% использование всех имеющихся процессоров параллельной вычислительной системы; в соответствии с законом Мура (Moore) происходит постоянное совершенствование последовательных компьютеров, мощность которых возрастает практически в 2 раза каждые 18^24 месяца, на это замечание можно отметить, что аналогичное развитие свойственно и параллельным системам, кроме того, применение параллелизма позволяет получать желаемое ускорение вычислений без какого-либо ожидания новых более быстродействующих процессоров; согласно закона Амдаля (Amdahl), ускорение процесса вычислений при использовании р процессоров ограничивается величиной 1 d+(l-d)/p' где d есть доля последовательных вычислений в применяемом алгоритме, однако часто доля последовательных операций характеризует не невозможность параллельного решения задач, а последовательные свойства применяемых алгоритмов, как результат, доля последовательных вычислений может быть существенно снижена при выборе подходящих для распараллеливания алгоритмов', параллельные системы отличаются существенным разнообразием архитектурных принципов построения, и получить максимальный эффект от использования параллелизма бывает затруднительно, но в последовательных ЭВМ тоже присутствуют способы параллелизма, такие как конвейерные вычисления, многопроцессорные системы и т. п., кроме того, инвариантность создаваемого программного обеспечения может быть обеспечена и при помощи использования типовых программных средств поддержки параллельных вычислений типа программных библиотек MPI, PVJV1 и др.; существующее программное обеспечение ориентировано в основном на последовательные ЭВМ, переработка которого не является необходимой, если оно обеспечивает решение поставленных задач, однако если последовательные программы не позволяют получать решения задач за приемлемое время или же возникает необходимость решения новых задач, то необходимой становится разработка нового программного обеспечения в параллельном выполнении.

Подведя итог вышесказанному, можно заключить, что организация параллельных вычислений представляет собой довольно сложную научно-техническую проблему, решение которой подразделяется на следующие направления деятельности: разработка распределенных вычислительных систем [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 научно-практических конференциях: третьей международной конференции «Информационные системы и технологии IST'2006», секция «Параллельная и распределенная обработка данных» (Минск, 2006); республиканской научной конференции «Социально-экономическое и гуманитарное развитие белорусского общества в XXI веке», секция «Информационные технологии и математические методы в экономике» (Минск, 2004); научно-практической конференции «Экономический механизм формирования национальной модели развития экономики РБ», секция «Развитие информационных технологий в Республике Беларусь» (Пинск, 2005); II научно-практической конференции «Актуальные проблемы рыночной экономики», секция «Статистические и математические методы в экономике» (Бобруйск, 2005); международной научной конференции «Экономическое развитие Беларуси в контексте расширения Европейского Союза», секция «Информационные технологии в экономических процессах» (Гродно, 2005); II научно-практической конференции «Исследования молодых ученых Пинщины», секция «Информационных технологий и компьютерные коммуникации» (Пинск, 2005); научно-практической конференции «Механизм формирования социально-экономического развития регионов Республики Беларусь в условиях перехода к рыночной экономике», секция «Внедрение информационных технологий в повышение эффективности социально-экономического развития Белорусского Полесья» (Пинск, 2006); международной научно-практической конференции «Механизмы устойчивого развития инновационных социально-экономических систем», секция «Статистические и математические методы в экономике» (Бобруйск, 2006); международной научно-практической конференции «Социально-экономическое и историко-культурное развитие Полесского региона в XXI веке», секция «Техника, информационных технологий и компьютерные коммуникации» (Пинск, 2006); VII международной конференции «Проблемы прогнозирования и государственного регулирования социально-экономического регулирования», секция «Математическое регулирование экономических процессов» (Минск, 2006).

Опубликованность результатов

Основные результаты диссертации опубликованы в 16 работах. Статей в научных и научно-теоретических журналах 6. Количество опубликованных в них материалов 1,42 авторских листа. Тезисов докладов и выступлений на международных и республиканских научных конференциях 10.

Структура и объем диссертации

Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения и библиографического списка из 85 наименований, Объем диссертационной работы составляет 91 страниц машинописного текста, включая 10 рисунков.

Основные результаты диссертационного исследования, выносимые на защиту: решены задачи нахождения минимального общего времени выполнения неоднородных, однородных и одинаково распределенных конкурирующих процессов в асинхронном и синхронных режимах с учетом дополнительных системных расходов, связанных с организацией параллельного использования блоков структурированного программного ресурса множеством конкурирующих процессов при распределенной обработке [23, 35, 52, 54-56]; проведен сравнительный анализ временной, сложности базовых режимов организации одинаково распределенных конкурирующих процессов при достаточном числе процессоров многопроцессорной системы [36, 5253]; в случае неограниченного параллелизма получено условие существования для любой эффективной одинаково распределенной системы конкурирующих процессов более эффективной одинаково распределенной системы [23, 36, 56]; для всех трех базовых режимов в случае достаточного числа процессоров, а для асинхронного и второго синхронного режимов взаимодействия конкурирующих процессов в общем случае, получены достаточные условия эффективности одинаково распределенных систем конкурирующих процессов [23, 36, 56]; определены критерии существования эффективных систем одинаково распределенных конкурирующих процессов в зависимости от величины дополнительных системных расходов [23, 36, 56]; в условиях неограниченного и ограниченного параллелизма получены критерии оптимальности одинаково распределенных систем конкурирующих процессов [57].

Рекомендации по практическому использованию результатов

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

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

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

ЗАКЛЮЧЕНИЕ

Результаты, представленные в настоящей диссертационной работе, фрагментарно были опубликованы в работах [23, 35-36, 52-58]. Ряд положений, представленных к защите, прошли теоретическую и практическую апробацию в виде выступлений на научных и научно-практических конференциях и семинарах, а также в ходе выполнения с 01.05.2004 г. по 01.06.2006 г. научно-исследовательских работ в рамках Белорусского республиканского фонда фундаментальных исследований по теме «Разработка новых подходов к распараллеливанию численных методов математической физики на основе анализа тонких свойств графов», проект № Ф04Р-156.

Основные научные результаты диссертации

1. Антонов А. С. Параллельное программирование с использованием технологии MP1. - М.: МГУ, 2004. - 71 с.

2. Барский А. Б. Параллельные процессы в вычислительных системах: Планирование и организация. М.: Радио и связь, 1990. - 256 с.

3. Богачев К. Ю. Основы параллельного программирования. М.: БИНОМ, 2003.-342 с.

4. Б оч ар о в Н. В. Технологии и техника параллельного программирования // Программирование. 2003. - №1. - С. 5-23.

5. Бройдо В. Л. Вычислительные системы, сети и телекоммуникации. СПб.: Питер, 2002. - 688 с.

6. Букатов А. А., Дацюк В. Н., Жегуло А. И. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону: ЦВВ, 2003. -208 с.

7. Вабищевич А. М., Коваленко Н. С. Приемы ускорения вычислений при векторно-конвейерной обработке. Минск, 1991. - 20 с. (Препринт / АН БССР. Ин-т математики; № 10(460)).

8. Валкомскиц В. А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. - 176 с.

9. Высокопроизводительные параллельные вычисления на кластерных системах: Сб. ст. / Нижегородского ун-т.; Под ред. Р. Г. Стронгина. -Н. Новгород, 2002. 217 с.

10. Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

11. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. 608 с.

12. Воеводин Вл. В. Распределенная обработка данных // Вторая сибирская школа-семинар по параллельным вычислениям / ТГУ. 2004. - С. 3-9.

13. Гергель В. П., Стронгин Р. Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Н. Новгород: ННГУ, 2001.- 122 с.

14. Головкин Б. А. Параллельные вычислительные системы. М.: Наука, 1980.-520 с.

15. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272 с.

16. Дейт л Г. Введение в операционные системы. М.: Мир, 1984. -255 с,

17. Евстигнеев В. Н., Касьянов В. А. Графы в программировании: обработка, визуализация и применение. М.: BHV, 2003. - 1104 с.

18. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. -384 с.

19. Иванников В. П., Коваленко Н. С., Метельский В. М. О. минимальном времени реализации распределенных конкурирующих процессов в синхронных режимах // Программирование. 2000. - №5. - С. 44-52.

20. Ильин В. П. О стратегиях распараллеливания в математическом моделировании // Программирование. 1999. - № 1. - С. 41-46.

21. КанцедалС. А. Последовательные и параллельные вычисления в общей задаче теории расписаний // Автоматика и телемеханика. 1989. - № 12,- С. 153-160.

22. Капитонова Ю. В., Коваленко Н. С., Овсеец М. И. Эффективность конвейерной реализации конкурирующих процессов при ограниченном числе копий программного ресурса // Кибернетика. 1989. - №3. - С. 60-65.

23. Капитонова Ю. В., Коваленко Н. С., Павлов П.А. Оптимальность систем одинаково распределенных конкурирующих процессов // Кибернетика и системный анализ. 2005. - №6. - С. 3-10.

24. Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычислительных систем. М.: Наука, 1988. - 296 с.

25. Капитонова Ю. В., Овсеец М. И. Алгоритм построения оптимальной компановки линейно структурированных программных ресурсов // Кибернетика. 1986. - №1. - С. 5-8.

26. Коваленко Н. С. О некоторых задачах анализа параллельных вычислений // Кибернетика. 1980. - №3. - С. 142-144.

27. Коваленко Н. С. Сосредоточенная обработка неоднородных конкурирующих процессов // Управляющие системы и машины. 1998. - №2. -С. 29-34.

28. Коваленко Н. С. О минимальном времени реализации сосредоточенных конкурирующих процессов в синхронных режимах // Управляющие системы и машины. 1998. - №3. - С. 10-16.

29. Коваленко Н. С., Метельский В. М. О времени реализации конкурирующих процессов при распределенной обработке // Кибернетика и системный анализ. 1996. - №1. - С. 54-64.

30. Коваленко Н. С., Метельский В. М. Режимы взаимодействия неоднородных распределенных конкурирующих процессов // Кибернетика и системный анализ. 1997. - №3. - С. 31-43.

31. Коваленко Н. С., Метельский В. М. Синхронный режим взаимодействия конкурирующих процессов при распределенной обработке // Весщ НАН Беларусь Сер. ф1з.-мат. навук. 1998. - №1. - С. 117-122.

32. Коваленко Н. С., Метельский В. М. Организация синхронного выполнения распределенных конкурирующих процессов // Весщ НАН Беларусь Сер. ф1з.-мат. навук. 1998. - №2. - С. 117-121.

33. Коваленко Н. С., Метельский В. М. Оптимальность структурирования программных ресурсов при распределенной обработке // Кибернетика и системный анализ. 1999. - №6. - С. 59-62.

34. Коваленко Н. С., Метельский Н. С., Самаль С. А. Оптимизация числа процессоров при реализации неоднородных распределенных конкурирующих процессоров // Кибернетика и системный анализ. 2003. -№6. - С. 52-61.

35. Коваленко Н.С., Павлов П.А. Эффективность и оптимальность структурирования программных ресурсов при распределенной обработке // Труды минского института управления. 2005. - №1. - С. 104-107.

36. Коваленко Н.С., Павлов П.А. Эффективность систем конкурирующих процессов с учетом накладных расходов // Доклады НАН Беларусь Сер. ф1з.-мат. навук. 2005. - №3. - С. 32-36.

37. Коваленко Н. С., Самаль С. А. Минимизация общего времени выполнения заданных объемов вычислений в синхронных режимах // Кибернетика и системный анализ. 2003. - №6. - С. 39-47.

38. Коваленко Н. С., Самаль С. А. Вычислительные методы реализации интеллектуальных моделей сложных систем. Минск: Бел. навука, 2004.- 166 с.

39. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. М.: Наука, 1978. - 352 с.

40. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНТО, 2000. - 960 с.

41. КорнеевВ. В. Параллельные вычислительные системы. М.: Но-лидж, 1999.-320 с.

42. Кор не ев В. В. Параллельное программирование в MPI. М.Ижевск: Институт компьютерных исследований, 2003. - 304 с.

43. КорнеевВ.В., Киселев А. В. Современные микропроцессоры. -М.: Нолидж, 1999. 320 с.

44. Костпенко В. А. К вопросу об оценке оптимальной степени параллелизма // Программирование. 1995. - №4. - С. 24-28.

45. Крюков В. А. Разработка параллельных программ для вычислительных кластеров и сетей. http://parallel.ru.

46. Лацис А. Как построить и использовать суперкомпьютер. М.: Бестселлер, 2003. - 274 с.

47. Марков Н. Г., Мирошниченко Е. А., Сарайкин А. В. Моделирование параллельного программного обеспечения с использованием PS-сетей // Программирование. 1995. - №5. - С. 24-32.

48. Миренков Н. Н. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989. - 320 с.

49. Мищенко В. А., Лазаревич Э. Г., Аксенов А. И. Расчет производительности многопроцессорных вычислительных систем. Минск: Вышейшая школа, 1985. - 208 с.

50. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф. Г. Э н с л о у: Пер. с англ. М.: Мир, 1976. 383 с.

51. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ-Петербург, 2002. -396 с.

52. Павлов П. А. Анализ режимов организации одинаково распределенных конкурирующих процессов // Вестник БГУ. Серия 1: Физ. Мат. Ин-форм. -2006.-№1.-С. 116-120.

53. Павлов П. А. Сравнительный анализ одинаково распределенных конкурирующих процессов с учетом дополнительных системных расходов // Вестник Фонда фундаментальных исследований. 2006. - №1. - С. 55 - 58.

54. Павлов П.А. Эффективность систем одинаково распределенных конкурирующих процессов // Актуальные проблемы рыночной экономики: Материалы II науч.-практ. конф. Бобруйск, 7 апр. 2005 г. / БГЭУ. Минск,2005.-С. 141-144.

55. Павлов П. А. Приемы ускорения вычислений // Исследования молодых ученых Пинщины: Материалы II науч-практ. конф. Пинск, 14 мая 2005 г./БГЭУ.-Пинск, 2005.-С. 106-110.

56. Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации. Киев: Наук, думка, 1988. - 472 с.

57. Сергиенко И. В., Шило В. П., Рощин В. А. Распараллеливание процесса оптимизации для задач дискретного программирования // Кибернетика и системный анализ. 2004. - №2. - С. 45-52.

58. Системы параллельной обработки / Под ред. Д. И в е н с а. М.: Мир, 1985.-371 с.

59. Столингс В. Структурная организация и архитектура компьютерных систем. М.: Вильяме, 2002. - 896 с.

60. Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. - 328 с.

61. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. -М.: Наука, 1975.-256 с.

62. Теория расписаний и вычислительные машины / Под ред. Э. Г. Коффмана.-М.: Наука, 1984.-336 с.

63. Хамахер К., Вранешич 3., Заки С. Организация ЭВМ. СПб.: Питер, 2003. - 848 с.

64. Хокни Р., Джессхоуп К. Параллельные ЭВМ: архитектура, программирование, алгоритмы. М.: Радио и связь, 1986. - 389 с.68: Шпаковский Г. И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие. Минск: БГУ, 1996. - 284 с.

65. Шпаковский Г. И., Серикова Н. В. Программирование для многопроцессорных систем в стандарте MPI: Пособие. Минск: БГУ, 2002. -323 с.

66. Эндрюс Г. Р. Основы многопоточного, параллельного и рапреде-леннош программирования: Пер. с англ. М.: Издательский дом "Вильяме",2003.- 512 с.

67. Элементы параллельного программирования / В. А. Вольский, В. Е. Котов, А. Г. Марчук, Н. Н. Миренков. М.: Радио и связь, 1983. -240 с.

68. Babaoglu Ozalp, Bartoli Alberto, Dini Gianluca. Enriched view synchrony: A programming paradigm for partitionable asynchronous distributed systems // IEEE Trans. Computers, 1997. Vol. C-46, - №6. - P. 642-658.

69. Braeunnl T. Parallel Programming. An Introduction. Prentice Hall, 1996.

70. Chandra R., Menon R., Dagum L., Kohr D., Maydan D., McDonald J. Parallel Programming in OpenMP. Morgan Kaufmann Publishers, 2000.

71. Data forwarding in scalable sharedmemory multiprocessors / D. Kou-faty, X. Chen, D. Poulsen, J. Torrelas // IEEE Trans. Parall. and Distrib. Syst, 1996. Vol. 7, - №12. - P. 1250-1264.

72. Dimitri P., John N. Parallel and Distributed Computation. Numerical Menhods. Prentice Hall, Englewood Cliffs, New Jersey, 1989.

73. Fox G. Solving Problems on Concurrent Processors. Prentice Hall, Englewood Cliffs, New Jersey, 1988.

74. Geist G., Beguelin A., Dongarra J., Jiang W., Manchek В., Sunder am V. PVM: Parallel Virtual Machine A User's Guide and Tutorial for Network Parallel Computing. - MIT Press, 1994.

75. Kovalenko N. S., Metelski V. M. The speed-up of computation in distributed processing of competing processes // First International Conference on Parallel Processing and Applied Mathematics. Czestochova, Poland, 1994. P. 92-99.

76. Kovalenko N. S., Metelski V. M. On a Distributed processing of Competing Processes // International Conference on Advanced Mathematics, Computations and Applications. Novosibirsk, 1995. P. 187-188.

77. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing. The Benjamin/Cummings Publishing Company Inc., 1994. •

78. Nevis on C. Teaching parallel computing using transputers // Parallel Computting Technologies, Processings of the International Conference. Obninsk-Moscow: NT-Center, 1993. P. 619-629.

79. Miller R., Boxer L. A Unified Approach to Sequential and Parallel Algorithms. Prentice Hall, Upper Saddle River, New Jersey, 2000.

80. P а с h e с о S. Parallel programming with MPI. Morgan Kaufmann Publishers, San Francisco, 1997.

81. WoegingerG. J. A polynomial-time approximation scheme for maximizing the minimum machine completion time // Oper. Res. Lett. 1997. - Vol. 20, - №4. - P. 149-154.