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

Получение параллельного варианта для метода чет-нечетной перестановки уже не представляет каких-либо затруднений – сравнения пар значений на итерациях сортировки являются независимыми и могут быть выполнены параллельно. В случае 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 элемента). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессов, для которых параллельно выполняются операции "сравнить и разделить". Взаимодействующие пары процессов выделены в таблице рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

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

Таблица 9.1. Пример сортировки данных параллельным методом чет-нечетной перестановки№ и тип итерациПроцессоры1234

Исходные данные	13 55 59 88	29 43 71 85	2 18 40 75	4 14 22 43
1 нечет (1, 2), (3, 4)	13 55 59 88	29 43 71 85	2 18 40 75	4 14 22 43
	13 29 43 55	59 71 85 88	2 4 14 18	22 40 43 75
2 чет (2, 3)	13 29 43 55	59 71 85 88	2 4 14 18	22 40 43 75
	13 29 43 55	2 4 14 18	59 71 85 88	22 40 43 75
3 нечет (1, 2), (3, 4)	13 29 43 55	2 4 14 18	59 71 85 88	22 40 43 75
	2 4 13 14	18 29 43 55	22 40 43 59	71 75 85 88
4 чет (2, 3)	2 4 13 14	18 29 43 55	22 40 43 59	71 75 85 88
	2 4 13 14	18 22 29 40	43 43 55 59	71 75 85 88

Содержание раздела

---

---