Теория и практика параллельных вычислений
Принципы распараллеливания
При внимательном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно заметить, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановке этих значений, если их порядок не соответствует условиям сортировки.
Пример 9.1. Операция "сравнить и переставить"
// Базовая операция "сравнить и переставить" if ( A[i] > A[j] ) { temp = A[i]; A[i] = A[j]; A[j] = temp; }
Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения, собственно, и проявляется различие алгоритмов сортировки.
Для параллельного обобщения выделенной базовой операции сортировки рассмотрим первоначально ситуацию, когда количество процессоров совпадает с числом сортируемых значений (т. е. p=n) и на каждом из процессоров содержится только по одному значению исходного набора данных. Тогда сравнение значений ai и aj, располагаемых соответственно на процессорах Pi и Pj, можно организовать следующим образом (параллельное обобщение базовой операции сортировки):
- выполнить взаимообмен имеющихся на процессорах Pi и Pj
значений (с сохранением на этих процессорах исходных элементов);
- сравнить на каждом процессоре Pi и Pj получившиеся одинаковые пары значений (ai, aj); результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т. е. Pj) запоминает для дальнейшей обработки большее значение пары
