НОУ ІНТУЇТ | лекція | Паралельні методи сортування

1. 9.5. Швидке сортування 9.5.1. послідовний алгоритм
2. 9.5.2. Паралельний алгоритм швидкого сортування
3. 9.5.2.2. аналіз ефективності

9.5. Швидке сортування

9.5.1. послідовний алгоритм

При загальному розгляді алгоритму швидкого сортування (the quick sort algorithm), запропонованої Хоаром (CAR Hoare), перш за все слід зазначити, що цей метод ґрунтується на послідовному поділі сортується набору даних на блоки меншого розміру таким чином, що між значеннями різних блоків забезпечується відношення впорядкованості (для будь-якої пари блоків все значення одного з цих блоків не перевищують значень іншого блоку). На першій ітерації методу здійснюється розподіл вихідного набору даних на перші дві частини - для організації такого поділу вибирається деякий провідний елемент і всі значення набору, менші провідного елементу, переносяться в перший формується блок, всі інші значення утворюють другий блок набору. На другий ітерації сортування описані правила застосовуються рекурсивно для обох сформованих блоків і т.д. При належному виборі провідних елементів після виконання log2n ітерацій вихідний масив даних виявляється впорядкованим. Більш докладний виклад методу може бути отримано, наприклад, в [ [26] , [50] ].

Ефективність швидкого сортування в значній мірі визначається правильністю вибору провідних елементів при формуванні блоків. У гіршому випадку трудомісткість методу має той же порядок складності, що і бульбашкова сортування (тобто T1 ~ n2). При оптимальному виборі провідних елементів, коли поділ кожного блоку відбувається на рівні за розміром частини, трудомісткість алгоритму збігається з швидкодією найбільш ефективних способів сортування . В середньому випадку кількість операцій, що виконуються алгоритмом швидкого сортування, визначається виразом (див., Наприклад, [ [26] , [50] ]):

Загальна схема алгоритму швидкого сортування може бути представлена ​​в наступному вигляді (як провідного елементу вибирається перший елемент впорядковує набору даних).

Алгоритм 9.5. Послідовний алгоритм швидкого сортування

// Алгоритм 9.5 // Послідовний алгоритм швидкого сортування void QuickSort (double A [], int i1, int i2) {if (i1 <i2) {double pivot = A [i1]; int is = i1; for (int i = i1 + 1; i <i2; i ++) if (A [i] Ј pivot) {is = is + 1; swap (A [is], A [i]); } Swap (A [i1], A [is]); QuickSort (A, i1, is); QuickSort (A, is + 1, i2); }}

9.5.2. Паралельний алгоритм швидкого сортування

9.5.2.1. Організація паралельних обчислень

Паралельне узагальнення алгоритму швидкого сортування (див., Наприклад, [63]) найбільш простим способом може бути отримано, якщо топологія комунікаційної мережі може бути ефективно представлена ​​у вигляді N мірного гіперкуба (тобто p = 2N). Нехай, як і раніше, початковий набір даних розподілений між процесорами блоками однакового розміру n / p; результуюче розташування блоків має відповідати нумерації процесорів гіперкуба. Можливий спосіб виконання першої ітерації паралельного методу при таких умовах може полягати в наступному:

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

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

Для пояснення на Мал. 9.6 представлений приклад упорядкування даних при n = 16, p = 4 (тобто блок кожного процесора містить 4 елементи). На цьому малюнку процесори зображені у вигляді прямокутників, всередині яких показано вміст упорядковуваних блоків даних; значення блоків наводяться на початку і при завершенні кожної ітерації сортування. Взаємодіючі пари процесорів з'єднані двонаправленими стрілками. Для поділу даних вибиралися найкращі значення провідних елементів: на першій ітерації для всіх процесорів використовувалося значення 0, на другий ітерації для пари процесорів 0, 1 провідний елемент дорівнює -5, для пари процесорів 2, 3 це значення було прийнято рівним 4.

Приклад упорядкування даних паралельним методом швидкого сортування (без результатів локальної сортування блоків)

Як і раніше, в якості базової підзадачі для організації паралельних обчислень може бути обрана операція "порівняти і розділити", а кількість підзадач збігається з числом використовуваних процесорів. Розподіл подзадач по процесорам повинно проводитися з урахуванням можливості ефективного виконання алгоритму при поданні топології мережі передачі даних у вигляді гіперкуба.

9.5.2.2. аналіз ефективності

Оцінимо трудомісткість розглянутого паралельного методу. Нехай у нас є N -мірний гиперкуб, що складається з p = 2N процесорів, де p <n.

Ефективність паралельного методу швидкого сортування, як і в послідовному варіанті, багато в чому залежить від правильності вибору значень провідних елементів. Визначення загального правила для вибору цих значень є досить важко. Складність такого вибору може бути знижена, якщо виконати впорядкування локальних блоків процесорів перед початком сортування і забезпечити однорідний розподіл сортируемих даних між процесорами обчислювальної системи.

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

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

Таким чином, загальний час обчислень паралельного алгоритму швидкого сортування становить

де є час виконання базової операції перестановки.

Розглянемо тепер складність виконуваних комунікаційних операцій. Загальна кількість міжпроцесорних обмінів для розсилки ведучого елемента на N -мірному гиперкубе може бути обмежена оцінкою

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

де - латентність, - пропускна здатність мережі, а w є розмір елемента набору в байтах.

З урахуванням всіх отриманих співвідношень загальна трудомісткість алгоритму виявляється рівною