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

Сортировки

Постановка задачи
  • Выполнить реализацию параллельного и последовательного алгоритма сортировки пузырьком. Сравнить производительность двух алгоритмов для различного числа процессов и для различного объема сортируемых данных.

  • Выполнить реализацию параллельного и последовательного алгоритма быстрой сортировки. Сравнить производительность двух алгоритмов для различного числа процессов и для различного объема сортируемых данных.


Описание алгоритма
  • Последовательная версия пузырьковой сортировки

       Последовательный алгоритм пузырьковой сортировки сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности (a1, a2, ..., an) алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов (a1, a2), (a2, a3), ..., (an-1, an).

       В результате после первой итерации алгоритма самый большой элемент перемещается ("всплывает") в конец последовательности. Далее последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и описанная выше процедура применяется к оставшейся части последовательности (a'1, a'2, ..., a'n-1).

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



  • Параллельная версия пузырьковой сортировки

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

       Таким образом, на всех нечетных итерациях сравниваются пары

    (a1, a2), (a3, a4), ..., (an-1,an) (при четном n),

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

    (a2, a3), (a4, a5), ..., (an-2,an-1).

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

  • Последовательная версия быстрой сортировки

       При общем рассмотрении алгоритма быстрой сортировки (the quick sort algorithm), предложенной Хоаром (C.A.R. Hoare), прежде всего следует отметить, что этот метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока).

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

  • Параллельная версия быстрой сортировки

       Параллельное обобщение алгоритма быстрой сортировки наиболее простым способом может быть получено, если топология коммуникационной сети может быть эффективно представлена в виде N-мерного гиперкуба (т.е. p=2N). Пусть, как и ранее, исходный набор данных распределен между процессорами блоками одинакового размера n/p; результирующее расположение блоков должно соответствовать нумерации процессоров гиперкуба. Возможный способ выполнения первой итерации параллельного метода при таких условиях может состоять в следующем:

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

       В результате выполнения такой итерации сортировки исходный набор оказывается разделенным на две части, одна из которых (со значениями меньшими, чем значение ведущего элемента) располагается на процессорах, в битовом представлении номеров которых бит N равен 0. Таких процессоров всего p/2, и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N-1. К этим подгиперкубам, в свою очередь, может быть параллельно применена описанная выше процедура. После N-кратного повторения подобных итераций для завершения сортировки достаточно упорядочить блоки данных, получившиеся на каждом отдельном процессоре вычислительной системы.

Анализ эффективности
  • Пузырьковая сортировка

       Последовательный метод упорядочивания данных характеризуется квадратичной зависимостью сложности от числа упорядочиваемых данных, т.е. T1~n^2. Но для сортировки могут быть применены более эффективные последовательные алгоритмы, трудоемкость которых имеет порядок


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

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


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


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


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


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


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

  • Быстрая сортировка

      Оценим трудоемкость рассмотренного параллельного метода. Пусть у нас имеется N-мерный гиперкуб, состоящий из p=2N процессоров.

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

      При завершении вычислений процессор выполняет сортировку своих блоков, что может быть выполнено при использовании быстрых алгоритмов за (n/p)log2(n/p) операций.Таким образом, общее время вычислений параллельного алгоритма быстрой сортировки составляет

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

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

      При используемых предположениях (выбор ведущих элементов осуществляется наилучшим образом) количество итераций алгоритма равно log2p, а объем передаваемых данных между процессорами всегда равен половине блока, т.е. величине (n/p)/2. При таких условиях коммуникационная сложность параллельного алгоритма быстрой сортировки определяется при помощи соотношения:

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

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


Результаты

Эксперимент проводился на следующем ПК:
Процессор - Intel Core i5 CPU M 430 2.27 GHz
Оперативная память - 4 GB
Операционная система - MS Windows 7 x64
Компилятор - MS Visual Studio 2008
Скорость обмена между процессами - 1 698 986 918 байт/с
Время выполнения базовой операции перестановки - 10 нс
Размер элемента набора - 8 байта
Tp - практическое время выполнения
Tp* - теоретическое время выполнения


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

Количество сортируемых чисел Последовательный алгоритм Параллельный алгоритм,2 процесса,Tp Параллельный алгоритм,2 процесса,Tp* Ускорение (2 процесса) Параллельный алгоритм,4 процесса, Tp Параллельный алгоритм,4 процесса, Tp* Ускорение (4 процесса)
5.000 0,096152 0,107055 0,098532 0, 898217 0,142816 0,110983 0,067326
10.000 0,203184 0,203183 0,298739 1,000009 0,21655 0,249832 0,938273
15.000 0,709623 0,709621 0,796482 1,183293 0,578042 0,549830 1,227639
20.000 1,209853 0,939602 0,928714 1,287629 0,897042 1,109374 1,348720
30.000 3,398720 2,299088 3,198023 1,478293 1,923842 2,709382 1,766630

Быстрая сортировка

Количество сортируемых чисел Последовательный алгоритм Параллельный алгоритм,2 процесса, Tp Параллельный алгоритм,2 процесса, Tp* Ускорение (2 процесса) Параллельный алгоритм,4 процесса, Tp Параллельный алгоритм,4 процесса, Tp* Ускорение (4 процесса)
10.000 0,000545 0,000591 0,000617 0,921122 0,000592 0,000721 0,919823
100.000 0,008219 0,008279 0,0081121 1,028891 0,007412 0,008312 1,109212
500.000 0,044693 0,049270 0,056142 1,109812 0,036906 0,039812 1,210984
1.000.000 0,100101 0,072071 0,079132 1,389001 0,667932 0,691732 1,498702
5.000.000 0,758342 0,484807 0,591945 1,564212 0,42983 0,410834 1,76429
10.000.000 1,489742 0,087123 0,102281 1,709921 0,706203 0,888638 2,10953

Об авторах

Работу выполнили:
студент группы 8410 : Сизов Илья
студентка группы 8409 : Люлькова Елена

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012