Размещено на http://www.allbest.ru/

БАЗОВІ ПІДХОДИ ДО КЛАСИФІКАЦІЇ ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ

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

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

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

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

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

Розрізняють такі режими виконання незалежних частин програми:

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

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

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

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

Приклади паралельних обчислювальних систем

Розмаїття паралельних обчислювальних систем величезне. Кожна така система унікальна, в кожній з них встановлюються різні апаратні складові: процесори (Intel, Power, AMD, HP, Alpha, Nec, Cray, та ін.), мережеві карти (Ethernet, Myrinet, Infiniband, SCI,...). Вони функціонують під управлінням різних операційних систем (версії Unix/Linux, версії Widjws,...) і використовують різне прикладне програмне забезпечення. Видається, що практично неможливо знайти між ними щось спільне, що не так. Далі будуть сформульовані варіанти класифікацій паралельних обчислювальних систем. Розглянемо декілька прикладів.

Суперкомп'ютери

Початком ери суперкомп'ютерів вважається 1976 різ з появою векторної системи Cray 1. Результати, показані цією системою на обмеженому в той час наборі додатків, були більш ніж вражаючими в порівнянні з іншими, тому система отримала назву "суперкомп'ютер" і протягом тривалого часу вона визначала розвиток всієї індустрії високопродуктивних обчислень. Проте в результаті сумісної еволюції архітектури та програмного забезпечення на ринку стали з'являтися системи з кардинально різними характеристиками, тому поняття "суперкомп'ютер" стало багатозначним і неодноразово переглядалися. Спроби дати означення терміну "суперкомп'ютер" базуватися не тільки на продуктивність, не зворотно приводять до необхідності постійно переглядати таку позицію. З альтернативних означень найбільш цікаві два: економічне та філософське. Перше означає, що суперкомп'ютер - це система, ціна якої вища за 1 - 2 млн. доларів США, друге - що суперкомп'ютер - це комп'ютер, потужність якого тільки на порядок менша необхідної для розв'язання сучасних задач.

Програма ASCI

Програма ASCI (http://www.llnl.gov/asci/) - Accelerated Strategic Computing Initiative, яка підтримується Міністерством енергетики США, в якості однієї з основних цілей - створення суперкомп'ютерів з продуктивністю в 100 TFlops (Терафлопс, означає 1 трильйон операцій за секунду). Перша система серії ASCI - ASCI Red, створена в 1996 р. компанією Intel, стала першим в світі комп'ютером з продуктивністю в 1 TFlops, яка надалі була доведена до 3 TFlops. Трьома роками пізніше з'явилися ASCI Blue Pacific від IBM та ASCI Blue Mountain від SGI, які стали першими на той час суперкомп'ютерами з швидкодією 3 TFlops. В червні 2000 р. була введена в дію система ASCI White з піковою продуктивністю вище за 12 TFlops, реальна продуктивність на тесті LINPACK скала 4938 TFlops, пізніше цей показник був доведений до 7304 TFlops. Апаратно ASCI White є системою IBM RS/6000 SP з 512 симетричними мультипроцесорами (SMP) вузлами. Кожний вузол має 16 процесорів, система в цілому - 8192 процесорів. Оперативна пам'ять системи складає 4 ТВ, ємність дискового простору складає 180 ТВ. Всі вузли системи є симетричними мультипроцесорами IBM RS/6000 POWER 3 з 64 - розрядною архітектурою. Кожний вузол автономний, має власну пам'ять, операційну систему, локальний диск та 16 процесорів. Процесори POWER 3 є суперскалярними 64 - розрядними числами конвеєрної організації з двома пристроями з обробки команд з плаваючою комою та трьома пристроями з обробки цілочислових команд. Вони здатні виконувати до 8 команд за тактовий цикл та до 4 операцій з плаваючою комою за такт. Тактова частота кожного такого процесора 375 MHz.

Програмне забезпечення ASCI White підтримує мішану модель програмування - передача повідомлень між вузлами та багато потоковість всередині SMP - вузла. Операційна система є версією Unix - IBM AIX. AIX підтримує як 32 -, так і 64 - розрядні системи RS/6000. Підтримка паралельного коду на ASCI White включає паралельні бібліотеки, налагоджування, зокрема TotalView), профілювання, утиліти IBM та сервісні програми з аналізування ефективності виконання. Підтримуються бібліотеки MPI, OpenMP, потоки POSIX та транслятор директив IBM. Є паралельне налагодження IBM.

Система BlueGene. Один з найпотужніших нині суперкомп'ютерів у світі створений фірмою IBM, роботи в цьому напрямку продовжуються донині. На даний час система називається "BlueGene/L DD2 beta-System", вона є першою чергою повної обчислювальної системи. Згідно з прогнозами, на момент введення в дію в роботу її пікова продуктивність досягне 360 TFlops. Основні напрямки застосування є гідродинаміка, квантова хімія, моделювання клімату, та ін. Поточний варіант системи має такі характеристики: 32 стійки по 1024 двох ядерних 32-бітних процесори PowerPC 440 з тактовою частотою 0.7 GHz; пікова продуктивність - порядку 180 TFlops; максимально показана продуктивність (на тесті LINPACK) - 135 TFlops.

MBC - 1000

Один з найпотужніших в РФ суперкомп'ютерів - Багатопроцесорна обчислювальна система МВС-1000М встановлена у в Міжвідомчому супекомп'ютерному центрі РАН, роботи з його створення проводилися з 2000 до 2001рік. Склад системи такий: 384 двох процесорних модулі на базі Alpha 21264 з тактовою частотою 667 MHz (кеш L2 - 4 Mb), зібрані у вигляді 6 базових блоків, по 64 модулі у кожному; керуючий сервер та файл-сервер NetApp F840; мережі Myrinet 2000 та Fast/Gigabit Ethernet; мережевий монітор; система безперебійного живлення. Кожний обчислювальний модуль має по 2 Gb оперативної пам'яті, HDD 20 GB, мережеві карти Myrinet (2000 Mbit). при обміні даними між модулями з використанням протоколів МР1 на мережі Myrinet пропускна здатність в МВС-1000М складає 110-150 Mb в секунду.

Кластер AC3 Velocity Cluster

Цей кластер встановлений в Корнельському університеті США є результатом сумісної діяльності університету та консорціуму АС3 (Advanced Cluster Computing Consortium), утвореного компаніями Dell, Intel. Microsoft, Giganet та ще 15 виробників ПЗ з метою інтеграції різних технологій для створення кластерної архітектури для навчальних та державних установ. Склад кластера: 64 чотирьох процесорних сервери Dell PowerEdge 6350 на базі Intel Pentium III Xeon MHz, 4 GB HDD, 100 MBit Ethernet card; 1 восьми процесорний сервер Dell PowerEdge 6350 на базі Intel Pentium III Xeon 550 MHz, 8 GB RAM, 36 GB HDD, 100 MBit Ethernet card.

Чотирьох процесорні сервери змонтовані по вісім штук на стійку і працюють під управлінням ОС Microsoft Windows NT 4.0 Server Enterprise Edition. Між серверами встановлено з'єднання на швидкості 100 Мбайт/с через Cluster Switch компанії Giganet.

Завдання в кластері управляються з використанням Cluster ConNTroller, створеного в Корнельському університеті. Пікова продуктивність АС3 Velocity складає 122 GFlops з вартістю в 4-5 меншою, порівняно з суперкомп'ютерами з аналогічними показниками. На момент виходу в дію, в 2000 році, кластера з показниками на тесті LINPACK в 47 GFlops займав 381 стрічку в списку Top 500.

Кластер NCSA NT Supercluster

В 2000 році в Національному центрі суперкомп'ютерних технологій (NCSA - National Center for Supercomputing Applications) на основі робочих станцій Hewlett-Packard Kayak XU PC workstation був зібраний ще один кластер, для якого була вибрана операційна система OC Microsoft Windows. Розробники назвали його NT Supercluster. На момент введення в дію кластер з показником на тесті LINPACK в 62 GFlops та піковою продуктивністю в 140 GFlops займав 207 стрічку списку Top 500. Кластер побудований з 38 двох процесорних серверів на базі Intel Pentium III Xeon 550 MHz, 1 Gb RAM, 7.5 Gb HDD, 100 MBit Ethernet card. Зв'язок між вузлами базується на мережі Myrinet. Програмне безпечення кластера: операційна система - Microsoft Windows NT 4.0; компілятори - Fortran77, C/C++; рівень передачі повідомлень базується на HPVM.

Кластер Thunder

Нині чисельність систем, зібраних на основі процесорів корпорації Intel, які представлені в списку Top 500, складає 318. Самий потужний суперкомп'ютер, який представляє собою кластер на основі Intel Itanium2, встановлений в Ліверморській національній лабораторії (США). Апаратна конфігурація кластера Thunder (http://www.llnl.gov/linux/thunder/); 1024 сервери, по 4 процесори Intel Itanium 1.4GHz в кожному; 8 Gb оперативної пам'яті на вузол; загальна місткість дискової системи 150 Tb. Програмне забезпечення: операційна система CHOS 2.0; середовище паралельного програмування MPICH2; налагоджування паралельних програм TotalView; Intel та GNU Fortran, C/C++ компілятори. Нині кластер Thunder займає 5 позицію списку Top 500 (на момент встановлення - влітку 2004 року він займав 2 стрічку) з піковою продуктивністю 22938 GFlops і максимально показаною на тесті LINPACK 19940 GFlops.

2. Класифікація паралельних обчислювальних систем

Мультикомп'ютери

Це багатопроцесорні системи з розподіленою пам'яттю, які вже не забезпечують спільного доступу до всієї наявної в системі пам'яті (no-remote memory access чи NORMA). Незважаючи на всю схожість подібної архітектури з системами з розподіленою спільною пам'яттю, мультикомп'ютери мають принципову відмінність: кожний процесор системи може використовувати тільки свою локальну пам'ять, в той час як для доступу до даних, розташованих на інших процесорах, слід явним чином виконати операції передачі повідомлень (message passing operations). Такий підхід застосовується за умови побудови двох важливих типів багатопроцесорних обчислювальних систем - масивно-паралельних систем (massively parallel processor) та кластерів (clusters). Серед представників першого типу систем - IBM RS/6000 SP2, Intel PARAGON, ASCI Red, трансп'ютерні системи Parsytec та ін.; прикладами кластерів є, наприклад, системи AC3 Velocity та NCSA NT Supercluster. Характеристикою обчислювальних систем кластерного типу є надзвичайно швидкий розвиток мікропроцесорних обчислювальних систем. Під кластером розуміють множину окремих комп'ютерів, об'єднаних в мережу, для яких за допомогою апаратно-програмних засобів забезпечується можливість уніфікованого управління (single system image), надійного функціонування (availability) та ефективного використання (performance). Кластери можуть бути утворені на основі вже наявних у споживачів окремих комп'ютерів або ж сконструйовані з типових комп'ютерних елементів, що не потребує істотних фінансових витрат. Застосування кластерів може певною мірою усунути проблеми, пов'язані з розробкою паралельних алгоритмів та програм, оскільки підвищення обчислювальної потужності окремих процесорів дає змогу будувати кластери з порівняно невеликої кількості (декілька десятків) окремих комп'ютерів (lowly parallel processing). Тобто для паралельного виконання в алгоритмах розв'язку обчислювальних задач достатньо виділити тільки крупні незалежні частини розрахунків (coarse granularity), що в свою чергу, знижує складність побудови паралельних методів обчислень і зменшує потоки даних, що передаються, між комп'ютерами кластера. Разом з тим організація взаємодії обчислювальних вузлів кластера за допомогою передачі повідомлень приводить до значних часових затримок, що накладає додаткові обмеження на тип розроблюваних паралельних алгоритмів та програм. Звертається увага на відмінність поняття кластера від мережі комп'ютерів (network of workstations чи NOW). Для побудови локальної комп'ютерної мережі використовують більш прості мережі передачі даних (порядку 100 Мбіт/сек). Комп'ютери мережі більше розосереджені, тому користувачі можуть застосувати їх для виконання якихось додаткових робіт. Слід зауважити, що існують також інші способи класифікації обчислювальних систем.

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

1) Повний граф 2) Лінійка

3) Кільце 4) Зірка

5) 2 - вимірна решітка 6) 3 - вимірна решітка

Приклади топології багатопроцесорних обчислювальних систем

- повний граф (completely-connected graph або clique) - система, в якій між будь-якою парою процесорів існує пряма лінія зв'язку. Така топологія забезпечує мінімальні затрати при передачі даних, проте вона має складну реалізацію за умови великої кількості процесорів;

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

- кільце (ring) - ця топологія отримується з лінійки процесорів з'єднанням першого і останнього процесорів лінійки;

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

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

- гіперкуб (hypercube) - ця топологія є окремим випадком структури решітки, коли за кожною розмірністю сітки є тільки два процесори (тобто гіперкуб містить 2N процесорів при розмірності N). Такий варіант організації мережі передачі даних поширений на практиці і характеризується таким рядом розпізнавальних ознак: два процесори мають з'єднання, якщо двійкові зображення їх номерів мають тільки одну відмінну позицію; в N- вимірному гіперкубі кожний процесор зв'язаний рівно з N сусідами; N - вимірний гіперкуб можна розділити на два (N-1) - вимірних гіперкуби (всього можливі N таких варіантів розбиття); найкоротший шлях між двома будь-якими процесорами має довжини, яка співпадає з кількістю відмінних бітових значень в номерах процесорів (ця величина називається відстанню Хеммінга). обчислювальний програмний комп'ютерний мультипроцесор

Топологія мережі обчислювальних кластерів

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

Характеристики топології мережі

Як основні характеристики топології мережі передачі даних використовуються такі показники:

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

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

- ширина бінарного поділу (bisection width) - показник, який визначається як мінімальна кількість дуг, які слід видалити для розділу мережі передачі даних на дві незв'язні області однакового розміру;

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

Для порівняння в таблиці 6.1 наводяться значення перерахованих показників для різних топологій мережі передачі даних.

Таблиця Характеристики топологій мережі передачі даних (р - кількість процесорів)

Характеристика системних платформ для побудови кластерів

За системну платформу для побудови кластерів використовують обидві поширені нині операційні системи Unix та Microsoft Windows. Далі розглядатимемо рішення на основі ОС сім'ї Microsoft Windows. Microsoft Compute Cluster Server 2003 (CCS) є інтегрованою платформою для підтримки високопродуктивних обчислень на кластерних системах. CCS складається з операційної системи Microsoft Windows Server 2003 та Microsoft Compute Cluster Pack (CCP) - набору інтерфейсів, утиліт та інфраструктури управління. Разом з ССР постачається SDK, який містить необхідні інструменти розробки програм для CCS, включно власну реалізацію MPI (Microsoft MPI). Окрім того, до Microsoft Compute Cluster Server 2003 логічно примикає Microsoft Visual Studio 2005 - інтегроване середовище розробки (IDE), яке містить компілятор та налагоджування програм, розроблених з використанням технологій MPI та OpenMP.

Як обчислювальні вузли кластера застосовуються 64 - бітові процесори сім'ї х86 з, мінімум, 512 Мб оперативної пам'яті та 4 Гб вільного дискового простору. На обчислювальних вузлах кластера слід встановити ОС Microsoft Windows Server 2003 (Standard, Enterprise або Compute Cluster Edition). До складу CCP входить Microsoft MPI - версія реалізації стандарту MPI 2 від Argonne National Labs. MS MPI сумісна з МРІСН 2 і підтримує повнофункціональний АРІ з більш ніж 160 функціями. MS MPI у Windows Compute Cluster Server 2003 задіє WinSock Direct протокол для найкращої продуктивності та ефективного використання центрального процесора. MS MPI може використати будь-яке Ethernet з'єднання, яке підтримується Windows Server 2003, та з'єднання InfiniBand чи Myrinet, з використанням WinSock Direct драйверів, які постачаються виробниками апаратного забезпечення. MS MPI підтримує мови програмування C, Fortran 77, Fortran 90, a Microsoft Visual Studio 2005 включає паралельне налагоджування, яке працює з MS MPI. Розробники можуть запустити свій MPI - додаток на декількох обчислювальних вузлах, та Visual Studio автоматично з'єднатися з процесами на кожному вузлі, надаючи змогу розробнику призупиняти додаток і проглядати значення змінних в кожному процесі окремо.

Крім реалізації MPI до складу ССР входить зручна система планування завдань, яка дає змогу проглядати стан всіх запущених задач, збирати статистику, призначати запуски програм на певний час, завершувати "завислі" задачі, та ін. В поточній версії робота можлива або через графічний інтерфейс, або через командну стрічку. В остаточній версії буде передбачена можливість звертання до системи та через інші інтерфейси: СОМ, web - сервіс, та ін. Windows Compute Cluster Server 2003 підтримує 5 різних мережевих технологій, причому кожний вузол може мати від 1 до 3 мережевих карток. Правильний вибір використовуваної технології необхідний для оптимального функціонування обчислювального кластера.

3. Рівні розпаралелювання обчислень

Класифікація паралельності за рівнями, що відрізняються показниками абстрактності розпаралелювання задач наведена в табл.6.2. Чим "глибше" рівень, в якому наступає паралельність, тим детальнішим, малоелементнішим буде розпаралелювання, що торкається елементів програми (інструкція, елементи інструкції тощо). Чим вище розміщено рівень абстракції, тим більші блоки має паралельність.

Таблиця Рівні паралельності обчислень

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

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

На цьому найвищому рівню одночасно ( або щонайменше розподілено за часом) виконуються комплектні програми (рис.6.2). Машина, що виконує ці програми, не повинна бути паралельною ЕОМ, досить того, що в ній наявна багатозадачна операційна система (наприклад, реалізована як система розподілу часу). В цій системі кожному користувачеві відповідно до його пріоритету планувальник (Scheduler} виділяє відрізок часу різної тривалості. Користувач одержує ресурси центрального процесорного блоку тільки впродовж короткого часу, а потім стає в чергу на обслуговування.

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

Рівень процедур

На цьому piвні різні розділи однієї і тієї самої програми мають виконуватися паралельно. Ці розділи називаються "процесами" i відповідають приблизно послідовним процедурам. Проблеми поділяються на суттєво незалежні частини так, щоб по можливості рідше виконувати операції обміну даними між процесами, які потребують відносно великих витрат часу. В різних галузях застосування стає ясно, що цей рівень паралельності ні в якому разі не обмежується розпаралелюванням послідовних програм. існує великий ряд проблем, які потребують паралельних структур цього типу навіть тоді, коли так само, як i на програмному piвні, у користувача є тільки один процесор.

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

Рівень арифметичних виразів

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

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

Рівень двійкових розрядів

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

4. Паралельні операції

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

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

Одномісцеві операції

Приклад 9_>3 "Корінь"

б). Скаляр _> вектор Розмноження числової величини

Приклад 9_>(9,9,9,9) "Broadcast"

в). Вектор _> скаляр Редукція вектора в скаляр

Приклад (1,2,3,4)_>10 "Складання"

(із спрощувальним припущенням, що довжина вектора не змінюється)

г-1) Локальна векторна покомпонентна операція.

Приклад: (1,4,9,16) _>*(1,.2,3,4) "Корінь"

г-2) Глобальна векторна операція з перестановками.

Приклад: (1,2,3,4) _>* (2,4,3,і) "Заміна місць компонент вектора"

г-3) Глобальна векторна операція (часто складається з простих операцій)

Приклад: (і,2,3,4) _> (1,3,6,10) "Часткові суми"

Двомісцеві операції

д) (скаляр, скаляр)_> вектор Послідовне виконання

Приклад: (1,2)_>3 Скалярне складання"

е) (скаляр, вектор)_>вектор Покомпонентне застосування операцій над скаляром i вектором

Приклад: (3,(1,2,3,4))_>(4,5,6,7) "Складання скаляра з вектором";

операція виконується як послідовність операцій б) та є) складання векторів:

є) (вектор, вектор) _> вектор Покомпонентне застосування операції над двома векторами

Приклад: ((1,2,3,4),(0,і,3,2)) _> (1,3,6,6) "Складання векторів"

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

Приклад: Скалярний добуток

((1,2,3),(4,2,1))(4,4,3) 11

5. Алгорим паралельних обчислень

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

Перший етап: Розбиття задачі на незалежні підзадачі.

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

Третій етап: Збирання результатів роботи окремих процесорів.

Размещено на Allbest.ru