Теория и практика параллельных вычислений
Принципы распараллеливания
При внимательном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно заметить, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановке этих значений, если их порядок не соответствует условиям сортировки.
Пример 9.1. Операция "сравнить и переставить"
// Базовая операция "сравнить и переставить" if ( A[i] > A[j] ) { temp = A[i]; A[i] = A[j]; A[j] = temp; }
Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения, собственно, и проявляется различие алгоритмов сортировки.
Для параллельного обобщения выделенной базовой операции сортировки рассмотрим первоначально ситуацию, когда количество процессоров совпадает с числом сортируемых значений (т. е. p=n) и на каждом из процессоров содержится только по одному значению исходного набора данных. Тогда сравнение значений ai и aj, располагаемых соответственно на процессорах Pi и Pj, можно организовать следующим образом (параллельное обобщение базовой операции сортировки):
- выполнить взаимообмен имеющихся на процессорах Pi и Pj
значений (с сохранением на этих процессорах исходных элементов);
- сравнить на каждом процессоре Pi и Pj получившиеся одинаковые пары значений (ai, aj); результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т. е. Pj) запоминает для дальнейшей обработки большее значение пары
Представим возможный вариант параллельной программы обобщенной быстрой сортировки. При этом реализация отдельных модулей не приводится, если их отсутствие не оказывает влияния на понимание общей схемы параллельных вычислений.
1. Главная функция программы. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы.
// Программа 9.1. // Обобщенная быстрая сортировка int ProcRank; // Ранг текущего процесса int ProcNum; // Количество процессов int main(int argc, char *argv[]) { double *pProcData; // Блок данных процесса int ProcDataSize; // Размер блока данных
MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);
// Инициализация данных и их распределение между процессами ProcessInitialization(&pProcData, &ProcDataSize);
// Параллельная сортировка ParallelHyperQuickSort(pProcData, ProcDataSize);
// Завершение вычислений процесса ProcessTermination(pProcData, ProcDataSize);
MPI_Finalize(); }
Функция ProcessInitialization определяет исходные данные решаемой задачи (размер сортируемого массива), выделяет память для хранения данных, осуществляет генерацию сортируемого массива (например, при помощи датчика случайных чисел) и распределяет его между процессами.
Функция ProcessTermination осуществляет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных.
Реализация всех перечисленных функций может быть выполнена по аналогии с ранее рассмотренными примерами и предоставляется читателю в качестве самостоятельного упражнения.
2. Функция ParallelHyperQuickSort. Функция производит параллельную быструю сортировку согласно рассмотренному алгоритму.
Пример 9.1.
(html, txt)
Функция LocalDataSort выполняет сортировку блока данных на каждом процессоре, используя последовательный алгоритм быстрой сортировки.
Функция PivotDistribution определяет ведущий элемент и рассылает его значение всем процессорам.
Функция GetProcDataDivisionPos выполняет разделение блока данных относительно ведущего элемента. Ее результатом является целое число, обозначающее позицию элемента на границе двух блоков.
Функция DataMerge осуществляет слияние частей в один упорядоченный блок данных.
3. Функция PivotDistribution. Функция выбирает ведущий элемент и рассылает его все процессорам гиперкуба. Так как данные на процессорах отсортированы с самого начала, ведущий элемент выбирается как средний элемент блока данных.
Пример 9.2.
(html, txt)
