Кеш процессора

[Sobaka_ru]

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

Построить графики зависимости среднего времени обращения к элементу массива от числа фрагментов N. Использовать следующие параметры:
BlockSize = размер кэша данных 1 уровня (если неизвестно, то 8 KB),
Offset = 1 MB.
Число фрагментов N = 1…20.
По полученному графику определить степень ассоциативности кэш-памяти (какого-либо уровня). Сделать вывод о соответствии полученных результатов действительным параметрам кэш-памяти.

Указания по выполнению

1. Компилируйте программы с оптимизацией (используйте ключ /O2), чтобы переменные расположились на регистрах, и не происходило лишних обращений к памяти.
2. Для замера времени с большей точностью и меньшими накладными расходами используйте команду процессора rdtsc (смотрите пример ниже). Эта команда работает на процессорах Intel, а также на Athlon64/Opteron (Athlon/Duron не проверял; возможно, тоже работает). При ее использовании время на графиках отображайте в тактах.
3. В цикле обхода данных не должно быть «лишних» обращений к памяти, т.е. используемые переменные должны быть расположены в регистрах. Если график получается «непохожим», то либо обход выполняется неправильно, либо происходят лишние обращения к памяти.
4. Не путайте единицы измерения массивов: элементы и байты. Один элемент – 4 байта.
5. «Случайный» обход массива должен быть действительно случайным. Наличие какой-либо закономерности обхода может сказаться на результатах. Кроме того, следите, чтобы в циклический список попали все элементы массива.
6. При оптимизации компилятор может выкинуть «ненужные» с его точки зрения куски кода программы. Например, если после приведенного выше фрагмента обхода массива значение переменной k никак не используется, то компилятор может выкинуть весь цикл. Явный признак такой оптимизации – время обхода очень маленькое и не зависит от размера массива. Чтобы этого избежать, можно после замера времени добавить команды, гарантирующие «полезность» нужного нам кода. Например: if (k==12345) printf(“”); Здесь компилятор увидит, что переменная k как-то используется дальше, и не станет выкидывать цикл, вычисляющий ее значение.

Примечания

• Графики можно строить в Excel. Для удобства переноса данных в Excel лучше выводить значения в две колонки: размер массива и время, а при запуске перенаправить вывод в txt-файл. Например: prog.exe > result.txt В результате выполнения этой команды весь текст, который должен был быть выведен программой prog.exe на экран, будет помещен в файл result.txt (перенаправление вывода). Текстовый файл (*.txt) можно открыть в Excel-е (а не набирать все результаты вручную).
• Полученные графики могут оказаться сильно «замусоренным» посторонними задачами (много высоких пиков). В этом случае следует закрыть все возможные работающие программы. Если это не поможет, то можно попробовать запустить программу на более «спокойной» машине.

Пример использования команды rdtsc для измерения времени:
// Проверено в MS Visual С++ 6.0

#include<stdio.h>
#define FREQ 1995 // Частота процессора, MHz
#define N 10000
#define DUP 10
// функция возвращает значение счетчика тактов процессора
unsigned long tick() 
{ 
  __asm rdtsc 
}
int main(int argc, char* argv[])
{ 
  long a[N],i,k,n;
  unsigned long t1,t2;
  double t;
  for (i=0;i<N-1;i++) a[i]=i+1;
  a[i]=0;
  t1=tick(); // начало замера
  for (i=0,k=0;i<N*DUP;i++) k=a[k];
  t2=tick(); // конец замера
  if (k==12345) printf("");
  t=(double)(t2-t1)/(N*DUP);
  printf("Element access average time:\n");
  printf("  ticks: %lf\n",t);      // такты процессора
  printf("  usec : %lf\n",t/FREQ); // микросекунды
  return 0;
}

Помогите программу написать...