Постановка задачи

Массивы это часто используемый элемент в программе. И самая распространенная операция, выполняемая над ними, это операция сортировки, заключающаяся в том, чтобы последовательность a₀, a₁... a_n расположить в таком порядке, когда выполняется условие: a_i <= a_i+1, для всех i от 0 до n.

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

Метод решения

Для реализации поставленной задачи потребуется модифицированный алгоритм последовательной пузырьковой сортировки под названием «чет-нечет». Смысл его заключается в том, что элементы сравниваются по другому правилу, в отличие от обычного «пузырька», где это происходит последовательно от первой пары элементов, до последней. В модификации с последующим элементом на четных итерациях сравниваются и, если надо, меняются местами четные элементы, а на нечетных соответственно нечетные элементы. Например на 2 итерации будут сравниваться такие пары:(a₀, a₁)( a₂, a₃)( a₄, a₅)…( a_n,a_n+1)(åñëè n ÷åòíî), а на 3 следующие: (a₁, a₂)(a₃,a₄)(a₅,a₆)…(a_n+1,a_n+2).И после n таких сравнений и перестановок мы получим отсортированный массив.

Алгоритм решения

Приведенный выше модифицированный алгоритм легко расспаралелить.

1. Делим массив из n элементов на количество процессов p.
2. Отсылаем каждому процессу его часть массива из n/p элементов.
3. Каждый процесс сортирует полученную часть методом быстрой сортировки.
4. Теперь в цикле от 1 до p выполняем следующие действия для каждого процесса:
   1. Если номер итерации четный и номер процесса четный или номер итерации нечетный и номер процесса нечетный, тогда посылаем и принимаем массив от предыдущего процесса.
      1. Склеиваем полученный массив с массивом процесса, который его получил, сохраняя упорядоченность.
      2. Из полученного массива запоминаем p/n больших элементов.
   2. Если номер итерации четный и номер процесса нечетный или номер итерации нечетный и номер процесса четный, тогда посылаем и принимаем массив от следующего процесса.
      1. Склеиваем полученный массив с массивом процесса, который его получил, сохраняя упорядоченность.
      2. Из полученного массива запоминаем p/n меньших элементов.
5. 5 Склеиваем части со всех процессов в один отсортированный массив.

Анализ эффективности

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

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

Следует также учесть трудоемкость коммуникационных действий:

Где а – латентность, b - пропускная способность сети передачи данных, w - размер элемента упорядочиваемых данных в байтах.

Общее время выполнения:

Где t - время выполнения базовой операции сортировки.

Ускорение S и эффективность E мы можем найти следующим образом:

Результаты вычислительных экспериментов