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



             

Принципы распараллеливания


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




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