Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Методичні вказівки
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти та Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
М Е Т О Д И Ч Н І В К А З І В К И
до розрахункової роботи з дисципліни “Паралельні та розподілені обчислення”
для студентів базового напряму 6.050102 "Комп’ютерна інженерія"
Затверджено на засіданні кафедри Електронних обчислювальних машин Протокол № від року
Львів - 2013
Методичні вказівки до розрахункової роботи з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.050102 "Комп’ютерна інженерія"/ Укладачі: Є. Ваврук, І.Грицик – Львів: Національний університет “Львівська політехніка”, 2013, 24 с.
Укладачі: Є. Ваврук, к.т.н., доцент
І. Грицик, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
Рецензенти: Парамуд Я.С., к. т. н, доцент
Дунець Р.Б., д.т.н., доцент.
Анотація
Дані методичні вказівки укладені у відповідності з робочою навчальною програмою з дисципліни „Паралельні та розподілені обчислення”. В них розглянуті основні питання моделювання задач предметних галузей, та паралельного виконання операцій над матрицями і векторами. Вивчення матеріалів, що наведені в методичних вказівках, допоможе студентам набути практичні навики з проектування паралельних процесів.
Зміст
Зміст 4
Вступ 5
1. Загальні положення 6
2. Принципи паралельного перемноження матриць. 7
2.1. Особливості перемноження матриці на матрицю і їх реалізація на основних типах структур: кільцева, 2D (решітка), 3D (куб). 7
2.2. Особливості використання технології паралельного програмування Message Passing Interface (MPI). 12
3. Вимоги і варіанти курсових робіт 15
3.1 Вимоги до оформлення пояснювальної записки. 15
3.2 Варіанти до розрахункової роботи. 16
4. Оцінювання роботи 19
Висновки 20
Література 21
Додаток А 22
Додаток Б 23
Вступ
Для розв’язання багатьох задач (прогноз погоди, задачі гідро- і газодинаміки, квантової хімії, астрономії, спектроскопії, біології, ядерної фізики тощо) необхідна висока продуктивність обчислень, висока швидкість передачі інформації по каналах зв’язку та великі об’єми оперативної і постійної пам’яті. Одним з шляхів забезпечення таких вимог є організація паралельних обчислювальних процесів і відповідних технічних засобів їх реалізації.
Причому, ефективність паралельної обробки залежить як від продуктивності комп’ютерів, так і від розмірів і структури пам’яті, пропускної здатності каналів зв’язку, використаних мов програмування, компіляторів, операційних систем, чисельних методів та інших математичних досліджень. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів.
Для скорочення термінів розробки паралельних засобів та дослідження їх роботи використовується моделювання.
Метою виконання розрахункової роботи є засвоєння основних методів та алгоритмів моделювання паралельних обчислювальних процесів, принципів побудови відповідних структур, набуття початкових практичних навиків проектування таких засобів та ознайомлення з бібліотекою MPI.
В результаті вивчення курсу студент повинен:
знати: основні методи, алгоритми і засоби паралельного опрацювання інформації, засоби програмування на паралельних структурах, склад апаратних засобів та програмного забезпечення обчислювальних систем з елементами паралельного опрацювання;
вміти: виконувати елементарні вправи з розпаралелення задач та алгоритмів, проводити розрахунки параметрів, моделювати паралельні обчислювальні процеси з сучасних технологій паралельного програмування (CUDA,MPI), проектувати окремі вузли.
1. Загальні положення
Тематика розрахункової роботи охоплює основні напрямки розвитку паралельних обчислень, а саме:
1. Паралельне виконання операцій множення матриць.
2. Моделювання задач предметних галузей. Курсові роботи даного напрямку рекомендується до виконання студентам, які схильні до наукової роботи і планують продовжити навчання в магістратурі.
Вибір напрямку виконяння розрахункової роботи слід проводити з врахуванням індивідуальних схильностей студента до певного напрямку творчої діяльності.
Тему розрахункової роботи за напрямком “Моделювання задач предметних областей” пропонує студент і погоджує з викладачем.
2. Принципи паралельного перемноження матриць.
2.1. Особливості перемноження матриці на матрицю і їх реалізація на основних типах структур: кільцева, 2D (решітка), 3D (куб).
Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач лінійної алгебри, наприклад ітераційних методів розв’язання систем лінійних рівнянь і т.п. Тому приведені алгоритми тут можна розглядати як фрагменти в алгоритмах цих методів. Розглянемо три алгоритми множення матриці на матрицю. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один комп'ютер; і завантаження даних безпосередньо кожним комп'ютером з дискової пам'яті. Якщо завантаження даних здійснюється через один комп'ютер, то дані зчитуються цим комп'ютером з дискової пам'яті, розрізаються на частини, які розсилаються іншим комп'ютерам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана на диск у виді окремого файлу зі своїм ім'ям; потім кожен комп'ютер безпосередньо зчитує з диска, призначений для нього файл.
Алгоритм 1- Перемноження матриці на матрицю на кільцевій структурі.
Задано дві вихідні матриці A і B. Обчислюється добуток C = А х B, де А - матриця n1 х n2, і B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці попередньо розрізані на смуги, смуги записані на дискову пам'ять окремими файлами зі своїми іменами і доступні всім комп'ютерам. Матриця результатів повертається в нульовий процес.
Реалізація алгоритму виконується на кільці з p1 комп'ютерів. Матриці розрізані як показане на рис. 2.1: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p1 вертикальних смуг, і матриця результату C розрізана на p1 смуги. Тут передбачається, що в пам'ять кожного комп'ютера завантажується і може знаходитися тільки одна смуга матриці А і одна смуга матриці B.
Рис. 2.1 Розрізування даних для паралельного алгоритму добутку двох матриць при обчисленні на кільці комп'ютерів. Виділені смуги розташовані в одному комп'ютері.
Оскільки за умовою в комп'ютерах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно "прокрутити" по кільцю комп'ютерів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця і відповідна операція множення наведена на рис.2.2 у виді окремого кроку. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отриманий у підматриці(i,j) матриці C.
Обчислення відбувається в такій послідовності.
1. Кожен комп'ютер зчитує з дискової пам’яті відповідну йому смугу матриці А. Нульова смуга повинна зчитуватися нульовим комп'ютером, перша смуга - першим комп'ютером і т.д., остання смуга - зчитується останнім комп'ютером. На рис. 2.2 смуги матриці А і B пронумеровані.
2. Кожен комп'ютер зчитує з дискової пам’яті відповідну йому смугу матриці B. У даному випадку нульова смуга повинна зчитуватися нульовим комп'ютером, перша смуга - першим комп'ютером і т.д., остання смуга - зчитується останнім комп'ютером.
3. Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
4. Обчислювальний крок 2. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів. І т.д.
5. Обчислювальний крок p1-1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
6. Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця комп'ютерів.
7. Матриця C збирається в нульовому комп'ютері.
Рис. 2.2 Стадії обчислень добутку матриць у кільці комп'ютерів.
Якщо "прокручувати" вертикальні смуги матриці B, то матриця С буде розподілена горизонтальними смугами, а якщо "прокручувати" горизонтальні смуги матриці A, то матриця С буде розподілена вертикальними смугами.
Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа в сусідній комп'ютер. Тоді сумарний час операцій множень дорівнює:
U = (n1*n2)*(n3*n2)*tu, (2.1)
сумарний час операцій додавань дорівнює:
S = (n1*n2)*(n3*(n2-1))*ts (2.2)
сумарний час операцій пересилань даних по всіх комп'ютерах дорівнює:
P = (n3*n2)*(p1-1)*tp (2.3)
Загальний час обчислень визначимо як:
T = (U+S+P)/p1 (2.4)
Відношення часу "обчислень без обмінів" до загального часу обчислень є величина:
K = (U+S)/(U+S+P). (2.5)
Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам'ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами - 1. При великих матрицях цим можна знехтувати.
При достатніх ресурсах пам'яті в системі краще використовувати алгоритм, у якому мінімізовані обміни між комп'ютерами в процесі обчислень. Це досягається за рахунок дублювання деяких даних у пам'яті комп'ютерів. У наступних двох алгоритмах використовується цей підхід.
Алгоритм 2 - Перемноження матриці на матрицю на 2D решітці.
Обчислюється добуток C = А х B, де А - матриця n1 х n2, і B - матриця n2 х n3. Матриця результатів C має розмір n1 х n3. Вихідні матриці спочатку доступні на нульовому процесі, і матриця результатів повертається в нульовий процес.
Паралельне виконання алгоритму здійснюється на двовимірній (2D) решітці комп'ютерів розміром p1 х p2. Матриці розрізані, як показано на рис. 2.3: матриця А розрізана на p1 горизонтальних смуг, матриця B розрізана на p2 вертикальних смуг, і матриця результату C розрізана на p1 х p2 підматриці (або субматриці).
Рис. 2.3 Розрізування даних для паралельного алгоритму добутку двох матриць при обчисленні на 2D решітці комп'ютерів. Виділені дані розташовані в одному комп'ютері.
Кожен комп'ютер (i,j) обчислює добуток i-й горизонтальної смуги матриці A і j-й вертикальної смуги матриці B, добуток отримується у підматриці (i,j) матриці C.
Послідовність стадій обчислення наведена на рис.2.4:
1. Матриця А розподіляється по горизонтальних смугах уздовж координати (x,0).
2. Матриця B розподіляється по вертикальних смугах уздовж координати (0,y).
3. Смуги А поширюються у вимірі y.
4. Смуги B поширюються у вимірі х.
5. Кожен процес обчислює одну підматрицю добутку.
7. Матриця C збирається з (x,y) площини.
Здійснювати пересилання між комп'ютерами під час обчислень не потрібно, тому що всі смуги матриці А перетинаються з усіма смугами матриці B у пам'яті комп'ютерів системи.
Цей алгоритм ефективніший від попереднього, тому що непродуктивний час пересилань даних здійснюється тільки при завантаженні даних у пам'ять комп'ютерів і при їхньому вивантаженні, і обміни даними в процесі обчислень відсутні. Оскільки час обмінів рівний нулеві, а час завантаження і вивантаження тут не враховується, то загальний час обчислень дорівнює:
T = (U+S)/(p1*p2) (2.6)
А відношення часу "обчислень без обмінів" до загального часу обчислень є величина:
K = (U+S)/(U+S)=1. (2.7)
Рис. 2.4 Стадії обчислення добутку матриць у 2D паралельному алгоритмі.
Алгоритм 3 - Перемноження матриці на просторовій сітці комп’ютерів.
Для великих матриць, час обчислення добутків може бути зменшений шляхом застосуванням алгоритму, що здійснює обчислення на 3-мірній (просторовій) сітці комп'ютерів.
У приведеному нижче алгоритмі відображаються основні дані обсягом n1 х n2 + n2 х n3 + n1 х n3 на об'ємну сітку комп'ютерів розміром p1 х p2 х p3. Матриці розрізані, як показано на рис. 2.5: Матриця А розрізана на p1 х p2 субматриці, матриця B розрізана на p2 х p3 субматриці, і матриця C розрізана на p1 х p3 субматриці. Комп'ютер (i,j,k) обчислює добуток субматриці (i,j) матриці А і субматриці (j,k) матриці B. Субматриця (i,k) матриці C виходить підсумовуванням проміжних результатів, обчислених у комп'ютерах (i,j,k), j = 0,...,p2-1.
Послідовність стадій обчислення наведена на рис. 2.6.
1. Субматриці А розподіляються в (x,y,0) площині.
2. Субматриці B розподіляються в (0,y,z) площині.
3. Субматриці А поширюються у вимірі z.
4. Субматриці B поширюються у вимірі х.
5. Кожен процес обчислює одну субматрицю.
6. Проміжні результати редукуються у вимірі y.
7. Матриця C збирається з (x,0,z) площини.
Алгоритм подібний до попереднього, але додатково розрізаються ще смуги матриць, і ці розрізані смуги розподіляються в третьому вимірі y. У даному випадку в кожному комп'ютері будуть перемножуватися тільки частини векторів рядків матриці А і частини стовпців матриці B. В результаті буде тільки часткова сума для кожного елемента результуючої матриці C. Операція підсумовування уздовж координати y цих отриманих часткових сум для результуючих елементів і завершує обчислення матриці C.
Загальний час обчислень у цьому алгоритмі дорівнює:
T = (U+S)/(p1*p2*p3) (2.8)
А відношення часу "обчислень без обмінів" до загального часу обчислень є величина:
K = (U+S)/(U+S)=1. (2.9)
Рис. 2.5 Розрізування даних для паралельного алгоритму добутку двох матриць при обчисленні на просторовій сітці комп'ютерів.
Рис. 2.6. Стадії обчислень у 3D паралельному алгоритмі добутку матриць.
2.2. Особливості використання технології паралельного програмування Message Passing Interface (MPI).
MPI - бібліотека функцій, яка забезпечує взаємодію паралельних процесів за допомогою механізму передачі повідомлень і не має ніяких засобів для розподілення процесів по обчислювальних вузлах і для запуску їх на виконання. МРІ не містить механізмів динамічного створення і знищення процесів під час виконання програми.
Для ідентифікації наборів процесів вводиться поняття групи і комунікатора.
Процеси об’єднуються в групи, можуть бути вкладені групи. Усередині групи всі процеси понумеровані. З кожною групою асоційований свій комунікатор. Тому при здійсненні пересилок необхідно вказати ідентифікатор групи, усередині якої проводиться це пересилка.
Процедури МРІ:
- ініціалізації та закриття МРІ –процесів;
- реалізації комутаційних операцій типу “точка-точка”;
- реалізації колективних операцій;
- для роботи з групами процесів і комунікаторами;
- для роботи з структурами даних;
- формування топології процесів.
До базових функцій МРІ відносяться:
ініціалізація МРІ;
завершення МРІ;
визначення кількості процесів в області зв’язку;
визначення номеру процесу, який виконується;
передача повідомлень;
приймання повідомлень;
функції відліку часу.
Кожна МРІ – функція характеризується способом виконання.
Локальна функція – виконується всередині процесу, що її викликав. Її завершення не вимагає комунікацій.
Нелокальна функція – для її завершення необхідно виконати МРІ – процедуру іншим процесом.
Глобальна функція – процедуру повинні виконати всі процеси групи. Невиконання цієї умови може привести до “зависання” задачі.
Блокуюча функція – повернення керування з процедури гарантує можливість повторного використання параметрів, які приймали участь у виклику. Ніякої змін в стан процесу, що викликав блокуючий запит до виходу з процедури не може відбуватися.
Неблокуюча функція – повернення з процедури відбувається негайно, без очікування завершення операції. Завершення неблокуючих операцій здійснюється спеціальними функціями.
Операції обміну повідомленнями
Розглянемо: режими обміну, обмін типу “точка-точка”, колективний обмін, способи реалізації моделі передачі повідомлень.
Режими обміну:
В загальному випадку є чотири режими обміну: асинхронний (стандартний), синхронний, з буферизацією, по “готовності”.
Обмін типу “точка-точка” – найпростіша форма обміну повідомленнями, в якій приймають участь тільки два процеси: джерело і адресат. Є кілька різновидностей двохточкового обміну:
синхронний обмін – супроводжується повідомленням про завершення прийому повідомлення;
асинхронний обмін – таким повідомленням не супроводжується;
блокуючі прийом/передача – призупиняють виконання процесу на час приймання повідомлення. Організація блокуючого обміну повідомленнями наведена на рис.2.7;
неблокуючі прийом/передача - виконання процесу продовжується в фоновому режимі, а програма в потрібний момент може запитати підтвердження завершення приймання повідомлення. Організація неблокуючого обміну повідомленнями наведена на рис.2.8.
Неблокуючий обмін вимагає акуратності при виконанні функцій прийому. Оскільки неблокуючий прийом завершується негайно, для системи неважливо, чи прибуло повідомлення до місця призначення чи ні. Переконатися про це можна за допомогою функції перевірки отримання повідомлення. Звичайно виклик таких функцій розміщується в циклі, який повторюється до тих пір, доки функція перевірки не поверне значення “істина” (перевірка отримання пройшла успішно). Після цього можна викликати функцію прийому повідомлення з буферу повідомлень.
Рис.2.7. Блокуючий обмін повідомленнями
Рис.2.8. Неблокуючий обмін повідомленнями
Колективний обмін . В операціях використовуються не два а більше процесів. Різновидностями обміну є:
широкосмугова передача – передача виконується від одного процесу до всіх;
обмін з бар’єром – форма синхронізації роботи процесів, коли обмін повідомленнями проходить тільки після того, як до певної процедури звернулась певна кількість процесів;
операції приведення – вхідними є дані кількох процесів, а результат – одне значення, яке стає доступним всі процесам, які приймали участь в обміні.
Важливою властивістю системи передачі повідомлень є гарантія збереження порядку прийому повідомлень (при відправленні одним процесом іншому кількох повідомлень вони повинні бути прийняті в тій самій послідовності в якій були відправлені). Більшість реалізацій моделі передачі повідомлень забезпечують цю властивість, але не у всіх режимах обміну.
3. Вимоги і варіанти курсових робіт
3.1 Вимоги до оформлення пояснювальної записки.
В залежності від обраного напрямку, рекомендації до оформлення можуть бути різними. Для напрямку «Паралельне виконання операцій над матрицями і векторами» пояснювальна записка повинна містити такі складові частини:
Титульний аркуш.
Завдання
Анотацію на двох мовох (англійська та українська)
Зміст
Вступ
Постановка, формулювання та аналіз завдання.
Розробка граф-схеми виконання операції перемноження матриці на матрицю на розрахованій на основі варіанту структурі на рівні опису формул та функціональних блоків з описом призначення кожного з них.
Розробка граф-схеми функціонування системи паралельного множення матриць із розгорнутим поясненням її роботи та проведеними необхідними обчисленнями показників ефективності розпаралелення.
Розробка та детальний опис програмної моделі системи паралельного множення матриць засобами MPI.
Оцінка та дослідження програмної моделі системи паралельного виконання операції множення матриць.
Висновки.
Перелік літературних джерел оформлений за стандантом “Бібліографічний запис. Бібліографічний опис" (ДСТУ 7.1:2006).
12. Допоміжні результати обчислень, схемні рішення, повний лістинг програми необхідно подавати в Додатках.
Для робіт виконаних за напрямком “Моделювання задач предметних областей” в основі яких лежить певний алгоритм чи процедура складові частини 7-10 пояснювальної записки повинні бути замінені на:
Розробка граф-схеми виконання розпаралеленого алгоритму (процедури) з детальним описом формул та функціональних блоків.
Розробка граф-схеми функціонування системи, із розгорнутим поясненням її роботи та проведеними необхідними обчисленнями показників ефективності розпаралелення.
Вибір технології паралельного проектування. Розробка та детальний опис програмної моделі системи паралеленого виконання алгоритму (процедури).
Оцінка та дослідження програмної моделі системи паралеленого виконання алгоритму (процедури).
Орієнтовні вимоги до змісту Пояснювальної записки розрахункової роботи наведені в таблиці 3.1.
Таблиця 3.1. Вимоги до Пояснювальної записки розрахункової роботи
№
п/п
Орієнтована назва розділу
Орієнтований зміст розділу
Орієнтовна
кількість сторінок
(мінімум)
1
Титульна сторінка
Назва теми роботи
1
2
Завдання до роботи
Вибір варіанту.
3
3
Анотація
Коротко наведені результати роботи(англійська та українська мова).
2
4
Зміст
Детальний зміст.
1
Таблиця 3.1(продовження)
5
Вступ
Значення, актуальність та практична цінність роботи.
2
6
Теоретичний розділ
Область застосування заданої досліджуваної задачі (алгоритму), особливості її реалізації.
5
7
Аналіз (розробка) граф-схеми виконання досліджуваної задачі
Результати розробки граф-схеми виконання досліджуваної задачі (повинні бути наведені граф-схема та опис її роботи; аргументовано вибір типу обробки).
5
8
Розробка функціональної схеми
Результати розробки структурної і функціональної схем функціонування системи (повинні бути наведені структурна і функціональна схеми та їх опис).
10
9
Розрахунковий розділ
Розрахунок показників ефективності розпаралелення досіджуваної задачі(алгоритму).
5
10
Розробка програми виконання досліджуваної задачі (алгоритму)
Блок схема, опис програми що моделює паралельне виконання досліджуваної задачі( алгоритму) з використанням технології паралельного програмування MPI. Аналіз часу виконання програми.
10
11
Висновки
Висновки щодо отриманих результатів з аналізом отриманих чисельних показників функціонування системи. Перспективи і шляхи покращення запропонованих технічних рішень.
1
12
Література
Перелік використаної літератури.
1
13
Додатки
Лістинг програми.
15
Основні вимоги до оформлення.
- формат аркушів А4;
- текстовий редактор Word (шрифт – 14; інтервал – 1,5; гарнітура – TimesNewRomanCyr);
- формули Equation 3 або 4;
відступи, мм:
зліва, 25;
справа 10;
зверху, знизу 20.
Решту матеріалів пояснювальної записки повинні відповідати вимогам нормативних документів.
Приклад оформлення титульної сторінки пояснювальної записки наведений в додатку А, список інтернет-джерел з інформацією про сучасні напрямки та перспективи розвитку паралельних та розподілених обчислень наведений в додатку Б.
3.2 Варіанти до розрахункової роботи.
Для курсових робіт виконаних за напрямком “Паралельне виконання операцій множення матриць” варіанти завдань розраховуються індивідуально для кожного студента на основі його П.І.Б (Прізвище, Імя,По-батькові), номера залікової книжки та номера групи. Нище наведений приклад розрахунку завдання до розрахункової роботи:
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3):
n1=3П, n2=2І, n3=2Б – КІ-41
n1=2П, n2=3І, n3=5Б – КІ-42
n1=1П, n2=7Б, n3=3І – КІ-43
n1=2Б , n2=4П, n3=2І – КІ-44
n1=6Б, n2=3П, n3=1І – КІ-45
n1=2І, n2=4П, n3= 4Б – КІ-46
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Наприклад студент Петренко Василь Іванович з групи КІ-41:
n1 = 3П – Т n2 = 2І – А n3 = 2Б – В
декодування вибраних літер для n1,n2,n3 відбувається на основі таблиці 3.2.
Таблиця 3.2 Декодування літер розмірностей для n1,n2,n3
n1
n2
n3
А-120
Б-110
В-100
Г-90
Ґ-80
Д-70
Е-60
А-64
Б-72
В-56
Г-88
Ґ-96
Д-104
Е-112
А-117
Б-95
В-73
Г-195
Ґ-301
Д-247
Е-149
Є-140
Ж-130
З-150
И-160
І-170
Ї-180
Й-190
Є-128
Ж-146
З-154
И-168
І-176
Ї-184
Й-192
Є-93
Ж-111
З-127
И-349
І-181
Ї-163
Й-217
К-200
Л-210
М-220
Н-230
О-240
П-250
Р-260
К-208
Л-216
М-224
Н-232
О-248
П-256
Р-264
К-307
Л-325
М-251
Н-67
О-333
П-241
Р-159
С-270
Т-280
У-50
Ф-40
Х-290
Ц-300
Ч-310
С-272
Т-288
У-296
Ф-304
Х-312
Ц-328
Ч-336
С-234
Т-91
У-181
Ф-143
Х-37
Ц-45
Ч-129
Ш-320
Щ-330
Ь-340
Ю-350
Я-360
Ш-344
Щ-352
Ь-48
Ю-368
Я-376
Ш-225
Щ-71
Ь-167
Ю-349
Я-118
Згідно з таблицею 3.2 отримаємо такі значення n1,n2,n3:
n1=3П – Т=280
n2=2І – А=64
n3=2Б – В=73
Отже маємо матрицю А(280*64) та матрицю В(64*73)
2. Розробити та описати алгоритм множення матриць А*В на структурі яка задається виразом:
16b-5b-8b-4b-12b-7b-6b-14b – КІ-41
5b-12b-6b-11b-8b-1b-3b-13b – КІ-42
14b-8b-1b-3b-9b-2b-11b-5b – КІ-43
3b-6b-2b-5b-10b-13b-14b-11b – КІ-44
9b-10b-3b-6b-7b-12b-8b-4b – КІ-45
7b-3b-4b-11b-15b-9b-2b-1b – КІ-46
, де «nb»- номер букви П.І.Б студента.
Наприклад студент ПетренкоВасильІванович з групи КІ-41*:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
П
Е
Т
Р
Е
Н
К
О
В
А
С
И
Л
Ь
І
В
А
Н
О
В
И
Ч
4
2
7
6
3
5
8
1
*якщо кількість букв недостатньо то вираз застосовується до послідовності ПІБПІБПІБ.
Отримаємо – ВЕОРИКНЬ**
**якщо присутнє дублювання букв то береться буква яка іде наступною в ПІБ після необхідної.
На основі декодування отриманого набору букв на основі таблиці 3.3 формуємо варіант-стовпець
Таблиця 3.3 Кодування букв
А -27 Б -35 В -203 Г -74 Ґ -95 Д - 13 Е - 171
Є- 34 Ж-126 З -67 И -91 І -223 Ї -161 Й -146
К -47 Л -212 М -43 Н -134 О- 250 П -219 Р – 93
С -82 Т - 198 У -164 Ф -233 Х- 127 Ц -201
Ч -49 Ш -157 Щ -19 Ь -28 Ю – 63 Я- 155
Для ВЕОРИКНЬ отримаємо 203,171,250,93,91,47,134,28. Даний набір чисел записуємо у стовпець і переводимо кожне в двійкове 8-ми розрядне число:
203 - 11001011
171 - 10101011
250 - 11111010
093 - 01011101
091 - 01011011
047 - 00101111
134 - 10000110
028 - 00001110
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
11001011 01001011
10101011 10101011
11111010 11011010
01011101 01001101
01011011 => 01010011
00101111 00101011
10000110 10000100
00001000 00001000
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори, а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує певну 8-ми процесорну систему (структуру) із направленими зв’язками між вершинами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для заданому співвідношенні часових параметрів та типу початкового завантаження, що визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1...k, де k – кількість цифр номера залікової книжки.
Type=1 (спільна пам’ять), type=2 (через один процесор), type=3 (розподілена пам’ять).
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
tU = (Zk-3 +1)*tS = (Zk-2 +1)*tP = (Zk-1 +1)*tZ = (Zk+1)*tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.
4. Оцінювання роботи
Максимальна кількість балів (100) складається з двох окремих компонентів:
а) правильність, достовірність і якість викладення матеріалів в пояснювальній записці (40 балів);
б) усна відповідь та демонстрація роботи (60 балів).
2. Розподіл балів за видами робіт розрахункової роботи наведений в таблиці 4.1.
Таблиця 4.1. Оцінювання розрахункової роботи
Види робіт
Максимальна к-сть балів
п.а)
п. б)
Теоретичні основи
4
5
Розробка алгоритму
5
15
Достовірність і повнота обчислень
5
10
Розробка схемних рішень,
8
10
Розробка програмного забезпечення
8
10
Демонстрація програми
-
10
Якість і повнота оформлення текстових матеріалів ПЗ
10
-
Сума балів
40
60
Висновки
В наведених методичних вказівках детально описані принципи моделювання паралельних обчислювальних процесів. Основна увага приділена задачі паралельного виконання операцій над матрицями та векторами.
В матеріалах наведені вимоги та варіанти курсових робіт, сформовані вимоги до змісту, оформлення курсових робіт, система їх оцінювання.
Оскільки даний напрямок досліджень постійно розвивається, в Додатках до методичних вказівок навели Internet-ресурси звідки можна почерпнути багато нового в організації паралельної роботи та деякі теоретичні виклади, котрі забезпечать можливість кращого виконання розрахункової роботи.
Література
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб: БХВ-Петербург, 2002.
Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.:Мир, 1991.
Программирование на параллельных вычислительных системах: Пер с англ./Под ред. Р.Бэбба.М.:Мир, 1991.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник
22.03.2018 19:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора