Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Ужгородський національний університет
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Курсова робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра комп’ютерних систем та мереж
КУРСОВА РОБОТА
з дисципліни
«Паралельні та розподілені обчислення»
напрям підготовки 6.050102 – «Комп’ютерна інженерія»
ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД «УЖГОРОДСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»
Інженерно-технічний факультет
Кафедра комп’ютерних систем та мереж
ТЕХНІЧНЕ ЗАВДАННЯ
до курсової роботи з дисципліни
«Паралельні та розподілені обчислення»
студента 4 курсу
Сірка Ю.Ю
Тема роботи: Розробка програмного забезпечення для паралельної обчислювальної системи із використанням мови Java та моніторів.
Вхідні дані(Варіант 19):
22 варіант
Математична функція
Процесори
1
2
3
4
МА=МВ*(МС*МТ)
МВ, МС,МТ
-
МА
-
30 варіант
Сучасні ПОС із локальною пам’яттю
Вихідні дані:
Розроблена програма з використанням моніторів на мові Java в якій виконується обчислення заданої математичної функції для різних розмірів матриці в чотирипроцесорній ПОС із спільною пам'яттю.
Зміст пояснювальної записки:
Вступ відображає сучасний стан розвитку та викорис тання ПОС, особливостей розробки та використання програмного забезпечення для ПОС.
Аналітична частина записки містить:
аналіз структурної організації сучасних ПОС із прикладами реальних
систем та їх характеристик;
аналіз системного і прикладного програмного забезпечення сучасних ПОС;
Розрахунково-проектувальна частина містить:
- опис реальної ПОС, для якої необхідно розробити програм не забезпечення;
- аналіз вхідного математичного завдання (векторно-матрич ної задачі) на внутрішній паралелізм з визначенням коефіцієнтів прискорення та ефективності при використанні концепції необмеженого паралелізму;
- побудову паралельного математичного алгоритму для зада ної математичної задачі;
- визначення точок синхронізації потоків;
- розробку алгоритмів для кожного паралельного протоку;
- побудову схеми взаємодії потоків;
- розробку програми;
- налагодження програми;
- отримання і аналіз результатів роботи програми.
Дослідницька частина містить:
- опис досліджень, які були виконано з метою визначення ефективності розробленого програмного забезпечення;
- результати проведених експериментальних досліджень у вигляді таблиць та графіків;
- висновки за результатами досліджень.
У висновках узагальнюються основні результати курсової роботи.
Список літератури включає літературні джерела, що були використані при виконанні курсової роботи і на які є посилання в тексті пояснювальної записки. Список літератури оформлений у відповідності до вимог стандарту.
Додатки містять лістинг програми.
Завдання видано____________
Термін здачі роботи_________
Керівник__________________
ЗМІСТ
1. АНАЛІТИЧНА ЧАСТИНА. 7
1.1. Паралельні обчислювальні системи і їх класифікація 7
1.2. ПОС із локальною пам'яттю. 8
1.3. Сучасні ПОС із локальною пам'яттю. 9
2. РОЗРАХУНКОВО-ПРОЕКТУВАЛЬНА ЧАСТИНА. 11
Етап 1. Побудова паралельного алгоритму. 11
Етап 2. Розроблення алгоритмів процесів. 11
Етап 3. Розробка структурної схеми взаємодії задач. 12
Етап 4. Розробка програми. 13
3. ДОСЛІДНИЦЬКА ЧАСТИНА. 17
ВИСНОВКИ 20
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 21
ДОДАТКИ 22
ВСТУП
Прогрес сучасних галузей техніки, технологій та біотехнологій, технологій довкілля залежить від рівня теорії та практичної реалізації методів проектування автоматизованих технічних об’єктів, технологічних установок та ліній, що визначаються як складні динамічні системи (ДС). Динамічними системами прийнято називати системи різної фізичної природи, що мають цілеспрямовані зміни фізичних параметрів у часі. До динамічних систем відносяться керовані механізми та машини, технологічні установки, виробництва та процеси у них, транспортні об’єкти, енергетичні установки та системи, гідравлічні, пневматичні, електричні, газорозподільні та вентиляційні мережі та ін. Наприкінці 90-х років моделювання стало вирішальним фактором забезпечення високої якості проектування динамічних систем з зосередженими та розподіленими параметрами, розширилося коло об’єктів моделювання – від “традиційних” технічних систем до керованих біотехнологічних процесів та систем.
Центральною проблемою проектів ДС є гарантування новизни та якості проектних рішень. У переліку факторів безумовного вирішення цієї проблеми чільне місце займають методи та засоби моделювання динамічних систем, які можуть використовуватись на всіх етапах проекту ДС від формулювання техніко-економічних вимог до випробувань та початку експлуатації. Основи такого модельного супроводження проектів ДС були в значній мірі відпрацьовані на аналогових та аналого-цифрових засобах моделювання. З середини 80-х років почався інтенсивний перехід до засобів цифрового моделювання: розроблені та реалізовані на всіх типах цифрових ЕОМ блоково - та рівняння-орієнтовані мови моделювання ДС, швидко розвивається апаратна база моделювання – персональні та супер- ЕОМ, паралельні обчислювальні системи SIMD та MIMD-архітектур. Саме останні покликані компенсувати відсутність надпотужних паралельних процесорів в моделюючих комплексах, які свого часу відіграли вирішальну роль у розробці аерокосмічних та технологічних ДС. Застосування паралельних ресурсів потребує нової системної організації засобів моделюван-
ня ДС, відкриває принципово нові можливості побудови моделей реальної складності та модельної підтримки проектів ДС, призводить до більш високих вимог до системотехнічної та системопрограмної організації засобів моделювання та інтерфейсів користувача.
Перспективним напрямком удосконалення та розвитку засобів моделювання є широке застосування паралельних обчислювальних систем до побудови моделюючих середовищ.
1. АНАЛІТИЧНА ЧАСТИНА.
1.1. Паралельні обчислювальні системи і їх класифікація
Паралельні обчислювальні системи - це фізичні комп'ютерні, а також програмні системи, що реалізують тим чи іншим способом паралельну обробку даних на багатьох обчислювальних вузлах(рис.1).
Рис.1.Паралельна обчислювальна система
Стиль програмування, заснований на паралелізмі завдань, має на увазі, що обчислювальне завдання розбивається на декілька відносно самостійних підзадач і кожен процесор завантажується своєю власною підзадачею.
Класифікація паралельних обчислювальних систем:
Загальна класифікація архітектур ЕОМ за ознаками наявності паралелізму в потоках команд і даних. Була запропонована в 70 -ті роки Майклом Флінном (Michael Flynn). Все розмаїття архітектур ЕОМ за Фліном зводиться до чотирьох класів:
· ОКОД - Обчислювальна система з одиночним потоком команд і одиночним потоком даних(SISD, Single Instruction stream over a Single Data stream).
· ОКМД - Обчислювальна система з одиночним потоком команд і множинним потоком даних(SIMD, Single Instruction , Multiple Data) .
· МКОД - Обчислювальна система зі множинним потоком команд і одиночним потоком даних(MISD , Multiple Instruction Single Data) .
· МКМД - Обчислювальна система зі множинним потоком команд і множинним потоком даних(MIMD , Multiple Instruction Multiple Data) .
Типовими представниками SIMD є векторні архітектури. До класу MISD ряд дослідників відносить конвеєрні ЕОМ , однак це не знайшло остаточного визнання , тому можна вважати , що реальних систем - представників даного класу не існує. Клас MIMD включає в себе багатопроцесорні системи , де
процесори обробляють множинні потоки даних.
Ставлення конкретних машин до конкретного класу сильно залежить від точки зору дослідника. Так, конвеєрні машини можуть бути віднесені і до класу SISD ( конвеєр - єдиний процесор) , і до класу SIMD (векторний потік даних з конвеєрним процесором ) і до класу MISD ( безліч процесорів конвеєра обробляють один потік даних послідовно ) , і до класу MIMD - як виконання послідовності різних команд (операцій щаблів конвеєра ) на множинним скалярним потоком даних ( вектором ) .
1.2. ПОС із локальною пам'яттю.
КС із локальною пам'яттю – це система в якій вузол системи містить і процесор і локальну пам’ять, для взаємодії вузлів використовують систему зв’язків, яка зв’язує вузли за допомогою лінків(рис.2). Така система називається моделлю взаємодії процесів, що грунтуються на посиланні повідомлень.
Рис.2 . КС із локальною пам’яттю
Системи з локальною пам’яттю належать до категорії тісно зв’язаних систем, які ставлять високі вимоги до пропускної здатності системи зв’язків. Реалізацію повного зв’язку процесорів у системах з розподіленою пам’яттю можна забезпечити тільки для невеликої кількості процесорів. Для того щоб уникнути цю проблему можна, використовуючи різні топології(кільце, зірка, решітка та ін.). Кожна з цих структур характеризується кількістю процесорів, кількістю зв’язків між вузлами, степенем вузла, який задає кількість зв’язків цього вузла та діаметром системи, який визначає відстань між двома найбільш віддаленими процесорами системи.
Обмін даними в цих КС між процесорами відбувається через пересилання повідомлень(link). Така схема має ряд переваг в порівнянні з системами, побудованими на основі спільної пам’яті, а саме: можливість побудови систем необхідного виробництва і збільшення їх потужності за рахунок установки додаткових процесорів, низька вартість.
КС із локальною пам'яттю можуть бути легко побудовані з використанням будь-яких однопроцесорних або багатопроцесорних систем на основі спільної пам’яті об’єднаних мережею. Але ефективність таких комп’ютерних систем залежить від ефективності програмного забезпечення.
1.3. Сучасні ПОС із локальною пам'яттю.
Комп'ютери з розподіленою пам'яттю – це комп’ютери в яких кожен процесор має доступ лише до власної(локальної) пам’яті. Доступ до віддаленої пам’яті виконується за допомогою обміну повідомленнями. Процесор може звертатися до локальної пам'яті, може посилати й одержувати повідомлення. Повідомлення використовуються для читання і запису віддалених блоків пам'яті(блоків локальної пам’яті іншого процесора).
До комп'ютерів з розподіленою пам'яттю належать комп’ютери з масово-паралельною архітектурою(MPP)(рис.3). Ця система складається з однорідних обчислювальних вузлів, що включають:
один чи декілька центральних процесорів (RISC);
локальну пам'ять;
комунікаційний процесор чи мережевий адаптер;
жорсткі диски чи інші пристрої введення/виведення.
Рис.3. КС з масово-паралельною архітектурою
До системи можуть бути додані спеціальні вузли введення/виведення і управляючі вузли.
ПОС з локальною пам'яттю: IBM RS/6000 SP2, Intel PARAGON/ASCIRed, SGI / CRAY T3E, Hitachi SR8000, системи Parsytec.
Загальне число процесорів у реальних системах досягає декількох тисяч (ASCI Red, Blue Mountain).
Операційна система для масово-паралельної архітектури є двох типів:
повноцінна операційна система працює тільки на головному вузлі, на інших вузлах працює “урізаний” варіант операційної системи (Cray T3E);
на кожному вузлі працює повноцінна операційна система(IBM RS/6000 SP із ОС AIX).
2. РОЗРАХУНКОВО-ПРОЕКТУВАЛЬНА ЧАСТИНА.
Етап 1. Побудова паралельного алгоритму.
Паралельний алгоритм операції можна подати у вигляді:
Спільним ресурсом є матриці МВ і МС, відносно яких необхідно розв’язувати завдання взаємного виключення під час формування кінцевого результату.
Етап 2. Розроблення алгоритмів процесів.
Рис.4.Структурна схема чотирипроцесорної системи
Задача Т1 Точки синхронізації
Введення МВ, МС, МТ.
Сигнал задачам Т2-Т4 про завершення введення. S2,3,4-1
Копія МС і МВ. КД
Обчислення .
Сигнал задачі Т3 про завершення обчислення. S3-2
Задача Т2 Точки синхронізації
Чекати на введення в Т1. W1-1
Копія МС і МВ. КД
Обчислення Сигнал задачі Т3 про завершення обчислення. S3-1
Задача Т3 Точки синхронізації
Чекати на введення в Т1. W1-1
Копія МС і МВ. КД
Обчислення .
Чекати на завершення обчислень в Т1, Т2, Т4. W1,2,4-2
Виведення результату МА.
Задача Т4 Точки синхронізації
Чекати на введення в Т1. W1-1
Копія МС і МВ. КД
Обчислення
Сигнал задачі Т3 про завершення обчислення. S3-1
Етап 3. Розробка структурної схеми взаємодії задач.
Цей етап пов’язаний з розробкою структури класу(монітора), за допомогою якого реалізується взаємодія задач. Клас Data включає чотири захищені(private) поля: F1, F2, MB, MC а також набір методів для роботи(рис. ).
Рис.5.Структура монітора
Клас Data містить такі методи:
Signal1() – сигнал про завершення введення даних.
Signal2() – сигнал про завершення обчислень.
Wait1() – очікування завершення введення даних.
Wait2() – очікування завершення обчислень.
Copy_MB() – для копіювання спільного ресурсу МВ.
Copy_MC() – для копіювання спільного ресурсу МС.
Write_MB() – для запису спільного ресурсу МВ.
Write_MC() – для запису спільного ресурсу МС.
Етап 4. Розробка програми.
Програма складається із шести класів: головний клас(Main.java), клас-монітор(Data.java), і чотири класи процесів(Thread1, Thread2, Thread3, Thread4).
Всі класи описані в пакеті kyrsova.
В головному класі створюються 4 об’єкти класів процесів і один об’єкт класу монітора. Також в цьому класі підключено бібліотеку Date(import java.util.Date) для визначення часу виконання програми. Метод getTime() класу Date повертає кількість мілісекунд, які пройшли від 1 січня 1970 року. Різниця між двома об’єктами класу Date створеними на початку і в кінці головної функції буде часом виконання функції в мілісекундах. Щоб перевести час в секунди потрібно отриману різницю поділити на 1000.Наприклад:
Date tm1=new Date();
//код для якого знаходимо час виконання
Date tm2=new Date();
System.out.println("Time: "+((double)tm2.getTime()-(double)tm1.getTime()/1000);
В класі монітора(Data) описані всі змінні математичної функції(матриці МА, МВ, МС, МТ). Матриці МВ і МС є спільним ресурсом і тому описані з ключем доступу private, інші матриці і змінні описані із ключем доступу public. Це зроблено для того, шоб доступ до спільного ресурсу можна було б здійснювати тільки через методи даного класу. Методи описані із ключовим словом synchronized, що дозволяє використовувати метод в даний момент часу лише одному процесу, а всі зміни які в ньому виконуються буде видно у всіх інших процесах.
Наприклад:
public synchronized void Write_MC(int[][] el) {
MC=el.clone(); //метод копіює матрицю з допомогою вбудованої
} //функції clone()
Також в класі Data описані такі змінні, як: кількість процесів(Р), розмірність матриць(N), змінна H, яка визначає яку кількість елементів матриці буде обраховувати кожен процес(H=N/P), а також змінні F1 і F2, які визначають закінчилися введення/обчислення в процесах чи ні. Всі змінні ініціалізуються в конструкторі класу:
public Data(){
N=1800; P=4;
H=N/P;
MA=new int[N][N];
MT=new int[N][N];
MC=new int[N][N];
MB=new int[N][N];
F1=F2=0;
}
Методи Signal1, Signal2 – це сигнали, які посилають процеси. Signal1 – це
сигнал про закінчення введення матриць. Цей сигнал посилає перший процес(Thread1). Signal2 – це сигнал про закінчення обчислень(використовують Thread1, Thread2, Thread4).
public synchronized void signal1() {
notifyAll();
F1++;}
public synchronized void signal2() {
notifyAll();
F2++;}
Методи Wait1 і Wait2 – це методи очікування завершення введення/обчислення даних. Вони призупиняють роботу процесу в якому використовуються поки не буде закінчено введення/обчислення даних.
public synchronized void wait1() {
try {
while (F1 != 1) wait();
} catch (Exception e) {
System.out.println(e);}
}
public synchronized void wait2() {
try {
while (F2!=3) wait();
} catch (Exception e) {
System.out.println(e);
}
}
Методи Copy_MB, Copy_MC, Write_MC, Write_MB забезпечують копіювання і запис спільних ресурсів, а саме матриць МВ і МС.
public synchronized int[][] Copy_MB() {
return MB.clone();
}
public synchronized int[][] Copy_MC() {
return MC.clone();
}
public synchronized void Write_MC(int[][] el) {
MC=el.clone();
}
public synchronized void Write_MB(int[][] el) {
MB=el.clone();
}
В класах процесів(Thread1 – Thread4) описані об’єкти класу монітора(d1 – d4) в які передається об’єкт монітора описаний в головному класі, а також матриці в які копіюються спільні ресурси(матриці МВ і МС).
Data d1 = new Data();
int MB1[][],MC1[][],R[][];
Всі змінні ініціалізуються в конструкторі.
public Thread1(Data d) {
d1 = d;
MB1 = new int[d1.N][d1.N];
MC1 = new int[d1.N][d1.N];
R = new int[d1.N][d1.N];}
Кожен клас процесу наслідує клас Thread(extends Thread) і перевизначає метод run() який містить код, що повинен виконуватись при запуску процесу.
Процес запускається з допомогою методу start() в головному класі. В кожному процесі виконується обчислення четвертої частини матриці, а саме H рядків матриці. Отже, Thread1 обраховує від 0 до H-1 стовпців, Thread2 від H до 2*H-1 стовпців, Thread3 від 2*H до 3*H-1, Thread4 від 3*H до 4*H-1. Наприклад:
Обчислення перших H стовпців матриці(Thread1).
for (int i = 0; i < d1.H; i++) {
for (int j = 0; j < d1.N; j++) {
R[i][j] = 0;
for (int k = 0; k < d1.N; k++) {
R[i][j] += MC1[i][k] * d1.MT[k][j];
}
}
for (int j = 0; j < d1.N; j++) {
d1.MA[i][j] = 0;
for (int k = 0; k < d1.N; k++) {
d1.MA[i][j] += R[i][k] * MB1[k][j];
}
}
}
3. ДОСЛІДНИЦЬКА ЧАСТИНА.
В дослідницькій частині виконано дослідження, яке пов’язане з визначенням часу виконання паралельної програми в ПОС. Для цього в головному класі підключено бібліотеку Date для обчислення часу виконання програми. На початку і в кінці класу створено об’єкти цього класу, а між ними запускаються процеси для яких визначається час виконання. Для того, щоб час не було обчислено скорше ніж закінчать свою роботу всі процеси використано метод join() – очікування закінчення роботи процесу.
try{
t1.join();
t2.join();
t3.join();
t4.join();
}catch(Exception e){
System.out.println("Error: "+e);
}
В першій таблиці наведено час виконання в ПОС із двома ядрами(T2).
Таблиця 1. Час виконання програми в ПОС з двома ядрами
Розмірність матриці
800х800
1000х1000
1200х1200
1800х1800
Час виконання(с.)
10,64
10,837
10,633
10,841
10,816
10,848
10,907
10,861
10,768
10,963
25,44
25,515
24,855
24,838
24,83
24,928
25,229
24,905
25,284
24,735
50,285
49,438
49,686
49,798
49,792
49,936
49,623
49,887
49,96
49,955
200,651
204,426
203,265
208,327
199,902
200,516
199,98
201,614
199,962
201,372
Середнє значення
10,9114
25,0559
49,836
202,0015
Для більш точного обчислення коефіціенту прискорення було обраховано час виконання 10 разів для одинакових даних і одинакової кількості елементів і знайдено їхнє середнє значення. Це було зроблено для декількох значень N – розміру векторів або матриць(N = 800, 1000, 1200, 1800).
Також було визначено і середній час виконання програми на одному ядрі(таблиця 2) для таких самих даних і розмірів як і в першій таблиці.
Таблиця 2. Час виконання програми в ПОС з відключеним ядром
Розмірність матриці
800х800
1000х1000
1200х1200
1800х1800
Час виконання(с.)
21,556
21,834
21,314
22,732
21,472
21,109
21,125
21,086
20,833
21,105
49,787
49,097
49,305
49,125
49,114
49,492
49,624
49,067
49,029
49,488
99,13
97,606
97,575
98,013
99,205
98,852
99,742
97,434
98,264
98,744
401,289
395,637
401,302
400,89
402,154
398,614
400,12
399,97
401,102
401,451
Середнє значення
21,4166
49,3128
98,4565
400,2529
Коефіцієнт прискорення() обчислюється за формулою , де Т2 – час виконання в ПОС із двома ядрами, а Т1 – час виконання в ПОС із одним ядром. Отже, для матриці розміром N = 800 1,962773, для N = 1000 1,968111, для N = 1200 1,97561, для N = 1800 1,981435. Обрахувавши можна побудувати графік його залежності від кількості елементів матриці(рис. 6).
Рис.6. Поведінка в залежності від розміру матриці Проаналізувавши графік і таблиці можна дійти висновку, що при збільшенні кількості процесорів зменшується час виконання програми тому і збільшиться коефіцієнт прискорення.
Отже, дане програмне забезпечення буде більш ефективним, а саме зменшиться час його виконання на ПОС із двома ядрами в порівнянні із ПОС з одним ядром. Це випливає із значення , яке (2 і показує, що при включенні одного ядра в ПОС час виконання зменшився вдвічі, а це доводить ефективність паралельного виконання програми.
ВИСНОВКИ
Отже, під час виконання курсової роботи було розроблено програмне забезпечення для паралельної обчислювальної системи із використанням моніторів мови Java. Було проведено аналіз структурної організації сучасних ПОС із локальною пам'яттю, аналіз системного і прикладного програмного забезпечення сучасних ПОС, огляд особливостей архітектури ПОС з локальною пам'яттю. Було описано реальну ПОС, для якої розроблювалось програм не забезпечення. Після аналізу вхідного математичного завдання (векторно-матрич ної задачі) на внутрішній паралелізм з визначенням коефіцієнтів прискорення було побудовано паралельний математичний алгоритм для зада ної математичної задачі. Програмне забезпечення було досліджено з метою визначення ефективності його роботи. Результати проведених досліджень описано вище у вигляді таблиць та графіків з метою визначення ефективності роботи програмного забезпечення.
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
Кей С. Хорстманн, Гари Корнелл Java. Библиотека профессионала, том 1. Основы. 9-е издание — М.: «Вильямс», 2013. — 864 с.
В.В.Воеводин, Вл.В.Воеводин - "Параллельные вычисления", издательство "БХВ ",2002
Корнеев В.В. Параллельные вычислительные системы. М.: “Нолидж”, 1999. 320 с.
Джошуа Блох. Java. Эффективное программирование — М.: Лори, 2002. — 224 с.
Любош Бруга. Java по-быстрому: Практический экспресс-курс — М.: Наука и техника, 2006. — 369 с.
С.Немнюгин, О.Стесик, "Параллельное программирование для многопроцессорных вычислительных систем" СПб:, "БХВ-Петербург", 2002
Герберт Шилдт. Java. Полное руководство. Java SE 7. — 8-е изд. — М.: Вильямс, 2012. — 1104 с.
Флэнаган Д. Java в примерах. Справочник, 2-е издание Пер с англ. СПб: Символ-плюс, 2003. 664 с., ил
ДОДАТКИ
09.01.2014 18:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора