Особливості паралелізму
1.2.2. Особливості паралелізму.
У цьому пункті, слідуючи [1], ми охарактеризуємо різні особливості та типи паралелізму, суттєві з позицій пошуку адекватних мовних засобів для його вираження. Природно, що зрештою поняття паралелізму пов'язані з одночасністю дій чи процесів, здійснюваних у дискретному часі. Широко відомі поняття синхронності та асинхронності процесів, що протікають, відображають допустимі схеми і “кордони” взаємодії процесів. Пошук моделей абсолютно асинхронних, або абсолютно паралельних процесів хоч і є нерозв'язною проблемою, проте ставить цілком природне і важливе для паралельних обчислень завдання порівняння за виразною силою різних підходів, моделей та мов, пов'язаних з паралельним програмуванням.
Однією із важливих характеристик паралелізму є спосіб його завдання: явний чи неявний.
Перший передбачає існування мови або певного набору примітивів, засобами яких програміст описує в програмі дії, що її цікавлять паралельно виконувані. Примітиви parbeginparend, fork-join, засоби завдання паралельних процесів в MPI, PVM, багатьох інших подібних програмних засобах для завдання паралелізму, нарешті, різні процесні моделі (мережі Петрі, моделі взаємодії процесів Мілнера і Хоара [34] та ін) тощо . - Приклади явного завдання паралелізму.
Паралелізм неявно присутній майже в будь-якій послідовній програмі і його часто з успіхом може виявити компілятор, паралелізм неявно відображений в арифметичних або логічних виразах завдяки властивостям операцій (асоціативності, комутативності, дистрибутивності), що використовуються при їх побудові.
Неявно паралелізм присутній у функціональних мовах [5, 6], логіка першого порядку, Пролог. Завдяки тому, що ці мови мають сувору детонаційну семантику та незалежну паралельну операційну семантику (у функціональних мов – ця семантика здійснюється через процеси згортання та розгортання дерев [5, 6], у логічних формалізмів та мов – за допомогою побудови паралельних алгоритмів виведення [7] . Більше того, будь-яка спроба явної вказівки, що має виконуватися паралельно в таких програмах виглядає протиприродним і, крім того, майже завжди буде призводити до того, що багато можливостей розпаралелювання будуть просто втрачені.
Очевидно, неявні способи відображення паралелізму без звернення до процесу паралельного виконання програми мають ту перевагу, що поділяють аспекти програмування і власне організації паралельного виконання програм, у програміста немає необхідності, як, наприклад, при використанні MPI, з одного боку, програмувати функцію або алгоритм, що реалізують метод розв'язання задачі. З іншого боку, вирішувати іншу задачу, як організувати паралельні процеси її виконання.
Інший аспект характеризації паралелізму пов'язаний із проблемно – орієнтованим мовним середовищем, засобами якого описується паралельна програма.
У зв'язку з цим розрізняють типи паралелізму: функціональний, логічний, паралелізм послідовних програм, паралелізм об'єктно - орієнтованих програм, процесний паралелізм.
Кожен із названих видів паралелізму заснований на певній парадигмі програмування і має свої особливості, що виявляються як у способах його виявлення, так і властивої йому процесної моделі та реалізації.
Говорячи про процесний паралелізм, ми маємо на увазірізні процесні моделі (мережі Петрі, моделі Хоара і Мілнера, акторні моделі та ін. [8] говорячи про процесний паралелізм, ми маємо на увазі різні процесні моделі () ммування будуть просто втрачені. природно), в яких уточнюються основні поняття, пов'язані з породженням та взаємодією процесів.
Саме на основі цих моделей реалізовано багато мов процесів (наприклад, OCCAM), засоби ОС для організації "ниткових" процесів та ін.
Ще один важливий у практичному сенсі аспект у характеризації паралелізму – це обмеження на “зернистість”, для уточнення якої зазвичай використовують поняття: крупно – зернистий, середньо та дрібно – зернистий паралелізм (можлива і детальніша шкала диференціації).
Глибина розпаралелювання, яка обговорювалася у п. (1.2.1), уточнює це поняття. Зазвичай крупон – зернистий паралелізм пов'язують із модульним програмуванням, із розробкою складних програмних комплексів із різноманітними додатками, зокрема орієнтованими вирішення завдань обчислювального характеру. Дрібно – зернистий паралелізм – здатність функціональних та логічних програм.
Дрібно - зернистий паралелізм - особливість арифметичних та логічних функціональних програм, алгоритмів виведення в логіці та ін. ефективність реалізації паралельних обчислень на ЗС [1, 2].
Понад те, розв'язання завдання оптимального управління завантаженістю комп'ютерів (процесорів) ЗС потрібно вводити механізми динамічного виміру глибини розпаралелювання [1].
Наприклад, у реалізації мови функціонального програмування FTPL[5] на кластерах введеномеханізм управління глибиною розпаралелювання при виконанні програми шляхом віднесення рекурсивно певних функцій до складніших з обчислювальної точки зору фрагментів програми порівняно з базовими функціями.
Крім того, щоб програміст міг також варіювати "зернистість" паралелізму в програмі, в мовах функціонального та логічного програмування вводять засоби модульної організації програми, покажчики, які її фрагменти повинні виконуватися паралельно (див., наприклад, Т систему паралельного програмування [9])
Ще дві важливі властивості паралелізму – це його комутативність чи некомутативність [1]. Комутативність передбачає, що готові до виконання фрагментів паралельної програми можуть призначатися до виконання у довільному порядку, впливаючи результат. Для некомутативного паралелізму це не так.
Зрозуміло, що аргументи
Однак довільний порядок не гарантує отримання правильного результату. Наприклад, якщо значення
Важливе властивість паралелізму пов'язані з випереджальними обчисленнями. У загальному випадку безліч готових для виконання фрагментів паралельної програми можна розділити на два непересічні підмножини: підмножина фрагментів, про які відомо, що результати їхвиконання обов'язково потрібні, та підмножина фрагментів, виконання яких можна здійснювати з випередженням, не знаючи заздалегідь, будуть їх результати використані чи ні.
Типовий приклад - умовний оператор: if
Усі паралельні програми можуть бути віднесені до двох класів: з обмеженим та необмеженим паралелізмом [1, 2] (див. п. 1.2.1). Для програм першого класу заздалегідь можна вказати кількість (зазвичай найменше) комп'ютерів ВС, що достатньо реалізації всіх можливостей паралелізму в програмі при її виконанні для певної множини вихідних даних. Для паралельних програм, віднесених до класу програм, з необмеженим паралелізмом ця умова не виконується. Розглянуті у п. 1.2.1 приклади паралельного обчислення n!, паралельного перемноження матриць належать до класу паралельних програм з необмеженим паралелізмом, якщо не накладати жодних обмежень на n.
Для таких програм часто з практичної точки зору є завдання досягнення певного рівня розпаралелювання, а ефективна послідовна реалізація паралелізму на обмежених ресурсах ВС.
Слід зазначити, що програми на мові граф, що реалізується в даній роботі, – схемного потокового програмування, має властивість некомутативності, можливість завдання обчислень з випередженням і необмеженим паралелізмом, якщо не накладати обмеженьна глибину буферних зв'язків між модулями
Аналіз, що зачіпає організаційну специфіку паралелізму, як системи взаємодіючих процесів, виділяє синхронну та асинхронну його реалізацію. Перша, на відміну від другої, передбачає строгу специфікацію моментів часу (або подій), в які можуть відбуватися ті чи інші дії при виконанні паралельної програми. Типовий приклад, векторний оператор parbeginparend, що передбачає контроль його завершення після закінчення виконання оператора, що входить до нього, з максимальним часом виконання (або всіх таких операторів, якщо їх кілька).
Інша процесна характеризування паралелізму - це та, якою визначаться схема його реалізації як розподіленої в просторі системи процесів (те, що зазвичай називають розподіленою обробкою), або шляхом організації потокової обробки. У першому випадку паралелізм у [1] також названий просторовим. Схема потокової обробки має різні відтінки. Насамперед, це перенесення у сферу організації процесів обчислень давно застосовуваної на виробництві схемою конвеєрної обробки Відомо, що розбиваючи складний процес на окремі дрібні фази, що послідовно виконуються, і організуючи конвеєрну (потокову) обробку шляхом створення для реалізації кожної фази самостійного вузла (устрою, верстата і т.п. .п.) можна в граничному випадку в раз збільшити продуктивність такої схеми виконання "робіт", де k - число ступенів конвеєра. Понад те, ця схема дозволяє досягати показника найкращого показника використання ресурсів конвеєра. Справжнє своє втілення на комп'ютерному ґрунті конвеєр отримав у 60-х роках минулого століття у комп'ютерах СТРЕТЧ та БЕСМ-6, де одночасно оброблялося від 7 до 10 команд програми. Будь-який сучасний комп'ютер(персональний або супер – комп'ютер, наприклад Крей), окрім командного, реалізують скалярний та/або векторний конвеєри для виконання арифметичних операцій.
Однак ці конвеєри мають свої принципові обмеження. Так, в силу обставин, що склалися, виконання, наприклад, операції складання речових чисел складається всього з 5-ти фаз: порівняння порядків, зсув мантис, власне додавання, нормалізація і не може бути збільшено, щоб підвищити продуктивність. Крім того, конвеєрні схеми, що використовуються в комп'ютерах, як правило, лінійні (варто відзначити, що комп'ютери фірми Крей використовуються паралельно працюючі конвеєри, які можуть взаємодіяти один з одним, передаючи дані).
Реальні системи обробки інформації в загальному випадку багатопотокові, як правило, з чергами на входах їх вузлів і складними зв'язками, що визначають "напрямок" руху даних: один до багатьох, багато до одного вузла та ін.
Ця схема обробки даних все ширше використовується у паралельному програмуванні, описі розподілених систем та процесів [10].
У мові граф, що реалізується в роботі, – схемного потокового програмування [11] можлива побудова будь-яких схем потокової обробки (багатопотокових схем з чергами даних на входах модулів), причому через те, що модулі взаємодіють тільки за даними інформаційно – незалежні модулі легко виявляються за відсутністю зв'язків між ними.
Більш того, часто виникають завдання потокозалежної обробки, наприклад, обчислення
На закінчення параграфа зазначимо, що ця вищеХарактеристика різних сторін прояви паралелізму особливо важлива для практики при створенні мов паралельного програмування та їх реалізації на ЗС. З її урахуванням створювався мову граф – схемного паралельного потокового програмування і будувалися важливі рішення, у його реалізації на ЗС.