Ширина частотної смуги комутаційних мереж.

Пропускна спроможність комутаційної мережі SIMD- структури значною мірою визначає продуктивність всієї системи. З одного боку, витрати часу на побудову схеми зв’язку і проведення комунікації, а також масиви паралельного обміну даними значно менші, ніж в MIMD – системі. Швидкість виконання локального обміну даними між фізичними сусідніми ПЕ приблизно така сама, як швидкість виконання однієї паралельної операції. З іншого боку, неструктуровані, глобальні операції обміну даними потребують для їхнього проведення значно більше часу. SIMD- системи, що мають локальну та глобальну комутаційні структури, характеризуються також відповідними двома різними величинами ширини смуги частот комутаційних мереж, вплив яких на продуктивність системи залежить від прикладної програми. В деяких програмах із складними структурами зв’язку вплив смуги пропускання комутаційної мережі дуже посилюється і може стати в певних умовах критичним фактором. Тому ширина смуги пропускання має бути якомога більшою.

З огляду на обмежену смугу пропускання глобальної комутаційної мережі, прикладні програми мають відповідати таким вимогам:

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

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

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

Робота в режимі багатьох користувачів і толерантність до помилок.

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

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

 

Навчальне видання

 

Організація паралельних обчислень

 

Навчальний посібник

з дисципліни “Паралельні та розподілені обчислення”

для студентів базового напрямку 6.0915 "Комп'ютерна інженерія"

 

Укладачі: Ваврук Євгеній Ярославович

Лашко Оксана Любомирівна

 

Редактор

Комп’ютерне верстання

 

Здано у видавництво. Підписано до друку

Формат 70х100/16. Папір офсетний. Друк на різографі

Умовн. друк. арк. Обл..-вид. арк..

Тираж прим. Зам..

 

Видавництво Національного університету “Львівська політехніка”

Реєстраційне свідоцтво ДК №751 від 27.12.2001 р.

 

Поліграфічний центр Видавництва

Національного університету “Львівська політехніка”

 

Вул.. Ф. Колесси, 2. Львів, 79000

Доповнення до лекцій (РОБОЧИЙ Варіант)

Лекція 1.

Розподілені обчислення

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

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

Зміст [сховати] · 1 Список проектів розподілених обрахунків · 2 Список українських проектів розподілених обчислень o 2.1 Біологія та медицина o 2.2 Математика та криптографія o 2.3 Природничі науки o 2.4 ПЗ для організації розподілених обчислень · 3 Дивіться також · 4 Ресурси інтернету

[ред.]Список проектів розподілених обрахунків

Нижче приведений список найбільш популярних проектів розподілених обчислень в інтернеті. Більш повний список практично всіх існуючих і закінчених проектів розподілених обчислень в інтернеті можна прогялнути на сайті Distributed Computing(англ.).

[ред.]Список українських проектів розподілених обчислень

§ Magnetism@Home

§ SLinCA@Home

[ред.] Біологія та медицина

§ Rosetta@home — вирахування структури білка із самою низькою енергією;

§ Folding@Home — проект з вирахування третинної структури білків;

§ World Community Grid — дослідження, пов'язані із генетикою людини, а також із різноманітними важкими захворюваннями. Вивчення білків, та їх каталогізація;

§ grid.org — проект з пошуку ліків від Карциноми (закінчений 27 квітня 2007 року (не знайдено));

§ Find-a-Drug — проект з пошуку ліків від різноманітних хвороб шляхом обрахунку докінгу білків із різними молекулами (закінчено 2005 року), приєднався до WCG;

§ DrugDiscovery@Home — Російський проект, Згортання білків, скрінінг баз даних біологічно активних сполук;

§ Proteins@home.

[ред.] Математика та криптографія

§ Seventeen or Bust — проект, який займається підтвердженням задачі Серпінського;

§ GIMPS — проект з пошуку простих чисел Мерсенна;

§ ZetaGrid — перевірка гіпотези Рімана (закінчено 2005 року).

§ distributed.net — проекти зі злому RC5-72 повним перебором, пошуком оптимальних лінійок Голомба - OGR-27;

§ RainbowCrack;

§ ABC@home — проект з пошуку ABC-трійок.

[ред.] Природничі науки

§ SETI@Home — проект з обробки сигналів радіотелескопу, для пошуку радіосигналів поаземних цивілізацій.

§ Einstein@Home — проект з перевірки гіпотези Ейнштейна про гравітаційні хвилі за допомогою аналізу гравітаційних полів пульсарів чинейтронних зірок.

§ Climate Prediction — проект з моделювання впливу відходів вуглекислого газу на клімат Землі.

§ Spinhenge@home — проект в області нанотехнологій, вивчення магнітних молекул.

§ LHC@home — розрахунки магнітної підсистеми прискорювача заряджених частинок — Великого адронного колайдера (LHC).

§ Muon1 DPAD — розрахунки з проектування ще потужнішого прискорювача — Neutrino Factory/Muon Collider.

§ Cosmology@home — пошук моделі, яка кращим чином описує наш Всесвіт, а також визначення діапазону моделей, які узгоджуються із сучасними астрономічними та фізичними даними;

§ AQUA@home — моделювання роботи адіабатичного квантового надпровідного комп'ютера;

§ MilkyWay@home — створення трьохмірної моделі зорь у Галактиці;

§ EDGeS@Home — проект в областіи фізики плазми, моделювання поведінки заряджених частинок в магнітному полі термоядерного реактора ITER.

[ред.] ПЗ для організації розподілених обчислень

§ Apache Hadoop

§ BOINC — відкрита інфраструктура для розподілених обрахунків Університету Берклі (Berkeley Open Infrastructure for Network Computing), яка поширюється за ліцензією LGPL.

§ Condor(англ.)

§ Globus Toolkit(англ.) — набір програм, який значно спрощує створення та керування розподіленими обрахунками.

[ред.]Дивіться також

§ Обмін повідомленнями,

§ Взаємне блокування,

§ Виклик віддалених процедур,

§ Ґрід.

[ред.]Ресурси інтернету

§ Розподілені обчислення в Україні

 

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

Способи паралельної обробки:

1. Чистий паралелізм.

2. Конвеєризація.

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

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

Якщо конвеєр кроків містить n кроків і кожен з них спрацьовує за 1 часу, то час обробки n незалежних операцій складе <L + n – 1.

Всі операції бувають двох типів: векторні і скалярні.

Якщо хоча б один елемент команди є вектором, то команда називається векторною. Тоді кількість операцій визначається: L+n-1+s, де s - час ініціалізації вектора. Векторні операції ефективні тоді, коли n>>s, в протилежному випадку вектори перетворюються в скаляри, тобто, оскільки ні s, ні L не залежать від n, то із збільшенням довжини вхідних векторів, ефективність конвеєрної обробки зростає.

Формула ефективності:

E = n/t = n /(s + L + n - 1)t = 1 /((st/n) + (Lt/n) + t - (t/n)) = 1 /t + ((s + L – 1)/n)t

При n ®¥ E ®1/t

Для формування паралельного алгоритму необхідно:

1. ідентифікувати частини роботи, які можуть бути виконані одночасно

2. відобразити зазначені частини на множину одночасно застосовуваних процесорів

3. розподілити вхідні, вихідні і проміжні дані між процесами відповідно до поставленої задачі

4. керувати доступом до спільно використовуваних даних

5. синхронізувати процеси на різних стадіях виконання програми