Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
ПАРАЛЕЛЬНІ АЛГОРИТМИ МНОЖЕННЯ МАТРИЦІ НА ВЕКТОР
Методичні вказівки до лабораторної роботи № 4 з курсу “Паралельні та розподілені обчислення”
для студентів базового напряму 6.0915 - “Комп’ютерна інженерія”
Затверджено на засіданні кафедри ”Електронні обчислювальні машини” Протокол № _ від 2010 року
Львів – 2010
Паралельні алгоритми множення матриці на вектор: Методичні вказівки до лабораторної роботи № 4 з курсу “Паралельні та розподілені обчислення” для студентів базового напряму 6.0915 - “Комп’ютерна інженерія”/ Укладачі: Є. Ваврук, О. Акимишин – Львів: Національний університет “Львівська політехніка”, 2010, 14 с.
Укладачі: Є. Ваврук, к.т.н., доцент.
О. Акимишин, к.т.н., асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
Рецензенти: Попович Р.Б., к. т. н, доцент
Юрчак І.Ю., к. т. н, доцент
МЕТА РОБОТИ
Ознайомитись з методами організації паралельного множення матриці на вектор та розробити паралельну програму з використанням технології MPI.
ТЕОРЕТИЧНІ ВІДОМОСТІ:
Матриці та операції над ними широко використовуються при математичному моделюванні найрізноманітніших процесів, явищ і систем. Матричні обчислення складають основу багатьох наукових і інженерних розрахунків.
Враховуючи важливість ефективного виконання матричних обчислень багато стандартних бібліотек програм містять процедури для різних матричних операцій. Об'єм програмного забезпечення для операцій над матрицями постійно збільшується - розробляються нові оптимальні структури даних для зберігання матриць спеціального типу (трикутних, стрічкових, розріджених тощо), створюються різні високоефективні машинно-залежні реалізації алгоритмів, проводяться теоретичні дослідження для пошуку швидших методів матричних обчислень.
Будучи обчислювально трудомісткими, матричні обчислення є класичною областю застосування паралельних обчислень. З одного боку, використання високопродуктивних багатопроцесорних систем дозволяє істотно підвищити складність завдань, які розв’язуються. З іншого боку, через своє достатньо просте формулювання матричні операції надають прекрасну можливість для демонстрації багатьох прийомів і методів паралельного програмування.
У даній лабораторній роботі аналізуються методи паралельних обчислень для операції векторно-матричного множення.
1. Принципи розпаралелювання
Для багатьох методів матричних обчислень характерним є повторення одних і тих же операцій для різних даних. Дана властивість свідчить про наявність паралелізму за даними при виконанні матричних обчислень, і, як результат, розпаралелювання матричних операцій зводиться, в більшості випадків, до розбиття оброблюваних матриць між процесорами використовуваної обчислювальної системи. Вибір способу поділу матриць приводить до визначення конкретного методу паралельних обчислень; існування різних схем розподілу даних породжує ряд паралельних алгоритмів матричних обчислень.
Найбільш загальні і широко використовувані способи поділу матриць полягають в розбитті даних на смуги (по вертикалі або горизонталі) або на прямокутні фрагменти (блоки).
1.1. Стрічкове розбиття матриці. При стрічковому (block-striped) розбитті кожному процесору виділяється певна підмножина рядків (rowwise або горизонтальне розбиття) або стовпців (columnwise або вертикальне розбиття) матриці. При такому підході для горизонтального розбиття по рядках, наприклад, матриця A представляється у вигляді (1)
, де (1)
ai = (ai1,ai2,...,ain),
0 <= i < m i-й рядок матриці A (передбачається, що кількість рядків m кратна кількості процесорів p, тобто m = k·p).
Інший можливий підхід до формування смуг полягає в застосуванні тієї чи іншої схеми чергування (циклічності) рядків або стовпців. Як правило, для чергування використовується кількість процесорів p - в цьому випадку при горизонтальному розбитті матриця A приймає вигляд
(2)
1.2. Блокове розбиття матриці. При блоковому (chessboard block) розбитті матриця ділиться на прямокутні набори. Хай кількість процесорів складає p = s·q, кількість рядків матриці є кратним s, а кількість стовпців - кратним q, тобто m = k·s і n = l·q. Представимо початкову матрицю A у вигляді набору прямокутних блоків таким чином (3):
(3)
де Aij - блок матриці, що складається з елементів:
(4)
При такому підході доцільно, щоб обчислювальна система мала фізичну або, принаймні, логічну топологію процесорних граток з s рядків і q стовпців. При такому розбитті даних, сусідні в структурі граток процесори, обробляють суміжні блоки початкової матриці. Треба зазначити, що і для блокової схеми може бути застосоване циклічне чергування рядків і стовпців.
У лабораторній роботі розглядаються три паралельні алгоритми для множення квадратної матриці на вектор. Кожен підхід заснований на різному типі розбиття початкових даних (елементів матриці і вектора) між процесорами. Розбиття даних міняє схему взаємодії процесорів, тому кожен з представлених методів істотним чином відрізняється від решти.
а) б) в)
Рис. 1. Способи розбиття елементів матриці між процесорами
обчислювальної системи
На рис. 1 схематично неведені способи розбиття матриць між процесорами: а) горизонтальне розбиття, б) вертикальне розбиття та в) блокове розбиття матриці.
2. Постановка задачі
В результаті перемноження матриці А розмірності m х n і вектора b, що складається з n елементів, отримується вектор розміру m, кожен i-й елемент якого є результат скалярного множення i-того рядка матриці А (позначимо цей рядок aі) і вектора b:
(4)
Тим самим отримання результуючого вектора С припускає повторення m однотипних операцій по множенню рядків матриці A і вектора b. Кожна така операція включає множення елементів рядка матриці і вектора b (n операцій) і подальше підсумовування отриманих множень (n - 1 операцій). Загальна кількість необхідних скалярних операцій є величина
T1 = m·(2n-1). (5)
2.1. Послідовний алгоритм. Послідовний алгоритм перемноження матриці на вектор може бути представлений таким чином.
// Послідовний алгоритм множення матриці на вектор
for (i = 0; i < m; i++){
с[i]= 0;
for (j = 0; j < n; j++){
с[i]+= A[i][j]*b[j]
}
}
Векторно-матричне множення - це послідовність обчислення скалярних добутків. Оскільки кожне обчислення скалярного добутку векторів довжини n вимагає виконання n операцій множення і (n-1) операцій додавання, його трудомісткість становить O(n). Для виконання векторно-матричного множення необхідно здійснити m операцій обчислення скалярного добутку, таким чином, алгоритм має трудомісткість порядку O(mn).
2.2. Розділення даних. При виконанні паралельних алгоритмів перемноження матриці на вектор, окрім матриці А, необхідно розбити вектор b і вектор результату с. Елементи векторів можна продублювати, тобто скопіювати всі елементи вектора на всі процесори, складові багатопроцесорної обчислювальної системи, або розділити між процесорами. При блоковому розбитті вектора з n елементів кожен процесор обробляє безперервну послідовність із k елементів вектора (припускається, що розмірність вектора n без остачі ділиться на число процесорів, тобто n= k·p).
Пояснимо, чому дублювання векторів b і с між процесорами є допустимим рішенням (далі для простоти викладу вважатимемо, що m=n). Вектори b і с складаються з n елементів, тобто містять стільки ж даних, скільки і один рядок або один стовпець матриці. Якщо процесор зберігає рядок або стовпець матриці і одиночні елементи векторів b і с, то загальне число елементів, що зберігаються, має трудомісткість порядку O(n). Якщо процесор зберігає рядок (стовпець) матриці і всі елементи векторів b і с, то загальна кількість елементів, що зберігаються, також порядку O(n). Таким чином, при дублюванні і при розбитті векторів вимоги до об'єму пам'яті з одного класу складності.
КОНТРОЛЬНІ ЗАПИТАННЯ
Які типи розбиття матриць для їх паралельного перемноження ви знаєте?
Навести та охарактеризувати схему стрічкового розбиття матриць.
Навести та охарактеризувати схему стрічкового розбиття матриць.
Яка загальна кількість операцій при перемножені матриці на вектор?
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Розробити схему інформаційної взаємодії підзадач при перемноженні матриць згідно заданого (варіанту) типу розбиття.
Розробити структурну схему алгоритму перемноження матриці на вектор для заданого розбиття.
Обчислити кількість операцій та розмір даних для кожного процесора.
Розробити програму для перемноження матриць з використанням МРІ.
Зробити висновок про ефективність застосування заданого типу розбиття для поставленої задачі.
Підготувати та захистити звіт.
ЗМІСТ ЗВІТУ ДО ЛАБОРАТОРНОЇ РОБОТИ
1. Типи розбиття матриць для їх паралельного перемноження з використанням МРІ.
2. Завдання (розмір матриці, тип розбиття та кількість процесорів) згідно варіанту.
3. Схема інформаційної взаємодії між підзадачами.
4. Граф-схема алгоритму перемноження матриці на вектор для заданого типу розбиття.
5. Розрахунки кількості операцій та розміру блоку даних для кожного процесора.
6. Текст програми на С з використанням бібліотеки МРІ.
7. Результат виконання програми.
8. Висновок.
ЗАВДАННЯ
№ варіанту
Розмір матриці
Тип розбиття
Кількість процесорів
1
80
650
блокове
5
2
70
1200
блокове
7
3
130
580
стрічкове(верт)
13
4
160
50
стрічкове(гор)
8
5
140
70
блокове
7
6
220
440
блокове
11
7
150
810
стрічкове(верт)
5
8
100
280
стрічкове(гор)
10
9
250
750
блокове
25
10
120
470
блокове
12
11
240
360
стрічкове(верт)
8
12
150
570
стрічкове(гор)
5
13
200
280
блокове
10
14
230
60
блокове
10
15
160
500
стрічкове(верт)
8
16
270
630
стрічкове(гор)
9
17
180
160
блокове
9
18
120
370
блокове
6
19
190
510
стрічкове(верт)
10
20
240
120
стрічкове(гор)
15
21
80
650
блокове
8
22
70
1200
блокове
7
23
130
580
стрічкове(верт)
13
24
160
50
стрічкове(гор)
8
25
140
70
блокове
10
26
220
440
блокове
11
27
150
810
стрічкове(верт)
15
28
100
280
стрічкове(гор)
10
29
250
750
блокове
10
30
120
470
блокове
6
ЛІТЕРАТУРА
А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003, 208 с.
Антонов А.С. Параллельное программирование с использованием технологии МРІ: Учебное пособие. – М.: Издательство МГУ, 2004. – 71 с.
Є. Ваврук, О. Лашко. Організація паралельних обчислень: Навчальний посібник. – Львів: Національний університет “Львівська політехніка”, 2007. – 70 с.
www.parallel.ru
www.mcs.anl.gov/mpi/mpich
ПРИКЛАД ВИКОНАННЯ
Завдання
Розробити програму для паралельного перемноження матриці на вектор заданого розміру з використанням МРІ. Тип розбиття – стрічкове горизонтальне. Кількість процесорів – 7.
Розмір матриці
Тип розбиття
Кількість процесорів
120
7
Стрічкове (гор)
7
Розбиття матриці
При горизонтальному способі розбиття даних (розбиття матриці на горизонтальні смуги) вхідна матриця буде мати такий вигляд:
Рис. 2. Розбиття вхідної матриці на горизонтальні смуги для 7 процесорів.
Для кожного процесора визначено наступний розмір блоку для таких параметрів: матриця А розмірності m х n, вектор b, що складається з n елементів та вектора результатів с розміру m. Вважається, що вектори b і c копіюються на кожний процесор.
Тоді: m x n / p + n + m = 120 x 70 / 10 + 70 + 120 = 1390 елементів;
Кількість операцій визначається на основі (5) та становить 2280 операцій для кожного процесора.
Як базова підзадача може бути вибрана операція скалярного множення одного рядка матриці на вектор.
Розробка схеми інформаційної взаємодії
Для виконання базової підзадачі скалярного добутоку процесор повинен містити відповідний рядок матриці А і копію вектора b. Після завершення обчислень кожна базова підзадача визначає один з елементів вектора результату с.
Для об'єднання результатів і отримання повного вектора с на кожному з процесорів обчислювальної системи необхідно виконати операцію узагальненого збору даних, в якій кожен процесор передає свій обчислений елемент вектора с решті всіх процесорів. Цей крок можна виконати, наприклад, з використанням функції MPI_Allgather з бібліотеки MPI.
У загальному вигляді схема інформаційної взаємодії підзадач в ході виконуваних обчислень наведена на рис. 3.
Рис. 3. Організація обчислень при виконанні паралельного алгоритму множення матриці на вектор, основане на розбитті матриці по рядках
Розбиття та масштабування підзадач по процесорах
В процесі множення матриці на вектор кількість обчислювальних операцій для отримання скалярного добутку однакова для всіх базових підзадач. Тому, у разі, коли кількість процесорів p менше від кількості базових підзадач, можна об'єднати базові підзадачі так, щоб кожен процесор виконував декілька таких підзадач, що відповідають безперервній послідовності (області) рядків матриці А. В цьому випадку після закінчення обчислень кожна базова підзадача визначає набір елементів результуючого вектора с.
Розробка програми з використанням МРІ
Головна функція програми. Реалізує логіку роботи алгоритму, послідовно викликає необхідні підпрограми.
// Множення матриці на вектор - стрічкове горизонтальне розбиття
// (початковий і результуючий вектори дублюються між процесами)
void main(int argc, char* argv[])
{
double* pMatrix; // Перший аргумент - початкова матриця
double* pVector; // Другий аргумент - початковий вектор
double* pResult; // Результат множення матриці на вектор
int Size; // Розміри початкової матриці і вектора double* pProcRows;
double* pProcResult;
int RowNum;
double Start, Finish, Duration;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);
MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);
// Виділення пам'яті і ініціалізація початкових даних
ProcessInitialization(pMatrix, pVector, pResult, pProcRows,
pProcResult, Size, RowNum);
// Розподіл початкових даних між процесами
DataDistribution(pMatrix, pProcRows, pVector, Size, RowNum);
// Паралельне виконання множення матриці на вектор
ParallelResultCalculation(pProcRows, pVector, pProcResult,
Size, RowNum);
// Збір результуючого вектора на всіх процесах
ResultReplication(pProcResult, pResult, Size, RowNum);
// Завершення процесу обчислень
ProcessTermination(pMatrix, pVector, pResult, pProcRows,
pProcResult);
MPI_Finalize();
}
Функція ProcessInitialization. Ця функція задає розмір і елементи для матриці A і вектора b. Значення для матриці A і вектора b визначаються у функції Randomdatainitialization.
// Функція для виділення пам'яті і ініціалізації початкових даних
void ProcessInitialization (double* &pMatrix, double* &pVector,
double* &pResult, double* &pProcRows, double* &pProcResult,
int &Size, int &RowNum)
{
int RestRows; // Кількість рядків матриці, які ще
// не розподілені
int i;
if (ProcRank == 0) {
do {
printf("\nВведіть розмір матриці: ");
scanf("%d", &Size);
if (Size < ProcNum) {
printf("Розмір матриці повинен перевищувати кількість
процесів! \n ");
}
}
while (Size < ProcNum);
}
MPI_Bcast(&Size, 1, MPI_INT, 0, MPI_COMM_WORLD);
RestRows = Size;
for (i=0; i<ProcRank; i++)
RestRows = RestRows-RestRows/(ProcNum-i);
RowNum = RestRows/(ProcNum-ProcRank);
pVector = new double [Size];
pResult = new double [Size];
pProcRows = new double [RowNum*Size];
pProcResult = new double [RowNum];
if (ProcRank == 0) {
pMatrix = new double [Size*Size];
RandomDataInitialization(pMatrix, pVector, Size);
}
}
Функція DataDistribution. Здійснює розсилку вектора b і розподіл рядків початкової матриці A по процесах обчислювальної системи. Слід зазначити, що коли кількість рядків матриці n не є кратною числу процесорів p, об'єм даних, що пересилаються, для процесів може опинитися різним і для передачі повідомлень необхідно використовувати функцію MPI_Scatterv бібліотеки MPI.
// Функція для розбиття початкових даних між процесами
void DataDistribution(double* pMatrix, double* pProcRows,
double* pVector, int Size, int RowNum)
{
int *pSendNum; // Кількість елементів, що посилаються процесу
int *pSendInd; // Індекс першого елементу даних
// посиланого процесу
int RestRows=Size; // Кількість рядків матриці, які ще
// не розподілені
MPI_Bcast(pVector, Size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Виділення пам'яті для зберігання тимчасових об'єктів
pSendInd = new int [ProcNum];
pSendNum = new int [ProcNum];
// Визначення положення рядків матриці, призначених
// кожному процесу
RowNum = (Size/ProcNum);
pSendNum[0] = RowNum*Size;
pSendInd[0] = 0;
for (int i=1; i<ProcNum; i++) {
RestRows -= RowNum;
RowNum = RestRows/(ProcNum-i);
pSendNum[i] = RowNum*Size;
pSendInd[i] = pSendInd[i-1]+pSendNum[i-1];
}
// Розсилка рядків матриці
MPI_Scatterv(pMatrix, pSendNum, pSendInd, MPI_DOUBLE, pProcRows,
pSendNum[ProcRank], MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Звільнення пам'яті
delete [] pSendNum;
delete [] pSendInd;
}
3.3.4. Функція ParallelResultCaculation. Дана функція проводить множення на вектор тих рядків матриці, які розподілені на даний процес, і таким чином виходить блок результуючого вектора с.
// Функція для обчислення частини результуючого вектора
void ParallelResultCalculation(double* pProcRows, double* pVector,
double* pProcResult, int Size, int RowNum) {
int i, j;
for (i=0; i<RowNum; i++) {
pProcResult[i] = 0;
for (j=0; j<Size; j++)
pProcResult[i] += pProcRows[i*Size+j]*pVector[j];
}
}
3.3.5. Функція ResultReplication. Об'єднує блоки результуючого вектора c, отримані на різних процесах, і копіює вектор результату на всі процеси обчислювальної системи.
// Функція для збору результуючого вектора на всіх процесах
void ResultReplication(double* pProcResult, double* pResult,
int Size, int RowNum)
{
int *pReceiveNum; // Кількість елементів, що посилаються процесом
int *pReceiveInd; // Індекс елементу даних в результуючому
// векторі
int RestRows=Size; // Кількість рядків матриці, які ще не
// розподілені
int i;
// Виділення пам'яті для тимчасових об'єктів
pReceiveNum = new int [ProcNum];
pReceiveInd = new int [ProcNum];
// Визначення положення блоків результуючого вектора
pReceiveInd[0] = 0;
pReceiveNum[0] = Size/ProcNum;
for (i=1; i<ProcNum; i++) {
RestRows -= pReceiveNum[i-1];
pReceiveNum[i] = RestRows/(ProcNum-i);
pReceiveInd[i] = pReceiveInd[i-1]+pReceiveNum[i-1];
}
// Збір всього результуючого вектора на всіх процесах
MPI_Allgatherv(pProcResult, pReceiveNum[ProcRank],
MPI_DOUBLE, pResult, pReceiveNum, pReceiveInd,
MPI_DOUBLE, MPI_COMM_WORLD);
// Звільнення пам'яті
delete [] pReceiveNum;
delete [] pReceiveInd;
}
Висновок
В даній лабораторній роботі розроблено алгоритм паралельного перемноження матриці на вектор при стрічковому горизонтальному розбитті вхідних даних. Виконано його програмну реалізацію з використанням МРІ. Розроблено схему інформаційної взаємодії між підзадачами та виконано їх масштабування на задану кількість проесорів системи. Обчислено кількість елементів та операцій для кожного процесора.
НАВЧАЛЬНЕ ВИДАННЯ
ПАРАЛЕЛЬНІ АЛГОРИТМИ МНОЖЕННЯ МАТРИЦІ НА ВЕКТОР
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 4 з дисципліни “Паралельні та розподілені обчислення”
для студентів для студентів базового напряму 6.0915 - “Комп’ютерна інженерія”
Укладачі: Ваврук Євгеній Ярославович
Акимишин Орест Ігорович
Редактор
Комп’ютерне верстання
Здано у видавництво . Підписано до друку
Формат 70х100/16. Папір офсетний. Друк на різографі
Умовн. друк. арк. Обл..-вид. арк..
Тираж прим. Зам..
Видавництво Національного університету “Львівська політехніка”
Реєстраційне свідоцтво ДК №751 від 27.12.2001 р.
Поліграфічний центр Видавництва
Національного університету “Львівська політехніка”
Вул.. Ф. Колесси, 2. Львів, 79000
19.11.2012 18:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора