Дипломная работа: Распараллеливание многоблочных задач для SMP-кластера

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.

Класс «Данные Подзадачи» предназначен для хранения основных характеристик исходной подзадачи, таких как минимальное допустимое количество процессоров, максимальное допустимое количество процессоров, базовый способ вычисления времени на основе использования формулы Амдала, параметризованной значениями времени исполнения последовательной части и времени исполнения параллельной части на одном процессоре. Основным методом в интерфейсе является получение времени исполнения подзадачи в зависимости от количества процессоров, на которых планируется ее запустить.

Класс «Подзадача» предназначен для описания подзадачи с уже назначенным конкретным числом процессоров.