трспо. Лекція Колективні операції обміну повідомленнями в mpi
 Скачать 3.37 Mb.
|
|
5. Ефективність використання OpenMP 5.1 Коли використовувати OpenMP? Знати, коли використовувати технологію OpenMP, не менш важливо, ніж уміти з нею працювати. Перед використанням OpenMP слід звернути увагу на наступне: 1. Цільова платформа є многопроцессорной або многоядерной. Якщо додаток повністю використовує ресурси одного ядра або процесора, то, зробивши його багатопотоковим за допомогою OpenMP, ви майже напевно підвищите його швидкодію. 2. Додаток має бути кросплатформним. OpenMP - багатоплатформовий і широко підтримуваний API. А так як він реалізований на основі директив pragma, додаток можна скомпілювати навіть за допомогою компілятора, який не підтримує стандарт OpenMP. 3. Виконання циклів потрібно распараллелить. Весь свій потенціал OpenMP демонструє при організації паралельного виконання циклів. Якщо в додатку є тривалі цикли без залежностей, OpenMP - ідеальне рішення. 4. Перед випуском додатки потрібно підвищити його швидкодію. Так як технологія OpenMP не вимагає переробки архітектури додатку, вона прекрасно підходить для внесення в код невеликих змін, що дозволяють підвищити його швидкодію. 5. У той же час слід визнати, що OpenMP - не панацея від усіх бід. Ця технологія орієнтована в першу чергу на розробників високопродуктивних обчислювальних систем і найбільш ефективна, якщо код включає багато циклів і працює з розділяються масивами даних. Створення як звичайних потоків, так і паралельних регіонів OpenMP має свою ціну. Щоб застосування OpenMP стало вигідним, виграш в швидкості, що забезпечується паралельним регіоном, повинен перевершувати витрати на створення групи потоків. У версії OpenMP, реалізованої в Visual C ++, група потоків створюється при вході в перший паралельний регіон. Після завершення регіону група потоків призупиняється, поки не знадобиться знову. За лаштунками OpenMP використовує пул потоків Windows. Рис. 2 ілюструє приріст швидкодії простої програми, наведеної на початку лекції, який досягається завдяки OpenMP на двопроцесорних комп'ютері при різній кількості ітерацій. Максимальний приріст швидкодії становить приблизно 1,7 від вихідного, що типово для двопроцесорних систем. Рис. 2. Порівняння часу послідовного і паралельного виконання коду в двухпроцессорной системі На даному графіку вісь y представляє відношення часу послідовного виконання коду на час паралельного виконання того ж коду. Зверніть увагу, що паралельна версія наздоганяє за швидкодією послідовну приблизно при 5000 ітерацій, але це майже що найгірший сценарій. Більшість паралельних циклів будуть виконуватися швидше послідовних навіть при значно меншій кількості ітерацій. Це залежить від обсягу роботи, виконуваної на кожній ітерації. Як би там не було, цей графік показує, наскільки важливо оцінювати продуктивність ПО. Саме по собі застосування OpenMP не гарантує, що швидкодія вашого коду підвищиться. OpenMP-директиви pragma прості у використанні, але не дозволяють отримувати детальні відомості про помилки. Якщо ви пишете критично важливий додаток, яке повинно визначати помилки і коректно відновлювати нормальну роботу, від OpenMP, мабуть, слід відмовитися (по крайней мере, поки). Наприклад, якщо OpenMP не може створити потоки для паралельних регіонів або критичну секцію, поведінка програми стає невизначеним. Ще одна ситуація, в якій слід зберігати пильність, має місце при використанні потоків Windows разом з потоками OpenMP. Потоки OpenMP створюються на основі потоків Windows, тому вони прекрасно працюють в одному процесі. Але OpenMP нічого не знає про потоках Windows, створених іншими модулями. З цього випливають дві проблеми: по-перше, виконуюче середовище OpenMP не веде облік інших потоків Windows, а по-друге, методи синхронізації OpenMP НЕ синхронізують потоки Windows, тому що вони не входять до груп потоків. Пастки, в які можна потрапити при використанні OpenMP Хоча використовувати OpenMP зовсім нескладно, деякі моменти все ж вимагають до себе підвищеної уваги. Наприклад, індексна змінна самого зовнішнього паралельного циклу for є приватною, а індексні змінні вкладених циклів for за замовчуванням загальні. При роботі з вкладеними циклами зазвичай потрібно, щоб індекси внутрішніх циклів були приватними. Використовуйте для цього розділ private. Розробляючи програми OpenMP, слід бути обережним при генерації виключень C ++. Якщо додаток генерує виняток в паралельному регіоні, воно повинно бути оброблено в тому ж регіоні тим же потоком. Інакше кажучи, виключення не повинно покинути регіон. Як правило, всі винятки, які можуть бути згенеровані в паралельному регіоні, слід перехоплювати. Якщо не перехопити виняток в тому ж паралельному регіоні, додаток швидше за все потерпить крах. Щоб можна було відкрити структурований блок, вираз #pragma omp <директива> [розділ] має завершуватися символом нового рядка, а не фігурною дужкою. Директива, що закінчується фігурною дужкою, призведе до помилки компіляціі1: // Погано #pragma omp parallel { // Помилка компіляції } // Добре #pragma omp parallel { // Код } Налагоджувати додатка OpenMP в середовищі Visual Studio 2005 іноді важко. Зокрема, певні незручності пов'язані з входом в паралельний регіон і / або з виходом з нього натисканням клавіші F10 / F11. Це пояснюється тим, що компілятор генерує додатковий код для виклику виконуючого середовища і груп потоків. Отладчик про це не знає, тому те, що ви побачите, може здатися вам дивним. Рекомендуєтся встановити точку переривання в паралельному регіоні і натиснути F5, щоб досягти її. Щоб вийти з паралельного регіону, встановіть точку переривання поза такого регіону і натисніть F5. При знаходженні всередині паралельного регіону в вікні Threads Window відладчика буде відображатися інформація про потоках, які виконуються в групі потоків. Ідентифікатори цих потоків будуть відповідати НЕ потокам OpenMP, а лежачим в їх основі потоками Windows. В даний час використовувати з OpenMP оптимізацію, яка визначається профілем (Profile Guided Optimization, PGO), не можна. На щастя, технологія OpenMP заснована на директивах pragma, тому ви можете скомпілювати свій додаток з параметром / openmp і з PGO і дізнатися, який підхід більш ефективний. 5.2 OpenMP і .NET Високопродуктивні обчислення мало у кого асоціюються з .NET, але в Visual C ++ 2005 ця ситуація поліпшена. Особливо варто наголосити на тому, що можлива спільна робота OpenMP з керованим C ++ - кодом. Для цього забезпечена сумісність параметра / openmp с / clr і / clr: OldSyntax. Тобто можна використовувати OpenMP для паралельного виконання методів .NET- типів. Зараз параметр / openmp несумісний ні з / clr: safe, ні з / clr: pure, але планується виправити це. Необхідно згадати одне важливе обмеження, пов'язане із застосуванням OpenMP в керованому коді. Додаток, в якому задіяні інструментарій OpenMP, слід використовувати тільки в одному домені додатку. При завантаженні іншого AppDomain в процес з уже завантаженої виконуючою середовищем OpenMP додаток може потерпіти крах. OpenMP – проста, але потужна технологія розпаралелювання програм. Вона дозволяє реалізувати паралельне виконання як циклів, так і функціональних блоків коду. Вона легко інтегрується в існуючі програми і включається / вимикається одним параметром компілятора. OpenMP дозволяє більш повно використовувати обчислювальну потужність багатоядерних процесорів. Рекомендується ознайомитися зі специфікацією OpenMP. Лекція 3. Концепції потокової обробки План лекції: 1. Визначення програмних потоків 2. Поточна обчислювальна модель 3. Конструкції паралельного програмування 1. Визначення програмних потоків Програмний потік – це окрема послідовність взаємозв’язаних між собою команд, яка виконується незалежно від інших послідовностей команд. Кожна програма має хоча б один програмний потік – головний. Цей потік ініціалізує програму та починає виконання перших команд. Він може створювати інші потоки, які будуть виконувати різні задачи. Кожен програмний потік підтримує свій поточний машинний стан, тобто адресу виконуваної команди, адреси та значення даних, які знаходяться в регістрах процесора або в пам’яті. Щоб зрозуміти, яким чином реалізувати потокову обробку в своєму додатку, потрібно добре знати наступні моменти: • структуру додатку та підходи до його розробки; • потоковий програмний інтерфейс АРІ; • компілятор або середовище виконання додатку; • цільові апаратні платформи, на яких буде виконуватися додаток. Кожен потік повинен мати свій стековий простір. Управління стеками звичайно виконує операційна система. На рис. 3.1 наведено типовий стек багатопотокового процесу. Рисунок 3.1. Вигляд стеку багатопотокового процесу Розмір стеку за замовчуванням в різних операційних системах відрізняється. Тому у деяких системах створення великої кількості потоків може значно знизити продуктивність. Після створення потік знаходиться в одному з чотирьох станів: • готовність; • виконання; • очікування; • завершення. На рис. 3.2. наведена діаграма станів потоку. Рисунок 3.2. Діаграма станів потоку Як показано на рисунку, кожен створений потік буде знаходитися в стані готовності. Після цього, коли новий потік виконує команди він буде знаходитися в стані виконання. Якщо потік потребує якогось ресурсу, або його перериває інший потік, він переходить в стан очікування. При закінченні роботи потоку, він або завершується, або переходить в стан готовності. Після завершення програми головний та допоміжні потоки також завершуються. Процеси та потоки представляють різні рівні виконавчого механізму системи. Для того, щоб вірно оцінити можливості поточної обробки, важливо зрозуміти вплив потоків на компоненти системи. 2. Поточна обчислювальна модель Поточну обчислювальну модель (рис. 3.3) складають три рівня поточної обробки: • Потоки рівня користувача – створюються і керуються із додатків; • На рівні ядра в операційній системі реалізуються більшість програмних потоків; • Апаратними потоки – створюються для виконавчих ресурсів апаратного забезпечення. Рисунок 3.3. Поточна обчислювальна модель Потоки виконання ядра відносяться до «легких» одиниць планування ядра. Всередині кожного процесу існує принаймні один потік виконання ядра. Якщо в рамках процесу можуть існувати кілька потоків виконання ядра, то вони спільно використовують спільну пам'ять і файл ресурсів. Якщо процес виконання планувальника операційної системи є пріоритетним, то потоки виконання ядра теж є пріоритетно багатозадачними. Потоки виконання ядра не мають власних ресурсів, за винятком стека викликів, копії регістрів процесора, включаючи лічильник команд, і локальну пам'ять потоку виконання (якщо вона є). Ядро може призначити по одному потоку виконання для кожного логічного ядра системи (оскільки кожен процесор поділяє сам себе на декілька логічних ядер, якщо він підтримує багатопоточність, або підтримує лише одне логічне ядро на кожне фізичне ядро, якщо не підтримує багатопоточність), а може виконувати свопінг заблокованих потоків виконання. Однак потоки виконання ядра вимагають набагато більше часу, ніж потрібно на свопінг настроюваних потоків виконання. Потоки виконання іноді реалізуються в користувацькому просторі бібліотек, в цьому випадку вони називаються призначеними для користувача потоками виконання. Ядро не знає про них, так що вони управляються і плануються в користувацькому просторі. У деяких реалізаціях користувальницькі потоки виконання ґрунтуються на кількох верхніх потоках виконання ядра, щоб використовувати переваги багатопроцесорних машин (моделі M:N). Тут під терміном «потік виконання» за замовчуванням (без кваліфікатора «ядра» або «користувацький») мається на увазі «потік виконання ядра». Користувальницькі потоки виконання, реалізовані з допомогою віртуальних машин, називають «зеленими потоками виконання». Користувальницькі потоки виконання, як правило, можна швидко створювати, і ними легко керувати, але вони не можуть використовувати переваги багатопоточності і багатопроцесорності. Вони можуть блокуватися, якщо всі пов'язані з ним потоки виконання ядра зайняті, навіть якщо деякі користувальницькі потоки готові до запуску. Апаратний потік -– це окрема частина обладнання, яка виконує код. Десять років тому в окремо взятому процесорі був всього один апаратний потік, а більша кількість таких потоків зустрічалася лише в комп'ютерах з декількома фізично незалежними процесорами, підключеними до окремих портів на материнській платі. Однак два нововведення, а саме багатоядерні процесори і гиперпоточность, ускладнили взаємодію між потоками і апаратною частиною. Багатоядерний процесор – це фактично кілька процесорів на одній кремнієвій схемі. Гіперпоточность, також іменована одночасна багатопоточність (SMT), все ускладнює ще більше. На багатопотоковому ядрі певні елементи процесора дублюються (іноді копій ще більше, однак найчастіше використовується саме дублювання). В такому випадку лише одна частина процесора може проводити, скажімо, ділення з плаваючою точкою, але при цьому існують два комплекти регістрів і логіки для набору команд. Серед регістрів є лічильник команд, стежить за виконанням і поточним робочим станом коду, так що два набору регістрів дають можливість одночасно запускати два фрагменти коду на одному ядрі. Іншими словами, гіперпоточность дозволяє одному ядру мати два апаратних потоки. Два контексти виконання змушені спільно використовувати ресурси – вони не можуть одночасно виконувати ділення з плаваючою точкою, так як цим займається лише одна частина процесора. Але, якщо одному з апаратних потоків потрібно ділити, а інший зайнятий перемножуванням чисел, їм, як правило, вдається робити це паралельно, оскільки дані операції виконують різні частини ядра. 3. Конструкції паралельного програмування До конструкцій паралельного програмування відносятся: - взаємовиключення, умовна синхронізація, примітиви синхронізації; - критичні секції, види блокувань. Паралельна програма містить кілька процесів, працюючих спільно над виконанням деякої задачі. Кожен процес – це послідовна програма, а точніше – послідовність операторів, що виконуються один за іншим. Послідовна програма має один потік управління, а паралельна – кілька. Спільна робота процесів паралельної програми здійснюється за допомогою їх взаємодії. Взаємодія програмується з застосуванням поділюваних змінних або пересилання повідомлень. Якщо використовуються колективні змінні. один процес здійснює запис у змінну, що зчитується іншим процесом. При пересиланні повідомлень один процес відправляє повідомлення, яке отримує інший. При будь-якому вигляді взаємодії процесів необхідна взаємна синхронізація. Існують два основних види синхронізації взаємне виключення і умовна синхронізація. Рисунок 3.4. Взаємне виключення з використанням критичної секції Взаємне виключення забезпечує, щоб критичні секції операторів не виконувалися одночасно. Умовна синхронізація затримує процес до тих пір, поки не виконається певну умову. Апаратні методи організації взаємовиключення. В чому основна проблема програмних методів взаємовиключення? Неможливо гарантувати нерозривність виконання окремих дій: програма може перерватися в будь-який момент і можливі довільні послідовності операцій у паралельній програмі (недетерминизм). Одне з рішень – введення в апаратуру (або в системний шар) спеціальних конструкцій, що володіють властивістю нерозривності (атомарности). Примітиви синхронізації. Семафори – об'єкт, що обмежує кількість потоків, які можуть увійти в заданий ділянку коду. Визначення введено Эдсгером Дейкстрой. Семафори використовуються при передачі даних через поділювану пам'ять. М'ютекси – це найпростіші двійкові семафори, які можуть знаходитися в одному з двох станів – незаблокованому або заблокованому (відкритім і закритім відповідно). Коли який-небудь потік, що належить будь-якого процесу, стає власником об'єкта mutex, останній переводиться в заблокований стан для інших потоків. Рисунок 3.5. Взаємодія потоків з використанням семафора і м’ютекса Критична секція(CriticalSection) це ділянка коду, в якому потік (thread) отримує доступ до ресурсу (наприклад змінна), який доступний з інших потоків. Об'єкт критична секція забезпечує синхронізацію. Спінлок (англ. Spinlock – циклічна блокування) — низькорівневий примітив синхронізації с использованием циклов активного ожидания (без перевода в блоктрованное состояние), застосовуваний в багатопроцесорних системах для реалізації взаємного виключення. Монітори – у мовах програмування, високорівневий механізм взаємодії і синхронізації процесів, що забезпечує доступ до неподіляємим ресурсам. Підхід до синхронізації двох або більше комп'ютерів, що використовують спільний ресурс, зазвичай апаратуру або набір змінних. Умовна змінна – примітив синхронізації, що забезпечує блокування одного або декількох потоків до моменту надходження сигналу від іншого потоку про виконання деякої умови або до закінчення максимального проміжку часу очікування. Умовні змінні використовуються разом з асоційованим мьютексом і є елементом деяких видів моніторів. Readers-Writeslock (RWLock)– необхідний для асиметричної схеми доступу до ресурсу. Блокування – це механізм синхронізації що дозволяє забезпечити винятковий доступ до поділюваного ресурсу між кількома потоками. Блокування один із способів забезпечити політику управління розпаралелюванням. Види блокувань. В основному, використовується м'яка блокування, при цьому передбачається, що кожен потік намагається отримати блокування перед доступом до відповідного поділюваному ресурсу. В деяких системах надається механізм обов'язкового блокування, при його використанні спроба несанкціонованого доступу до заблокованого ресурсу буде перервана, через створення виключення в потоці, який намагався отримати доступ. Семафор найпростіший тип блокування. З точки зору доступу до даних не робиться ніяких відмінностей між режимами доступу: загальним (тільки читання) або ексклюзивним (читання і запис). В режимі загального доступу кілька потоків можуть запросити для блокування доступу до даних у режимі тільки читання. Також використовується ексклюзивний режим доступу в алгоритмах оновлення та видалення. Типи блокувань розрізняють стратегії блокування продовження виконання потоку. У більшості реалізацій запит блокування перешкоджає подальшому виконанню потоку поки не з'явиться доступ до заблокованої ресурсу. Спинлок це блокування яка очікує у циклі поки не з'явиться доступ. Така блокування дуже ефективна якщо потік очікує блокування незначний інтервал часу, це дозволяє уникнути надмірної перепланування потоків. Витрати на очікування доступу будуть значними при тривалому утриманні блокування одним з потоків. Для ефективної реалізації механізму блокування потрібна підтримка на апаратному рівні. Апаратна підтримка може бути реалізована у вигляді однієї або декількох атомарних операціях таких як "test-and-set", "fetch-and-add" або "compare-and-swap". Такі інструкції дозволяють без переривань перевірити, що блокування вільна і якщо це так то зайняти блокування. В однопроцесорних системах є можливість виконувати інструкції без апаратних переривань використовуючи спеціальні інструкції або префікси інструкції, які тимчасово відключають переривання, але такий підхід не працює в багатопроцесорних системах зі спільною пам'яттю. Повна підтримка блокувань в багатопроцесорному оточенні може вимагати досить складною апаратної і програмної підтримки, зі значними проблемами синхронізації. |