Дипломная работа: Распараллеливание многоблочных задач для SMP-кластера
Повторяем шаг 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. Помечаем все, как нераспределенные