Исходный код последовательной программы для матричного умножения
Содержание
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);
}