20.01.2013, 02:58
общий
это ответ
Здравствуйте, Евгений!
Вот Вам программа, умножающая две матрицы разными способами,
используя разный порядок следования вложенных циклов.
Чем больше используются размещенные последовательно числа, тем
быстрее будет общая работа.
Кроме того, при последовательной выборке данных увеличивается
эффективность использования кэш-памяти.
Программа показывает, что быстрее всего работает порядок ikj, чуть хуже kij
[code h=200]#include "stdafx.h"
#include <cstdio>
#include <iostream>
#include <cmath>
#include <windows.h>
//Умножение двух матриц.
//Матрица представлена, как одномерный массив адресов строк, где хранятся массивы столбцов
//Инициализация матрицы значениями sin(rnd())
//Параметры: адрес массива строк и число строк и столбцов
void init(float *a[], int rows, int columns)
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < columns; j++)
//заполняем случайными значениями -1 < a[i][j] < +1
a[i][j] = sin((float)rand()/RAND_MAX);
}
}
//Очистка матрицы нулями
//В программе не стоит задача получить значения выходной матрицы, поэтому значения матрицы неважны.
//Но, для чистоты эксперимента, перед расчетом везде выходную матрицу будем обнулять.
//Кроме того, в первый раз это даст нам корректные числа (вместо мусора).
void clear(float *a[], int rows, int columns)
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < columns; j++)
a[i][j] = 0;
}
}
//Размер матриц
#define MAX_SIZE 1500
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "Russian");
float *a[MAX_SIZE]; //исходная матрица A, как массив адресов массивов
float *b[MAX_SIZE]; //исходная матрица B, как массив адресов массивов
float *c[MAX_SIZE]; //выходная матрица C, как массив адресов массивов
//их выделим в стеке
//запросим динамическую память под элементы массивов
for(int i=0; i<MAX_SIZE; i++) //по строкам
{
a[i] = (float*)_aligned_malloc(sizeof(float)*MAX_SIZE, 16);
b[i] = (float*)_aligned_malloc(sizeof(float)*MAX_SIZE, 16);
c[i] = (float*)_aligned_malloc(sizeof(float)*MAX_SIZE, 16);
}
DWORD startTime, endTime; //переменные для подсчета времени работы
startTime = GetTickCount(); //засекаем начало инициализации исходных массивов
init(a, MAX_SIZE, MAX_SIZE); //инициируем массив A случайными числами
init(b, MAX_SIZE, MAX_SIZE); //инициируем массив B случайными числами
endTime = GetTickCount(); //конец инициализации
printf("Инициализация массивов: %7.0d мс\n", endTime - startTime); //время работы в милисекундах
//далее отрабатываем расчет умножения матриц
// разным порядком вложенных циклов
//цикл ijk
printf("Цикл ijk: %dx%d: ", MAX_SIZE, MAX_SIZE); //выведем, что мы считаем...
clear(c, MAX_SIZE, MAX_SIZE); //очистим результат
startTime = GetTickCount(); //засекаем начало
for (int i = 0; i < MAX_SIZE; i++) //считаем
for (int j = 0; j < MAX_SIZE; j++)
for (int k = 0; k < MAX_SIZE; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount(); //засекаем конец
printf("%7.0d мс\n", endTime - startTime); //выводим время работы
//далее аналогично...
//цикл ikj
printf("Цикл ikj: %dx%d: ", MAX_SIZE, MAX_SIZE);
clear(c, MAX_SIZE, MAX_SIZE);
startTime = GetTickCount();
for (int i = 0; i < MAX_SIZE; i++)
for (int k = 0; k < MAX_SIZE; k++)
for (int j = 0; j < MAX_SIZE; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount();
printf("%7.0d мс\n", endTime - startTime);
//цикл jik
printf("Цикл jik: %dx%d: ", MAX_SIZE, MAX_SIZE);
clear(c, MAX_SIZE, MAX_SIZE);
startTime = GetTickCount();
for (int j = 0; j < MAX_SIZE; j++)
for (int i = 0; i < MAX_SIZE; i++)
for (int k = 0; k < MAX_SIZE; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount();
printf("%7.0d мс\n", endTime - startTime);
//цикл jki
printf("Цикл jki: %dx%d: ", MAX_SIZE, MAX_SIZE);
clear(c, MAX_SIZE, MAX_SIZE);
startTime = GetTickCount();
for (int j = 0; j < MAX_SIZE; j++)
for (int k = 0; k < MAX_SIZE; k++)
for (int i = 0; i < MAX_SIZE; i++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount();
printf("%7.0d мс\n", endTime - startTime);
//цикл kij
printf("Цикл kij: %dx%d: ", MAX_SIZE, MAX_SIZE);
clear(c, MAX_SIZE, MAX_SIZE);
startTime = GetTickCount();
for (int k = 0; k < MAX_SIZE; k++)
for (int i = 0; i < MAX_SIZE; i++)
for (int j = 0; j < MAX_SIZE; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount();
printf("%7.0d мс\n", endTime - startTime);
//цикл kji
printf("Цикл kji: %dx%d: ", MAX_SIZE, MAX_SIZE);
clear(c, MAX_SIZE, MAX_SIZE);
startTime = GetTickCount();
for (int k = 0; k < MAX_SIZE; k++)
for (int j = 0; j < MAX_SIZE; j++)
for (int i = 0; i < MAX_SIZE; i++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
endTime = GetTickCount();
printf("%7.0d мс\n", endTime - startTime);
for(int i=0; i<MAX_SIZE; i++) //освобождаем память
{
_aligned_free(a[i]);
_aligned_free(b[i]);
_aligned_free(c[i]);
}
return 0;
}[/code]
Вторая программа:
[code h=200]#include "stdafx.h"
#include <cstdio>
#include <conio.h>
#include <iostream>
#include <cmath>
#include <windows.h>
//Умножение двух матриц.
//Матрица представлена, как одномерный массив адресов строк, где хранятся массивы столбцов
//Инициализация матрицы значениями sin(rnd())
//Параметры: адрес массива строк и число строк и столбцов
void init(float *a[], int rows, int columns)
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < columns; j++)
//заполняем случайными значениями -1 < a[i][j] < +1
a[i][j] = sin((float)rand()/RAND_MAX);
}
}
//Очистка матрицы нулями
void clear(float *a[], int rows, int columns)
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < columns; j++)
a[i][j] = 0;
}
}
//Размер матриц
const int n = 1000;
//расчет умножения матриц c=a*b
//size - размер матриц
//N - количество блоков
void CalcMatrix(float *a[], float *b[], float *c[], int size, int N)
{
DWORD startTime, endTime; //переменные для подсчета времени работы
int M = size / N; //размер одного блока
printf("Количество блоков = %d, размер блока = %d: ", N, M); //выведем, что мы считаем...
clear(c, size, size); //очистим результат
startTime = GetTickCount(); //засекаем время начала расчета
for (int k = 0; k < N; k++)
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
{
int max1 = (i+1)*M; //чтобы не считать много раз
for (int i1 = i*M; i1 < max1; i1++)
{
int max2 = (j+1)*M;
for (int j1 = j*M; j1 < max2; j1++)
{
int max3 = (k+1)*M;
for (int k1 = k*M; k1 < max3; k1++)
c[i1][j1] = c[i1][j1] + a[i1][k1]*b[k1][j1];
}
}
}
endTime = GetTickCount(); //засекаем конец расчета
printf("%7.0d мс\n", endTime - startTime); //выводим время работы
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "Russian");
float *a[n]; //исходная матрица A, как массив адресов массивов
float *b[n]; //исходная матрица B, как массив адресов массивов
float *c[n]; //выходная матрица C, как массив адресов массивов
//их выделим в стеке
//запросим динамическую память под элементы массивов
for(int i=0; i<n; i++) //по строкам
{
a[i] = (float*)_aligned_malloc(sizeof(float)*n, 16);
b[i] = (float*)_aligned_malloc(sizeof(float)*n, 16);
c[i] = (float*)_aligned_malloc(sizeof(float)*n, 16);
}
DWORD startTime, endTime; //переменные для подсчета времени работы
startTime = GetTickCount(); //засекаем начало инициализации исходных массивов
init(a, n, n); //инициируем массив A случайными числами
init(b, n, n); //инициируем массив B случайными числами
endTime = GetTickCount(); //конец инициализации
printf("Инициализация массивов: %7.0d мс\n", endTime - startTime); //время работы в милисекундах
//далее отрабатываем расчет умножения матриц
// с разным количеством блоков
CalcMatrix(a, b, c, n, 1); //1 блок из 1000 элементов
CalcMatrix(a, b, c, n, 2); //2 блока из 500 элементов
CalcMatrix(a, b, c, n, 4); //4 блока из 250 элементов
CalcMatrix(a, b, c, n, 5); //5 блоков из 200 элементов
CalcMatrix(a, b, c, n, 8); //8 блоков из 125 элементов
CalcMatrix(a, b, c, n, 10); //10 блоков из 100 элементов
CalcMatrix(a, b, c, n, 20); //20 блоков из 50 элементов
CalcMatrix(a, b, c, n, 25); //25 блоков из 40 элементов
CalcMatrix(a, b, c, n, 40); //40 блоков из 25 элементов
CalcMatrix(a, b, c, n, 50); //50 блоков из 20 элементов
CalcMatrix(a, b, c, n, 100); //100 блоков из 10 элементов
CalcMatrix(a, b, c, n, 125); //125 блоков из 8 элементов
CalcMatrix(a, b, c, n, 200); //200 блоков из 5 элементов
CalcMatrix(a, b, c, n, 250); //250 блоков из 4 элементов
CalcMatrix(a, b, c, n, 500); //500 блоков из 2 элементов
CalcMatrix(a, b, c, n, 1000); //1000 блоков из 1 элемента
printf("Нажмите на любую клавишу для выхода ");
_getch();
for(int i=0; i<n; i++) //освобождаем память
{
_aligned_free(a[i]);
_aligned_free(b[i]);
_aligned_free(c[i]);
}
return 0;
}[/code]
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен