Тема 2. Паралелізм обчислень. Архітектури паралельних ос Лекція 2. Види і засоби обчислень

Необхідність побудови ПОС. Класи задач; структурний та алгоритмічний (процедурний) підходи до вирішення задач, приклади; рішення задач в реальному масштабі часу.

Труднощі на шляху до реалізації паралелізму: закон Гроша; гіпотеза Мінського. Закон Амдала. Проблеми. Перспективи. [2, с. 7-23].

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

Приклад 2.1 [7]. Для того, щоб усвідомити складність вирішуваних на практиці задач, розглянемо конкретну предметну область – процес видобутку нафти. Нехай є підземний нафтовий резервуар з деяким числом пробурених свердловин: за однією на поверхню відкачують нафту, за іншими в резервуар закачується вода. Задачая полягає в оцінці запасів нафти і в розрахунку оптимального числа необхідних додаткових свердловин, для чого необхідно промоделювати ситуацію в цьому резервуарі.

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

10⁶ (точок сітки)*10 (функцій)*500 (арифметичних операцій)*500 (кроків по часу) = 2.5*10¹².

2,5 трильйонів арифметичних операцій для виконання лише одного розрахунку! А зміна параметрів моделі? А відстеження поточної ситуації при зміні вхідних даних? Подібні розрахунки необхідно робити багато разів, що накладає дуже жорсткі вимоги на продуктивність використовуваних обчислювальних систем.

В [7] наведені й інші приклади областей людської діяльності, які вимагають застосування високопродуктивних ВС. Все це визначає необхідність побудови паралельних ОС (ПОС). Ефект, що досягається за рахунок застосування ПОС, зростає при збільшенні масштабів обробки даних, тобто концентрації по можливості великих обсягів даних і процесів їх обробки в рамках однієї технічної системи.

Можна виділити наступні класи розв'язуваних СОД задач: науково-технічні розрахунки, проектування, моделювання, прогнозування, адміністративне управління, управління виробництвом (АСУВ) і технологічними процесами (АСУТП), багато з яких працюють в реальному масштабі часу, тобто в темпі протікання процесів¹.

Рішення задачи з позиції теорії множин полягає в знаходженні відображення множини вхідних даних X на множину розв'язків Y (вихідних даних). Відображення X Y може бути отримано двома принципово різними підходами:

1) для вирішення використовується множина {Q_i} найпростіших операторів, послідовно застосування яких призводить до вирішення задачи;

2) для вирішення використовуються рішаючі елементи (РЕ), які виконують операції компонент структури математичного опису задачі, наприклад, інтегрування деякої змінної.

Ці підходи називаються відповідно алгоритмічним (процедурним) і структурним. Перший реалізується цифрової обчислювальної машиною (ЦОМ), при цьому інформація представляється в дискретній формі, а другий – аналогової обчислювальної машиною (АВМ), при цьому інформація представляється в безперервній (аналоговій) формі. Рішення на АВМ виходить без затримок на обчислення за рахунок одночасного вирішення задачи на РЕ.

Приклад 2.2. Нехай потрібно обчислити певний інтеграл від функції f(x) на відрізку [a, b]. Рішення може бути отримано методом прямокутників [8], при якому інтеграл замінюється сумою площ прямокутників. Кожен прямокутник апроксимує криву f(x) на відрізку [х_і-1, х_і], при цьому в якості його висоти береться значення ординати кривої в середині відрізка, що дорівнює y_i=f(x_i-1+h/2). Тоді вихідний інтеграл може бути наближено (чим більше n, тим точніше) представлений виразом:

.

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

Приклад 2.3. Розглянемо застосування АВМ для побудови моделі генератора сіну-соиди, тобто пристрою, що реалізує функцію y(x)=sinx. В даному випадку x – час, у – вихідний сигнал пристрою, представлений напругою.

Визначимо диференціальне рівняння (ДУ), рішенням якого є задана функція. Продиференціюємо функцію у двічі: y’ = cosx, y’’ = -sinx. Неважко бачити, що y’’ = - y. Це і є шукане ДУ, в якому рівність має місце в будь-який момент часу. Для вирішення ДУ необхідні 2 початкових умови: у₀=y(0) = 0, y’₀= y’(0) = 1.

Складемо структурну схему аналогової моделі генератора синусоїди² .

Для цього виберемо точку А і будемо вважати, що в ній є змінна y’’. Двічі її проинтегрировав за допомогою РЕ – інтеграторів 1 і 2, отримаємо шукану змінну, тобто рішення ДУ. Однак залишилося вирішити питання, як в точку А може потрапити змінна y’’. Для цього звернемося до ДУ, з якого видно, що y’’ може бути отримана з y. Ясно, що проинвертировав змінну у, отримаємо y’’. Замкнувши вихід схеми з її входом (т. А) ланцюгом зворотного зв'язку через РЕ інвертор 3, отримаємо структурну схему моделі генератора (рис. 2.1). На входах інтеграторів і інвертора стоять масштабні коефіцієнти.

Рішення ДУ в ідеальному випадку виходить миттєво, так як РЕ не витрачають час на перетворення вхідної інформації, як це відбувається при обчисленнях на дискретних структурах, бо це – природний фізичний (в даному випадку – електричний) процес. Так, на виходах інтеграторів одночасно існують поточні значення синусоїди і відповідні їм значення косинусоиди – обидві криві формуються синхронно.

Зазначимо, що форма подання даних не є головною відмінністю двох видів машин – головним є спосіб перетворення інформації. Щоб при цифровому поданні можна було використовувати структурний підхід, необхідно витримати умову: час  обчислень в РЕ повинен бути значно менше часу Т помітної зміни модельованого (обчислюваного) процесу, <<T.

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

В кінці 50-х років минулого століття були зроблені спроби з'єднати достоїнства АВМ і ЦОМ, вирівнявши їх недоліки; так з'явилися гібридні обчислювальні машини (ГВМ). Були випробувані різні способи гібридизації, починаючи від рівня форми представлення інформації і закінчуючи рівнем окремих машин, аналогових і цифрових.

Спочатку під терміном ЕОМ розуміли АВМ, ЦВМ і ГВМ. Але поступово взяв гору цифровий напрямок, і на нього були кинуті матеріальні та інтелектуальні ресурси. Це й визначило те, що в кінці 60-х років 20-го століття АВМ і ГВМ були в основному витіснені з обчислювальних центрів і лабораторій. У той же час відбувався бурхливий розвиток цифрової техніки, і далі під терміном ЕОМ стали розуміти тільки ЦОМ.

Універсальні і спеціалізовані ОС.

В універсальних ОС множина {Q_i} вибирається таким чином, щоб можна було вирішити принципово будь-яку задачу, для якої існує алгоритм. Такими є, наприклад, персональні комп'ютери.

В спеціалізованих системах вирішуються особливі задачи (вузький клас задач), для яких множина {Q_i} оптимізована, завдяки чому задача на спеціалізованій машині вирішується значно швидше, ніж на універсальній.

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

Проблеми становлення і розвитку ОС

Поряд з побудовою все більш потужних ОС інженери і програмісти шукали можливості прискорювати перетворення інформації за рахунок суміщення у часі окремих етапів вирішення задач, наприклад, введення-виведення даних з обчисленнями на процесорі. Також здійснювався перехід до багатомашинних комплексів (БМК).

На початку 60-х років почалися дискусії про паралельній обробці, при цьому багато говорилося про те, що еволюції в цьому напрямку буде перешкоджати випереджальне збільшення складності ВС. Пізніше, на основі зіставлення фон-Неймановской ЕОМ і БМК, були сформульовані закон Гроша і гіпотеза Мінського.

Закон Гроша свідчить, що продуктивність одного процесора збільшується пропорційно квадрату його вартості (рис. 2.2). Якщо це дійсно так, то, природно, будувати БМК нерозумно. Так, для двократного збільшення продуктивності (на основі двухмашинного комплексу) потрібне двократне збільшення вартості. Вже краще спроектувати процесор з відповідною продуктивністю, але збільшивши витрати 2 разів. З цієї причини застосування БМК довгий час обмежувалося сферою військових програм. Пізніше стало ясно, що зростання продуктивності визначається не стільки капіталовкладеннями, скільки технологією виробництва логічних елементів і, почасти, відстанями між ними. Тому настає момент, коли грошові вливання перестають давати відчутний ефект (пунктир), і зростання продуктивності все більше сповільнюється. Так відбувається до нового прориву у технології.

Мінський враховував взаємодія двох і більше машин. У гіпотезі Мінського стверджується, що в паралельній системі з р процесорами (умовна продуктивність кожного з яких дорівнює 1), за необхідності обміну даними, загальна продуктивність зростає лише як log₂p (рис. 4.3).

Рисунок 4.2. Закон Гроша

Різниця Q між ідеальним випадком масштабованої системи (Q=kn) і системою за гіпотезою Мінського являє собою втрату продуктивності, пов'язану з необхідністю організації взаємодії машин паралельної системи по обміну даними і по загальному управлінню.

Рисунок 2.3. Ілюстрація гіпотези Мінського

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

Складності паралельного програмування

Існують чисто теоретичні обмеження на максимальний приріст продуктивності при виконанні задачі на ПОС порівняно з однопроцесорною машиною, що виражаються законом Амдала (G. Amdahl, 1967 р).

Нехай частка операцій, які потрібно виконувати послідовно, дорівнює , де 01, тоді (1-) – частка паралельних операцій. Прискорення S, яке може бути отримано на комп'ютері з р процесорів при даному значенні , рівно:

Розглянемо граничні випадки. Випадок =0 відповідає повністю паралельній програмі, при цьому S=p; випадок =1 відповідає повністю послідовній програмі, при цьому S=1/.

Якщо 9/10 програми виконується паралельно, а 1/10 послідовно, то прискорення більш, ніж в 10 разів одержати в принципі неможливо незалежно від якості реалізації паралельної частини коду і кількості використовуваних процесорів (10 виходить тільки в тому випадку, коли час виконання паралельної частини дорівнює 0).

З іншого боку, для того щоб прискорити виконання програми в q разів, необхідно прискорити не менше, ніж в q раз не менше, ніж (1-1/q)-у частину програми. Отже, для прискорення програми в 100 разів порівняно з її послідовним варіантом, необхідно отримати не менше прискорення для не менш, ніж 99.99% коду!

Проте в 1988 р. Дж. Густафсон звернув увагу на те, що на практиці параметри р і (1-) не є незалежними. Обчислювальним задачам притаманна властивість масштабованості. Суперкомп'ютер з великою кількістю процесорів дозволяє реалізовувати більш детальні обчислення, збільшувати їх точність і т. д., що зазвичай веде до зменшення . Тому песимістичні висновки, які можна зробити (і які були зроблені) із закону Амдала, на практиці зазвичай не виправдовуються.

Наступна важлива проблема паралельних обчислень – оптимальне завантаження процесорів (балансування навантаження).

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

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

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

Перелічимо та інші проблеми, що стоять перед ПОС:

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

• організація зв'язку процесорів між собою;

• ефективність паралельних алгоритмів;

• ефективність мов паралельного програмування.

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

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

Перспективи розвитку ПОС

За час існування ПОС було випробувано чимало цікавих ідей організації взаємодії множини процесорів, серед яких слід згадати однорідні обчислювальні системи [9] (ООС), як розвиток ідеї конвеєра; у вузлах ООС можуть знаходитись різноманітні процесорні елементи, у тому числі нескладні АЛУ і запропоновані в Англії трансп'ютери [10]. Цікавою є ідея систолічної структури [11], як розвиток автомата фон Неймана.

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

В даний час широко застосовуються кластерні рішення [1, гл. 5], – див. список, який публікується два рази на рік, п'ятисот найбільш продуктивних ОС – ТОР 500 [12]. Можна відзначити також безперервне зростання числа використовуваних у кластері процесорів.

Останнім часом багато уваги приділяється нейрокомп'ютерам [13]. Набули поширення багатоядерні процесори [1, гл. 7], графічні процесори [1, додаток 2] для розв'язування задач обчислювального характеру. І взагалі, ідея використання графічного процесора (GPU) в якості співпроцесора до основного стандартного процесору (CPU), ймовірно, переросте в ідею злиття CPU і GPU, в результаті чого буде отримано стандартний процесор з розширеним набором операцій за рахунок операцій графіки.

Намітився перспективний напрямок використання квантових комп'ютерів [1, гл. 8].

Для стратегічно важливих задач, наприклад, моделювання ядерних випробувань, використовуються суперкомп'ютери (СК) з найбільшою на даний момент продуктивністю, в яких використовуються найсучасніші ідеї та рішення. Широко відомі СК типу CRAY [1, п. 3.3] та Ельбрус [14]. Міжнародна кооперація Росії та Біларусі дозволила розробити спільну обчислювальну систему СКІФ [1, додаток 1]. У Росії активно розробляється більш загальний напрям комп’ютеробудування – побудова СК з програмованою архітектурою [15]. В Інституті кібернетики НАН України розроблена обчислювальна система ІНПАРКОМ (інтелектуальний паралельний комп'ютер) [16], який являє собою сімейство інтелектуальних паралельних комп'ютерів (інтелектуальний персональний комп'ютер, інтелектуальна робоча станція, інтелектуальний MIMD-комп'ютер) для дослідження і вирішення науково-технічних задач з наближено заданими вихідними даними та оцінкою вірогідності комп'ютерного рішення.

Відмітимо важливе: те, що спочатку пропонувалося в СК, потім поступово передавалося в масові комп'ютери.

Проводиться множина конференцій, присвячених питанням програмування паралельних ОС та їх апаратної реалізації. Дивись, наприклад, потужний інформаційний ресурс світового рівня – Parallel.ru – при науково-дослідному обчислювальному центрі МДУ (Росія).