- •Анотація
- •1. Загальні положення
- •2. Вимоги і варіанти курсових робіт
- •2.1. Паралельне виконання операцій над матрицями і векторами
- •Завданння
- •3. Вимоги до змісту та оформлення пояснювальної записки
- •4. Оцінювання роботи
- •Висновки
- •Література
- •«Паралельні та розподілені обчислення»
- •«Паралельне виконання операцій множення матриць»
- •Додаток б Ресурси Інтернет стосовно паралельних обчислень.
- •Методичні вказівки
2. Вимоги і варіанти курсових робіт
2.1. Паралельне виконання операцій над матрицями і векторами
Пояснювальна записка повинна містити:
Титульний аркуш.
Завдання
Анотацію на двох мовох (англійська та українська)
Вступ
Постановку, формулювання та аналіз завдання.
Загальну граф-схему виконання операції перемноження матриці на матрицю на структурі згідно варіанту на рівні опису формул та функціональних блоків з описом призначення кожного з них.
Розроблену граф-схему виконання операції перемноження матриці згідно з завданням, розгорнутим поясненням її роботи та проведеними необхідними обчисленнями.
Граф-схему алгоритму програмної реалізації та опис роботи програми.
Обґрунтування оптимальності вибраних рішень.
Висновки щодо прийнятих рішень у курсовій роботі.
Перелік літературних джерел.
Допоміжні результати обчислень, схемні рішення, лістинг програми пропонується давати в Додатках.
Завданння
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І номер букви в прізвищі, імені та по-батькові відповідно.
Наприклад студент Петренко Василь Іванович:
n1=1П – П
n2=1І – В
n3=1Б – І
декодування вибраних літер для n1,n2,n3 відбувається на основі таблиці 2.1.
Таблиця 2.1 Декодування літер розмірностей для 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 |
|
|
Згідно з таблицею 2.1 отримаємо такі значення n1,n2,n3:
n1=1П – П=250
n2=1І – В=56
n3=1Б – І=181
Отже маємо матрицю А(250*56) та матрицю В(56*181)
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»- номер букви П.І.Б студента.
Наприклад студент ПетренкоВасильІванович 16b-5b-8b-4b-12b-7b-6b-14b:
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 |
|
|
|
|
|
|
*якщо кількість букв недостатньо то вираз застосовується до послідовності ПІБПІБПІБ.
Отримаємо – ВЕОРИКНЬ**
**якщо присутнє дублювання букв то береться буква яка іде наступною в ПІБ після необхідної.
На основі декодування отриманого набору букв на основі таблиці 2.2 формуємо варіант-стовпець
Таблиця 2.2 Кодування букв
А -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 - 00011100
В отриманій двійковій матриці одиниці що розташовані на головній діагоналі замінюємо на 0.
11001011 01001011
10101011 10101011
11111010 11011010
01011101 01001101
01011011 => 01010011
00101111 00101011
10000110 10000100
00011100 00011100
Отримана матриця розміру 8*8 є матрицею зв’язків орієнтованого графу, вершини якого це процесори а напрямлені дуги це напрямлені лінії зв’язку між процесорами. На основі цієї матриці будується відповідний їй граф що характеризує конкретну 8-ми процесорну систему (структуру) із напрявленими зв’язками між вершинами.
3.Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, співвідношення часових параметрів та тип початкового завантаження визначаються за правилами:
3.1. Тип початкового завантаження даних type:
, де Zi цифри номера залікової книжки, n=1..k, де k – кількість цифр номера залікової книжки.
КІ-41 … КІ-46: type=1(спільна пам’ять),type=2(через один процесор), type=3(розподілена пам’ять).
3.2. Співвідношення часових параметрів tU,tS,tP,tZ,tW:
tU – час виконання однієї операції множення;
tS - час виконання однієї операції сумування;
tP - час виконання однієї операції пересилання даних між процесорами;
tZ - час виконання операції завантаження одних даних;
tW - час виконання операції вивантаження одних даних.
КІ-41 … КІ-46 :
tU=(Zk-3 +1)tS=(Zk-2 +1)tP=(Zk-1 +1)tZ=(Zk+1)tW, де Zi відповідна цифра номера залікової книжки, k -кількість цифр в номері залікової книжки.