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