Диссертация (1091135), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Задача быларешена за 26 дней на четырех разных кластерах НИВЦ МГУ. Использовалисьтолькотеинтервалывремени,когдаВУкластеровнебылизаняты101пользователями. Весь расчет проведен на фоне штатной работы только за счетиспользования периодов незанятости узлов. Эффективность работы созданнойвычислительной среды составила 98%. Решение этой же задачи в обычномрежиме заняло бы четыре года работы одного компьютера [1].3.2.1. Обоснование критериев эффективностиУмножениематрицоднаизоперацийчастоприменяемаяприисследованиях в области распараллеливания программ для РСОД. Различныеалгоритмы распараллеливания данной операции рассматриваются во многихисточниках, например в работах [50], [62] описаны алгоритмы, основанные наразделении матриц на строки и столбцы, после такого разбиения, выполняемогона центральном узле, полосы данных рассылаются между остальными узлами длявыполнения вычислений.В работах [50], [61], [62] описаны, так называемые блочные методыпараллельного умножения матриц, суть которых сводится к тому, что исходные ирезультирующая матрицы представляются в виде множества прямоугольныхблоков имеющих размерность m x m.

В таком случае, операцию умноженияматриц A и B на основе блочного метода можно представить следующимобразом: A11A k1A12...Ak 2A1k   B11 Akk   Bk1B12...Bk 2B1k   C11 C12 ...Bkk   Ck1 Ck 2Ck  ,Ckk где каждый блок Сij матрицы C определяется с помощью выражения = ∑ =1.(3.2.1.1)102Данный метод подробно рассмотрен в работе [40]. При описанном вышеспособе организации вычислений произведения матриц пересылка данныхполучается распределенной по времени, и это позволяет совместить процессыобработки данных и передачи.

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

однородныхРСОД, в которых узлы имеют одинаковую производительность. В задачицентрального узла входит только распределение частей матрицы по узлам.Но при решении крупномасштабных задач встает вопрос – какорганизовать вычислительную сеть в рамках одного предприятия, включающуюоднотипные узлы и коммуникации с одинаковой пропускной способностью. Вданном случае более рациональным выглядит применение т.н. гетерогенныхРСОД [63].Одним из решений данной проблемы может стать применение такого типаРСОД, как вычислительные среды, рассмотренного в первой главе [1]. Такиесистемы имеют сходство с кластерами, т.к.

обладают параллельной архитектуройи распределенной памятью. Различие заключается в том, что помимо общейрешаемой задачи в системе, на каждом узле пользователи производят своивычисления, что снижает наждёность узлов и повышает динамичностьконфигурации вычислительной среды.103Такие РСОД очень привлекательны с точки зрения экономическойдоступности, т.к. не требуют глобальных затрат и постепенно обновляютсяповышая технические характеристики [1].Как видно из предыдущего примера блочные методы имеют хорошуюсовместимость с однородными РСОД, в которых все ВУ обладают одинаковойпроизводительностью, и нет смысла затрачивать время на планирование.В гетерогенных РСОД и распределённых вычислительных средах такойподход может оказаться неэффективным из-за больших простоев узлов.

В такихРСОД целесообразно будет использовать алгоритмы распараллеливания, в основекоторых присутствует диспетчеризация и, которые позволяют подогнатьструктуру ПО под конфигурацию вычислительной сети либо некоторое еёсостояние [4], [58].Рисунок 3.2.1. Распределение блоков матрицы без учета производительности узловв однородной РСОДРисунок 3.2.2.

Распределение блоков матрицы с учетом производительности узловв гетерогенной РСОД104На рисунках 3.2.1 и 3.2.2 показаны возможные варианты распределенияматричных блоков в системах с учетом и без учета производительности узлов.Существует различные алгоритмы нахождения оптимальных расписаний.В данной работе проводится исследование методов основанных на эволюционномподходе, а именно ГА [53], [39], [47].В данной работе предложен модифицированный ГА, в котором фитнесфункция назначает неточные оценки расписаниям, за счёт чего повышаетсяскорость вычислений. Недостаток разработанного метода заключается в большойсклонностиГА,использующегомодифицированнуюфитнес-функциюкпреждевременной сходимости, для снижения эффекта ранней конвергенциипредлагается попеременное включение классического и модифицированногоалгоритмов (смешанный ГА).При использовании алгоритмов распараллеливания на основе построениярасписаний с учётом производительности узлов исходная задача умноженияматриц разбивается на атомарные процедуры (комплекс ИЗЗ), которые получаютна вход блоки данных.Предполагается, что во время выполнения умножения матриц в системеодин узел параллельно выполняет поиск расписания для следующей операцииумножения матриц и далее выполняет генерацию кода и рассылку частейпрограммы по узлам [1], [50].Представив операцию умножения матриц в виде комплекса ИЗЗ можнозаметить, что данная задача оптимально согласуется с концепцией ОМ,предлагаемой в работе [4].

Вся задача разбивается на атомарные процедурыумножения и сложения элементов матрицы, т.е. происходит построение графаканонической формы ИЗЗ.На следующем шаге стартует генетический алгоритм, на выходе которогогенерируетсярасписание,т.о.атомарныеоперационные модули и распределяются по сети.процедурыобъединяютсяв1053.2.2. Подготовка исходных данных и проведение экспериментаЦель эксперимента, описанного в данной работе, заключалась в сравненииэффективности классического ГА, модифицированного ГА, смешанного ГА иалгоритма на основе обыкновенного блочного метода в РСОД с однородной игетерогенной конфигурацией на примере параллельного выполнения операцииумножения матриц.Разработанныйпрограммныйкомплекс«Анализаторгенетическихалгоритмов», представляет модель вычислительной сети и позволяет задаватьразличные конфигурации сети и производить сравнение эффективности ГА иблочных методов.В процессе проведения эксперимента в программу вводились исходныеданные с различными конфигурациями сети и комплекса ИЗЗ, представляющегооперацию умножения двух квадратных матриц размерностью 10000x10000 с 64-хразрядными вещественными числами.

За атомарную операцию принималасьоперация умножения строки и столбца размерностью 10 элементов.В первой части эксперимента, результаты которой представлены в таблице3.2.2.2 проводилось сравнение вышеописанных алгоритмов в однородной РСОД схарактеристиками, представленными в таблице 3.2.2.1. РСОД представляетвычислительнуюсетьсполносвязнойтопологией,однотипнымивычислительными узлами и коммуникациями.Таблица 3.2.2.1.

Характеристики однородной РСОДХарктеристики узловIntel Core i5-2500K (Sandy Bridge), частоты 3,3-3,7 ГГцТопологияполносвязнаяПропускнаяспособность 10G Ethernet, 10 Гбит/скоммуникацийПрограммное обеспечениеОСРВ QNX 6.5.0106Таблица 3.2.2.2.

Результаты эксперимента для однородной РСОДНазвание методаВремя поискарасписанияКлассический ГАМодифицированный ГАСмешанный ГАБлочный метод100 мкс100 мкс100 мкс0Классический ГАМодифицированный ГАСмешанный ГАБлочный метод50 мкс50 мкс50 мкс0Среднее время выполнения операцииРазмерность системы100 узлов 1000 узлов 2500 узлов1,4 мc70 мкc59 мкс1,1 мс68 мкс61 мкс0,94 мс64 мкс58 мкс0,78 мс59 мкс46 мкс1,6 мc1,2 мс1,1 мс0,78 мс90 мкc69 мкс67 мкс59 мкс68 мкс63мкс61 мкс46 мксИз таблицы 3.2.2.1 видно, что алгоритм на основе блочного метода воднородной РСОД явно преобладает над алгоритмами, синтезирующимирасписания.Во второй части эксперимента производилось сравнение в гетерогеннойРСОД (таблица 3.2.2.4), с характеристиками, приведёнными в таблице 3.2.2.3.РСОД представляет вычислительную сеть с полносвязной топологией, свычислительными узлами двух типов и с коммуникациями, которые могутхарактеризуются двумя значениями пропускной способности.Таблица 3.2.2.3.

Характеристики

Список файлов диссертации