Параллельное обобщение базовой операции сортировки

Лекция 7. Параллельные численные алгоритмы для решения типовых задач вычислительной математики: сортировка и обработка графов.

Сортировка. Параллельное обобщение базовой операции сортировки. Пузырьковая сортировка. Сортировка Шелла. Быстрая сортировка. Обработка графов. Нахождение минимально охватывающего дерева. Поиск кратчайших путей.

Сортировка

Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора значений

в порядке монотонного возрастания или убывания

(здесь и далее все пояснения для краткости будут даваться только на примере упорядочивания данных по возрастанию).

Возможные способы решения этой задачи широко обсуждаются в литературе; один из наиболее полных обзоровалгоритмов сортировки содержится в работе [7]. Вычислительная трудоемкость процедуры упорядочивания является достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка, сортировка включением и др.) количество необходимых операций определяется квадратичной зависимостью от числа упорядочиваемых данных

.

Для более эффективных алгоритмов (сортировка слиянием, сортировка Шелла, быстрая сортировка) трудоемкость определяется величиной

.

Данное выражение дает также нижнюю оценку необходимого количества операций для упорядочивания набора из значений; алгоритмы с меньшей трудоемкостью могут быть получены только для частных вариантов задачи.

Ускорение сортировки может быть обеспечено при использовании нескольких ( , ) процессоров. Исходный упорядочиваемый набор в этом случае разделяется между процессорами; в ходе сортировки данные пересылаются между процессорами и сравниваются между собой. Результирующий (упорядоченный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами.

Оставляя подробный анализ проблемы сортировки для специального рассмотрения, в пособии основное внимание уделяется изучению параллельных способов выполнения для ряда широко известных методов внутренней сортировки, когда все упорядочиваемые данные могут быть размещены полностью в оперативной памяти ЭВМ.

Параллельное обобщение базовой операции сортировки

1. При детальном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно обратить внимание, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки

// операция "сравнить и переставить"

if ( a[i] > a[j] ) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения собственно и проявляется различие алгоритмов сортировки. Так, например, в пузырьковой сортировке [7] осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение ("всплывание пузырька"); далее для продолжения сортировки этот уже упорядоченный элемент отбрасывается и действия алгоритма повторяются

// пузырьковая сортировка

for ( i=1; i<n; i++ )

for ( j=0; j<n-i; j++ )

<сравнить и переставить элементы (a[j], a[j+1])>

}

2. Для параллельного обобщения выделенной базовой операции сортировки рассмотрим первоначально ситуацию, когда количество процессоров совпадает с числом сортируемых значений (т.е. ). Тогда сравнение значений и , располагаемых, например, на процессорах и , можно организовать следующим образом:

- выполнить взаимообмен имеющихся на процессорах и значений (с сохранением на этих процессорах исходных элементов);

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

, .

3.Рассмотренное параллельное обобщение базовой операции сортировки может быть надлежащим образом адаптировано и для случая , когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера ) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров и для совместного упорядочения содержимого блоков и может быть осуществлено следующим образом:

- выполнить взаимообмен блоков между процессорами и ;

- объединить блоки и на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре , а другую часть (с большими значениями соответственно) – на процессоре

.

Рассмотренная процедура обычно именуется в литературе как операция "сравнить и разделить" (compare-split). Следует отметить, что сформированные в результате такой процедуры блоки на процессорах и совпадают по размеру с исходными блоками и ивсе значения, расположенные на процессоре , являются меньшими значений на процессоре .