Вычисление частных сумм последовательности числовых значений

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

,

где есть количество суммируемых значений (данная задача известна также под названием prefix sum problem – см. п. 3.3).

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

.

..Последовательный алгоритм суммирования

Традиционный алгоритм для решения этой задачи состоит в последовательном суммировании элементов числового набора

Вычислительная схема данного алгоритма может быть представлена следующим образом (см. рис. 4.1):

,

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

есть множество дуг, определяющих информационные зависимости операций.

Рис. 4.1. Последовательная вычислительная схема алгоритма суммирования

Как можно заметить, данный "стандартный" алгоритм суммирования допускает только строго последовательное исполнение и не может быть распараллелен.

..Каскадная схема суммирования

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

• на первой итерации каскадной схемы все исходные данные разбиваются на пары и для каждой пары вычисляется сумма значений,
• далее все полученные суммы пар также разбиваются на пары и снова выполняется суммирование значений пар и т.д.

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

,

Рис. 4.2. Каскадная схема алгоритма суммирования

где есть вершины графа ( - операции ввода, - операции первой итерации и т.д.), а множество дуг графа определяется соотношениями:

.

Как можно оценить, количество итераций каскадной схемы оказывается равным величине

,

а общее количество операций суммирования

совпадает с количеством операций последовательного варианта алгоритма суммирования. При параллельном исполнении отдельных итераций каскадной схемы общее количество параллельных операций суммирования является равным

.

Как результат, можно оценить показатели ускорения и эффективности каскадной схемы алгоритма суммирования

где есть необходимое для выполнения каскадной схемы количество процессоров.

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

.

..Модифицированная каскадная схема

Получение асимптотически ненулевой эффективности может быть обеспечено, например, при использовании модифицированной каскадной схемы [18]. В новом варианте каскадной схемы все проводимые вычисления подразделяется на два последовательно выполняемых этапа суммирования (см. рис. 4.3):

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

Рис. 4.3. Модифицированная каскадная схема суммирования

Для упрощения построения оценок можно предположить . Тогда для выполнения первого этапа требуется выполнение параллельных операций при использовании процессоров. Для выполнения второго этапа необходимо

параллельных операций для процессоров. Как результат, данный способ суммирования характеризуется следующими показателями:

, .

С учетом полученных оценок показатели ускорения и эффективности модифицированной каскадной схемы определяются соотношениями:

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

.

Можно отметить также, что данные значения показателей достигаются при количестве процессоров, определенном в теореме 5 (см. раздел 2).

#######################################################################################

..Умножение матрицы на вектор 42

Задача умножения матрицы на вектор определяется соотношениями

.

Тем самым, получение результирующего вектора предполагает повторения однотипных операций по умножению строк матрицы и вектора . Получение каждой такой операции включает поэлементное умножение элементов строки матрицы и вектора и последующее суммирование полученных произведений. Общее количество необходимых скалярных операций оценивается величиной

.

Как следует из выполняемых действий при умножении матрицы и вектора, параллельные способы решения задачи могут быть получены на основе параллельных алгоритмов суммирования (см. параграф 4.1). В данном разделе анализ способов распараллеливания будет дополнен рассмотрением вопросов организации параллельных вычислений в зависимости от количества доступных для использования процессоров. Кроме того, на примере задачи умножения матрицы на вектор будут обращено внимание на необходимость выбора наиболее подходящей топологии вычислительной системы (существующих коммуникацион­ных каналов между процессорами) для снижения затрат для организации межпроцессорного взаимодействия.

..Достижение максимально возможного быстродействия ( )

1. Выбор параллельного способа вычислений. Выполним анализ информационных зависимостей в алгоритме умножения матрицы на вектор для выбора возможных способов распараллеливания. Как можно заметить

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

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

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

Таким образом, максимально необходимое количество процессоров определяется величиной

.

Использование такого количества процессоров может быть представлено следующим образом. Множество процессоров разбивается на групп

,

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

Рис. 4.5. Вычислительная схема операции умножения строки матрицы на вектор

2. Оценка показателей эффективности алгоритма. Время выполнения параллельного алгоритма при использовании процессоров определяется временем выполнения параллельной операции умножения и временем выполнения каскадной схемы

.

Как результат, показатели эффективности алгоритма определяются следующими соотношениями:

, ,

.

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

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

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

Коммуникационные действия, выполняемые при решении поставленной задачи, состоят в передаче данных между парами процессоров МВС. Подробный анализ длительности реализации таких операций проведен в п. 3.3.

4. Рекомендации по реализации параллельного алгоритма. При реализации параллельного алгоритма целесообразно выделить начальный этап по загрузке используемых процессоров исходными данными. Наиболее просто такая инициализация обеспечивается при топологии вычислительной системы с топологией в виде полного графа (загрузка обеспечивается при помощи одной параллельной операции пересылки данных). При организации множества процессоров в виде гиперкуба может оказаться полезной двухуровневое управление процессом начальной загрузки, при которой центральный управляющий процессор обеспечивает рассылку строк матрицы и вектора к управляющим процессорам процессорных групп , , которые, в свою очередь, рассылают элементы строк матрицы и вектора по исполнительным процессорам. Для топологий в виде линейки или кольца требуется последовательных операций передачи данных с последовательно убывающим объемом пересылаемых данных от до элементов.

..Использование параллелизма среднего уровня ( )

1. Выбор параллельного способа вычислений. При уменьшении доступного количества используемых процессоров ( ) обычная каскадная схема суммирования при выполнении операций умножения строк матрицы на вектор становится не применимой. Для простоты изложения материала положим и воспользуется модифицированной каскадной схемой. Начальная нагрузка каждого процессора в этом случае увеличивается и процессор загружается ( ) частями строк матрицы и вектора . Время выполнения операции умножения матрицы на вектор может быть оценено как величина

.

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

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

- множество процессоров разбивается на непересекающиеся процессорные группы

,

при этом группа , , состоит из процессоров и используется для выполнения итерации каскадного алгоритма (группа применяется для реализации поэлементного умножения); общее количество процессоров ;

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

- при выполнении вычислений каждый раз после завершения операции поэлементного умножения осуществляется загрузка процессоров группы элементами очередной строки матрицы и инициируется процесс вычислений для вновь загруженных данных.

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

Рис. 4.6. Состояние конвейера для операции умножения строки матрицы на вектор после выполнения 2 итераций

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

.

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

Как результат, показатели эффективности алгоритма определяются соотношениями следующего вида:

, ,

.

3. Выбор топологии вычислительной системы. Целесообразная топология вычислительной системы полностью определяется вычислительной схемой – это полное бинарное дерево высотой . Количество передач данных при такой топологии сети определяется общим количеством итераций, выполняемых конвейером, т.е.

.

Инициализация вычислений начинается с листьев дерева, результаты суммирования накапливаются в корневом процессоре.

Анализ трудоемкости выполняемых коммуникационных действий для вычислительных систем с другими топологиями межпроцессорных связей предполагается осуществить в качестве самостоятельного задания (см. также п. 3.4).

..Организация параллельных вычислений при

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

Подобная схема вычислений может быть определена следующим образом. Представим множество процессоров в виде линейной последовательности (см. рис. 4.7):

;

каждый процессор , , используется для умножения элементов столбца матрицы и элемента вектора . Выполнение вычислений на каждом процессоре , , состоит в следующем:

- запрашивается очередной элемент столбца матрицы;

- выполняется умножение элементов и ;

- запрашивается результат вычислений предшествующего процессора;

- выполняется сложение значений ;

- полученный результат пересылается следующему процессору.

Рис. 4.7. Состояние линейного конвейера для операции умножения строки матрицы на вектор после выполнения двух итераций

При инициализации описанной схемы необходимо выполнить ряд дополнительных действий:

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

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

Кроме того, для однородности описанной схемы для первого процессора , у которого нет предшествующего процессора, целесообразно ввести пустую операцию сложения ( ).

Для иллюстрации на рис. 4.7 показано состояние процесса вычислений после второй итерации конвейера при .

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

.

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

Показатели эффективности данной вычислительной схемы определяются соотношениями:

, ,

.

3. Выбор топологии вычислительной системы. Необходимая топология вычислительной системы для выполнения описанного алгоритма однозначно определяется предлагаемой вычислительной схемой – это линейно упорядоченное множество процессоров (линейка).

#######################################################################################

..Матричное умножение 43

Задача умножения матрицы на матрицу определяется соотношениями

.

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

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

..Макрооперационный анализ алгоритмов решения задач

Задача матричного умножения требует для своего решения выполнение большого количества операций ( скалярных умножений и сложений). Информационный граф алгоритма при большом размере матриц становится достаточно объемным и, как результат, непосредственный анализ этого графа затруднен. После выявления информационной независимости выполняемых вычислений могут быть предложены многочисленные способы распараллеливания алгоритма.

С другой стороны, алгоритм выполнения матричного умножения может быть рассмотрен как процесс решения независимых подзадач умножения матрицы на столбцы матрицы . Введение макроопераций, как можно заметить по рис. 4.8, приводит к более компактному представлению информационного графа алгоритма, значительно упрощает проблему выбора эффективных способов распараллеливания вычислений, позволяет использовать типовые параллельные методы выполнения макроопераций в качестве конструктивных элементов при разработке параллельных способов решения сложных вычислительных задач.

Рис. 4.8. Вычислительная схема матричного умножения при использовании макроопераций умножения матрицы A на столбец матрицы B

Важно отметить, что процесс введения макроопераций может осуществляться поэтапно с последовательно возрастающим уровнем детализации используемых операций. Так, для задачи матричного умножения после построения графа вычислений на основе макроопераций умножения матрицы на вектор может быть выполнено рассмотрение каждой макрооперации как последовательности независимых операций скалярного произведения векторов и т.п. Подобная иерархическая декомпозиционная методика построения параллельных методов решения сложных задач является одной из основных в параллельном программировании и широко используется в практике.

..Организация параллелизма на основе разделения данных

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

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

,

где каждый блок матрицы определяется в соответствии с выражением

.

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

Рис. 4.9. Информационный граф матричного умножения при блочном представлении матриц

Для организации параллельных вычислений предположим, что процессоры образуют логическую прямоугольную решетку размером (обозначим через процессор, располагаемый на пересечении строки и столбца решетки). Основные положения параллельного метода, известного как алгоритм Фокса (Fox) [15], состоят в следующем:

• каждый из процессоров решетки отвечает за вычисление одного блока матрицы ;
• в ходе вычислений на каждом из процессоров располагается четыре матричных блока:

o блок матрицы , вычисляемый процессором;

o блок матрицы , размещенный в процессоре перед началом вычислений;

o блоки , матриц и , получаемые процессором в ходе выполнения вычислений;

Выполнение параллельного метода включает:

• этап инициализации, на котором на каждый процессор передаются блоки , и обнуляются блоки на всех процессорах;
• этап вычислений, на каждой итерации , которого выполняется:

o для каждой строки , процессорной решетки блок процессора пересылается на все процессоры той же строки ; индекс , определяющий положение процессора в строке, вычисляется по соотношению

,

( есть операция получения остатка от целого деления);

o полученные в результаты пересылок блоки , каждого процессора перемножаются и прибавляются к блоку

;

o блоки каждого процессора пересылаются процессорам , являющимися соседями сверху в столбцах процессорной решетки (блоки процессоров из первой строки решетки пересылаются процессорам последней строки решетки).

Для пояснения приведенных правил параллельного метода на рис. 4.10 приведено состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений (для процессорной решетки ).

Приведенный параллельный метод матричного умножения приводит к равномерному распределению вычислительной нагрузки между процессорами

, .

Вместе с тем, блочное представление матриц приводит к некоторому повышению объема пересылаемых между процессорами данных - на этапе инициализации и на каждой итерации этапа вычислений на каждый процессор передается 2 блока данных общим объемом . Учитывая выполняемое количество итераций метода, объем пересылаемых данных для каждого процессора составляет величину

Рис. 4.10. Состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений

Объем пересылаемых данных может быть снижен, например, при использовании строкового (для ) и столбцового (для ) разбиения матриц, при котором справедлива оценка

.

Данные оценки показывают, что различие объемов пересылаемых данных

является не столь существенным и данное различие уменьшается при увеличении числа используемых процессоров.

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

#######################################################################################

..Сортировка 44

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

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

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

Возможные способы решения этой задачи широко обсуждаются в литературе; один из наиболее полных обзоров алгоритмов сортировки содержится в работе [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). Следует отметить, что сформированные в результате такой процедуры блоки на процессорах и совпадают по размеру с исходными блоками и и все значения, расположенные на процессоре , являются меньшими значений на процессоре .

..Пузырьковая сортировка

Алгоритм пузырьковой сортировки [7], общая схема которого представлена в начале данного раздела, в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения используется не сам этот алгоритм, а его модификация, известная в литературе как метод чет-нечетной перестановки (odd-even transposition) [23]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Т.е., на всех нечетных итерациях сравниваются пары

, ,…, (при четном ),

на четных итерациях обрабатываются элементы

, ,…, .

После -кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.

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

Таблица 4.1. Пример сортировки данных параллельным методом чет-нечетной перестановки

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

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

,

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

,

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