Содержание к диссертации
Введение
Глава 1. Распределенные вычислительные системы с программируемой структурой 15
1.1. Понятие о вычислительных системах с программируемой, структурой 15
1.1.1. Модель коллектива вычислителей 15
1.1.2. Классификация ВС 19
1.1.3. Особенности ВС с программируемой структурой 21
1.2. Основные режимы функционирования ВС 23
1.2.1. Монопрограммный режим 23
1.2.2. Мультипрограммные режимы 24
1.3. Организация функционирования ВС в мультипрограммных режимах 25
1.3.1. Алгоритмы организации функционирования ВС 25
1.3.2. Обзор средств поддержки мультипрограммных режимов 28
1.4. Выводы 31
ГЛАВА 2. Алгоритмы функционирования распределенных ычислительных систем в режиме обработки задач набора 33
2.1. Оптимизация загрузки ВС при обработке задач набора 33
2.2. Точный алгоритм распределения задач набора по элементарным машинам ВС 37
2.3. Эвристические алгоритмы распределения задач набора с фиксированными параметрами 2.3.1. Формирование пакетов задач 45
2.3.2. Минимизация времени решения задач набора на ВС 52
2.3.3. Параллельный алгоритм минимизации времени решения задач набора на ВС 58
2.3.4. Минимизация штрафа за задержку решения задач набора на ВС 63
2.3.5. Параллельный алгоритм минимизации штрафа за задержку решения задач набора на ВС 67
2.4. Эвристические алгоритмы распределения набора
задач с нефиксированными параметрами 7 0
2.4.1. Минимизация времени решения задач набора на ВС 7 0
2.4.2. Минимизация штрафа за задержку решения задач набора на ВС 74
2.5. Выводы 77
ГЛАВА 3. Алгоритмы функционирования распределенных вычислительных систем в режиме обслуживания потока задач 7 8
3.1. Создание многопроцессорного расписания для потока параллельных задач 7 8
3.2. Децентрализованный алгоритм организации подсистем в ВС 7 9
3.3. Децентрализованный алгоритм создания многопроцессорного расписания 93
3.4. Механизмы обеспечения отказоустойчивости при
формировании подсистем в ВС 96
3 б Выводы 100
ГЛАВА 4. Программное обеспечение распределенной мультикластерной вычислительной системы 101
4.1. Архитектура мультикластерной ВС Центра Параллельных Вычислительных Технологий СибГУТИ 101
4.2. Моделирование алгоритмов распределения параллельных задач набора с постоянными параметрами 103
4.3. Моделирование алгоритмов распределения набора параллельных задач с нефиксированными параметрами 108
4.4. Моделирование алгоритмов организации подсистем и создания многопроцессорного расписания 112
4.5. Программное обеспечение распределенной мультикластерной ВС 114
4.5.1. Состав программного обеспечения. Стандартные компоненты 114
4.5.2. Программное обеспечение для поддержки мультипрограммных режимов 116
4.6. Выводы 120
Заключение 121
Литература
- Особенности ВС с программируемой структурой
- Точный алгоритм распределения задач набора по элементарным машинам ВС
- Децентрализованный алгоритм организации подсистем в ВС
- Моделирование алгоритмов распределения параллельных задач набора с постоянными параметрами
Введение к работе
Актуальность работы. Потребность в высокопроизводительных средствах обработки информации привела к созданию вычислительных систем (ВС) с массовым параллелизмом [8,28,29,101,156]. В общем случае ВС есть композиция элементарных машин (ЭМ) и сети межмашинных связей, способная осуществлять параллельную обработку информации. Построение таких систем основывается на следующих принципах:
параллельность выполнения операций;
программируемость структуры;
конструктивная однородность.
Одним из типов архитектур вычислительных систем являются распределённые ВС. Все основные ресурсы таких систем (арифметико-логические устройства, память и средства управления) являются логически и технически рассредоточенными. Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч и более (например, в МВС-15000ВМ это число равно 924, а в создаваемой системе IBM Blue Gene планируется до 1 000 000).
Для решения задач могут использоваться как все ЭМ (вся система целиком), так и часть из них. В последнем случае возможно одновременное решение нескольких задач, путём организации параллельного мультипрограммного режима. Опыт применения распределённых ВС показал, что, чаще всего, для решения задач не требуются ресурсы всей системы [37,38,40-51]. Поэтому проблема создания средств организации функционирования распределенных ВС
в мультипрограммных режимах на сегодняшний день является актуальной.
Разработки распределенных вычислительных систем ведутся с середины XX столетия. С тех пор, выполнен ряд фундаментальных работ, посвященных проблемам организации высокопроизводительных вычислительных средств: проведены исследования по теории функционирования и построению оптимальных (макро)структур ВС, проработаны многие аспекты разработки программного обеспечения, исследован широкий круг задач, допускающий эффективную реализацию на распределённых ВС. Построены отечественные вычислительные системы с программируемой структурой: СУММА, МИНИМАКС, МИКРОС, МВС-100, МВС-1000, МВС-1000М, МВС-15000ВМ и т.д.
Фундаментальный вклад в теорию и практику вычислительных систем и параллельных вычислительных технологий внесли советские и российские учёные, среди которых: Е.П.Балашов [2,3], В.Б. Бетелин [1], B.C. Бурцев [8,9], В.В. Васильев [10], В.В. Воеводин [12], В.М. Глушков [15,16], В.Ф. Евдокимов [25], Э.В.Евреинов [26-29], А.В. Забродин [32], В.П. Иванников [34], М.Б. Игнатьев [16,35], А.В. Каляев [36,37], Л.Н. Королев [51], В.Г.Лазарев [54], С.А.Лебедев [56], В.К. Левин [57], Г.И.Марчук[65] , Ю.И.Митропольский[66], С.В.Пискунов[78-80], Д.А. Поспелов [81], И.В. Прангишвили [82,83], Д.В. Пузанков [3,11], Г.Е. Пухов [84], Г.Г. Рябов [86], А.А. Самарский [133], В.Б. Смолов [3,96], А.Н. Томилин [105], Я.А. Хетагуров [110], В.Г. Хорошевский [23,29, 30,49,50,113-125,134], Б.Н.Четверушкин [128], Ю.И.Шокин [129], Н.Н. Яненко [134], а также зарубежные учёные:
S. Cray [138], M. Flynn [138], I. Foster [135], D. Hillis [144], C. Kesselman [141], DL.Slotnick [155], A. Tanenbaum [100,101] и другие. При решении проблем оптимизации функционирования распределенных ВС большую роль сыграли фундаментальные работы по оптимальному управлению и исследованию операций советских и российских ученых: В.Л. Вереснева [6], Э.Х. Гимади [14], В.Т.Дементьева [21], Ю.И. Журавлева [31], К.В. Рудакова [85] и зарубежных - R. Bellmann [136], D. Johnson [145], Н. Tana [103] и других.
Возможности ВС могут быть полностью использованы только при применении эффективных методов и средств организации процессов решения задач [5,18,54,55,58] и, в частности, мультипрограммных режимов [116] . Под эффективностью методов понимается не только то, что методы способны получить решение с необходимой точностью, но и то, что реализация этих методов на ВС позволяет выполнить это за достаточно короткое время.
На сегодняшний день существует несколько подходов к организации работы ВС в мультипрограммных режимах, допускающих деление на режимы обработки задач набора и обслуживания задач потока. В общем случае для большинства связанных с этим оптимизационных задач поиск оптимального решения связан с вычислительными затратами, растущими экспоненциально с ростом сложности. Поэтому исследования и разработка приближенных, а так же эвристических алгоритмов организации функционирования ВС, позволяющих получить, по крайней мере, субоптимальное решение, являются актуальными.
Результат работы большинства существующих методов зависит от случайного фактора, а их трудоемкость - от требуемой точности получаемого решения, что может привести к неоправданным дополнительным затратам на организацию функционирования ВС. Кроме того, существующие алгоритмы не позволяют организовывать работу ВС в случае поступления задач с нефиксированными параметрами (например, рангом или временем решения). Следовательно, остается актуальной задача создания алгоритмов организации функционирования ВС, независимых от случайных величин и допускающих возможность изменения параметров обрабатываемых задач.
Распределённые ВС формируются из неабсолютно надёжных компонентов, и, как следствие, в системе в случайные моменты времени и по разным причинам могут происходить отказы ресурсов. Разработка устойчивых к отказам средств управления такими системами необходима.
Учитывая все сказанное выше, перспективным является рассматриваемый в данной работе подход к организации функционирования распределённых вычислительных систем в мультипрограммных режимах.
Цели работы и задачи исследования. Разработка и ис-
следование методов, алгоритмов и программных средств организации эффективного функционирования распределённых вычислительных систем в мультипрограммных режимах.
К основным задачам исследований относятся:
- развитие существующих и разработка новых алгоритмов оптимального распределения параллельных задач набора по ресурсам ВС;
разработка децентрализованных алгоритмов оптимальной загрузки ЭМ в случае обслуживания ВС потока задач;
реализация программных компонентов поддержки режимов параллельного мультипрограммирования в ВС.
Методы исследования. Для решения поставленных задач использовались методы теории вычислительных систем, математического программирования и исследования операций. Экспериментальные исследования осуществлялись с помощью имитационного и статистического моделирования и параллельного программирования.
Научная новизна. Автором получены нижеследующие научные результаты, которые выносятся на защиту.
1. Последовательные и параллельные эвристические ал
горитмы минимизации времени решения и штрафа за задерж
ку решения задач набора на распределённых ВС, обладаю
щие лучшей по сравнению с известными средствами эффек
тивностью.
2. Алгоритмы обработки набора задач, позволяющие
распределять параллельные задачи с нефиксированными па
раметрами.
Децентрализованные алгоритмы организации подсистем в случае функционирования ВС в режиме обслуживания потоков параллельных задач, учитывающие возможные отказы ресурсов.
Программные компоненты поддержки режимов параллельного мультипрограммирования для распределенных ВС, основанные на предложенных алгоритмах.
Практическая ценность работы. Разработанные в диссертации модели, методы и алгоритмы представляют основу для эффективной организации функционирования большемас-штабных распределенных ВС в мультипрограммных режимах.
Оригинальные параллельные алгоритмы распределения задач набора по элементарным машинам ВС позволяют получать (суб)оптимальные значения целевых функций.
Применение отказоустойчивого децентрализованного алгоритма создания подсистем из ЭМ в вычислительных системах позволяет организовать обслуживание интенсивных потоков параллельных задач в условиях их конкуренции за ресурсы.
Разработан и внедрен в распределённую мультикластер-ную ВС программный комплекс для диспетчеризации параллельных задач и осуществления мониторинга технического состояния системы.
Реализация и внедрение. Основные результаты диссертационной работы получены в рамках проекта № 3.2 «Разработка методов анализа и алгоритмов организации функционирования большемасштабных распределенных вычислительных систем и создание аппаратно-программного инструментария параллельного моделирования» федеральной целевой программы № 21 фундаментальных исследований Президиума РАН. Диссертационная работа поддержана грантами Российского фонда фундаментальных исследований (РФФИ) № 02-07-90379, 02-07-09380, 05-07-08011, 05-07-90009. Полученные результаты внедрены в распределенную мультик-ластерную ВС Центра параллельных вычислительных технологий СибГУТИ и использовались при разработке и чтении
12 учебных курсов на Кафедре вычислительных систем СибГУТИ по дисциплинам «Теория функционирования распределенных вычислительных систем», «Высокопроизводительные вычислительные системы» и «Сетевое программное обеспечение».
Внедрение научных результатов диссертационной работы подтверждено соответствующими актами.
Апробация работы. Основные результаты работы докладывались на международных и всероссийских научных конференциях, в том числе:
Международной научно-технической конференции "Информационные системы и технологии" (2003 г., г. Новосибирск) ;
Всероссийской научной конференции молодых ученых «Наука. Технологии. Инновации» (2003, 2004 гг., г. Новосибирск) ;
Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы» (2003, 2005 гг., г. Геленджик);
Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (2005 г., г. Новосибирск) ;
International scientific conference «Automation, Control and Information Technology - Software Engineering» (2005 г., г. Новосибирск);
Всероссийской научной конференции «Методы и средства обработки информации» (2005 г., г. Москва).
Публикации. По теме диссертации опубликовано 12 работ, включая 3 статьи в центральных изданиях.
Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы, изложенных на 14 3 страницах, а также приложений на 7 страницах.
Содержание работы.
В первой главе описывается архитектурная и программная организация современных распределённых ВС с программируемой структурой, описываются основные режимы их работы. Произведен краткий анализ известных методов организации функционирования распределенных ВС в мультипрограммных режимах, рассмотрены наиболее распространенные средства их поддержки.
Во второй главе описаны модели функционирования распределённых ВС в режиме обработки наборов задач с постоянными и нефиксированными параметрами, предложены параллельные и последовательные алгоритмы минимизации времени решения и штрафа за задержку решения набора, проведен их анализ.
В третьей главе предложен децентрализованный алгоритм создания подсистем из ЭМ в вычислительной системе и, разработанный на его основе, алгоритм составления многопроцессорного расписания для обслуживания потоков параллельных задач. Предложены и проанализированы средства обеспечения устойчивости данных методов к отказам ресурсов ВС.
В четвертой главе описана архитектура распределенной мультикластерной ВС и реализованные на базе предложенных алгоритмов средства поддержки мультипрограммных режимов. Приведены результаты моделирования разработанных алгоритмов.
В заключении сформулированы основные результаты диссертационной работы.
В приложении приведены сравнительные характеристики разработанных алгоритмов организации функционирования распределенных ВС, изложен алгоритм параллельной сортировки.
Особенности ВС с программируемой структурой
Определение. Монопрограммным режимом называется процесс решения на ВС одной сложной задачи с использованием всех вычислительных ресурсов системы [2 9].
Сложной задачей, предназначенной для решения на системе, считается параллельная задача с количеством операций 109-1015, которая по разным причинам не может быть решена на последовательной ЭВМ. Для такой задачи разрабатывают параллельный алгоритм, который, в свою очередь, служит основой для создания параллельной программы. Качество параллельного алгоритма определяется используемой методикой распараллеливания [12,52,53,60,66, 130,131].
В целях повышения эффективности работы ВС используется методика крупноблочного распараллеливания задач [11,29,113], которая позволяет разбить задачу на крупные параллельные ветви, между которыми существует слабая взаимосвязанность, иначе говоря, общее число производимых ветвями операций значительно превосходит число операций обмена между ними.
Монопрограммный режим не позволяет использовать в полной мере возможности ВС, поскольку большое количест во решаемых параллельных задач не требует всех вычислительных ресурсов системы.
Определение. Мультипрограммным режимом называется процесс решения на ВС нескольких параллельных задач. В мультипрограммном режиме все ресурсы ВС делятся между несколькими задачами [29,77,133].
В общем случае, допускается также выполнения более одной задачи на каждой ЭМ с использованием режима разделения времени. Такая организация функционирования позволяет более полно использовать возможности системы, поскольку снижаются простои вычислительных ресурсов. Различают режимы обработки набора и обслуживания потока задач [29,113].
Для большого круга приложений, особенно связанных с моделированием управления сложными объектами, характерно заранее фиксированное число решаемых задач. В таких случаях ВС функционирует в режиме обслуживания задач набора. При этом учитывается не только их количество, но и параметры: число ветвей в программе, время решения, объем памяти, число ЭМ, необходимое для решения задачи [108]. Этот режим является обобщением режима решения сложной задачи на ВС.
Если задачи поступают в систему в случайные моменты времени и их параметры случайны, то считается, что ВС функционирует в режиме обслуживания потока задач [2 9,39]. В этом случае необходимо определить процедуру обслуживания поступающих задач и выделения подсистем из ЭМ для их решения.
Использование потенциальных возможностей ВС существенно зависит от того, как организовано функционирование системы, в частности, от того, как осуществляется выделение ресурсов и как происходит решение поступающих параллельных задач.
В режиме обработки задач набора необходимо выбрать алгоритм распределения задач по ЭМ вычислительной системы и последовательность их решения так, чтобы обеспечить эффективное функционирование ВС в смысле одного из критериев. В качестве таких критериев, можно взять минимум времени решения или штрафа за задержку решения задач набора.
В работе [29] предложена математическая модель организации решения задач набора на ВС. Данная модель позволяет получить распределение задач по ЭМ системы для небольших наборов, используя один из методов математического программирования. Однако указанная модель не позволяет учесть решение параллельных задач на системе, а также не допускает возможность изменения одного или нескольких параметров решаемых задач.
Проблема организации функционирования ВС при распределении задач набора является NP-полной [19], что является достаточным основанием для отказа от поиска нетрудоемкого точного алгоритма для ее решения. Интерес представляют эвристические и приближенные методы, по
зволяющие получить субоптимальное распределение задач по ЭМ.
В работах [29,71,94] предложены эвристические и стохастические алгоритмы, решающие данную проблему. Их недостатком является существенная зависимость трудоемкости метода от входных параметров, влияющих на точность получаемого решения, что существенно сказывается на накладных расходах на организацию функционирования ВС. Вследствие этого, закономерным является предположение о не лучшей эффективности стохастических методов распределения задач набора, основанных на генетических, эволюционных алгоритмах, методах муравьиной колонии и прочих эвристик, использующих вероятностный фактор [8 9] . Данные методы могут быть успешно применены в случае однократного решения задачи организации функционирования [71,95], однако их регулярное использование при обработке достаточно больших наборов задач может привести к неоправданным накладным расходам. Кроме того, известные методы не позволяют учитывать возможность изменения параметров поступающих задач.
Точный алгоритм распределения задач набора по элементарным машинам ВС
Минимизация времени решения задач набора показана в следующем примере. Имеется вычислительная система из 5 ЭМ и набор из 8 задач с рангами 6(2,1,2,2,1,2,2,3} и временами решения /,.6(10,15,20,10,7,2,5,3}, / = 1,...,8. В качестве вектора решения, удовлетворяющего ограничениям (1) - (4) и обеспечивающего минимум Т{т) можно рассмотреть вектор т= (0,0,0,10,15,20,20,22,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5). Оптимальным временем решения набора будет Т(т ) = 25.
Введем в приведенную выше модель дополнительные переменные rt, i = \,L - ранг распределяемых задач. Тогда модель распределения набора задач с переменными параметрами будет выглядеть следующим образом [88].
Необходимо найти вектор T = (t і г г J1 У f Jr f Jr ) минимизирующий T(r) = max(f, + tir)) -» min при ограничениях: (5) V/ j, i,j = \,L верно, по крайней мере, одно из следующих двух условий: a) [i„ii + t,W)n[ij,ij + ///))) = 0 ; 6) \fkx=\4,k2=uj, {Jb,jb 0)= (jb jb); (6) vi=\,Lykx k2kvk2 = W (J!],J!2 O)= (J! J!2); (7) Wi = \,L, 22sign(jf) = r,; k=\ (8) V/ = U, r- rt rf, rieZ+; (9) V/ = 1,L, = U,+, J JU{0}; (10) V/ = UI, /, 0, /(eR .
В данной модели ограничения (5) запрещают одновременное решение двух и более задач на одной ЭМ, (б) -обеспечивают реализацию разных ветвей каждой задачи на разных ЭМ, (7) и (8) обеспечивают решение задачи на необходимом количестве ЭМ, (9) и (10) - задают область значений переменных. Модель задачи минимизации штрафа за задержку решения может быть получена заменой целевой функции на F(r) = ї,с,.- min (=1 Минимизация времени решения набора задач с нефиксированными параметрами показана в следующем примере. Пусть имеется вычислительная система из 5 ЭМ и набор из 3 задач с рангами г Є {1,2,3}, +Є {3,4,3} и временем решения /,(/ ){—,—,—}, / = 1,2,3. В качестве вектора решения, удов-к к г. летворяющего ограничениям (5) - (10) и обеспечивающего минимум Т(т) можно рассмотреть вектор т = (0,0,4,3,2,3,1,2,3,4,5,1,2,3). Оптимальным значением времени решения набора будет
Точный алгоритм распределения задач набора по элементарным машинам ВС В ряде случаев можно найти распределение набора задач с постоянными параметрами, обеспечивающее точное значение времени решения набора Т . Пусть указанная задача интерпретируется как задача размещения набора прямоугольников в заданном прямоугольнике П. Каждая параллельная задача /. є /, i-\,L, представляется прямоугольником с высотой /. - время решения задачи, шириной rt -ранг задачи, i=\,L. Пусть Q представляет собой прямоугольник с шириной п (общее число элементарных машин ВС), и высотой
(очевидно, что Д - верхняя оценка времени решения набора) . Расположение каждого прямоугольника і в О определяется координатами ( , -) его левого нижнего угла. В процессе поиска решения Q разбивается на прямоугольники, часть которых содержит уже назначенные на ЭМ задачи (далее будем называть такие
Очевидно, что распределение задач набора, соответствующее разбиению Q на прямоугольники удовлетворяет условиям (1) - (4) п. 2.1.
Гипотеза. Для любого оптимального распределения набора задач по ЭМ существует соответствующее ему разбиение Q на прямоугольники.
Следовательно, если выдвинутая гипотеза верна и оптимальное распределение набора задач может быть представлено в виде такого разбиения, его поиск может быть осуществлен предложенным далее алгоритмом [92] . В противном случае алгоритмом, будет получено субоптимальное решение.
Алгоритм (далее для краткости будем обозначать его Т_ЕХТ) основан на методе ветвей и границ и является по сути одним из вариантов направленного перебора множества всех допустимых решений. В процессе поиска решения нефиксированные прямоугольники могут быть объединены или разбиты с образованием новых. При назначении каждой задачи на ЭМ определяется вмещающий ее прямоугольник. Будем считать, что прямоугольник вмещает задачу, если его ширина не меньше ранга, а высота - времени решения задачи.
Обозначим [r,t,r,t] - прямоугольник ширины г, высоты t, с координатами левого нижнего угла [rj] . Введем на множестве прямоугольников отношения порядка: [ , , ] [r2J2,r2,t2] если либо tx t2, либо ї1=72лг1 г2. Примем также следующие обозначения: D - частичное решение (множество пар назначенных на ЭМ задач и соответствующих фиксированных прямоугольников) ; D - дополнение задач из D до множества всех задач /; т, А - нижняя и верхняя оценки времени решения набора соответственно; В - множество упорядоченных по возрастанию прямоугольников, В в объединении с фиксированными прямоугольниками, содержащими задачи из D образует разбиение Q.; (D,B,m,&) - узел дерева поиска оптимального решения; Е = {(Д,5,,ш,, A,),.. .,{Ds,Bs,ms,As)} - множество всех узлов дерева поиска; 5= - число узлов дерева поиска; mmin - минимальная нижняя оценка времени решения Т ; Amin - минимальная верхняя оценка времени решения Т ; КОНЕЦ - конец работы алгоритма.
Алгоритм Т_ЕХТ строит дерево поиска оптимального решения, оперируя на каждом шаге с множеством узлов Е . Поиск решения (ветвление) осуществляется с узлами, содержащими частичные решения (D.&0), на которых достигается минимум значений верхней и нижней оценок времени решения. На каждой итерации происходит дополнение частичного решения в выбранном узле очередной назначаемой на ЭМ задачей. Если в Е больше нет узлов для ветвления, алгоритм заканчивает работу.
Децентрализованный алгоритм организации подсистем в ВС
Рассматривается ВС, на каждую из элементарных машин которой поступает поток параллельных задач. Каждая задача характеризуется рангом (требуемьм числом ЭМ) и временем решения. Любая ЭМ содержит расписание для исполнения распределенных на неё задач (или параллельных ветвей). Время загрузки ЭМ - это максимум времени завершения выполнения всех распределенных на нее задач. Под временем загрузки ВС понимается максимум времени загрузки по всем ЭМ. Требуется распределить поступающие задачи по ВС (т.е. выделить для каждой из них подсистему из ЭМ) так, чтобы время загрузки ВС было минимально.
Особенностями функционирования ВС при обслуживании параллельных задач потока являются случайность параметров задач, моментов их поступления на ВС, необходимость учитывать структуру сети связи, а также возможные отказы ресурсов при формировании подсистем.
Предложим алгоритм создания подсистемы из ЭМ [93] по параллельную задачу. Пусть всем машинам ВС присвоены уникальные номера J., j=\,п (п - число машин в ВС). Каждая ЭМ J. содержит очередь Q поступающих на неё задач j = ],п. Две ЭМ будем называть соседними, если они непосредственно соединены друг с другом каналом связи. Рангом подсистемы будем называть число включенных в нее машин. В процессе работы предложенного алгоритма под очередную задачу ранга г организуется подсистема того же ранга путем, по возможности, равномерного распределения требуемого числа параллельных ветвей задачи среди соседних ЭМ. В свою очередь, каждая соседняя ЭМ распределяет назначенные на нее ветви на еще не включенные в подсистему соседние с ней машины. Другими словами, алгоритм строит дерево, в котором корнем является ЭМ Jj, инициирующая создание подсистемы, а ЭМ каждого следующего уровня являются соседями одной или нескольких ЭМ с предыдущего. Листьями дерева являются ЭМ, на которые распределена одна параллельная ветвь.
Работа алгоритма (далее для краткости будем называть его алгоритм S_DEC) основана на событиях, обмене сообщениями между ЭМ и их состояниях. Каждая машина может находиться в одном из 3-х состояний. I (Idle) - ЭМ не участвует в создании подсистемы. Р (Primary) - ЭМ создает подсистему для поступившей на неё задачи. S (Secondary) - ЭМ создает подсистему по запросу от другой машины.
Имеются б видов сообщений: «приветствие» (далее будем обозначать его «л») оповещает о появлении новой ЭМ в вычислительной системе . «информация» («і») - применяется для оповещения соседних ЭМ об изменениях в текущей машине; «запрос» («д») - запрос создания подсистемы определенного размера; «ответ» («г») - информирует о размере подсистемы, которая может быть создана; «подтверждение» («f») - информирует о предоставлении запрошенной ранее подсистемы; «отмена» («с») - используется для разрушения созданной подсистемы. На рис. 3.1 приведен пример подсистемы из 4 машин, созданной алгоритмом S_DEC. Число рядом с каждой ЭМ указывает параллельную ветвь, распределенную на данную машину. В скобках указано состояние ЭМ. событие2 - приход сообщения «д»; событиеЗ - приход сообщения «г»; событие4 - приход сообщения «f»; событиеБ - приход сообщения «с»; событиеб - приход сообщения «і»; событие7 - приход сообщения «h».
Текущей ЭМ будем называть машину, на которой произошло одно из указанных событий. Для каждого события предусмотрен алгоритм обработки, результатом которого является изменение состояния текущей ЭМ или рассылка сообщений соседним машинам.
Примем также следующие обозначения: к - номер ЭМ, инициирующей создание подсистемы; s - номер текущей ЭМ; Ms - множество, состоящее из ЭМ Js и множества её соседей; STATE" - состояние ЭМ Js ; Ms = ijj\, Т" = \т\ - множество соседей ЭМ Js и их загрузка соответственно; Msn - множество, состоящее из ЭМ J и тех её сосе дей, которым направлены запросы на распределение параллельных ветвей; Rsq=Yj\, Tj - количество ветвей, запрошенных машиной J у машины /,.; Uq = Uj\ - определяет множество соседних с ЭМ Js машин, создавших подсистему максимально возможного размера (таких соседей будем называть предельными); /. - флаг предельности, lj = 1, если г. максимально для ЭМ J., иначе lj = 0; M lczM - подмножество соседних с Js ЭМ, приславших сообщение «г» («ответ»); к - номер ЭМ, от которой машиной Js был получен запрос на создание подсистемы; N ,r,t - обрабатываемая задача [N - номер, г число параллельных ветвей, t - время решения). Сообщения имеют следующий вид: [TYPE; N; г; /; t; Ts; Т; Ц, /2,...,/,}] , где TYPE - тип сообщения (один из б вышеперечисленных); N - номер задачи, для которой создается подсистема; г - требуемый ранг подсистемы; / - флаг предельности указанного количества ЭМ; t - время решения задачи, для которой создается подсистема; Ts - загрузка ЭМ Js ; Т - максимально возможная загрузка включаемой в подсистему машины (равна загрузке ЭМ, инициирующей создание подсистемы); {/,, i2,..., ir) - номера включенных в подсистему машин; КОНЕЦ - окончание работы алгоритма обработки события .
Моделирование алгоритмов распределения параллельных задач набора с постоянными параметрами
Моделирование предложенных в п.2.1-2.3 алгоритмов состояло из четырех частей. В первой проводилось моделирование работы точного алгоритма минимизации времени решения набора задач Т_ЕХТ. Во второй сравнивались алгоритмы Т_МС и Т_РАСК по времени работы и по получаемому общему времени решения набора задач на ВС. В третьей части эксперимента проводилось сравнение алгоритмов минимизации общего штрафа за задержку решения Р_МС и Р_РАСК. Целью четвертой части эксперимента было определение коэффициентов ускорения параллельных алгоритмов распределения набора задач Т_РРАСК и Р_РРАСК.
Рассматривались тестовые наборы задач со случайным рангом, временем и штрафом за задержку решения, равномерно распределенных в интервалах соответственно rt є(0,10], f. є(0,100], с,е(0,10], / = 1,L. Число задач L в наборе изменялось в пределах от 1-Ю5 до 2 106. В качестве показателя эффективности рассматривалось время работы алгоритмов на ВС и получаемое ими время реализации набора задач. Требуемое время решения пакета задач 0 = 4 00, общее число ЭМ л = 10. В алгоритмах Т_МС и Р_МС d = к = 8. Для вычисления коэффициента ускорения параллельных алгоритмов число ЭМ л изменялось в пределах от 2 до 16. Результат рассчитывался как среднее значение исследуемого показателя среди 10 различных наборов задач. Результаты моделирования приведены в табл. 4.2 и на рис. 4.2-4.9.
1. Экспериментально проверена способность алгоритма Т_ЕХТ находить точное решение задачи минимизации общего времени решения набора параллельных задач (см. табл. 4.1). Применение данного алгоритма имеет существенные ограничения в силу его экспоненциальной трудоемкости.
2. Как видно из рис. 4.2, предложенный алгоритм Т_РАСК распределяет набор задач эффективнее алгоритма Т_МС на 20-30%. Рис. 4.3 показывает, что время работы алгоритма Т_РАСК меньше времени работы алгоритмы Т_МС в 1,5-7,5 раз в зависимости от числа задач в наборе, при чем на больших наборах Т_РАСК работает существенно бы стрее, чем Т_МС.
3. Рис. 4.4, 4.5 показывают преимущество предложенного алгоритма Р_РАСК перед Р_МС, составляющее, в ряде случаев, 6-кратное улучшения штрафа за задержку решения набора задач и в 1,2-1,35 раза меньшее время работы.
4. В заключительной части моделирования проводилось исследования параллельных алгоритмов Т_РРАСК и Р_РАСК. Рис. 4.6 и 4.8 показывают, что оба параллельных алгоритма работают быстрее соответствующих последовательных реализаций лишь на достаточно больших пакетах задач. При увеличении числа используемых ЭМ время работы параллельных алгоритмов сокращается незначительно из-за существенного роста времени, затрачиваемого на обмен информацией между параллельными ветвями (рис. 4.7 и 4.9) .
Использовались наборы задач со следующими параметрами: L = 1000, л = 8, 16, 32, 64, 128, 256, гГ,Г? и Si случайно распределены в интервалах [1,а п), [1,(оп) и [1,10) соответственно. Параметр со регулировал верхнюю границу ранга задач и принимал значения 0.25, 0.5, 0.75 и 1. Наборы задач были сгенерированы с помощью равномерного и пуассоновского распределений. Число наборов задач было равно 1000.
Результаты моделирования на наборах задач, имеющих равномерно распределенные ранги (см. рис. 4.10), показывают, что алгоритм TD_PACK наиболее эффективен для наборов, в которых ранг задач изменяется в более широком диапазоне (см. значения для 75% и 100% максимума ранга). Отметим, что в этом случае получаемое алгоритмом хуже нижней оценки оптимального решения в среднем на 15%, и существенно не меняется с ростом числа машин ВС. В случае небольшого интервала изменения ранга (значения для 25%) с ростом числа ЭМ точность алгоритма заметно падает, т. е. для распределения параллельных задач с мало изменяющимся числом ветвей алгоритм менее эффективен.
Результаты моделирования для задач с незначительно меняющимися параметрами (при пуассоновском распределении верхней и нижней границ ранга) приведены на рис. 4.11. Как видно из диаграммы, алгоритм TD_PACK более эффективен для распределения задач с небольшим рангом (25% и менее от числа ЭМ) , либо рангом близким к числу машин в ВС (значение 100%) .
Рассмотрим результаты моделирования алгоритма PD_PACK. Использовались наборы задач со следующими параметрами: L = 1000, л = 8, r J і ti и СІ равномерно распределены в интервалах [1,8), [1,8) [1,100) и [1,10) соответственно. В качестве оценки работы алгоритма рассматривалась величина в-bL. F где F и F - штраф за задержку решения задач набора, распределенных соответственно алгоритмом и случайным назначением.
Результаты моделирования на наборах задач, имеющих равномерно распределенные ранги (см. рис. 4.12), показывают, что с увеличением верхней границы ранга эффективность алгоритма PD_PACK ухудшается, например, для ВС из 16 машин она падает с 1,75 до 1,14. Тем не менее, даже в худшем случае алгоритм дает решение в два раза лучше полученного случайным распределением задач набора.