Протестировать и сравнить ускорение параллельного и последовательного алгоритма.
Последовательный алгоритм
Метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока). На первой итерации метода осуществляется деление исходного набора данных на первые две части – для организации такого деления выбирается некоторый ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения образуют второй блок набора. На второй итерации сортировки, описанные правила применяются рекурсивно для обоих сформированных блоков и т.д. При надлежащем выборе ведущих элементов после выполнения log₂n итераций исходный массив данных оказывается упорядоченным.
Параллельный алгоритм
Существует несколько параллельных обобщений последовательного алгоритма быстрой сортировки. Применим простой способ, наиболее подходящий для кластерных систем с большим количеством процессоров(N).
Пусть, исходный набор данных расположен на первом процессоре, с него начинается ускорение алгоритма:
- процессор выбирает ведущий элемент и оставляет слева меньшие элементы, справа большие;
- всю меньшую часть он отдаёт другому процессору;
- отдав меньшую часть, процессор продолжает работать с большей одновременно с другим процессом, который работает с меньшей по принципу начиная с 1го пункта;
- Когда все N процессоров получат свою часть, ускорение алгоритма будет максимальным.
В результате выполнения такой итерации сортировки, исходный набор оказывается разделенным на две части (случайно), меньшая из которых передаётся другому процессору, большая остаётся на исходном для дальнейших итераций, в результате следующей итерации обе части опять будут разделены и опять на двух исходных останятся большие части (на первом процессоре всё равно бОльшая), а меньшие отправятся новым процессам. В этом заключается ускорение алгоритма. При зодействовании всех процессов, все части параллельно будут сортироваться последовательным алгоритмом.
Такой алгоритм даёт максимальное ускорение на многопроцессорных системах (кластерах, суперкомпьютерах).
Однако есть и минус этого алгоритма. Принцип быстрой сортировки в том, что массив делится случайно на 2 части и редко пололам. Процессоры, получающие меньшие части, закончат с ними сортировку быстрее, первый исходный (главный) процессор и будут простаивать. Алгоритм нуждается в модификации.
Проанализируем эффективность алгоритма для p процессоров и N.
Временные затраты на ускорение алгоритма:
Каждую итерацию массив делится случайно. На первой итерации при делении на 2 части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части n1. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части N-n1, с этой частью мы проделываем точно такую же итерацию с разделителем n2. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя nk. Где p=2^k.
T1=[N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk)]*t, где t - время перестановки.
Временные затраты на работу алгоритма при максимальном ускорении:
После достижения максимального ускорения алгоритм будет работать в режиме стандартной быстрой сортировки. Последняя бОльшая, и поэтому учитываемая, часть будет иметь длину (N-n1-...-nk).
T2=[(N-n1-...-nk)log₂(N-n1-...-nk)]*t, где t - время перестановки.
Временные затраты на передачу частей массива процессам:
T3=(α+w/β)(log₂(p))^2 + (α+w(N/2p)/β)(log₂(p)), где α - латентность, β - пропускная способность сети, а w – размер элемента набора в байтах.
Общие временные затраты параллельного алгоритма:
T=T1+T2+T3
*В качестве n берется среднее число, которым может быть разбиение. То есть (из теории вероятности) - 3/4.
Результаты вычислительных экспериментов
Тестирование алгоритма проводился на системе с характеристиками:
Intel(R) Core(TM) 2 Duo (2 GHz); 3072MB RAM.
Таблица 1. Результаты тестов:
|
Объем выборки |
Число ядер процессора |
Время выполнения (послед) |
Время выполнения (паралл) |
Ускорение |
|
1000000 |
2 |
0.14 |
0.094 |
1.489361702 |
|
2000000 |
2 |
0.312 |
0.219 |
1.424657534 |
|
5000000 |
2 |
0.984 |
0.75 |
1.312 |
|
10000000 |
2 |
2.781 |
2.109 |
1.318634424 |
|
20000000 |
2 |
8.594 |
5.469 |
1.57140245 |
|
50000000 |
2 |
44.562 |
25.313 |
1.7604393 |
Параметры передачи между процессами на одной машине: латентность α - 48,445 млс, пропускная способность β - 985123443 байт/c
Так как элементы массива - простой int, w = 4.
Таблица 2. Сравнение теоретических и полученных результатов
|
Объем выборки |
Число ядер процессора |
Время выполнения (теор) |
Время выполнения (практ) |
|
1000000 |
2 |
0,208605738 |
0.094 |
|
2000000 |
2 |
0,417955076 |
0.219 |
|
5000000 |
2 |
1,047356706 |
0.75 |
|
10000000 |
2 |
2,098457012 |
2.109 |
|
20000000 |
2 |
4,204407625 |
5.469 |
|
50000000 |
2 |
10,53579561 |
25.313 |
Об авторе
Работу выполнил:
студент факультета ВМК ННГУ, гр. 8409
Курицын Михаил Владимирович.
