Транскрипт

1 Частина 3. Методи паралельних обчислень 6. Принципи розробки паралельних методів 6. Принципи розробки паралельних методів Моделювання паралельних програм Етапи розробки паралельних алгоритмів Поділ обчислень на незалежні частини Виділення інформаційних залежностей Розподіл незалежні частини Виділення інформаційних залежностей Масштабування та розподіл підзадач по процесорах Аналіз ефективності паралельних обчислень Короткий оглядРозділу Огляд літератури Контрольні питання Завдання та вправи Розробка алгоритмів (а особливо методів паралельних обчислень) для вирішення складних науково-технічних завдань часто є значною проблемою. Для зниження складності теми, що розглядається, залишимо осторонь математичні аспекти розробки та доказу збіжності алгоритмів ці питання тією чи іншою мірою вивчаються в ряді "класичних" математичних навчальних курсів. Тут же ми будемо вважати, що обчислювальні схеми вирішення завдань, що розглядаються далі як приклади, вже відомі 1). З урахуванням висловлених припущень наступні дії для визначення ефективних способів організації паралельних обчислень можуть полягати в наступному: Виконати аналіз наявних обчислювальних схем та здійснити їх поділ (декомпозицію) на частини (підзавдання), які можуть бути реалізовані значною мірою незалежно один від одного, сформованого набору підзадач інформаційні взаємодії, які повинні здійснюватися в ході вирішення вихідної поставленої задачі, Визначити необхідну (або доступну) для розв'язання задачі обчислювальну систему та виконати розподіл набору підзадач між процесорами системи. При найзагальнішому розгляді зрозуміло, що обсяг обчислень для кожного використовуваного процесора повинен бути приблизно однаковий, це дозволить забезпечити рівномірне обчислювальне завантаження (балансування) процесорів. Крім того, також зрозуміло, що розподіл підзадач між процесорами має бути виконано таким чином, щоб наявність інформаційних зв'язків(комунікаційних взаємодій) між підзавданнями було мінімальним. 1) Незважаючи на те, що для багатьох науково-технічних завдань насправді відомі не тільки послідовні, а й паралельні методи вирішення, дане припущення є, звичайно, дуже сильним, оскільки для нових завдань, що вимагають для свого вирішення великого обсягу обчислень, процес розробки алгоритмів становить істотну частину всіх виконуваних робіт.

2 Поділ обчислень на незалежні частини Виділення інформаційних залежностей Масштабування підзадач Розподіл підзадач між процесорами Рис Загальна схема розробки паралельних алгоритмів Після виконання всіх перерахованих етапів проектування можна оцінити ефективність паралельних методів, що розробляються, для цього зазвичай визначаються значення показників якості порождаемих, . За результатами проведеного аналізу може бути необхідним повторення окремих (у разі) етапів розробки слід зазначити, що до попередніх кроків розробки може відбуватися будь-який стадії проектування паралельних обчислювальних схем. У цьому відношенні часто виконуваним додатковим дією в наведеній вище схемі проектування є коригування складу сформованого безлічі завдань після визначення наявної кількості процесорів підзавдання можуть бути укрупнені (агреговані) за наявності малої кількості процесорів або, навпаки, деталізовані в іншому випадку. В цілому, дані дії можуть бути визначені як масштабування алгоритму, що розробляється, і виділені в якості окремого етапу проектування паралельних обчислень. Для застосування одержуваного в кінцевому підсумку паралельного методу необхідно виконати розробку програм для вирішення сформованого набору підзадач і розмістити розроблені програми процесорів відповідно до обраної схеми розподілу підзадач. Для проведення обчислень програми запускаються на виконання (програми на стадії виконання зазвичай називаються процесами), для реалізації інформаційних взаємодій програми повинні мати у своєму розпорядженні засоби обміну даними (канали передачі повідомлень). Слід зазначити, що кожен процесор зазвичай виділяється для вирішення однієї єдиної підзавдання, однак за наявності великої кількості підзадач або використання обмеженої кількості процесорів це правило може не дотримуватися і, в результаті, на процесорах може виконувати одночасно кілька програм (процесів). Зокрема, при розробці та початковій перевірці паралельної програми для виконання всіх процесів може використовуватися один процесор (при розташуванні на одному процесорі процеси виконуються в режимі розподілу часу). Розглянувши уважно розроблену схему проектування та реалізації паралельних обчислень, можна відзначити, що цей підхід значною мірою орієнтований на обчислювальні системи з розподіленою пам'яттю, коли необхідні інформаційні взаємодії реалізуються за допомогою передачі повідомлень каналами зв'язку між процесорами. Проте, дана схемаможе бути використана без втрати будь-якої ефективності паралельних обчислень і для розробки паралельних методів для систем із загальною пам'яттю у цьому випадку механізми передачі повідомлень для забезпечення інформаційних взаємодій повинні бути замінені операціями доступу до загальних (розділених) змінних Моделювання паралельних програм Розглянута схема проектування та реалізації паралельних обчислень дає спосіб розуміння паралельних алгоритмів та програм. На стадії проектування паралельний метод може бути представлений у вигляді графа "підзавдання повідомлення", який є не що інше, як укрупнене (агреговане) подання графа інформаційних залежностей (графа "операції-операнди" див. розділ 2). Аналогічно на стадії виконання для опису паралельної програми може бути використана модель у вигляді графа "процеси канали", в якій замість підзадач використовується поняття процесів, а інформаційні залежності замінюються каналами 2

3 передачі повідомлень. На додаток, на цій моделі може бути показано розподіл процесів по процесорах обчислювальної системи, якщо кількість підзадач перевищує число процесорів див. рис процес - канал - операції прийому (передачі) - вхідні (вихідні) канали для взаємодії процесів "процеси-канали" Використання двох моделей паралельних обчислень 2) дозволяє краще розділити проблеми, що виявляються розробки паралельних методів. Перша модель граф "підзавдання - повідомлення" дозволяє зосередитись на питаннях виділення підзавдань однакової обчислювальної складності, забезпечуючи при цьому низький рівень інформаційної залежності між підзадачами. Друга модель граф "процеси канали" концентрує увагу на питаннях розподілу підзадач по процесорах, забезпечуючи ще одну можливість зниження трудомісткості інформаційних взаємодій між підзадачами за рахунок розміщення на тих самих процесорах інтенсивно взаємодіючих процесів. Крім того, ця модель дозволяє краще аналізувати ефективність розробленого паралельного методу та забезпечує можливість більш адекватного опису процесу виконання паралельних обчислень. Даємо додаткові пояснення для понять, що використовуються в моделі "процеси-канали": Під процесом у рамках даного навчального матеріалу будемо розуміти виконувану на процесорі програму, яка використовує для своєї роботи частину локальної пам'яті процесора і яка містить ряд операцій прийому/передачі даних для організації інформаційної взаємодії між виконуваними процесами паралельної програми, Канал передачі даних з логічної точки зору може розглядатися як черга повідомлень, в яку один або кілька процесів можуть відправляти дані, що пересилаються, і з якої процес-адресат може витягувати повідомлення, що відправляються іншими процесами. У випадку, можна вважати, що канали виникають динамічно в момент виконання першої операції прийому/передачі з каналом. За ступенем спільності канал може відповідати одній або кільком командам прийому даних процесу-отримувача; аналогічно під час передачі повідомлень канал може використовуватися однією чи кількома командами передачі даних однієї чи кількох процесів. Для зниження складності моделювання та аналізу паралельних методів припускатимемо, що ємність каналів є необмеженою і, як результат, операції передачі даних виконуються практично без затримок простим копіюванням повідомлень у канал. З іншого боку, операції прийому повідомлень можуть призводити до затримок (блокувань), якщо дані з каналу дані ще не були відправлені процесами-джерелами повідомлень. Слід зазначити важливу перевагу розглянутої моделі "процеси-канали" у цій моделі проводиться чіткий поділ локальних (виконуваних на окремому процесорі) обчислень і 2) У Foster (1995) розглядається лише одна модель модель "завдання-канал" для опису паралельних обчислень, яка займає деяке проміжне положення порівняно з викладеними тут моделями. Так, у моделі "завдання канал" не враховується можливість використання одного процесора для вирішення кількох підзадач одночасно. 3

4 дій щодо організації інформаційної взаємодії одночасно виконуваних процесів. Такий підхід значно знижує складність аналізу ефективності паралельних методів та суттєво спрощує проблеми розробки паралельних програм Етапи розробки паралельних алгоритмів Розглянемо докладніше викладену вище методику розробки паралельних алгоритмів. Значною мірою дана методика спирається на підхід, вперше розглянутий у Foster (1995), і, як зазначалося раніше, включає етапи виділення підзавдань, визначення інформаційних залежностей, масштабування та розподілу підзавдань процесорами обчислювальної системи (див. рис. 6.1). Для демонстрації рекомендацій, що наводяться, далі буде використовуватися навчальна задача пошуку максимального значення серед елементів матриці A (така задача виникає, наприклад, при чисельному розв'язанні систем лінійних рівнянь для визначення провідного елемента методу Гауса): y = max a. 1 i, j N i j Таке завдання носить повністю ілюстративний характер, і після розгляду етапів розробки в частині розділу, що залишилася, буде наведено більше повний прикладвикористання даної методики розробки паралельних алгоритмів. Крім того, дана схема розробки буде застосована і при викладі всіх далі аналізованих методів паралельних обчислень. Вимоги, яким повинен задовольняти обраний підхід, зазвичай полягають у забезпеченні рівного обсягу обчислень у підзавданнях, що виділяються, і мінімуму інформаційних залежностей між цими підзадачами (за інших рівних умов потрібно віддавати перевагу рідкісним операціям передачі більшого розміру повідомлень порівняно з частими пересиланнями даних невеликого обсягу). У загальному випадку, проведення аналізу та виділення задач є досить складною проблемою ситуацію допомагає вирішити існування двох типів обчислювальних схем, що часто зустрічаються: а) б) Рис Поділ даних для матриці A: а) стрічкова схема, б) блочна схема Для великого класу задач обчислення зводяться до виконання однотипної обробки елемент елементів великого набору даних до такого виду завдань відносяться, наприклад, матричні обчислення, чисельні методи розв'язання рівнянь у приватних похідних та ін. . Так, наприклад, для нашої навчальної задачі пошуку максимального значення при формуванні підзадач вихідна матриця A може бути розділена на окремі рядки (або послідовні групи рядків) стрічкова схема поділу даних (див. рис. 6.3) або прямокутні набори елементів блокова схема поділу даних. Для великої кількості розв'язуваних завдань поділ обчислень за даними призводить до породження одно-, дво- та тривимірних наборів підзадач, для яких інформаційні зв'язки існують лише між найближчими сусідами (такі схеми зазвичай називаються сітками або ґратами), 4

5 Рис Регулярні одно-, дво- та тривимірні структури базових підзадач після декомпозиції даних Для іншої частини завдань обчислення можуть полягати у виконанні різних операцій над одним і тим же набором даних у цьому випадку говорять про існування функціонального паралелізму (як приклади можна навести завдання обробки послідовності запитів до інформаційним базам даних, обчислення з одночасним застосуванням різних алгоритмів розрахунку тощо). Дуже часто функціональна декомпозиція може бути використана для організації конвеєрної обробки даних (наприклад, при виконанні будь-яких перетворень даних обчислення можуть бути зведені до функціональної послідовності введення, обробки та збереження даних). Важливе питання виділенні подзадач полягає у виборі необхідного рівня декомпозиції обчислень. Формування максимально можливої ​​кількості підзадач забезпечує використання гранично досяжного рівня паралелізму розв'язуваного завдання, проте ускладнює аналіз паралельних обчислень. Використання при декомпозиції обчислень лише досить "великих" підзавдач призводить до ясної схеми паралельних обчислень, проте може утруднити ефективне використання досить великої кількості процесорів. Можливе розумне поєднання цих двох підходів може полягати у використанні як конструктивних елементів декомпозиції лише тих підзадач, котрим методи паралельних обчислень є відомими. Так, наприклад, при аналізі завдання матричного множення як підзавдання можна використовувати методи скалярного твору векторів або алгоритми матрично-векторного твору. Подібний проміжний спосіб декомпозиції обчислень дозволить забезпечити простоту подання обчислювальних схем, і ефективність паралельних розрахунків. Обираемые подзадачи у разі підході будемо називати далі базовими, які можуть бути елементарними (неподільними), а то й допускають подальшого поділу, чи складовими інакше. Для аналізованої навчальної задачі достатній рівень декомпозиції може полягати, наприклад, у поділі матриці A на безліч окремих рядків та одержанні на цій основі набору підзавдань пошуку максимальних значень в окремих рядках; Для оцінки коректності етапу поділу обчислень на незалежні частини можна скористатися контрольним списком питань, запропонованих у Foster (1995): Виконана декомпозиція не збільшує обсяг обчислень і необхідний обсяг пам'яті? Чи можливе при вибраному способі декомпозиції рівномірне завантаження всіх наявних процесорів? Чи достатньо виділених частин процесу обчислень для ефективного завантаження наявних процесорів (з урахуванням можливості збільшення їхньої кількості)? Виділення інформаційних залежностей За наявності обчислювальної схеми розв'язання задачі після виділення базових підзавдань визначення інформаційних залежностей між підзадачами зазвичай не викликає великих труднощів. При цьому, однак, слід зазначити, що насправді етапи виділення підзавдань та інформаційних залежностей досить складно піддаються розподілу. Виділення підзавдань має відбуватися з урахуванням інформаційних зв'язків, що виникають; після аналізу обсягу та частоти необхідних інформаційних обмінів між підзадачами може знадобитися повторення етапу поділу обчислень. При проведенні аналізу інформаційних залежностей між підзадачами слід розрізняти (переважні форми інформаційної взаємодії виділені підкресленням): Локальні та глобальні схеми передачі даних для локальних схем передачі даних у кожний момент часу виконуються тільки між невеликим числом підзадач (розташованих як 5

6 правило, на сусідніх процесорах), для глобальних операцій передачі даних у процесі комунікації беруть участь усі підзадачі, Структурні та довільні способи взаємодії для структурних способів організація взаємодій призводить до формування деяких стандартних схем комунікації (наприклад, у вигляді кільця, прямокутної решітки і т.п. д.), для довільних структур взаємодії схема виконуваних операцій передач даних не носить характер однорідності, Статичні або динамічні схеми передачі даних для статичних схем моменти та учасники інформаційної взаємодії фіксуються на етапах проектування та розробки паралельних програм, для динамічного варіанту взаємодії структура операції передачі даних визначається в ході обчислень, Синхронні та асинхронні способи взаємодії для синхронних способів операції передачі даних виконуються тільки при готовності всіх учасників взаємодії і завершуються тільки після повного закінчення всі х комунікаційних процесів, при асинхронному виконанні операцій учасники взаємодії можуть чекати повного завершення процесів передачі даних. Для представлених способів взаємодії досить складно виділити кращі форми організації передачі даних: синхронний варіант, як правило, більш простий для використання, тоді як асинхронний спосіб часто дозволяє суттєво знизити тимчасові затримки, спричинені операціями інформаційної взаємодії. Як уже зазначалося в попередньому пункті, для навчальної задачі пошуку максимального значення при використанні як базових елементівпідзадач пошуку максимальних значень в окремих рядках вихідної матриці A структура інформаційних зв'язків має вигляд, представлений на рис. Чи обчислювальна складність підзавдань інтенсивності їх інформаційних взаємодій? Чи однакова інтенсивність інформаційних взаємодій для різних підзадач є однаковою? Чи є схема інформаційної взаємодії локальною? Чи не перешкоджає виявлена ​​інформаційна залежність паралельному рішенню підзавдань? Масштабування набору підзадач Масштабування розробленої обчислювальної схеми паралельних обчислень проводиться у разі, якщо кількість наявних підзадач відрізняється від кількості процесорів, що плануються до використання. Для скорочення кількості підзавдань необхідно виконати укрупнення (агрегацію) обчислень. Правила, що застосовуються тут, збігаються з рекомендаціями початкового етапу виділення підзадач, що визначаються підзадачі, як і раніше, повинні мати однакову обчислювальну складність, а обсяг і інтенсивність інформаційних взаємодій між підзадачами повинні залишатися на мінімально-можливому рівні. Як результат, першими претендентами на об'єднання є підзавдання з високим ступенемінформаційної взаємозалежності При недостатній кількості наявного набору підзадач для завантаження всіх доступних для використання процесорів необхідно виконати деталізацію (декомпозицію) обчислень. Як 6

7 правило, проведення подібної декомпозиції не викликає будь-яких труднощів, якщо для базових завдань методи паралельних обчислень є відомими. Виконання етапу масштабування обчислень має звестися, зрештою, до розробки правил агрегації та декомпозиції підзавдань, які мають параметрично залежати від кількості процесорів, які застосовуються для обчислень. Для навчальної задачі пошуку максимального значення агрегація обчислень може полягати в об'єднанні окремих рядків у групи (стрічкова схема поділу матриці див. рис. 6.3а), при декомпозиції підзадач рядка вихідної матриці A можуть розбиватися на кілька частин (блоків). Список контрольних питань, запропонований у Foster (1995) з метою оцінки правильності етапу масштабування, виглядає так: Чи не погіршиться локальність обчислень після масштабування наявного набору подзадач? Чи мають підзавдання після масштабування однакову обчислювальну та комунікаційну складність? Чи відповідає кількість завдань кількості наявних процесорів? Чи залежать параметрично правила масштабування кількості процесорів? Розподіл підзадач між процесорами Розподіл підзадач між процесорами є завершальним етапом розробки паралельного методу. Слід зазначити, що управління розподілом навантаження для процесорів можливе лише обчислювальних систем з розподіленою пам'яттю, для мультипроцесорів (систем із загальною пам'яттю) розподіл навантаження зазвичай виконується операційною системою автоматично. Крім того, даний етап розподілу підзадач між процесорами є надлишковим, якщо кількість підзадач збігається з числом наявних процесорів, а топологія мережі передачі даних обчислювальної системи є повним графом (тобто всі процесори пов'язані між собою прямими лініями зв'язку). Основний показник успішності виконання даного етапуефективність використання процесорів, яка визначається як відносна частка часу, протягом якого процесори використовувалися для обчислень, пов'язаних з вирішенням вихідної задачі. Шляхи досягнення хороших результатів у цьому напрямі залишаються такими, як і раніше, необхідно забезпечити рівномірний розподіл обчислювального навантаження між процесорами і мінімізувати кількість повідомлень, що передаються між процесорами. Так само, як і на попередніх етапах проектування, оптимальне вирішення проблеми розподілу підзадач між процесорами ґрунтується на аналізі інформаційної зв'язності графа "підзавдання - повідомлення". Так, зокрема, підзавдання, між якими є інформаційні взаємодії, доцільно розміщувати процесорах, між якими існують прямі лінії передачі даних. Слід зазначити, вимога мінімізації інформаційних обмінів між процесорами може суперечити умові рівномірної завантаження процесів. Так, ми можемо розмістити всі підзавдання на одному процесорі та повністю усунути міжпроцесорну передачу повідомлень, проте, зрозуміло, завантаження більшості процесорів у цьому випадку буде мінімальним. Для нашої навчальної завдання пошуку максимального значення розподіл підзадач між процесорами не викликає будь-яких труднощів достатньо забезпечити розміщення підзадач, між якими є інформаційні зв'язки, на процесорах, для яких існують прямі канали передачі даних. Оскільки структура інформаційного зв'язку навчального завдання має вигляд лінійного графа, виконання цієї вимогиможе бути забезпечено практично за будь-якої топології мережі обчислювальної системи. Вирішення питань балансування обчислювального навантаження значно ускладнюється, якщо схема обчислень може змінюватися під час вирішення завдання. Причиною цього можуть бути, наприклад, неоднорідні сітки при вирішенні рівнянь у похідних приватних, розрідженість матриць і т.п. 3). Крім того, використовуються на етапах проектування оцінки обчислювальної складності рішення підзавдань можуть мати наближений характер і, нарешті, кількість підзавдач може змінюватися під час обчислень. У таких ситуаціях може знадобитися перерозподіл базових підзадач між 3) Можна відзначити, що навіть для нашого простого навчального завдання може спостерігатися різна обчислювальна складність сформованих базових завдань. Так, наприклад, кількість операцій при пошуку максимального значення для рядка, в якому максимальне значення має перший елемент, і рядки, в якій значення є впорядкованими за зростанням, буде різнитися вдвічі. 7

8 процесорами вже безпосередньо в процесі виконання паралельної програми (або, як завжди кажуть, доведеться виконати динамічне балансування обчислювального навантаження). Дані питання є одними з найскладніших (і найцікавіших) в галузі паралельних обчислень, на жаль, розгляд даних питань виходить за рамки даного навчального матеріалу. додаткова інформаціяможе бути отримана, наприклад, Buyya (1999) і Wilkinson and Allen (1999)). Як приклад дамо коротку характеристику широко використовуваного способу динамічного управління розподілом обчислювального навантаження, що зазвичай називається схемою "менеджер - виконавець" (manager-worker scheme). При використанні даного підходу передбачається, що підзавдання можуть виникати і завершуватися в ході обчислень, при цьому інформаційні взаємодії між підзавдання або повністю відсутній, або мінімальні. Відповідно до схеми, що розглядається, для управління розподілом навантаження в системі виділяється окремий процесор-менеджер, якому доступна інформація про всі наявні підзавдання. Інші процесори системи є виконавцями, які для отримання обчислювального навантаження звертаються до процесора-менеджера. Нові підзавдання, що породжуються в ході обчислень, передаються назад процесору-менеджеру і можуть бути отримані для вирішення при наступних зверненнях процесорів-виконавців. Завершення обчислень відбувається у момент, коли процесори-виконавці завершили рішення всіх переданих їм підзадач, а процесор-менеджер немає жодних обчислювальних робіт до виконання. Запропонований у Foster (1995) перелік контрольних питань для перевірки етапу розподілу підзавдання полягає в наступному: Чи не призводить розподіл кількох завдань на один процесор до зростання додаткових обчислювальних витрат? Чи існує необхідність динамічного балансування обчислень? Чи не є процесор-менеджер вузьким місцем при використанні схеми менеджер менеджер? 6.3. Паралельне рішення гравітаційної задачі N тел Багато обчислювальних завдань у галузі фізики зводяться до операцій обробки даних кожної пари об'єктів наявної фізичної системи. Таким завданням є, зокрема, проблема, широко відома в літературі як гравітаційна задача N тіл (або просто завдання N тіл) див., наприклад, Andrews (2000) загальному вигляді, Завдання може бути описано наступним чином. Нехай дано велику кількість тіл (планет, зірок і т.д.), для кожного з яких відома маса, початкове положеннята швидкість. Під дією гравітації положення тіл змінюється, і необхідне рішення задачі полягає в моделюванні динаміки зміни системи N тіл протягом деякого інтервалу часу, що задається. Для проведення такого моделювання заданий інтервал часу зазвичай розбивається на тимчасові відрізки невеликої тривалості і на кожному кроці моделювання обчислюються сили, що діють на кожне тіло, а потім оновлюються швидкості і положення тіл. Очевидний алгоритм розв'язання задачі N тіл полягає у розгляді на кожному кроці моделювання всіх пар об'єктів фізичної системи та виконанні для кожної пари, що отримується, усіх необхідних розрахунків. Як результат, при такому підході час виконання однієї ітерації моделювання становитиме 4) T = N (N 1) / 2, 1 де є час перерахування параметрів однієї пари тіл. Як випливає з наведеного опису, обчислювальна схема розглянутого алгоритму є порівняно простою, що дозволяє використовувати завдання N тіл як ще одну наочну демонстрацію застосування методики розробки паралельних алгоритмів. 4) Слід зазначити, що для розв'язання задачі N тіл існує і більш ефективні послідовні алгоритми, проте їх вивчення може вимагати чималих зусиль. З урахуванням даної обставини для подальшого розгляду вибирається саме цей "очевидний" (але не найшвидший) метод, хоча, загалом, безумовно, для розпаралелювання слід вибирати найкращі схеми виконання розрахунків. 8

9 Поділ обчислень на незалежні частини Вибір способу поділу обчислень не викликає будь-яких труднощів - очевидний підхід полягає у виборі як базове підзавдання всього набору обчислень, пов'язаних з обробкою даних одного будь-якого тіла фізичної системи Виділення інформаційних залежностей Виконання обчислень, пов'язаних з кожною підзавданням, стає можливим тільки у випадку, коли в підзавданнях є дані (положення та швидкості пересування) про всі тіла наявної фізичної системи. Як результат, перед початком кожної ітерації моделювання кожна підзавдання має отримати всі необхідні відомості від інших підзадач системи. Така процедура передачі, як у розділі 3, називається операцією збору даних (single-node gather). У аналізованому алгоритмі дана операція має бути виконана кожної подзадачи такий варіант передачі зазвичай іменується як операція узагальненого збору даних (multi-node gather or all gather). Визначення вимог до необхідних результатів інформаційного обміну не призводить до однозначного встановлення потрібного інформаційного обміну між підзавданнями. Найбільш простий спосіб виконання необхідного інформаційного обміну полягає в реалізації послідовності кроків, на кожному з яких всі наявні підзавдання розбиваються попарно і обмін даними здійснюється між підзадачами пар, що утворилися. При належній організації попарного поділу підзадач (N-1) кратне повторення описаних дій призведе до повної реалізації необхідної операції збору даних. Розглянутий вище метод організації інформаційного обміну є досить трудомістким для збору всіх необхідних даних (N-1) ітерацій, на кожній з яких виконується одночасно (N/2) операцій передачі даних. Для скорочення необхідної кількості ітерацій можна звернути увагу на факт, що після виконання першого кроку операції збору даних підзавдання будуть містити не тільки свої дані, а й дані підзавдань, з якими вони утворювали пари. Як результат, на другій ітерації збору даних можна буде утворювати пари підзадач для обміну даними відразу про два тіла фізичної системи тим самим, після завершення другої ітерації кожна підзавдання міститиме відомості про чотири тіла системи і т.д. Як можна помітити, даний спосібРеалізація обмінів дозволяє завершити необхідну процедуру за log 2 N ітерацій. Слід зазначити, що при цьому обсяг даних, що пересилаються, в кожній операції обміну подвоюється від ітерації до ітерації на першій ітерації між підзадачами пересилаються дані про одне тіло системи, на другий ітерації про два тіла і т.д. Використання розглянутого способу реалізації операції узагальненого збору даних призводить до визначення структури інформаційних зв'язків між підзадачами у вигляді N-мірного гіперкуба Масштабування та розподіл підзадач по процесорах Як правило, число тіл фізичної системи N значно перевищує кількість процесорів p. Як результат, розглянуті раніше підзавдання слід укрупнити, об'єднавши в рамках однієї підзадачі обчислення групи (N/p) тел. Після проведення подібної агрегації число підзадач і кількість процесорів буде збігатися, і при розподілі підзадач між процесорами залишиться лише забезпечити наявність прямих комунікаційних ліній між процесорами з підзадачами, між якими є інформаційні обміни при виконанні операції збору даних Аналіз ефективності паралельних обчислень на вирішення завдання N тел. Оскільки запропоновані варіанти відрізняються лише методами виконання інформаційних обмінів, порівняння підходів досить визначити тривалість операції узагальненого збору даних. Використовуємо для оцінки часу передачі повідомлень модель, запропоновану Хокні (див. розділ 3), тоді тривалість виконання операції збору даних для першого варіанта паралельних обчислень може бути виражена як 1 T p (comm) = (p 1) (α + m (N / p) / β), де α, β є параметри моделі Хокні (латентність і пропускна здатність мережі передачі даних), а m задає обсяг даних, що пересилаються, для одного тіла фізичної системи. 9

10 Для другого способу інформаційного обміну, як уже зазначалося раніше, обсяг даних, що пересилаються, на різних ітераціях операції збору даних різниться. На першій ітерації обсяг повідомлень, що пересилаються, становить (mn/p), на другій ітерації цей обсяг збільшується вдвічі і виявляється рівним 2(mN/p) і т.д. У загальному випадку для ітерації з номером i обсяг повідомлень оцінюється як 2 i-1 (mn/p). Як результат, тривалість виконання операції збору даних у цьому випадку може бути визначена за допомогою наступного виразу T 2 p log p i = 1 i 1 (comm) = (α + 2 m (N / p) / β) = α log p + m (N/p)(p 1) / β. Порівняння отриманих виразів показує, що другий розроблений спосіб паралельних обчислень має істотно більш високу ефективність, несе менші комунікаційні витрати і допускає кращу масштабованість при збільшенні кількості використовуваних процесорів. Дана методика включає етапи виділення підзавдань, визначення інформаційних залежностей, масштабування та розподілу підзавдань по процесорах обчислювальної системи. При застосуванні методики передбачається, що обчислювальна схема вирішення завдання, що розглядається, вже є відомою. Основні вимоги, які мають бути забезпечені при розробці паралельних алгоритмів, полягають у забезпеченні рівномірного завантаження процесорів при низькій інформаційній взаємодії сформованої множини підзадач. Для опису одержуваних у процесі розробки обчислювальних паралельних схем розглянуто дві моделі. Перша з них модель "підзавдання-повідомлення" може бути використана на стадії проектування паралельних алгоритмів, друга модель "процеси-канали" може бути застосована на стадії реалізації методів у вигляді паралельних програм. На завершення розділу показується застосування розглянутої методики розробки паралельних алгоритмів з прикладу розв'язання гравітаційної завдання N тел Огляд літератури Розглянута у розділі методика розробки паралельних алгоритмів було запропоновано у Foster (1995). У роботі виклад методики проводиться більш детально; з іншого боку, у роботі міститься кілька прикладів використання методики розробки паралельних методів на вирішення низки обчислювальних завдань. Корисною при розгляді питань проектування та розробки паралельних алгоритмів може бути також робота Quinn (2004). Гравітаційне завдання N тіл докладніше розглядається в Andrews (2000) Контрольні питання 1. У чому полягають вихідні припущення щодо можливості застосування розглянутої у розділі методики розробки паралельних алгоритмів? 2. Які основні етапи проектування та розробки методів паралельних обчислень? 3. Як визначається модель "підзавдання-повідомлення"? 4. Як визначається модель "процеси-канали"? 5. Які основні вимоги мають бути забезпечені під час розробки паралельних алгоритмів? 6. У чому полягають основні дії на етапі виділення підзавдань? 7. Які основні дії на етапі визначення інформаційних залежностей? 8. У чому полягають основні дії на етапі масштабування наявного набору підзавдань? 9. У чому полягають основні дії на етапі розподілу підзавдань процесорами обчислювальної системи? 10. Як відбувається динамічне керуваннярозподілом обчислювального навантаження за допомогою схеми "менеджер-виконавець"? 11. Який метод паралельних обчислень було розроблено на вирішення гравітаційної задачі N тел? 10

11 12. Який спосіб виконання операції узагальненого збору даних є більш ефективним? 6.7. Завдання та вправи 1. Виконайте реалізацію каскадної схеми обчислення суми послідовності числових значень (див. розділ 2) та порівняйте час виконання виконаної реалізації та функції MPI_Bcast бібліотеки MPI. 2. Виконайте реалізацію розглянутих способів виконання узагальненої операції збору даних та порівняйте час їх виконання. Зіставте отримані тимчасові характеристики з теоретичними оцінками. Виконайте порівняння з часом виконання функції MPI_Allgather бібліотеки MPI. 3. Розробте схему паралельних обчислень, використовуючи розглянуту в розділі методику проектування та розробки паралельних методів: для пошуку максимального значення серед мінімальних елементів рядків матриці (таке завдання має місце для вирішення матричних ігор) y = max min a, 1 i N 1 j N ij (зверніть особливу увагу на ситуацію, коли кількість процесорів перевищує порядок матриці, тобто p>n), для задачі обчислення певного інтеграла з використанням методу прямокутників b N 1 y = f (x) dx h fi, a i = 0 f i = f (x), x = i h, h = (ba) / N. i i (опис методів інтегрування дано, наприклад, у Kahaner, Moler and Nash (1988)) 4. Виконайте реалізацію розроблених паралельних методів для задач п Розробте схему паралельних обчислень для завдання множення матриці на вектор, використовуючи розглянуту розділ методику проектування і розробки паралельних методів. Література Andrews, G. R. (2000). Мова: Видавничий дім "Вільямс", 2003) Bertsekas, D.P., Ts. , J.N. (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (російський переклад Каханер Д., Моулер Л., Неш С. Чисельні методи та програмне забезпечення. М.: Світ, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools для Software Engineering. Reading, MA: Addison-Wesley. Quinn, MJ (2004). Parallel Programming в C з MPI та OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11

РОЗДІЛ 3 ПРИНЦИПИ РОЗРОБКИ ПАРАЛЕЛЬНИХ МЕТОДІВ Розробка алгоритмів (а особливо методів паралельних обчислень) для вирішення складних науково-технічних завдань часто є значною

Методи та алгоритми паралельних обчислень Проектування паралельних алгоритмів Кулаков Кирило Олександрович 2016 Петрозаводськ Цілі проектування Балансування навантаження Масштабованість Ефективність

Високопродуктивні обчислення Лекція 2. Оцінка максимально можливого паралелізму Забезпечення найкращих найкращого прискорення S T = ефективності E = 1 можливо не для всіх обчислювально T трудомістких

Лекції Лекція 1. Принципи побудови паралельних обчислювальних систем.............................. 23 Лекція 2. Моделювання та аналіз паралельних обчислень. .... 49 Лекція 3. Оцінка комунікаційної

Нижегородський державний університет ім. Н.І.Лобачевського Факультет Обчислювальної математики та кібернетики Освітній комплекс Введення в методи паралельного програмування Розділ 9. Паралельні

Проект комісії Президента з модернізації та технологічного розвитку економіки Росії «Створення системи підготовки висококваліфікованих кадрів у галузі суперкомп'ютерних технологій та спеціалізованого

Тема: Розпаралелювання виразів на прикладі арифметичних Основні характеристики складності та паралельності Що підлягає розпаралелювання? Завдання (декомпозиція на підзавдання меншої розмірності) 2Метод

ПИТАННЯ ДО ТЕСТУ ПО КУРСУ «ПАРАЛЕЛЬНІ ОЧИСЛЮВАЛЬНІ СИСТЕМИ» 1. Принципи побудови паралельних обчислювальних систем (15) 1. Схеми багатопроцесорних систем з однорідним і неоднорідним доступом. 2.

Проектування паралельних алгоритмів Лекція 3.1 29.03.2012 Т.Ю.Лимар 1 3.1 Методологія проектування Розділ Встановлення зв'язків Агрегування Прив'язка до конкретної ЕОМ 29.03.2012 Т.Ю.Лимар 2 3.1.1

Московський державний університет ім. М.В. Ломоносова Історія та методологія паралельного програмування 9. Проектування паралельних алгоритмів Розробники: Л.Б. Соколинський, д.ф.-м.н., професор

Федеральне агентство освіти Нижегородський державний університет ім. Н.І. Лобачевського Національний проект "Освіта" Інноваційна освітня програма ННГУ. Освітньо-науковий

Нижегородський державний університет ім. Н.І.Лобачевського Факультет обчислювальної математики та кібернетики Кафедра математичного забезпечення ЕОМ Лабораторія «Інформаційні технології» ItLab Практичний

Нижегородський державний університет ім. Н.І. Лобачевського – Національний дослідницький університет – Лекція. Моделювання паралельних обчислень Гергель В.П., декан ВМК ННГУ Суперкомп'ютерні

Алгоритми для паралельних обчислювальних систем 1. Типи паралелізму та методи синтезу паралельних алгоритмів. 2. Оцінка ефективності паралельних алгоритмів. 1. Типи паралелізму та методи синтезу паралельних

СУПЕРКОМП'ЮТЕРНИЙ КОНСОРЦІУМ УНІВЕРСИТЕТІВ РОСІЇ Проект Створення системи підготовки висококваліфікованих кадрів у галузі суперкомп'ютерних технологій та спеціалізованого програмного забезпечення

Оцінка ефективності паралельних алгоритмів Лекція 4. 29.03.2012 Т.Ю. Лимар 1 Вступ Принциповий момент розробки паралельних алгоритмів - аналіз ефективності використання паралелізму:

Оцінка ефективності паралельних алгоритмів Лекція 7 Т.Ю. Лимар Принциповий момент розробки паралельних алгоритмів - аналіз ефективності використання паралелізму: Оцінка максимально можливого

ОСНОВНІ ПОНЯТТЯ ПАРАЛЕЛЬНИХ ВИЧИСЛЕНЬ Паралельні обчислення (паралельна обробка) це використання кількох чи багатьох обчислювальних пристроїв для одночасного виконання різних частин однієї

Математичні моделі та методи ефективного використання розподілених Цифрова обчислювальних 3D-медицина систем Заголовок Результати Підзаголовок в області комп'ютерної презентаціїграфіки та геометричного

УДК 681.5 ПАРАЛЕЛЬНІ АЛГОРИТМИ ЧИСЛІВОГО РІШЕННЯ ЗАДАЧІ КОШІ ДЛЯ СОДУ Назарова І.А. Донецький національний технічний університет Запропоновано паралельні чисельні алгоритми однокрокових методів

РОЗДІЛ МОДЕЛЮВАННЯ ТА АНАЛІЗ ПАРАЛЕЛЬНИХ ВИЧИСЛЕНЬ При розробці паралельних алгоритмів розв'язання складних науковотехнічних завдань принциповим моментом є аналіз ефективності використання паралелізму,

1. Цілі та завдання дисципліни: Суперкомп'ютерні технології та високопродуктивні обчислення з використанням багатопроцесорних обчислювальних систем (МВС) стають важливим фактором науково-технічного

Побудова статистичних моделей ефективності паралельних програм В.Н.Белецький, С.А.Рєзнікова, А.А.Чемеріс Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України У статті розглянуто

Інформатика, управління, економіка ПРАЦІ МФТІ 2 ​​Том 2, (5) УДК 59687+475 АС Хританков Московський фізико-технічний інститут (державний університет) Математична модель характеристик продуктивності

АЛГОРИТМИ БАЛАНСУВАННЯ ЗАВАНТАЖЕННЯ ПРОЦЕСОРІВ ПАРАЛЕЛЬНОЇ ВИЧИСЛЮВАЛЬНОЇ СИСТЕМИ Бєльков Д.В. Донецький національний технічний університет, м. Донецьк кафедра обчислювальної математики та програмування

Обчислювальні машини та програмне забезпечення УДК 681.3.06 П.А. Павлов ЕФЕКТИВНІСТЬ РОЗПОДІЛЕНИХ ВИЧИСЛЕНЬ У МАСШТАБОВАНИХ СИСТЕМАХ Масштабованість (scalability) є однією з найважливіших вимог

Метод Ритца Виділяють два основні типи методів розв'язання варіаційних завдань. До першого типу належать методи, що зводять вихідне завдання до розв'язання диференціальних рівнянь. Ці методи дуже добре розвинені

ДІАГОНАЛЬНИЙ МЕТОД ПРИМНОЖЕННЯ ЩІЛЬНИХ МАТРИЦЬ Князькова Т.В., к.т.н., доцент, ВятГУ, м. Кіров Сьогодні зі зростанням потужностей обчислювальних систем та сучасних суперкомп'ютерів у широкому спектрі галузей економіки

Введення 1 Розділ 1 Завдання 1.1 Розминка Перше завдання написання програми, що використовує бібліотеку MPI, одне на всіх. 1.1.1 Обчислення числа π Обчислити число π за такою формулою: 1 1 dx 4 1 + x

Лабораторна робота 4 Паралельна реалізація методу Якобі у тривимірній області Мета роботи: практичне освоєння методів розпаралелювання чисельних алгоритмів на регулярних сітках на прикладі реалізації

Р. І. Ідрисов ТИМЧАСОВА РОЗВЕРТКА ВНУТРІШНЬОГО ПРЕДСТАВЛЕННЯ IR2 МОВИ SISAL 3.1 * На сьогоднішній день збільшення обчислювальних потужностей пов'язане вже не з прискоренням окремої, а з додаванням додаткових

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

ОРГАНІЗАЦІЯ ПАРАЛЕЛЬНИХ ЗЕРНИНИХ ВИЧИСЛЮВАЛЬНИХ ПРОЦЕСІВ (Отримання паралельних послідовностей зернистих обчислень) Наведемо приклади отримання паралельних алгоритмів, безлічі операцій яких

ПАРАЛЕЛЬНІ ВЛАСТИВОСТІ АЛГОРИТМА Паралельні комп'ютери (суперкомп'ютери) призначені для швидкого вирішення великих завдань. Чим потужніший комп'ютер, тим швидше можна вирішити у ньому завдання. Крім

Каляєв А.В. ПРОГРАМУВАННЯ ВІРТУАЛЬНИХ АРХІТЕКТУР ТА ОРГАНІЗАЦІЯ СТРУКТУРНО- ПРОЦЕДУРНИХ ВИЧИСЛЕНЬ У БАГАТОПРОЦЕСОРНИХ СИСТЕМАХ З МАСОВИМ ПАРАЛЕЛІЗМОМ 1 Анотація НІІ

Алгоритми паралельного множення матриць 1 Стрічкові алгоритми множення матриць У даних алгоритмах матриці розбиваються на безперервні послідовності рядків чи стовпців (смуги). У найпростішому випадку

Розподіл пам'яті - це процес, в результаті якого окремим елементам вихідної програми ставляться у відповідність адреса, розмір та атрибути області пам'яті, необхідної для розміщення

РІШЕННЯ НЕЛІНІЙНИХ РІВНЯНЬ І СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ. полягає у знаходженні значень

«Алгебра та геометрія» 13. Системи лінійних рівнянь алгебри (СЛАУ). Теорема Кронекер-Капеллі. Загальне та приватне рішення СЛАУ. 14. Криві другого порядку: еліпс, гіпербола, парабола та їх властивості.

УДК 681.32 ПІДВИЩЕННЯ ПРОДУКТИВНОСТІ КЛАСТЕРІВ РОБОЧИХ СТАНЦІЙ З ВИКОРИСТАННЯМ ВЕЄРНОГО РОЗПОДІЛУ ДОДАТКОВИХ ЗАВДАНЬ НА ПРОСТАЮЮЧЕ ОБЛАДНАННЯ.2.

Граф алгоритму та паралельні обчислення. Внутрішній паралелізм програм. Лекція 3 12.04.2012 (С) Л.Б.Соколинський 1 3.1 Внутрішній паралелізм Програма містить паралелізм, якщо деякі її частини (оператори)

МІНОБРНАУКИ РОСІЇ ФЕДЕРАЛЬНА ДЕРЖАВНА БЮДЖЕТНА ОСВІТАЛЬНА УСТАНОВА ВИЩОЇ ПРОФЕСІЙНОЇ ОСВІТИ «САМАРСЬКИЙ ДЕРЖАВНИЙ АЕРОКОМІС.

Лекція 5 5 Теорема існування та єдиності розв'язання задачі Коші для нормальної системи ОДУ Постановка задачі Завдання Коші для нормальної системи ОДУ x = f (, x), () полягає у відшуканні розв'язання x =

Нижегородський державний університет ім. Н.І.Лобачевського Факультет Обчислювальної математики та кібернетики Освітній комплекс Введення у методи паралельного програмування Розділ 2. Моделювання

Розділ 5. МЕТОДИ НЕЯВНОГО ПЕРЕБОРУ Розглянемо загальну постановку задачі дискретної оптимізації mi f (x), (5.) x D у якій -мірний вектор, що шукається x належить кінцевій множині допустимих рішень D.

ЗМІСТ Вступ.... 12 Частина I. Основи розпаралелювання Лекція 1. Про постановку задачі розпаралелювання... 17 1.1. 17 1.2. Про деяких обчислювальних завданнях.... 19 1.3. Чисельний

УДК 68.3.06 ВИЗНАЧЕННЯ ЧИСЛА І ТОПОЛОГІЇ РОЗМІЩЕННЯ СТАНЦІЙ БАГАТОПРОЦЕСОРНОЇ ВИЧИСЛЮВАЛЬНОЇ СИСТЕМИ О.В. Погребний Інститут "Кібернетичний центр" ТПУ E-mail: [email protected]Розглянуто завдання

ЕКСТРАПОЛЯЦІЙНІ БЛОЧНІ ОДНОКРОКОВІ МЕТОДИ ЧИСЛІВОГО ВИСОКОТОЧНОГО РІШЕННЯ ЗАДАЧІ КОШІ Кулаков В.В. Назарова І. А. Фельдман Л.П. Донецький національний технічний університет Розглядаються паралельні

Праці ІСА РАН, 2008. Т. 32 Про поняття продуктивності в розподілених обчислювальних системах М. А. Посипкін, А. С. Хрітанков Інститут системного аналізу Російської академії наук (ІСА РАН)

2007 НАУКОВИЙ ВЕСТНИК МДТУ ГА 26 серія Радіофізика та радіотехніка УДК 6236:6239 ОЦІНКА ДОЦІЛЬНОСТІ РОЗПАРАЛЮВАННЯ ІНФОРМАЦІЙНО-ЗАЛЕЖНИХ ЗАВДАНЬ У ВИЧИСЛЮВАЧІВ

Максимальне розпаралелювання алгоритмів на основі концепції Q-детермінанта Валентина Миколаївна Алеєва Південно-Уральський державний університет (НДУ) Новосибірськ, 2015 ВСТУП У доповіді розглядається

Міністерство освіти та науки Російської ФедераціїНижегородський державний університет ім. Н.І. Лобачевського В.П. Гергель ВИСОКОВИРОБНИЧІ ВИЧИСЛЕННЯ ДЛЯ БАГАТОПРОЦЕСОРНИХ БАГАТОЯДЕРНИХ

ЛК 1. Моделювання. 1. Основні поняття. 2 Принципи моделювання. 3 Властивості моделей 4 Класифікація методів моделювання. 5. Математичне моделювання 1. ОСНОВНІ ПОНЯТТЯ. Моделювання заміщення

Федеральне агентство з освіти Державне освітня установавищої професійної освіти "Новосибірський державний університет" (НГУ) Факультет інформаційних технологій

Нижегородський державний університет ім. Н.І. Лобачевського Науково-дослідний університет Створення навчальної бібліотеки паралельних методів Parlib Виконали: Козінов О.О. Кутлаєв М.В. Осокін

УДК 681.3.06 ПРОЕКТУВАННЯ СТРУКТУРИ ЛОКАЛЬНОЇ МЕРЕЖІ ДЛЯ РОЗПОДІЛЕНОЇ ВИЧИСЛЮВАЛЬНОЇ СИСТЕМИ РЕАЛЬНОГО ЧАСУ А.В. Погрібний, Д.В. Погребний Інститут "Кібернетичний центр" ТПУ E-mail: [email protected]

ПАРАЛЕЛЬНІ АЛГОРИТМИ МЕТОДУ ЦИКЛІЧНОЇ ПРОГОНИ Головашкін Д.Л., Філатов М. В. Інститут систем обробки зображень РАН Самарський державний аерокосмічний університет Анотація Робота присвячена

УДК 519.856; 519.854; 519.85 СТАТИСТИЧНИЙ ПОШУК СТРУКТУР ІНФОРМАЦІЙНО-ВИЧИСЛЮВАЛЬНОЇ МЕРЕЖІ В.В. Малигін Досліджено властивості збіжності функції оцінки структури інформаційно-обчислювальної мережі. на

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

12.1. Опитування готовності пристрою Готовність або неготовність зовнішнього пристрою до введення-виводу перевіряється в регістрі стану зовнішнього пристрою Для програмно-керованого вводу/виводу

ТАКСОНОМІЯ ФЛІННА Кириллова Юлія 6057/2 22.11.11 Таксономія Флінна загальна класифікація архітектур ЕОМ за ознаками наявності паралелізму в потоках команд та даних. запропонована 1972 р. Майклом Флінном.

Лабораторна робота 4 Розв'язання задачі Пуассона методом Якобі в тривимірній області Мета - практичне освоєння методів розпаралелювання алгоритмів задач, які вирішуються сіточними методами на прикладі рішення

Плаксин М.А.

Національний дослідницький університет Вища школа економіки (Пермська філія), м.Перм, к.ф.м.н., доцент кафедри інформаційних технологій у бізнесі, mapl@list. ru

«СУПЕРКОМП'ЮТЕРИ» VS «ПАРАЛЕЛЬНЕ ПРОГРАМУВАННЯ». «ПАРАЛЕЛЬНЕ ПРОГРАМУВАННЯ» VS «СПІЛЬНА ДІЯЛЬНІСТЬ». ЯК ВИВЧАТИ ТЕМУ «ПАРАЛЕЛЬНІ ВИЧИСЛЕННЯ» У СЕРЕДНІЙ ШКОЛІ?

КЛЮЧОВІ СЛОВА

Інформатика, паралельне програмування, паралельні обчислення, паралельні алгоритми, суперкомп'ютери, початкова школа, середня школа, ТРИЗформашка.

АННОТАЦІЯ

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

Сучасний етап розвитку computer science пов'язаний з масовим поширенням паралелізму обчислень на всіх рівнях (багатомашинні кластери, багатопроцесорні ЕОМ, багатоядерні процесори).

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

Сучасна теорія алгоритмів створювалася для поняття послідовного алгоритму. Яким чином позначиться на понятті алгоритму відмову від вимоги послідовності виконання кроків?

Принаймні останні 20 років поняття «алгоритм» запроваджувалося в школі в нерозривній зв'язці з поняттям «виконавець». Для послідовного алгоритму це природно. Як бути з алгоритмом паралельним? Його виконує один виконавець чи група виконавців? Для конкретності як приклад розглянемо комп'ютерну навчальну програму «Танковий екіпаж». У цій програмі від учня потрібно запрограмувати дії екіпажу танка, що складається з трьох осіб: навідника, водія та заряджання. Кожен із них має свою систему команд. Для того щоб виконати бойове завдання (вразити всі цілі), всі члени екіпажу повинні діяти узгоджено. Приклад ігрового поля програми "Танковий екіпаж" див. на рис.1.

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

Файл 1*ра Вікне Про програму

Виполієти все

Bbno.n«fTb до виділеного рядка

Повернути до початкового потрапу**»

бипопнлтъ покроково (після виконання «.ладом команди несйкоа^« буде наждтъ кнопки гВ иголг«п-ъ наступний uwr")

Е ЬГВД iTHWTt. швидкий крок

Оглноснть покрокове

Рис.1. Фрагмент ігрового поля програми «Танковий екіпаж»

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

Потрібно домовитися про термін для позначення групи виконавців, що спільно діють. Термін «команда» не годиться, асоціюється з «системою команд виконавця» та з «командами центрального процесора». Колектив виконавців? "Бригада виконавців"?

Ш. Алгоритм

н Наїзд1«; Водій Заряджаючий

1 Пмер^ть орун* по «освій сгклл V Стоп V Зарядити 1

г Пці V Стоп V Зарядити 2

3 Опт! V Повернутися годинникової стрілки на 90 градусів V Зарядити 1 V

Л V Перш V Зарядити? V

5 Вогонь! V Стоп V Зарядити 1

І П^чм V Ст*п V Зарясся? V

7 Вогонь! V Стоп V Зарядити 1 V

3 Па^ V Повернутися па годинниковій стрілці на 45 градусів V Зарядити 2 V

S Пауя V Вперйа V Пауза V

10 Пвдеа V Вперед V Пауза ¿d

11 Плрл V Вперед V Пауза V

12 Паум V Повернутися за годинниковою стрілкою на 45 градусів V Пауза V

13 Падм V Вперед V Пауза V

14 V n&stpHyTbtft то чксевн стрілці на 45 градус «V Зар^а^ьТ V

Рис.2. Фрагмент програми для «Танкового екіпажу» (приклад лінійок команд) Вимагає доопрацювання традиційне поняття «системи команд виконавця» (СКІ) та саме поняття команди. Якщо ми вважаємо, що три члени танкового екіпажу утворюють єдиного виконавця, то що вважати СКІ цього виконавця? І що вважати командою? Чи залишити поняття СКІ для кожного персонажа? Тобто це вже не система команд ВИКОНАВЦЯ, а система команд одним із компонентів виконавця (для якої ще немає назви)?

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

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

Окреме питання - методи розпаралелювання вже існуючих послідовних алгоритмів.

Донедавна паралельне програмування було долею невеликої кількості висококваліфікованих системних програмістів. Сьогодні воно стає частиною професійної компетенції. Але технологія паралельного програмування суттєво відрізняється від традиційного послідовного. На підтвердження цього твердження за Л.Л. Босової процитуємо найбільшого російського фахівця у галузі паралельних обчислень В.В. Воєводина:

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

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

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

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

елементом загальної культури мислення. Питання: яким чином позначиться на мисленні наступного покоління освоєння поняття паралельного алгоритму, чого призведе перебудова свідомості «на паралельний лад»?

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

Історично першу спробу включення тематики паралельних обчислень до шкільного курсу інформатики було зроблено ще двадцять років тому. Двадцять років тому в курсі під назвою «Алгоритміка» було описано виконавця «Директора будівництва», який командував паралельними діями кількох бригад, що будують споруду з блоків прямокутної та трикутної форми. Більше того, для цього виконавця було створено програмну реалізацію. На жаль! Ця чудова методична розробка в середині 90-х виявилася не затребуваною. Вона майже на двадцять років випередила свій час!

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

Інтерес, який викликає у суспільстві, зокрема, серед учнів, тема суперкомп'ютерів. Цей інтерес повторює на сучасному рівні інтерес, який півстоліття тому викликали великі машини – суперкомп'ютери свого часу;

Організаційну підтримку суперкомп'ютерного співтовариства. Щоліта на факультеті обчислювальної математики та кібернетики МДУ проводиться Літня Суперкомп'ютерна Академія. І щоліта в рамках цієї Академії організується шкільний трек для вчителів інформатики. Навчання проводиться безкоштовно. Іногородні слухачі забезпечуються житлом на пільгових умовах. На конференції Russian Supercomputing Days у вересні 2015 р. було організовано шкільну секцію та майстер-клас для вчителів інформатики. Послідовна організаційна робота призвела до виявлення та формування групи вчителів, зацікавлених у просуванні цієї тематики;

Наявність яскравого харизматичного лідера, яким є Володимир Валентинович Воєводін – доктор фізико-математичних наук, професор, член-кореспондент РАН, заступник директора Науково-дослідного обчислювального центру Московського державного університету;

Інтерес і підтримку (зокрема, матеріальну) із боку російського представництва фірми Інтел та менеджера зі стратегічного розвитку фірми Інтел Ігоря Олеговича Одинцова.

Нестача «суперкомп'ютерного» підходу полягає у зауживанні тематики паралельних обчислень. Самі суперкомп'ютери школярам, ​​як правило, недоступні (хіба що у великих містах на них можна подивитися на екскурсії). Завдання, на вирішення яких вони націлені, для школярів занадто складні і, як правило, не мають безпосередньої практичної значущості і не мають практичного інтересу.

Природним розширенням суперкомп'ютерної тематики вивчення паралельного програмування. Нині до виконання паралельних програм не обов'язково мати суперЭВМ. Достатньо багатоядерного процесора чи відеокарти з набором графічних прискорювачів. А це є вже майже всім. З робіт у цьому напрямі зазначимо кандидатську дисертацію М.О. Соколовській за методикою навчання майбутніх вчителів інформатики основ паралельного програмування та досвід О.Ю. Кисельової з освоєння школярами технології CUDA.

На думку автора цієї статті, зосередження уваги на спуерЕОМ і паралельному програмуванні суттєво збіднює та ускладнює тему паралельних обчислень, відволікає учнів від безлічі важливих та доступних питань. Метою теми «паралельні

обчислення» в середній школі є не навчання «реальному» паралельному програмуванню (вивчення відповідних мовних конструкцій, мов програмування та технологій), а ознайомлення учнів з відповідним набором понять та розуміння особливостей паралельної роботи. Світ навколо і всередині нас є складною паралельною системою. І ця система сама по собі дає масу матеріалу для освоєння понять та механізмів паралелізму. Жодні складні штучні конструкції типу технологій MPI та OpenMP для цього не потрібні. Шкільна інформатика має виховати мислення, налаштоване на «паралельний лад». А далі університет нехай закладає у це мислення професійні знання, уміння, навички. У школі акцентувати має сенс не знайомство з суперкомп'ютерами та вивчення паралельного програмування, а освоєння механізмів «спільної діяльності», які постійно і широко використовуються в житті. У курсі пропонується відобразити такі питання:

1) Спільна робота кількох виконавців (копання канави декількома землекопами) і розпаралелювання «всередині» одного виконавця за наявності кількох обробних пристроїв (читаємо яблуко). У computer science це будуть багатомашинний комплекс та багатоядерний процесор.

2) Види паралелізму: паралелізм істинний та псевдопаралелізм (один процесор виконує частинами кілька програм).

3) Виконавці однотипні (землекопи) та різнотипні (екіпаж танка).

4) Роботи однотипні та різнотипні.

5) Співвідношення «виконавці – роботи»: 1 виконавець – 1 робота, 1 виконавець – N робіт (псевдопаралельне виконання або справжній паралелізм за наявності декількох обробних пристроїв для різних робіт), N виконавців – 1 робота, N виконавців – N робіт.

6) Погодження діяльності виконавців. Види узгодження: по частинах роботи, у часі, за результатами діяльності, за ресурсами.

7) Ресурси. Ресурси, що поділяються та нерозділяються, витрачаються та повторно використовуються. Утилізація спожитих ресурсів («складання сміття» у сенсі).

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

9) Конкуренція виконавців за ресурси. Блокування. Клінч (глухий кут).

10) Механізми узгодження дій виконавців.

11) Псевдопаралельне виконання процесів на комп'ютері (розподіл між виконавцями-процесами одного ресурсу - процесора).

12) Придатність алгоритмів до розпаралелювання. Можливий ступінь розпаралелювання. Існування алгоритмів, що не піддаються розпаралелювання.

Зазначимо, що наведений список є приватною думкою автора статті та відкритий для обговорення, доповнення та коригування. Більше того, на думку автора, було б дуже корисно, щоб «суперкомп'ютерна спільнота» сформулювала «соціальне замовлення» для школи: які саме знання-вміння-навички вона хоче бачити у випускниках школи. Чим випускник школи «суперкомп'ютерного світу» має відрізнятися від сьогоднішнього випускника? Буде замовлення – буде й результат. Свіжий приклад. Першого дня Russian Supercomputing Days-2015 у двох доповідях прозвучала думка, що швидкодія сучасних суперЕОМ визначається не потужністю процесорів (яка знаходиться в центрі уваги публіки), а швидкодією оперативної пам'яті. Саме вона стає пляшковим шийкою, пропускна здатність якого визначає продуктивність усієї системи. В результаті на другий день конференції учасники вчительського майстер-класу обкатували вигадану автором цієї статті гру, яка демонструє взаємодію центрального процесора, оперативної пам'яті та кеш-пам'яті. Порядок та форма викладу матеріалу – питання відкрите.

Матеріал має бути продемонстрований на прикладах, не пов'язаних із роботою ЕОМ. Виконавці мають маніпулювати матеріальними об'єктами.

Якомога більша частина навчання має мати характер ділових (організаційно-діяльнісних) ігор.

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

Роботу над підготовкою методики вивчення паралельних обчислень автор цієї статті розпочав у 2013 р. у ході підготовки конкурсу «ТРИЗформашка-2013» та продовжив у наступні роки.

(«ТРИЗформашка» - міжрегіональний Інтернет-конкурс з інформатики, системного аналізу та ТРВЗ. Проводиться щорічно у другій половині березня. Вік учасників – з І класу до IV курсу. Географія – від Владивостока до Риги. Середня кількість учасників – 100 команд (300 чол.) .), максимальне - 202 команди (понад 600 чол.) Сайт конкурсу www.trizformashka.ru.) Тоді, в 2013 р. мета роботи була сформульована наступним чином:

1. Протягом двох-трьох років підготувати опис виконавців, набір ігор та завдань, пов'язаних із паралельними обчисленнями;

2. Запропонувати їх (у частинах, щорічно) учасникам конкурсу;

3. Проаналізувати їхню реакцію (оцінити кількість вирішуючих, їх вік, успішність вирішення, типові помилки, виявлені неточності у формулюванні завдань тощо). Конкурс «ТРИЗформашка» виявився зручним інструментом налагодження завдань, оскільки

дозволяв отримати реакцію різного віку (від I класу до IV курсу), з різних регіонів, з різних навчальних закладів.

За минулі роки було підготовлено наступний набір методичних інструментів та майданчиків для їхньої апробації.

1. Завдання на паралелізм, починаючи з 2013 р., увійшли до конкурсу «ТРИЗформашка» (починаючи з 2013 р., конкурс має підзаголовок «Паралельні обчислення»). Список типів завдань наведено нижче;

2. Підготовлено розділ про паралелізм для нової версії підручника інформатики для 4 класу. Матеріал пройшов апробацію у 3-х та 4-х класах Ліцею №10 м.Пермі;

3. Розроблено та з 2014 р. використовується в конкурсі «ТРИЗформашка» комп'ютерна гра«Танковий екіпаж»;

4. Розроблено та пройшов апробацію ряд ігор, у яких відображені такі питання:

Погодження діяльності виконавців. Різні види погодження;

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

Ресурси. Ресурси поділяються та нерозділені;

Конкуренція виконавців за ресурси. Блокування. Клінч (глухий кут). Були запропоновані та випробувані такі типи завдань:

1. Завдання на види погодження. (Які види погодження існують у шкільній їдальні?);

2. Гра «Танковий екіпаж». Завдання на побудову паралельного алгоритму;

3. Виконавець «Будівництво». Одночасно працюючі бригади будують споруду з горизонтальних та вертикальних балок. Завдання включають завдання на виконання зазначеного алгоритму, на розробку нового алгоритму, на пошук помилок у заданому алгоритмі, на дослідження алгоритмів (порівняння термінів будівництва за різними алгоритмами, порівняння вартості будівництва, оцінка можливості заощадити за рахунок перерозподілу робочої сили та ін);

4. Конкуренція за ресурси. Три порося готують кожен сам собі обід. Для кожного порося вказано, які страви він готує, які ресурси (обладнання, посуд і т.д.) йому для цього потрібні та протягом якого часу ці ресурси мають використовуватись. Потрібно скласти графік роботи кожного порося, якщо він готує на кухні один, якщо вони готують парами, якщо готують усі троє одразу. Час приготування їжі має бути мінімізовано;

5. Мережевий графік. Дано мережевий графік. Потрібно зобразити (схематично) споруду, яка буде побудована, визначити, скільки днів знадобиться для будівництва при тій чи іншій кількості бригад, яка частина роботи буде виконана до певного часу;

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

7. Діаграми Ганта. Описаний текстом план робіт з реконструкції цеху: тривалість та взаємна послідовність дій, необхідні працівники. Потрібно визначити термін здавання об'єкта, зміну терміну при тих чи інших змінах у робочій силі, список працівників, які задіяні на конкретну дату.

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

На сьогодні маємо такі результати:

1. Сформульовано підхід із вивчення теми «паралельні обчислення»: йти не від проблем computer science, а «від життя», наголошувати на «спільній діяльності»;

2. Сформульовано перелік питань, які пропонується відобразити у початковому курсі паралельних обчислень;

3. Сформульовано деякі класи завдань. На підставі накопиченого досвіду можна оцінити, які завдання варто вигадувати;

4. Підготовлено набір завдань названих класів. Завдання пройшли апробацію у конкурсах «ТРИЗформашка» за 2013, 2014, 2015 р.р. та/або у початковій школі (на заняттях з учнями третіх-четвертих класів ліцею №10 м.Пермі);

5. Підготовлено набір ділових ігор. Ігри пройшли апробацію у початковій школі та на низці заходів для вчителів. Зокрема, були представлені на шкільному треку Літньої Суперкомп'ютерної Академії ВМК МДУ у 2014 р., на майстер-класі для вчителів на Russian Supercomputing Days-2015, на кількох інших конференціях (у тому числі на конференції ІТ-0освіта-2015 асоціації АПКІТ) та інших заходах для вчителів інформатики;

6. Підготовлено комплект текстів для паралелізму для підручника IV класу. Тексти пройшли апробацію у ліцеї №10 м.Пермі;

7. Підготовлено комп'ютерну гру «Танковий екіпаж». Гра пройшла апробацію у конкурсах «ТРИЗформашка» 2014 та 2015;

8. Конкурс «ТРИЗформашка» виправдав себе як апробаційний майданчик;

9. Сформульовано завдання «провести рокіровку» у процесі навчання алгоритмізації: вчити відразу паралельному програмуванню, представляючи послідовний алгоритм частиною паралельного. Існує думка про те, як можна реалізувати цю ідею. Є можливість випробувати ці ідеї протягом поточного навчального року (на учнів 4-х - 5-х класів);

10. Є потреба, бажання та можливість продовжувати роботу.

Література

1. Алгоритміка: 5-7 класи: Підручник і задачник для загальноосвіт. навчальних закладів/А.К. Дзвінкін, А.Г. Кулаков, С.К. Ландо, А.Л. Семенов, А.Х. Шень. - М: Дрофа, 1996.

2. Босова Л.Л. Паралельні алгоритми у початковій та основній школі. //Інформатика у шкільництві. 2015 №2. С.24-27.

3. Воєводін В.В. 10 лекція про те, чому важко вирішувати завдання на обчислювальних системах паралельної архітектури і що треба знати додатково. щоб успішно долати ці проблеми: підручник. М: Вид-во МДУ 2010.

4. Гаврилова І.В. Перша подорож у «паралельний світ». //Інформатика у шкільництві. 2015 №6. С.16-19.

5. Дітер М.Л., Плаксін М.А. Паралельні обчислення у шкільній інформатиці. Гра «Будівництво». //Інформатика в школі: минуле, сьогодення та майбутнє.: матеріали Всерос. наук.-метод. конф. з питань застосування ІКТ в освіті, 6-7 лютого 2014 р. / Перм. держ. нац. ісл. ун-т. – Перм, 2014. – С.258-261.

6. Іванова Н.Г., Плаксін М.А., Русакова О.Л. ТРИЗформашка. //Інформатика. N05 Перевірено 10.10.2015.

14. Плаксін М.А. Інформатика: підручник для 4 класу: о 2 год. /М.А.Плаксін, Н.Г.Іванова, О.Л.Русакова. - М: БІНОМ. Лабораторія знань, 2012

15. Плаксін М.А. Про методику початкового знайомства з паралельними обчисленнями у неповній середній школі. //Інформатика в школі: минуле, сьогодення та майбутнє.: матеріали Всерос. наук.-метод. конф. з питань застосування ІКТ в освіті, 6-7 лютого 2014 р. / Перм. держ. нац. ісл. ун-т. – Перм, 2014. – С.256-258.

16. Плаксін М.А. Комплекс ділових ігор для знайомства з паралельними обчисленнями у початковій школі. //Викладання інформаційних технологій у Російській Федерації: матеріали Тринадцятої відкритої Всеросійської конференції «ІТ-0бразування-2015» (м.Перм, 14-15 травня 2015 р.). Пермський державний національний дослідницький університет – Перм, 2015. С.60-62.

17. Плаксін М.А., Іванова Н.Г., Русакова О.Л. Набір завдань для знайомства з паралельними обчисленнями у конкурсі «ТРИЗформашка». //Викладання інформаційних технологій у Російській Федерації: матеріали Тринадцятої відкритої Всеросійської конференції «ІТ-Освіта-2015» (м.Перм, 14-15 травня 2015 р.). Пермський державний національний дослідницький університет - Перм, 2015. С. 232-234.

18. Соколовська М.А. Методична система навчання основ паралельного програмування майбутніх вчителів інформатики: автореф. дис. ... канд. пед. наук, Красноярськ, 2012.

Поняття паралельних обчислень

ОСНОВИ ПАРАЛЕЛЬНИХ ВИЧИСЛЕНЬ

Лекція №6

Під паралельними обчисленнями (parallel or concurrent computations)можна розуміти процеси розв'язання завдань, в яких в той самий момент часу можуть виконуватися одночасно кілька обчислювальних операцій

Паралельні обчислення становлять основу суперкомп'ютерних технологій та високопродуктивних розрахунків

· Паралельна обробка

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

Аналогічно система з N пристроїв ту роботу виконає за 1000/N одиниць часу. Подібні аналогії можна знайти і в житті: якщо один солдат закопає город за 10 годин, то рота солдатів з п'ятдесяти чоловік з такими ж здібностями, працюючи одночасно, впораються з тією ж роботою за 12 хвилин – принцип паралельності у дії!

Піонером у паралельній обробці потоків даних був академік А.А.Самарський, який виконував на початку 50-х років розрахунки, необхідні моделювання ядерних вибухів. Самарський вирішив це завдання, посадивши кілька десятків панянок з арифмометрами за столи. Панночки передавали дані один одному просто на словах і відкладали необхідні цифри на арифмометрах. Таким чином, зокрема, було розраховано еволюцію вибухової хвилі.

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

· Конвеєрна обробка

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

Припустимо, що операції можна виділити п'ять мікрооперацій, кожна з яких виконується за одну одиницю часу. Якщо є один неподільний послідовний пристрій, то 100 пар аргументів він обробить за 500 одиниць. Якщо кожну мікрооперацію виділити в окремий етап (або інакше кажуть - ступінь) конвеєрного пристрою, то на п'ятій одиниці часу на різній стадії обробки такого пристрою будуть перші п'ять пар аргументів, а весь набір зі ста пар буде оброблений за 5+99=104 одиниці часу - прискорення проти послідовним пристроєм майже п'ять разів (за кількістю щаблів конвеєра).

Моделі паралельних комп'ютерів (класифікація Флінна)

· "Один потік команд - один потік даних" (SISD - "Single Instruction Single Data")

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

· "Один потік команд - багато потоків даних" (SIMD - "Single Instruction - Multiplе Data")

SIMD (англ. Single Instruction, Multiple Data)- принцип комп'ютерних обчислень, що дозволяє забезпечити паралелізм лише на рівні даних. SIMD комп'ютери складаються з одного командного процесора (керуючого модуля), званого контролером, та кількох модулів обробки даних, званих процесорними елементами. Керуючий модуль приймає, аналізує та виконує команди.

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

· "Багато потоків команд - один потік даних" (MISD - "Multiple Instruction - Single Data")

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

Масиви ПЕ з безпосередніми сполуками між прилеглими ПЕ називаються систолічними. Такі масиви винятково ефективні, але кожен із них орієнтований рішення дуже вузького класу завдань. Розглянемо, як можна побудувати систолічний масив для вирішення певного завдання. Нехай, наприклад, потрібно створити пристрій для обчислення матриці D=C+AB, де

Тут усі матриці – стрічкові, порядку n. Матриця Aмає одну діагональ вище та дві діагоналі нижче головної; матриця B- одну діагональ нижче та дві діагоналі вище головної; матриця Cпо три діагоналі вище та нижче головної. Нехай кожен ПЕ може виконувати скалярну операцію c+abта одночасно здійснювати передачу даних. Кожен ПЕ, отже, повинен мати три входи: a, b, cі три виходи: a, b, c. Вхідні ( in) та вихідні ( out) дані пов'язані співвідношеннями

a out = a in , b out = b in , c out = c in + a in * b in;

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

Масив працює за тактами. За кожний такт усі дані переміщуються до сусідніх вузлів за напрямками, вказаними стрілками.

На малюнку показано стан систолічного масиву у певний час. У наступний такт усі дані перемістяться на один вузол та елементи a11, b11, c11опиняться в одному ПЕ, що перебуває на перетині штрихових ліній. Отже, буде обчислено вираз c11+a11b11.У цей же такт дані a12і b21впритул наблизиться до ПЕ, що у вершині систолічного масиву.

У наступний такт усі дані знову перемістяться на один вузол у напрямку стрілок і у верхньому ПЕ виявляться a12і b21і результат попереднього спрацьовування ПЕ, що знизу, тобто. c11+a11b11. Отже, буде обчислено вираз c11+a11b11+a12b21. Це є елемент d11матриці D.

Продовжуючи потактний розгляд процесу, можна переконатися, що на виходах ПЕ, що відповідають верхній межі систолічного масиву, періодично через три такти видаються елементи матриці D, у своїй кожному виході з'являються елементи однієї й тієї діагоналі. Приблизно через 3nтактів буде закінчено обчислення всієї матриці D. При цьому завантаженість кожного систолічного осередку асимптотично дорівнює 1/3 .

· "Багато потоків команд - багато потоків даних" (MIMD - "Multiple Instruction - Multiple Data")

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

Гігантська продуктивність паралельних комп'ютерів та супер-ЕОМ з лишком компенсується складнощами їх використання. Почнемо з найпростіших речей. У вас є програма та доступ, скажімо, до 256-процесорного комп'ютера. Що ви очікуєте? Так ясно що: ви цілком законно очікуєте, що програма виконуватиметься у 256 разів швидше, ніж на одному процесорі. А ось саме цього, швидше за все, і не буде.

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

Вступ

Наближався захід ери 32-бітового каміння, і було очевидно, що треба підвищувати не тільки потужність, а й розрядність. Розробники процесорів зіткнулися з низкою проблем у збільшенні тактової частоти: неможливо розсіювати теплоту, що виділяється кристалом, не можна далі зменшувати розмір транзисторів, проте головною проблемою стало те, що при збільшенні тактової частоти швидкодія програм не підвищувалася. Причиною цього стала паралельна робота сучасних комп'ютерних систем, а один процесор, хоч би яким потужним він був, у кожен час може виконувати лише одне завдання. Наприклад, у мене в системі Windows 7 у момент написання статті виконується 119 процесів. Хоча вони далеко не всі знаходяться у бекграунді, їм не всім потрібна висока потужність. На одному камені виконання кількох процесів/потоків може бути конкурентним. Тобто їх робота чергується: після того, як певний потік відпрацює свій квант часу, протягом якого він виконав корисне навантаження, його поточний стан збережеться в пам'яті, а він буде вивантажений з процесора і замінений наступним потоком, що знаходиться в черзі, - відбудеться перемикання контексту на що витрачається дорогоцінний час. А поки що йде обмін даними між процесором та оперативною пам'яттю, через обмежену пропускну здатністьсистемної шини процесор нервово палить бамбук, осторонь чекаючи дані. На допомогу можуть прийти апаратний та програмний (наприклад, з операційної системи) планувальники, щоб підвантажувати дані в кеш. Однак кеш дуже обмежений за обсягом, тому таке рішення не може бути панацеєю. Виходом стала паралельна обробка, коли він у реальному часі одночасно виконуються кілька процесів. А щоб її реалізувати, потрібно фундаментально перепроектувати і перебудувати камінь - поєднати в одному корпусі два виконуючі кристали і більше.

Планування

При розробці паралельної програми стадія проектування стає більш важливою, ніж під час розробки однопоточних додатків. І оскільки насправді паралельне програмування у вузькому колі завдань використовується вже десятиліттями, були виявлені деякі концепції, що зарекомендували себе. Найважливіше - подивитись розробку інакше, не послідовно, виділити одиницю виконуваної роботи, провести декомпозицію завдання. Є три способи: декомпозиція за завданнями, декомпозиція за даними, декомпозиція з інформаційних потоків. Перший спосіб декомпозиції найпростіший: ми просто прив'язуємо окрему функцію до певного потоку та запускаємо його на виконання. Паралельна обробка готова. Однак можуть бути проблеми - конкуренція, якщо в одиниці, що виконується, використовуються загальні глобальні дані. Але про це ми поговоримо згодом. Другий спосіб теж досить зрозумілий метод розпаралелювання: наприклад, великий масив даних обробляється кількома потоками, кожен із яких працює над частиною, обмеженою певними межами. Декомпозиція з інформаційних потоків служить завданням, коли робота одного потоку залежить від результату виконання іншого. Наприклад, під час читання з файлу потік - обробник лічених даних не може розпочати роботу, поки потік-читач не рахує певний обсяг даних.

Апаратні рішення

Перш ніж перейти до багатоядерності, розробники процесорів з'ясували, що при виконанні одного потоку процесорне ядро ​​завантажується не повністю (думаю, для цього не треба бути провидцем). І оскільки для виконання другого програмного потоку використовуються не всі ресурси мікропроцесора (оскільки апаратний стан - виконавчі пристрої, кеш - може зберігатися в одному екземплярі), то дублювання потребує лише область стану програмної архітектури (логіка переривань). Ця технологія отримала назву гіперпоточності (Hyper-Threading). Гіперпотоковість - апаратний механізм, у якому кілька незалежних апаратних потоків виконуються в одному такті на єдиному суперскалярному процесорному ядрі. З її допомогою один фізичний процесор представляється як два логічні, тобто його бачить операційна система, тому що планування і виконання, по суті, здійснюється з розрахунком на два ядра. Це відбувається завдяки безперервному потоку команд, що виконуються на спільному устаткуванні. Ця технологія була додана до архітектури NetBurst, реалізованої в процесорах Pentium 4. Тому гіперпоточність була реалізована ще в останніх версіях Pentium 4, але мені тоді якось не вдалося її застати. Проте зараз я можу спостерігати її в процесорі Atom, встановленому в нетбуку. У цьому камені, крім гіперпоточності, реалізована багатоядерність (у кількості двох штук), тому в операційній системі я спостерігаю чотири камені. Але, наприклад, у Core 2 Duo гіперпоточність відсутня, так само як і в Core i5. За допомогою гіперпоточності швидкість виконання оптимізованих для багатопоточності програм вдалося підвищити на 30%. Підкреслю, що приріст продуктивності матиме місце лише у спеціально підготовлених додатках.

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

Потім винайшли багатоядерні процесори, які нині використовуються повсюдно. Багатоядерні процесори підтримують мультипроцесорну обробку кристалі. У цій архітектурі два або більше ядра реалізуються в одному процесорі, що встановлюється в один сокет. Залежно від конструкції ці ядра можуть спільно використовувати великий кеш тому ж кристалі. Багатоядерні процесори також потребують сумісного чіпсету. Так як кожне ядро ​​є самостійним виконуючим модулем, то багатоядерні процесори забезпечують справжній паралелізм - виконання кожного потоку в відокремленому середовищі. У разі присутності кількох виконуючих ядер може бути спосіб обміну інформацією з-поміж них, без чого просто неможливо створити паралельну систему, причому потрібен спеціальний ресурс. Для цього був винайдений удосконалений програмований контролер переривань (APIC). Він виконує обмін інформацією між процесорами/ядрами, використовуючи механізм міжпроцесорного переривання (Interprocessor Interrupt). Останній у свою чергу використовується операційною системою для планування/виконання потоків.

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

Програмні рішення

У паралельному виконанні коду велику роль грають програмні рішення. На сцену виходять як системні програмні продукти (операційні системи, компілятори), так і програми користувача рівня. З погляду прикладного програміста ми можемо скористатися лише другою підмножиною. Насправді цього цілком достатньо, якщо операційна система є надійною. Подальша розповідь здебільшого відноситься до Windows NT 6.1, якщо не зазначено інше. Як тобі відомо, Windows NT використовує модель багатопоточності, що витісняє. Коли запускається програма, стартує процес, у ньому можуть виконувати свою роботу один або кілька потоків, всі вони поділяють загальну пам'ять та загальний адресний простір. Потік же, своєю чергою, - це відокремлена послідовність команд, виконувана незалежно. Існує три види потоків:

• користувача рівня - створюється в програмі користувача (на рівні користувача). Ці потоки в Windows NT проектуються на потоки рівня ядра, тому їх бачить процесор;
• потік ядра - керується ядром операційної системи;
• апаратний потік – одиниця, що виконується на процесорі.

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

Примітиви паралельного кодингу

Ділянки коду, які можуть бути одночасно використані кількома потоками та містять загальні змінні, називаються критичними секціями. Вони читання-запис значень під впливом двох і більше потоків можуть відбутися асинхронно. Цей стан називається станом перегонів. Тому в кожний часовий проміжок усередині критичної секції має виконуватися лише один потік. Для цього використовуються примітиви синхронізації - блокування. Семафор – історично найперший механізм для синхронізації, розроблений Дейкбудом у 1968 році. Дозволяє увійти в критичну секцію певній кількості потоків, при вході до неї потоку зменшує своє значення та збільшує у момент його виходу. Обов'язковою умовою є атомарне виконання операцій перевірки значення семафору + збільшення значення, а також перевірки значення + зменшення значення. Розвитком семафору служить м'ютекс, який є двійковим семафором і тому в критичній секції допускає виконання тільки одного потоку. Блокування читання-запису дозволяють кільком потокам читати значення загальної змінної, що у критичної секції, але записувати лише одному. Під час очікування спин блокування не блокується, а продовжує активне опитування заблокованого ресурсу. Спін-блокування – погане вирішення проблеми синхронізації для одноядерного процесора, оскільки займає всі обчислювальні ресурси.

Схожий на семафори механізм умовних змінних, проте вони, на відміну семафорів (і м'ютексів), не містять реальних значень. Вони стежать виконання зовнішніх умов.

У сучасних мовах програмування є високорівневі механізми, що дозволяють спростити використання блокувань та умовних змінних («монітори»). Замість того, щоб явно писати операції блокування та розблокування ділянки коду, розробнику достатньо оголосити критичну секцію як синхронізовану.

Для обміну інформацією між процесами/потоками застосовуються повідомлення, що поділяються на три групи: внутрішньопроцесні (для передачі між потоками одного процесу), міжпроцесні (для передачі інформації між процесами - із залежністю від потоків) і процес - процес (поточно незалежна передача інформації між процесами) ).
У той же час при використанні блокувань для уникнення перегонів можуть настати мертві (dead lock) та живі (live lock) блокування. Мертве блокування має місце, коли один потік заблокований на очікуванні певного ресурсу від іншого потоку, але той не може дати його (наприклад, очікує на результат від першого). Мертве блокування може статися при виконанні чотирьох добре визначених умов (ми не розбиратимемо ці умови в цій статті). Тому при написанні багатопотокового коду програміст має можливість уникнути дідлока, але на практиці це виглядає набагато складніше. Жива блокування гірша за мертву тим, що в першому випадку потоки заблоковані, а в другому вони постійно конфліктують.

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

Win32 threads

Після появи першої версії Windows NT багатопотокове програмування в ній покращувалося від версії до версії, одночасно покращувався пов'язаний з потоками API. Отже, коли стартує процес за допомогою функції CreateProcess, він має один потік виконання команд. Потік складається з двох об'єктів: об'єкт ядра (через нього система керує потоком) та стек, в якому зберігаються параметри, функції та змінні потоки. Щоб створити додатковий потік, необхідно викликати функцію CreateThread. У результаті створюється об'єкт ядра - компактна структура даних, використовувана системою управління потоком. Цей об'єкт, насправді, не є потоком. Також з адресного простору батьківського процесу потоку виділяється пам'ять. І оскільки всі потоки одного процесу виконуватимуться в його адресному просторі, вони розділятимуть його глобальні дані. Повернемося до функції CreateThread та розглянемо її параметри. Перший параметр – покажчик на структуру PSECURITY ATTRIBUTES, яка визначає атрибути захисту та властивості успадкування, для встановлення значень за умовчанням достатньо передати NULL. Другий параметр типу DW0RD визначає, яку частину адресного простору може використовувати потік під свій стек. Третій параметр PTHREAD START_ROUTIME pfnStartAddr - покажчик на функцію, яку необхідно прив'язати до потоку і яку він виконуватиме. Ця функція повинна мати вигляд DWORD WINAPI ThreadFunc(PVOID pvParam), вона може виконувати будь-які операції; коли вона завершиться, то поверне управління, а лічильник користувачів об'єкта ядра потоку буде зменшено на 1, у випадку, коли цей лічильник дорівнюватиме 0, даний об'єктбуде знищено. Четвертий параметр функції CreateThread - покажчик на структуру PVOID, що містить параметр для ініціалізації виконуваної функції в потоці (див. опис третього параметра). П'ятий параметр (DWORD) визначає прапор, що вказує на активність потоку після створення. Останній, шостий параметр (PDWORD) – адреса змінної, куди буде поміщений ідентифікатор потоку, якщо передати NULL, тим самим ми повідомимо, що вона нам не потрібна. У разі успіху функція повертає дескриптор потоку, за допомогою якого можна маніпулювати потоком; при фейлі функція повертає 0.

Існують чотири шляхи завершення потоку, три з яких небажані: це завершення потоку через виклик функції ExitThread, через виклик TerminateThread при завершенні батьківського процесу без попереднього завершення потоку. Лише 1 шлях – самозавершення потоку, що відбувається у виконанні призначених йому дій, є сприятливим. Тому що тільки в цьому випадку гарантується звільнення всіх ресурсів операційної системи, знищення всіх об'єктів C/C++ за допомогою деструкторів.

Ще кілька слів про створення потоку. Функція CreateThread знаходиться у Win32 API, при цьому в бібліотеці Visual C++ є її еквівалент _beginthreadex, у якої майже той же список параметрів. Рекомендується створювати потоки саме з її допомогою, оскільки вона використовує не тільки CreateThread, але і виконує додаткові операції. Крім того, якщо потік був створений за допомогою останньої, то при знищенні викликається _endthreadex, яка очищає блок даних, який займає структура, що описує потік.

Потоки плануються виконання з урахуванням пріоритету. Якби всі потоки мали рівні пріоритети, то для виконання кожного (WinNT) виділялося б по 20 мс. Але це не так. У WinNT є 31 (від нуля) потоковий пріоритет. При цьому 31 - найвищий, на ньому можуть виконуватися тільки критичні програми - драйвери пристроїв; 0, найнижчий, зарезервований для виконання потоку обнулення сторінок. Тим не менш, розробник не може явно вказати номер пріоритету для виконання свого потоку. Натомість у Windows є таблиця пріоритетів, де вказано символьні позначення згрупованих номерів пріоритетів. У цьому кінцевий номер формується як основі цієї таблиці, а й у значеннях пріоритету батьківського процесу. Значення приховані за символьними константами через те, що Microsoft залишає за собою право їх змінити та користується ним від версії до версії своєї операційної системи. При створенні потік отримує нормальний рівень пріоритету. Його можна змінити функцією SetThreadPriority, що приймає два параметри: HANDLE hThread - дескриптор потоку, що змінюється, int nPriority - рівень пріоритету (з таблиці). За допомогою функції GetThreadPriority можна отримати поточний пріоритет, передавши до неї дескриптор потрібного потоку. Перед зміною пріоритету потоку його треба призупинити, це робиться функцією SuspendThread. Після зміни пріоритету потік треба віддати планувальнику для планування виконання функцією ResumeThread. Обидві функції одержують дескриптор потоку, з яким працюють. Всі описані операції крім припинення та відновлення застосовні і до процесів. Вони не можуть бути припинені/відновлені, оскільки не витрачають процесорний час, тому не плануються.

Уникнення гонок у Win32

У багатопотокових додатках треба скрізь наскільки можна використовувати атомарні - неподільні операції, виконання яких неспроможна встрявати інший потік. Такі функції Win32 API мають префікс Interlocked, наприклад, для інкременту змінної замість i++ використовувати InterlockedExchangeAdd(&i, 1). Крім операцій збільшення/зменшення, є операції для атомарного порівняння, але ми їх залишимо як твоє домашнє завдання.

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

CRITICAL_SECTION g_cs; DWORD WINAPI ThreadRun(PVOID pvParam) ( EnterCriticalSection(&g_cs); // Щось обчислюємо LeaveCriticalSection(&g_cs); return 0; )

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

AcquireSRWLockExclusive(PSRWLOCK SRWLock); // Записуємо значення ReleaseSRWLockExclusive(PSRWLOCK SRWLock);

З іншого боку, під час читання здійснюємо розшарований доступ:

AcquireSRWLockShared(PSRWLOCK SRWLock); // Читаємо значення ReleaseSRWLockShared(PSRWLOCK SRWLock);

Зверніть увагу: всі функції приймають проініціалізовану структуру SRWLock як параметр.
З допомогою умовних змінних зручно організувати залежність «постачальник - споживач» (див. декомпозицію з інформаційних потоків), тобто така подія має відбутися залежно від попереднього. У цьому механізмі використовуються функції SleepConditionVariableCS і SleepConditionVariableSRW, що служать для блокування критичної секції або структури тонкого блокування. Вони приймають три і чотири параметри відповідно: покажчик на умовну змінну, очікувану потоком, покажчик на критичну секцію чи SRWLock, застосовну синхронізації доступу. Наступний параметр- час (у мілісекундах) для очікування потоком виконання умови, якщо умова не буде виконана, функція поверне False; останній параметр другої функції – вид блокування. Щоб пробудити заблоковані потоки, потрібно з іншого потоку викликати функцію WakeConditionVariable або WakeAllConditionVariable. Якщо виконана в результаті виклику цих функцій перевірка підтвердить виконання умови, що передається як параметр даним функціям, потік буде пробуджено.

У наведеному описі ми познайомилися із загальними визначеннями механізмів семафор та м'ютекс. Зараз подивимося, як вони реалізовані у Win32. Створити семафор можна за допомогою функції CreateSemaphore. Їй передаються такі параметри: покажчик структуру PSECURITY_ATTRIBUTES, що містить параметри безпеки; максимальна кількість ресурсів, що обробляються додатком; кількість цих ресурсів, доступних спочатку; покажчик на рядок, що визначає ім'я семафору. Коли потік, що очікує семафору, хоче отримати доступ до ресурсу, що охороняється семафором, то wait-функція потоку опитує стан семафору. Якщо його значення більше 0, значить семафор вільний і його значення зменшується на 1, а потік планується на виконання. Якщо при опитуванні семафор зайнятий, його значення дорівнює 0, тоді викликаючий потік перетворюється на стан очікування. У момент, коли потік залишає семафор, викликається функція ReleaseSemaphore, у якій значення семафору збільшується на 1. М'ютекси, як і семафори, - об'єкти ядра. Функціонування мьютексів схоже на критичні секції Win32, з різницею в тому, що останні виконуються в режимі користувача. У кожний момент часу м'ютекс дозволяє виконуватись лише одному потоку і надає доступ лише до одного ресурсу. При цьому він дозволяє синхронізувати декілька потоків, зберігаючи ідентифікатор потоку, який захопив ресурс та лічильник кількості захватів. Щоб створити м'ютекс, можна скористатися функцією CreateMutex, її параметри аналогічні розглянутим вище. Коли очікування м'ютексу потоком успішно завершується, останній отримує монопольний доступ до захищеного ресурсу. Решта потоків, які намагаються звернутися до цього ресурсу, переходять у стан очікування. Коли потік, який займає ресурс, закінчує з ним працювати, він повинен звільнити виклик викликом функції ReleaseMutex. Ця функція зменшує лічильник рекурсії в м'ютексі на 1. Вибір механізму синхронізації, що використовується, багато в чому залежить від часу його виконання і коду, в якому він використовується.

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

Висновок

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

У цій статті спочатку ми розібралися з примітивами паралельного кодингу – загальними поняттями, потім розібралися, як вони виконані у конкретному API – Win 32 threads. Рамки статті не дозволили нам розглянути інші API для багатопотокового кодингу. Сподіватимемося, що ми ще матимемо можливість колись продовжити обговорення цієї потрібної теми.

Бажаю удачі, до зустрічі!

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

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

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

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

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

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

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

1. OpenMPвикористовується у паралельних системах із загальною пам'яттю (наприклад, сучасні комп'ютери з багатоядерними процесорами);

2. MPI (Message Passing Interface)є стандартом систем передачі повідомлень між процесами, що виконуються паралельно, використовується при розробці програм для суперкомп'ютерів;

3. POSIX Threadsє стандартом реалізації потоків виконання;

4. Операційна система Windows має вбудовану підтримку багатопотокових додатків для C++ лише на рівні API;

5. PVM (Parallel Virtual Machine)дозволяє об'єднувати різнорідні пов'язані мережею комп'ютери загальний обчислювальний ресурс.

Системи з урахуванням кількох комп'ютерів відносять до класу систем для розподілених обчислень. Такі рішення використовуються досить давно. Найбільш яскравий приклад технології розподілених обчислень – MPI (Message Passing Interface – інтерфейс передачі повідомлень). MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для величезної кількості комп'ютерних платформ. MPI надає програмісту єдиний механізм взаємодії гілок усередині паралельного застосування незалежно від машинної архітектури (однопроцесорні/багатопроцесорні із загальною/роздільною пам'яттю), взаємного розташування гілок (на одному процесорі або на різних).

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

А ось системи паралельного програмування для роботи на одній машині почали розвиватися відносно недавно. Звичайно, це не принципово нові ідеї, але саме з приходом багатоядерних систем на ринок персональних комп'ютерів, мобільних пристроїв, такі технології як OpenMP набули значного розвитку.

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

OpenMP (Open Multi-Processing) – це набір директив компілятора, бібліотечних процедур та змінних оточення, які призначені для програмування багатопотокових додатків на багатопроцесорних системах із загальною пам'яттю.

Розробку специфікації OpenMP ведуть кілька великих виробників обчислювальної техніки та програмного забезпечення, робота яких регулюється некомерційною організацією, званою OpenMP Architecture Review Board (ARB).

Перша версія з'явилася 1997 року, призначалася для мови Fortran. Для С/С++ версія розроблена 1998 року. 2008 року вийшла версія OpenMP 3.0. Інтерфейс OpenMP став однією з найпопулярніших технологій паралельного програмування. OpenMP успішно використовується як при програмуванні суперкомп'ютерних систем з великою кількістю процесорів, так і в настільних системах користувача або, наприклад, в Xbox 360.

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

Завдання, виконувані потоками паралельно, як і дані, необхідні виконання цих завдань, описуються з допомогою спеціальних директив препроцесора відповідної мови - прагм. Наприклад, ділянка коду на мові Fortran, яка повинна виконуватися кількома потоками, кожен з яких має свою копію змінної N, передує наступній директиві: !$OMP PARALLEL PRIVATE(N)

Кількість створюваних потоків може регулюватися як самою програмою з допомогою виклику бібліотечних процедур, і ззовні, з допомогою змінних оточення.

Ключовими елементами OpenMP є

1. конструкції для створення потоків (директива parallel);

2. конструкції розподілу роботи між потоками (директиви DO/for та section);

3. конструкції для управління роботою з даними (вирази shared і private визначення класу пам'яті змінних);

4. конструкції для синхронізації потоків (директиви critical, atomic і barrier);

5. процедури бібліотеки підтримки часу виконання (наприклад, omp_get_thread_num);

6. змінні оточення (наприклад, OMP_NUM_THREADS).

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

Число потоків у групі, що виконуються паралельно, можна контролювати кількома способами. Один із них - використання змінної оточення OMP_NUM_THREADS. Інший спосіб – виклик процедури omp_set_num_threads(). Ще один спосіб - використання виразу num_threads у поєднанні з директивою parallel.

У цій програмі два масиви (a та b) складаються паралельно десятьма потоками.

#include

#include

int main(int argc, char *argv)

float a[N], b[N], c[N];

omp_set_dynamic(0); // заборонити бібліотеці openmp змінювати кількість потоків під час виконання

omp_set_num_threads(10); // встановити число потоків 10

// ініціалізуємо масиви

for (I = 0; I< N; i++)

// обчислюємо суму масивів

#pragma omp parallel shared(a, b, c) private(i)

for (I = 0; I< N; i++)

c[i] = a[i] + b[i];

printf (“%f\n”, c);

Цю програму можна скомпілювати, використовуючи gcc-4.4 та новіші з прапором –fopenmp. Очевидно, якщо прибрати підключення заголовного файлу omp.h, а також виклики функції налаштування OpenMP, програму можна скомпілювати на будь-якому компіляторі як звичайну послідовну програму.

OpenMP підтримується багатьма сучасними компіляторами:

1. Компілятори Sun Studio підтримують офіційну специфікацію – OpenMP 2.5 – з покращеною продуктивністю під ОС Solaris; підтримка Linuxзаплановано на наступний реліз.

2. Visual C++ 2005 і вище підтримує OpenMP у редакціях Professional та Team System.

3. GCC 4.2 підтримує OpenMP, а деякі дистрибутиви (такі як Fedora Core 5 gcc) включили підтримку у свої версії GCC 4.1.

4. Intel C++ Compiler, включаючи версію Intel Cluster OpenMP для програмування в системах із розподіленою пам'яттю.

Message Passing Interface (MPI,інтерфейс передачі повідомлень) - програмний інтерфейс (API) передачі інформації, який дозволяє обмінюватися повідомленнями між процесами, виконують одне завдання. Розроблений Вільямом Гроуппом, Евіном Ласком (англ.) та іншими.

MPI є найбільш поширеним стандартом інтерфейсу обміну даними в паралельному програмуванні, існують його реалізації для великої кількості комп'ютерних платформ. Використовується для розробки програм для кластерів і суперкомп'ютерів. Основним засобом комунікації між процесами MPI є передача повідомлень один одному. Стандартизацією MPI займається MPI Forum. У стандарті MPI описаний інтерфейс передачі повідомлень, який має підтримуватися як у платформі, і у додатках користувача. В даний час існує велика кількість безкоштовних та комерційних реалізацій MPI. Існують реалізації для мов Фортран 77/90, Сі та Сі++.

Насамперед MPI орієнтований на системи з розподіленою пам'яттю, тобто коли витрати на передачу даних великі, тоді як OpenMP орієнтований на системи із загальною пам'яттю (багатоядерні із загальним ЕШем). Обидві технології можуть використовуватися спільно, щоб оптимально використовувати багатоядерні системи в кластері.

Перша версія MPI розроблялася 1993-1994 року, і MPI 1 вийшла 1994-го.

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

передача та отримання повідомлень між окремими процесами;

колективні взаємодії процесів;

взаємодії у групах процесів;

реалізація топологій;

динамічне породження процесів та управління процесами;

односторонні комунікації (Get/Put);

паралельне введення та виведення;

розширені колективні операції (процеси можуть виконувати колективні операції усередині одного комунікатора, а й у кількох комунікаторів).

Версія MPI 2.1 вийшла на початку вересня 2008 року.

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

1. відправник - ранг (номер групи) відправника повідомлення;

2. одержувач – ранг одержувача;

3. ознака - може використовуватися поділу різних видів повідомлень;

4. комунікатор – код групи процесів.

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

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

Нижче наведено приклад програми обчислення числа π мовою C з використанням MPI:

// Підключення необхідних заголовків

#include

#include

// Підключення заголовного файлу MPI

#include «mpi.h»

// Функція для проміжних обчислень

double f(double a)

return (4.0/(1.0+ a*a));

// Головна функціяпрограми

int main(int argc, char **argv)

// Оголошення змінних

int done = 0, n, myid, numprocs, I;

double PI25DT = 3.141592653589793238462643;

double mypi, pi, h, sum, x;

double startwtime = 0.0, endwtime;

char processor_name;

// Ініціалізація підсистеми MPI

MPI_Init(&argc, &argv);

// Отримати розмір комунікатора MPI_COMM_WORLD

// (Загальна кількість процесів у рамках завдання)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Отримати номер поточного процесу у межах

// комунікатора MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Виведення номера потоку у загальному пулі

fprintf(stdout, “Process %d of %d є %s\n”, myid,numprocs,processor_name);

// кількість інтервалів

fprintf(stdout, “Enter number of intervals: (0 quits) “);

if(scanf(“%d”,&n) != 1)

fprintf(stdout, “No number entered; quitting\n”);

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1.0/(double) n;

// Обчислення точки, закріпленої за процесом

for(I = myid + 1; (I<= n) ; I += numprocs)

x = h * ((double) I - 0.5);

// Скидання результатів з усіх процесів та додавання

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Якщо це головний процес, висновок отриманого результату

printf(“PI is approximately %.16f, Error is %.16f\n”, pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf(“wall clock time = %f\n”, endwtime-startwtime);

// Звільнення підсистеми MPI

Найбільш поширеними реалізаціями MPI на сьогоднішній день є:

MPICH - найпоширеніша безкоштовна реалізація, працює на UNIX-системах та Windows NT

LAM/MPI – ще одна безкоштовна реалізація MPI. Підтримує гетерогенні конфігурації, LAM (http://www.lam-mpi.org) підтримує гетерогенні конфігурації, пакет Globus та задовольняє IMPI (Interoperable MPI).

Підтримуються різноманітні комунікаційні системи (зокрема Myrinet).

WMPI – реалізація MPI для Windows

MPI/PRO for Windows NT – комерційна реалізація для Windows NT

Intel MPI – комерційна реалізація для Windows / Linux

Microsoft MPI входить до складу Compute Cluster Pack SDK. Заснований MPICH2, але включає додаткові засоби управління завданнями. Підтримується специфікація MPI-2.

HP-MPI – комерційна реалізація від HP

SGI MPT – платна бібліотека MPI від SGI

Mvapich - безкоштовна реалізація MPI для Infiniband

Open MPI – безкоштовна реалізація MPI, спадкоємець LAM/MPI

Oracle HPC ClusterTools – безкоштовна реалізація для Solaris SPARC/x86 та Linux на основі Open MPI

MPJ - MPI для Java

POSIX Threads- стандарт POSIX реалізації потоків виконання, що визначає API для створення та управління ними.

Бібліотеки, що реалізують цей стандарт (і функції цього стандарту), зазвичай називаються Pthreads (функції мають приставку pthread_). Хоча найбільш відомі варіанти для Unix-подібних операційних систем, таких як Linux або Solaris, але є й реалізація для Microsoft Windows (Pthreads-w32)

Pthreads визначає набір типів і функцій мовою програмування Сі. Заголовний файл – pthread.h.

Типи даних:

1. pthread_t - дескриптор потоку;

2. pthread_attr_t – список атрибутів потоку.

Функції керування потоками:

1. pthread_create() – створення потоку;

2. pthread_exit() - завершення потоку (має викликатися функцією потоку при завершенні);

3. pthread_cancel() – скасування потоку;

4. pthread_join() – заблокувати виконання потоку до припинення іншого потоку, вказаного у виклику функції;

5. pthread_detach() – звільнити ресурси займані потоком (якщо потік виконується, то звільнення ресурсів відбудеться після його завершення);

6. pthread_attr_init() – ініціалізувати структуру атрибутів потоку;

7. pthread_attr_setdetachstate() – вказати системі, що після завершення потоку вона може автоматично звільнити ресурси, які займає поток;

8. pthread_attr_destroy() – звільнити пам'ять від структури атрибутів потоку (знищити дескриптор).

Функції синхронізації потоків:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Приклад використання потоків мовою C:

#include

#include

#include

#include

static void wait_thread(void)

time_t start_time = time(NULL);

while (time(NULL) == start_time)

/* не виключає chew CPU slices for up to one second. */

static void *thread_func(void *vptr_args)

for (I = 0; I< 20; i++)

fputs(“b\n”, stderr);

pthread_t thread;

if (pthread_create(&thread, NULL, thread_func, NULL) != 0)

return EXIT_FAILURE;

for (I = 0; I< 20; i++)

if (pthread_join(thread, NULL)! = 0)

return EXIT_FAILURE;

return EXIT_SUCCESS;

Подана програма використовують два потоки, що друкують у консоль повідомлення, один, що друкує "a", другий - "b". Виведення повідомлень змішується внаслідок перемикання виконання між потоками або одночасного виконання на мультипроцесорних системах.

Програма C створює один новий потік для друку "b", а основний потік друкує "a". Основний потік (після друку "aaaaa….") чекає завершення дочірнього потоку.

Контрольні питання

1. Що таке паралельна програма?
2. У чому різниця між процесом та потоком виконання?
3. Чи може програма створити 5 потоків під час роботи на чотириядерному процесорі?
4. Які особливості паралельних програм з пам'яттю, що розділяється?
5. Які існують програмні засоби розробки паралельних програм?
6. Чому велике поширення під час створення програм для ПК отримав саме OpenMP, а чи не, наприклад, MPI?