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

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

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

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

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

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

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

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

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

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

З результатами порівняльних експериментів з виконання різних послідовних і паралельних алгоритмів обчислення чисел Фібоначчі, створених в рамках різних обчислювальних моделей, можна познайомитися на сайті Intel Software Network ( software.intel.com/ru-ru/blogs/2009/11/06/2002442 ). З розглянутих моделей лише підхід на базі автоматів підтверджує висновки теорії про лінійний характер обчислювальної складності паралельного рекурсивного алгоритму. Розглядаючи ж паралельні рішення на базі бібліотеки Intel TBB (Threading Building Blocks) і мови MC #, можна прийти до помилкового висновку про властивості паралельного алгоритму (в реальному часі складність має експонентну залежність). Звідси - або «час» не те, або реалізація паралельних алгоритмів не паралельна.

З порівняння роботи однопотокового і двухпоточного варіантів паралельного алгоритму на TBB слід, що, наприклад, при двох ядрах ми маємо лінійне прискорення в два рази. Але що це міняє, якщо обчислювальна складність алгоритму має всі ту ж експонентну залежність? У такій ситуації про паралелізм як обчислювальної моделі мови немає. Або, може, потрібна, як у випадку з автоматної моделлю, інша шкала часу? Інакше складається враження, що TBB реалізує якусь подобу «ручки швидкості», що збільшує швидкість роботи процесора. І, здавалося б, - тисни так тисни! Але тут саме час згадати про час реальному - рішення з TBB на одному потоці спочатку зменшує швидкість виконання в шістдесят шість разів, а потім збільшує в два рази. У підсумку маємо уповільнення, коли для досягнення навіть вихідної швидкості нам потрібен процесор, як мінімум, з тридцятьма трьома ядрами. А чи буде «ручка» і далі працювати за лінійним законом? А обчислювальна складність? Якщо вона залишиться експоненційної, то легко будуть «з'їдені» все ядра і будь-яка швидкість.

Для кого-то табун коней - краще, ніж один кінь. Але навіть величезний табун не бігатиме швидше автомобіля з Москви в Санкт-Петербург. Може, між багатоядерним процесором і відповідно багатопотоковим програмуванням - з одного боку, і паралельним програмуванням - з іншого, така ж якісна прірву, як між конем і автомобілем? На це питання ще тільки належить дізнатися відповідь із доказів «лінійності» паралельних алгоритмів Фібоначчі на TBB або на MC #.

***

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

В'ячеслав Любченко, Юрій Тяжлов ( sllubch/[email protected] ) - співробітники компанії «Парадіп» (Москва).

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