Лекції з дисципліни "паралельні обчислення" - Лекції. Типи паралельної обробки інформації

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

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

Паралельні ЕОМ часто поділяються за класифікацією Флінна на машини типу SIMD (Single Instruction Multiple Data – з одним потоком команд при множинному потоці даних) та MIMD (Multiple Instruction Multiple Data – з множинним потоком команд при множинному потоці даних). Як і будь-яка інша, наведена вище класифікація недосконала: існують машини, що прямо в неї не потрапляють, є також важливі ознаки, які в цій класифікації не враховані. Зокрема, до машин типу SIMD часто відносять векторні процесори, хоча їхня висока продуктивність залежить від іншої форми паралелізму - конвеєрної організації машини. Багатопроцесорні векторні системи типу Cray Y-MP складаються з декількох векторних процесорів і тому можуть бути названі MSIMD (Multiple SIMD).

Класифікація Флінна не робить відмінності за іншими важливими для обчислювальних моделей характеристиками, наприклад, за рівнем "зернистості" паралельних обчислень та методами синхронізації.

Можна виділити чотири основні типи архітектури систем паралельної обробки:

1) Конвеєрна та векторна обробка.

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

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

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

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

Моделі обчислень на векторних та матричних ЕОМ настільки схожі, що ці ЕОМ часто обговорюються як еквівалентні.

3) Машини типу MIMD. Термін "мультипроцесор" покриває більшість машин типу MIMD і (подібно до того, як термін "матричний процесор" застосовується до машин типу SIMD) часто використовується як синонім для машин типу MIMD. У мультипроцесорній системі кожен процесорний елемент (ПЕ) виконує свою програму незалежно від інших процесорних елементів. Процесорні елементи, звичайно, повинні якось зв'язуватися один з одним, що робить необхідним докладнішу класифікацію машин типу MIMD. У мультипроцесорах із загальною пам'яттю (сильно пов'язаних мультипроцесорах) є пам'ять даних і команд, доступна всім ПЕ. Із загальною пам'яттю ПЕ зв'язуються за допомогою загальної шини чи мережі обміну. На противагу цьому варіанту в слабопов'язаних багатопроцесорних системах (машинах з локальною пам'яттю) вся пам'ять ділиться між процесорними елементами і кожен блок пам'яті доступний тільки пов'язаному з ним процесору. Мережа обміну пов'язує процесорні елементи друг з одним.

Базовою моделлю обчислень на MIMD-мультипроцесорі є сукупність незалежних процесів, що епізодично звертаються до даних, що розділяються. Існує велика кількість варіантів цієї моделі. На одному кінці спектру - модель розподілених обчислень, в якій програма ділиться на досить велику кількість паралельних завдань, що складаються з багатьох підпрограм. З іншого боку спектра - модель потокових обчислень, у яких кожна операція у програмі можна як окремий процес. Така операція чекає на свої вхідні дані (операнди), які мають бути передані їй іншими процесами. Після їх отримання операція виконується, і отримане значення передається тим процесам, які його потребують. У потокових моделях обчислень з великим і середнім рівнем гранулярності процеси містять велику кількість операцій і виконуються в потоковій манері.

4) Багатопроцесорні машини із SIMD-процесорами.

Багато сучасних супер-ЕОМ є багатопроцесорними системами, в яких як процесори використовуються векторні процесори або процесори типу SIMD. Такі машини належать до машин класу MSIMD.

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

Багатопроцесорні системи за роки розвитку обчислювальної техніки зазнали ряду етапів свого розвитку. Історично першою стала освоюватися технологія SIMD. Однак у цей час намітився стійкий інтерес до архітектур MIMD. Цей інтерес головним чином визначається двома факторами:

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

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

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

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

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

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

До першої групи відносяться машини із загальною (розділюваною) основною пам'яттю, що об'єднують до декількох десятків (зазвичай менше 32) процесорів. Порівняно невелика кількість процесорів у таких машинах дозволяє мати одну централізовану загальну пам'ять та об'єднати процесори та пам'ять за допомогою однієї шини. За наявності у процесорів кеш-пам'яті достатнього обсягу високопродуктивна шина та загальна пам'ять можуть задовольнити звернення до пам'яті, що надходять від кількох процесорів. Оскільки є єдина пам'ять з тим самим часом доступу, ці машини іноді називаються UMA (Uniform Memory Access). Такий спосіб організації з порівняно невеликою пам'яттю, що розділяється, в даний час є найбільш популярним. Структура такої системи представлена на рис. 10.1.

Мал. 10.1. Типова архітектура мультипроцесорної системи із загальною пам'яттю.

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

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

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

Зазвичай пристрої введення/виводу, як і пам'ять, розподіляються по вузлах і насправді вузли можуть складатися з невеликого числа (2-8) процесорів, з'єднаних між собою іншим способом. Хоча така кластеризація кількох процесорів з пам'яттю та мережевий інтерфейс можуть бути досить корисними з точки зору ефективності у вартісному вираженні, це не дуже суттєво для розуміння того, як така машина працює, тому ми поки що зупинимося на системах з одним процесором на вузол. p align="justify"> Основна різниця в архітектурі, яку слід виділити в машинах з розподіленою пам'яттю полягає в тому, як здійснюється зв'язок і яка логічна модель пам'яті.

Мал. 10.2. Типова архітектура машини із розподіленою пам'яттю.

4 курс, 1 та 2 потоки, 7-й семестр

лекції (34 години), залік

Кафедра, яка відповідає за курс: АСВК

Упорядник програми: чл.-кор. РАН, доктор фіз.-мат. наук Воєводін Вл.В.,

Лектори: чл.-кор. РАН, доктор фіз.-мат. наук Воєводін Вл.В.

Анотація

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

Для 1-го та 2-го потоків обговорюються підходи до узгодження особливостей архітектури паралельних систем та структури алгоритмів, питання теорії аналізу структури програм та алгоритмів, моделі у паралельних обчисленнях.

Програма

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

2. Основні класи сучасних паралельних обчислювальних систем. Комп'ютери із загальною пам'яттю, приклади, причини зниження продуктивності реальних програмах. Архітектури SMP, NUMA, ccNUMA. Комутація процесорів та модулів пам'яті, шина, матричний комутатор, омега-мережа. Векторно-конвеєрні обчислювальні системи, приклади, причини зниження продуктивності. Комп'ютери з розподіленою пам'яттю, приклади, причини зниження продуктивності. Топологія зв'язку між процесорами: зірка, грати, тривимірний тор, двійковий гіперкуб, їх властивості. Обчислювальні кластери, приклади, латентність та пропускна спроможність різних комунікаційних технологій. Архітектури з паралелізмом на рівні машинних команд, VLIW, суперскалярність.

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

4. Продуктивність паралельних обчислювальних систем. Універсальність та спеціалізація комп'ютерів, продуктивність спецпроцесорів. Закон Мура. Методи оцінки продуктивності. Введення єдиного числового параметра, Mflops, MIPS. Пікова та реальна продуктивність комп'ютерів. Тест Linpack та його варіанти. Набори взаємодоповнюючих тестових програм, STREAM та NPB.

5. Графові моделі програм. Граф управління та інформаційний граф програми. Інформаційна та операційна історія реалізації програм. Граф алгоритму як компактна параметрична форма подання інформаційної історії. Інформаційна незалежність операцій та можливість їх паралельного виконання. Довжина критичного шляху графа алгоритму як міра ступеня паралельності. Кінцевий та масовий паралелізм, координатний та скошений паралелізм. Еквівалентні перетворення програм, елементарні перетворення циклів.

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

Література

1. Воєводін В.В., Воєводін Вл.В. Паралельні обчислення. - СПб.: БХВ Петербург, 2002. - 608 с.

2. Корольов Л.М. Архітектура процесорів електронних обчислювальних машин. - М: Вид. факультету ВМК МДУ, 2003.

3. В.В.Корнєєв. Паралельні обчислювальні системи. - М.: Вид-во "Нолідж", 1999. - 320с.

4. Матеріали інформаційно-аналітичного центру з паралельних обчислень Parallel.ru.

додаткова література

1. Антонов А.С. Паралельне програмування з використанням технології

MPI: Навчальний посібник. - М.: Вид-во МДУ, 2004. - 71 с.

Паралельна обробка даних

Інформатика, кібернетика та програмування

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

Лекція 1

Паралельна обробка даних

План

1. Ярусно-паралельна форма алгоритму.

2. Автоматичне виявлення паралелізму.

3. Ступінь та рівні паралелізму.

4. Види паралелізму.

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

Продуктивність паралельних ЗС залежить від багатьох факторів і значною мірою від архітектури та структури системи(малювати структуру паралельної системи та пояснювати):

Від ступеня та рівня паралелізму в системі;

Від організації передачі між паралельно працюючими процесорами;

Від системи комутації;

Від взаємодії процесорів та пам'яті;

Від співвідношення між апаратною та програмною реалізацією макрооперації.

В основу паралельної обробки можуть бути покладені різні принципи:

Просторовий паралелізм;

Тимчасовий паралелізм:

Конвеєризація.
Векторизація.
Матричний.
Систолічний.
Організація структури обробки потоку даних.
Організація системи з урахуванням структури гиперкуб.
Динамічна розбудова структури ЗС.

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

1. Ярусно-паралельна форма алгоритму

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

Алгоритм у ярусно-паралельній форміпредставляється як ярусів, причому у нульовий ярус входять оператори (гілки) незалежні друг від друга.

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

При побудові ЯПФ спираються базовий набір примітивних операцій (БНО). Ярусно-паралельна форма характеризується такимипараметрами:

1. Довжина графа (кількість ярусів) L.

2. Ширина i-го ярусу - b i.

3. Ширина графа ярусно-паралельної форми | B = max (b i).

4. Середня ширина графа ЯПФУ порівн.

5. Коефіцієнт заповнення i-го ярусу k i .

6. Коефіцієнт розкиду операцій у графі - Q j i , j БНО , де - кількість j -го типу операцій у i-му ярусі.

7. Мінімальна необхідна кількість обчислювачів (з БНТ) для реалізації алгоритму, представленого даним графом ЯПФ.

8. Мінімальний час вирішення алгоритму (сума часів спрацьовування обчислювачів з максимальним обсягом обчислень по кожному ярусу)Т min.

9. Зв'язковість алгоритму (кількість проміжних результатів, яку необхідно зберігати в процесі реалізації алгоритму)З.

2. Автоматичне виявлення паралелізму

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

Методи побудови паралельного алгоритму з послідовного засновані на виділенні в послідовному алгоритмі типових конструкцій, що часто зустрічаються, які за певними правилами замінюються паралельними. (Що дозволяє певною мірою підняти ступінь паралелізму, втрачений алгоритмом під час програмування послідовною мовою.)

Характер зміни ступеня паралелізму під час підготовки машинної програми показаний на рис. 2.2.

потенційний паралелізм

Метод

рішення

Початковий текст

Машинна програма

Мал. 2.2. Зміна потенційного паралелізму під час розробки програми:

1 система паралельного програмування;

2 | послідовне програмування та

векторизуючий компілятор

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

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

Під час аналізу програми будується граф потоку даних. Щоб виявити явну паралельність процесів, аналізуються безлічі вхідних (зчитуваних) змінних R та вихідних (записуваних) змінних W кожного процесу.

Явна паралельна обробка може бути виявлена серед процесів i та j (i ≠ j ), що задовольняють наступним умовам:

вхідні дані одного процесу не повинні модифікуватися (записуватись) іншим процесом

ніякі два процеси не повинні модифікувати загальні змінні

а) R i W j =;

б) W i R j =;

в) W i W j =;

Прихована паралельна обробка вимагає деякої процедури перетворення послідовної програми, щоб уможливити її паралельне виконання. Перетворення може бути наступним:

а) зменшення висоти дерев арифметичних виразів (рис.2.3). Для арифметичних виразів з n Змінними або константами зменшення висоти дерева дозволяє досягти прискорення обробки порядку O (n/log 2 n ) при використанні O (n) процесорів;

б) перетворення лінійних рекурентних співвідношень;

((a + b) + c) + d

(a + b) + (c + d)

Мал. 2.3. Зменшення висоти дерева

в) заміна операторів;

г) перетворення блоків умовних переходів та циклів до канонічного вигляду;

д) розподіл циклів.

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

При перетворенні паралелізму програми враховують: 1) схему розміщення даних у пам'яті; 2) адресацію пам'яті (індексування); 3) вибір маршруту даних (спосіб з'єднання процесорів та ЗП).

Рис.2.4. Зберігання

матриці зі зсувом

Як приклад обліку схеми розміщення пам'яті візьмемо пам'ять з діагональної адресацією. Для забезпечення паралельної обробки матриць елементи їх рядків і стовпців повинні бути розподілені між пристроями процесорів, що запам'ятовують, таким чином, щоб можна було їх одночасно зчитувати і обробляти. При цьому матриця зберігається зі зсувом (рис.2.4).

Будь-який алгоритм містить послідовні (скалярні) ділянки. Доведено, що довжина цих скалярних ділянок є визначальним фактором під час реалізації алгоритму на паралельній ВС.

3. Ступінь та рівні паралелізму

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

1) Низький рівень: від 2 до 10 процесорів.

2) Середній ступінь: від 10 до 100 процесорів.

3) Високий ступінь: від 100 до 10 4 процесори.

4) Надвисокий ступінь: від 10 4 до 10 6 процесорів.

Мал. 2.5. Профіль паралелізму

Графічне подання параметра D (t ) як функції часу називаютьпрофілем паралелізму програми. Зміни у рівні завантаження процесорів під час спостереження залежить від багатьох чинників (алгоритму, доступних ресурсів, ступеня оптимізації, що забезпечується компілятором тощо.). На рис. 2.5 показаний типовий профіль паралелізму.

У прикладних програмах є широкий спектр потенційного паралелізму. У обчислювально-інтенсивних програмах у кожному циклі паралельно можуть виконуватися від 500 до 3500 арифметичних операцій, якщо для цього є існуюче обчислювальне середовище. Однак, навіть правильно спроектований суперскалярний процесор здатний підтримувати від 2 до 5,8 команди за цикл. Таке падіння пов'язане насамперед із комунікаційними та системними витратами.

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

Розглядають алгоритмічнийта схемний рівні паралелізму.

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

1. Рівень завдань:

а) між завданнями;

б) між фазами завдань.

2. Програмний рівень:

а) між частинами програми(частини одного завдання виконуються на безлічі обчислювачів);

б) не більше циклів.

(Якщо окремі ітерації в циклі не залежать один від одного. Наприклад : Для I:=1 до N до A(I):=B(I) + C(I))

3. Командний рівень:

а) між фазами виконання команд.

4. Арифметичний та розрядний рівень:

а) між елементами векторної операції;

б) усередині логічних схем АЛУ.

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

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

Паралельна обробка може бути реалізована на наступних схемних рівнях:

1. На рівні логічних вентилів та елементів пам'яті.Це нижчий рівень - рівень транзисторів. Тут із логічних вентилів будують паралельні логічні схеми (ЛЗ ) (наприклад: паралельний суматор).

2. Рівень логічних схем та простих автоматів з пам'яттю.З логічних схем будують паралельний елементарний автомат (ЕА).

3. Рівень регістрів та інтегральних схем пам'яті.На елементарних автоматах одержують паралельні схеми мікропроцесорів (МП).

4. Рівень елементарних процесорів.З мікропроцесорів будують паралельні макропроцесори до виконання среднеблочных операцій (МАП).

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

6. Рівень обчислювальних машин, процесорів та програм.Вищий рівень паралелізму з багатопроцесорних систем отримують паралельні обчислювальні системи (НД).

4. Види паралелізму

4.1. Природний паралелізм та

паралелізм безлічі об'єктів

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

Завдання має природним паралелізмом, якщо її вихідної постановці вона зводиться до операції над багатовимірними векторами, багатовимірними матрицями чи над решітчастими функціями (рис.2.6). Тут не використовуються проміжні результати завдань. Кожне завдання програмується незалежно від інших. Цей вид паралелізму вимагає об'єднання ЕОМ в комплекси. Однак збільшення кількості незалежних завдань у СОД підвищує пропускну спроможність системи. Наприклад: обробка транзакцій до БД на багатопроцесорних серверах.

1 завдання

2 завдання

Мал. 2.6. Інформаційний граф завдання, що характеризується природним паралелізмом

Орі

Орi+1

у 1

у 2

у 3

у 4

Мал. 2.7. Інформаційний граф

завдання, що характеризується

паралелізмом безлічі об'єктів

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

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

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

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

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

Паралелізм безлічі об'єктів характеризується такимипараметрами:

1. Сумарна довжина програми L ¦ сумуються довжини всіх операторів по всіх гілках.

2. Середня довжина програми L ср обчислюється виходячи з рангу завдання.

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

3. Величина розбіжності задачі D

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

4.2. Паралелізм незалежних гілок

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

Гілка програми Y не залежить від гілки X , якщо:

Мал. 2.8. Інформаційний граф задачі, що характеризується

паралелізмом незалежних гілок

між ними немає функціональних зв'язків, тобто. жодна з вхідних змінних гілки Y не є вихідний змінної гілки X або будь-якої гілки, яка залежить від X;

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

4.3. Паралелізм суміжних операцій або

локальний паралелізм

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

Локальний паралелізм характеризується такимипараметрами:

1. Показник зв'язності суміжних операційЦе ймовірність того, що результат деякої операції буде використаний в наступній за нею операції. Що менше зв'язність операції, то більше вписувалося для неї глибина паралелізму суміжних операцій. Зазвичай величина має значення 0105.

2. Імовірність того, що, починаючи від цієї операції, є ланцюжок завдовжки не менше l l

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

4. Глибина паралелізму суміжних операцій L ПСО Це математичне очікування довжини ланцюжка операцій, які можна виконувати одночасно

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

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

________________________________________________________________________________________________

Курс «Організація ЕОМ»

10 -

(курсовий проект)

Збільшення продуктивності ЕОМ, рахунок чого?

А чому суперкомп'ютери рахують так швидко? Варіантів відповіді може бути кілька, серед яких два мають явну перевагу: розвиток елементної бази та використання нових рішень в архітектурі комп'ютерів.

Спробуємо розібратися, який із цих факторів виявляється вирішальним для досягнення рекордної продуктивності. Звернемося до відомих історичних фактів. На одному з перших комп'ютерів світу - 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 хвилин – принцип паралельності у дії!

p align="justify"> До речі, піонером у паралельній обробці потоків даних був академік А.А.Самарський, який виконував на початку 50-х років розрахунки, необхідні для моделювання ядерних вибухів. Самарський вирішив це завдання, посадивши кілька десятків панянок з арифмометрами за столи. Панночки передавали дані один одному просто на словах і відкладали необхідні цифри на арифмометрах. Таким чином, зокрема, було розраховано еволюцію вибухової хвилі. Роботи було багато, панночки втомлювалися, а Олександр Андрійович ходив між ними і підбадьорював. Це, можна сказати, і була перша паралельна система. Хоча розрахунки водневої бомби були майстерно проведені, точність їх була дуже низька, тому що вузлів у сітці було мало, а час рахунку виходив занадто великим.

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

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

Здавалося б конвеєрну обробку можна з успіхом замінити звичайним паралелізмом, для чого продублювати основний пристрій стільки разів, скільки ступенів конвеєра передбачається виділити. Насправді, п'ять пристроїв попереднього прикладу опрацюють 100 пар аргументів за 100 одиниць часу, що швидше за час роботи конвеєрного пристрою! У чому ж справа? Відповідь проста, збільшивши в п'ять разів кількість пристроїв, ми значно збільшуємо як об'єм апаратури, так і її вартість. Уявіть собі, що на автозаводі вирішили забрати конвеєр, зберігши темпи випуску автомобілів. Якщо раніше на конвеєрі одночасно знаходилася тисяча автомобілів, то діючи за аналогією з попереднім прикладом треба набрати тисячу бригад, кожна з яких (1) може повністю зібрати автомобіль від початку до кінця, виконавши сотні різного роду операцій, і (2) зробити це за той самий час, що машина раніше знаходилася на конвеєрі. Уявили собівартість такого автомобіля? Ні? Згоден, важко, хіба що Ламборгіні спадає на думку, але тому і виникла конвеєрна обробка...

Прості розрахунки показують, що конфігурації подібних систем можуть коштувати не один мільйон доларів США – заради інтересу прикиньте, скільки коштують, скажімо, лише 4 Тбайти оперативної пам'яті? Виникає ціла низка природних питань: які завдання настільки важливі, що потрібні комп'ютери вартістю кілька мільйонів доларів? Або які завдання настільки складні, що хорошого Пентіума мало? На ці та подібні до них питання хотілося б знайти розумні відповіді.

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

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

10 6 (точок сітки) * 10 (функцій) * 500 (операцій) * 500 (кроків за часом) = 2.5 * 10 12

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

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

автомобілебудування
нафто- та газовидобуток
фармакологія
прогноз погоди та моделювання зміни клімату
сейсморозвідка
проектування електронних пристроїв
синтез нових матеріалів
і багато, багато інших

В 1995 корпус автомобіля Nissan Maxima вдалося зробити на 10% міцніше завдяки використанню суперкомп'ютера фірми Cray (The Atlanta Journal, 28 травня, 1995р). З допомогою нього було знайдено як слабкі точки кузова, а й найефективніший спосіб їх видалення.

За даними Марка Міллера (Mark Miller, Ford Motor Company), для виконання crash-тестів, при яких реальні автомобілі розбиваються об бетонну стіну з одночасним виміром необхідних параметрів, зйомкою та подальшою обробкою результатів, компанії Ford знадобилося б від 10 до 150 прототипів нових моделей. за загальних витрат від 4 до 60 мільйонів доларів. Використання суперкомп'ютерів дозволило скоротити кількість прототипів на третину.

Зовсім недавній приклад - це розвиток однієї з найбільших світових систем резервування Amadeus, що використовується тисячами агенств з 180 000 терміналів у більш ніж ста країнах. Установка двох серверів Hewlett-Packard T600 по 12 процесорів у кожному дозволила довести рівень оперативної доступності центральної системи до 99.85% при поточному завантаженні близько 60 мільйонів запитів на добу.

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

Збільшення продуктивності ЕОМ, рахунок чого?

Паралельна обробка даних на ЕОМ

Коротка історія появи паралелізму в архітектурі ЕОМ

Сьогодні паралелізмом в архітектурі комп'ютерів вже мало кого здивуєш. Всі сучасні мікропроцесори, будь то 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.

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

А що ж зараз використовують у світі?

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

Припустимо, що у вашій програмі частка операцій, які потрібно виконувати послідовно, дорівнює f, де 0

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

Подивимося на проблему з іншого боку: а яку ж частину коду треба прискорити (а отже, і попередньо дослідити), щоб отримати прискорення? Відповідь можна знайти внаслідок закону Амдала: для того щоб прискорити виконання програми в qраз необхідно прискорити не менше, ніж у qразів не менше, ніж (1-1/ q)-ю частину програми. Отже, якщо є бажання прискорити програму в 100 разів у порівнянні з її послідовним варіантом, то необхідно отримати не менше прискорення не менше ніж на 99.99% коду, що майже завжди становить значну частину програми!

Звідси перший висновок – перш, ніж ґрунтовно переробляти код для переходу на паралельний комп'ютер (а будь-який суперкомп'ютер, зокрема, є таким) треба ґрунтовно подумати. Якщо оцінивши закладений у програмі алгоритм, ви зрозуміли, що частка послідовних операцій велика, то на значне прискорення розраховувати явно не доводиться і потрібно думати про заміну окремих компонентів алгоритму.

Нерідко послідовний характер алгоритму змінити негаразд складно. Припустимо, що у програмі є наступний фрагмент для обчислення суми n чисел:

S = 0 Do i = 1, ns = s + a(i) EndDo (можна теж саме будь-якою іншою мовою)

За своєю природою він суворо послідовний, оскільки і-й ітерації циклу потрібен результат з (i-1)-й і всі ітерації виконуються одна одною. Маємо 100% послідовних операцій, а отже, і ніякого ефекту від використання паралельних комп'ютерів. Водночас вихід очевидний. Оскільки у більшості реальних програм (запитання: а чому в більшості, а не в усіх?) немає істотної різниці, в якому порядку складати числа, виберемо іншу схему складання. Спочатку знайдемо суму пар сусідніх елементів: a(1)+a(2), a(3)+a(4), a(5)+a(6) тощо. Зауважимо, що за такої схеми всі пари можна складати одночасно! На наступних кроках діятимемо абсолютно аналогічно, отримавши варіант паралельного алгоритму.

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

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

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

Заключне питання. Як ви думаєте, чи правильне твердження: чим потужніший комп'ютер, тим швидше на ньому можна вирішити це завдання?

Заключна відповідь. Ні, це не так. Це можна пояснити найпростішим побутовим прикладом. Якщо один землекоп викопає яму 1м*1м*1м за 1 годину, то два таких же землекопи це зроблять за 30 хв - це можна повірити. А скільки часу цю роботу зроблять 60 землекопів? За хвилину? Звичайно ж ні! Починаючи з деякого моменту вони просто заважатимуть один одному, не прискорюючи, а уповільнюючи процес. Так само і в комп'ютерах: якщо завдання надто мало, то ми довше займатимемося розподілом роботи, синхронізацією процесів, збиранням результатів тощо, ніж безпосередньо корисною роботою.

Цілком ясно, що не все так просто...

Лабораторія Паралельних Інформаційних Технологій, НДЦ МДУ