Паралельні сортування: швидше, простіше ... розумнішими

1. Алгоритми угруповань - одна з найпопулярніших тем в програмуванні. Однак її обговорення зазвичай зводиться...
2. розумна сортування
3. Про реальному часі виконання тестів
4. конвеєрна сортування
5. Про ефективність автоматної віртуальної машини
6. висновки
7. література

Алгоритми угруповань - одна з найпопулярніших тем в програмуванні. Однак її обговорення зазвичай зводиться до того, що швидше сортування Хоара (або, як її називають, швидкого сортування) ще не придумано. Але є вже інші підходи до розробки алгоритмів, наприклад, паралельне програмування.

Сортування зазвичай порівнюють за кількістю операцій порівняння і / або пересилання. Чим їх більше, тим імовірно повільніше алгоритм [1]. Але такий підхід явно не підходить до паралельним алгоритмам. Більш універсальний критерій - абстрактне час роботи алгоритму.

Якщо поглянути на типову блок-схему програми, то легко побачити, що, як шлях пішохода - не пряма лінія, так і програма містить розгалужені і циклічні ділянки, а її умовні оператори подібно перехресть і переходам розбивають програму на лінійні ділянки. Ці ділянки і можна вважати окремим кроком - тактом абстрактного дискретного часу або лінійної послідовністю таких кроків. Тут кожен такт - це кілька операторів на мові високого рівня або, якщо говорити про низький рівень реалізації алгоритму, якесь число команд асемблера.

Але «програмний шлях» можна уявити і як послідовну зміну внутрішніх станів алгоритму, коли перехід з одного стану в інший здійснюється, виходячи з аналізу значень внутрішніх і зовнішніх даних, даних і поточних станів інших паралельних алгоритмів. І якщо умови для переходу настали, то перехід цей супроводжується виконанням дій. Іноді такі дії асоціюються безпосередньо з станами і виконуються при будь-якому переході в них. Так узагальнено - у формі автоматів Мілі і Мура - можна описати модель програм на базі моделі кінцевого автомата.

Формально моделі блок-схем і кінцевих автоматів еквівалентні; для будь-якої блок-схеми можна створити еквівалентний автомат [3]. Для цього необхідно розмітити оператори-дії блок-схеми (прямокутники) символами внутрішніх станів кінцевого автомата. При цьому безліч шляхів з одного стану в інший визначає безліч переходів, умови, що зустрічаються на шляху, - умова спрацьовування переходу, операції - дії на цьому переході.

Перехід від блок-схем до кінцевих автоматів робить явними дискретні кроки, властиві в тій чи іншій формі будь-якої моделі обчислень. Вони на формальному рівні відповідають дискретним тактам абстрактного або модельного часу [4]. У модель автомата, на відміну від блок-схеми, модель реального часу включена явно: він за визначенням функціонує в дискретному часі. Знаючи реальну тривалість дискретного такту і сама кількість тактів, можна досить точно - точніше, ніж за формулою - розрахувати реальний час роботи моделі.

Перехід до еквівалентного автомату і подальший розрахунок дискретного часу його роботи вводить критерій, який дозволяє точніше оцінити ефективність алгоритму, представленого блок-схемою. Ми досліджуємо його на відомих алгоритмах угруповань. Крім того, ми розробимо паралельні сортування, порівняємо їх між собою і з їх послідовними «конкурентами».

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

Перш ніж розглянути швидку сортування, розглянемо найпростішу - «бульбашкова». В роботі [2] наведено лістинг її програми на Сі, а блок-схема представлена ​​на рис. 1. На ній показані позначки, які відповідають внутрішнім станам еквівалентного автомата, а також імена предикатів і дій автомата, якими позначені елементи блок-схеми. За аналогією створені і автоматні моделі угруповань Шелла і швидкого сортування [2, 5].

Автоматні моделі дозволяють точніше судити про складність алгоритмів. З порівняння за кількістю станів, числу входів / виходів (або предикатів / дій) і загальної кількості переходів слід, що сортування Хоара найскладніша ( Таблиця 1 ). Це загальновідомий факт, але тільки тепер він виражений ще і в конкретних цифрах.

В колонках таблиці 1 розміщені результати роботи на масивах різної довжини, де масив - кратне повторення тестового набору з 15 чисел - 1, 11, 15, 4, 9, 2, 7, 3, 5, 12, 10, 6, 8, 13 , 14.

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

розумна сортування

Для демонстрації таких проблем паралельних систем, як блокування або тупики (deadlock), ситуації відштовхування (starvation) і т.п., Дейкстра давно запропонував задачу про обідають філософів [6, 7]. І доводиться тільки дивуватися, що її ще не застосували для вирішення проблеми сортування.

У задачі кілька філософів сідають обідати за спільний стіл, де кожному виділено місце і вилка, що лежить зліва. Для їжі потрібні дві вилки, одну з яких філософ повинен взяти (попросити) її у сусіда праворуч. Проблема не тільки в тому, що сусід може її не дати, або вилки сусіда може не виявитися на місці, але і в тому, що вилку самого філософа можуть взяти, а потім і не повернути. Рішення завдання полягає в створенні такого протоколу взаємодії між філософами, який виключав би конфлікти, що призводять до «голодної смерті» одного з об'єктів.

Втім, зараз нас в задачі про філософів цікавлять не тупики, а то, що їм можна доручити задачу сортування. Для цього потрібно доручити кожному філософу сортування вилок, якими він їсть. Самі вилки при цьому потрібно попередньо перенумерувати (відповідно до даних масиву) і визначити, кому з філософів відповідає перший елемент масиву. Через якийсь час філософи впорядкують вилки відповідно до критерію сортування. Такий алгоритм сортування на базі філософів ми будемо далі називати «розумної сортуванням» або Ф-сортуванням.

У використовуваному нами рішенні окремий філософ представлений двома паралельними моделями - «вилкою» і «слугою» [6, 7]. Моделі представлені на рис. 2 автоматами P і F. Ці автомати, взаємодіючи між собою, реалізують поведінку окремого філософа, а філософи, спілкуючись між собою, - загальна поведінка системи, вирішуючи, як в нашому випадку, завдання сортування даних. Зв'язки автоматів на графі зображені пунктирними стрілками. Аналогічними стрілками показані зв'язку філософа з його сусідами. Автомати і зв'язку в сумі складають модель філософа в формі СМКА (мережева машина кінцевого автомата) [8].

У СМКА компонентні автомати функціонують паралельно і в єдиному дискретному часі. Тому ми маємо право за кількістю тактів будь-якого з автоматів мережі судити про дискретно часу, який витрачено системою на рішення задачі. Абстрактніше час сортування масивів даних філософами приведено в таблиці 2 (Рядок Philosopher). Порівняння таблиць 1 і 2 показує, що філософи сортують масиви втричі швидше, ніж швидке сортування.

Про реальному часі виконання тестів

Обговоримо тепер відповідність абстрактного і реального часів. Оскільки автоматні моделі реалізовані на віртуальній, а не на реальній машині, то від них не можна чекати реальних швидкостей, які показують еквівалентні їм сортування, реалізовані на «рідний» архітектурі.

Але, розглядаючи реалізацію паралельних алгоритмів і звертаючи увагу на реальну швидкість роботи, потрібно враховувати і проблему реалізації самого паралелізму. У сучасних популярних процесорах і операційних системах він, в основному, моделюється. При цьому моделлю паралельних обчислень слід вважати модель потоків, ниток і т.п. Але це означає, що паралельні алгоритми, що виконуються на віртуальній автоматної машині і на «рідний», паралельної, але теж віртуальній машині, перебувають приблизно в рівних умовах. Таким чином, реалізуючи той чи інший паралельний алгоритм (ті ж сортування), ми по їх роботі можемо оцінювати ефективність відповідних паралельних моделей і / або віртуальних машин.

«Розумна сортування» представляє одночасно і паралельну модель обчислень. При цьому вона дозволяє досить точно оцінити ефективність реалізації віртуальної машини, а не тільки алгоритму сортування як такого. Дані таблиці 2 дозволяють оцінити швидкісні якості паралельної автоматної моделі. І якщо реалізувати цей же алгоритм, використовуючи типові паралельні механізми (нитки і т.п.), то швидкість сортування буде в кілька разів менше.

Реальний час виконання тесту можна визначити лише з певною точністю. Дискретні ж кроки або абстрактне час визначаються точно. Безумовно, при порівнянні різних алгоритмів, потрібно враховувати відмінність в кодах дій, а також його вплив на реальний час роботи моделі, але, як правило, у близьких алгоритмів, а тим більше еквівалентних, однакові за змістом дії та відрізняються незначно.

конвеєрна сортування

Практична значимість завдання сортування і результати тестування Ф-сортування стимулюють на пошуки ще більш ефективних алгоритмів. Чи можна сортування ще прискорити? Один із шляхів - створити більшу кількість зв'язків між об'єктами, інший - використання більш простих протоколів. Останній шлях, який ми розглянемо на прикладі «конвеєрної сортування», найбільш реальний.

Уявімо філософів, які, підкоряючись певного ритму, як на конвеєрі, беруть вилки, потім їдять і, змінюючи, якщо необхідно, їх місцями, кладуть вилки знову на стіл. А щоб при цьому не було конфліктів з сусідами, нехай філософи роблять це через одного і через такт. Нехай, наприклад, на одному такті їжу поглинають ( «сортують») філософи з непарними номерами, на іншому - з парними. Результати роботи такої «конвеєрної сортування» представлені в таблиці 2 рядком Pipeline. Швидкість сортування «на конвеєрі» зросла більш ніж в п'ять разів!

Про ефективність автоматної віртуальної машини

Спробуємо оцінити використану при тестуванні віртуальну машину з точки зору ефективності реалізації паралельних процесів. Для чого зведемо результати тестування послідовної автоматної сортування Хоара та паралельних алгоритмів в окрему таблицю 3 .

У порівнянні з алгоритмом Хоара процес сортування може бути прискорений в п'ятнадцять разів. Але, правда, в абстрактному часу. У реальному ж часу, алгоритм Хоара в різних режимах роботи має або найвищу швидкість роботи або найнижчу. При цьому режим роботи без виведення поточної інформації про стан масиву відповідає додатку обчислювального типу. Так працюють, наприклад, стандартні бібліотечні функції.

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

Дані в стовпці V дозволяють оцінити вплив затримок, внесених віртуальною машиною. При інтенсивному виведення даних, автоматне моделювання послідовних обчислювальних процесів уповільнює процес обчислень приблизно на 3-4% для одного процесу і менш ніж втричі при наявності майже двох тисяч паралельних процесів. Дійсно, час роботи набагато сильніше залежить від режиму роботи програми (в одному з тестів розмір сформованого текстового доходить до 36 Мбайт), ніж від кількості паралельних процесів.

З порівняння стовпців V і VI слід досить цікавий висновок: запис в файл на диск і відображення цієї ж інформації у вікні програми займає приблизно однаковий час. Вплив виведення у всіх його проявах на ефективність роботи програми істотно. Той же програмний цикл, але без виведення даних, займе мізерно малий час (рядок Qsort, стовпець III).

висновки

Існуючі апаратні паралельні архітектури (кластери, матричні, векторні процесори і т.п.) спеціалізовані, а тому мають досить вузьку сферу застосування і в загальному випадку низьку ефективність. На прикладі угруповань ми розглянули універсальну паралельну модель - СМКА, в якій окремий процес - це автомат, а все автомати - система взаємопов'язаних автоматів, що працюють в абстрактному єдиному часу. Ефективність даної моделі по відношенню до інших найкраще оцінити, вирішуючи конкретні приклади. Сортування - майже ідеальний засіб для з'ясування переваг тій чи іншій моделі, мови або технології і для їх порівняння між собою.

Результати тестування переконують, що синхронні системи (наприклад, конвеєрна сортування) ефективніше систем асинхронного типу (Ф-сортування). Можна піти навіть далі, припустивши, що немає синхронного і асинхронного програмування, а є просто паралельне програмування, що базується на тій чи іншій моделі обчислень, але використовує різні типи протоколів - синхронні і асинхронні.

Паралельна сортування може бути швидше швидкої, але поки лише в певних ситуаціях. Застереження «може бути» і з приводу «ситуацій» ми можемо виключити повністю, реалізувавши віртуальну машину апаратно. На першому етапі можна навіть обмежитися реалізацією не в повному обсязі: виграш можна отримати, використовуючи навіть більш простий послідовний автоматний варіант.

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

література

1. Вірт Н. Алгоритми і структури даних: Пер з англ. - М .: Мир, 1989.
2. Шілдт Г. Теорія і практика С ++: пров. з англ. - СПб .: BHV - Санкт-Петербург, 1999..
3. Баранов С.І. Синтез мікропрограмних автоматів. - Л .: Енергія, 1979.
4. Глушков В.М. Введення в кібернетику. - К .: Вид-во АН Української РСР. 1964.
5. Порівняння алгоритмів сортування. http://mastergl.narod.ru/sort.html
6. Любченко В.С. Обідають філософи Дейкстри (про модель паралельних процесів) http://www.softcraft.ru/auto/ka/fil/fil.shtml
7. Хоар Ч. Взаємодіючі послідовні процеси: Пер. з англ. - М .: Мир, 1989.
8. Любченко В.С. Від машини Тьюринга до машини Милі. «Світ ПК», 2002 № 8.

В'ячеслав Любченко ( [email protected] ), Програміст АКБ «Алекскомбанк» (м Александров).