English
РусскийЦель работы.
Изучение метода сортировки Батчера. Реализация сортировки Батчера на многоядерных архитектурах. Исследование алгоритмической сложности последовательной и параллельной реализаций сортировки.
Теоретическая часть.
Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора, состоящего из значений в порядке монотонного убывания или возрастания .
Пусть дана последовательность целых чисел , где . Необходимо отсортировать данную последовательность по возрастанию. Для получения алгоритма сортировки, временная сложность которого меньше, чем необходимо выбирать для сравнения элементы, расположенные на каком-то шаге друг от друга, при этом шаг должен изменяться во время работы алгоритма. Эта идея была реализована в алгоритме сортировки Шелла, где шаг убывает. Однако проблема сортировки Шелла – невозможность одновременного выполнения сравнений и перестановок, что отсутствует в алгоритме Батчера. Приведём алгоритм сортировки Батчера:
Input: a[0..N-1], t, N = 2t
for p = 2t-1, 2t-2,..., 1 do
r = 0
d = p
for q = 2t-1, 2t-2,..., p do
for k = 0,..., N-d-1 do in parallel
if k&p = r then
if a[k] > a[k+d] then
swap(a[k], a[k+d])
end if
end if
end for
d = q – p
r = p
end for
end for
Output: a[0..N-1], a[i] < a[i+1]
Пример 1. Работы алгоритма сортировки Батчера.
p q r d
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
8 8 0 8
4 8 0 4
4 4 4 4
2 8 0 2
2 4 2 6
2 2 2 2
1 8 0 1
1 4 1 7
1 2 1 3
1 1 1 1
Результат
53 87 52 61 98 17 89 27 65 42 15 59 62 77 76 3
53 42 15 59 62 17 76 3 65 87 52 61 98 77 89 27
53 17 15 3 62 42 76 59 65 77 52 27 98 87 89 61
53 17 15 3 62 42 52 27 65 77 76 59 98 87 89 61
15 3 53 17 52 27 62 42 65 59 76 77 89 61 98 87
15 3 53 17 52 27 62 42 65 59 76 77 89 61 98 87
15 3 52 17 53 27 62 42 65 59 76 61 89 77 98 87
3 15 17 52 27 53 42 62 59 65 61 76 77 89 87 98
3 15 17 52 27 53 42 62 59 65 61 76 77 89 87 98
3 15 17 42 27 53 52 61 59 65 62 76 77 89 87 98
3 15 17 27 42 52 53 59 61 62 65 76 77 87 89 98
Практическая часть.
1. Реализовать алгоритм сортировки Батчера для одноядерной архитектуры,
2. Реализовать алгоритм сортировки Батчера для многоядерной архитектуры в соответствии с заданием,
3. Оценить арифметическую сложность последовательной и параллельной реализаций метода,
4. Посчитать теоретическое и практическое ускорение параллельной программы,
5. Разработать и провести полную систему тестов сортировки массива в соответствии с заданием.
Варианты заданий.
1. Сортировка массива с количеством элементов на количестве ядер кратных двум,
2. Сортировка массива с количеством элементов на количестве ядер не кратных двум,
3. Сортировка массива с количеством элементов на количестве ядер кратных двум,
4. Сортировка массива с количеством элементов на количестве ядер не кратных двум,
5. Сортировка массива с произвольным количеством элементов на произвольном количестве ядер.
