Arch_rgz_2
.pdfМинистерство образования и науки РФ Новосибирский государственный Технический Университет
Кафедра ПВТ
Лабораторная работа №2
по дисциплине «Архитектура ЭВМ и вычислительных систем»
Факультет: ПМИ Группа: ПМИ-22 Студенты: Суслов А.В.
Матвеев Т.И. Преподаватель: Маркова В.П.
Новосибирск
2013
Задание №2. Исследовать влияние порядка обхода данных в кэш-памяти на время работы программы.
Условие задачи:
1.Написать программу, многократно выполняющую чтение элементов массива заданного размера. Элементы массива представляют собой связный список, в котором значение очередного элемента представляет собой номер следующего. Способы обхода массива — прямой, обратный и случайный.
2.Построить графики зависимости среднего времени обращения к элементу массива от размера обрабатываемого массива для трех видов обхода. На графиках должно быть видно влияние кэш-памяти (1 и 2 уровня).
3.По результатам измерений сделать вывод о скорости различных способов
обхода массива, а также о размерах различных уровней кэш-памяти (насколько полученные результаты соответствуют действительности).
График зависимостей среднего времени доступа к одному элементу массива от общего размера массива:
Предположение о размерах кэша 1-го и 2-го уровней (на основе г рафика):
Кэш 1-го уровня (L1): 64 Кб Кэш 2-го уровня (L2): 512 К б
Команды компиляции и запуска:
Компиляция: g++ -march=i386 -O1 -o main1 -Wall main1.cpp
Запуск: ./main1
Исходный код программы:
#include <stdio.h> #include <stdlib.h> #include <time.h>
#ifdef WIN32
#include <intrin.h> #pragma intrinsic(__rdtsc)
typedef unsigned __int64 uint64_t; uint64_t rdtsc() { return __rdtsc(); }
#else
#include <stdint.h>
extern __inline__ uint64_t rdtsc() { uint64_t x;
__asm__ __volatile__ ("rdtsc" : "=A" (x) ); return x;
}
#endif
#define METHODS 3 // count of the methods of filling array #define RETRIES 5 // count of follows to get minimal time
// platform-specific supposed cache size #define L1 64
#define L2 1024
const int LRAND_MAX = RAND_MAX * RAND_MAX + RAND_MAX;
uint64_t tsc; // global counter value
// --------------------------------------
int lrand() // because of limitation of only 32767 for RAND_MAX
{
#if RAND_MAX > 0x7fff return rand();
#else
return rand() * RAND_MAX + rand(); // 2^30 + 2^15
#endif
}
bool follow(int *A, int N)
{
int b = 0, K = 0; do
{
b = A[b]; K++;
}
while(K != N); return b == 0;
}
void directed(int *A, int N)
{
for(int i = 0; i < N - 1; i++) A[i] = i;
A[N - 1] = 0;
}
void reversed(int *A, int N)
{
for(int i = 1; i < N; i++) A[i] = i - 1;
A[0] = N - 1;
}
void shuffled(int *A, int N) // my algorithm
{
bool *B = new bool[N];
for(int i = 0; i < N; i++) // init
{
A[i] = -1; // any never-will-be value B[i] = true;
}
B[0] = false;
int i = 0; int b;
for(int j = 0; j < N - 1; j++)
{
do
{
b = lrand() % N;
}
while(!( (b != i) && B[b] ));
A[i] = b; B[b] = false; i = b;
}
A[i] = 0;
delete B;
}
void fillByMethod(int *A, int N, int a)
{
if(a < 0 || a >= METHODS) printf("Method #%d is not available\n", a); else
switch(a)
{
case 0:
directed(A, N);
break;
case 1:
reversed(A, N);
break; case 2:
shuffled(A, N);
break;
}
}
void timerUp() // we use rdtsc there only
{
tsc = rdtsc();
}
uint64_t timerDown()
{
return rdtsc() - tsc;
}
uint64_t timedWork(int *A, int N)
{
follow(A, N); // warm-up uint64_t r = 0, v = 0;
for(int i = 0; i < RETRIES; i++)
{
timerUp(); follow(A, N);
v = timerDown();
if(r == 0 || r > v) r = v;
}
return r;
}
int main()
{
FILE *f = fopen("output.txt", "w");
srand(time(0)); // some init int r[METHODS];
for(int i = 1; i < L2 * 2; i++) // Размер массива — от 1 КБайта с шагом 1 КБайт
{
int N = i * 256; // 256 = 1024 / sizeof(int)
int *A = new int[N];
for(int j = 0; j < METHODS; j++)
{
fillByMethod(A, N, j);
r[j] = (int)timedWork(A, N) / N;
}
fprintf(f, "%d\t%d\t%d\t%d\n", i, r[0], r[1], r[2]);
delete A;
}
fclose(f);
#ifdef WIN32 system("pause");
#endif
return 0;
}