Н., Пескова Е. Е., Шаманаев П. А. Основы параллельного программирования с использованием технологий mpi и openmp учебное пособие саранск издательство свмо 2013 2

41 
Сопоставив схему разделения данных и порядок выполнения 
вычислений в методе Гаусса, можно отметить, что использование 
циклического способа формирования полос позволяет обеспечить лучшую 
балансировку вычислительной нагрузки между подзадачами. 
Распределение подзадач между процессорами должно учитывать 
характер выполняемых в методе Гаусса коммуникационных операций. 
Основным видом информационного взаимодействия подзадач является 
операция передачи данных от одного процессора всем процессорам 
вычислительной системы. Как результат, для эффективной реализации 
требуемых 
информационных 
взаимодействий 
между 
базовыми 
подзадачами топология сети передачи данных должны иметь структуру 
гиперкуба или полного графа [8,9]. 
2.7.5 Алгоритм параллельной пузырьковой сортировки 
 
Последовательный алгоритм пузырьковой сортировки сравнивает и 
обменивает соседние элементы в последовательности, которую нужно 
отсортировать. Для последовательности 
)
,...,
2
,
1
(
n
a
a
a
алгоритм сначала выполняет 
1

n
базовых операций "сравнения-обмена" 
для последовательных пар элементов 
)
,
1
(
)...,
3
,
2
(
),
2
,
1
(
n
a
n
a
a
a
a
a

В результате после первой итерации алгоритма самый большой 
элемент перемещается ("всплывает") в конец последовательности. Далее 
последний элемент в преобразованной последовательности может быть 
исключен из рассмотрения, и описанная выше процедура применяется к 
оставшейся части последовательности 
)
'
1
,...,
'
2
,
'
1
(

n
a
a
a
Как можно увидеть, последовательность будет отсортирована после 
1

n
итерации. 
// Последовательный алгоритм пузырьковой сортировки 
void BubbleSort(double A[], int n) { 
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i; j++) 
compare_exchange(A[j], A[j + 1]); 
} 
 
Алгоритм пузырьковой сортировки в прямом виде достаточно 
сложен 
для 
распараллеливания 
– 
сравнение 
пар 
значений 

42 
упорядочиваемого набора данных происходит строго последовательно. В 
связи с этим для параллельного применения используется не сам этот 
алгоритм, а его модификация, известная в литературе как метод чет-
нечетной перестановки. Суть модификации состоит в том, что в алгоритм 
сортировки вводятся два разных правила выполнения итераций метода: в 
зависимости от четности или нечетности номера итерации сортировки для 
обработки выбираются элементы с четными или нечетными индексами 
соответственно, сравнение выделяемых значений всегда осуществляется с 
их правыми соседними элементами. Таким образом, на всех нечетных 
итерациях сравниваются пары 
(при четном n), 
а на четных итерациях обрабатываются элементы 
. 
После 
n
-кратного повторения итераций сортировки исходный набор 
данных оказывается упорядоченным. 
// Последовательный алгоритм чет-нечетной перестановки 
void OddEvenSort(double A[], int n) { 
for (int i = 1; i < n; i++) { 
if (i % 2 == 1) { // нечетная итерация 
for (int j = 0; j < n/2 - 2; j++)
compare_exchange(A[2*j + 1], A[2*j + 2]); 
if (n % 2 == 1) // сравнение последней пары при нечетном n 
compare_exchange(A[n - 2], A[n - 1]); 
} 
else // четная итерация 
for (int j = 1; j < n/2 - 1; j++)
compare_exchange(A[2*j], A[2*j + 1]); 
} 
} 
 
Получение параллельного варианта для метода чет-нечетной 
перестановки уже не представляет каких-либо затруднений – сравнения 
пар значений на итерациях сортировки являются независимыми и могут 
быть выполнены параллельно. В случае 
n
p 
, когда количество 
процессоров меньше числа упорядочиваемых значений, процессоры 
содержат блоки данных размера 
p
n /
и в качестве базовой подзадачи 
может быть использована операция "сравнить и разделить" [2,5]. 
// Параллельный алгоритм чет-нечетной перестановки 
ParallelOddEvenSort(double A[], int n) { 

43 
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); 
} 
} 
} 
 
Для пояснения такого параллельного способа сортировки в 
таблице 2.3 приведен пример упорядочения данных при 
4
,
16


p
n
(т.е. 
блок значений на каждом процессоре содержит 
4
/

p
n
элемента). В 
первом столбце таблицы приводится номер и тип итерации метода, 
перечисляются пары процессов, для которых параллельно выполняются 
операции "сравнить и разделить". Для каждого шага сортировки показано 
состояние упорядочиваемого набора данных до и после выполнения 
итерации. 
Таблица 2.3. Пример сортировки данных 
параллельным методом чет-нечетной перестановки 

жүктеу/скачать 6.58 Mb.

Достарыңызбен бөлісу: