Тополо́гія мереж характеризує фізичну організацію вузлів (комп'ютерів, кабелів) різноманітних мереж Топологія комп'ютерних мереж

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

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

Топологія мережіспричиняєтьсяїї характеристиками. Зокрема, вибіртієїабоіншоїтопологіївпливає на:

· складнеобхідного мережного встаткування;

· характеристики мережного встаткування;

· можливостірозширеннямережі;

· спосіб керування мережею.

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

1. Фізичнатопологія (тобто схема розташуваннякомп'ютерів і прокладки кабелів).

2. Логічнатопологія (тобто структура зв'язків, характер поширеннясигналів мережею). 3. Топологіякеруванняобміном (тобто принцип і послідовністьпередачі права на захват мережіміжокремимикомп'ютерами).

4. Інформаційнатопологія (тобтонапрямокпотоківінформації, переданої мережею).

36. Функції маршрутизації даних в КС. Реверсування бітів, зсув, мережа ILLIAC.

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

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

37. Статичні топології КС: лінійна, кільцева, зіркоподібна. Параметри, переваги і недоліки.

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

У лінійній топології вузли мережі утворюють одномірний масив і з'єднані в ланцюжки.

Лінійна топологія характеризується наступними параметрами: D = N-1; d = 1 для крайніх вузлів і d = 2 для всіх інших вузлів; I = N-1; B = 1.

Кільце (ring) - це топологія, в якій кожен процесор має двох сусідів з метою комунікації.

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

В якості практичних прикладів для топології кільця можна назвати обчислювальні системи KSR1 і SCI.

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

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

Зіркоподібна мережа об'єднує безліч вузлів першого порядку за допомогою спеціалізованого центрального вузла - концентратора.

Топологія характеризується такими параметрами: D = 2; d = 1 для крайових вузлів і d = N-1 для вузла-концентратора; I = N-1; B = 1.

38. Статичні топології КС: деревоподібна, решітчата і повнозв’язна. Параметри, переваги і недоліки.

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

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

Таку мережу можна охарактеризувати наступними параметрами: D = 2log2 [(N + 1) / 2]; d = 1 для крайових вузлів, d = 2 для кореневого вузла і d = 3 для інших вузлів; I = N-1; В = 1. Діаметр для двійкового дерева зростає пропорційно лише логарифму числа вузлів, в той час як ступінь вузла залишається постійною. Мережа з такою топологією добре масштабується. Основний недолік топології - мала ширина бисекции, що передбачає обмежену смугу пропускання.

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

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

39. Статичні топології КС: тороїдальна, циліндрична і топологія гіперкуба. Параметри, переваги і недоліки.

Якщо провести операцію згортання (wraparound) плоскої матриці, з'єднавши інформаційними трактами однойменні вузли лівого і правого стовпчиків або однойменні вузли верхньої та нижньої рядків плоскою матриці, так щоб стовпці (рядки) утворювали кільце, то з плоскої конструкції виходить топологію типу циліндра. У топології циліндра кожен ряд (або стовпець) матриці являє собою кільце. Якщо одночасно провести згортання плоскою матриці в обох напрямках, виходить тороїдальна топологія мережі. Двомірний тор на базі решітки n × n володіє наступними параметрами: D = 2min [n / 2]; d = 4; I = 2N; B = 2n.

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

Топологія «гіперкуб» досить широко поширена на практиці при об'єднанні паралельних процесорів. Лінія, що з'єднує два вузли визначає одновимірний гіперкуб. Квадрат, утворений чотирма вузлами - двовимірний гіперкуб, а куб з восьми вузлів - тривимірний гіперкуб і т.д. З цього ряду слід алгоритм отримання n-мірного гіперкуба: почати з (n-1) -мірного гіперкуба, зробити його ідентичну копію, а потім додати зв'язку між кожним вузлом вихідного гіперкуба і однойменним вузлом копії.

40. Динамічні топології КС. Блокуючі і неблокуючі мережі. Шинна топологія.

Блокуюча топологія

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

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

До блокуючим відносяться мережі «Баньяна», «Омега», n-куб та ін.

Неблокуюча топологія

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

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

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

41. Динамічні топології КС: топологія перехресної комутації (кросбар).

Топологія полносвязной комутаційної матриці на основі матричного комутатора являє собою класичний приклад одноступінчастої динамічної мережі. Зміст, вкладений в поняття «повнозв'язна матриця», полягає в тому, що будь вхідний порт може бути пов'язаний з будь-яким вихідним портом. Не зовсім офіційний термін «кроссбар» бере свій початок з найперших телефонних комутаторів, де за допомогою штекерів вхідні лінії замикалися на вихідні, утворюючи з'єднання. Комутатор типу кроссбар являє собою матрицю, рядки якої утворені провідниками, пов'язаними з входами, а стовпці - з виходами. На перетині ліній і стовпців матриці знаходяться керовані перемикачі, які можуть або замикати з'єднання рядка на стовпець, або, навпаки, розмикати його. Для управління перемикачами, що знаходяться на перетині рядків і стовпців такий комутаційної матриці, кроссбар повинен мати контролер, який управляє станом перемикачів на основі аналізу інформації про адресу призначення. Кроссбар n × l здатний з'єднати n вхідних і l вихідних термінальних вузлів (процесорів, банків пам'яті і т. П.), Причому так, що обмін інформацією одночасно можуть вести min (n, l) пар термінальних вузлів, і конфлікти при цьому не виникають . Нове з'єднання може бути встановлене в будь-який момент за умови, що вхідний і вихідний порти вільні. Головне достоїнство топології полягає тому, що мережа виходить неблокірующіх і забезпечує меншу затримку в передачі повідомлень в порівнянні з іншими топологіями, оскільки будь-який шлях містить тільки один ключ. Проте через значного числа ключів в кроссбаре (n × l) використання такої топології у великих мережах стає непрактичним, хоча це досить хороший вибір для малих мереж. Кроссбари можуть використовуватися в комутаторах, орієнтованих як на комутацію пакетів, так і на комутацію сполук. Вони придатні для застосування в синхронних і асинхронних мережах. Мережі кроссбар традиційно використовуються в невеликих ВС з пам'яттю, що, де всі процесори можуть одночасно звертатися до банків пам'яті за умови, що кожен процесор працює зі своїм банком пам'яті. Коли два або більше процесорів змагаються за один і той же банк пам'яті, спрацьовує схема арбітражу, роздільна доступ до банку лише одному з процесорів, у той час як інші процесори змушені очікувати. В цілому ж схема арбітражу в кроссбаре може бути менш складною, ніж у випадку шини, оскільки конфлікти в кроссбаре є скоріше винятком, ніж правилом. При n = l кроссбар називають повним. Топологія використовується для організації з'єднань в деяких серійно випускаються обчислювальних системах, наприклад в обчислювальній системі Earth Simulator фірми NEC використовується кроссбар 639 × 639.

42. Комутуючі елементи мереж з динамічною топологією. Топологія “баньян”.

Баньян-мережі (BanyanNetwork) - сімейство багатоступеневих динамічних мереж (МДС), в яких між будь-яким входом і будь-яким виходом можливий тільки єдиний шлях. Подклассом мереж «Баньян» є мережі «Омега» і «Дельта». Серед блокуючих багатоступеневих мереж найбільшого поширення набули баньяноподобние мережі. Назву свою мережі отримали через те, що їх конфігурація нагадує повітряні корені дерева баньян (індійської смоковниці). Мережа n × n (n = 2m) складається з mn / 2 базових комутуючих елементів. Мережа «Баньян» 4 × 4 по топології збігається з мережею «Батерфляй». Дана мережа відноситься до мереж з самомаршрутізаціей (self- routing), оскільки адреса пункту призначення не тільки визначає маршрут повідомлення до потрібного вузла, але і використовується для управління проходженням повідомлення по цьому маршруту. Рухаючись пакет в своєму заголовку містить трьохрозрядний двійковий номер вузла призначення. Топологія «Баньян» вельми популярна через те, що комутація забезпечується простими коммутирующими елементами, що працюють з однаковою швидкістю, повідомлення передаються паралельно. Крім того, великі мережі можуть бути побудовані із стандартних модулів меншого розміру.

43.Динамічні топології КС: “омега”, “дельта”.

.Дельта-мережі являють собою підклас баньян-мереж і мають властивість самомаршрутізаціі. Існує кілька типів дельта-мереж, що розрізняються тим, які функції маршрутизації використані між ступенями мережі та на її вході. Серед баньян-мереж найбільшого поширення набули так звані мережі «Дельта», запропоновані Пателом в 1981 році. Дельта-мережу на n входів і n виходів має log2n ступенів комутації, кожна з яких складається з n / 2 базових комутуючих елементів (БКЕ). Різні варіанти мереж класу «Дельта» («Омега», «базова лінія», «батерфляй», «непрямий» n-куб та ін.) Розрізняються тим, які функції маршрутизації використані між ступенями мережі та на її вході. По відношенню до довільного трафіку всі мережі забезпечують еквівалентну продуктивність. Істотним достоїнством цих мереж, що визначив їх популярність, є властивість самомаршрутізаціі. Щоб доставити повідомлення до вузла-одержувача, використовується адреса цього вузла, що міститься в заголовку переданого пакета. Ця адреса не тільки визначає маршрут повідомлення до потрібного вузла, але і використовується для управління проходженням повідомлення по цьому маршруту. Число бітів в двійковому поданні адреси дорівнює числу ступенів мережі, причому кожен біт відповідає певному щаблі: старший біт - нульовий (лівої) ступені, молодший біт - останньої (правої) ступені. Кожен БКЕ, куди потрапляє пакет, переглядає один біт адреси (відповідний ступені мережі, де цей БКЕ розташований), і залежно від його значення направляє повідомлення на верхній або нижній вихід. Якщо значення біта дорівнює нулю, то повідомлення пропускається через верхній вихід БКЕ, а при одиничному значенні - через нижній.Мережа з топологією «Омега» є різновидом дельта-мереж і являє собою багаторівневу структуру, де суміжні рівні пов'язані між собою відповідно до функції досконалого тасування.Мережа n × n, де n = 2m, складається з m рівнів базових комутуючих елементів (БКЕ), при загальному числі БКЕ - mn / 2. Кількість з'єднань, що забезпечуються мережею «Омега», так само nn / 2, що набагато менше, ніж n !, тобто топологія «Омега» є блокуючої. Якщо в повідомленні присутні адреси джерела і одержувача повідомлень, мережа може функціонувати в режимі самомаршрутізаціі.

44. Динамічні топології КС: “Клоша”, “базова лінія”.

Клоз показав, що багатоступенева мережу на основі елементів типу кроссбар, що містить не менше трьох ступенів, може володіти характеристиками неблокірующіх мережі. Мережа Клоза з трьома ступенями, показана на малюнку (див. Додатково файл .pdf), містить r1 кроссбаров у вхідний щаблі, m кроссбаров в проміжній ступені і r2 кроссбаров у вихідний щаблі. У кожного комутатора вхідний ступені є n1, входів і m виходів - по одному виходу на кожен кроссбар проміжної щаблі. Комутатори проміжної ступені мають r1 входів по числу кроссбаров вхідний щаблі й r2 виходів, що відповідає кількості перемикачів у вихідний щаблі cети. Вихідна щабель мережі будується з кроссбаров з m входами і n2 виходами. Звідси числа n1, n2, r1, r2 і m повністю визначають мережу. Число входів мережі N = r1n1, а виходів - M = r2n2. Зв'язки всередині складеного комутатора організовані за такими правилами:

▪ k-й вихід i-го вхідного комутатора з'єднаний з i-м входом k-го проміжного комутатора;

▪ k-й вхід j-го вихідного комутатора з'єднаний з j-м виходом k-го проміжного комутатора.

Кожен модуль першої і третьої ступенів мережі з'єднаний з кожним модулем другий її щаблі. Хоча в розглянутій топології забезпечується шлях від будь-якого входу до будь-якого виходу, відповідь на питання, чи буде мережа неблокірующіх, залежить від числа проміжних ланок. Клоз довів, що подібна мережа є неблокірующіх, якщо кількість кроссбаров в проміжній ступені m задовольняє умові: m ≥ n1 + n2-1. Якщо n 1 = n2 = n, то матричні перемикачі в проміжній ступені являють собою «повний кроссбар» і критерій Неблокована набуває вигляду: m ≥ 2n-1. За умови m ≥ n2 мережу клош можна віднести до неблокуючим мереж з реконфигурацией. У всіх інших співвідношеннях між m, n1 і n2 дана топологія стає блокуючої.

«Базова лінія» одна з варіантів мереж класу «Дельта», які різняться тим, які функції маршрутизації використані між ступенями мережі та на її вході. По відношенню до довільного трафіку всі мережі забезпечують еквівалентну продуктивність.Функція маршрутизації типу базисної лінії визначається співвідношенням: Li (xn-1, ..., xi + 1xixi-1, ..., x1x0) = xn-1, ..., xi + 1x0xi, ..., x1, 0 ≤ i ≤ n-1 і зводиться до циклічного зсуву i + 1 молодших цифр адреси вузла-джерела на одну позицію вправо. Передбачається, що розмір мережі (кількість вузлів) дорівнює N, розрядність адреси - n, де n = log2N і біти адреси позначені як xi.

45Загальні принципи організації пам’яті в комп’ютерних системах. Особливості організації пам’яті із чергуванням адрес.

Загальні принципи організації пам’яті в комп’ютерних системах. Особливості організації пам’яті із чергуванням адрес.

Загальні принципи організації пам’яті в комп’ютерних системах. Особливості організації пам’яті із чергуванням адрес.

В комп’ютерних системах організація пам’яті поділяється на:

Когерентність кеш-пам'яті

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

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

Колективна кеш-пам'ять

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

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

Розподілена пам'ять

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

Слабо пов'язані системи також зустрічаються як у класі SIMD, так і в класі MIMD, і інший раз, щоб підкреслити дану особливість, вводять підкласи DM-SIMD (DistributedMemory SIMD) і DM-MIMD (DistributedMemory MIMD).

Колективна пам'ять

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

Системи із загальною пам'яттю називають сильно зв'язаними (closelycoupledsystems). Подібна побудова обчислювальних систем має місце як в класі SIMD, так і в масі MIMD. Іноді, щоб підкреслити цю обставину, вводять спеціальні підкласи, використовуючи для їх позначення абревіатури SM-SIMD (SharedMemory SIMD) і SM-MIMD (SharedMemory MIMD).

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

Класифікація моделей архітектури пам’яті обчислювальних комп’ютерних систем

Головними видами взаємодій в паралельних системах є: 1) спільна пам′ять; 2) обмін повідомленнями; 3) віддалений виклик процедур (RPC), що включає передачу параметрів. Спільна пам′ять є простим, близьким за парадигмою до послідовного програмування засобом, використання якого проте обмежене за розміром і масштабованістю. Тому застосовується тільки в тіснозв′язаних системах, а саме, векторно-конвеєрних та симетричної обробки. Головними проблемами для паралельних систем пам′яті є проблеми когерентності (цілісності) і несуперечливості (coherence&consistency), що виникають через можливості паралельного доступу та реплікації даних. Несуперечливість − це когерентність (цілісність) у синхронізаційній точці. В сучасних архітектурах спільними можуть вважатись не просто дані, аоб′єкти. Файл − об′єкт операційної системи для довго-тривалогозберіганняданих (persistentobject), а файлова система, як компонента ОС, відповідає за іменування, створення, видалення, модифікацію і захист файлів.

47 Моделі архітектур із загальною пам’яттю: UMA, NUMA. Переваги і недоліки.

Системи з однорідним доступом до пам'яті UMA - обчислювальні системи з фізично пам'яттю, де всі процесори мають рівні можливості з доступу до єдиного адресного простору і доступ будь-якого процесора до пам'яті проводиться одноманітно і займає однаковий час.Єдина пам'ять може бути побудована як одноблокової або за модульним принципом, але зазвичай практикується другий варіант.Архітектура UMA найбільш поширена архітектура пам'яті паралельних ВС з пам'яттю, що.Технічно UMА-системи припускають наявність вузла, що з'єднує кожен з n процесорів з кожним з m модулів пам'яті. Найпростіший шлях побудови таких ВС - об'єднання декількох процесорів з єдиною пам'яттю допомогою загальної шини. У цьому випадку, однак, в кожен момент часу обмін по шині може вести тільки один з процесорів, тобто процесори повинні змагатися за доступ до шини. А оскільки, фактично процесор зазвичай набагато швидше пам'яті, дана схема широкого застосування не знаходить. Ситуація може бути поліпшена за наявності у кожного процесора локальної кеш-пам'яті .При альтернативному способі побудови багатопроцесорної ВС, із загальною пам'яттю на основі UMA шина замінюється комутатором, маршрутизуючого запити процесора до одного з декількох банків пам'яті. Незважаючи на те що є декілька банків пам'яті, всі вони входять в єдиний адресний простір. Перевага такого підходу в тому, що комутатор в змозі паралельно обслуговувати декілька запитів. Кожен процесор може бути з'єднаний зі своїм модулем пам'яті і мати доступ до нього на максимально допустимої швидкості. Суперництво між процесорами може виникнути при спробі одночасного доступу до одного і того ж банку пам'яті

48Моделі архітектур із загальною пам’яттю: COMA, CC-NUMA, NCC-NUMA. Переваги і недоліки. Переваги:простота програмування;спільний адресний простір;простота роботи;Недоліки:невелика кількість процесорів;дуже велика вартість;Щоб збільшити кількість процесорів, але при цьому залишити єдиний адресний простір, пропонується декілька архітектур. Найпопулярніша з них - СС VNUMA.

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

Недоліки:

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

зазвичай призводить до значних часових затримок,

— додаткові обмеження на тип розроблюваних паралельних алгоритмів і програм (низька

інтенсивність потоків передачі даних).

49. Моделі архітектур з розподіленою пам’яттю. Переваги і недоліки.

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

50-51. Мультипроцесорна когерентність кеш-пам’яті та програмні методи її вирішення. Апаратні способи вирішення проблеми когерентності кеш-пам’яті в комп’ютерних системах. Переваги і недоліки.

На рис. 1 як приклад показано стан двопроцесорної системи зі спільною пам'яттю і кешами першого рівня для кожного процесора до і після зміни поділюваної змінної. При зміні значення змінної Х процесором CPU2, значення її або відразу записується тільки в кеш процесора СPU2, а в загальну пам'ять при витісненні з кеша Cache2 (така стратегія називається зворотним записом), або відразу ж і в кеш процесора СPU2, і в загальну пам'ять (така стратегія називається наскрізним записом). В обох випадках значення поділюваної змінної в кеші процесора СPU1 (Cache1) виявляється неправильним, що і веде до неузгодженості вмісту кешів.

Рисунок 1 – Проблема когерентності кеш-пам'яті

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

Існує кілька способів вирішення проблеми когерентності на апаратному рівні :

· відмова від кешування: принципово вирішує проблему, але сильно знижує продуктивність системи за рахунок значної різниці між швидкістю роботи процесорів та швидкістю доступу до пам'яті;

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

Під протоколом когерентності кеш-пам'яті розуміють будь-який апаратний механізм подолання проблеми когерентності. Існує декілька класів протоколів когерентності:

· протоколи на основі довідника (directory based). Інформація про стан блоку фізичної пам'яті міститься тільки в одному місці – довіднику (фізично довідник може бути розподілений по вузлах системи);

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

53.Використання протоколів на основі довідника для забезпечення когерентності кеш-пам’яті в комп’ютерних системах. Переваги і недоліки.

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

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

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

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

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

З узгодженням стану пам'яті ми можемо гарантувати когерентність шляхом забезпечення двох властивостей:

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