Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки
Предмет:
Комп’ютерні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний технічний університет України «Київський політехнічний інститут»
Методичні вказівки
до виконання лабораторних робіт з курсу
ПРОЕКТУВАННЯ КОМП’ЮТЕРНИХ СИСТЕМ
для студентів спеціальності 8.091501
“Комп`ютерні системи та мережі”
денної та заочної форм навчання
Київ 2012
ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
Сучасні обчислювальні системи являють собою високопродуктивні, відмовостійкі засоби обчислювальної техніки. У зв’язку з безперервним розширенням сфери застосування обчислювальних систем і необхідністю вирішення все більш складних задач у промисловості постійно зростають вимоги до їх продуктивності та надійності.
Для закріплення практичних навичок, отриманих при вивченні курсів “Проектування комп’ютерних систем” та “Дослідження та проектування комп’ютерних систем”, передбачено виконання лабораторних робіт. Лабораторні роботи супроводжуються складанням звіту і виконуються в лабораторії кафедри обчислювальної техніки.
Перш ніж розпочати виконання лабораторної роботи, необхідно ознайомитись з теоретичними відомостями. Звіт по лабораторній роботі повинен бути оформлений на окремих аркушах, містити титульний аркуш, на якому має бути вказана тема лабораторної роботи, назва дисципліни, факультет, група, прізвище, ім’я, по батькові студента, варіант лабораторної роботи, мета, загальні теоретичні відомості, хід виконання роботи, схеми та рисунки, висновки.
Лабораторні роботи 1-5
ВИЗНАЧЕННЯ ТОПОЛОГІЧНИХ ХАРАКТЕРИСТИК ДЛЯ П’ЯТИ МАСШТАБОВАНИХ КЛАСТЕРНИХ МРР СИСТЕМ
Мета робіт: вивчення властивостей різних масштабованих МРР систем на базі їх топологічних характеристик.
Загальні теоретичні відомості
MPP системи або системи з масовим паралелізмом – це багатопроцесорні компютерні системи (КС) з локальною пам’яттю. Їх основна перевага – необмежена масштабованість (можливість нарощування кількості процесорів у системі без зміни їх властивостей). У звязку з цим МРР системи можуть складатись із сотень, тисяч і навіть десятків тисч процесорів. Так, сучасні найбільш продуктивні системи такі, як Roadrunner включають більше 192 тисяч процесорів, а Blue Jene/L - біля 213 тисяч процесорів.
Найбільш важливим аспектом МРР систем є те, як взаємодіють між собою окремі процесори. Конфігурація системи міжпроцесорного зв’язку істотно впливає на порядок підключення ліній зв’язку, що з’єднують окремі процесори. Організація внутрішніх комунікацій КС називається топологією.
Залежно від того, чи залишається конфігурація взаємозв’язків незмінною (доки виконується відповідне завдання), розрізняють КС зі статичною та динамічною топологіями. В статичних КС структура взаємозв’язків фіксована. В КС із динамічною топологією в процесі обчислень конфігурація взаємозв’язків за допомогою програмних засобів може бути оперативно змінена.
До статичних топологій відносять такі, де між двома вузлами можливий лише один чи декілька фіксованих шляхів, тобто немає комутуючих пристроїв. З можливих критеріїв класифікації статичних КС обирають їх розмірність. З цих позицій розрізняютьодновимірні топології (лінійний масив);
двовимірні топології (кільце, зірка, дерево, решітка);
багатовимірні топології (повнозв’язана топологія);
гіперкубічну топологію.
У простій лінійній топології вузли системи утворюють одновимірний масив та з’єднані у ланцюг (рис.1).
Рис. 1. Лінійна топологія КС
У лінійній топології час передавання повідомлення залежить від відстані між вузлами, а відмова одного з них може призвести до неможливості передавання повідомлення. З цього приводу в лінійних КС використовують відмовостійкі вузли, які при відмові ізолюють себе від мережі, дозволяючи повідомленню обминути несправний вузол.
Рис. 2. Кільцева топологія КС
Стандартна кільцева топологія (рис.2) являє собою лінійний ланцюг, кінці якого з’єднані між собою. Недолік: додавання чи вилучення вузла потребує демонтажу мережі.
Зіркоподібна організація вузлів (рис. 3) рідко використовується для об’єднання процесорів багатопроцесорної КС, але добре працює, коли потік інформації йде від декількох вторинних вузлів, з’єднаних з одним первинним вузлом, наприклад при підключенні терміналів. Загальна пропускна здатність мережі звичайно обмежується швидкодією концентратора. Основна перевага зіркоподібної схеми у тому, що конструктивне виконання вузлів на кінцях cbcntvb може бути дуже простим.
Рис. 3. Зіркоподібна топологія КС
У деревоподібній топології (рис.4) система будується за схемою двійкового дерева, де кожний вузол більш високого рівня зв’язаний з двома вузлами наступного за порядком більш низького рівня. Вузол, що знаходиться на більш високому рівні, називають батьківським, а два підключених до нього нижчерозташованих вузла – дочірніми. В свою чергу, кожний дочірній вузол виступає як батьківський для двох вузлів наступного більш низького рівня. Кожний вузол зв’язаний лише з двома дочірніми та одним батьківським.
Рис. 4. Деревоподібна топологія КС
При великих об’ємах передачі даних між несуміжними вузлами деревоподібна топологія виявляється недостатньо ефективною, оскільки повідомлення повинні проходити через один чи декілька проміжних процесорів. На більш високих рівнях системи ймовірність затору через недостатньо високу пропускну здатність ліній зв’язку вище.
КС з решітчастою топологією (рис.5) орієнтовані на задачі, пов’язані з обробкою масивів. Їх конфігурація визначається видом та розмірністю масиву.
Рис. 5. Решітчаста топологія КС
У системах, де кожний процесор з’єднаний з декількома сусідніми процесорами, можна досягти компромісу між складністю системи міжпроцесорного зв’язку, її пропускною здатністю й затримкою обмінів даними. В одновимірних решітках процесорів, що часто називають лінійним масивом, кожний процесор, крім крайніх, з’єднаний з двома сусідніми. При цьому дані, що пересилаються із процесора-джерела в процесор-приймач, послідовно проходять транзитні процесори, розташовані між джерелом і приймачем. У двовимірній решітці кожний процесор з’єднаний з північним, південним, східним і західним сусідами. Решітки процесорів характеризуються регулярністю, локальністю і простотою маршрутизації міжпроцесорних зв’язків. У тривимірному масиві кожний із процесорів з’єднаний із шістьома сусідами. Перевагою такої системи є мінімальна кількість ліній зв’язку (з кожного процесору виходить не більше двох ліній зв’язку).
У повністюзв’язаній системі кожний процесор має пряме з’єднання з будь-яким іншим процесором.
При об’єднанні паралельних процесорів дуже популярна топологія гіперкуба. Лінія, що з’єднує два вузла (рис.6, а), визначає одновимірний гіперкуб. Квадрат, що утворений чотирма вузлами (рис.6, б) – двовимірний гіперкуб, а куб з 8 вузлів (рис. 6, в) – тривимірний гіперкуб та т.ін.
Обмін повідомленнями в гіперкубі базується на двійковому поданні номерів вузлів. Нумерація вузлів робиться так, що для будь-якої пари суміжних вузлів двійкове подання номерів цих вузлів відрізняється лише в одній позиції. Вузли 010 та 110 – сусіди, а вузли 110 та 101 такими не є.
Рис. 6. Гіперкубова топологія КС
Така архітектура дає малу кількість зв’язків між процесорами. В КС з такою архітектурою обчислювальний процес будується таким чином: кожний процесор у вузлі має власну пам’ять та відповідно володіє потужним обчислювальним ресурсом. Якщо обчислювальної потужності не вистачає, то до вирішення залучають процесори з сусідніх вузлів чи всього кубу. Якщо і цього недостатньо, то залучають процесори, які розташовані у вузлах зовнішнього гіперкубу відносно до даного.
Недоліки окремих типів систем мінімізуються при їх комбінуванні (гібридні системи міжпроцесорного зв’язку). Наприклад, конфігурацію піраміди одержують додаванням зв’язків між процесорами, що належать одному ярусу дерева, відповідно до конфігурації двовимірних решіток. Таким чином, у піраміді об’єднані переваги дерева й решітки.
Структури КС із кластерами також відносять до гібридних систем зв’язку. У межах кластера процесори з’єднані відповідно до однієї з конфігурацій зв’язків, наприклад, загальною шиною, а кілька кластерів об’єднані у КС за допомогою іншої конфігурації зв’язків, наприклад, у вигляді решітки або гіперкуба.
У динамічній топології КС з’єднання вузлів забезпечується електронними ключами, варіюючи установки яких можна змінювати топологію системи. У вузлах динамічних КС розташовуються комутуючі елементи, а пристрої, що обмінюються повідомленнями (термінали), підключаються до входів та виходів цієї мережі. Як термінали можуть виступати процесори чи процесори та модулі пам’яті. Для таких КС частіше всього використовується одно- або багатокаскадна комутація на основі матричних комутаторів.
КС з шинною архітектурою – найбільш простий та дешевий вид динамічних КС. При одношинній топології (рис. 7), усі вузли підключені до однієї шини, що сумісно використовується. В кожний момент часу обмін повідомленнями може вести лише одна пара вузлів, тобто на період передавання повідомлення шину можна розглядати як мережу, що складається з двох вузлів.
Рис. 7. Одношинна топологія КС
Більш ефективною архітектурою динамічних КС є система, в якій процесори зв’язані між собою за допомогою матричного комутатора. У цьому випадку в кожний момент часу обмін повідомленнями можуть вести n/2- пар вузлів, де n – кількість вузлів у системі. Недоліком такої архітектури є висока вартість.
Сьогодні більшість найпропродуктивніших МРР систем будується на основі кластерів. Тому лабораторні роботи присвячуються саме таким системам із статичними топологіями. Для аналізу їх потенційних можливостей з точки зору ефективності функціонуванняних використовують різні топологічні характеристики. Основними топологічними характеристиками є:
Діаметр (D). Діаметр систем – це мінімальна відстань між двома максимально віддаленими процесорами. Наприклад, діаметр для повністю зв’язної системи дорівнює 1, а для топології «зірка» дорівнює 2. Діаметр кільцевої топології дорівнює , а лінійної топології дорівнює n-1, де n – кількість процесорів у системі. Оптимальним є мінімальне значення діаметра.
Середній діаметр (). Ця характеристика визначається згідно з формулою:
(8)
де dij – мінімальна відстань між i-м та j-м процесорами. Оптимальним є
мінімальне значення середнього діаметра.
Ступінь (S). Ця характеристика визначається як максимальне число дуг (зв’язків) інцидентних вершині (процесору) у графі топології системи. Так, ступінь лінійної та кільцевої топології дорівнює 2, повністю зв’язної топології дорівнює n-1, а у деревовидної топології дорівнює 3. Оптимальним є мінімальне значення ступеню.
Вартість (C). Існує сукупність варіантіов ивзначення вартості системи. У відповідності з одним з них вартість визначається як сумарна кількість зв’язків у системі. У відповідності з другим варіантом вартість визначається згідно формули:
C= (9)
У работах можна використовувати будь-який варіант визначення вартості. Оптимальним є мінімальне значення вартості.
Топологічний трафік (T). Ця характеристика (для симетричних систем) визначається згідно формули:
T= (10)
Топологічний трафік визначає ступінь використання зв’язків у системі. Оптимальне значення T = 1, яке означає потенційне використання усіх існуючих зв’язків між процесорами. Якщо T<1, це означає, що частина фізичних зв’язків у системі при пересилці даних не будуть використані. Якщо ж T>1, при пересилці даних існуючих у системі зв’язків буде недостатньо, а значить можливі додаткові затримки часу.
Вхідні дані до виконання лабораторних робіт 1-5
Вхідними даними до виконання лабораторних робіт є п’ять масштабованих топологій МРР систем на базі кластерів (для кожної лабораторної роботи своя система). Варіанти побудови таких систем представлені у таблиці 1. Вона включає 38 варіантів кластерів, які можуть бути об’єднані в одну із таких топологій:
лінійка
кільце
зірка
двійкове дерево
решітка
тор
Варіант кожної роботи узгоджується з викладачем.
Таблиця 1
Варіанти завдань до виконання лабораторних робіт 1-5
Типи топологій:
линійка
кільце
дерево
решітка
зірка
тор
Номер кластера
Тип кластера
Типи топологій
1
2
3
4
5
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Завдання на лабораторну роботу та порядок її виконання.
Для кожної із заданих топологій:
Визначити порядок нумерації процесорів в кластерах системи при масштабуванні. Приклад. Нехай задана лінійна топологія системи, яка складається з кластерів, зображених на рис.11.
рис.11
Визначимо нумерацію процесорів при масштабуванні (рис. 12).
1 крок масштабування
2 крок масштабування
3 крок масштабування
р-й крок масштабування
рис. 12
Визначити число процесорів, які додаються на кожному кроці масштабування. Для розглянутого прикладу таке число процесорів дорівнює 3 (для деяких топологій це значення не є const і може бути визначено за аналітичною формулою).
Програмно описати зв'язки між процесорами (внутршньокластерні і міжкластерні) на кожному кроці масштабування за допомогою відповідних матриць суміжності. Розмір матриць визначається кількістю процесорів. Якщо існує зв'язок між i - м і j - м процесорами, відповідне значення матриці на перетині i - го рядка та j - го стовпця дорівнює "1", в іншому випадку дорівнює "0". Наприклад, матриця суміжності для 1 - го кроку масштабування має вигляд:
N
1
2
3
1
0
1
1
2
1
0
1
3
1
1
0
Матриця суміжності для 2 – го кроку масштабування топології, зображеної на рис. 12 має вигляд:
N
1
2
3
4
5
6
1
0
1
1
0
0
0
2
1
0
1
0
0
0
3
1
1
0
1
0
0
4
0
0
0
0
1
1
5
0
0
0
1
0
1
6
0
0
0
1
1
0
Масштабування всіх топологій виконувати до тих пір, поки кількість процесорів системи не досягне значення 100.
Для кожного кроку масштабування, використовуючи матрицю суміжності програмно обчислити основні топологічні характеристики (діаметр, середній діаметр, ступінь, вартість, топологічний трафік). Для визначення діаметру (D) можна скористатися формулою: D = max {dij}
де dij - найкоротша відстань між і-м та j-м процесорами в графі системи. Для визначення dij можна використовувати один з алгоритмів (Дейкстри, Флойда, хвильовий). Значення ступеня системи визначається як максимальна сума "1" в рядку матриці суміжності. Вартість системи визначається або за формулою (9), або як сума "1" в матриці суміжності, поділена на 2.
Для визначення (середнього діаметру) можна скористатися формулою (8).Топологічний трафік визначається за формулою (10). Наприклад, для 1 кроку масштабування топології на рис.12, характеристики мають такі значення: D = 1, = 1.0, S = 2, C = 3, T = 1. Для 2 - го кроку масштабування топології на рис.12, характеристики мають такі значення: D = 3, = 1.8, S = 3, C = 7, T = 1.2. Результати обчислення топологічних характеристик для кожної топології можуть бути представлені у вигляді такої таблиці 2:
n (кількість процесорів)
топологічні характеристики
D
S
C
T
3
1
1
2
3
1
6
3
1,8
3
7
1,2
…
…
…
…
…
…
100
Лабораторна робота 6
ПОРІВНЯЛЬНИЙ АНАЛІЗ П’ЯТИ МАСШТАБОВАНИХ КЛАСТЕРНИХ МРР СИСТЕМ НА ОСНОВІ ЇХ ТОПОЛОГІЧНИХ ХАРАКТЕРИСТИК
Мета роботи: проаналізувати ефективність роботи різних кластерних МРР систем на базі їх топологічних характеристик.
Вхідні дані до виконання лабораторної роботи 6.
Вхідними даними для виконання цієї лабораторної роботи є пять таблиць (для кожної топології МРР системи своя) з результатами визначених топологічних характеристик, отриманих в роботах 1-5.
Завдання на лабораторну роботу та порядок її виконання.
1. На підставі отриманих результатів в таблицях, побудувати 5 видів графіків (по кількості топологічних характеристик), в яких зображені криві зміни топологічних характеристик в залежності від зростання числа процесорів в системі (вісь абсцис - n, вісь ординат - одна з характеристик D,, C, S або T). Для порівняння зміни топологічних характеристик в різних системах, слід на кожному графіку зобразити 5 кривих (за кількістю заданих топологій). 2. Виконати порівняльний аналіз заданих топологій систем на підставі отриманих графіків. Для цього необхідно визначити місця перетину графіків і розділити їх на зони. Наприклад, нехай є графіки зміни D 5 топологій:
Максимальне число перетинань маємо в районі 30 і 60 процесорів. Таким чином, дослідження будемо проводити в трьох зонах: від 1 до30 процесорів, від 31 до 60 процесорів, від 61 процесора до 100 процесорів. Причому зони для досліджень по всіх топологічних характеристиках повинні бути одні й ті ж. Потім усередині кожної зони, кожна топологія може бути оцінена за п'ятибальною оцінкою. Оцінка присвоюється залежно від того, наскільки топологічна характеристика наближається до її оптимального значення. Потім отримані оцінки всередині зони дослідження кожної топології підсумовуються, і отримуємо інтегральну оцінку. Отримані результати записуємо в таблицю, приклад якої наведено нижче
N топології
Зона 1-30
D
S
C
T
∑
1
2
2
3
4
3
14
2
3
3
4
5
3
18
3
5
4
4
2
5
20
4
4
5
5
1
4
19
5
1
1
2
3
2
9
На підставі інтегральної оцінки вибираємо найкращу (з максимальною сумою) і найгіршу топології. Аналогічно виконуємо порівняльний аналіз для решти зон. Робимо загальні висновки.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора