Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.423 RSS
←   Январь 2013   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.423 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Советник
Рейтинг: 11031
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4055
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2138
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1778
Дата выхода:25.01.2013, 09:30
Администратор рассылки:Киселёва Алёна aka Verena (Академик)
Подписчиков / экспертов:96 / 66
Вопросов / ответов:1 / 1

Консультация # 187107: Здравствуйте! У меня возникли сложности с таким вопросом: Написать программу умножения матриц размером 1500?1500. Оценить время выполнения вычислений для различных вариантов порядка следования вложенных циклов. Дать объяснение полученным результатам. 2) Написать программу умножения блочных матриц размером 1000?1000. Определить размер...

Консультация # 187107:

Здравствуйте! У меня возникли сложности с таким вопросом:
Написать программу умножения матриц размером 1500?1500.
Оценить время выполнения вычислений для различных вариантов порядка
следования вложенных циклов. Дать объяснение полученным результатам.
2) Написать программу умножения блочных матриц размером
1000?1000. Определить размер блоков, при котором достигается мини-
мальное время выполнения программы.

Результаты представить в виде таблицы представленной ниже

Дата отправки: 17.01.2013, 08:57
Вопрос задал: Евгений (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, Евгений!
Вот Вам программа, умножающая две матрицы разными способами,
используя разный порядок следования вложенных циклов.

Чем больше используются размещенные последовательно числа, тем
быстрее будет общая работа.
Кроме того, при последовательной выборке данных увеличивается
эффективность использования кэш-памяти.

Программа показывает, что быстрее всего работает порядок ikj, чуть хуже kij

Код :
#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;
}

Вторая программа:
Код :
#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;
}

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 20.01.2013, 02:58
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное