Определение числа регистров, доступных для локальных переменных подпрограммы. Определение размеров реально доступной для программы памяти, страница 2

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

                             p[i]++;

              return (int)benchmark_stop();

}

void mainLoop(int low, int high, int step)

{

              int size;

              void *ptr;

              ptr = malloc(high);

              if(!ptr)

              {

                             fprintf(stderr, "error: malloc()\n");

                             return;

              }

              for(size = low; size <= high; size += step)

              {

                             int t;

                             t = test(ptr, size);

                             printf("t(%d) = %d;\tt/size = %d\n", size, t, (1000*t)/size);

              }

}

main(int argc, char *argv[])

{

              int sizeLow, sizeHigh, sizeStep;

              if(argc != 5)

              {

                             fprintf(stderr, "error: command line takes four integer parameters\n");

                             fprintf(stderr, "low_size high_size step times_to_pass\n");

                             return;

              }

              sscanf(argv[1], "%d", &sizeLow);

              sscanf(argv[2], "%d", &sizeHigh);

              sscanf(argv[3], "%d", &sizeStep);

              sscanf(argv[4], "%d", &TIMES);

              printf("for(i = %d; i <= %d; i += %d)\n", sizeLow, sizeHigh, sizeStep);

              mainLoop(sizeLow, sizeHigh, sizeStep);

Контрольные вопросы:

1)  Для какого алгоритма замещения проявляется более резкое возрастание после линейной области – для алгоритма случайного замещения или LRU.

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

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

Задание.

1. Написать программу умножения двух квадратных матриц. Программа строится на двух вложенных циклах. Внешний пробегает по строкам первой матрицы и соответствующим им столбцам второй матрицы. Во вложенном цикле идет итерация по всем элементам выбранных во внешнем строк и столбцов. Добавить в программу код для замера времени умножения.

2. Осуществить замеры времени умножения для размеров матрицы от 100 до 1000 с шагом 100, сделать выводы, при каких размерах матрицы полностью умещаются в первичном, вторичном кэшах.

Размер матриц	Время исполнения программы, с

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

Пример решения для Alpha 21264.

Реализация базового варианта приводится в тексте 3, а варианта с транспонированием матрицы В – в тексте 4. На фиг. 4 показаны времена умножения для обоих реализаций при размере матриц от 50 до 1000 с шагом 50.

#include <stdio.h>

#include <stdlib.h>

#include <sys/time.h>

#include <unistd.h>

struct timeval      tv1, tv2, dtv;

struct timezone    tz;

void benchmark_start(void); // см. реализацию в тексте 1

long benchmark_stop(void); // см. реализацию в тексте 1

float M1[SIZE][SIZE];

float M2[SIZE][SIZE];

float MR[SIZE][SIZE];

void mulM()

{

              int x, y, i;

              for(y = 0; y < SIZE; y++)

              for(x = 0; x < SIZE; x++)

              {

                             MR[y][x] = 0.;

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

                                           MR[y][x] += M1[y][i] * M2[i][x];

              }

}

main()

{

              // код задания начальных значений матриц А и B опущен

              benchmark_start();

              mulM();

              printf("%d (msec.)\n", benchmark_stop());

#include <stdio.h>

#include <stdlib.h>

#include <sys/time.h>

#include <unistd.h>

struct timeval      tv1, tv2, dtv;

struct timezone    tz;

void benchmark_start(void); // см. реализацию в тексте 1

long benchmark_stop(void); // см. реализацию в тексте 1

float M1[SIZE][SIZE];

float M2[SIZE][SIZE];

float MR[SIZE][SIZE];

void rotateM1()

{

              int x, y, tmp;

              for(y = 0; y < SIZE; y++)

              for(x = y; x < SIZE; x++)

              {

                             tmp = M1[y][x];

                             M1[y][x] = M1[x][y];

                             M1[x][y] = tmp;

              }

}

void mulM()

{

              int x, y, i;

              for(y = 0; y < SIZE; y++)

              for(x = 0; x < SIZE; x++)

              {

                             MR[x][y] = 0.;

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

                                           MR[x][y] += M1[y][i] * M2[x][i];

              }

}

main()

{

              …

              benchmark_start();

              rotateM1();

              mulM();

              printf("%d (msec.)\n", benchmark_stop());

              …