Класифікація систем паралельної обробки даних. Послідовна та паралельна обробка інформації

«Паралелізм як спосіб паралельної обробки даних»

Котовськ2010

Вступ

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

p align="justify"> Найбільш перспективним і динамічним напрямом збільшення швидкості вирішення прикладних завдань є широке впровадження ідей паралелізму в роботу обчислювальних систем. На даний час спроектовані та випробувані сотні різних комп'ютерів, які використовують у своїй архітектурі той чи інший вид паралельної обробки даних. У науковій літературі та технічній документації можна знайти більше десятка різних назв, що характеризують лише загальні принципи функціонування паралельних машин: векторно-конвеєрні, масивно-паралельні, комп'ютери з широким командним словом, систолічні масиви, гіперкуби, спецпроцесори та мультипроцесори, ієрархічні та клас , матричні ЕОМ та багато інших. Якщо ж до подібних назв для повноти опису додати ще й дані про такі важливі параметри, як, наприклад, організація пам'яті, топологія зв'язку між процесорами, синхронність роботи окремих пристроїв або спосіб виконання арифметичних операцій, кількість різних архітектур стане і зовсім неосяжним.

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

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

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

1. Паралельні обчислювальні системи

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

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

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

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

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

2. Типи паралелізму

2.1 Паралелізм на рівні бітів

Ця форма паралелізму полягає в збільшенні розміру машинного слова. Збільшення розміру машинного слова зменшує кількість операцій, необхідних процесору до виконання дій над змінними, розмір яких перевищує розмір машинного слова. Наприклад: на 8-бітному процесорі необхідно скласти два 16-бітних цілих числа. Для цього спочатку потрібно скласти нижні 8 біт чисел, потім скласти верхні 8 біт і до результату складання додати значення прапора переносу. Разом 3 інструкції. З 16-бітним процесором можна виконати цю операцію однією інструкцією.

Історично 4-бітні мікропроцесори замінили 8-бітними, потім з'явилися 16-битные і 32-битные. 32-бітові процесори тривалий час були стандартом у повсякденних обчисленнях. З появою технології x86-64 для цього стали використовувати 64-бітові процесори.

2.2 Паралелізм на рівні інструкцій

Комп'ютерна програма – це, сутнісно, потік інструкцій, виконуваних процесором. Але можна змінити порядок цих інструкцій, розподілити їх за групами, які виконуватимуться паралельно, без зміни результату роботи всієї програми. Цей прийом відомий як паралелізм лише на рівні інструкцій. Просування розвитку паралелізму лише на рівні інструкцій в архітектурі комп'ютерів відбувалися з середини 1980-х до середини 1990-х.

Сучасні процесори мають багатоступінчастий конвеєр команд. Кожному щаблі конвеєра відповідає певна дія, що виконується процесором у цій інструкції на цьому етапі. Процесор з N ступенями конвеєра може мати одночасно N різних інструкцій на різному рівні закінченості. Класичний приклад процесора з конвеєром - це RISC-процесор з 5-ма ступенями: вибірка інструкції з пам'яті (IF), декодування інструкції (ID), виконання інструкції (EX), доступ до пам'яті (MEM), запис результату в регістри (WB) . Процесор Pentium 4 має 35-ступінчастий конвеєр.

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

2.3 Паралелізм даних

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

2.4 Паралелізм завдань (багатопоточність)

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

2.5 Розподілені операційні системи

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

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

Робота додана на сайт сайт: 2016-06-20

"Лекція " xml:lang="en-US" lang="en-US">6

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

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

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

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

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

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

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

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

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

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

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

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

1. Довжина графа (кількість ярусів)" xml:lang="en-US" lang="en-US">L">.

2. Ширина " xml:lang="en-US" lang="en-US">i->го ярусу - " xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">.

3. Ширина графа ярусно-паралельної форми |" xml:lang="en-US" lang="en-US">B">= " xml:lang="en-US" lang="en-US">max">(" xml:lang="en-US" lang="en-US">b;vertical-align:sub" xml:lang="en-US" lang="en-US">i">).

4. Середня ширина графа ЯПФ В;vertical-align:sub">ср "> ">.

5. Коефіцієнт заповнення" xml:lang="en-US" lang="en-US">i">-го ярусу | " xml:lang="en-US" lang="en-US">k;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> ">.

6. Коефіцієнт розкиду операцій у графі -" xml:lang="en-US" lang="en-US">Q;vertical-align:super" xml:lang="en-US" lang="en-US">j;vertical-align:sub" xml:lang="en-US" lang="en-US">i"> ">, " xml:lang="en-US" lang="en-US">j">БНО, де ">- кількість " xml:lang="en-US" lang="en-US">j->-го типу операцій у" xml:lang="en-US" lang="en-US">i">-м ярусі.

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

8. Мінімальний час вирішення алгоритму (сума часів спрацьовування обчислювачів з максимальним обсягом обчислень по кожному ярусу);vertical-align:sub" xml:lang="en-US" lang="en-US">min">.

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

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

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

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

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

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

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

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

а) зменшення висоти дерев арифметичних виразів (рис.6.3);

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

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

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

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

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

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

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

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

Ступінь паралелізму"> (" xml:lang="en-US" lang="en-US">D">) "> це порядок числа паралельно працюючих пристроїв у системі при реалізації алгоритму завдань, за умови, що кількість процесорів (обробних пристроїв) не обмежена.

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

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

3) Високий ступінь: від 100 до 10;vertical-align:super">4 "> процесорів.

4) Надвисокий ступінь: від 10;vertical-align:super">4 ">до 10 ;vertical-align:super">6 "> процесорів.

Графічне подання параметра" xml:lang="en-US" lang="en-US">D">(" xml:lang="en-US" lang="en-US">tяк функції часу називають профілем паралелізму програми. На рис.6.5 показаний типовий профіль паралелізму.

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

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

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

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

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

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

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

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

а) між частинами програми;

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

3. Командний рівень (між фазами виконання команд).

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

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

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

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

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

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

1. На рівні логічних вентилів та елементів пам'яті (рис.6.6).

2. Рівень логічних схем та простих автоматів з пам'яттю (рис.6.7).

3. Рівень регістрів та інтегральних схем пам'яті (рис.6.8).

4. Рівень елементарних мікропроцесорів (рис.6.9).

5. Рівень макропроцесорів, що реалізують великі операції (рис.6.10).

6. Рівень обчислювальних машин, процесорів та програм (рис.6.11).

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

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

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

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

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

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

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

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

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

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

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

-> між ними немає зв'язку по робочим полям пам'яті;

- вони повинні виконуватися за різними програмами;

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

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

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

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

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

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

5. Модель завдання

Модель завдання будується для порівняльного аналізу структур паралельних ЕОМ. Тому вона повинна мати досить загальний характер і описувати лише склад форм паралелізму та типів зв'язків.

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

скалярних ділянок (СК);
ділянок із паралелізмом незалежних гілок (ВТ);
векторні ділянки (ВК).

Модель завдання - це сукупність параметрів, що характеризують паралельну програму

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

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

" xml:lang="en-US" lang="en-US">Wск

" xml:lang="en-US" lang="en-US">Wвт

" xml:lang="en-US" lang="en-US">W">вк

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">ск

" xml:lang="en-US" lang="en-US">m;vertical-align:sub" xml:lang="en-US" lang="en-US">вт

" xml:lang="en-US" lang="en-US">m;vertical-align:sub">вк

" xml:lang="en-US" lang="en-US">А

" xml:lang="en-US" lang="en-US">В

" xml:lang="en-US" lang="en-US">C

обсяг обчислень

відносна довжина

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

1.2.1 Принципова можливість паралельної обробки

Практично всі розроблені на цей час алгоритми є послідовними. Наприклад, при обчисленні виразу a + b × c спочатку необхідно виконати множення і тільки потім виконати додавання. Якщо в електронно-обчислювальних машин присутні вузли складання та множення, які можуть працювати одночасно, то в даному випадку вузол додавання буде простоювати в очікуванні завершення роботи вузла множення. Можна довести твердження, яке полягає в тому, що можливо побудувати машину, яка заданий алгоритм оброблятиме паралельно.

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

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

1.2.2 Абстрактні моделі паралельних обчислень

Модель паралельних обчислень забезпечує високорівневий підхід до визначення характеристик та порівняння часу виконання різних програм, при цьому абстрагуються від апаратного забезпечення та деталей виконання. Першою важливою моделлю паралельних обчислень стала машина з паралельним випадковим доступом (PRAM – Parallel Random Access Machine), яка забезпечує абстракцію машини з пам'яттю (PRAM є розширенням моделі послідовної машини з довільним доступом RAM – Random Access Machine). Модель BSP (Bulk Synchronous Parallel, масова синхронна паралельна) поєднує абстракції як розділеної, і розподіленої пам'яті. Вважається, що це процесори виконують команди синхронно; у разі виконання однієї і тієї ж команди PRAM є абстрактною SIMD-машиною (SIMD – Single Instruction stream/Multiple Data stream – одиночний потік команд поряд з множинним потоком даних), проте процесори можуть виконувати й різні команди. Основними командами є зчитування з пам'яті, запис у пам'ять та звичайні логічні та арифметичні операції.

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

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

Моделювати схеми з функціональних елементів за допомогою паралельних машин із довільним доступом (PRAM) дозволяє теорема Брента. Як функціональні елементи можуть виступати як 4 основних (що здійснюють логічні операції NOT, AND, OR, XOR - заперечення, логічне І, логічне АБО і виключає АБО відповідно), більш складні NAND і NOR (І-НЕ та АБО-НЕ), так та будь-якої складності.

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

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

Малюнок 1. Моделювання схеми розміру 15, глибини 5 із двома процесорами за допомогою паралельної машини з довільним доступом (PRAM – машина)

На малюнку 1 наведено результат моделювання схеми розміром (загальна кількість процесорів) n=15 при глибині схеми (максимальна кількість елементів на кожному з рівнів глибини) d=5 з числом процесорів p=2 (одночасно моделювані елементи об'єднані групи прямокутними областями, причому для кожній групі вказаний крок, на якому моделюються її елементи, моделювання відбувається послідовно зверху вниз у порядку зростання глибини, на кожній глибині р штук за раз). Відповідно до теореми Брента моделювання такої схеми займе трохи більше ceil(15/2+1)=9 кроків.

Міністерство освіти та науки Російської Федерації

ФДБОУ ВПО «Брянська державна інженерно-технологічна

академія»

Кафедра інформаційних технологій

Послідовна та паралельна обробка інформації

Розрахунково-графічна робота № 1

з дисципліни

"Технології обробки інформації"

Варіант №16

РГР-02068025.230400.084

Брянськ 2015

Вступ 3

Паралельна обробка інформації 4

Системи з поділом пам'яті 6

Паралельна SQL-обробка 7

Послідовна обробка інформації 9

Прості пакетні системи 10

Список литературы 13

Вступ

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

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

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

Паралельна обробка інформації

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

Паралельна обробка. Якщо якийсь пристрій виконує одну операцію за одиницю часу, тисячу операцій він виконає за тисячу одиниць. Якщо припустити, що є п'ять таких самих незалежних пристроїв, здатних працювати одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту роботу виконає за 1000/N одиниць часу. Подібні аналогії можна знайти і в житті: якщо один солдат закопає город за 10 годин, то рота солдатів з п'ятдесяти чоловік з такими ж здібностями, працюючи одночасно, впораються з тією ж роботою за 12 хвилин – принцип паралельності у дії!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ієрархія пам'яті.
Ієрархія пам'яті п'яного ставлення до паралелізму немає, проте, безумовно, належить до особливостям архітектури комп'ютерів, які має значення підвищення їх продуктивності (згладжування різниці між швидкістю роботи процесора і часом вибірки з пам'яті). Основні рівні: регістри, кеш-пам'ять, оперативна пам'ять, дискова пам'ять. Час вибірки за рівнями пам'яті від дискової пам'яті до регістрів зменшується, вартість перерахунку на 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 землекопів? За хвилину? Звичайно ж ні! Починаючи з деякого моменту вони просто заважатимуть один одному, не прискорюючи, а уповільнюючи процес. Так само і в комп'ютерах: якщо завдання надто мало, то ми довше займатимемося розподілом роботи, синхронізацією процесів, збиранням результатів тощо, ніж безпосередньо корисною роботою.

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

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