Перемноження матриці А на В кільцевій структурі

Міністерство Освіти і Науки України Національний Університет «Львівська Політехніка»

Курсовий проект з дисципліни «Паралельні та розподілені обчислення»

Перемноження матриці А на В кільцевій структурі

Хмельницький — 2011

Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю n1*n2) на матрицю В (розмірністю n2*n3)а кільцевій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці. Процесори паралельно записують чи читають дані. Збір даних проводиться по двох напрямках.

Анотація В курсовій роботі розроблена модель 7-ми процесорної системи, яка виконує множення двох матриць з розмірами 230×590 і 590×300. Завантаження даних здійснюється через один з процесорів. Процесори можуть тільки послідовно записувати чи читати дані. Наведені граф-схеми роботи, визначені ефективність, час виконання алгоритму, відсоток послідовної частини алгоритму.

Зміст Вступ

1. Теоретичний розділ

2. Розробка блок-схеми виконання алгоритму

3. Розробка функціональної схеми

4. Розрахунковий розділ

5. Розробка програми Висновок Література Додаток

Вступ Створення програм, що використовують паралельні алгоритми виконання є однією з найпріорітетніших задач в сучасному програмуванні. Основним завдання програмістів є ефективне розділення навантаження на обчислювальні системи. Це одночасно є і основною проблемою програмування. Тому що створення програм з явним паралелізмом невластиве для людей які думають послідовно, також є проблема організації доступу до пам’яті, синхронізації обміну даними між процесорами та ін.

В даній курсовій роботі розроблена модель множення матриць на декількох процесорах, так як проблема множення матриць являється поширеною в таких науках як квантова фізика, робототехніка, обробка графіки та ін.

1. Теоретичний розділ Множення матриці на вектор і матриці на матрицю є базовими макроопераціями для багатьох задач. Для їх реалізації використовуються різні алгоритми та різні структури. Розмаїтість варіантів алгоритмів виникає із-за розмаїтості обчислювальних систем і розмаїтості розмірів задач. Розглядаються і різні варіанти завантаження даних у систему: завантаження даних через один з процесорів, завантаження даних безпосередньо кожним процесором з розподіленої пам’яті. Якщо завантаження даних здійснюється через один з процесорів, то дані зчитуються цим процесором з пам’яті, розрізаються на частини, які розсилаються іншим процесорам. Але дані можуть бути підготовлені і заздалегідь, тобто заздалегідь розрізані вроздріб і кожна частина записана в окрему пам’ять, потім кожен процесор безпосередньо зчитує з пам’яті призначений для нього файл.

Алгоритм перемноження матриці на матрицю на 7 процесорах Задано дві матриці А і В. обчислюються С=А х В, де, А — матриця n1 х n2, В — матриця

n2 х n3. Матриця результатів С має розмір n1 х n3. Вхідні дані зчитує один з процесорів який виконує розрізання матриць на шматки й пересилку їх по заданих процесорах.

Реалізація алгоритму виконується на 7-ми процесорах. Матриці розрізані як наведено на рис 1.1: матриця, А розрізана на 7 горизонтальних смуг, матриця В — на 7 вертикальних смуг, і матриця результату С на 7*7 кубиків. Передбачається, що в па`ять кожного процесора необхідно завантажити тільки одну смугу матриці А і одну смугу матриці В. Дане завантаження виконується потоковим методом.

Рис 1.1 Схема розрізання даних Оскільки за умовою в процесорах знаходиться по одній смузі матриць, то смуги матриці B (або смуги матриці A) необхідно «прокрутити» по кільцю процесорів повз смуги матриці A (матриці B). Кожний зсув смуг уздовж кільця. На кожному з таких кроків обчислюється тільки частина смуги. Процес i обчислює на j-м кроці добуток i-й горизонтальної смуги матриці A j-ї вертикальної смуги матриці B, добуток отримується у підматриці(i, j) матриці C.

Обчислення відбувається в такій послідовності.

1. Перший процесор дістає повну матрицю, А та матрицю В. Він пересилає в наступний процесор 6/7 і залишає собі 1/7 і так до кінця.

2. Обчислювальний крок 1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.

3. Обчислювальний крок 2. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів. І т.д.

4. Обчислювальний крок p1−1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.

5. Обчислювальний крок p1. Кожен процес обчислює одну підматрицю добутку. Вертикальні смуги матриці B зсуваються уздовж кільця процесорів.

6. Всі дані збираються в першому процесорі.

Алгоритм характерний тим, що після кожного кроку обчислень здійснюється обмін даними. Нехай tu, ts, і tp час операцій, відповідно, множення, додавання і пересилання одного числа між сусідніми процесорами. Тоді загальний час виконання операцій множення:

U = (n1*n2*n2)*tu,

загальний час виконання операцій додавань:

S = (n1*(n2−1)*n3)*ts,

загальний час виконання операцій пересилань даних по всіх процесорах:

P = (n3*n2)*(p1−1)*tp.

Загальний час обчислень визначимо як T = (U+S+P)/p1. Відношення часу «обчислень без обмінів» до загального часу обчислень:

K = (U+S)/(U+S+P).

Якщо час передачі даних великий в порівнянні з часом обчислень, або канали передачі повільні, то ефективність алгоритму буде не висока. Тут не враховується час початкового завантаження і вивантаження даних у пам’ять системи. У смугах матриць може бути різна кількість рядків, а різниця в кількості рядків між смугами 1.

2. Проектування граф-схеми виконання алгоритму Рис 2.1 Граф-схема виконання алгоритму множення двох матриць на структурі 7-ми процесорів з доступом до пам`яті через один з них.

Для матриць А[N1,N2] та B[N2,N3] і Р процесорів розміри підматриць Аі та Ві визначаються так.

Для, А та для В обчислюємо

де С1А та С1В — ціла частина від ділення, С2А та С2В — залишки.

Перші (Р — С2А) підматриці матриці А матимуть кількість рядків С1А, решту — (С1А + 1) рядків. Для матриці В, відповідно, (Р — С2В), С1 В, (С1 В + 1) стовпців.

На рисунку 2.2 наведено граф-схему покрокового виконання алгоритму. Ця блок-схема характеризує алгоритм загалом.

Для кінцевого визначення результату необхідно виконати кількість циклів множення рівну кількості процесорів в системі. Тобто, кожен процесор в кільці зчитує з наступного по ходу нову підматрицю та її розміри. Після завершення останнього циклу множення, яке проходить паралельно на кожному процесорі, починається заключна послідовна фаза обчислення добутку, а саме вивантаження часткових результатів в пам`ять.

Рис. 2.2 Граф-схема покрокового виконання алгоритму множення

3. Розробка функціональної схеми Рис. 3.1 Граф-схема перемноження матриці

4. Розрахунковий розділ Для процесорних елементів визначимо такі розміри підматриць:

A0[32,590]B0[590,42]

A1[33,590]B1[590,43]

A2[33,590]B2[590,43]

A3[33,590]B3[590,43]

A4[33,590]B4[590,43]

A5[33,590]B5[590,43]

A6[33,590]B6[590,43]

Оскільки кожен процесор завантажує дані паралельно, в даному випадку кількість операцій завантаження:

Tz=(135 700+177000) 312 700+178686+89 343+44671=625 400

Після операції завантаження початкових даних в процесори записується цикл обробки даних, який має 7 ітерацій, які включають в себе як множення підматриць, так і пересилання даних між процесорами (підматриці Ві).

Для послідовного алгоритму загальна кількість операцій множення і додавання:

Tuz=N1*N2*N3=230*590*300=837 210

Tsz=N1*N3*(N2−1)=230*300*589=40 641 000

Загальна кількість операцій множення та додавання на кільцевій структурі рівна: ітерації

Tu=N11*N21*N31=33*590*43=153 000

Ts=N11*N31*(N21−1) = 33*43*589=835 791

Сумарна кількість операцій множення і додавання при опрацюванні даних:

Tus= Tu*7, Tus = 1 071 000

Tss= Ts*7, Tss = 5 850 537

Кількість операцій обміну на кожній ітерації рівна кількості елементів найбільшої з підматриць Ві:

Tp=N2*Nb=590*43=25 370

Тоді загальна кількість операцій обміну буде рівна:

1>0, 6>0, 3>2, 4>5

2>1, 5>6

1>0, 6>0

2>1, 4>5

1>0, 6>0

Tps=Tp*5*(p-1)= 25 370*5*6=761 100

Після виконання п’яти ітерацій в пам’яті кожного з процесорів отримуємо результуючу часткову підматрицю Сі. Отже необхідно зібрати всі підмасиви Сі з кожного процесора в загальну пам’ять результуючої матриці С.

Вивантаження даних відбувається в паралельному режимі. Звідси, кількість операцій вивантаження буде рівна кількості елементів результуючої матриці С:

Tw=5*33*300 = 49 500

Для визначення точних характеристик системи врахуємо співвідношення часових параметрів (згідно з завданням). Насамперед, зведемо часи виконання різних операцій до спільного знаменника, тобто визначимо базову операцію для знаходження часів виконання інших операцій. Згідно завдання:

Tu = 16Ts = 5Tp = 8Tz = 7Tw

Виразимо інші операції через найменший час Ts:

, ,

Для визначення повного часу необхідно визначити час всіх його складових, де операції виконуються послідовно (вивантаження) та паралельно (завантаження, обчислення, обмін даними).

При паралельному завантаженні виконується операцій що еквівалентно кількості операцій додавання:

Кількість операцій множення 1 071 000, що еквівалентно:

.

Кількість операцій додавань та кількість операцій пересилань даних, що еквівалентно:

Кількість операцій вивантаження, що є еквівалентно:

Тоді загальна кількість операцій додавання при виконанні паралельного алгоритму на кільцевій структурі:

Для порівняння обчислимо умовний час виконання послідовного алгоритму: перемноження процесорний матриця

Tpos= (+()*7+)=164 635 222 Ts

Tpos/T=164 635 222/26776000=6.15

Порівнюючи останні результати бачимо, що перемноження однакових матриць на одному процесорі приблизно в 6 разів повільніше за множення на семи процесорній системі на основі кільцевої топології.

Для характеристики алгоритму визначимо коефіцієнт К, який рівний відношенню часу виконання загального алгоритму до часу виконання паралельних операцій.

Ефективність визначається як відношення часу виконання задачі на однопроцесорній системі, до часу потрібного на виконання для багатопроцесорної на кількість процесорів в ній.

5. Розробка програми Граф-схема програми наведена на рис. 5.1. Лістинг програми наведений в Додатку. Дана прогрвма розроблена за допомогою мови програмування С++, на основі програмного продукту «С++ Builder 6.0», в якому використовується стандартний набір користувацького інтерфейсу на основі компонентів «VCL».

Рис. 5.1 Алгоритм роботи програми

Висновок В ході виконання даної курсової роботи розроблено структуру перемноження двох матриць. Також було проведено обчислення, які дають уявлення про характеристики даного алгоритму. В результаті проведеної роботи можна зробити такі висновки. Для 7 процесорної системи та матриць з розмірами 230×590, 590×300 умовний час виконання програми в інтервалах виконання операції додавання виявився рівним .

Література

1. Методичні вказівки до курсової роботи з дисципліни «Моделювання паралельних обчислювальних процесів» для студентів базового напряму «Комп`ютерна інженерія». Укладачі: Ваврук Є.Я., Ляшко О. — Львів: Національний університет «Львівська політехніка», 2009 р.

2. Воеводин В. В. «Параллельные вычесления.» — СПБ: БХВ-Питербург, 2002 р.

3. Ортега Дж. «Введение и параллельные и векторные методы решения линейных систем», М.:Мир, 1991 р.

4. http://www.mpiforum.org — Повний варіант описів стандартів МРІ.

5. http://www.keldysh.ru.norma — Опис системи програмування НОРМА.

6. http://www.citforum.ru — Сервер інформаційних технологій.

7. http://www.parallel.ruІнформаційно-аналітичний центр з паралельних обчислень.

8. http://www.csa.ru — Інститут високопродуктивних обчислень і баз даних.

9. http://www.hpc.nw.ru — Високопродуктивні обчислення.

Додаток Лістинг програми

CPU_Circular.cs

namespace Kursova

{

class CPU₇_Circular

{

public CPU₇_Circular (Int16 n1, Int16 n2, Int16 n3)

{

N1 = n1;

N2 = n2;

N3 = n3;

CPUStructure = new CPU[8];

CPUStructure[0] = new CPU (32, 590, 42);

CPUStructure[1] = new CPU (33, 590, 43);

CPUStructure[2] = new CPU (33, 590, 43);

CPUStructure[3] = new CPU (33, 590, 43);

CPUStructure[4] = new CPU (33, 590, 43);

CPUStructure[5] = new CPU (33, 590, 43);

CPUStructure[6] = new CPU (33, 590, 43);

//Joining to ring

CPUStructure[0]. Next = CPUStructure[1];

CPUStructure[1]. Next = CPUStructure[2];

CPUStructure[2]. Next = CPUStructure[3];

CPUStructure[3]. Next = CPUStructure[4];

CPUStructure[4]. Next = CPUStructure[5];

CPUStructure[5]. Next = CPUStructure[6];

CPUStructure[6]. Next = CPUStructure[7];

//==

}

~CPU₇_Circular ()

{ }

public struct CPUsPartOfMemory

{

public Int16[,] StripA;

public Int16[,] StripB;

}

//Fields

private CPU[] _cpuStructure;

private CPUsPartOfMemory[] _cpuMP;

private Int16 _n1;

private Int16 _n2;

private Int16 _n3;

private Double _operationsTime;

//Properties

public CPU[] CPUStructure

{

get { return _cpuStructure; }

set { _cpuStructure = value; }

}

public CPUsPartOfMemory[] CPUsMem

{

get { return _cpuMP; }

set { _cpuMP = value; }

}//Sructure that represents the memory of each CPU

public Int16 N1

{

get { return _n1; }

set { _n1 = value; }

}

public Int16 N2

{

get { return _n2; }

set { _n2 = value; }

}

public Int16 N3

{

get { return _n3; }

set { _n3 = value; }

}

public Double OpTime

{

get { return _operationsTime; }

set { _operationsTime = value; }

}//Total operations

//Methods

public Double StartPerforming (DataGridView A, DataGridView B, DataGridView C)

{

//program

OpTime = 0;

InitSplittedMemory (A, B, C);//initialising processors memories

for (Int16 x = 0; x <7; ++x)//initialising processors cache vith zeros

CPUStructure[x]. CZero ();

for (Int16 i = 0; i < 7; ++i)//calculation cycles

{

Double suops = 0, su;

}

for (Int16 cpu = 0; cpu < 7; ++cpu)//~Parallel computing~

{

//Calculating partial aray

su = CPUStructure[cpu]. CalculatePartialC ();

if (su > suops)

{ suops = su; }

//==

}

OpTime += suops;

if (i < 8)

{

for (Int16 cp = 0; cp < 7; ++cp)//data changing

CPUStructure[cp]. DataChange ();

for (Int16 ad = 0; ad < 6; ++ad)//Adopting new data

CPUStructure[ad]. AdoptNextData ();

}

OpTime += N2 * N3 * (7/2);

}

//saving data from partial arrays to output array

OpTime += CPUStructure[0]. SaveData (42, C);

OpTime += CPUStructure[1]. SaveData (85, C);

OpTime += CPUStructure[2]. SaveData (127, C);

OpTime += CPUStructure[3]. SaveData (170, C);

OpTime += CPUStructure[4]. SaveData (213, C);

OpTime += CPUStructure[5]. SaveData (257, C);

OpTime += CPUStructure[6]. SaveData (300, C);

//==

return OpTime;

}

private Boolean InitSplittedMemory (DataGridView A, DataGridView B, DataGridView C)

{

CPUsMem = new CPUsPartOfMemory[7];

for (Int16 i = 0; i < 7; ++i)

{

CPUsMem[i] = new CPUsPartOfMemory ();

}

//CPU#1−3

for (Int16 c13 = 0; c16 < 7; ++c16)

{

CPUsMem[c8]. StripA = new Int16[8, N2]; //A

for (Int16 c8ar = 0; c8ar < 7; ++c16ar)

{

for (Int16 c16ac = 0; c8ac < N2; ++c16ac)

{

CPUsMem[c8]. StripA[c8ar, c16ac] = new Int16();

Int16.TryParse (A[c8ac, 8 * c16 + c16ar]. Value. ToString (), out CPUsMem[c7]. StripA[c7ar, c7ac]);

}

}

CPUsMem[c9]. StripB = new Int16[9]; //B

for (Int16 c9br = 0; c9br < N2; ++c9br)

{

for (Int16 c9bc = 0; c9bc < 7; ++c13bc)

{

CPUsMem[c9]. StripB[c9br, c9bc] = new Int16();

Int16.TryParse (B[c9*8+c9bc, c9br]. Value. ToString (), out CPUsMem[c9]. StripB[c9br, c9bc]);

}

}

}

//CPU#4−7

for (Int16 c9 = 8; c9 < 8; ++c9)

{

CPUsMem[c9]. StripA = new Int16[9]; //A

for (Int16 c9r = 0; c9r < 7; ++c9r)

{

for (Int16 c9c = 0; c9c < N2; ++c9c)

{

CPUsMem[c9]. StripA[c9r, c9c] = new Int16();

Int16.TryParse (A[c9c, 9 * c6 + c9r]. Value. ToString (), out CPUsMem[c9]. StripA[c9r, c9c]);

}

}

CPUsMem[c9]. StripB = new Int16[9]; //B

for (Int16 c9br = 0; c9br < N2; ++c9br)

{

for (Int16 c9bc = 0; c9bc < 7; ++c9bc)

{

CPUsMem[c46]. StripB[c46br, c9bc] = new Int16();

Int16.TryParse (B[9+ c9bc, c9br]. Value. ToString (), out CPUsMem[c19]. StripB[c9br, c9bc]);

}

}