Проведение вычислительных экспериментов

Для последующего тестирования ускорения работы параллельного алгоритма необходимо провести эксперименты по вычислению времени выполнения последовательного алгоритма. Анализ времени выполнения алгоритма разумно проводить для достаточно больших объектов. Задавать элементы больших матриц и векторов будем при помощи датчика случайных чисел. Для этого реализуем еще одну функцию задания элементов RandomDataInitialization (датчик случайных чисел инициализируется текущим значением времени):

// Function for random initialization of objects’ elements

void RandomDataInitialization (double* pMatrix,double* pVector,int Size) {

int i, j; // Loop variables

srand(unsigned(clock()));

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

pVector[i] = rand()/double(1000);

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

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

}

}

Будем вызывать эту функцию вместо ранее разработанной функции DummyDataInitialization,

которая генерировала такие данные, что можно было легко проверить правильность работы алгоритма:

// Function for memory allocation and data initialization

void ProcessInitialization (double* &pMatrix, double* &pVector,

double* &pResult, int Size) {

// Size of initial matrix and vector definition

<…>

// Memory allocation

<…>

// Random data initialization

RandomDataInitialization(pMatrix, pVector, Size);

}

Скомпилируйте и запустите приложение. Убедитесь в том, что данные генерируются случайным образом.

Для определения времени можно воспользоваться стандартной функцией языка С, которая

позволяет узнать время работы программы или её части: time_t clock(void);

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

Реализуем функцию GetTime(), которая позволяет более точно замерить время выполнения участка кода с использованием функций библиотеки WinAPI:

// Function that converts numbers form LongInt type to double type

double LiToDouble (LARGE_INTEGER x) {

double result =

((double)x.HighPart) * 4.294967296E9 + (double)((x).LowPart);

return result;

}

// Function that gets the timestamp in seconds

double GetTime() {

LARGE_INTEGER lpFrequency, lpPerfomanceCount;

QueryPerformanceFrequency (&lpFrequency);

QueryPerformanceCounter (&lpPerfomanceCount);

return LiToDouble(lpPerfomanceCount)/LiToDouble(lpFrequency);

}

Функция GetTime возвращает текущее значение времени, которое отсчитывается от фиксированного момента в прошлом, в секундах. Следовательно, вызвав эту функцию два раза – до и после исследуемого фрагмента можно вычислить время его работы. Например, этот фрагмент вычислит время duration работы функции f().

double t1, t2;

t1 = GetTime();

f();

t2 = GetTime();

double duration = (t2-t1);

Добавим в программный код вычисление и вывод времени непосредственного выполнения умножения матрицы на вектор, для этого поставим замеры времени до и после вызова функции ResultCalculation:

// Matrix-vector multiplication

Start = GetTime();

ResultCalculation(pMatrix, pVector, pResult, Size);

Finish = GetTime();

Duration = (Finish-Start);

// Printing the result vector

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

PrintVector(pResult, Size);

// Printing the time spent by matrix-vector multiplication

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

Скомпилируйте и запустите приложение. Для проведения вычислительных экспериментов с большими объектами, отключите печать матриц и векторов (закомментируйте соответствующие строки кода). Проведите вычислительные эксперименты, результаты занесите в таблицу:

В результате проведенного анализа следует, что время выполнения вычислений для умножения матрицы на вектор может оценить при помощи следующего соотношения:

                                                          (1.2)

где n есть размерность матрицы, τ есть время выполнения одной вычислительной операции, β есть пропускная способность канала доступа к оперативной памяти.

Далее заполните таблицу сравнения реального времени выполнения со временем, которое может быть получено по формуле (1.2).