трспо. Лекція Колективні операції обміну повідомленнями в mpi
 Скачать 3.37 Mb.
|
|
4. Продуктивність паралельних обчислень. Найважливішим критерієм ефективності паралельного програмування є швидкодія програми, її продуктивність. На продуктивність впливають різні фактори. Це технологія виконання апаратної частини (в тому числі електронних компонентів), архітектура обчислювальної системи, методи управління ресурсами, ефективність паралельного алгоритму, особливості структури даних, ефективність мови програмування, кваліфікація програміста, ефективність транслятора і т. д. Час виконання програми залежить від часу доступу до головної і зовнішньої пам'яті, кількості операцій введення та виведення, завантаженості операційної системи. Процесор управляється тактовим генератором, що виробляє керуючі імпульси фіксованої тривалості – такти. Зворотна тривалості імпульсу величина називається частотою. Виконання кожної машинної команди вимагає кількох тактів. Кількість тактів на команду (CPI — Cycles Instruction Per) характеризує трудомісткість і тривалість команди. В різних класах програм різне середнє значення CPI, тому воно може служити чисельною характеристикою програми. Процесорний час, необхідний для виконання програми, можна визначити за формулою: T=Ni*CPI*t, де Ni – кількість машинних команд у програмі, a t – тривалість такту. Швидкодія процесора вимірюється в MIPS (Million Instructions Per Second). MIPS зворотно пропорційна CPI. 4.1. Закон Амдала У загальному випадку структура інформаційного графа алгоритму займає проміжне положення між крайніми випадками повністю послідовного і повністю паралельного алгоритму. У цій структурі є фрагменти, які допускають одночасне виконання на декількох функціональних пристроях – це паралельна частина програми. Є і фрагменти, які повинні виконуватися послідовно і на одному пристрої – це послідовна частина програми. З допомогою інформаційного графа можна оцінити максимальне прискорення, якого можна досягти при розпаралелюванні алгоритму там, де це можливо. Припустимо, що програма виконується на машині, архітектура якої ідеально відповідає структурі інформаційного графа програми. Нехай час виконання алгоритму на послідовній машині Т1, причому Тѕ — час виконання послідовної частини алгоритму, а Тр — паралельної. Очевидно: T1 = Ts + Тр. При виконанні тієї ж програми на ідеальній паралельній машині, N незалежних гілок паралельної частини розподіляються по одній на N процесорів, тому час виконання цієї частини зменшується до величини Тр/N, а повний час виконання програми складе: T2=Ts+ Tp/N. Коефіцієнт прискорення, який показує, у скільки разів швидше програма виконується на паралельній машині, ніж на послідовній, визначається формулою: Х= Т1/Т2 = (Ts + Tp) / (Ts + Tp/N) = 1/(S + P/N), де S=Ts/(Ts + Tp) і P= Tp/(Ts + Tp) – відносні частки послідовної і паралельної частин (S+ Р= 1). Залежність коефіцієнта прискорення від числа процесорів і ступеня паралелізму алгоритму (відносної частки паралельної частини) носить назву закону Амдала. Для програм (алгоритмів) з невеликим ступенем паралелізму використання великого числа процесорів не дає скільки-небудь значного виграшу в швидкодії. Якщо ж ступінь паралелізму досить велика, коефіцієнт прискорення може бути великим. Починаючи з деякого значення, збільшення числа процесорів дає тільки невеликий приріст продуктивності. На практиці, коли доводиться приймати до уваги кінцевий час обміну даними, при збільшенні кількості процесорів може спостерігатися навіть падіння продуктивності, оскільки збільшується кількість обмінів. Ступенем паралелізму називають кількість процесорів, які використовуються в кожен момент часу для виконання програми. Ступінь паралелізму може змінюватися в процесі виконання програми. Це, взагалі кажучи, змінна величина, яка залежить, зокрема, від наявності та доступності ресурсів, тому іноді вводять різні середні характеристики паралелізму. Дослідження показали, що потенційний паралелізм в наукових і технічних прикладних програмах може бути дуже великим, до сотень і тисяч команд на такт, однак реальний ("досяжний") паралелізм значно менше – 10- 20. Рисунок 2.5. Теоретичне порівняння збільшення кількості процесорних ядер та паралелізму реалізації (додатку) Закон Амдала (англ. Amdahl'slaw, іноді також Закону Амдала-Уера) — ілюструє обмеження зростання продуктивності обчислювальної системи із збільшенням кількості обчислювачів. Джин Амдал сформулював закон в 1967 році, виявивши просте по суті, але непереборне за змістом обмеження на зростання продуктивності при розпаралелюванні обчислень: «У випадку, коли завдання поділяється на кілька частин, сумарний час його виконання на паралельній системі не може бути менше часу виконання самого довгого фрагмента». Згідно з цим законом, прискорення виконання програми за рахунок розпаралелювання її інструкцій на множині обчислювачів обмежена часом, необхідним для виконання її послідовних інструкцій. 4.2 Особливості закону Амдала. Закон Амдала описує максимальний теоретичний виграш в продуктивності паралельного рішення по відношенню до кращого послідовного вирішення. Закон Амдала описується наступною математичною формулою: де у скільки разів можна прискорити обчислення (прискорення), n – кількість процесорів (ядер), - частка послідовно обчислюваного коду ( ). Закон Амдала, незважаючи на те, що він не враховує багатьох факторів, накладає обмеження на максимально досяжну ефективність паралельного алгоритму. Припустимо, наприклад, що , тобто дві третини операцій в алгоритмі можуть виконуватися паралельно, а третина – ні. Тоді прискорення . Таким чином, незалежно від кількості процесорів (ядер) і навіть при ігноруванні всіх витрат на підготовку даних не можна прискорити рішення завдання більш, ніж у три рази. 4.3. Закон Густавсона. Закон Густавсона-Барсиса (1988р) оцінює максимально допустиме прискорення виконання паралельної програми, в залежності від кількості одночасно виконуваних потоків обчислень і частки послідовних розрахунків. Формула Густавсона - Барсиса виглядає наступним чином: Де – частка послідовних розрахунків в програмі, n – кількість процесорів. Густавсон зауважив, що, працюючи на багатопроцесорних системах, користувачі схильні до зміни тактики вирішення задачі. Тепер зниження загального часу виконання програми поступається обсягу розв'язуваної задачі. Така зміна мети обумовлює перехід від закону Амдала до закону Густавсона. Приміром, на 100 процесорах програма виконується 20 хвилин. При переході на систему з 1000 процесорами можна досягти часу виконання близько двох хвилин. Однак для одержання більшої точності рішення має сенс збільшити обсяг розв'язуваної задачі, тобто при збереженні загального часу виконання користувачі прагнуть отримати більш точний результат. Збільшення обсягу розв'язуваної задачі призводить до збільшення частки паралельної частини, так як послідовна частина (введення/виведення, менеджмент потоків, точки синхронізації тощо) не змінюється. Рисунок 2.6. Ілюстрація закону Амдала. Прискорення програми з допомогою паралельних обчислень на декількох процесорах Лекція 1. Головні складові архітектури високопродуктивних обчислювальних систем. План лекції: 1. Історія розвиткувисокопродуктивних обчислювальних систем. 2. Класифікація паралельних архітектур по Флінну 3. Основні елементи архітектури високопродуктивних обчислювальних систем. 3.1. Конвеєри 3.2. RISC-процесори 3.3. Суперскалярні процесори 3.4. Суперскалярні процесори зі наддовгим командним словом 4. Архітектура багатоядерних процесорів 5. Різниця між багатоядерною архітектурою і технологією гіперпоточності 6. Векторно-конвеєрні комп'ютери 7. Симетричні мультипроцесорні системи SMP 8. Системи з масовим паралелізмом (МРР) Архітектура комп'ютера – це опис основних комп'ютерних комплектуючих та їх взаємозв'язку. Традиційна фон-нейманівська архітектура базується на таких принципах: • програма зберігається на комп'ютері; • програма під час виконання та необхідні для її роботи дані розташовані в оперативній пам'яті; • існує арифметико-логічний пристрій, який виконує арифметичні та логічні операції над даними; • існує пристрій управління, який інтерпретує команди, вибрані з пам'яті, та виконує їх; • пристрої вводу та виводу (ВВ) використовуються для введення програм і даних і для відображення результатів обчислення. Працює під управлінням пристрою управління. Основні методи підвищення продуктивності засновані на розширеннях традиційної архітектури фон Неймана, у тому числі: • конвеєрній обробці команд і даних; • використанні процесорів зі скороченим набором команд (RISC). Процесорами RISC більшість команд виконується за 1-2 такти; • використанні суперскалярних процесорів; • векторній обробці даних; • використанні процесорів з наддовгим командним словом; • використанні багатопроцесорних конфігурацій. Найбільш перспективним класом високопродуктивних систем є багатопроцесорні системи. В організації багатопроцесорних обчислювальних систем можна підкреслити наступні ключові моменти: • кількість окремих процесорів та їх архітектура; • структура та організація доступу до оперативної пам'яті; • топологія комунікаційної мережі і її швидкодія; • робота з пристроями вводу-виводу. Найбільш важливою характеристикою багатопроцесорної обчислювальної системи є її масштабованість. Масштабованість – це міра, яка вказує на те, чи можна вирішити дану проблему швидше, якщо збільшити кількість процесорних елементів. Цю властивість має як апаратне, так і та програмне забезпечення. 1. Історія розвитку високопродуктивних обчислювальних систем У процесі розвитку суперкомп'ютерних технологій ідею підвищення продуктивності обчислювальної системи за рахунок збільшення числа процесорів використовували неодноразово. Якщо не вдаватися занадто глибоко в історичний екскурс і обговорення всіх таких спроб, то можна таким чином коротенько описати розвиток подій. Експериментальні розробки по створенню багатопроцесорних обчислювальних систем почалися в 70-х роках 20 століття. Однією з перших таких систем стала розроблена в Іллінойському університеті (мультипроцесорна обчислювальна система) МОС ILLIAC IV, яка включала 64 (у проекті до 256) процесорних елемента (ПЕ), що працюють за єдиною програмою, відповідно до вмісту власної оперативної пам'яті кожного ПЕ. Обмін даними між процесорами здійснювався через спеціальну матрицю комунікаційних каналів. Зазначена особливість комунікаційної системи дала назву "матричні суперкомп'ютери" відповідного класу МВС. Відзначимо, що більш широкий клас МОС з розподіленою пам'яттю і з довільною комунікаційною системою отримав згодом назву "багатопроцесорні системи з масовим паралелізмом", або МОС з MPP- архітектурою (MPP - MassivelyParallelProcessing). При цьому, як правило, кожен з ПЕ MPP системи є універсальним процесором, чинним за своєю власною програмою (на відміну від загальної програми для всіх ПЕ матричної МОС). Перші матричні МОС випускалися буквально поштучно, тому їх вартість була фантастично високою. Серійні ж зразки подібних систем, такі як ICL DAP, що включали до 8192 ПЕ, з'явилися значно пізніше, проте не набули широкого поширення зважаючи на складність програмування МОС з одним потоком управління (з однією програмою, спільною для всіх ПЕ). Перші промислові зразки мультипроцесорних систем з'явилися на базі векторно-конвеєрних комп'ютерів в середині 80-х років. Найбільш поширеними МОС такого типу були суперкомп'ютери фірми Cray. Однак такі системи були надзвичайно дорогими і вироблялися невеликими серіями. Як правило, в подібних комп'ютерах об'єднувалося від 2 до 16 процесорів, які мали рівноправний (симетричний) доступ до загальної оперативної пам'яті. У зв'язку з цим вони отримали назву симетричні мультипроцесорні системи (SymmetricMulti-Processing - SMP). Як альтернатива таким дорогим мультипроцесорним системам на базі векторно-конвеєрних процесорів була запропонована ідея будувати еквівалентні за потужністю багатопроцесорні системи з великого числа дешевих серійно виготовляємих мікропроцесорів. Однак дуже скоро виявилося, що SMP архітектура має дуже обмежені можливості з нарощуванням числа процесорів в системі, через різке збільшення числа конфліктів при зверненні до загальної шини пам'яті. У зв'язку з цим виправданою представлялася ідея забезпечити кожен процесор власною оперативною пам'яттю, перетворюючи комп'ютер у об'єднання незалежних обчислювальних вузлів. Такий підхід значно збільшив ступінь масштабованості багатопроцесорних систем, але у свою чергу зажадав розробки спеціального способу обміну даними між обчислювальними вузлами, реалізованого зазвичай у вигляді механізму передачі повідомлень (MessagePassing). Комп'ютери з такою архітектурою є найбільш яскравими представниками MPP систем. В даний час ці два напрямки (або якісь їхні комбінації) є домінуючими в розвитку суперкомп'ютерних технологій. Щось середнє між SMP і MPP представляють собою NUMA-архітектури (NonUniformMemoryAccess), в яких пам'ять фізично розділена, але логічно загальнодоступна. При цьому час доступу до різних блоків пам'яті стає неоднаковим. В одній з перших систем цього типу Cray T3D час доступу до пам'яті іншого процесора був у 6 разів більший, ніж до своєї власної. Рисунок 1.1. SMP і NUMA-архітектури В даний час розвиток суперкомп'ютерних технологій йде за чотирма основними напрямками: векторно-конвеєрні суперкомп'ютери, SMP системи, MPP системи і кластерні системи. Розглянемо основні особливості перерахованих архітектур. 2. Класифікація паралельних архітектур по Флінну Загальна класифікація архітектур ЕОМ за ознаками наявності паралелізму в потоках команд і даних була запропонована Майклом Флінном в 1966 році і розширена в 1972 році. Все розмаїття архітектури ЕОМ в цій класифікації зводиться до чотирьох класів: Рисунок 1.2. Класифікація паралельних архітектур по Флінну ОКОД - Обчислювальна система з одиночним потоком команд і одиночним потоком даних (SISD, SingleInstructionstreamover a SingleDatastream). ОКМД - Обчислювальна система з одиночним потоком команд і множинним потоком даних (SIMD, SingleInstruction, MultipleData). МКОД - Обчислювальна система з множинним потоком команд і одиночним потоком даних (MISD, MultipleInstructionSingleData). МКМД - Обчислювальна система з множинним потоком команд і множинним потоком даних (MIMD, MultipleInstructionMultipleData). Розглянемо цю класифікацію більш докладно. SISD - комп'ютери (рис. 1.3) – це звичайні послідовні комп'ютери, що виконують в кожен момент часу тільки одну операцію над одним елементом даних. Більшість сучасних персональних ЕОМ належать саме цій категорії . Кілька потоків команд і один потік даних Кілька потоків команд і кілька потоків даних Один потік команд і один потік даних Один потік команд і кілька потоків даних Команды Данные Рисунок 1.3. Схема SISD - комп'ютера Багато сучасних обчислювальні системи включають в свій склад кілька процесорів, але кожен з них працює зі своїм незалежним потоком даних , що належать до незалежної програмою . Такий комп'ютер є, фактично, набором SISD - машин, що працюють з незалежними множинами даних. SIMD-комп'ютери (рис. 1.4 і 1.5) складаються з одного командного процесора ( керуючого модуля ) , званого контролером , і декількох модулів обробки даних, званих процесорними елементами (ПЕ) . Кількість модулів обробки даних таких машин може бути від 1 024 до 16 384. Керуючий модуль приймає , аналізує і виконує команди. Типовими представниками SIMD є векторні архітектури. Рисунок 1.4. Схема SIMD - комп'ютера з роздільною пам’яттю Рисунок 1.5. Схема SIMD - комп'ютера з розподіленою пам’яттю Якщо в команді зустрічаються дані, контролер розсилає на всі ПЕ команду, і ця команда виконується або на декількох, або на всіх процесорних елементах. Процесорні елементи в SIMD – комп'ютерах мають відносно простий пристрій, вони містять арифметико-логічний пристрій (АЛП ), що виконує команди, які надходять з устрою управління (УУ) , кілька регістрів і локальну оперативну пам'ять. Однією з переваг даної архітектури вважається ефективна реалізація логіки обчислень . До половини логічних команд звичайного процесора пов'язане з управлінням процесом виконання машинних команд , а решта їх частин відноситься до роботи з внутрішньою пам'яттю процесора. У SIMD-комп'ютері управління виконується контролером, а " арифметика" віддана процесорним елементам. Підкласом SIMD-комп'ютерів є векторні комп'ютери . Приклад такої обчислювальної системи – Hitachi S3600 . Інший приклад SIMD-комп'ютера – матричні процесори ( Array Processor ) . Як приклад можна привести обчислювальну систему Thinking Machines CM - 2 , де 65536 ПЕ пов'язані між собою мережею комунікацій з топологією " гіперкуб " . Часто комп'ютери з SIMD-архітектурою спеціалізовані для вирішення конкретних завдань, що допускають матричне подання . Це, наприклад, можуть бути завдання обробки зображень, де кожен модуль обробки даних працює на отримання одного елемента кінцевого результату . Клас MI S D включає в себе багатопроцесорні системи, де процесори обробляють множинні потоки даних. Обчислювальних машин такого класу мало. Один з небагатьох прикладів – систолічний масив процесорів , в якому процесори знаходяться в вузлах регулярної решітки. Роль ребер в ній грають міжпроцесорні з'єднання, всі ПЕ управляються загальним тактовим генератором. У кожному циклі роботи кожен ПЕ отримує дані від своїх сусідів , виконує одну команду і передає результат сусідам. На рис. 1.6 дана схема фрагмента систолічного масиву. Рисунок1.6. Схема MISD - комп'ютера Належність конкретних машин до конкретного класу сильно залежить від точки зору дослідника. Так, конвеєрні машини можуть бути віднесені і до класу SISD (конвеєр – єдиний процесор), і до класу SIMD (векторний потік даних з конвеєрним процесором) і до класу MISD (безліч процесорів конвеєра обробляють один потік даних послідовно), і до класу MIMD – як виконання послідовності різних команд (операцій щаблів конвеєра) над множинним скалярним потоком даних (вектором). MIMD-комп’ютери. Цей клас архітектур (рис. 1.7 і 1.8) найбільш багатий прикладами успішних реалізацій. У нього потрапляють симетричні паралельні обчислювальні системи, робочі станції з декількома процесорами, кластери робочих станцій і т . д. Досить давно з'явилися комп'ютери з декількома незалежними процесорами , але спочатку на них був реалізований тільки принцип паралельного виконання завдань та інш. На різних процесорах одночасно виконувалися незалежні програми . Розробці перших комп'ютерів для паралельних обчислень були присвячені проекти під умовною назвою СМ* і С.ММР в університеті Карнегі (США). Технічною базою для цих проектів були процесори DEC PDP - 11. На початку 90 -х років минулого століття саме MIMD-комп'ютери вийшли в лідери на ринку високопродуктивних обчислювальних систем . Розвитком концепції MIMD-архітектури з розподіленою пам'яттю є розподілена обробка, коли замість набору процесорів в одному корпусі використовуються комп'ютери, пов'язані досить швидкої мережею. Концептуального відмінності від MIMD-архітектури з розподіленою пам'яттю немає, а особливістю є повільне мережеве з'єднання. |