Исходный код последовательной программы для матричного умножения

Содержание

1. Общие указания по выполнению РГР 3

2. Варианты заданий

2.1. I уровень 4

2.2. II уровень 18

2.3. III уровень 21

Приложение 22

Литература 28

То, что нам надо постичь, чтобы уметь это делать, мы постигаем, делая это.

Аристотель

Общие указания по выполнению РГР

Данная РГР предназначена для освоения технологи MPI (версия стандарта MPI 1.1) путем самостоятельного выполнения практических заданий.

При выполнении заданий должны быть использованы функции из всех основных разделов стандарта MPI 1.1:

o обмены типа точка-точка;

o коллективные обмены;

o контексты, группы и коммуникаторы;

o топологии процессов.

Краткий справочник по функциям MPI приведен в Приложении.

Решение практических задач следует строить по следующей схеме:

1. Написать, откомпилировать и отладить последовательную программу, реализующую алгоритм решения задачи.

2. Исследовать эффективность выполнения программы и возможности по ее распараллеливанию.

3. Исследовать структуру информационных зависимостей алгоритма решения задачи, выбрать метод распределения операций между процессорами.

4. Спланировать структуру обменов данными между процессами. Определить длину сообщения, на которой достигается максимально достижимая пропускная способность (количество мегабайт в секунду).

5. Сравнить эффективность реализации пересылок данных между процессорами с блокировкой и без блокировки.

6. Оценить целесообразность использования барьерной синхронизации при помощи пересылок типа точка-точка и сравнить эффективность различных вариантов реализации.

7. Спланировать использование глобальных операций при реализации выбранного варианта параллельного алгоритма. Реализовать разбиение процессов на группы, для каждой из которых выбрать подходящую топологию (одномерная или многомерная декартова топология, топология графа и т.д.).

8. Оценить возможность использования для пересылок производных типов данных и упакованных данных.

9. Проанализировать эффективность использованных механизмов и при необходимости оптимизировать структуру коммуникаций для разработанной параллельной программы.

Варианты заданий распределены по уровням сложности, что предполагает ограничение на максимальное количество баллов, получаемых в качестве итоговой оценки за РГР:

· 1-ый уровень – стандартный (максимальная сумма баллов – 74);

· 2-ой уровень – повышенный (максимальная сумма баллов – 89);

· 3-ий уровень – творческий (максимальная сумма баллов – 100).

Варианты заданий

I уровень

Разработка параллельного алгоритма матричного умножения

Определение задачи матричного умножения

Умножение матрицы A размера и матрицы B размера m×n и n×l приводит к получению матрицы С размера m×l, каждый элемент которой с_ij есть скалярное произведение i-ой строки матрицы A и j-ого столбца матрицы B.

Тем самым, получение результирующей матрицы С предполагает повторение m×l однотипных операций по умножению строк матрицы A и столбцов матрицы В. Каждая такая операция включает умножение элементов строки и столбца матриц и последующее суммирование полученных произведений.

Псевдокод для последовательного алгоритма умножения матрицы на вектор может выглядеть следующим образом:

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

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

C[i][j] = 0;

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

C[i][j] = C[i][j] + A[i][k]*B[k][j]; } } }

Исходный код последовательной программы для матричного умножения

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <time.h>

// Function for simple initialization of matrix elements

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

int i, j; // Loop variables

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

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

pAMatrix[i*Size+j] = 1;

pBMatrix[i*Size+j] = 1;

}

// Function for random initialization of matrix elements

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);

}

// Function for memory allocation and initialization of matrix elements

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

double* &pCMatrix, int &Size) {

// Setting the size of matricies

do {

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

scanf("%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);

// Memory allocation

pAMatrix = new double [Size*Size];

pBMatrix = new double [Size*Size];

pCMatrix = new double [Size*Size];

// Initialization of matrix elements

DummyDataInitialization(pAMatrix, pBMatrix, Size);

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

pCMatrix[i] = 0;

}

// Function for formatted matrix output

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");

}

// Function for matrix multiplication

void SerialResultCalculation(double* pAMatrix, double* pBMatrix,

double* pCMatrix, int Size) {

int i, j, k; // Loop variables

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

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

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

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

}

// Function for computational process termination

void ProcessTermination(double* pAMatrix, double* pBMatrix,

double* pCMatrix) {

delete [] pAMatrix;

delete [] pBMatrix;

delete [] pCMatrix;

}

void main() {

double* pAMatrix; // The first argument of matrix multiplication

double* pBMatrix; // The second argument of matrix multiplication

double* pCMatrix; // The result matrix

int Size; // Size of matricies

time_t start, finish;

double duration;

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

// Memory allocation and initialization of matrix elements

ProcessInitialization(pAMatrix, pBMatrix, pCMatrix, Size);

// Matrix output

printf ("Initial A Matrix \n");

PrintMatrix(pAMatrix, Size, Size);

printf("Initial B Matrix \n");

PrintMatrix(pBMatrix, Size, Size);

// Matrix multiplication

start = clock();

SerialResultCalculation(pAMatrix, pBMatrix, pCMatrix, Size);

finish = clock();

duration = (finish-start)/double(CLOCKS_PER_SEC);

// Printing the result matrix

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

PrintMatrix(pCMatrix, Size, Size);

// Printing the time spent by matrix multiplication

printf("\n Time of execution: %f\n", duration);

// Computational process termination

ProcessTermination(pAMatrix, pBMatrix, pCMatrix);

}