Введення в паралельні обчислення c
2. Використання паралелізму
Припустимо тепер, що ми навчилися якимось чином будувати та досліджувати інформаційну історію виконання програми. Виділивши в ній безліч інформаційно незалежних операцій, приходимо до питання: яким же чином розподіляти ці множини між процесорами або іншими обробними пристроями?
Досить очевидним способом буде наступний. Зауважимо в інформаційній історії ті операції, які залежать тільки від зовнішніх даних програми та скажемо, що такі операції належать до першого ярусу інформаційної історії. На другий ярус помістимо операції, що залежать тільки від операцій першого ярусу та зовнішніх даних тощо. Розподіливши таким чином операції інформаційної історії, отримуємо її вид, який називається ярусно-паралельною формою програми. Кількість ярусів ярусно-паралельної форми називається довжиною критичного шляху. По побудові операції, які потрапили однією ярус, що неспроможні перебувати щодо інформаційної залежності, отже, можуть бути виконані одночасно. Таким чином, процес отримання паралельної програми може бути наступним: спочатку розподіляємо між процесорами операції першого ярусу, після завершення -операції другого ярусу і т.д. Оскільки будь-яка операція n-го ярусу залежить хоча б від однієї операції (п-1)-го ярусу, то її не можна почати виконувати раніше, ніж завершиться виконання операцій попереднього ярусу, а значить, ярусно-паралельна форма є в певному сенсі максимально паралельною реалізацію програми. У цьому довжина критичного шляху характеризує кількість паралельних кроків, необхідні її виконання.
Однак ярусно-паралельна форма майже ніколи не використовується для практичногорозпаралелювання програм. Причиною цього є те, що описаний спосіб розпаралелювання погано узгоджений як з конструкціями реальних мов програмування, так і з архітектурними особливостями сучасних комп'ютерів. Щоб переконатися в цьому, можете спробувати сконструювати таким способом паралельну реалізацію практично будь-якого ал-
20 і оцінити як складність написання такої програми, так і кількість необхідних комунікацій між процесорами.
Насправді набагато частіше використовуються інші способи розпаралелювання, що використовують характерні особливості найбільш поширених мов програмування. Так, найпростішим варіантом розподілу робіт між процесорами є приблизно наступна конструкція (великоблочне розпаралелювання):
При цьому передбачається, що кожен процесор якимось чином може отримати унікальний номер, привласнити його змінною MyProc і використовувати надалі для отримання ділянки коду незалежного виконання. Таким чином, у наведеному прикладі операції у перших фігурних дужках будуть виконані лише процесором з номером 0, операції у других фігурних дужках - процесором номером K і т.д. При цьому, природно, необхідно, щоб одночасно різні процесори могли виконувати лише блоки інформаційно незалежних операцій, що може вимагати операцій синхронізації процесорів, а також за потреби потрібно забезпечувати обмін даними між процесорами.
Однак далеко не завжди вдається виділити в програмі досить велику кількість блоків незалежних операцій, а значить, при значній кількості процесорів у комп'ютері, частина з них простоюватиме. Тому поряд із попереднім способом використовують також більш низькорівневе розпаралелювання. Якпоказує практика, найбільший ресурс паралелізму у програмах зосереджений у циклах. Тому найпоширенішим способом розпаралелювання є той чи інший розподіл ітерацій циклів. Якщо між ітераціями деякого циклу немає інформаційних залежностей, їх можна тим чи іншим способом роздати різним процесорам для одночасного виконання. Умовно це може бути виражено приблизно такою конструкцією:
for (i = 0; i Попередня 10 11 12 13 14 15 .. 28 >> Наступна