Паралельні комп'ютери і супер-ЕОМ
Воєводін Вл.В.
Про те, що десь існують якісь містичні
"дуже потужні" комп'ютери чув, напевно, кожен. Справді, не
так давно було багато розмов про поставку в Гідрометеоцентр Росії могутніх
комп'ютерів фірми Cray Research. У листопаді 1999 року відбулося офіційне
відкриття Міжвідомчої суперкомп `ютерний центр, який в даний
момент має комп'ютер з 768 процесорами. Знову ж таки, якщо комп'ютер з ім'ям
Deep Blue обіграв самого Гаррі Каспарова, то він, погодьтеся - і тут інтуїція
Вас не підвела, ну ніяк не може бути простою персональні виставки.
Для багатьох подібні комп'ютери так і залишаються таємницею
за сімома печатками, деякої TERRA INCOGNITA, з якої асоціації завжди пов'язані з
чимось більшим: величезні розміри, великі завдання, великі фірми і компанії,
неймовірні швидкості роботи чи щось інше, але обов'язково це буде "на
межі ", для чого" звичайного "явно мало, а підійде тільки
"супер", суперкомп'ютер або супер-ЕОМ. У цьому інтуїтивному сприйнятті
є неабияка частка істини, оскільки до класу супер-ЕОМ належать лише ті
комп'ютери, які мають максимальну продуктивність в даний час.
Швидкий розвиток комп'ютерної індустрії визначає
відносність даного поняття - те, що десять років тому можна було назвати
суперкомп'ютером, сьогодні під це визначення вже не потрапляє. Наприклад,
продуктивність персональних комп'ютерів, які використовують Pentium-III/500MHz,
порівнянна з продуктивністю суперкомп'ютерів початку 70-х років, проте за
сьогоднішніми мірками суперкомп'ютерами не є ні ті, ні інші.
У будь-якому комп'ютері всі основні параметри тісно
пов'язані. Важко собі уявити універсальний комп'ютер, що має високу швидкодію
і мізерну оперативну пам'ять, або величезну оперативну пам'ять і невеликий
обсяг дисків. За логікою, робимо висновок: супер-ЕОМ це комп'ютери, які мають у
даний час не тільки максимальну продуктивність, а й максимальний
об'єм оперативної і дискової пам'яті (питання про спеціалізованому ПЗ, за допомогою
якого можна ефективно всім цим скористатися, поки залишимо осторонь).
Так про що ж мова і які існують в суперкомп'ютери
Нині у світі? Ось лише декілька параметрів, що дають достатньо
промовисту характеристику машин цього класу. Комп'ютер ASCI WHITE,
що займає перше місце в списку п'ятисот самих потужних комп'ютерів світу,
об'єднує 8192 процесора Power 3 із загальною оперативною пам'яттю в 4 терабайта і
продуктивністю більше 12 трильйонів операцій за секунду.
Супер-ЕОМ і надвисока продуктивність: навіщо?
Прості розрахунки показують, що конфігурації подібних
систем можуть коштувати не один мільйон доларів США - з цікавості прикиньте,
скільки коштують, скажімо, лише 4 Тбайт оперативної пам'яті? Виникає цілий ряд
природних питань: які завдання настільки важливі, що потрібні комп'ютери
вартістю кілька мільйонів доларів? Або, які завдання настільки складні,
що хорошого Пентіума не достатньо? На ці та подібні їм питання хотілося б
знайти розумні відповіді.
Для того, щоб оцінити складність розв'язуваних на практиці
завдань, візьмемо конкретну предметну область, наприклад, оптимізацію процесу
видобутку нафти. Маємо підземний нафтовий резервуар з яким-то число пробурених
свердловин: за одним на поверхню відкачується нафту, за іншими назад
закачується вода. Треба змоделювати ситуацію в цьому резервуарі, щоб
оцінити запаси нафти або зрозуміти необхідність у додаткових свердловинах.
Приймемо спрощену схему, при якій моделюються
область відображається в куб, однак і її буде достатньо для оцінки числа
необхідних арифметичних операцій. Розумні розміри куба, при яких можна
отримувати правдоподібні результати - це 100 * 100 * 100 пікселів. У кожній точці куба
треба вирахувати від 5 до 20 функцій: три компоненти швидкості, тиск,
температуру, концентрацію компонент (вода, газ і нафта - це мінімальний набір
компонент, у більш реалістичних моделях розглядають, наприклад, різні
фракції нафти). Далі, значення функцій знаходяться як рішення нелінійних
рівнянь, що вимагає від 200 до 1000 арифметичних операцій. І нарешті, якщо
досліджується нестаціонарний процес, тобто потрібно зрозуміти, як ця система веде
себе в часі, то робиться 100-1000 кроків за часом. Що вийшло:
106 (точок сітки) * 10 (функцій) * 500 (операцій) * 500 (кроків
за часом) = 2.5 * 1012
2500 млрд арифметичних операцій для виконання
одного лише розрахунку! А зміна параметрів моделі? А відстеження поточної
ситуації при зміні вхідних даних? Подібні розрахунки необхідно робити багато
разів, що накладає дуже жорсткі вимоги на продуктивність
використовуваних обчислювальних систем.
Приклади використання суперкомп'ютерів можна знайти не
тільки в нафтовидобувній промисловості. Ось лише невеликий список областей
людської діяльності, де використання суперкомп'ютерів дійсно
необхідно:
автомобілебудування
нафто-і газовидобуток
фармакологія
прогноз погоди і моделювання зміни клімату
сейсморозвідка
проектування електронних пристроїв
синтез нових матеріалів
і багато, багато інших
У 1995 році корпус автомобіля Nissan Maxima вдалося
зробити на 10% міцнішим завдяки використанню суперкомп'ютера фірми Cray (The
Atlanta Journal, 28 травня, 1995). За допомогою нього були знайдені не тільки слабкі
точки кузова, але і найбільш ефективний спосіб їх видалення.
За даними Марка Міллера (Mark Miller, Ford Motor
Company), для виконання crash-тестів, за яких реальні автомобілі
розбиваються об бетонну стіну з одночасним виміром необхідних параметрів,
зйомкою і наступною обробкою результатів, компанії Форд знадобилося б від
10 до 150 прототипів нових моделей при загальних витратах від 4 до 60 мільйонів
доларів. Використання суперкомп'ютерів дозволило скоротити кількість прототипів
на одну третину.
Зовсім недавній приклад - це розвиток однієї з
найбільших світових систем резервування Amadeus, використовуваної тисячами агенств
з 180000 терміналів у більш ніж ста країнах. Встановлення двох серверів
Hewlett-Packard T600 по 12 процесорів у кожному дозволила довести ступінь
оперативної доступності центральної системи до 99.85% при поточній завантаженні
близько 60 мільйонів запитів на добу.
І подібні приклади можна знайти всюди. Свого часу
дослідники фірми DuPont шукали заміну хлорофлюорокарбону. Потрібно було знайти
матеріал, що має ті ж позитивні якості: незаймистість, стійкість до
корозії і низьку токсичність, але без шкідливого впливу на озоновий шар
Землі. За один тиждень були проведені необхідні розрахунки на суперкомп'ютері із загальними
витратами близько 5 тисяч доларів. За оцінками фахівців DuPont, використання
традиційних експериментальних методів досліджень вимагало б близько трьох
місяців і 50 тисяч доларів і це без урахування часу, необхідного на синтез і
очищення необхідної кількості речовини.
Збільшення продуктивності ЕОМ, за
рахунок чого?
А чому суперкомп'ютери вважають так швидко? Варіантів
відповіді може бути декілька, серед яких два мають явну перевагу:
розвиток елементної бази і використання нових рішень в архітектурі
комп'ютерів.
Спробуємо розібратися, який з цих факторів
виявляється вирішальним для досягнення рекордної продуктивності. Звернемося до
відомим історичним фактам. На одному з перших комп'ютерів світу - EDSAC,
, що з'явилося в 1949 році в Кембриджі і мав час такту 2 мікросекунди
(2 * 10-6 секунди), можна було виконати 2 * n арифметичних операцій за 18 * n
мілісекунд, тобто в середньому 100 арифметичних операцій у секунду. Порівняємо з
одним обчислювальним вузлом сучасного суперкомп'ютера Hewlett-Packard V2600:
час такту приблизно 1.8 наносекунди (1.8 * 10-9 секунд), а пікова
продуктивність близько 77 мільярдів арифметичних операцій у секунду.
Що ж виходить? За півстоліття продуктивність
комп'ютерів виросла більш, ніж в сімсот мільйонів разів. При цьому виграш в
швидкодії, пов'язаний зі зменшенням часу такту з 2 мікросекунд до 1.8
наносекунд, становить лише близько 1000 разів. Звідки ж взялася решта? Відповідь
очевидний - використання нових рішень в архітектурі комп'ютерів. Основне
місце серед них займає принцип паралельної обробки даних, що втілює
ідею одночасного (паралельного) виконання декількох дій.
Паралельна обробка даних на
ЕОМ
Паралельна обробка даних, втілюючи ідею
одночасного виконання кількох дій, має два різновиди:
конвеєрного і власне паралельність. Обидва види паралельної обробки
інтуїтивно зрозумілі, тому зробимо лише невеликі пояснення.
Паралельна обробка. Якщо якийсь пристрій
виконує одну операцію за одиницю часу, то тисячі операцій воно виконає за
тисячі одиниць. Якщо припустити, що є п'ять таких же незалежних пристроїв,
здатних працювати одночасно, то ту ж тисячі операцій система з п'яти
пристроїв може виконати вже не за тисячу, а за двісті одиниць часу.
Аналогічно система з N пристроїв ту ж роботу виконає за 1000/N одиниць
часу. Подібні аналогії можна знайти і в житті: якщо один солдат скопає
город за 10 годин, то рота солдатів з п'ятдесяти людина з такими ж
здібностями, працюючи одночасно, впораються з тією ж роботою за 12 хвилин --
принцип паралельності в дії!
До речі, піонером у паралельній обробці потоків
даних був академік А. А. Самарський, що виконував на початку 50-х років розрахунки,
необхідні для моделювання ядерних вибухів. Самарський вирішив це завдання,
посадив кілька десятків панночок з арифмометра за столи. Панянки
передавали дані один одному просто на словах і відкладали необхідні цифри
на арифмометра. Таким чином, зокрема, була розрахована еволюція вибуховою
хвилі. Роботи було багато, панночки втомлювалися, а Олександр Андрійович ходив між
ними і підбадьорював. Це, можна сказати, і була першою паралельна система.
Хоча розрахунки водневої бомби були майстерно проведені, точність їх була дуже
низька, тому що вузлів у використовуваної сітці було мало, а час рахунку
виходило занадто великим.
Конвеєрна обробка. Що необхідно для складання
двох дійсних чисел, представлених у формі з плаваючою комою? Ціле
безліч дрібних операцій таких, як порівняння порядків, вирівнювання порядків,
складання мантиси, нормалізація і т.п. Процесори перших комп'ютерів виконували
всі ці "мікрооперації" для кожної пари аргументів послідовно
один за однієї до тих пір, поки не доходили до остаточного результату, і лише
після цього переходили до обробки наступної пари доданків.
Ідея конвеєрної обробки полягає у виділенні
окремих етапів виконання спільної операції, причому кожен етап, виконавши свою
роботу, передавав би результат наступного, одночасно беручи нову порцію
вхідних даних. Отримуємо очевидний виграш у швидкості обробки за рахунок
суміщення перш рознесені в часі операцій. Припустимо, що в операції
можна виділити п'ять мікрооперацій, кожна з яких виконується за одну
одиницю часу. Якщо є одне неподільне послідовне пристрій, то 100
пар аргументів воно обробить за 500 одиниць. Якщо кожну мікрооперацій виділити
в окремий етап (або інакше говорять - ступінь) конвеєрного пристрої, то на п'ятому
одиниці часу на різній стадії обробки такого пристрою будуть знаходиться
перші п'ять пар аргументів, а весь набір зі ста пар буде оброблений за 5 +99 = 104
одиниці часу - прискорення в порівнянні з послідовним пристроєм майже в
п'ять разів (за числом ступенів конвеєра).
Здавалося б конвеєрну обробку можна з успіхом
замінити звичайним паралелізмом, для чого продублювати основний пристрій
стільки разів, скільки ступенів конвеєра передбачається виділити. Справді,
п'ять пристроїв попереднього прикладу оброблять 100 пар аргументів за 100 одиниць
часу, що швидше часу роботи конвеєрного пристрою! У чому ж справа?
Відповідь проста, збільшивши в п'ять разів кількість пристроїв, ми значно збільшуємо
як обсяг апаратури, так і її вартість. Уявіть собі, що на автозаводі
вирішили прибрати конвеєр, зберігши темпи випуску автомобілів. Якщо раніше на
конвеєрі одночасно перебувала тисячі автомобілів, то діючи за аналогією з
попереднім прикладом треба набрати тисячі бригад, кожна з яких (1) в стані
повністю зібрати автомобіль від початку до кінця, виконавши сотні різного роду
операцій, і (2) зробити це за той же час, що машина перш перебувала на
конвеєрі. Представили собівартість такого автомобіля? Ні? Згоден, важко,
хіба що Ламборгіні спадає на думку, але тому і виникла конвеєрна
обробка ...
Коротка історія появи паралелізму в архітектурі
ЕОМ
Сьогодні паралелізмом в архітектурі комп'ютерів уже
мало кого здивуєш. Всі сучасні мікропроцесори, будь то Pentium III або
PA-8700, MIPS R14000, Е2К або Power3 використовують той чи інший вид паралельної
обробки. У ядрі Pentium 4 на різних стадіях виконання може одночасно
перебувати до 126 мікрооперацій. На презентаціях нових чіпів і в прес-релізах
корпорацій це підноситься як останнє слово техніки та передовий край
науки, і це дійсно так, якщо розглядати реалізацію цих принципів в
мініатюрних рамках одного кристала.
Разом з тим, самі ці ідеї з'явилися дуже давно.
Спочатку вони впроваджувалися в самих передових, а тому одиничних, комп'ютерах
свого часу. Потім після належної відпрацювання технології і здешевлення
виробництва вони спускалися в комп'ютери середнього класу, і нарешті сьогодні всі
це в повному обсязі втілюється в робочих станціях і персональних комп'ютерах.
Для того щоб переконатися, що всі основні
нововведення в архітектурі сучасних процесорів насправді використовуються
ще з часів, коли ні мікропроцесорів, ні поняття суперкомп'ютерів ще не
було, зробимо маленький екскурс в історію, почавши практично з моменту
народження перших ЕОМ.
IBM 701 (1953), IBM 704 (1955):
розрядно-паралельна пам'ять, розрядно-паралельна арифметика.
Всі самі перші комп'ютери (EDSAC, EDVAC, UNIVAC)
мали розрядно-послідовну пам'ять, з якої слова зчитувалися
послідовно біт за бітом. Першим комерційно доступним комп'ютером,
використовують розрядно-паралельну пам'ять (на CRT) і розрядно-паралельну
арифметику, став IBM 701, а найбільшу популярність отримала модель IBM 704
(продано 150 екз.), в якій, крім сказаного, була вперше застосована пам'ять
на феритових сердечниках і апаратне АУ з плаваючою точкою.
IBM 709 (1958): незалежні
процесори введення/виводу.
Процесори перших комп'ютерів самі керували вводом/виводом.
Однак швидкість роботи найшвидшого зовнішнього пристрою, а на ті часи
це магнітна стрічка, була в 1000 разів менше швидкості процесора, тому під
час операцій введення/виводу процесор фактично простоював. У 1958р. до
комп'ютера IBM 704 приєднали 6 незалежних процесорів введення/виводу, які
після отримання команд могли працювати паралельно з основним процесором, а сам
комп'ютер перейменували на IBM 709. Дана модель вийшла дивно
вдалою, тому що разом з модифікаціями було продано близько 400 примірників,
причому останній був вимкнений у 1975 році - 20 років існування!
IBM STRETCH (1961): випереджаюче
перегляд вперед, розшарування пам'яті.
У 1956 році IBM підписує контракт з Лос-Аламоської
науковою лабораторією на розробку комп'ютера STRETCH, що має дві
принципово важливі особливості: випереджаюче перегляд вперед для вибірки
команд і розшарування пам'яті на два банки для узгодження низької швидкості
вибірки з пам'яті і швидкості виконання операцій.
ATLAS (1963): конвеєр команд.
Вперше конвеєрний принцип виконання команд був
використаний в машині ATLAS, розробленої в Манчестерському університеті.
Виконання команд розбито на 4 стадії: вибірка команди, обчислення адреси
операнда, вибірка операнда і виконання операції. Конвейеризації дозволила
зменшити час виконання команд з 6 мкс до 1,6 мкс. Комп'ютер надав
величезний вплив, як на архітектуру ЕОМ, так і на програмне забезпечення: в
ньому вперше використана мультипрограмному ОС, заснована на використанні
віртуальної пам'яті і системи переривань.
CDC 6600 (1964): незалежні
функціональні пристрої.
Фірма Control Data Corporation (CDC) при
безпосередньої участі одного з її засновників, Сеймура Р. Крея (Seymour
R. Cray) випускає комп'ютер CDC-6600 - перший комп'ютер, в якому
вико?? алось кілька незалежних функціональних пристроїв. Для порівняння з
сьогоднішнім днем наведемо деякі параметри комп'ютера:
час такту 100нс,
продуктивність 2-3 млн. операцій в секунду,
оперативна пам'ять розбита на 32 банку за 4096 60-ти
розрядних слів,
цикл пам'яті 1мкс,
10 незалежних функціональних пристроїв.
Машина мала величезний успіх на науковому ринку, активно
витісняючи машини фірми IBM.
CDC 7600 (1969): конвеєрні
незалежні функціональні пристрої.
CDC випускає комп'ютер CDC-7600 з вісьмома
незалежними конвеєрними функціональними пристроями - поєднання паралельної
і конвеєрної обробки. Основні параметри:
такт 27,5 нс,
10-15 млн. опер/сек.,
8 конвеєрних ФУ,
2-х рівнева пам'ять.
ILLIAC IV (1974): матричні
процесори.
Проект: 256 процесорних елементів (ПЕ) = 4 квадранта
по 64ПЕ, можливість реконфігурації: 2 квадранта по 128ПЕ або 1 квадрант з
256ПЕ, такт 40нс, продуктивність 1Гфлоп;
роботи розпочато в 1967 році, до кінця 1971 виготовлена
система з 1 квадранта, у 1974р. вона введена в експлуатацію, доведення велася до
1975;
центральна частина: пристрій керування (УУ) +
матриця з 64 ПЕ;
УУ це проста ЕОМ з невеликою продуктивністю, що управляє
матрицею ПЕ; все ПЕ матриці працювали в синхронному режимі, виконуючи в кожен
момент часу одну і ту ж команду, що поступила від УУ, але над своїми даними;
ПЕ мав власну АЛП з повним набором команд, ОП --
2Кслова по 64 розряду, цикл пам'яті 350нс, кожен ПЕ мав безпосередній
доступ тільки до своєї ОП;
мережа пересилання даних: двовимірний тор із зсувом на 1
по кордону по горизонталі;
Незважаючи на результат у порівнянні з проектом:
вартість в 4 рази вище, зроблений лише 1 квадрант, такт 80нс, реальна произв-ть
до 50Мфлоп - даний проект мав величезний вплив на архітектуру наступних
машин, побудованих за схожим принципом, зокрема: PEPE, BSP, ICL DAP.
CRAY 1 (1976):
векторно-конвеєрні процесори
У 1972 році С. Крей залишає CDC і засновує свою
компанію Cray Research, яка в 1976р. випускає перший векторно-конвеєрний
комп'ютер CRAY-1: час такту 12.5нс, 12 конвеєрних функціональних пристроїв,
пікова продуктивність 160 мільйонів операцій у секунду, оперативна пам'ять
до 1Мслова (слово - 64 розряду), цикл пам'яті 50НС. Головним нововведенням є
введення векторних команд, що працюють з цілими масивами незалежних даних і
що дозволяють ефективно використовувати конвеєрні функціональні пристрої.
Ієрархія пам'яті.
Ієрархія пам'яті пямого відношення до паралелізму НЕ
має, проте, безумовно, належить до тих особливостей архітектури
комп'ютерів, які має величезне значення для підвищення їх
продуктивності (згладжування різниці між швидкістю роботи процесора і часом
вибірки з пам'яті). Основні рівні: регістри, кеш-пам'ять, оперативна пам'ять,
дискова пам'ять. Час вибірки за рівнями пам'яті від дискової пам'яті до регістрів
зменшується, вартість в перерахунку на 1 слово (байт) зростає. В даний час,
подібна ієрархія підтримується навіть на персональних комп'ютерах.
А що ж зараз використовують у світі?
За яким же напрямках йде розвиток
високопродуктивної обчислювальної техніки в даний час? Основних
напрямків чотири.
1. Векторно-конвеєрні комп'ютери. Конвеєрні
функціональні пристрої і набір векторних команд - це дві особливості таких
машин. На відміну від традиційного підходу, векторні команди оперують цілими
масивами незалежних даних, що дозволяє ефективно завантажувати доступні
конвеєри, тобто команда виду A = B + C може означати складання двох масивів, а не
двох чисел. Характерним представником даного напрямку є сімейство
векторно-конвеєрних комп'ютерів CRAY куди входять, наприклад, CRAY EL, CRAY J90,
CRAY T90 (у березні 2000 року американська компанія TERA перекупила підрозділ
CRAY у компанії Silicon Graphics, Inc.).
2. Масивно-паралельні комп'ютери з розподіленою
пам'яттю. Ідея створення комп'ютерів цього класу тривіальна: візьмемо серійні
мікропроцесори, забезпечимо кожен своєю локальною пам'яттю, з'єднаємо допомогою
деякої комунікаційного середовища - ось і все. Переваг у такої архітектури
маса: якщо потрібна висока продуктивність, то можна додати ще
процесорів, якщо обмежені фінанси або заздалегідь відома необхідна
обчислювальна потужність, то легко підібрати оптимальну конфігурацію і т.п.
Однак є й вирішальний "мінус", що зводить
багато "плюси" нанівець. Справа в тому, що міжпроцесорних взаємодія
в комп'ютерах цього класу йде набагато повільніше, ніж відбувається локальна
обробка даних самими процесорами. Саме тому написати ефективну
програму для таких комп'ютерів дуже складно, а для деяких алгоритмів іноді
просто неможливо. До даного класу можна віднести комп'ютери Intel Paragon, IBM
SP1, Parsytec, в якійсь мірі IBM SP2 і CRAY T3D/T3E, хоча в цих
комп'ютерах вплив зазначеного мінуса значно послаблено. До цього ж класу
можна віднести і мережі комп'ютерів, які все частіше розглядають як дешеву
альтернативу вкрай дорогим суперкомп'ютерів.
3. Паралельні комп'ютери із загальною пам'яттю. Вся
оперативна пам'ять таких комп'ютерів розділяється декількома однаковими
процесорами. Це знімає проблеми попереднього класу, але додає нові --
число процесорів, що мають доступ до загальної пам'яті, з чисто технічних причин
не можна зробити великим. В даний напрямок входять багато сучасних
багатопроцесорні SMP-комп'ютери або, наприклад, окремі вузли комп'ютерів HP Exemplar
і Sun StarFire.
4. Останній напрямок, строго кажучи, не є
самостійним, а радше являє собою комбінації попередніх трьох. З
декількох процесорів (традиційних або векторно-конвеєрних) і загальної для них
пам'яті сформуємо обчислювальний вузол. Якщо отриманої обчислювальної потужності
не достатньо, то об'єднаємо декілька вузлів високошвидкісними каналами.
Подібну архітектуру називають кластерної, і за таким принципом побудовані CRAY SV1,
HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 та інші. Саме
цей напрямок є в даний час найбільш перспективним для
конструювання комп'ютерів з рекордними показниками продуктивності.
Використання
паралельних обчислювальних систем
На жаль дива в житті рідко трапляються. Гігантська
продуктивність паралельних комп'ютерів і супер-ЕОМ з лишком компенсується
складностями їх використання. Почнемо з найпростіших речей. У вас є
програма і доступ, скажімо, до 256-процесорного комп'ютера. Що ви очікуєте? Так
ясно що: ви цілком законно очікуєте, що програма буде виконуватися в 256 разів
швидше, ніж на одному процесорі. А от саме цього, швидше за все, і не
буде.
Закон Амдала і його наслідки
Припустимо, що у вашій програмі частка операцій,
які потрібно виконувати послідовно, дорівнює f, де 0 <= f <= 1 (при цьому
частка розуміється не по статичному числа рядків коду, а за кількістю операцій у
процесі виконання). Крайні випадки в значеннях f відповідають повністю
паралельним (f = 0) і повністю послідовним (f = 1) програмами. Так от, для
того, щоб оцінити, яке прискорення S може бути отримано на комп'ютері з 'p'
процесорів при даному значенні f, можна скористатися законом Амдала:
Якщо 9/10 програми виконується паралельно, а 1/10
як і раніше, послідовно, то прискорення більше, ніж у 10 раз отримати в
принципі неможливо поза залежністю від якості реалізації паралельної частини
коду і кількості використовуваних процесорів (ясно, що 10 виходить тільки в тому
випадку, коли час виконання паралельної частини дорівнює 0).
Подивимося на проблему з іншого боку: а яку ж
частина коду треба прискорити (а значить і попередньо дослідити), щоб
отримати задане прискорення? Відповідь можна знайти в слідстві із закону Амдала:
для того щоб прискорити виконання програми в q разів необхідно прискорити не
менше, ніж у q раз не менш, ніж (1-1/q)-у частину програми. Отже, якщо
є бажання прискорити програму в 100 разів у порівнянні з її послідовним
варіантом, то необхідно отримати не менше прискорення не менш, ніж на 99.99%
коду, що майже завжди складає значну частину програми!
Звідси перший висновок - перш, ніж грунтовно
переробляти код для переходу на паралельний комп'ютер (а будь-який
суперкомп'ютер, зокрема, є таким) треба грунтовно подумати. Якщо
оцінивши закладений у програмі алгоритм ви зрозуміли, що частка послідовних
операцій велика, то на значне прискорення розраховувати явно не доводиться і
потрібно думати про заміну окремих компонент алгоритму.
У ряді випадків послідовний характер алгоритму
змінити не так складно. Припустимо, що в програмі є наступний фрагмент для
обчислення суми n чисел:
s = 0
Do i = 1, n
s = s + a (i)
EndDo
(можна теж саме будь-якою іншою мовою)
За своєю природою він строго послідовний, тому що на
i-й ітерації циклу потрібно результат з (i-1)-й і все ітерації виконуються
одна за одною. Маємо 100% послідовних операцій, а значить і ніякого
ефекту від використання паралельних комп'ютерів. Разом з тим, вихід
очевидний. Оскільки в більшості реальних програм (питання: а чому в
більшості, а не у всіх?) немає істотної різниці, в якому порядку
складати числа, виберемо іншу схему складання. Спочатку знайдемо суму пар
сусідніх елементів: a (1) + a (2), a (3) + a (4), a (5) + a (6) і т.д. Зауважимо, що при
такою схемою всі пари можна складати одночасно! На наступних кроках будемо
діяти абсолютно аналогічно, отримавши варіант паралельного алгоритму.
Здавалося б у цьому випадку всі проблеми вдалося
дозволити. Але уявіть, що доступні вам процесори різнорідні за своєю
продуктивності. Значить буде такий момент, коли хтось із них ще
трудиться, а хтось вже все зробив і марно простоює в очікуванні. Якщо
розкид в продуктивності комп'ютерів великий, то й ефективність всієї
системи при рівномірному завантаженні процесорів буде вкрай низькою.
Але підемо далі і припустимо, що всі процесори
однакові. Проблеми скінчилися? Знову ні! Процесори виконали свою роботу, але
результат-то треба передати іншому для продовження процесу підсумовування ... а
на передачу йде час ... і в цей час процесори знову простоюють ...
Словом, змусити паралельну обчислювальну систему
або супер-ЕОМ працювати з максимальною ефективність на конкретній програмі
це, прямо скажемо, завдання не з простих, оскільки
необхідно
ретельне узгодження структури програм і алгоритмів з особливостями
архітектури паралельних обчислювальних систем.
Заключний питання. Як ви думаєте, чи вірно
твердження: чим потужніший комп'ютер, тим швидше на ньому можна вирішити дану
завдання?
Заключний відповідь. Ні, це не правильно. Це можна
пояснити простим побутовим прикладом. Якщо один землекоп викопає яму 1м * 1м * 1м за
1 годину, то два таких же землекопа це зроблять за 30 хв - в це можна повірити.
А за скільки часу цю роботу зроблять 60 землекопів? За 1 хвилину? Звичайно ж
немає! Починаючи з деякого моменту вони будуть просто заважати один одному, не
прискорюючи, а сповільнюючи процес. Так само і в комп'ютерах: якщо завдання занадто мала,
то ми будемо довше займатися розподілом роботи, синхронізацією процесів,
складанням результатів і т.п., ніж безпосередньо корисною працею.
Абсолютно ясно, що не все так просто ...
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://parallel.ru/
