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 <= tMax, где curStartTime - допустимое стартовое время для рассматриваемой подзадачи на k процессоров, а curTime - время ее исполнения на некотором рассматриваемом количестве процессоров k.

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

· Если хороших расположений нет, то выбираем то (предпочтение более раннему стартовому времени, а среди расположений с равным стартовым временем - расположению с меньшим количеством используемых процессоров), которое минимизирует выражение 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##_ имеют следующий прототип:

int mproc_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 ) ON TSA( 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) ON TSA(renum(IB) )

DO 50 IB = 1,NBL

CALL JACOBI(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 Duo 2.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. Jahed Djomehri, Rupak Biswas, Noe Lopez-Benitez. Load balancing strategies for multi-block overset grid applications [PDF] (http://www.nas.nasa.gov/News/Techreports/2003/PDF/nas-03-007.pdf)

3. Oliver Sinnen. Task Scheduling for Parallel Systems // John Wiley And Sons, Inc. 2007.

4. Nir Menakerman, Raphael Rom. Bin Packing with Item Fragmentation // Algortihms and Data Structures. Springer Berlin / Heidelberg, 2001. Volume 2125/2001. P. 313-324

5. Andrei Radulescu, Arjan J.C. van Gemund. A Low-Cost Approach towards Mixed Task and Data Parallel Scheduling // ICPP. 2001. P. 69-76

6. Buyya, Rajkumar. High Performance Cluster Computing : Architectures and Systems, Volume 1 // Prentice Hall. 1999.

7. GCC, the GNU Compiler Collection [PDF] (http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc.pdf)

Страницы: 1, 2, 3