Теория и практика параллельных вычислений
Масштабирование параллельных вычислений
Рассмотренное параллельное обобщение базовой операции сортировки может быть надлежащим образом адаптировано и для случая p<n, когда количество процессоров меньше числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера n/p) сортируемого набора данных.
Определим в качестве результата выполнения параллельного алгоритма сортировки такое состояние упорядочиваемого набора данных, при котором имеющиеся на процессорах данные упорядочены, а порядок распределения блоков по процессорам соответствует линейному порядку нумерации (т. е. значение последнего элемента на процессоре Pi меньше значения первого элемента на процессоре Pi+1, где 0i<p-1 или равно ему).
Блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (начальная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров Pi и Pi+1 для совместного упорядочения содержимого блоков Ai и Ai+1 может быть осуществлено следующим образом:
- выполнить взаимообмен блоков между процессорами Pi и Pi+1;
- объединить блоки Ai и Ai+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков Ai и Ai+1 процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);
- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре Pi, а другую часть (с большими значениями, соответственно) – на процессоре Pi+1
Рассмотренная процедура обычно именуется в литературе операцией "сравнить и разделить" (compare-split). Следует отметить, что сформированные в результате такой процедуры блоки на процессорах Pi и Pi+1 совпадают по размеру с исходными блоками Ai и Ai+1 и все значения, расположенные на процессоре Pi, не превышают значений на процессоре Pi+1.
Определенная выше операция "сравнить и разделить" может быть использована в качестве базовой подзадачи для организации параллельных вычислений. Как следует из построения, количество таких подзадач параметрически зависит от числа имеющихся процессоров, и, таким образом, проблема масштабирования вычислений для параллельных алгоритмов сортировки практически отсутствует. Вместе с тем следует отметить, что относящиеся к подзадачам блоки данных изменяются в ходе выполнения сортировки. В простых случаях размер блоков данных в подзадачах остается неизмененным. В более сложных ситуациях (как, например, в алгоритме быстрой сортировки – см. подраздел 9.5) объем располагаемых на процессорах данных может различаться, что может приводить к нарушению равномерной вычислительной загрузки процессоров.
