Системи (мови) паралельного програмування

Вступ

Основні терміни теми

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

Рада Міністрів Української РСР – вищий орган виконавчої влади, до компетенції якого належало координація діяльності міністерств. Створена в 1946 р. замість ради Ради Народних Комісарів. Проіснувала до 1990 р., коли була перейменована у Кабінет Міністрів.

Раднаргоспи (РНГ) – створені в 1957 р. місцеві органи влади, які здійснювали управління підприємствами промисловості та іншими господарськими організаціями на території двох або більше областей. В 1965 р. ліквідовані.

 

Комп’ютерні системи з’явились в дугій половині ХХ століття і дуже скоро стали незамінним інструментом для обробки різноманітної інформації.

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

Під час вивчення дисципліни “комп’ютерні системи” більша увага буде приділена великим та супервеликим комп’ютерам, їх особливостям.

Об’єднати комп’ютери вдалось не відразу. З моменту настання такої можливості, виникла ідея об’єднання великої кількості комп’ютерів в єдину систему з метою підвищення загальної продуктивності обчислювальної техніки. В одній з самих великих сучасних комп’ютерних систем ASCI White об’єднано 8192 процесора, що дозволило досягнути максимальну продуктивність 12 Тфлопс, оперативну пам’ять 4 Тбайт, дисковий масив 160 Тбайт. Проте, треба вміти ефективно використати такі комп’ютерні системи.

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

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

 

 

Лекція № 1

 

Комп’ютерні системи і паралельна обробка інформації

 

1.1 Архітектура комп’ютерних систем

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

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

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

Комп’ютерні системи класифікують за наступними критеріями:

- по розрядності інтерфейсів і машинних слів: 8-, 16-, 32-, 64-, 128-розрядні;

- по особливостях набору регістрів, формату команд і даних: CISC, RISC,

VLIW;

- по кількості центральних процесорів: однопроцесорні, багатопроцесорні;

- багатопроцесорні за принципом взаємодії з пам'яттю: симетричні

багатопроцесорні (SMP), масивно-паралельні (MPP), розподілені.

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

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

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

Паралельні обчислення існують в декількох формах:

- паралельність на рівні інструкцій,

- паралельність даних,

- паралельність завдань.

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

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

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

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

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

Паралельність на рівні інструкцій.

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

 

Паралельність даних.

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

 

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

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

 

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

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

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

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

В результаті мережева ОС може розглядатися як набір операційних систем окремих комп'ютерів, складових мережі. На різних комп'ютерах мережі можуть виконуватися однакові або різні ОС. Наприклад, на всіх комп'ютерах мережі може працювати одна і та ж ОС UNIX. Реалістичнішим варіантом є мережа, в якій працюють різні ОС, наприклад, частина комп'ютерів працює під управлінням UNIX, частина - під управлінням NetWare, а решту – під управлінням Windows NT і Windows 98. Всі ці операційні системи функціонують незалежно один від одного в тому сенсі, що кожна з них приймає незалежні рішення про створення і завершення своїх власних процесів і управління локальними ресурсами. Але в будь-якому разі операційні системи комп'ютерів, що працюють в мережі, повинні включати взаємно погоджений набір комунікаційних протоколів для організації взаємодії процесів, що виконуються на різних комп'ютерах мережі, і розділення ресурсів цих комп'ютерів між користувачами мережі.

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

Таким чином, термін «мережева операційна система» використовується в двох значеннях: як сукупність ОС всіх комп'ютерів мережі і як операційна система окремого комп'ютера, здатного працювати в мережі. Таким чином такі операційні системи, як, Windows NT, NetWare, Solaris, HP-UX, є мережевими, оскільки всі вони володіють засобами, які дозволяють їх користувачам працювати в мережі.

 

Шляхи досягнення паралельності.

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

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

- надмірність елементів обчислювальної системи.

Організація надмірності може здійснюватися в наступних основних формах:

- використання спеціалізованих пристроїв (наприклад, окремих процесорів для різних завдань, пристроїв багаторівневої пам'яті (регістри, кеш);

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

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

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

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

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

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

 

 

Контрольні запитання

 

1 Чим відрізняється прінстонська архітектура комп’ютерних систем від гарвардської?

2 Які є форми паралельних обчислень?

3 За якими критеріями класифікують архітектури комп’ютерних систем?

4 Які методи досягнення паралельності?

5 Багатозадачний режим виконання незалежних частин програм є паралельним чи псевдопаралельним?

 

Лекція №2

Основи теорії комп’ютерних систем

 

2.1 Класифікація комп’ютерних систем

У 1966 р. М.Флінн (Flynn) запропонував класифікацію архітектури обчислювальних систем, яка з часом набула широкого визнання (рис.2.1). За основу класифікації ним було взято поняття «потоку». Під «потоком» розуміється послідовність елементів, команд або даних, оброблювана процесором. Відповідна система класифікації заснована на розгляді числа потоків інструкцій і потоків даних і описує чотири архітектурні класи:

· SISD - single instruction stream, single data stream (одиночний потік команд і одиночний потік даних);

· MISD - multiple instruction stream, single data stream (множинний потік команд і одиночний потік даних);

· SIMD - single instruction stream, multiple data stream (одиночний потік команд і множинний потік даних);

· MIMD - multiple instruction stream, multiple data stream (множинний потік команд і множинний потік даних)

а) SISD б)SIMD

в) MISD г) MIMD

Рисунок 2.1 - Класи комп’ютерних систем за класифікацією Флінна

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

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

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

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

Велика різноманітність систем, що потрапляють в даний клас, робить класифікацію Фліннна не повністю адекватною. Дійсно, і чотирипроцесорний SX-5 компанії NEC, і тисячепроцессорний Cray T3E потрапляють в цей клас.

У КС класу SISD входять однопроцесорні послідовні комп'ютери типа VAX 11/780. Проте в цей клас можна включити і векторно-конвеєрні КС, якщо розглядати вектор як одні неподільні дані для відповідної команди. У такому разі в цей клас потраплять і такі системи, як CRAY-1, CYBER 205, машини сімейства FACOM VP і багато інших.

Представниками класу SIMD також вважаються матриці процесорів: ILLIAC IV, ICL DAP, Goodyear Aerospace MPP, Connection Machine 1 і т.п. У таких системах єдиний пристрій, що управляє, контролює безліч процесорних елементів. Кожен процесорний елемент отримує від пристрою управління в кожен фіксований момент часу однакову команду і виконує її над своїми локальними даними.

Клас MIMD надзвичайно широкий, оскільки включає рзноманітні мультипроцесорні системи: CRAY Y-MP, Denelcor HEP,BBN Butterfly, Intel Paragon, CRAY T3D і багато інших. Якщо конвеєрну обробку даних розглядати як виконання безлічі команд (операцій ступенів конвеєра) не над одиночним векторним потоком даних, а над множинним скалярним потоком, то всі розглянуті вище векторно-конвеєрні комп'ютери можна розташувати і в даному класі.

Запропонована схема класифікації аж до теперішнього часу є основною при початковій характеристиці тої або іншої комп’ютерної системи. Якщо сказати, що КС належить класу SIMD або MIMD, то відразу стає зрозумілим базовий принцип її роботи, і в деяких випадках цього буває достатньо. Проте в даної класифікації є і недоліки. Зокрема, архітектура dataflow і векторно-конвеєрні машини не можливо однозначно вписати в дану класифікацію. Інший недолік - це надмірно заповнений клас MIMD. Необхідний засіб, що більш вибірково систематизує архітектуру, яка по Фліннну потрапляє в один клас, але має абсолютно різні характеристики по числу процесорів, природі і топології зв'язку між ними, за способом організації пам'яті і, звичайно ж, за технологією програмування.

Наявність фактично незаповненого класу (MISD) не вважається недоліком класифікації. Такий клас, на думку деяких дослідників в області класифікації архітектури КС, може стати надзвичайно корисними для розробки принципово нових концепцій в теорії і практиці побудови КС.

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

Рисинук 2.2 -Класикомпютернихсистем

Клас КСSIMDрозділяють на дві підгрупи. У першу підгрупу потрапляють численні суперкомп'ютери і інші машини, які оперують векторами, виконуючи одну і ту ж операцію над кожним елементом вектора. У другу підгрупу потрапляють машини типа ILLIAC IV, в яких головний блок управління посилає команди декільком незалежним АЛП.

Клас КС MIMD розділяють на мультипроцесори (машини з пам'яттю сумісного використання) і мультикомп’ютеры (машини з передачею повідомлень). Існує три типи мультипроцесорів. Вони відрізняються один від одного за способом реалізації пам'яті сумісного використання. Вони називаються UMA (Uniform Memory Access - архітектура з однорідним доступом до пам'яті), NUMA (NonUniform Memory Access - архітектура з неоднорідним доступом до пам'яті)і СОМА (Cache Only Memory Access - архітектура з доступом тільки до кеш-пам'яті).

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

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

У другу підкатегорію класу КС MIMD потрапляють мультикомп’ютери, які на відміну від мультипроцесорів не мають пам'яті сумісного використання на архітектурному рівні. Іншими словами, операційна система в процесорі мультикомп’ютера не може дістати доступ до пам'яті, що відноситься до іншого процесора, просто шляхом виконання команди LOAD. Йому доводиться відправляти повідомлення і чекати відповіді. Саме здатність операційної системи прочитувати слово з віддаленого модуля пам'яті за допомогою команди LOAD відрізняє мультипроцесори від мультикомп’ютеров. В мультикомп’ютері призначені для користувача програми можуть звертатися до інших модулів пам'яті за допомогою команд LOAD і STORE, але цю ілюзію створює операційна система, а не апаратне забезпечення. Різниця незначна, але дуже важлива. Оскільки мультикомп’ютеры не мають прямого доступу до віддалених модулів пам'яті, вони іноді називаються машинами NORMA (NO Remote Memory Access - без доступу до віддалених модулів пам'яті).

Мультикомп’ютериможна розділити на дві категорії. Перша категорія містить процесори МРР (Massively Parallel Processors - процесори з масовим паралелізмом)- дорогі суперкомп'ютери, які складаються з великої кількості процесорів, зв'язаних високошвидкісною комунікаційною мережею. Як приклади можна назвати Cray T3E і IBM SP/2.

Друга категорія мультикомп’ютерів включає робочі станції, які зв'язуються за допомогою вже наявної технології з'єднання. Ці примітивні машини називаються NOW (Network of Workstations - мережа робочих станцій)і COW (ClusterofWorkstattions - кластер робочих станцій).

 

2.2 Паралельні алгоритми

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

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

Методи і алгоритми обробки інформації, рішення задач, як правило, - послідовні. Процес “пристосування” методів до реалізації на колективі обчислювачів або процес “розщеплювання” послідовних алгоритмів рішення складних задач називається розпаралелюванням (Paralleling or Multisequencing).

Теоретична і практична діяльність по створенню паралельних алгоритмів і програм обробки інформації називається паралельним програмуванням (Parallel or Concurrent Programming). Якість паралельного алгоритму (або його ефективність) визначається методикою розпаралелювання складних завдань.

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

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

Рисунок 2.3 - Схеми паралельних алгоритмів

 

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

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

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

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

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

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

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

У 70-і роки став активно застосовуватися принцип конвеєризації обчислень. Конвеєр Intel Pentium 4 складається з 20 ступенів. Таке розпаралелювання на мікрорівні- перший крок на шляху еволюції процесорів (рис.2.4). На принципах конвеєризації базуються і зовнішні пристрої. Наприклад, динамічна пам'ять (організація чергування банків) або зовнішня пам'ять (організація RAID).

Використання паралелізму мікрорівня дозволяло лише зменшувати CPI (Cycles Per Instruction - число тактів, необхідних для виконання однієї інструкції), оскільки мільйони транзисторів при виконанні одиночної інструкції простоювали. CPI = загальна кількість тактів / число виконаних команд.

Рисунок 2.4 – Рівні паралелізму

 

На наступному етапі еволюції в 80-і роки стали використовувати паралелізм рівня командза допомогою розміщення в CPU відразу декількох конвеєрів (рис.2.4). Такі суперскалярні CPU дозволяли досягати CPI<2.

Сучасні методики підвищення ILP засновані на використанні процесорів класу SIMD. Це векторне процесування, матричні процесори, архітектура VLIW.

Паралелізм рівня потоківі рівня завданьзастосовується в процесорах класу MIMD (рис.2.4).

Паралелізм всіх рівнів властивий не тільки процесорам загального призначення (GPP), але і процесорам спеціального призначення (ASP (Application-Specific Processor), DSP (Digital Signal Processor)).

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

Дрібнозернистийпаралелізм забезпечує сам CPU, а компілятор може і повинен йому допомогти.

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

Грубозернистийпаралелізм забезпечує ОС.

 

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

 

Модель передачі повідомлень

Основні особливості даного підходу:

- програма породжує декілька завдань;

- кожному завданню привласнюється свій унікальний ідентифікатор;

- взаємодія здійснюється за допомогою відправки і прийому повідомлень;

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

Основними інструментами програмування є спеціалізовані бібліотеки (MPI - Message Passing Interface, PVM - Parallel Virtual Machines).

 

Модель паралелізму даних

Основні особливості даного підходу:

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

- "зернистість" обчислень мала;

- програміст повинен вказати транслятору, як дані слід розподілити між завданнями;

- при програмуванні на основі паралелізму даних часто використовуються спеціалізовані мови або надбудови над мовами DVM Fortran, HPF (High Perfomance Fortran) та інші.

2.3 Характеристика типових схем комунікації в багатопроцесорних комп’ютерних системах

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

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

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

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

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

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

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

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

- два процесори мають з'єднання, якщо двійкове представлення їх номерів має тільки одну позицію, що відрізняється;

- у N-мірному гіперкубі кожен процесор пов'язаний рівно з N сусідами;

- N-мірний гіперкуб може бути роздільний на два (N - 1)-мірних гіперкуба (всього можливо N різних таких розділень);

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

 

 


а) повний граф б) лінійка

 

в) кільце г) зірка

 

д) грати е) гіперкуб

 

Рисунок 2.5 – Приклади топологій багатопроцесорних комп’ютерних систем

 

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