16.Закон Амдала

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

Випадок α=0 відповідає повністю паралельній програмі й ми одержуємо N-кратний приріст, випадок α=1 – повністю послідовної, і в цьому випадку приросту немає. Закон Амдала деякою мірою допомагає відчути складність паралельного програмування: наприклад, для прискорення виконання програми в 100 разів, необхідно, щоб 99,99% операцій в програмі можливо було б виконувати з 100-кратним розпаралеленням.

Устремління числа процесорів N у нескінченність приводить до очевидного результату: S(∞,α) = 1/α, тобто принципово неможливо одержати прискорення більше 1/α при будь-якій кількості використовуваних процесорів.

17.Закон Густавсона – Барсиса

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

де (n) і (n) є часи послідовної і паралельної частин виконуваних обчислень відповідно, тобто

З урахуванням введеної величини g можна отримати

що дозволяє побудувати оцінку для прискорення

Спрощення останньої оцінки для прискорення

Оцінку прискорення, що отримується відповідно до закону Густавсона-барсиса, ще називають прискоренням масштабування (scaled speedup), оскільки дана характеристика може показати, наскільки ефективно можуть бути організовані паралельні обчислення при збільшенні складності вирішуваних завдань

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

Якщо складність вирішуваного завдання є фіксованою (T1=const), то при зростанні числа процесорів ефективність, як правило, убуватиме за рахунок зростання накладних витрат T0

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

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

19.----

20. Навести та охарактеризувати основні типи апаратних комунікаційних інтерфейсів для організації високопродуктивних систем опрацювання даних.

-myrinet

-sci (scalable coherent interface)

-infiniband

-gigabit ethernet

-fastethernet

Myrinet (ANSI/VITA 26-1998) - широко вживаний для побудови кластерів тип комунікаційного середовища.

Характеристики

Топологія: комутована, елементом комутації є матриця 8х8. Комутатори на її основі підтримують до 128 портів. Для побудови великих мереж використовуються різні варіанти топології Fat Tree, найкраща продуктивність досягається з використанням Clos Network. Програмне забезпечення: низькорівневий інтерфейс програмування GM, MPICH/GM, PVM/GM, стік TCP/IP, а також комерційні продукти - MPIPro, Scali MPI Connect.

Ethernt (эзернет, від латів. aether - ефір) - пакетна технологія комп'ютерних мереж, переважно локальних.

Gigabit Ethernet (GbE) - термін, що описує набір технологій для передачі пакетів Ethernet зі швидкістю 1 Гбіт/с. Він визначений в документі IEEE 802.3-2005. Існують чотири різних фізичних шари стандартів для Gigabit Ethernet, використовуючи оптоволокні (1000Base-X) кабель, вита пара (1000Base-T), або збалансований мідний кабель (1000Base-CX).

В IEEE 802.3z стандарт включає 1000Base-SX для передачі багатомодові волокна, 1000Base-LX для передачі одномодові волокна, і майже застарілих 1000Base-CX для передачі збалансованим мідним кабелем. Ці стандарти використовують 8b/10b кодування, який розширює канал на 25%, з 1000 Мбіт / с до 1250 Мбіт / с для забезпечення DC збалансований сигнал. Символи надіслано з допомогою NRZ.

IEEE 802.3ab, який визначає широко використовуються 1000Base-T тип інтерфейсу, що використовує іншу схему кодування, з тим щоб тримати швидкість як можна більш низькому рівні, що дозволило передачі по витій парі.

Fast Ethernet (Швидкий Ethernet) - термін, що описує набір стандартів Ethernet для пакетної передачі даних з номінальною швидкістю 100 Мбіт/с, що в 10 разів швидше за початкову для Ethernet швидкість у 10 Мбіт/с

Більш складна структура фізичного рівня технології Fast Ethernet викликана тим, що в ній використовуються три варіанти кабельних систем: волоконно-оптичний багатомодовый кабель, використовуються два волокна; кручена пари категорії 5, використовуються дві пари; кручена пари категорії 3, використовуються чотири пари. Офіційний стандарт 802.3u встановив три різних специфікації для фізичного рівня Fast Ethernet і дав їм наступні назви (мал. 3.21): l00Base-TX для двопарного кабелю на неекранованій кручений парі UTP категорії 5 чи екранованій кручений парі STP Type 1; 100Base-T4 для кабелю з чотирьох пар на неекранованій кручений парі UTP категорії 3, 4 чи 5; l00Base-FX для багатомодового оптоволоконого кабелю, використовуються два волокна.

Infiniband — високошвидкісна комутована послідовна шина, що застосовується як для внутрішніх (внутрісистемних), так і для міжсистемних з'єднань.

Подібно PCI Express Infiniband використовує двонаправлену послідовну шину. Базова швидкість - 2,5 Гбіт/с в кожному напрямі; зараз (2006 р.) застосовуються, найчастіше, Single Data Rate (SDR) канали (англ. lanes) 1x, 4x і 12x. Підтримується також робота з Double Data Rate (DDR, 20 Гбіт/с) і Quad Data Rate (QDR, 40 Гбіт/с).

Основне призначення Infiniband - міжсерверні з'єднання, у тому числі і для організації RDMA (Remote Direct Memory Access).

Протоколи і API

Infiniband використовується наступними протоколами і API:

RDMA (англ. Remote Direct Memory Access)

uDAPL (англ. User Direct Access Programming Library)

IPoIB (IP over Infiniband)

SRP (англ. SCSI RDMA Protocol)

DDP (англ. Direct Data Placement

SDP (англ. Socket Direct Protocol)

Характеристики

Виробники: найбільш поширені апаратні рішення від компаній Qlogic, Mellanox, Voltaire, Topspin (компанія Topspin була придбана компанією Cisco в 2005-м року).

Тести виробників показують пропускну спроможність на рівні MPI близько 800 Мб/сек і час затримки 1-7 мкс.

Топологія: комутована з використанням Fat Tree для великих конфігурацій, існуючі комутатори підтримують велику кількість (>256) портів (Прімер:silverstorm).

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

Корпорацією Oracle Corporation був розроблений спеціальний протокол RDS, орієнтований на роботу з цією шиною.

SCI (Scalable Coherent Interface), є ANSI/IEEE стандартом, що визначає неймовірно гнучкий високошвидкісний протокол передачі даних для з'єднань «крапка-крапка».

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

21. Масштабований когерентний інтерфейс - Scalable Coherent Interface (SCI), є ANSI/IEEE стандартом, що визначає неймовірно гнучкий високошвидкісний протокол передачі даних для з'єднань «крапка-крапка». Хоча спочатку SCI замислювався для використання в нових, швидших об'єднувальних платах із швидкістю передачі даних більш 1Гбита/сек, його творці заглянули далеко уперед, реалізувавши в нім чудове масштабоване транспортне середовище, низьку латентність і когерентність кеша пам'яті. Інтерфейс SCI розроблений для забезпечення високоефективної передачі даних і спільного використання пам'яті між процесорами, материнськими платами або об'єднувальними платами апаратного блоку.

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

Характеристики

Виробник: компанія Dolphin, в даний час повний аналог цих адаптерів виробляється в Росії ОАО «НИЦЭВТ».

Пропускна спроможність: фізична швидкість передачі - 667 Мб/сек, залежно від використовуваних апаратних платформ пропускна спроможність на рівні MPI - від 200 до 325 Мб/сек.

Час затримки: цей тип комунікаційного середовища відрізняється рекорд низьким часом затримки: 2-3 мкс - апаратне і близько 4 мкс - на рівні MPI.

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

Програмне забезпечення: вільне (а саме, поширюване на умовах ліцензії GNU GPL) низькорівневе ПО від компанії Dolphin (драйвери і бібліотека SISCI), SCI-MPICH з Аахенського університету, а також комерційне ПО від Scali.