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



             

Определение подзадач и выделение информационных зависимостей


Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнения пар значений на итерациях сортировки являются независимыми и могут быть выполнены параллельно. В случае p<n, когда количество процессоров меньше числа упорядочиваемых значений, процессоры содержат блоки данных размера n/p и в качестве базовой подзадачи может быть использована операция "сравнить и разделить" (см. подраздел 9.2).

Алгоритм 9.3. Параллельный алгоритм чет-нечетной перестановки

// Алгоритм 9.3 // Параллельный алгоритм чет-нечетной перестановки ParallelOddEvenSort(double A[], int n) { int id = GetProcId(); // номер процесса int np = GetProcNum(); // количество процессов for (int i = 0; i < np; i++ ) { if (i % 2 == 1) { // нечетная итерация if (id % 2 == 1) { // нечетный номер процесса // Cравнение-обмен с процессом — соседом справа if (id < np - 1) compare_split_min(id + 1); } else // Cравнение-обмен с процессом — соседом слева if (id > 0) compare_split_max(id - 1); } else { // четная итерация if(id % 2 == 0) { // четный номер процесса // Cравнение-обмен с процессом — соседом справа if (id < np - 1) compare_split_min(id + 1); } else // Cравнение-обмен с процессом — соседом слева compare_split_max(id - 1); } } }

Для пояснения такого параллельного способа сортировки в табл. 9.1 приведен пример упорядочения данных при n=16, p=4 (т.е. блок значений на каждом процессоре содержит n/p=4 элемента). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессов, для которых параллельно выполняются операции "сравнить и разделить". Взаимодействующие пары процессов выделены в таблице рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

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


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