Аннотация
Оптимизация распределенияданных и вычислений между процессорами является важным шагом прираспараллеливании многоблочных задач. В первом разделе описаны параллельныесистемы и актуальность многоблочного метода. Во втором и третьем разделе определеныцели и задачи данной работы. В четвертом и пятом разделе приводится обзорсуществующих алгоритмов и предлагается эффективный метод отображения подзадач,допускающих распараллеливание. В шестом разделе описана практическаяреализация. Полученный результат в будущем может быть усовершенствован путёмввода в рассмотрение неоднородных вычислительных систем, а также учёта затратна коммуникации.
Оглавление
1 Введение
1.1 Параллельная ЭВМ и распределенныесистемы
1.2 Многоблочный метод решениясложных задач
1.3 Программирование параллельных ЭВМ
2 Цель работы
3 Постановка задачи
4 Обзор существующих решений
4.1 Алгоритм сокращения критическогопути (CPR)
4.2 Упаковка в контейнеры
4.3 Алгоритмы EVAH
5 Исследование и построение решениязадачи
5.1 Первоначальные предложения поотображению
5.2 Эволюция предложений поотображению
6 Описание практической части
6.1 Обоснование выбранногоинструментария
6.2 Общая архитектура разработанногосредства
6.3 Схема работы средства
6.4 Характеристики функционирования
7 Заключение
8 Список цитируемой литературы
1 Введение
В истории развитии микропроцессорови больших интегральных схем известен закон Мура. В 1965 году в процессеподготовки выступления, Гордон Мур сделал такое наблюдение: новые моделимикросхем разрабатывались спустя более-менее одинаковые периоды — 18-24 месяца— после появления их предшественников, а емкость их при этом возрастала каждыйраз примерно вдвое. Но даже при такой скорости развития мощность отдельныхвычислительных машин не может удовлетворять современные потребностифизиков-математиков. Появились суперкомпьютеры и кластеры, разработаныпараллельные алгоритмы, распределенные методы и системы. Для работы на такихсистемах нужно распараллеливать программы, а также в таких распределенныхсистемах важную роль играет балансировка вычислений.
/>1.1 ПараллельнаяЭВМ и распределенные системы
В настоящее время идетразвитие параллельной высокопроизводительной вычислительной техники последующим направлениям:
· Векторно-конвейерныекомпьютеры. Конвейерные функциональные устройства и набор векторных команд — это две особенности таких машин. В отличие от традиционного подхода, векторныекоманды оперируют целыми массивами независимых данных, что позволяет эффективнозагружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двухмассивов, а не двух чисел. Характерным представителем данного направленияявляется семейство векторно-конвейерных компьютеров CRAY куда входят, например, CRAY EL, CRAY J90, CRAY T90, новые CRAYX1/X1E.
· Параллельныекомпьютеры с общей памятью. Вся оперативная память таких компьютеровразделяется несколькими одинаковыми процессорами. Это снимает проблемыпредыдущего класса, связанные с необходимостью явного выделения векторныхопераций в программе, а также позволяет распределить неоднородную работу(например, пока один процессор складывает, одновременно с ним другой можетумножать), но добавляет новые — число процессоров, имеющих доступ к общейпамяти, по чисто техническим причинам нельзя сделать большим. В данноенаправление входят многие современные многопроцессорные SMP-компьютеры или, например, отдельныеузлы компьютеров HP Exemplar, HP Superdome и Sun StarFire.
· Массивно-параллельныекомпьютеры с распределенной памятью. Идея построения компьютеров этого классатривиальна: возьмем серийные микропроцессоры, снабдим каждый своей локальнойпамятью, соединим посредством некоторой коммуникационной среды — вот и все.Достоинств у такой архитектуры масса: если нужна высокая производительность, томожно добавить еще процессоров, если ограничены финансы или заранее известнатребуемая вычислительная мощность, то легко подобрать оптимальную конфигурациюи т.п.
Однако есть и решающий«минус», сводящий многие «плюсы» на нет. Дело в том, чтомежпроцессорное взаимодействие в компьютерах этого класса идет намногомедленнее, чем происходит локальная обработка данных самими процессорами.Именно поэтому написать эффективную программу для таких компьютеров оченьсложно, а для некоторых алгоритмов иногда просто невозможно. К данному классуможно отнести компьютеры Intel Paragon, IBM SP1, Parsytec, в какой-то степени IBM SP2 и CRAY T3D/T3E/X1/XMT, хотя в этих компьютерах влияниеуказанного минуса значительно ослаблено. К этому же классу можно отнести и сетикомпьютеров, которые все чаще рассматривают как дешевую альтернативу крайнедорогим суперкомпьютерам.
· Кластеры.Вычислительный кластер – это мультикомпьютер, состоящий из множества отдельныхкомпьютеров (узлов), связанных между собой единой коммуникационной системой.Каждый узел имеет свою локальную оперативную память. При этом общей физическойоперативной памяти для узлов не существует. Если в качестве узлов используютсямультипроцессоры (мультипроцессорные компьютеры с общей памятью), что внастоящее время является повсеместно практикуемым, то такой кластер называетсяSMP-кластером. Коммуникационная система обычно позволяет узламвзаимодействовать между собой только посредством передачи сообщений, нонекоторые системы могут обеспечивать и односторонние коммуникации — позволятьлюбому узлу выполнять массовый обмен информацией между своей памятью и локальнойпамятью любого другого узла. Если все входящие в состав вычислительногокластера узлы имеют одну и ту же архитектуру и производительность, то мы имеемдело с однородным вычислительным кластером. Иначе – с неоднородным.
Кластерное направление,строго говоря, не является самостоятельным, а скорее представляет собойкомбинации предыдущих трех. Но именно это направление является наиболееперспективным в настоящее время.
/>1.2 Многоблочныйметод решения сложных задач
Известно, что при решениисложных физико-математических задач, например в задачах вычислительнойгидроаэродинамики со сложной геометрией (газовая динамика, обтекание самолета,внутреннее течение в реакторах, и т.д.) построение единой целой сетки длярасчетной области является трудным процессом, а одинаковая подробность приведетк излишним затратам ресурсов – нужны сетки разные – для одних областей болеегрубые, для других – более точные. Для решения данной проблемы можно применитьподход многоблочного метода:
· Физическая областьможет быть разбита на несколько зон или блоков. Границы блоков могут несоответствовать границам физической области.
· Для каждого блокаотдельно строится сетка в соответствии с граничными условиями.
/>/>
Рисунок 1. Примеры сетокв многоблочном методе
При счете многоблочнойзадачи подзадачи для блоков считаются практически независимо, обмениваясьтолько границами с соседними блоками после каждого временного шага. При большомколичестве блоков сбалансированное их распределение по вычислителям может датьзаметный выигрыш во времени исполнения всей задачи по сравнению с другимираспределениями. Также возможно построение более эффективного распределения прииспользовании параллелизма внутри подзадач.
1.3 Программированиепараллельных ЭВМ
Чтобы считать задачу напараллельном вычислителе, она должна быть распараллелена. Распараллеливатьможет:
· пользователь — сразу написав параллельную программу. Разработка параллельной программы спомощью специализированного набора средств программирования предполагает либоиспользование специального языка программирования параллельного компьютера,либо традиционного языка программирования последовательных машин, расширенногонабором спецификаций параллельной обработки данных, либо традиционного языка ибиблиотеки, реализующей конкретную модель параллельного выполнения.
Для научно-инженерныхрасчетов применяются следующие модели программирования:
· Модель передачисообщений
Каждый процесс обладаетсобственным локальным адресным пространством. Для синхронизации и обработкиобщих данных используется передача сообщений. Стандартом интерфейса передачисообщений является MPI.
· Модель с общейпамятью
Все процессы разделяютединое адресное пространство. Доступ к общим данным регулируется с помощьюпримитивов синхронизации. Стандартом для моделей с общей памятью стал OpenMP.
· Модельпараллелизма по данным
В этой модели данныеразделяются между узлами вычислительной системы, а последовательная программаих обработки преобразуется компилятором в программу либо в модели передачисообщений, либо в модели с общей памятью. При этом вычисления распределяются поправилу собственных вычислений: каждый процессор выполняет вычисления данных,распределенных на него. Примером реализации этой модели является стандарты HPF1 и HPF2. На модели параллелизма по данным была такжеразработана отечественная система DVM.
· пользовательвместе со специальной программой-распараллеливателем в автоматизированномрежиме — указывая свойства последовательной программы
· автоматическийраспараллеливатель – он извлекает параллелизм самостоятельно изпоследовательной программы и распараллеливает ее в автоматическом режиме безучастия пользователя
В каждом варианте естьсвои недостатки. В первых двух пользователю приходится активно участвовать впроцессе распараллеливания (а в первом и вовсе написать новую – параллельнуюпрограмму), а в третьем зачастую получаются неэффективные результаты.
Подавляющее большинствопрограмм для систем с распределенной памятью в настоящее время разрабатываютсяв модели передачи сообщений (MPI). Языки, поддерживающие модель параллелизма поданным (HPF, Fortran-DVM, C-DVM), значительно упрощают разработку программ, ноих использование очень ограничено. Кардинальные изменения архитектуры ЭВМ(многоядерность, использование в качестве ускорителей графических процессоров)требуют появления новых языков высокого уровня, обеспечивающих более высокийуровень автоматизации программирования, в том числе и при создании многоблочныхпрограмм.
Всем используемым намногопроцессорных ЭВМ с распределенной памятью языкам программирования (включаяи DVM-языки) присущ один серьезный недостаток – ручное отображение подзадач напроцессоры. Для большого количества подзадач и большого количества процессоровсделать вручную эффективное отображение очень затруднительно.
2 Цельработы
Целью даннойработы являются следующие шаги по развитию средств поддержки многоблочныхпрограмм в DVM-системе:
· обеспечитьавтоматическое (а не только ручное) отображения подзадач на процессоры
· обеспечить балансировкузагрузки процессоров за счет эффективного отображения подзадач с учетомвозможности их параллельного выполнения.
3 Постановказадачи
Данамногоблочная программа на языке Fortran-DVM, использующая механизм подзадач DVM.
Требуетсяразработать и реализовать эффективный алгоритм автоматического отображенияподзадач на процессоры; изменить способкодирования операций отображения и запуска подзадач, чтобы обеспечитьиспользование алгоритма автоматического отображения; сравнить характеристикивыполнения исходной программы с ручным отображением и программы савтоматическим отображением.
4 Обзорсуществующих решений
4.1 Алгоритмсокращения критического пути (CPR)
CPR предложен разными авторами изголландского политехнического университета Delft и французского института INRIA. Сначала алгоритм был разработан для планировщиказадач в многопроцессорных системах, где граф задач можно моделировать в видеориентированного ациклического графа. Существуют и другие подходы для решениятакого рода задач (TwoL, CPA, TSAS) [5], но CPR показывает самый приемлемыйрезультат.
CPR можно применить для распределениямногоблочных задач (при условии возможности построения ориентированногоациклического графа).
/>
Рисунок 2.Иллюстрация ориентированного ациклического графа блоков
Определение
Критическийпуть (T): самый длинный путь в графе (отвхода до выхода).
Верхнийкритический путь блока t (Tv): самый длинный путь от входа до t
Нижнийкритический путь блока t (Tn): самый длинный путь от t до выхода
P — количество процессоров в системе.
N(t) — Количество процессоров, выделенных для блока t.
Описаниеалгоритма
Шаг 1. Длякаждого блока ti выделен один процессор N(ti) = 1. Построить расписание.
Шаг 2. Пусть X – множество всех блоков, для которыхвыделено меньше P процессоров.
Шаг 3. Пустьблок t – блок, у которого сумма Tv + Tn максимальная.
Выделить для t дополнительный процессор, N(t) = N(t) + 1. Построить новое текущеерасписание.
Если послевыделения, новый критический путь T’
Шаг 4.Повторяем шаг 3 пока X непусто
Сутьалгоритма состоит в выделении максимально возможного количества процессоров длякаждого блока с целью сокращения критического пути (т.е. сокращение общеговремени выполнения всех блоков). Данный алгоритм исходит из наличия алгоритмапостроения расписания.
Алгоритм эффективный,учитывает зависимости между блоками, но не рассматривает проблему назначениягрупп процессоров для конкретных блоков и составления расписания ихпрохождения.
/>4.2 Упаковка в контейнеры
Bin-packin это множество алгоритмов для решения задачи: объектыразличных объемов должны быть упакованы в конечное число контейнеров так, чтобыминимизировать количество используемых контейнеров. В нашем случае упаковка вконтейнеры используется для равномерного распределения задач по всем процессорам.
Упаковка в контейнеры безразбиения объектов
Имеем список объектов L=(a1, a2, …, an) и их размеры s(ai) Є {1, 2, …, U}. Размер контейнеров V больше U, количество контейнеров m. Отсортируем список объектов по размеру в убывающем порядке.Первые m объектов упаковывать соответственнобудем в m контейнеров. С остальными объектамидействуем по принципу: упаковывать в контейнер, у которого занимаемого местаменьше всего.
Упаковка в контейнеры сразбиением объектов
Существует два возможныхварианта упаковки в контейнеры с разбиением объектов [4]: с сохранением и сувеличением объема данных. Будем рассматривать вариант с увеличением объемаданных, так как после разбиения часто появляются дополнительные коммуникациимежду фрагментами.
Имеем список объектов L=(a1, a2, …, an) и их размеры s(ai) Є {1, 2, …, U}, U – размер контейнеров.
Введем некоторые понятия:
· Эффективностьалгоритма A: RA(L) = A(L)/OPT(L),где A(L) – нужное количество контейнеров когда применяем алгоритм A на список объектов L, OPT(L) – оптимальноеколичество контейнеров для данного списка объектов.
· R называется асимптотическойэффективностью в худшем случае, если
R = inf{r>=1:для некоторых N>0, RA(L)=N}
· Алгоритм Аназывается алгоритмом без лишнего разбиения если:
a) Разбивает объект только тогда,когда его размер больше размера контейнера
б) Разбивает объект надва фрагмента так, чтобы первый фрагмент вместится полностью в одном изконтейнеров
в) Открывает новыйконтейнер только тогда, когда в уже открытых контейнерах нельзя упаковать новыйфрагмент.
Известно, что для всехалгоритмов упаковки в контейнеры без лишнего разбиения:
R 2
Теперь рассмотрималгоритмы NF, NFD, NFI, FFD-I
· NF — Next-Fit
На каждом шаге открываемтолько один контейнер, упаковываем объекты по очереди, если размер объектабольше размера свободной части контейнера – разобьем на две части так, чтобыпервая часть заполнила контейнер. После этого открываем новый контейнер ивторую часть туда упаковываем. Это очень простой алгоритм и имеет плохуюэффективность
RNF=U/(U-2), U>=6
· NFD, NFI (Next-Fit с ранее отсортированным спискомобъектов по размеру в убывающем/возрастающем порядке)
RNFD >= U/(U-2) если U=2n, n>=3
RNFD >= (U+1)/(U-1)если U=2n+1, n>=2
Но это только нижняяоценка, мы вполне сможем подобрать пример, когда NFD и NFIработают тоже плохо, как и NF.
· FFD-I и FFI-I (Iterative First-FitDecreasing/Increasing with Item fragmentation)
Попробуем упаковать всеобъекты списка L в фиксированноеколичество m контейнеров. Сортируем списокобъектов по размеру в невозрастающем порядке. Каждый объект будем упаковывать впервый подходящий контейнер, если такого нет, разобьем объект на две части.Первая часть должна заполнить первый свободный контейнер, а вторую часть положимв отсортированный список объектов. Если не удалось упаковать все объекты в m контейнеров, увеличиваем m и повторяем.
Пусть s(L) – сумма всех объектов в списке L.
1) Взять m=[s(L)/U]
2) FFD()
3) Если успешно,останавливаем
4) Иначе m=m+1 и goto2)
Для алгоритма FFD-I:
RFFD-I
U/(U-1) =16
Получаем, что FFD-I лучше NFD/NFI и NF.
Алгоритм упаковки вконтейнеры без разбиения показывает хорошие результаты, но не учитываетпараллелизм внутри блоков (исходит из последовательной постановки). Так как алгоритмупаковки в контейнеры с разбиением исходит из идеального распараллеливания намультикомпьютере – без обменов, то, в условиях необходимости синхронизации впроцессе счета подзадачи, он не даёт ответа на вопрос составления итоговогорасписания, расположения объектов внутри контейнера, а также не учитываетнеобходимость разбиения объекта на равные части.
/>
/>4.3 АлгоритмыEVAH
В2001-ом году на международной конференции по параллельной обработке,организованной IEEE (ИнститутомИнженеров по Электротехнике и Радиоэлектронике) Джомери и Рупак Бизваспредложили ряд новых алгоритмов для решения задачи балансировки в приложенияхгидрогазодинамики [2]. Эти алгоритмы описаныв статье “Task Assignment Heuristics for Distributed CFDApplications”. Этойстатьи нет в свободном доступе, но идею алгоритма можно взять в другой статьеэтих же самых авторов.
Врамках этой работы будем использовать один алгоритм из этой серии, которыйназывается Largest Task First with Minimum Finish Time and Available Communication Costs” (LTF_MFT_ACC, в первую очередь большие задачи с наименьшимвременем выполнения и известными затратами на коммуникации). Позже EVAH был интегрирован другимиразработчиками в реальных приложениях типа OVERFLOW-D (моделирование подвижных объектов в аэродинамике) и показалвесьма неплохой результат.
Ядро алгоритма можноописать следующим образом:
Пусть:
zi – задача i
Xi – время выполнения zi
R(zi) – совокупность всех задач, откоторых zi получает данных
D(zi) – совокупность всех задач, которыеполучают данные от задачи zi
C – время коммуникации
T(pi) – суммарное время выполнения задачна процессоре pi
1: Отсортируемсписок задач по весу (времени выполнения) в убывающем порядке
2: Вначале время выполнения задач на каждом процессоре = 0 (процессоры свободные)
3: Длякаждой отсортированной задачи ziвыполнять:
3.1: Распределитьзадачу на процессор pj, укоторого загрузка T(pj) наименьшая. Пересчитать T(pj) = T(pj)+ Xi
3.2: Длякаждой задачи zr в R(zi),назначенной на процессор pk != pj выполнить
T(pj) = T(pj) + Cir
Еслизадача zr (которая уже распределена на другойпроцессор) получает данные от задачи zi то надо добавить в T(pj) время коммуникации между zi и zr */
3.3: Длякаждой задачи zd в D(zi),назначенной на процессор pm != pj выполнить
T(pm) = T(pm) + Cdi
Еслизадача zi получает данные от zd (которая уже распределена напроцессор pm) то надо добавить в T(pm) время коммуникации */
4: Конеццикла
Для иллюстрации работыалгоритма рассмотрим следующий пример (рисунок 3).
Имеем четыре пересекающиесясетки (блоки) zi (i=0..3). Надо распределить блоки по двум процессорам p0и p1 так, чтобы минимизировать времявыполнения.
/>
Рисунок 3. Иллюстрацияработы алгоритма EVAH
Шаг1. Четыре блока отсортированы в убывающем порядке по времени выполнения (Xi), получаем: z3, z2,z0, z1
Шаг 2. В начале суммарноевремя выполнения на процессорах равно 0, T(p0) = T(p1) = 0
Шаг3. Самый большой блок z3 назначен на процессор p0.Получаем T (po) = 75 вшаге 3.1. Так как никакие другие блоки не были еще назначены на процессоры,пропустим шаги 3.2 и 3.3 для z3.
Повторяем шаг 3 длязадачи z2. По предложенному алгоритму z2 должна быть назначена на процессор, где нагрузка наименьшая ипоэтому z2 назначена на процессор p1. Получаем T(p1) = 60 в шаге 3.1. На шаге 3.2 очевидно, что z3 получает от z2 данные ипоэтому T(p1) = 60 + 4 = 64. На шаге 3.3 наоборот, z2 получает данные от z3 и поэтому T(p0) = 75 + 4 = 79.
Аналогично повторяем шаг3 для распределения задач z0и z1.
В результатераспределения T(p0)=123, T(p1)=122. Значит, время параллельного выполнения будет123 а время последовательного 225 (сумма всех Xiбез затрат времени на коммуникации)
Заметим, что алгоритм EVAH имеет большое преимущество передтрадиционными алгоритмами на неориентированных графах именно в силу возможнойобработки ориентированного графа. Для многоблочных задач объем коммуникациимежду соседними блоками не всегда симметричный.
Алгоритм EVAH учитывает время на коммуникации, ноне пытается распределить блоки на несколько процессоров, используя параллелизмвнутри блока.
5 Исследованиеи построение решения задачи
5.1 Первоначальныепредложения по отображению
Попытаемсясвести нашу задачу отображения многоблочных задач на процессоры к задачеупаковки в контейнеры с дроблением грузов первого типа – дроблением сувеличением груза (накладными расходами).
Первыйвариант:
Квантуемвремя на достаточно малые равные промежутки dt. Будем считать, что каждыйконтейнер имеет вместимость N (количество процессоров в вычислительнойсистеме), а количество заполненных контейнеров обозначает время счетасовокупности подзадач (если заполнено T контейнеров, то совокупное время счетараспределенных на вычислительную систему подзадач будет T*dt). Будем считать,что каждый груз уже раздроблен на части весом Kmax (максимальное возможноеколичество процессоров для счета подзадачи, для каждого груза этот показательсвой). При дроблении количество частей в зависимости от веса каждой части будемполучать по формуле [Time(K)/dt]+1, где Time(K) –время счета подзадачи на Kпроцессорах.
Остается лишьввести следующие ограничения:
1. При дроблениигруза веса частей всегда равны между собой
2. В контейнере неможет быть более одной части одного груза
3. После появлениячасти i-го груза в контейнере если i-ый груз не полностью выложен вконтейнеры, то в следующем контейнере обязана появится часть i-го груза.
Этот вариантплох тем, что имеет отрицательную динамику роста общего веса груза при егодроблении – то есть полное время выполнения (равное времени выполнения,умноженному на количество задействованных процессоров) подзадачи уменьшается сувеличением количества частей, на которые разбивается соответствующий ей груз.Считаю, что данная отрицательная динамика не позволяет полностью свести нашузадачу к задаче упаковки в контейнеры с дроблением первого типа, а также делаетизвестные методики упаковки неприменимыми.
Второйвариант:
Считаем, чтокаждый контейнер обозначает процессор. Груз – подзадачу. Будем считать, чтокаждый груз уже раздроблен на Kmin (минимальное возможное количествопроцессоров для подзадачи) частей (для каждого груза этот показатель свой). Придроблении вес частей в зависимости от количества будем получать по формулеTime(K), где K – количество частей, на которые раздроблен груз, а Time(K) – время выполнения подзадачи с использованием K процессоров. Далее для полученияответа будем варьировать вместимости контейнеров в поиске минимальной возможнойвместимости для размещения всех грузов в данных N контейнерах.
Здесь такжевводятся дополнительные ограничения:
1. При дроблениивеса частей всегда равные
2. В контейнере неможет быть более одной части одного груза
3. А такжеограничение, которое заметно сложнее выполнить:
После полнойупаковки учитывая ограничения 1 и 2, должна существовать расстановка частейгрузов в каждом контейнере (возможно, с добавлением в контейнеры фиктивных грузовдля занятия места) такая, что все части одного груза имели бы равные начальныевремена (начальное время для части груза в контейнере с упорядоченными частямигрузов есть суммарный вес всех частей грузов с номерами меньшими данного). Приэтом возможно переполнение контейнеров и данное распределение считается неудовлетворяющимограничению 3.
Второйвариант кажется предпочтительнее своей естественностью, однако поддержаниеограничения 3 создает сильное препятствие для работы алгоритма отображения.
5.2 Эволюцияпредложений по отображению
Рассмотримсначала второй вариант из подраздела 5.1
Вышеизложенный принцип на данный момент не был использован для отображения с учетомпараллелизма, однако был использован для отображения без учета параллелизмавнутри подзадач. Был реализован и отлажен алгоритм, основанный на данномпринципе и названный «Жадное Отображение», принято решение использовать жаднуюстратегию заполнения контейнеров – такую, при которой следующий груз-кандидатпопадает в самый незаполненный контейнер.
Описаниеалгоритма:
1. Сортируем задачипо сложности в невозрастающем порядке
2. Помечаем все, какнераспределенные
3. Находим самуюсложную нераспределенную задачу t
4. Находим самыйнезанятый процессор (с самым ранним финишным временем) p
5. Ставим задачу t на процессор p и помечаем ее, как распределенную
6. Если естьнераспределенные задачи, то переходим к пункту 3
Алгоритмическаясложность реализованного алгоритма есть O(N*logN + N*M), где N – количество подзадач, а M – количество процессоров.
По этомуалгоритму были получены приемлемые отображения модельных и реальныхмногоблочных задач.
Главнаяпроблема данного подхода в том, что его сложно применить в условияхразрешенного параллелизма внутри подзадачи, поэтому данный подход не былразвит.
Теперьрассмотрим первый вариант из подраздела 5.1
Данный ранееизложенный принцип был использован для построения эффективного алгоритмаотображения многоблочной задачи с учетом параллелизма ее независимых подзадачна процессоры – алгоритма под названием «Транспонированное Отображение». Былаиспользована «непрерывная» модель при стремлении dt к нулю. Таким образом, уженет контейнеров, а есть некая неограниченная полоса, поделенная на M(количество процессоров) полос вдоль. Был реализован и отлажен алгоритм,основанный на данной модели, принято решение использовать жадно-переборнуюстратегию.
Опишемосновные принципы работы алгоритма и свойства отображения, поддерживаемые им впроцессе работы.
Сначалавведем несколько определений:
· Интегральноевремя подзадачи на заданном количестве процессоров есть Time(K) * K, где Time(K) – время счета подзадачи на количестве процессоров K.
· Минимальноеинтегральное время подзадачи есть Time(Kmin) * Kmin (здесь работаетпредположение невозрастающей эффективности распараллеливания)
Первыйосновной принцип – отображение подзадач в порядке невозрастания их минимальногоинтегрального времени – жадная стратегия. Смысл этого принципа в том, чтобысначала отобразить наиболее крупные подзадачи, а затем «заткнуть» свободныеместа задачами поменьше.
Второйосновной принцип – для каждой подзадачи перебор ее возможных расположений –переборная стратегия. Была выбрана именно переборная стратегия, ибо чистожадная стратегия давала слишком неэффективные отображения. Этот принциппозволяет более полно рассмотреть варианты отображения каждой конкретной подзадачи.
Третийосновной принцип – отсечение перебора:
· Если текущеепромежуточное отображение позволяет отобразить рассматриваемую в данный моментподзадачу на k процессоров, дав ей стартовое время x, то алгоритм не будетисследовать возможность ее отображения на k процессоров с более позднимстартовым временем y, большим x.
· Пусть tMax –максимальное по всем процессорам время освобождения процессора (по сути –промежуточный вариант итогового времени). Вариант расположения следующейрассматриваемой подзадачи назовём хорошим, если для него curStartTime + curTime
· Если дляподзадачи есть хорошее расположение, то выбираем в качестве результата хорошеерасположение с минимальным стартовым временем, а среди хороших расположений сминимальным стартовым временем – хорошее расположение с минимальным количествомиспользуемых процессоров.
· Если хорошихрасположений нет, то выбираем то (предпочтение более раннему стартовомувремени, а среди расположений с равным стартовым временем – расположению сменьшим количеством используемых процессоров), которое минимизирует выражениеmax((curStartTime + curTime) * M, tOccupied + curTime * k + tRestMin), гдеtOccupied – уже занятое отображенными подзадачами интегральное время, k –допустимое количество процессоров для рассматриваемой подзадачи, tRestMin –сумма минимальных интегральных времен еще не отображенных подзадач (не включаярассматриваемую в данный момент подзадачу)
Также стоитотметить, что данный алгоритм транспонированного отображения при запретепараллелизма подзадач переходит в описанный выше алгоритм жадного отображения,основанный на втором варианте модели.
6 Описаниепрактической части
Практическаяреализация служит для предоставления программистам Fortran-DVM и C-DVM возможности эффективно исполнять многоблочные задачи.Представляет собой статическую библиотеку, предоставляющую вызовы для генерацииотображения, а также исполняемый файл для генерации отображения в диалоговомрежиме.
6.1 Обоснование выбранного инструментария
Дляреализации был выбран стандартный Си++ с использованием компилятора GCC [7], ибо важна была кроссплатформенность,так как библиотека встраивается в систему поддержки времени исполнения LibDVM, и должна работать в том числе подуправлением ОС семейства GNU/Linux.
6.2 Общаяархитектура разработанного средства
Разработанноепрограммное средство представляет собой набор из исходных текстов на языкеСи++, shell-скрипт для сборки библиотеки иисполняемого файла, примеры входных файлов с описаниями блоков для работы вдиалоговом режиме. Общий объём исходных текстов составляет 1086 строк, из них1034 – Си++ код, а 52 – shell-скрипт.Архитектура программного средства такова, что допускает простое добавлениедругого алгоритма отображения и предоставляет удобные интерфейсы для построенияотображения, а также механизм самопроверки корректности построенного отображения.Оно позволяет гибко менять характеристики каждой подзадачи, такие какминимально-допустимое количество процессоров, необходимое для запускаподзадачи, равно как и максимально-допустимое количество процессоров, накотором подзадача может выполняться, а также время (в условных единицах),необходимое для завершения подзадачи.
Ниже, нарисунке 4 приведена диаграмма классов, иллюстрирующая архитектуру приложения,где «Жадное Отображение» и «Транспонированное Отображение» суть не классы, аотдельные функции, реализующие описанные в предыдущем разделе алгоритмыотображения. Также «DVM Адаптер» сутьне класс, а отдельная функция для генерации представления, используемого всистеме поддержки времени исполнения LibDVM.
Класс «ДанныеПодзадачи» предназначен для хранения основных характеристик исходной подзадачи,таких как минимальное допустимое количество процессоров, максимальноедопустимое количество процессоров, базовый способ вычисления времени на основеиспользования формулы Амдала, параметризованной значениями времени исполненияпоследовательной части и времени исполнения параллельной части на одномпроцессоре. Основным методом в интерфейсе является получение времени исполненияподзадачи в зависимости от количества процессоров, на которых планируется еезапустить.
Класс«Подзадача» предназначен для описания подзадачи с уже назначенным конкретнымчислом процессоров.
Класс «КвантЗагрузки Процессора» предназначен для описания интервала времени на одном изпроцессоров, занимаемых конкретной подзадачей.
Класс «ЗагрузкаПроцессора» предназначен для хранения структуры загрузки одного процессора, вкакие времена и на какие длительности какие подзадачи планируется запустить. Такжеон занимается проверкой корректности построенного отображения в рамках одногопроцессора.
Класс«Отображение Подзадачи» предназначен для сбора информации о том, на какиепроцессоры какая задача отображена, ее стартовое время, ее финишное время.Также он занимается проверкой корректности построенного отображения в рамкаходной подзадачи – ее стартовые, равно как и финишные, времена на всехпроцессорах, на которых планируется ее счет, должны совпадать.
Класс«Отображение» предназначен для сбора информации обо всём отображении в целом,вывода результатов, получения агрегированных данных об отображении.
Придобавлении нового алгоритма необходимо знание небольшого интерфейса классов«Отображение», «Данные Подзадачи», «Подзадача».
/>
Рисунок 4.Диаграмма классов разработанного средства
6.3 Схемаработы средства
Разработанноепрограммное средство предлагается использовать C-DVM и Fortran-DVM программистам вместо ручного отображения [1]. Следуетвместо вызова функции ручного отображения сделать следующее:
· Завести массивтипа int размером на, как минимум, количествоблоков (назовем его renum)
· Узнать количествопроцессоров в системе (например, вызовом NP = NUMBER_OF_PROCESSORS( ) )
· В зависимости отразмерности блоков вставить вызов mproc_adv1_ для одномерных блоков, mproc_adv2_ для двумерных и так далее. Функции вида mproc_adv##n##_ имеют следующий прототип:
intmproc_adv##n##_ (int *low_proc, int *high_proc, int *size, int *num_blocks, int*num_proc, int *renum);
Где в первыйаргумент – массив целых чисел – будет вписан нижний индекс номеров используемыхдля подзадачи процессоров; во второй соответственно верхний индекс номеровиспользуемых для подзадачи процессоров; третий аргумент должен содержатьразмеры блоков по каждому измерению (например, для двумерных блоков размер i-го блока есть size[2 * i] по первому измерению и size[2 * i + 1]по второму); четвертый аргумент суть указатель на число блоков; пятый –указатель на число процессоров; шестой – массив, куда следует записать порядокпрохождения подзадач для последующей его передачи системе LibDVM.
· В директивах DVM следует включить полученнуюперенумерацию. (например, для Fortran-DVM программы, фрагмент кода:
·
*DVM$TASK_REGION TSA
*DVM$ PARALLEL ( IB ) ONTSA( IB )
DO 50 IB = 1,NBL
CALL JACOBI(block(IB)%PA,
block(IB)%PB,SIZE(1,IB),SIZE(2,IB))
50 CONTINUE
*DVM$ END TASK_REGION
преобразовать так:
*DVM$ TASK_REGION TSA
*DVM$ PARALLEL (IB) ONTSA(renum(IB) )
DO 50 IB = 1,NBL
CALLJACOBI(block(renum(IB))%PA, block(renum(IB))%PB,SIZE(1, renum(IB)), SIZE(2,renum(IB)))
50 CONTINUE
*DVM$END TASK_REGION)
После этихмодификаций программа будет использовать функционал разработанного программногосредства. Схематично процесс представлен на рисунке 5.
/>
Рисунок 5.Схема работы разработанного программного средства
Схема нарисунке 5 отражает работу с разработанной библиотекой. Кроме этого такжевозможна работа в диалоговом режиме с разработанной исполняемой программой длягенерации отображений. Для работы с ней, необходимо запустить исполняемый файли следовать инструкциям, появляющимся на экране. Есть возможность сгенерироватьслучайным образом блоки, их характеристики; задать вручную; прочитать из файла.Формат файла, описывающего блоки таков: первая строка содержит количествопроцессоров, за ней построчно идут описания блоков, для каждого блока отдельнаястрока вида «порядковый номер время последовательной части время параллельной частиминимальное количество процессоров максимальное количество процессоров».Программа построит отображение, проверит его корректность, выведет временныехарактеристики работы алгоритма отображения, временные характеристикиполученного отображения; а также, в случае небольшого размера входных данных,выведет на экран в виде текстовой диаграммы картину загрузки процессоров. Нарисунке 6 изображен пример сессии работы с разработанным программным средствомв диалоговом режиме.
/>
Рисунок 6.Пример сессии работы с разработанным программным средством в диалоговом режиме
6.4 Характеристикифункционирования
Пусть имеетсяn подзадач и m процессоров, тогда алгоритмическая сложность разработанногопрограммного средства при использовании алгоритма «ТранспонированноеОтображение» асимптотически не превосходит C * (n * log(n) + n * m). Затраты по памяти асимптотическине больше C * (n + m),где C равен 2 килобайтам плюс-минус 30процентов. Время работы на тесте из 10000 блоков, 2048 процессоров напроцессоре Intel Core 2 Duo2.33 ГГц составило 100 секунд. При реализации были использованы быстрыеструктуры данных такие, как красно-черные деревья с помощью стандартнойбиблиотеки шаблонов языка Си++, а само представление данных было оптимизированопод алгоритм.
Алгоритм былпротестирован на данных о блоках реальной задачи из 810 подзадач помоделированию аэродинамики самолета при отображении на 29, 57, 128, 256, 384процессоров.
Оценки временивыполнения каждой подзадачи брались по закону Амдала с долей последовательнойчасти равной 0,1. Запусков счета этой задачи с различными отображения непроизводилось, все расчеты времени в условных единицах и являютсятеоретическими на основании знаний о размерах блоков.
Получаемыеотображения сравнивались с результатами работы алгоритма отображения без учетапараллелизма подзадач («Жадное Отображение»), а также с одним из вариантовиспользуемого в DVM отображения, работающему поалгоритму:
Пусть есть M процессоров
Пусть size(i) – размер i-гоблока
1. Посчитатьсуммарный размер блоков, пусть он равен S
2. Положить счетчикпроцессоров curProc равным единице. Положить счетчикпромежуточного суммарного размера блоков curSum равным нулю.
3. Для каждого блокаi выполнять:
Отобразить задачуi на процессор curProc.
curSum= curSum + size(i)
Если curSum >= curProc * S/ M то curProc = curProc + 1
4. Конец цикла
/>
/>
Рисунок 7.Сравнение результатов отображения различных алгоритмов на различном количествепроцессоров
Как видно издиаграмм на рисунке 7, на больших количествах процессоров (начиная с 57),алгоритм с использованием параллелизма внутри подзадачи дает лучшие результаты.
Такжезаметно, что на 128, 256, 384 процессорах у алгоритмов, не учитывающихпараллелизм подзадач, итоговое время исполнения совпадают это происходит из-заналичия нескольких подзадач сложности 11648, что заметно больше остальныхсложностей. Получается, что эти наиболее сложные подзадачи тормозят выполнениедругих менее сложных подзадач. А в случае с 384 процессорами почти в три раза.
Также былипроведены реальные тесты на кластере СКИФ-МГУ на другой многоблочной задаче –модельной задаче с 10 блоками. Были произведены запуски одной и той же задачи сиспользованием алгоритмов «Транспонированное Отображение» и ручного отображения,работающего по следующему алгоритму:
1. Если количествоблоков меньше количества процессоров, то каждый блок отобразить на всеимеющиеся процессоры
2. Есликоличество блоков не меньше количества процессоров, то, если n блоков и m процессоров, i-ыйблок отобразить на процессоры [1 + (i-1)*(m/n)… i * (m/n)]
Для каждогоалгоритма были произведены пуски с использованием 1, 4, 9, 10, 16, 56процессоров. В качестве результата бралось общее время работы всей задачи всекундах – в ней внутри каждого блока считался Якоби, 100 итераций. На рисунке8 наглядно продемонстрированы полученные времена работы.
/>
Рисунок 8. Сравнение результатов отображенияразличных алгоритмов на различном количестве процессоров
7 Заключение
В рамках этой работырассмотрены разные алгоритмы для отображения многоблочных задач. Предложенэффективный алгоритм отображения подзадач, использующий возможностьраспараллеливания подзадач. Он реализован в составе статической библиотеки,подключаемой во время компиляции совместно с системой поддержки времениисполнения LibDVM, а также в виде интерактивногоприложения для генерации отображений.
В дальнейшем стоит задачаавтоматического определения границ блоков (сейчас блоки определяются ручным образом)для сетки сложной структуры, а также задача усовершенствования предлагаемогоалгоритма отображения вводом в рассмотрение неоднородных вычислительных систем,а также учётом затрат на коммуникации.
8 Списокцитируемой литературы
1. Н.А. Коновалов, В.А. Крюков, А.А. Погребцов,Н.В. Поддерюгина, Ю.Л. Сазанов. Параллельное программирование в системе DVM.Языки Fortran DVM и C-DVM. Труды Международной конференции «Параллельныевычисления и задачи управления» (PACO’2001) Москва, 2-4 октября 2001 г.,140-154 с.
2. M. JahedDjomehri, Rupak Biswas, Noe Lopez-Benitez. Load balancing strategies formulti-block overset grid applications [PDF] (http://www.nas.nasa.gov/News/Techreports/2003/PDF/nas-03-007.pdf)
3. Oliver Sinnen. TaskScheduling for Parallel Systems // John Wiley And Sons, Inc. 2007.
4. Nir Menakerman, RaphaelRom. Bin Packing with Item Fragmentation // Algortihms and Data Structures.Springer Berlin / Heidelberg, 2001. Volume 2125/2001. P. 313-324
5. Andrei Radulescu, ArjanJ.C. van Gemund. A Low-Cost Approach towards Mixed Task and Data ParallelScheduling // ICPP. 2001. P. 69-76
6. Buyya, Rajkumar. HighPerformance Cluster Computing: Architectures and Systems, Volume 1 // PrenticeHall. 1999.
7. GCC, the GNU CompilerCollection [PDF] (http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc.pdf)