Теория и практика параллельных вычислений

         

Программная реализация


Представим возможный вариант параллельной программы обобщенной быстрой сортировки. При этом реализация отдельных модулей не приводится, если их отсутствие не оказывает влияния на понимание общей схемы параллельных вычислений.

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)



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий