67. Навести і описати паралельні методи сортування.
С
ортування
є однією з типових проблем обробки даних
і звичайно розуміється як задача
розміщення елементів неврегульованого
набору значень
в порядку монотонного зростання або убування
Бульбашкове сортування:
послідовний алгоритм
// Последовательный алгоритм пузырьковой copтировки
BubbleSort(продублируйте A[], int n){
для (i=0; i<n-1; i++)
для (j=0; j<n-i; j++)
compare_exchange(,[j+1]);
Трудомісткість обчислень має порядок о(n2)
В прямому вигляді складний для розпаралелювання
Бульбашкове сортування: алгоритм чет-нечетной перестановки
Вводяться два різні правила виконання ітерацій методу:
на всіх непарних ітераціях порівнюються пари (a1, a2), (a3, a4) ..., (an-1,an) (при парному n)
на парних ітераціях обробляються елементи (a2, a3), (a4, a5) ... (an-2,an-1).
Сортування Шелла: паралельний алгоритм
Хай топологія комунікаційної мережі має вид N-мерного гиперкуба (тобто кількість процесорів рівна p=2N).
Дії алгоритму полягають в наступному:
Перший етап (N ітерацій): виконання операції "порівняти і розділити" для кожної пари процесорів в гиперкубе. Формування пар процесорів відбувається за правилом - на кожній ітерації i, 0 Ј i < N, парними стають процесори, у яких відмінність в бітових представленні їх номерів є тільки у позиції N-i
Другий етап: реалізація звичайних ітерацій паралельного алгоритму чет-нечетной перестановки. Ітерації виконуються до припинення фактичної зміни сортованого набору. Загальна їх кількість L може бути різною - від 2 до p.
Швидке сортування
послідовний алгоритм.
Алгоритм швидкого сортування, запропонованої Хоаром (Hoare C.A.R.), грунтується на послідовному розділенні сортованого набору даних на блоки меншого розміру таким чином, що між значеннями різних блоків забезпечується відношення впорядкованості (для будь-якої пари блоків всі значення одного з цих блоків не перевищують значень іншого блоку):
На першій ітерації методу здійснюється розподіл початкового набору даних на перші дві частини - для організації такого розподілу вибирається деякий ведучий елемент і всі значення набору, менші провідного елемента, переносяться в перший формований блок, вся решта значень утворює другий блок набору
На другій ітерації сортування описані правила застосовуються рекурсивно для обох сформованих блоків і т.д.
При оптимальному виборі провідних елементів після виконання log2n ітерацій початковий масив даних виявляється впорядкованим
Сортування з використанням регулярного набору зразків: паралельний алгоритм.
Перший етап: впорядковування блоків кожним процесором незалежне один від одного за допомогою звичайного алгоритму швидкого сортування; далі кожний процесор формує набір з елементів своїх блоків з індексами
0, m, 2m.,(p-1) m, де m=n/p2
Д
ругий
етап: всі сформовані на процесорах
набори даних збираються на одному з
процесорів системи і об'єднуються в
ході послідовного зливання в одну
впорядковану множину; з одержаної
безлічі значень з елементів з індексами
формується набір провідних елементів, який передається всім процесорам;
на завершення етапу кожний процесор виконує розділення свого блоку на p частин з використанням одержаного набору провідних значень
Третій етап: кожний процесор розсилає виділені раніше частини свого блоку всій решті процесорів системи відповідно до порядку нумерації - частина j, 0Ј j<p, кожного блоку пересилається процесору з номером j
Четвертий етап: кожний процесор виконує злиття p одержаних частин в один відсортований блок.
Розглянуті способи паралельного виконання трьох широко відомих методу впорядкування даних:
Алгоритм бульбашкового сортування
Сортування Шелла
Швидке сортування
Для алгоритму швидкого сортування приведено дві додаткові модифікації:
Узагальнене швидке сортування
Сортування з використанням регулярного набору зразків
Представлена програмна реалізація методу узагальненого швидкого сортування
Використаний порядок викладу паралельних методів сортування можна розглядати як приклад процесу послідовного вдосконалення паралельних обчислень з метою поліпшення показників прискорення і ефективності
68.----