Вправи і завдання до теми №8

1. Сформулюйте характерні особливості моделі передачі повідомлень.

2. Чи допускає OpenMP зміну кількості паралельних ниток по ходу роботи програми?

3. Чи можна автоматично конвертувати DVM – програму в програму на OpenMP.

4. Спробуйте виділити найсильніші і найслабші боки кожної з технологій OpenMP і DVM.

Висновки

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

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

Оскільки даний напрямок досліджень постійно розвивається, автори в Додатках до даного навчального посібника навели Internet-ресурси звідки можна почерпнути багато нового в організації паралельної роботи та деякі теоретичні виклади, котрі, на жаль, не вдалося “втиснути” до навчального посібника.

 

Література

 

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.

2. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.

3. Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.

4. Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.

5. Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.

6. Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.

7. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999

8. С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных вычислительных систем. – СПб: БХВ-Петербург, 2002.

9. Pacheco P.Parallel Programming With MPI (див. www.parallel.ru).

10. Gropp W., Lusk E., Skjellum A. Using MPI (див. www.parallel.ru).

11. Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.

12. Internet-сайти

ДОДАТКИ

Додаток А

Ресурси Інтернет стосовно паралельних обчислень.

1. http://www.globus.org – Побудова метакомп’ютера.

2. http://www.gridforum.org– Побудова метакомп’ютера.

3. http://www.top500.org – Характеристики 500 найпотужніших комп’ютерів в світі.

4. http://www.mpiforum.org – Повний варіант описів стандартів МРІ.

5. http://www.keldysh.ru.norma – Опис системи програмування НОРМА.

6. http://www.citforum.ru – Сервер інформаційних технологій.

7. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.

8. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.

9. http://www.hpc.nw.ru – Високопродуктивні обчислення.

10. http://www.epm.ornl.gov/pvm/ - інформація про PVM.

11. http://www.beowulf.org – Інформація про кластери.

 

Додаток Б

 

КОНЦЕПЦІЇ ПАРАЛЕЛЬНОЇ ОБРОБКИ

Співпрограми

Використовуючи співпрограми (coroutine, рис. Б.1), говорять про концепцію обмеженої паралельної обробки інформації. В основу цієї обробки покладено однопроцесорну модель, де є тільки один потік інструкцій з послідовно виконуваним керуючим потоком, що передбачає організоване заняття та звільнення операційного ресурсу "процесор" співпрограмою.

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

У зв'язку з тим, що ця концепція будується на одному єдиному процесорі, вона не потребує відповідних управлінських витрат на мультизадачність. Однак тут не відбувається справжньої паралельної обробки!

Fork (розгалуження, виникнення паралельних процесів) i Join (об’єднання)

Конструкції fork i j oin ( які в операційній системі Unix відомі як fork i wait) належать до найперших паралельних мовних конструкцій (рис.Б.2).

В операційній системі Unix є можливість запускати паралельні процеси за допомогою операції fork, а закінчення їх чекати операцією wait. На відміну від співпрограм мова йде про приклад істинно паралельних процесів, що можуть за браком паралельних апаратних pecypciв оброблятись на одному процесорі в мультизадачному режимі з дискретним розподілом часу. У цьому способі паралельного програмування об’єднано дві принципово різні концепції: декларування паралельних процесів i синхронізація npoцeciв. Оскільки йдеться про концептуально різні задачі, було б доцільніше, з огляду на основи програмної інженерії, щоб вони були чітко розділені в мові програмування введенням різних мовних конструктивів.

У системі Unix виклик операції fork функціонує не так наочно, як показано на рис. Б.2. Замість цього виготовляється ідентична копія процесу, що викликається, i вона виконується паралельно йому. Змінні величини та стартова величина програмного лічильника нового процесу такі самі, як у вихідному npoцeci. Єдина можливість відрізнити ці процеси (які з них - процеси-батьки, а які – процесори - діти), полягає в тому, що fork операція видає ідентифікаційний номер, який треба оцінити. Його величина для процесів-дітей дорівнює нулю, а у процесів-батьків він збігається з ідентифікаційним номером процесів в ОС Unix (число, що завжди відрізняється від нуля). Такий cпociб організації процесів не відповідає проблематиці програмування, що ставить за мету побудову зрозумілих, зручних для читання та перегляду програм.

Щоб все ж таки запустити іншу програму i чекати на її закінчення, можна обидві системні Unix-процедури виклику сконструювати мовою програмування С таким чином:

int status;

if (fork()==0) execlp("program_B",...); /* процес-дитя */

…

wait (&status); /* процес-дитя */

Виклик операції fork видає для батьківського процесу номер процесу-дитини як зворотній зв'язок (тут fork() не є нулем), у той час як для процесу-дитини видається величина нуль; тим самим гарантується, що процес-дитина звичайно виконує нову програму операцією execlp i це не є текстом батьківського коду. Одночасно батьківський процес виконує наступні інструкції паралельно процесу-дитині. Батьківський процес може чекати закінчення процесу-дитини операцією wait; параметр зворотного зв'язку містить статус закінчення процесу-дитини.

ParBegin та ParEnd

За аналогією з відомими ключовими словами begin та end, що відокремлюють послідовні блоки інструкцій, словами parbegin та parend визначаються паралельні блоки, в яких інструкції мають виконуватись паралельно (рис. Б.3).

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

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

Процеси

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

Монітор (рис.Б.4) - єдине ціле із загальних даних, операцій доступу i списку черг чекання. Тільки один процес з багатьох може в деякий момент часу ввійти в монітор, чим з самого початку виключається багато проблем синхронізації. Блокування та розблокування процесів всередині монітора проводиться за умовними списками черг.

Однак явна синхронізація паралельних процесів дає не тільки додатковий обсяг роботи щодо керування, а й постійний острах до помилок. Цей спосіб організації паралельних обчислень потребує виняткової уваги під час програмування. Якщо різні процеси мають звертатися до одних i тих самих даних, то ці так звані "критичні розділи" треба захистити за допомогою синхронізаційних конструкцій. Це означає, що в кожний момент часу до цього розділу має право звернутися лише один процес і працювати з загальними даними. Найпоширенішими помилками є неконтрольований доступ до критичного розділу або вихід з нього (програміст забув про операції синхронізації) та помилкове керування процесами, що чекають, тобто блокованими. Ці помилки призводять передусім до виникнення неправильних даних, а кpiм цього, можуть спричинити блокування окремих процесів або навіть всієї системи процесів.

Обмін інформацією та синхронізація виконуються в системах з загальною пам'яттю (“тісно зв'язані” системи) через монітори з умовами. В системах без загальної пам'яті (“слабко зв’язані” системи) потрібна концепція передачі та прийому повідомлень, яка наведена нижче.

Дистанційний виклик

Щоб поширити концепцію процесів на паралельні процесори без загальної пам'яті, потрібно реалізувати спілкування процесів на різних процесорах через обмін повідомленнями. Концепція повідомлень може бути імплементована i на MIMD-структуру із загальною пам'яттю (але з більшими витратами на керування).

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

Цей cnoci6 паралельного розподілення робіт імплементується механізмом дистанційного виклику ("remote procedure call", RPC, рис.Б.5).

Здатність до обробки інформації суттєво зростає, якщо клієнт не чекає на результати сервера під час кожного звертання до нього, а паралельно йому може вести подальші розрахунки на своєму процесорі. Однак з цієї вимоги кращого завантаження апаратури та її більшої ефективності виникають i нові проблеми: параметри зворотного зв'язку недоступні негайно після виконання сервер-операції, оскільки вони більше відповідають операції типу "віддача замовлення". Результати, на які чекає клієнт, в цьому випадку після обчислень у сервері мають бути переслані у зворотному напрямку від сервера до клієнта у вигляді явного обміну даними. Труднощі в RPC- методі викликає також виготовлення безпомилкових протоколів вводу в дію i повторного пропуску задач виходу сервера з ладу.

Неявна паралельність

Уci представлені концепції паралельності застосовують спеціальні, явні мовні конструктиви для керування паралельною обробкою інформації. Суттєво елегантнішими є мови програмування, які виходять з того, щоб робити можливою паралельну обробку, не застосовуючи мовних конструктивів для обслуговування паралельності. Подібні мови програмування називають мовами з неявною паралельністю. Проте під час роботи на цих мовах програміст має мало засобів впливу на застосування паралельних процесорів для вирішення його проблеми. Тут має бути впевненість, що у програміста наявна достатня кількість процедуральної інформації ("знань"), щоб зробити можливим ефективне розпаралелювання. Подібне завдання може вирішувати, наприклад, "інтелектуальний компілятор" без спілкування з nporpaмicтом. Ця проблема стає зрозумілою передусім в декларативних мовах програмування, таких як Lisp (функціонально) або Prolog (логічно). Через декларативне представлення знань, принаймні постановки задачі (наприклад, складна математична формула), розв'язок її визначається в основному однозначно. Однак суттєві труднощі виникають при спробах перевести ці знання в командний паралельний програмний процес, тобто скласти програму для обчислень за формулою i проблему розчленити на задачі-частки, які б могли розв'язуватися паралельно.

Неявна паралельність може бути безпосередньо виділена із векторних конструкцій мов програмування, наприклад FP або APL. В APL немає жодної контрольної структури високого рівня, яка безумовно потрібна в будь-якій (послідовній чи паралельній) мові програмування.

Як показано на рис.Б.6, математичний запис додавання матриць містить у co6i неявну паралельність, яка в цьому випадку досить просто може бути перетворена на деяку паралельну обчислювальну структуру методом автоматичного розпаралелювання (наприклад, паралельність на piвнi виразів).

 

Неявна паралельність розвантажує програміста, бо він не повинен займатися задачами керування та контролю. Програмування відбувається на високому piвнi абстракцій, тому неявна паралельність часто має місце в непроцедурних мовах програмування високого рівня. На протилежність цьому явна паралельність дає програмісту суттєво більшу свободу дій, щоб досягти вищої обчислювальної продуктивності від правильного завантаження процесорів. Ця перевага пов'язана iз складнішим програмуванням, якому притаманна більша вірогідність помилок.

Додаток В