Новости
О Центре
Кластер
Обучение
Основной курс по параллельному программированию
Учебные курсы
Магистратура
Дополнительное образование
Работы студентов
Библиотека
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Cортировка Слиянием

Введение

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

S = {a1, a2, ..., an}

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

S ~ S'={(a1', a2', ..., an'): a1'<= a2' <=... <= an'}

Возможные способы решения этой задачи широко обсуждаются в литературе; в данной работе рассмотрен метод сортировки слиянием.


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

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

Программа должна использовать интерфейс MPI для эффективной работы на системах с распределенной памятью.


Описание алгоритма

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

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

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

3. Если число отсортированных цепочек больше единицы, перейти к шагу 2.

Проще всего формализовать этот алгоритм рекурсивным способом, хотя, конечно, есть и несложные итерационные методы. Функция Merge сортирует участок массива от элемента с номером a до элемента с номером b:


void merge (double* a, int n1, int n2)

{

     int m = (n1 + n2) / 2;

     if (n1 == n2)

          return;

     else

     {

          merge (a, n1, m);

          merge (a, m+1, n2);

          bond (a, n1, m, n2);

     }

}


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

Время работы сортировки слиянием составляет О(n*log2(n)). Пример работы процедуры показан на рисунке:


Параллельная реализация

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


MPI_Bcast (&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

if (rank < n%size)

     k = n/size + 1;

else

     k = n/size;

double *x = new double [k];

MPI_Scatterv(a, raz, dist, MPI_DOUBLE,

          x, k, MPI_DOUBLE,

          0, MPI_COMM_WORLD);

merge(x, 0, k - 1);


После этого мы имеем несколько отсортированных массивов. Теперь задача состоит в слиянии этих массивов в один, результирующий. Слияние будет проводиться итерационно: на первом шаге процессы делятся на пары, и правый массив передаёт свои данные левому. Тот процесс сортирует их, используя функцию bond. На втором шаге также объединяем процессы в пары, но только те, которые были левыми на первом шаге. Опять, также, правый процесс передаёт свои данные левому, а тот их сортирует. Это выполняется до тех пор, пока не останется один процесс. Его массив и будет результатом параллельной сортировки.


int s = size, m = 1;

while (s > 1)

{

     s = s/2 + s%2;

     if ((rank-m)%(2*m) == 0)

     {

          MPI_Send (&k, 1, MPI_INT,

              rank-m, 0, MPI_COMM_WORLD);

          MPI_Send (x, k, MPI_DOUBLE,

              rank-m, 0, MPI_COMM_WORLD);

     }

     if ((rank%(2*m) == 0) && (size - rank > m))

     {

          MPI_Status status;

          int k1;

          MPI_Recv (&k1, 1, MPI_INT,

              rank+m, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

          double *y = new double [k + k1];

          MPI_Recv (y, k1, MPI_DOUBLE,

              rank+m, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

          for (int i = 0; i < k; i++)

              y[i+k1] = x[i];

          bond(y, 0, k1-1, k+k1-1);

          x = new double [k1 + k];

          for (int i = 0; i < k+k1; i++)

              x[i] = y[i];

          k = k + k1;

     }

     m = 2*m;

}


Тестирование

Рассмотрим работу алгоритма на примере. Пусть дан массив из 15 элементов и 4 процесса.

1. На первом шаге объявляем массив в 0-ом процессе, записываем в него элементы и делим этот массив между всеми процессами.

2. Сортируем в каждом процессе массив.

3. Теперь поочерёдно сливаем массивы из процессов в один.


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


Как уже упоминалось выше, трудоёмкость выполнения последовательного алгоритма сортировки слияния равна О(n*log2(n)).

Теперь определим трудоёмкость параллельного алгоритма. После передачи элементов всем процессам они выполняют сортировку последовательным алгоритом слияния. Значит трудоёмкость t1 равна

t1 = (n/p)*log2(n/p)

Определим трудоёмкость метода при слиянии массивов из процессов. Число итераций равно p-1, а в каждой итерации число перестановок равно отношению количества элементов в изначальном массиве n к используемуму количесву процессов на данной итерации. На первом шаге их p, на втором p/2 и т.д. То есть трудоёмкость t2 равна

t2 = n/p + 2*n/p + ... + n = n*(2p-1)/p

Общее время всех выполняемых в ходе сортировки операций передачи блоков можно оценить при помощи соотношения:

Tp(comm)=p(a+w(n/p)/b),

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

Окончательная оценка алгоритма Tp равна

Tp=Tp(comm)+t1+t2=p(a+w(n/p)/b) + (n/p)*log2(n/p) + n*(2p-1)/p

Общая оценка показателя ускорения равна:

Sp = n*log2n / [p(a+w(n/p)/b) + (n/p)*log2(n/p) + n*(2p-1)/p]

Оценка эффективности:

Ep = n*log2n / p*[p(a+w(n/p)/b) + (n/p)*log2(n/p) + n*(2p-1)/p]


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


Вычислительные эксперименты для оценки эффективности параллельного алгоритма сортировки слиянием проводились при следующих условиях и оборудовании:

  • Процессор - Intel Core 2 Duo E6550, 2.33 ГГц
  • Оперативная память - 4 GB
  • Операционная система - Microsoft Windows 7 Enterprise
  • Компилятор - MS Visual Studio 2008
  • Длительность τ базовой скалярной операции - 14 нс
  • Параметры передачи между процессами на одной машине: латентность α - 48,445 млс, пропускная способность β - 985123443 байт/c
  • w = 4 байта


Об авторе

Работу выполнил студент группы 84-10 Мазур Е. С.

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012