Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
М Е Т О Д И Ч Н І В К А З І В К И
до курсових робіт з дисципліни “Паралельні та розподілені обчислення”
для студентів базового напряму 6.0915 - “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних обчислювальних машин Протокол № 6 від 03.03.2009 року
Львів - 2011
Методичні вказівки до курсової роботи з дисципліни “Моделювання паралельних обчислювальних процесів” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2011, 52 с.
Укладачі: Є. Ваврук, к.т.н., доцент
І. Грицик, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
Рецензенти: Парамуд Я.С., к. т. н, доцент
Дунець Р.Б., д.т.н., доцент.
Анотація
Дані методичні вказівки укладені у відповідності з робочою навчальною програмою з дисципліни „Паралельні та розподілені обчислення”. В них розглянуті основні питання моделювання задач предметних галузей, паралельних процесів засобами мереж Петрі та паралельного виконання операцій над матрицями і векторами. Вивчення матеріалів, що наведені в методичних вказівках, допоможе студентам набути практичні навики з проектування паралельних процесів.
ЗМІСТ
Вступ
5
1. Загальні положення
5
2. Вимоги і варіанти курсових робіт
5
2.1. Паралельне виконання операцій над матрицями та векторами
5
3. Вимоги до змісту та оформлення пояснювальної записки
9
4. Оцінювання роботи
9
Висновки
10
Література
10
Додатки: Приклад оформлення пояснювальної записки
11
Додаток А. Ресурси Інтернет стосовно паралельних обчислень
11
Вступ
Для розв’язання багатьох задач (прогноз погоди, задачі гідро- і газодинаміки, квантової хімії, астрономії, спектроскопії, біології, ядерної фізики тощо) необхідна висока продуктивність обчислень, висока швидкість передачі інформації по каналах зв’язку та великі об’єми оперативної і постійної пам’яті. Одним з шляхів забезпечення таких вимог є організація паралельних обчислювальних процесів і відповідних технічних засобів їх реалізації.
Причому, ефективність паралельної обробки залежить як від продуктивності комп’ютерів, так і від розмірів і структури пам’яті, пропускної здатності каналів зв’язку, використаних мов програмування, компіляторів, операційних систем, чисельних методів та інших математичних досліджень. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів.
Для скорочення термінів розробки паралельних засобів та дослідження їх роботи використовується моделювання.
Метою виконання курсової роботи є засвоєння основних методів та алгоритмів моделювання паралельних обчислювальних процесів, принципів побудови відповідних структур, набуття початкових практичних навиків проектування таких засобів.
В результаті вивчення курсу студент повинен:
знати: основні методи, алгоритми і засоби паралельного опрацювання інформації, засоби програмування на паралельних структурах, склад апаратних засобів та програмного забезпечення обчислювальних систем з елементами паралельного опрацювання;
вміти: виконувати елементарні вправи з розпаралелення задач та алгоритмів, проводити розрахунки параметрів, моделювати паралельні обчислювальні процеси, проектувати окремі вузли.
1. Загальні положення
Тематика курсової роботи охоплює основні напрямки розвитку паралельних обчислень, а саме:
1. Паралельне виконання операцій над матрицями і векторами.
2. Моделювання задач предметних галузей (див. Вступ). Курсові роботи даного напрямку рекомендується до виконання студентам, які схильні до наукової роботи і планують продовжити навчання в магістратурі.
Вибір теми курсової роботи слід проводити з врахуванням індивідуальних схильностей студента до певного напрямку творчої діяльності.
Студенту пропонується (або він вибирає сам) один з варіантів зазначених в напрямках 1 чи 2. Тему курсової роботи за напрямком 3 пропонує студент і погоджує з викладачем.
2. Вимоги і варіанти курсових робіт
2.1. Паралельне виконання операцій над матрицями і векторами
Пояснювальна записка повинна містити:
Титульний аркуш.
Завдання
Анотацію на двох мовох (англійська та українська
Вступ
Постановку, формулювання та аналіз завдання.
Загальну граф-схему виконання операції перемноження матриці на матрицю на певній структурі на рівні опису формул та функціональних блоків з описом призначення кожного з них.
Розроблену граф-схему виконання операції перемноження матриці згідно з завданням, розгорнутим поясненням її роботи та проведеними необхідними обчисленнями.
Граф-схему алгоритму програмної реалізації та опис роботи програми.
Обґрунтування оптимальності вибраних рішень.
Висновки щодо прийнятих рішень у курсовій роботі.
Перелік літературних джерел.
Допоміжні результати обчислень, схемні рішення, лістинг програми пропонується давати в Додатках.
Завданння
1.Задаються дві матриці А (розмірністю n1*n2) та В (розмірністю n2*n3) :
n1=1П, n2=1І, n3=1Б – КІ-41
n1=3П, n2=2І, n3=4Б – КІ-42
n1=2П, n2=2Б, n3=1І – КІ-43
n1=5Б ,n2=3П, n3=2І – КІ-44
n1=6Б, n2=1П, n3=3І – КІ-45
n1=3І, n2=2П, n3= 4Б – КІ-46
де nП, nБ та nІ номер букви в прізвищі, імені та по-батькові відповідно.
Наприклад студент Петренко Василь Іванович з групи КІ-41:
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»- номер букви П.І.Б студента.
Наприклад студент ПетренкоВасильІванович з групи КІ-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
*якщо кількість букв недостатньо то вираз застосовується до послідовності ПІБПІБПІБ.
Отримаємо – ВЕОРИКНЬ**
**якщо присутнє дублювання букв то береться буква яка іде наступною в ПІБ після необхідної.
На основі декодування отриманого набору букв на основі таблиці 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 - 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 – кількість цифр номера залікової книжки.
КІ-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 -кількість цифр в номері залікової книжки.
3. Вимоги до змісту та оформлення пояснювальної записки
В пояснювальній записці повинні бути відображені:
теоретичні аспекти (проблеми);
результати розроблення відповідної структури (структурна, функціональна схеми), програмного забезпечення (граф-схема і лістинг програми), виконані згідно з вимогами нормативних документів;
обчислення основних параметрів;
перспективи і шляхи покращення запропонованих технічних рішень.
Орієнтовні вимоги до змісту Пояснювальної записки курсової роботи наведені в таблиці 3.1.
Таблиця 3.1. Вимоги до пояснювальної записки до курсової роботи
№
п/п
Орієнтована назва розділу
Орієнтований зміст розділу
Орієнтовна
кількість сторінок
(мінімум)
1
Титульна сторінка
Назва теми роботи, № варіанту
1
2
Завдання до роботи
1
3
Анотація
Коротко наведені результати роботи
1
4
Зміст
1
5
Вступ
Значення, необхідність роботи
1
6
Теоретичний розділ
Область застосування заданої функції (алгоритму), особливості її реалізації
3
7
Аналіз (розробка) граф-схеми виконання заданої функції
Результати розробки граф-схеми виконання заданої функції (повинні бути наведені граф-схема та опис її роботи; аргументовано вибір типу обробки)
3
8
Розрахунковий розділ
6
9
Розробка функціональної схеми
Результати розробки структурної і функціональної схеми роботи (повинні бути наведені структурна і функціональна схеми та їх опис)
3
10
Розробка програми виконання заданої функції (алгоритму)
Блок схема, опис і лістинг програми на мові високого рівня або на асемблері. Порахований час виконання програми. При великому обсязі лістингу – навести його в Додатку
4
11
Висновки
Навести чисельні значення отриманих результатів. Перспективи і шляхи покращення запропонованих технічних рішень.
1
12
Література
Перелік використаної літератури
1
13
Додатки
Лістинг програми (див п.10)
-
Основні вимоги до оформлення:
- формат аркушів А4;
- текстовий редактор Word (шрифт – 14; інтервал – 1,5; гарнітура – TimesNewRomanCyr);
- формули Equation 3 або 4;
відступи, мм:
зліва, 25;
справа 10;
зверху, знизу 20.
Решту матеріалів пояснювальної записки повинні відповідати вимогам нормативних документів.
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.
Бройнль Т. Паралельне програмування: Початковий курс: Навчальний посібник. – К.:Вища школа.,1997.
Воеводин В.В. Математические основы параллельных вычислений.- М.: Изд-во МГУ, 1991.
Векторизация программ: теория, методы, реализация: Пер. с англ. и нем. /Под ред. Г.Д.Чинина. - М:. Мир, 1991.
Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999
С. Немнюгин, О.Стесик Параллельное программирование для многопроцессорных вычислительных систем. – СПб: БХВ-Петербург, 2002.
Питерсон Дж. Теория сетей Петри і моделирования систем: Пер. с англ. -М.: Мир, 1984. -264 с., ил.
10. http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
11. http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
12. http://www.hpc.nw.ru – Високопродуктивні обчислення.
13. Організація паралельних обчислень : Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 70 с.
14. Довідники з математики
Приклади оформлення матеріалів
пояснювальної записки
Додаток А
Паралельне виконання операцій множення матриць
---------------------------------------------------------------------------------------------------------------------
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Інститут комп’ютерних технологій, автоматики та метрології
Кафедра ЕОМ
КУРСОВА РОБОТА
з дисципліни:
«Паралельні та розподілені обчислення»
на тему:
«Паралельне виконання операцій множення матриць»
Варіант №
Виконав: студент групи .
.
Перевірив: .
Львів -20хх
------------------------------------------------------------------------------------------------------------------------
Додаток Б
Ресурси Інтернет стосовно паралельних обчислень.
http://www.globus.org – Побудова метакомп’ютера.
http://www.gridforum.org– Побудова метакомп’ютера.
http://www.top500.org – Характеристики 500 найпотужніших комп’ютерів в світі.
http://www.mpiforum.org – Повний варіант описів стандартів МРІ.
http://www.keldysh.ru.norma – Опис системи програмування НОРМА.
http://www.citforum.ru – Сервер інформаційних технологій.
http://www.parallel.ru – Інформаційно-аналітичний центр з паралельних обчислень.
http://www.csa.ru – Інститут високопродуктивних обчислень і баз даних.
http://www.hpc.nw.ru – Високопродуктивні обчислення.
http://www.epm.ornl.gov/pvm/ - інформація про PVM.
http://www.beowulf.org – Інформація про кластери.
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до курсової роботи з дисципліни “Моделювання паралельних обчислювальних процесів” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" с.
Укладачі: Ваврук Євгеній Ярославович
Грицик Іван Вікторович
Редактор
Комп’ютерне верстання
Здано у видавництво . Підписано до друку
Формат 70х100/16. Папір офсетний. Друк на різографі
Умовн. друк. арк. Обл..-вид. арк..
Тираж прим. Зам..
Видавництво Національного університету “Львівська політехніка”
Реєстраційне свідоцтво ДК №751 від 27.12.2001 р.
Поліграфічний центр Видавництва
Національного університету “Львівська політехніка”
Вул. Ф. Колесси, 2. Львів, 79000
06.03.2013 23:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора