Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Відповіді до екзаменаційних білетів
Предмет:
Комп’ютерні системи
Частина тексту файла (без зображень, графіків і формул):
Комп’ютерні системи
1 рівень
Визначити, з якою максимальною частотою будуть з’являтися на виході конвеєрного пристрою (КП) результати, якщо на вхід КП аргументи поступають без затримки ( КП створено з n ступенів; час спрацювання ступенів дорівнює, відповідно А, В, С, D i Е такта).
Якшо n=5 то перший результат зявиться за A+B+C+D+E такта а далі він буде зявлятися через кожні max(A,B,C,D,E) такта,відповідно частота зявляння резальтата буде
1/ max(A,B,C,D,E) *tтакта ,де t- тривалість одного такту.
T = max (A,B,C,D,E)*5 – період появи
F = 1/T - частота появи
Обґрунтувати, чому для асоціативного процесора може бути несуттєвим, щоб число елементів було рівне ступеню двійки, в той час, як у пам’яті з довільним доступом кількість слів обов’язково має бути ступеню двійки.
В асоціативних процесорах вибірка даних вибирається за вмістом.Тобто процесор порівнює певну маску із вмістом елементів і по найбільшому співпадінню з маскою вибирається результат.В памяті з довільним доступом вибірка даних відбувається за адресою і оскільки використовується двійкова система числення то потрібно точно представити всі елементи тобто присвоїти їм конкретні номери щоб не було такого що адреса є а елемента нема.
Визначити та пояснити, якщо дві КС відрізняються тільки версіями встановлених на них операційних систем, чи можуть на таких КС відрізнятися час роботи одної і тої самої програми.
Час роботи програми на різних версіях операційної системи на одинаковій КС з першого погляду не має відрізнятися, тому що одинаковий час виконання команд і одинакові набори команд. Але насправді він може відрізнятися. По-перше ця програма може мати набір системних викликів, час виконання яких на різних системах може бути різним. Крім цього операційна система може мати таку важливу функцію, як адресну трансляцію програми перед її виконанням. Адресна трансляція на різних версіях ОС може відрізнятися, а при наявності банків памяті які працюють паралельно, це може призвести до суттєвої різниці часу виконання програми
Визначити, за яке мінімально число тактів може бути виконано m операцій (конвеєрний пристрій створено із n ступенів і час спрацювання ступенів дорівнює, відповідно, А, В, С, D i Е такта).
Якшо n=5 то перший результат з’явиться за A+B+C+D+E такта а далі він буде з’являтися через кожні max(A,B,C,D,E) такта, відповідно m операцій буде виконано через A+B+C+D+E +( m-1)* max(A,B,C,D,E)
Tk = (n+m-1). Max(A,B,C,D,E)
Визначити, за який мінімальний час комп’ютер обчислить m незалежних операцій, якщо в комп’ютері є 7 паралельно працюючих пристроїв, кожний з яких може виконувати операцію за 7 одиниць часу.
Відповідь За 7 од.часу
Визначити основні умови, виконання яких є необхідними для того, щоб вважати гілки програми незалежними.
Паралелізм незалежних гілок. Суть полягає в тому, що при розв’язанні великої задачі можуть бути виділені окремі незалежні частини – гілки проги, які при наявності декількох пристроїв обробки можуть виконуватись паралельно та незалежно один від одного. Двома незалежними гілками програми будемо вважати такі частини задачі, при виконанні яких виконуються наступні умови:
Для обох гілок програми не мусить робитися запис в одну і ту саму комірку памяті (відсутність зв’язку із використанням одних і тих самих полів ОП);
Умови використання однієї гілки не залежить від результату або ознак, отриманих при виконанні іншої гілки (незалежність за керуванням);
Ні одна із вхідних для гілки величин не є вихідною величиною іншої гілки (відсутність функціональних зв’язків);
Обидві гілки мусять виконуватися за різними блоками програми (програмна незалежність).
Визначити основні види регістрів, які входять у архітектуру асоціативного процесора.
Цей ОКМД процесор побудований на базі асоціативного пристрою пам’яті. Пристрій пам’яті створений з асоціативних комірок пам’яті. Дані можуть бути співставленні по деяким критеріям (= ,<=,>=) з інформацією яка зберігається в пам’яті. Для цього використовуються наступні дії:
запис даних в регістр даних
виділення розрядів, які підлягають порівнянню з використанням регістру маски.
запис бітового набору, який описує підмножину даних у файлі, що відшукуються в регістр вибірки слів.
Результатом порівняння буде бітовий однорозр. набір у регістрі результатів пошуку, який забезпечений покажчиком (вказівником) на перше слово, яке відгукнулося. Цей покажчик називається пристрій дозволу множинних відліків. Він вказує на саме „верхнє слово” яке задовольняє критерій пошуку. Тобто на самий верхній біт регістру результату пошуку.
Визначити основні види затримок, які виникають у суперкомп’ютерах типу Hewlett-Packard Superdome при звертанні процесорів до пам’яті .
Одною з важливих проблем КС з архітектурою ссNUMA є різниця в часі при звертанні проца до пам’яті. В ідеалі було би бажано , щоб тої різниці не було. Ця сис. SMP погано масштабується. В комп’ютері HP”SD”можливі три види затримок, при звертанні процесора до пам’яті, що є платою за високу маштабованість системи:
Процесор і пам’ять розташовані в одній комірці(затримка min)
Процесор і пам’ять розташовані в різних комірках, але ці комірки під’єднані до одного комутатора.
Процесор і пам’ять є в різних комірках, але обидві комірки під’єднані до різних комутаторів(в цьому випадку інфа проходить через 2 комутатора).
Величина затримки залежить від взаєм. розповсюдження проц. і пам., а також від характеру обчисл. Навантаження. Затримка може мінятися залежно від числа додатків одночасно.
Затримка у залежності від числа проців та завантаження(коефіцієнт збільшення затримки)
Число процесорів
Однопотокові програми нс.
Багатопотокові нс.
4
174
235
8
208
266
16
228
296
32
261
336
64
275
360
Визначити основні ознаки КС типу SMP (Symmetric Multi Processors).
Конфігурація SMP сервер має 16-32-64 процесори
В SMP все, крім декількох проців, в одному примірнику:1 пам.,1 ОС,1 підсистема вв-вив. Симетрична значить. Слово симетричний в SMP означає, що кожен процесор може робити все те, що й інші.
Наведіть найбільш продуктивні багатопроцесорні суперкомп’ютери згідно з версією останнього TOP500.
Earth Simulation NEC 2002p. 35,86 TFlops 350 млн.$ Японія(Системи передбачення землетрусів).
Columbia NASA та SGI 51,87 Кластер з 20,512 проц. систем; 10240 проців
SX-8 - векторний суперкомп 65 TFlops
Blue GeneIL IBM 36,01- 8 шаф-16250 проців- ¼ запланованої сис.(70,72 ТФлопс)-Нац. Лівермоловська лабораторія
ІВМ- одна з перших ставить сис. на потік.
Збираються зробити 64 стойки і 130 проців 70,72(*4)
ASCI Purle –сис. з використанням практично стандартних ІВМ процесорів. Server p655
“Peramma”
Літом планується встановити в Лів. лабор. Споживає 4,8МВт.
Міністерство енергетики США має угоду з фірмою ІВМ про постановку 2-ох суперкомпів. Продуктивність 800 ТФлопс. Не плутати з продуктивністю в real-time.
Латентність- час поч. затримки при посиланні повідомлень.
Пропускна здатність мережі визначається швидкістю передачі інфи по сис.звязку.
Поясніть причини виникнення проблеми КЕШ-пам’яті у багатопроцесорних КС.
Ця архітектура є досить розповсюдженою і на її шляху досить не очікувано з’явилась проблема з кеш-пам’яттю. Кеш-пам’ять, яка дозволяє значно прискорити роботу окремих процесорів, для багато процесорних систем, створила складності. В перших комп’ютерах NUMA не було кеш-пам’яті і не було подібної проблеми. Але в сучасних комп’ютерах з’явилась кеш-пам’ять.
Нехай процесор Р1 зберігає значення х в комірці Q, а далі процесор Р2 хоче прочитати зміст тої самої комірки Q. Що отримає проц Р2?Бажано, щоб він отримав х, але як він отримає, якщо х знаходиться в кеші Р1 процесора.
Ця проблема має назву – “проблема узгодження змісту кеш-пам’яті” (Cache coherence problem).Ця проблема актуальна і для сучасних SMP-компів(Symmetric Multi Processors).
В SMP все, крім декількох проців, в одному примірнику:1 пам.,1 ОС,1 підсистема вв-вив.
CcNUMA
Для вирішення даної проблеми була розроблена спеціальна модифікація NUMA архітектура сс NUMA. На основі цієї архітектури випускаються багато реальних систем, які поширюються можливості традиційних комп’ютерів загальної пам’яті. Причому, якщо конфігурація SMP сервер має 8-16-32-64 процесори, то сс NUMA дає можливість об’єднати 8-16-32-64-256 та більше процесорів.
В цих системах крім декількох процесорів в одному примірнику: 1 пам’ять, 1 ОС, 1 система інтерфейсу вводу виводу. Слово симетричний означає, що кожен процесор може робити все те, що може інша.
В ссNUMA арх. пам’ять всього комп’ютера фізично розподілена, що значно підвищує потенціал його масштабованості, але пам’ять логічно залишиться загальною. Це дає можливість використання всіх технологій та методів програмування SMP. Зміст кеш-пам’яті на рівні процесорів узгоджується з ОП.
Значно збільшується число процесорів у порівнянні з класом архітектури. В цій архітектурі час звертання до пам’яті залежить від того чи є це звертання до локальної або віддаленої пам’яті.
Процес написання програми залишається тим самим і фізично розподіл пам’яті у програмі не бачить.
Поясніть доцільність застосування асоціативних КС та асоціативної обробки.
Концепція асоціативності не є нова. Асоціація може розглядатися як встановлення відповідності між об’єктами.
Найбільш загальні типи архітектури (організації асоціативних процесів).
Рг даних
Рг маски
Слово 1
Слово 2
Слово 3
Слово 4
Слово 5
Слово 6
Слово 7
Слово 8
Поле
РгВ РгВ АЗ
На малюнку є зображені такі елементи архітектури:
Регістри:
Регістри даних
Регістри маски
РгР - Регістри результату пошуку
РгВ - Регістри вибірки слів
Також є пристрої:
Дозволу множинних збігів (ДМЗ)
Масиво-асоціативної пам’яті
АЗ - Апаратні засоби обробки слів
Важливо виділити відсутність будь – яких пристроїв перетворення адрес. По суті, адрес взагалі немає.
Адресування даних у процесорі здійснюється за місцем або за будь – яким параметром пов’язаним із їх місцем.
Кожне слово пам’яті розбите на розрядні групи змінної довжини, яке має назву поля. Поля не обов’язково мусять бути утворені з послідовно розміщених розрядів. Регістри даних і маски містять ту саму кількість розрядів, яку мають слова пам’яті. Регістри результату пошуку та вибірки слів містять по одному розряду на кожне слово пам’яті.
Бітовий зріз уявляє собою бітовий вектор, який утворений із і-их розрядів з усіх вибраних слів і який не залежить від інших слів.
Приклади оп-цій, які здійсн. АП:
1.маскований пошук на рівність
2.різні види послідовно- порозрядних оп-цій пошуку на нерівність
3.послідовно- порозрядні арифм. оп-ції над полями
4.посл.-порозр. пошук максимума/мінімума, який дозвол. знаходити max(min)слово , що запис в пам’яті.
Тег - це група службових розрядів, які застосовуються для ідентифікації типу даних. В рег. даних записано слово, яке необхідно порівняти із вмістом пам’яті. Регістр маски вказує на ті розряди шуканих слів, які повинні бути включені в операції. У рег. результату записаний результат пошуку. Регістр вибирання слів вибирає слово, яке приймає участь у пошуку.В процесі виконання операції асоціативного проц., а саме пошуку на рівність буде виконано порівняння регістру пошуку із вмістом усіх полів, що вибрано.
У багатьох системах за операцією пошуку повинна слідувати операція зчитування або інша операція пошуку. Слова, що ідентифікуються, зчитуються послідовно. Вміст регістра результатів може бути переписаний у регістр вибірки слів, для того, щоб результат можна було використати в якості нового вмісту регістру вибірки слів. Може бути здійснена серія результатів пошуку, результат яких логічно об’єднаний, тобто дані які знаходяться в регістрі результатів пошуку логічно перемножуються із вмістом регістру вибірки слів, що формують новий вміст останнього.
Число вбудованих логічних функцій може бути великим. У системі АП присутній пристрій дозволу множинних збігів, або спів падінь. На мал. АП він показаний стрілкою.
Якщо результат пошуку отримали відклики від декількох слів, то ДМЗ вказує на 1-ий відлік, або на інакше на саме верхнє слово, для якого виконується умова пошуку.
Для АП розробляються багато режимні пристрої пам’яті.
В деяких системах може бути введена більша к-сть регістрів(КС Staran- система керування польотами в об’ємі).Маємо 3 регістри, які вказують напрямок пошуку слів,
ф-ції регістрів аналог. ф-ям вибирання слів і пошуку. Пам. об’ємна , а не плоска. Для асоц-их систем потрібні спеціальні види пам’яті .
У своїй праці „О пам’яти и воспоминаниє” Арістотель визначив 3 види асоціацій:
За схожістю
За контрастом
За близькістю
Доповнення:
Асоціації ідеї
Асоціації по причині та наслідку
Наведіть особливості побудови та параметри суперкомп’ютера Hewlett-Packard Superdome.
На базі Київстар стоїть суперкомп’ютер HP Superdome 2000р.
В стандартній конфігурації об’єднуються від двох до 64-х процесорів з можливим подальшим розширенням системи. Всі процесори мають доступ до загальної пам’яті орг. Відповідно в системі це означає що:
Всі процесори можуть працювати в єдиному адресному просторі адресуючи будь-який байт в пам’яті за допомогою звичайних операцій читання \ запису.
Доступ до локальної пам’яті буде іти трохи швидше ніж доступ до віддаленої пам’яті.
Проблеми з можливою невідповідністю даних викликаються на рівні..
Максимальні конфігурації може мати 256 Гбайт ОП.
Найближчі плани HP нарощувати оперативну пам’ять до одного Тбайт.
Основною архітектурою HP SUPERDOME являє собою обчислювальні комірки (сells), пов’язана ієрархічно системою перемикачів. Кожна комірка є симетричним мультипроцесором, який реалізований на одній платі (мікропроцесорів до 4-х штук, ОП до 16Гбайт, контролер комірки, перетворення живлення, система вводу/виводу).
Архітектура комп’ютера спроектована так що в неї може використовуватись декілька типів мікропроцесорів. Система повністю підготовлена для використання процесорів наступного покоління. При заміні існуючих процесорів Itanium гарантується двійкова система додатків на системному рівні.
Центральне місце в архітектурі комірки HPSuperDome це контролер комірки. Контролер комірки це дуже складний пристрій, який має 24млн транзисторів. Для кожного процесора комірки є свій власний порт контролера. Обмінним даним є 2 Гб/сек Пам’ять комірки має ємність від 2 до 16 Гбайт. Конструктивно вона поділена на два банки, кожен з яких має свій порт в контролері комірки. З’єднання контролера комірки з контролером пристрою вводу/виводу встановлюється оптимально. Один порт контролера комірки завжди пов’язаний з зовнішнім комутатором. Зовнішній комутатор потрібний для обміну даних з іншими процесорами. Швидкість роботи порта 8Гбайт\с.
Контролер комірки виконує інтерфейс функції між процесором і пам’яттю, який крім цього відповідає і за когерентність кеш-пам’яті.
Комірка – це базовий 4-х процесорний блок. В 64 процесорах конфігурації SuperDome має дві стойки, в кожні з яких 32 процесора. Кожна стойка має по два 8-ми портових комутатора. Всі порти комутаторів процесора мають швидкість 8Гбайт\с. До кожного комутатора підключають 4 комірки: 3-порти комутатора задіяні для зв’язку з іншими комутаційними системами( 1-ший для комутаторів тої самій стойки, і 2- для інших). Останній 8 порт зарезервований для зв’язку з іншими системами суперкомп’ютера, що дозволяє.
Одною з важливих проблем КС з архітектурою сс NUMA є різниця в часі при звертанні проца до пам’яті. В ідеалі було би бажано , щоб тої різниці не було. Ця сис. SMP погано масштабується. В комп’ютері HP”SD”можливі три види затримок, при звертанні процесора до пам’яті, що є платою за високу маштабованість системи:
Процесор і пам’ять розташовані в одній комірці(затримка min)
Процесор і пам’ять розташовані в різних комірках, але ці комірки під’єднані до одного комутатора.
Процесор і пам’ять є в різних комірках, але обидві комірки під’єднані до різних комутаторів(в цьому випадку інфа проходить через 2 комутатора).
Величина затримки залежить від взаєм. розповсюдження проц. і пам., а також від характеру обчисл. Навантаження. Затримка може мінятися залежно від числа додатків одночасно.
Затримка у залежності від числа проців та завантаження(коефіцієнт збільшення затримки)
Число процесорів
Однопотокові програми нс.
Багатопотокові нс.
4
174
235
8
208
266
16
228
296
32
261
336
64
275
360
В даному варіанті з’являються додаткові варіанти необхідні для підтримання когерентності кеш-пам’яті.
В багато гілкових варіантах з’являються додаткові витрати необхідні для підтримки когерентності кеш-пам’яті. Коефіцієнт збільшення затримки при переході від 4-х до 64-х процесорних конфігурацій – збільшується в 1.6 рази. 4 арифметичних операцій за один такт виконує PA8700 (750Mhz).
Той процесор PA8700 має суперскалярну архітектуру. Процесор має 10 функціональних пристроїв : 4-з цілочисельною арифметикою і логікою, 4- для роботи з іншим варіантом арифметики, і 2 пристрої для операцій читання/запис.
На кожному такті пристрій вибірки комірки комп’ютера може зчитувати до 4 комірок із кожної кеш-пам’яті.
Об’єм пам’яті 2.25Мбайти з яких 1.5Мб кеш даних, 0.75 Мб –кеш команд. Вся кеш має 4 канали. Якщо в програмі 20% всіх операцій виконується строго послідовно, то прискорення більше ніж 5 отримати неможливо, незалежно від того яке число швидкості процесора.
Комп працює під UNIX,Windows 2000,Lindows. Комп працює з великою к-стю зовн. пристроїв з можливістю гарячої заміни апаратури. Резервування, моніторинг базових параметрів.
Порівняйте багатомашинні та багатопроцесорні КС.
На перший погляд різниця незначна, але ця різниця призводить до двох різко відмінних за побудовою та організацією обчислень класів КС
багатомашинні КС
багатопроцесорні КС
У багато машинному варіанті уся система мовби розпадається на декілька незалежних систем класу ОКОД, тобто по суті це самостійні ЕОМ з усіма властивостями притаманним ЕОМ
Порівняйте переваги та недоліки централізованих та децентралізованих КС.
4.1. Визначення централізованого та децентралізованого управління
4.1.1. Централізоване управління (рис.1,а) передбачає наявність одного блоку управління, який збирає повну інформацію про всі об’єкти управління і генерує (розраховує, приймає рішення про) сигнали управління для всіх цих об’єктів. Децентралізоване управління (рис.1,б) передбачає, що кожний з об’єктів управління оснащений власним блоком управління, який генерує для нього сигнали управління, виходячи з інформації лише про нього.
ОУ БУ ОУ
БУ ОУ БУ ОУ
.... ..... .....
БУ ОУ
ОУ
а) б)
Рис.1. Структура а) централізованого та б) децентралізованого управління (БУ – блок управління, ОУ – об’єкт управління)
4.1.2. Існують дві вимоги до систем управління:
адекватність (цілеспрямованість, доцільність),
оперативність управління (швидкість з якою примаються рішення).
Принцип дуальності управління (Фельдбаум) – ці вимоги протирічать одна іншій, в наслідок чого має бути знайдено оптимальне співвідношення цих двох вимог. Це протиріччя набуває особливого змісту для розподілених систем.
4.2. Порівняння централізованого та децентралізованого управління на прикладі
4.2.1. Задача побудови вежі (Tower building task). Розглядається обмежений двовимірний дискретний простір. Перед колективом мобільних агентів ставиться задача побудувати в цьому просторі “вежу”. Кожний з агентів може рухатись в чотирьох напрямках (вверх, вниз, вправо, вліво), а також піднімати та перевозити один вантаж (підняти, покласти) ( всього шість команд. Першопочатково “будівельні блоки” розкидані випадковим чином. Стартове розміщення агентів в просторі так само випадкове. Де буде побудована вежа не має значення. Фактично треба зібрати всі блоки до купи.
4.2.2. Алгоритм для централізованого управління (один з можливих):
1. Визначити координату центру вежі.
2. Доки не побудована вежа: Цикл від 1 до N (виконується для кожного агента):
Якщо агент знайшов блок, то визначити чи належить цей блок до вежі. Якщо так, то шукати далі. Якщо ні, то визначити куди рухатися агенту з блоком (алгоритм №1 додавання блоку до вежі), і віддати відповідний наказ.
Інакше вибрати напрям руху для агента (алгоритм №2 пошук блоку в просторі) і віддати наказ.
4.2.3. Алгоритм для децентралізованого управління (виконується кожним агентом)
Рухатись в будь якому напрямку.
Якщо я зустрів вантаж, то
якщо я з вантажем, то покласти його біля цього вантажу і перейти до п.1.
інакше взяти вантаж і перейти до п.1.
4.2.4. Обидва алгоритми гарантують вирішення задачі. Алгоритм для централізованого управління є складним та більш швидко приводить до результату. Алгоритм для децентралізованого управління дуже простий та працює значно повільніше. Порівнюючи складність та швидкодію цих алгоритмів, можна зробити висновок про доцільність комбінації двох підходів до управління. В цьому аспекті самоорганізація розуміється як пошук оптимального співвідношення централізованого та децентралізованого управління в залежності від поставленою перед системою задачі та умов, в яких ця задача вирішується.
Визначити основні типи паралелізму, які дозволяють одночасне рішення різних задач або частин однієї задачі.
Природний паралелізм незалежних задач полягає в тому, що в систему поступає неперервний потік непов’язаних між собою задач. Тобто розвязок будь-якої задачі не залежить від результатів розвязку інших задач. У цьому випадку використовується декілька пристроїв обробки при будь-якому способі комплексування (прямому чи непрямому), що підвищує продуктивність системи.
Паралелізм незалежних гілок. Суть полягає в тому, що при розв’язанні великої задачі можуть бути виділені окремі незалежні частини – гілки проги, які при наявності декількох пристроїв обробки можуть виконуватись паралельно та незалежно один від одного. Двома незалежними гілками програми будемо вважати такі частини задачі, при виконанні яких виконуються наступні умови:
Для обох гілок програми не мусить робитися запис в одну і ту саму комірку памяті (відсутність зв’язку із використанням одних і тих самих полів ОП);
Умови використання однієї гілки не залежить від результату або ознак, отриманих при виконанні іншої гілки (незалежність за керуванням);
Ні одна із вхідних для гілки величин не є вихідною величиною іншої гілки (відсутність функціональних зв’язків);
Обидві гілки мусять виконуватися за різними блоками програми (програмна незалежність).
Ярусно-паралельна форма програми та її особливості при застосуванні КС.
Добре уявлення про паралелізм незалежних гілок дає ярусно- паралельна форма проги .
Прога представленна у вигляді сукуп. гілок , розміщених на декількох рівнях (ярусах).Довжина гілки представлена цифрою, що стоїть біля кружка.Стрілками позначені вхідні дані та результати обробки.Вхідні- символ Х, вихідні – символ У.Символи Х –мають нижні цифрові індекси, які позначають номери вхідних величин. Символ У мають цифрові індекси зверху і знизу : цифра вгорі відповідає номеру гілки , при виконанні якої отриманий даний результат; цифра внизу визначає порядковий номер результату, що отриманий при реалізації даної гілки проги.Гілки кожного ярусу не пов’язані одні з одним , тобто результати розвязку будь-якої гілки даного ярусу не є вхідними даними для іншої гілки цього ярусу.На цьому ж графі можуть бути зображенні зв’язки за керуванням або памятю .У цьому випадку граф дозволяє показати наочно повністю незалежні гілки. На прикладі цього графа можна виявити переваги КС, яка включає декілька пристроїв обробки та побачити деякі недоліки, що виникли при реалізації.
Довжина і-ї гілки представлена числом часових одиниць ti , які необхідні для її виконання.
Стрілками позначені вхідні дані та результати обробки. Вхідні символи позначені символом Х, а вихідні дані –Y. Символи Ч мають нижні цифрові індекси вхідної величини. Символи Y мають індекси знизу і вгорі. Цифри вгорі відповідають номеру гілки, виконанні якої отриманий даний результат, а цифра знизу визначає порядковий номер результату який отриманий при реалізації даної гілки програми.
Програма має 14 гілок, які розділені на п’ятьох ярусах. Гілки кожного яруса не пов’язані одні з іншим, тобто результат рішення будь-якої гілки даного ярусу не є вхідними даними для іншої гілки цього ярусу.
На цьому графі можуть бути зображені і зв’язки за керуванням, або пам’яттю.
На виконання цієї програми потрібно: ,де tі - довжина кожної гілки. Т = 375 од.часу.
Уявляємо, що програма виконується двома пристроями обробки (процесорами), які працюють незалежно один від одного, тому час буде різний в залежності від послідовності виконання незалежних гілок.
(Двопроцесорний варіант)
Варіант 1: Процесор 1: 1–4–5–9–10–13 (Т1=145)
Процесор 2: 2–6–3–7–8–11–12–14 (Т2=230)
Варіант 2: Процесор 1: 1–4–5–9–10–11–13 (Т1=160)
Процесор 2: 2–6–3–7–8–12–14 (Т2=215)
Варіант 3: Процесор 1: 1–4–8–12–11–13 (Т1=175)
Процесор 2: 2–5–6–3–7–9–10–14 (Т2=200)
Для того, щоб із допомогою декількох процесорів чи пристроїв обробки розв’язати задачу, яка має незалежні паралельні гілки, необхідна відповідна організація процесу та інформація про готовність кожної гілки.
Все це відносно легко реалізувати тоді, коли достатньо точно відома тривалість виконання кожної гілки. На практиці це буває дуже рідко. В кращому випадку відома наближена довжина гілок, тому організація близького до оптимального графіка роботи є досить складною задачею. Також тяжко уникнути деяких простоїв (затримок), які виникають за відсутності початкових даних тої або іншої гілки, тому виграш в продуктивності системи трохи знижується.
Є певні складності, які пов’язані із виділенням незалежних гілок. Наразі добре піддаються паралельній обробці (з використанням незалежних гілок) такі задачі:
задачі матричної алгебри;
задачі лінійного програмування;
задачі спектральної обробки сигналів;
прямі та зворотні перетворення Фур’є.
Визначити основну концепцію та гіпотези теорії колективної поведінки, які покладені в основу ідеології багатоагентних систем.
Теорія колективної поведінки базується на гіпотезі про перевагу колективної дії над індивідуальною та гіпотезі про простоту, яка стверджує, що сумісна реалізація та локальна взаємодія простих поведінкових актів може проводитися в результаті до складних поведінкових процесів.
Багатоагентні системи в першу чергу займаються проблемою самоорганізації.
Задачі самоорганізації:
самовиявлення колективу
само іменування агентів
самосинхронізація колективу(синхронізація в часі)
само впорядкування колективу
само впорядкування за параметром
Визначити поняття агента та самоорганізації багатоагентної системи; навести основні процедури самоорганізації колективу агентів.
Агент – створена штучно автономна реальна або віртуальна сутність (сукупність апаратних та програмних засобів), яка спроможна до самостійних цілеспрямованих активних дій у складі колективу або індивідуально в інтересах володаря або користувача.
Агент діє в інтересах досягнення сформульованих користувачем цілей, виходячи із своїх внутрішніх уявлень про середовище. Агент існує у середовищі, взаємодіє із середовищем та з іншими агентами і може змінювати середовище.
Багатоагентні системи в першу чергу займаються проблемою самоорганізації.
Задачі самоорганізації:
самовиявлення колективу
само іменування агентів
самосинхронізація колективу(синхронізація в часі)
само впорядкування колективу
само впорядкування за параметром
Поясніть вміст та значення двох законів Мура, закону Рока, законів Амдаля.
Закони, які треба враховувати при розгляді КС:
1. І з. Мура (1975) – число елементів на чіпі = const*2(рік-1975)/1,5.
2. З. Рока – вартість осн. обладнання для створення напівпровідникових пристроїв буде подвоюватися кожні 4 роки.
3. ІІ з. Мура (1995) – капітальні витрати збільшуються набагато швидше ніж витрати.
Один з осн. методів підвищення продуктивності полягає в паралельній обробці інформації.
Пар. обробку інф-ії можна робити враховуючи закони Амдала:
З.І. Продуктивність КС, яка створена з зв’язаних між собою пристроїв в заг. випадку визн. найбільш непродуктивним її пристроєм.
З.ІІ. У системі, що створена з S однакових універсальних пристроїв, при виконанні пар. частини алгоритму всі S пристроїв завантаженні повністю, max можливе прискорення R=S/(βS+(1-β)), де β=n/N – частка послідовних обчислень; n – послідовні операції з заг. N.
З.ІІІ. У системі, що створена з простих однакових універсальних пристроїв, при будь-якому режимі роботи прискорення не може перевищити зворотної величини частки послідовних обчислень.
Якщо послідовно виконується n операцій, то число ярусів будь-якої форми алгоритму не може бути менше n. В цих формуваннях ніде не конкретизувалося зміст операції. Сучасні КС можуть мати до 10000 процесорів, які повинні повністю завантажуватися. Дослідження доводять, що частка послідовних операцій у багатопроц. системах = 0,1-0,01 %.
В дослідженнях по закону Амдаля не конкретизується зміст операцій. В загальному випадку вони можуть бути як елементарними так і дуже складними, які уявля.ть алгоритм розв’язку достатньо складних задач. КС із великою кількісттю процесорів мусять бути завантажені достатньо богато, в іншому випадку немає смислу їх створювати. Дослідження показали, що в паралельних системах доля послідовних операцій мусять бути порядка десятих і сотих процента.
Визначити та обґрунтувати основні причини появи КС.
КС потрібні тоді коли універсальна ЕОМ не може впоратись зі своєю роботою
Існує 3 причини появи КС:
Підвищення надійності.(промислові комп’ютери, які створені для роботи у важких умовах )
Підвищення продуктивності.
Робота в режимі реального часу.
(Earth Simulation NEC 2002p. 35,86 TFlops 350 млн.$ Японія(Системи передбачення землетрусів).
Визначити основні ознаки, за якими класифікуються КС.
Класифікація КС – річ складна. Однієї класифікації не існує.
Ознаки:
КС бувають:
Централізовані
Децентралізовані
Існує ще підхід (Поспєлов):
абсолютно централізовані;
абсолютно децентралізовані.
Зараз у більшості використовуються централізовані системи. Звичайні системи – централізовані. Армія – це централізована система.
Є обставини, коли централізація неможлива:
коли центр гине;
об’єкти мають окремо приймати рішення, тобто нема центру.
КС бувають:
Однорідні
Неоднорідні
Якщо система складається з різнорідних об’єктів, то важче налагодити керування. Раніше під поняттям КС (комп’ютерні системи) розуміли сукупність однорідних машин, а під поняттям К комплекси – різнорідні. Зараз поняття КС об’єднує як однорідні, так і різнорідні системи.
КС бувають:
Територіально суміщені системи
Територіально розподілені системи
Визначити основні типи архітектури КС згідно класифікації Фліна.
Процес розв’язання задачі можна уявити як вплив певної послідовності команд програми (потоку команд) на відповідну послідовність даних (потоку даних), яка викликається всієї послідовності команд. Різні способи паралельної обробки інформації можна уявити, як засоби одночасного впливу одного або декількох потоків команд на один або декілька потоків даних.
Для такої класифікації є корисним ввести поняття множини потоків команд і даних. Під множиною потоків команд або даних будемо розуміти наявності в системі декілька послідовних команд які знаходяться в стані реалізації, або декілька послідовних даних, які обробляються комп’ютером.
Всі системи можуть бути поділені на 4 великі класи.
Системи з одним потоком команд і одним потоком даних (ОКОД). (SISD)
Системи з множиною потоків команд і одним потоком даних (МКОД). (MISD)
Системи з одним потоком команд і множиною потоків даних (ОКМД). (SIMD)
Системи з множиною потоків команд і множиною потоків даних (МКМД). (MIMD)
1. Системи класу ОКПД (ОКОД) SISD – Single Instruction Single Data.-cистеми цього класу–звичайні одно процесорні ЕОМ.Складаються з запам’я-товуючого пристрою(пам. даних і пам. команд), процесора(пристрій керування і АЛП).
Приклади ОКОД:
1.CISC – Complex Instruction Set Computer – Комп’ютер з певним набором команд. Intel всі свої процесори робить на основі CISC.
2.RISC – Reduced Instruction Set Computer – Комп’ютер із скороченим набором команд. Має 64 розрядні адреси команд.
3.VLIW-Itanium
4.EPIC- паралельна обробка команд з явним паралелізмом
VLIW I EPIC – наддовге слово , виконують декілька команд за один такт
Чіпи (кристали) RISC „розуміють” лише деякі інструкції, але кожну з них вони можуть виконати дуже швидко. Програми для RISC достатньо складні, але вони виконуються набагато швидше за тих які виконуються в CISC.
В основі процесора Itanium полягає архітектура Itanium Architecture 64, але назва її інша EPIC – Explicitly Parallel Instruction Computing- паралельна обробка команд з явним паралелізмом, VLIW – Very Long Instruction Word – (комп’ютер з наддовгим машинним словом).
Особливості концепції Itanium є те, що компілятор пакує декілька простих команд у довге слово яке відповідає набору функціональних пристроїв процесора. При цьому розпаралелення коду здійснюється на етапі компіляції.
Процесори Itanium мають значну більшу кількість ніж інші процесори.
Тип регістрів
К-сть регістрів
Розмір
Примітка
загал.призначення
128
64+1
програмісту доступні 64 біта,1-NaT(Not a Thing)
з плав. комою
128
82
предикативні
64
1
гілкування
64
8
Наприклад Itanium має 128 регістрів загального призначення. Архітектура х86 має 8 регістрів.
NaT-придатність інфи, що записана в регістрі. Якщо дані призначені невірно(в результаті невірного гілкування), то змінюється тільки NaT- це дає істотний виграш в часі, бо не вимагає стирання даних в регістрі.
Предикативність - контролює умови виконання інструкцій та гілкування.
Гілкування – вказує адреси гілок проги.
EPIC (архітектура з явним паралелізмом) надає, у порівнянні з RISC процесором, більш широке використання паралельних обчислень. Під терміном паралельні обчислення маємо на увазі не об’єднання 2-ох або більше процесорів для розв’язання одної задачі, а спроможність процесора типу Itanium виконати декілька команд за одним тактом .
В технології EPIC застосовуються дві методики:
Передбачення гілкування [predication]
Базується на аналізі компілятором проги, що виконується. Компілятор приймає рішення, які з гілок потрібно прораховувати, а які ні.
2. Припущення [speculation loading]
Iнструкція і дані завантажуються в проц до того, як вони можуть бути придатними, а у деяких випадках, навіть, якщо вони не будуть потрібні ніколи. Таке попереднє завантаження робиться під час простоювання системи. Якщо дані, що завантажуються, -це ті, які необхідні для подальшої роботи, потрібен час для завантаження.
Системи класу МКОД (MISD )
На малюнку:
ЗПК- запам’ятовуючий пристрій команд
ЗПД- запам’ятовуючий пристрій даних
В системі МКОД декілька потоків команді впливають на один і той же потік даних, але не існує такого класу задач у яких одна і та ж сама послідовність даних підлягала б обробці за декількома різними програмами. По цій причині така схема дотепер не реалізована. Реалізована інша схема з одним К замість двох
В даному випадку один потік команд розподіляється пристроями керування на декілька потоків мікро операцій , кожна з яких реалізується спеціалізованим налагодженням на виконання мікро операцій пристрою.
Потік даних проходить послідовно через всі або частину спеціалізованих АЛП. Саме такого класу системи прийнято називати конвеєрними або системи магістральної обробки інформації. В системах МКОД з метою досягнення великої продуктивності використовують не тільки конвеєр операцій ,але і конвеєр команд. Основною ознакою є конвеєр арифметичних і логічних операцій.
Системи такого класу розвивають тільки максимальну продуктивність при вирішені задач певного класу типу, у яких існують довгі послідовності однотипних операцій над достатньо великою послідовністю даних. Тобто коли має місце паралелізм об’єктів або даних.
Це конвеєрні системи. Їх реально не існує?
Системи класу ОКМД.
Системи такого класу орієнтовані на використання паралелізму об’єктів або даних для підвищення продуктивності.
В цій системі по одній і тій самій програмі обробляється декілька потоків даних. Одна команда керує багатьма даними. У цієї системи по одній (або майже по одній) прозі обробляються декілька потоків даних. Кожен з цих потоків обробляється своїм АЛП, але всі АЛП працюють під загальним керування, внаслідок чого досягається висока продуктивність і надійність системи. Ця загальна схема реалізується різними способами. Так АЛП може представляти собою достатньо складний пристрій, який містить пр. обробки операцій ЗП. Керування в пам’яті команд керується окремою ЕОМ, яким керує ансамбль процесорів. Наприклад, IRIAC має ансамбль матричний.
Пам’ять даних може мати не тільки адресу вибірки, але і асоціативну вибірку ,тобто за змістом пам’яті. Проте комп не може реалізувати повністю асоціативну роботу(одночасна обробка). Для систем класу ОКМД визначним є одночасна обробка декількох потоків даних декількома процесорами. Всі системи класу ОКМД поділяються на матричні та асоціативні.
Системи класу МКМД. MIMD - Multiple Instruction Multiple Data
Існують два способи побудови систем МКМД:
у вигляді сукупності елементарних систем ОКОД
не у вигляді сукупності елементарних систем ОКОД
На малюнках вказані лише частина системи, але таких частин багато
При такому варіанті побудови для Тут всі команди і всі дані розміщуються
кожної послідовності команд і даних у загальному ЗП(В одному приміщення)
маємо власний ЗП.(Наприклад, в різних
приміщеннях)
На перший погляд різниця незначна, але ця різниця призводить до двох різко відмінних за побудовою та організацією обчислень класів КС
4.1 багатомашинні КС
4.2 багатопроцесорні КС
У багато машинному варіанті уся система мовби розпадається на декілька незалежних систем класу ОКОД, тобто по суті це самостійні ЕОМ з усіма властивостями притаманним ЕОМ
Недоліки:
перевантаження класу МКМД.
Деякі архітектури, а саме – машина потоків даних та векторно-конвеєрні машини чітко не пояснюються даною класифікацією.
Визначити основні варіанти розв’язання проблеми паралельної обробки інформації на прикладі побудови мура ("Мур Фокса")
При пар. програмуванні виникають проблеми, які можна розглянути за доп. прикладу „Мур Фокса”. Задача: ск. часу потрібно 4 робітникам для побудови стіни, якщо одному треба t годин. Для робітників виникає проблема ефективності, конструктивності. Ось декілька шляхів розв’язання задачі, що має аналогію з пар. програмуванням.
Метод 1 – конвеєрне розв’язання.
Кожен робітник викладає 1 ряд цегли, рухаючись горизонтально, вздовж муру. Ефективність буде < 100%, тому що верхні ряди не будуть будуватися, поки не буде побудовано нижніх. Це забезпечує накладні витрати пов’язані з заповненням та звільненням векторного конвеєру векторних мащин. Цей метод ефективний при достатньо довгому мурі.
Метод 2 – геометричне розв’язання.
Мур розподіляється на вертикальні сектори, які виділяються кожному робітнику. Всі вони можуть почати роботу одночасно, але виникає проблема синхронізації робіт на стику секторів. Поки 2 цеглярі, що працюють поруч, не обміняються інф-єю про розміщення сусідньої цегли нижнього ряду, доти не можна класти наступний. Крім накладних витрат на обмін інф-єю і синхронізацію необхідно забезпечити ефективність. Через не рівномірний розподіл секторів такий метод є мало ефективним.
Метод 3 – колективне розв’язання.
Цегла і цемент лежать в одному місці, а не розділяються між робітниками. Вони беруть з собою деяку к-сть матеріалів і кладуть цемент і цеглу на вільне місце. При такій організації виникає неефективність на початку і в кінці робіт, але це не завада для деяких типів задач.
При пар. роботі виникають проблеми невизначеності та тупика, які можна вирішити так: офіціант не з середовища відвідуюючих.
Визначити основні типи архітектури КС згідно класифікації Р. Хокні.
Класифікація Р.Хокні (R.Hockney)
Додаткова класифікація класу МКМД.
Основна ідея класифікації :
1. Множинний потік команд може бути оброблений 2-ма способами:
-або 1-им конвеєрним пристроєм обробки, який прац...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора