- •Методичні вказівки
- •"Паралельні та розподілені обчислення"
- •М.Кривий Ріг
- •Основні вимоги та загальні методичні вказівки до виконання лабораторних робіт
- •Лабораторна робота №1 Тема: «Імітація процесу розпаралелювання обчислення суми, добутку, матриць та знаходження коефіцієнтів характеристичного поліному»
- •Концепція необмеженого паралелізму
- •Приклад:
- •Приклад виконання задачі для імітації розпаралелення процесу додавання двох матриць 2х2
- •Звіт повинен містити:
- •Контрольні питання:
- •Лабораторна робота №2 Тема: «Розпаралелювання обчислення суми десяти чисел»
- •Хід роботи
- •Для восьми чисел:
- •Для дев’яти чисел:
- •Особливості програмного інтерфейсу потоків
- •Створення потоків у Win32 арі
- •Завершення потоків у Win32 арі
- •Приєднання потоків у Win32 арі
- •Приклад програми для знаходження суми 8-ми чисел за допомогою процесів без розпаралелення
- •Звіт повинен містити:
- •Контрольні питання:
- •Лабораторна робота №3 Тема: «Розпаралелювання обчислення суми, добутку матриць та знаходження коефіцієнтів характеристичного поліному»
- •Приклад виконання задачі розпаралелювання процесу додавання двох матриць 2х2
- •Звіт повинен містити:
- •Контрольні питання:
- •Лабораторна робота №4 Тема: «Розпаралелювання процесу сортування масивів даних»
- •Теоретичні відомості Мютекси
- •Правила спрощеного паралелізму
- •Приклад програми процесу сортування масиву даних
- •Звіт повинен містити:
- •Контрольні питання:
- •Приклад виконання програми
- •Звіт повинен містити:
- •Контрольні питання:
- •Література
- •Додаток а
- •"Паралельні та розподілені обчислення"
- •6.050102 «Комп’ютерні системи та мережі»
Звіт повинен містити:
Тему, мету та завдання роботи.
Схему алгоритму розпаралелення.
Блок – схему програми.
Листинг програми.
Порядок виконання роботи з описом усіх дій.
Контрольні питання:
Що таке процес?
назвіть основні параметри процесу?
Які види процесів ви знаєте?
Що таке блок керування процесом?
Що таке пріорітет процесу? Для чого він потрібний?
В яких станах можуть знаходитися процеси?
Що відбувається при породженні процесу?
Поясніть стан готовності процесу?
назвіть можливі варіанти зміни стану процесу, який зараз виконується процесором?
Що таке блокування процесу? В яких випадках відбувається блокування процесу?
Що відбувається при завершенні процесу?
В яких випадках відбувається завершення процесу?
Що таке тупіковий стан процесу? Як уникнути тупіків?
Як створити процес (потік)?
Як блокувати процес (потік) на заданий час?
Як блокувати процес (потік) до настання певної події?
Що таке функції очікування? Які типи функцій очікування ви знаєте?
Як завершити процес (потік)?
Лабораторна робота №3 Тема: «Розпаралелювання обчислення суми, добутку матриць та знаходження коефіцієнтів характеристичного поліному»
Мета роботи: ознайомитися з принципами взаємодії процесів (потоків) на прикладі розпаралелювання обчислення суми, добутку матриць та знаходження коефіцієнтів характеристичного поліному
Задача
Задано матриці (22) А, В, D. Скласти блок-схеми і програму алгоритму розпаралелювання суми та добутку матриць А і В, а також обчислення коефіцієнтів характеристичного поліному матриці D. Алгоритм і програму складати за умови, що є від 3 до 12 процесорів згідно варіанту (див. таблицю 3.1). Розрахувати ширину, висоту, ефективність та прискорення паралельного алгоритму.
Таблиця 3.1 – Варіанти завдання
№ варіанту |
Кількість процесорів |
1 |
12 |
2 |
11 |
3 |
10 |
4 |
9 |
5 |
8 |
6 |
7 |
7 |
6 |
8 |
5 |
9 |
4 |
10 |
3 |
Приклад виконання задачі розпаралелювання процесу додавання двох матриць 2х2
Листинг програми
#include <windows.h> //Підключення бібліотек
#include <process.h>
#include <iostream.h>
#include <conio.h>
#include <vcl.h>
int number1 = 9,number2 = 1,numb=0; //Змінні
int a1,b1;
unsigned tid;
HANDLE hThreads[10],Thread[3];
DWORD res;
char *array[100];
int mem[12],a[4],b[4],i=0,j=0,k=0;
unsigned __stdcall Sum( void * num) // Функція потоку
{ k+=1;
mem[k]=a1+b1;
return 0;
};
unsigned __stdcall Umn( void * num) // Функція потоку
{ k+=1;
mem[k]=a1*b1;
cout<<mem[k]<<endl;
return 0;
};
int main()
{ SetConsoleOutputCP(1251); //Використання кодування 1251
cout<<"vvedite massiv A\n"; //Ініціалізація масиву А
for (i=0;i<4;i++){
cin>>a[i];
}
cout<<"vvedite massiv B\n"; //Ініціалізація масиву В
for (i=0;i<4;i++){
cin>>b[i];
}
cout<<"A"; //Виведення масиву А
cout<<endl;
for (i=0;i<4;i++){
cout<<a[i]<<"\t";
if (i==1) cout<<endl;
}
cout<<endl;
cout<<"B"; //Виведення масиву В
cout<<endl;
for (i=0;i<4;i++){
cout<<b[i]<<"\t";
if (i==1) cout<<endl;
}
cout<<endl;
a1=a[0];b1=b[0];
//Створення потоків, що виконують функції процесорів
Thread[0] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number1, 0, &tid);
Sleep(10);
a1=a[1];b1=b[2];
Thread[1] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
a1=a[2];b1=b[0];
Thread[2] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
a1=a[3];b1=b[2];
Thread[3] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
//Очікування завершення останнього потоку
if (WaitForSingleObject(Thread[3], INFINITE) != WAIT_FAILED) {
cout<<"Потоки завершили виконання" <<endl;}
//Завершення потоків
CloseHandle(Thread[0]);
CloseHandle(Thread[1]);
CloseHandle(Thread[2]);
CloseHandle(Thread[3]);
a1=a[0];b1=b[1];
Thread[0] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number1, 0, &tid);
Sleep(10);
a1=a[1];b1=b[3];
Thread[1] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
a1=a[2];b1=b[1];
Thread[2] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
a1=a[3];b1=b[3];
Thread[3] = (HANDLE)_beginthreadex(NULL, 0, Umn, (void *)++number2, 0, &tid);
Sleep(10);
if (WaitForSingleObject(Thread[3], INFINITE) != WAIT_FAILED) {
cout<<"Потоки завершили виконання" <<endl;}
CloseHandle(Thread[0]);
CloseHandle(Thread[1]);
CloseHandle(Thread[2]);
CloseHandle(Thread[3]);
a1=mem[1];b1=mem[2];
Thread[0] = (HANDLE)_beginthreadex(NULL, 0, Sum, (void *)++number1, 0, &tid);
Sleep(10);
a1=mem[5];b1=mem[6];
Thread[1] = (HANDLE)_beginthreadex(NULL, 0, Sum, (void *)++number2, 0, &tid);
Sleep(10);
a1=mem[3];b1=mem[4];
Thread[2] = (HANDLE)_beginthreadex(NULL, 0, Sum, (void *)++number2, 0, &tid);
Sleep(10);
a1=mem[7];b1=mem[8];
Thread[3] = (HANDLE)_beginthreadex(NULL, 0, Sum, (void *)++number2, 0, &tid);
Sleep(10);
if (WaitForSingleObject(Thread[3], INFINITE) != WAIT_FAILED) {
cout<<"Потоки завершили виконання" <<endl;}
CloseHandle(Thread[0]);
CloseHandle(Thread[1]);
CloseHandle(Thread[2]);
CloseHandle(Thread[3]);
//Виведення результату
Sleep(100);
for (i=9;i<13;i++){
cout<<mem[i]<<"\t";
if (i==10) cout<<endl;
}
getch();
return 0;
}
Дана програма виконує знаходження добутку матриць, в якості процесорів використовуючи потоки. Використано такі змінні:
12 комірок памяті — змінні mem[8];
4 процесори Thread[0-3];
лічильники i,j;
масиви a[4],b[4].
Рисунок 3.1 – Схема розпаралелення процесу
На рисунку 3.1 показано процес розпаралелювання. В першому та другому ярусі всі чотири процесори виконують функцію множення, в третьому — додавання. Як видно з рисунку при виконанні задачі не виникає конфліктів в пам’яті.
На рисунку 3.2 проілюстровано виконання програми.
В даній програмі виконуються наступні пункти для кожного ярусу:
Створюємо потоки Thread[N] = (HANDLE)_beginthreadex(NULL, 0, Umn, 0, 0, &tid);
Чекаємо завершення операції (Sleep(10);)
Чекаємо завершення потоків, та закриваємо їх :
if (WaitForSingleObject(Thread[3], INFINITE) != WAIT_FAILED) {
cout<<"Потоки завершили виконання"<<endl;}
CloseHandle(Thread[0]);
CloseHandle(Thread[1]);
CloseHandle(Thread[2]);
CloseHandle(Thread[3]);
Аналогічні операції виконуємо для кожного ярусу (рисунок 3.2).
Програма має дві функції Sum — для для знаходження суми, та Umn — для знаходження добутку потоками. Дані функції імітують команди АЛП.