MatrixC [i] [j] =MatrixC [i] [j] + MatrixA [i] [k] *MatrixB [k] [j];

}

}

}

Цей алгоритм є ітеративним і орієнтований на послідовне обчислення рядків матриці С. Дійсно, при виконанні однієї ітерації зовнішнього циклу (циклу по змінній i) обчислюється один рядок результуючої матриці (см. рис.2.6).

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

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

У цьому плані може виявитися корисною агрегація обчислень вже на кроці виділення базових підзадач. Можливе рішення може полягати в об'єднанні в рамках однієї підзадачі всіх обчислень, пов'язаних не з одним, а з декількома елементами результуючої матриці С. Для подальшого розгляду визначимо базове завдання як процедуру обчислення всіх елементів одного з рядків матриці С. Такий підхід призводить до зниження загальної кількості підзадач до величини n. Для виконання всіх необхідних обчислень базовій підзадачі мають бути доступні один з рядків матриці A і всі стовпці матриці B. Просте вирішення цієї проблеми:

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

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

Можлива проста схема організації необхідної послідовності передач стовпців матриці В між підзадачами полягає в представленні топології інформаційних зв'язків підзадач у вигляді кільцевої структури. В цьому випадку на кожній ітерації підзадача i, 0<i<n, передаватиме свій стовпець матриці В підзадачі з номером i+1 (відповідно до кільцевої структури підзадача n-1 передає свої дані підзадачі з номером 0) - див. рис.2.5 Після виконання всіх ітерацій алгоритму необхідна умова буде забезпечена - в кожній підзадачі по черзі виявляться всі стовпці матриці С.

На рис. 2.5 представлені ітерації алгоритму матричного множення для випадку, коли матриці складаються з чотирьох рядків і чотирьох стовпців (n=4). На початку обчислень в кожній підзадачі i, 0<i<n, розташовуються i-я рядок матриці A і i-й стовпець матриці B. В результаті їх перемножування підзадача отримує елемент cii результуючої матриці С.

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

Рис. 2.7 Загальна схема передачі даних для першого паралельного алгоритму матричного множення при стрічковій схемі розділення даних

2.2.3 Текст програми

#include "stdafx. h"

#include <stdio. h>

#include <stdlib. h>

#include <conio. h>

#include <time. h>

#include "mpi. h"

// Функція випадкового ініціалізації елементів матриці

void RandomDataInitialization (double* pAMatrix, double* pBMatrix, int Size) {

int i, j; // Loop variables

srand (unsigned (clock ()));

for (i=0; i<Size; i++)

for (j=0; j<Size; j++) {

pAMatrix [i*Size+j] = rand () /double (1000);

pBMatrix [i*Size+j] = rand () /double (1000);

}

}

// Функція для виділення пам'яті і ініціалізації елементів матриці

void ProcessInitialization (double* &pAMatrix, double* &pBMatrix,

double* &pCMatrix, double* &pCMatrixSum, int &Size) {

// Установка розміру матриці

do {

printf ("\nEnter size of matricies: ");

fflush (stdout);

scanf_s ("%d", &Size);

printf ("\nChosen matricies' size = %d\n", Size);

if (Size <= 0)

printf ("\nSize of objects must be greater than 0! \n");

}

while (Size <= 0);

// Виділення пам'яті

pAMatrix = new double [Size*Size];

pBMatrix = new double [Size*Size];

pCMatrix = new double [Size*Size];

pCMatrixSum = new double [Size*Size];

// Ініціалізація елементів матриці

RandomDataInitialization (pAMatrix, pBMatrix, Size);

for (int i=0; i<Size*Size; i++) {

pCMatrix [i] = 0;

pCMatrixSum [i] = 0;

}

}

// Функція форматованого виведення матриці

void PrintMatrix (double* pMatrix, int RowCount, int ColCount) {

int i, j; // Loop variables

for (i=0; i<RowCount; i++) {

for (j=0; j<ColCount; j++)

printf ("%7.4f", pMatrix [i*RowCount+j]);

printf ("\n");

}

}

// Функція для множення матриць

void SerialResultCalculation (double* pAMatrix, double* pBMatrix,

double* pCMatrix, int Size, int nCommRank, int nCommSize) {

int i, j, k; // Loop variables

for (i=0; i<Size; i++) {

for (j=0+nCommRank; j<Size; j+=nCommSize) {

for (k=0; k<Size; k++) {

pCMatrix [i*Size+j] +=

pAMatrix [i*Size+k] *pBMatrix [k*Size+j];

}

}

}

}

// Функція для обчислювальних завершення процесу

void ProcessTermination (double* pAMatrix, double* pBMatrix,

double* pCMatrix, double* pCMatrixSum) {

delete [] pAMatrix;

delete [] pBMatrix;

delete [] pCMatrix;

delete [] pCMatrixSum;

}

int main (int argc, char* argv []) {

double* pAMatrix; // Перший аргумент матричного множення

double* pBMatrix; // Другий аргумент матричного множення

double* pCMatrix; // Результат матриці

double* pCMatrixSum; // Результат матриці

int Size; // Розмір матриці

int nCommRank, nCommSize, namelen, nCounter;

int nIntervals;

char processor_name [MPI_MAX_PROCESSOR_NAME];

double t1, t2;

MPI_Status status;

MPI_Init (&argc, &argv);

MPI_Comm_rank (MPI_COMM_WORLD, &nCommRank);

MPI_Comm_size (MPI_COMM_WORLD, &nCommSize);

MPI_Get_processor_name (processor_name,&namelen);

if (nCommRank == 0) {

printf ("Parallel matrix multiplication program\n");

// Розподіл пам'яті і ініціалізацію елементів матриці

ProcessInitialization (pAMatrix, pBMatrix, pCMatrix, pCMatrixSum, Size);

// Вихідна матриця

printf ("Initial A Matrix \n");

PrintMatrix (pAMatrix, Size, Size);

printf ("Initial B Matrix \n");

PrintMatrix (pBMatrix, Size, Size);

t1 = MPI_Wtime ();

for (nCounter = 1; nCounter < nCommSize; nCounter++) {

MPI_Send (&Size, 1, MPI_INT, nCounter, 0, MPI_COMM_WORLD);

MPI_Send (pAMatrix, Size*Size, MPI_DOUBLE, nCounter, 1,MPI_COMM_WORLD);

MPI_Send (pBMatrix, Size*Size, MPI_DOUBLE, nCounter, 2,MPI_COMM_WORLD);

MPI_Send (pCMatrix, Size*Size, MPI_DOUBLE, nCounter, 3,MPI_COMM_WORLD);

}

} else {

MPI_Recv (&Size, 1, MPI_INT, 0, 0, MPI_COMM_WORLD,

MPI_STATUS_IGNORE);

pAMatrix = new double [Size*Size];

pBMatrix = new double [Size*Size];

pCMatrix = new double [Size*Size];

MPI_Recv (pAMatrix, Size*Size, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD,

MPI_STATUS_IGNORE);

MPI_Recv (pBMatrix, Size*Size, MPI_DOUBLE, 0, 2, MPI_COMM_WORLD,

MPI_STATUS_IGNORE);

MPI_Recv (pCMatrix, Size*Size, MPI_DOUBLE, 0, 3, MPI_COMM_WORLD,

MPI_STATUS_IGNORE);

}

// множення матриць

SerialResultCalculation (pAMatrix, pBMatrix, pCMatrix, Size, nCommRank, nCommSize);

MPI_Reduce (pCMatrix,pCMatrixSum,Size*Size,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_W

ORLD);

printf ("Process %d of %d running on %s\n", nCommRank, nCommSize,

processor_name);

if (nCommRank == 0) {

// Виведення результатів матриці

printf ("\n Result Matrix Sum: \n");

PrintMatrix (pCMatrixSum, Size, Size);

// Завершення обчислювального процесу

ProcessTermination (pAMatrix, pBMatrix, pCMatrix, pCMatrixSum);

t2 = MPI_Wtime ();

printf ("Time is %f seconds \n", t2-t1);

}

MPI_Finalize ();

}

2.2.4 Результати обчислювальних експериментів

Експерименти виконувалися з використанням двох, чотири і восьми процесорів.

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

Рис. 2.6 Графік залежності швидкості множення матриці на матрицю від кількості використовуваних процесів і від розмірності матриці

2.2.5 Висновки

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

Перелік посилань

1. Корнєєв В.Д. "Паралельне програмування в МРІ". Друге видання, випр. Новосибірськ, 2002.

2. Інтернет - сайт: http://iproc.ru/programming/mpich-windows/

3. Інтернет - сайт: http://bigor. bmstu.ru/? cnt/? doc=Parallel/base. cou

4. Хорошевский В.Г. "Архітектура обчислювальних систем". М: Навчальний посібник для вузів, 2005.

5. Інтернет - сайт: http://www.intuit.ru

6. Бувайло Д.П., Толок В.А. "Розподілені обчислення". Навчальний посібник для студентів математичних спеціальностей, 2002.

7. С.А. Немнюгин "Средства программирования для многопроцессорных вычислительных систем".

8. А.А. Букатов, В.Н. Дацюк, А.И. Жегуло "Программирование многопроцессорных вычислительных систем".

Размещено на Allbest.ru