Паралельне виконання операцій множення матриць

Після останньої паралельної ітерації множення перший процесор вивантажує частковий результат, тобто підматрицю С1. На цьому ж етапі отримано решту часткових результатів. Ці дані пересилаються по кільцю процесорів. Цикл буде повторюватись доти, доки не буде виведено останній частковий результат.

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

 

 

Таблиця 3.1. Схема покрокового виконання алгоритму

Проц. 1	Проц. 3	Проц. 5	Проц. 4	Проц. 7	Проц. 6	Проц. 8	Проц. 2
Z1(A1,B1)	Z3(A3,B3)	Z5(A5,B5)	Z4(A4,B4)	Z7(A7,B7)	Z6(A6,B6)	Z8(A8,B8)	Z2(A2,B2)
A1*B1	A3*B3	A5*B5	A4*B4	A7*B7	A6*B6	A8*B8	A2*B2
B1->3 B2(2)	B3->5 B1(1)	B5->4 B3(3)	B4->7 B5(5)	B7->6 B4(4)	B6->8 B7(7)	B8->2 B6(6)	B2->1 B8(8)
A1*B2	A3*B1	A5*B3	A4*B5	A7*B4	A6*B7	A8*B6	A2*B8
B2->3 B8(2)	B1->5 B2(1)	B3->4 B1(3)	B5->7 B3(5)	B4->6 B5(4)	B7->8 B4(7)	B6->2 B7(6)	B8->1 B6(8)
A1*B8	A3*B2	A5*B1	A4*B3	A7*B5	A6*B4	A8*B7	A2*B6
B8->3 B6(2)	B2->5 B8(1)	B1->4 B2(3)	B3->7 B1(5)	B5->6 B3(4)	B4->8 B5(7)	B7->2 B4(6)	B6->1 B7(8)
A1*B6	A3*B8	A5*B2	A4*B1	A7*B3	A6*B5	A8*B4	A2*B7
B6->3 B7(2)	B8->5 B6(1)	B2->4 B8(3)	B1->7 B2(5)	B3->6 B1(4)	B5->8 B3(7)	B4->2 B5(6)	B7->1 B4(8)
A1*B7	A3*B6	A5*B8	A4*B2	A7*B1	A6*B3	A8*B5	A2*B4
B7->3 B4(2)	B6->5 B7(1)	B8->4 B6(3)	B2->7 B8(5)	B1->6 B2(4)	B3->8 B1(7)	B5->2 B3(6)	B4->1 B5(8)
A1*B4	A3*B7	A5*B6	A4*B8	A7*B2	A6*B1	A8*B3	A2*B5
B4->3 B5(2)	B7->5 B4(1)	B6->4 B7(3)	B8->7 B6(5)	B2->6 B8(4)	B1->8 B2(7)	B3->2 B1(6)	B5->1 B3(8)
A1*B5	A3*B4	A5*B7	A4*B6	A7*B8	A6*B2	A8*B1	A2*B3
B5->3 B3(2)	B4->5 B5(1)	B7->4 B4(3)	B6->7 B7(5)	B8->6 B6(4)	B2->8 B8(7)	B1->2 B2(6)	B3->1 B1(8)
A1*B3	A3*B5	A5*B4	A4*B7	A7*B6	A6*B8	A8*B2	A2*B1
V(C1)	C3->5	C5->4	C4->7	C7->6	C6->8	C8->2	C2->1
V(C2)		C3->4	C5->7	C4->6	C7->8	C6->2	C8->1
V(C8)			C3->7	C5->6	C4->8	C7->2	C6->1
V(C6)				C3->6	C5->8	C4->2	C7->1
V(C7)					C3->8	C5->2	C4->1
V(C4)						C3->2	C5->1
V(C5)							C3->1
V(C3)

 

 

Таблиця 3.2. Опис елементів функціональної схеми

Елемент	Значення
Z1(A1,B1)	Цей елемент представляє процедуру  завантаження вхідних даних з  пам’яті. В даному прикладі, завантажується підматриця А1 та підматриця В1.
V(C1)	Елемент представляє процедуру  вивантаження часткових результатів, в даному випадку підматрицю С1.
A1*B1	Даний блок показує процедуру множення підматриць.
B1->2	Цей елемент представляє процедуру  відправки даних іншому процесору. В цьому прикладі, підматриця В1 відсилається на процесор з рангом 2.
B2(2)	Цей елемент представляє процедуру  отримання даних з іншого процесора. В цьому випадку, отримується  підматриця В2 з процесора з рангом 2.

 

 

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

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

А1-4[7, 208], А5-8[8, 208], B1-3[208, 40], B4-8[208, 41].

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

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

, , ,

 

4.1.     Послідовне виконання

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

Час завантаження:

T_Z =N1*N2 + N2*N3 = (60*208+208*325) *5/3* t_s= 133467 * t_s 

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

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

Час множення:

T_U = N1*N2*N3 = (60*208*325)*10 * t_s = 40560000 * t_s

Час додавання:

  T_S = N1*(N2-1)*N3 = (60*207*325) * t_s=  4036500* t_s 

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

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

Час вивантаження:

T_W = N1*N3= (60*325) *5/3* t_s =32500*t_s

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

Загальний час виконання послідовної частини:

Т_ПОС = T_Z + T_U + T_S + T_W =(133467 + 40560000 + 4036500 + 32500) * t_s =

= 44762467*t_s

 

2. Паралельне виконання

Оскільки кожен процесор завантажує дані паралельно, то кількість результуючих послідовних операцій завантаження буде рівна найбільшій кількості таких операцій виконаних певним процесором. Очевидно, що найдовше завантажуватиме саме 7-8-ий процесор, оскільки розміри його вхідних підматриць найбільші.

Час завантаження:

T_Z =8*N2 + N2*41 = (8*208+208*41) *5/3* t_s= 16987 * t_s

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

Загальний час виконання операцій множення та додавання на чотирьох ітераціях з врахуванням того, що найдовше буде виконуватись частина, де кількість рядків підматриці A=8, а кількість стовпців під матриці B=41 буде рівний:

T_U1 =8*N2*41 = (8*208*41) *10* t_s= 682240 * t_s

T_S1 =8*(N2-1)*41 = (8*(208-1)*41) *t_s= 67896 * t_s

Загальний час виконання операцій множення та додавання на інших чотирьох ітераціях з врахуванням того, що найдовше буде виконуватись частина, де кількість рядків підматриці A=7, а кількість стовпців під матриці B=41 буде рівний:

T_U2 =7*N2*41 = (7*208*41) *10* t_s= 596960 * t_s

T_S2 =7*(N2-1)*41 = (7*(208-1)*41) *t_s= 59409 * t_s                           

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

Час множення:

T_U = T_U1*4+T_U2*4= 4*(682240+596960) * t_s= 5116800 * t_s

Час додавання:

T_S = T_S1*4+T_S2*4= 4*(67896+59409) * t_s= 509220 * t_s

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

T_P1 =208*41 t_s = 8528 * t_s

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

Час пересилання:

T_P = T_P1*7= 59696 * t_s

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

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

На першому етапі вивантажується частковий результат C1 на першому  процесорі, в той же час паралельно пересилаються решта інших часткових  результатів по кільцю процесорів. На другому етапі вивантажується той частковий результат, який на попередньому етапі був пересланий в процесор P1 і знову паралельні дані пересилаються по кільцю. Такий алгоритм продовжується 8 ітерацій, кожна з яких має свої особливості.

Детальний опис етапів:

1-4. Оскільки час вивантаження є меншим за час пересилання (t_P=6t_w), то найдовше буде виконуватись пересилання часткового результату розміром 8х208:

T_W1-4 =4*8*208*10* t_s = 66560 * t_s

5-7. Оскільки час вивантаження є меншим за час пересилання (t_P=6t_w), то найдовше буде виконуватись пересилання часткового результату розміром 7х208:

T_W5-7=3*7*208*10* t_s = 43680 * t_s

8. На цьому етапі виконується тільки вивантаження часткового результату:

T_W8=7*208*5/3* t_s = 2427 * t_s

Час вивантаження:

T_W = T_W1-4 +T_W5-7 +T_W8= 66560 * t_s +43680 * t_s +2427 * t_s = 112667* t_s

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

Загальний час виконання паралельної частини:

 Т_ПАР = T_Z +T_U +T_S +T_P +T_W=16987 * t_s+5116800 * t_s+509220 * t_s+59696 * t_s+112667* t_s=5815370* t_s

Т_ПОС/Т_ПАР = 44762467*t_s/5815370* t_s=7,7.

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

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

K = Т_ПАР /( T_Z +T_U +T_S +T_P) = 5815370* t_s / (16987 * t_s+5116800 * t_s+509220 * t_s+59696* t_s)=1,02.

 

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

E= T_ПОС / (Т_ПАР * Р) = 44762467* t_s / (5815370* t_s * 8)= 0,96.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Розробка програми

Граф-схема програми наведена на рис. 5.1. Лістинг програми наведений в додатку. Дана програма містить консольний інтерфейс, розроблена за допомогою мови програмування Java.

Рис. 5.1. Граф-схема алгоритму перемноження матриць на заданій структурі.

В даній програмі для обміну повідомленнями були використані такі основніфункції для передачі повідомлень:

- sendData;

- receivedData;

Ці методи викликаються на кожному  процесорі, таким чином імітуючи роботу системи.

Генерація вхідних даних виконується  іншою програмою.

Розповсюдження вхідних даних  виконується не напряму, а із врахуванням  структури системи (з врахуванням  фізичних зв’язків між вузлами системи).

 

6. Результат виконання програми

На рис. 6.1 зображено результат роботи програми.

 

Рис 6.1. Результат виконання програми

 

На рис. 6.2 зображено частину результату множення матриць.

Рис 6.2. Результат множення матриць

 

Висновки

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

Для восьмипроцесорної системи  та матриць з розмірами 60х208 та 208х325 умовний час виконання паралельного алгоритму склав 5815370* t_s, послідовної частини 46522960*t_s. А це означає, що завдяки розпаралелюванню показник швидкості виконання програми збільшився в 7,7 разів, ефективність становить 96%, що є фактично ідеальним показником.

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