Форум программистов, компьютерный форум CyberForum.ru

Кеш процессора - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.73
Sobaka_ru
2 / 2 / 0
Регистрация: 16.12.2010
Сообщений: 75
18.10.2011, 12:19     Кеш процессора #1
Задание
Написать программу, многократно выполняющую чтение элементов массива заданного размера. Элементы массива должны представлять собой связный циклический список, в котором значение очередного элемента представляет собой номер следующего. Тип элементов массива: 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
C++
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
#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;
}
Помогите программу написать...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2011, 12:19     Кеш процессора
Посмотрите здесь:

Дирректива процессора C++
Имитация работы процессора C++
C++ Директив процессора
C++ Производительность CPU, КЕШ, многопоточность
C++ Быстродействие процессора?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LosAngeles
Заблокирован
18.10.2011, 13:01     Кеш процессора #2
для начала неплохо бы проверить доступна ли вообще rdtsc, в одном из cr есть кажись битик который разрешает команду на любом кольце или только на нулевом, если он равен единице то накроется твоя программулина медным тазом
Bers
Заблокирован
18.10.2011, 13:10     Кеш процессора #3
Цитата Сообщение от LosAngeles Посмотреть сообщение
для начала неплохо бы проверить доступна ли вообще rdtsc, в одном из cr есть кажись битик который разрешает команду на любом кольце или только на нулевом, если он равен единице то накроется твоя программулина медным тазом
на многоядерниках глючит
LosAngeles
Заблокирован
18.10.2011, 13:36     Кеш процессора #4
вроде как в winapi есть докучи всяких функций в том числе __rdtsc() лучше ими пользоваться
C
1
2
3
4
5
LARGE_INTEGER cpuFreq;
    if (QueryPerformanceFrequency(&cpuFreq))
    {
        cout << "cpu freq is " << cpuFreq.QuadPart << endl;
    }
не знаю правда что этот код считает, но у меня всегда одно число выдаёт, но у меня же ноутбук с i5 Turbo Boost, не похоже это на правду. Возможно там ещё какие функции интересные есть, я в виндовых апыях не шарю, так что удачного курения мсдн тебе)
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
18.10.2011, 15:30     Кеш процессора #5
QueryPerformanceFrequency - частота счётчика. Вообще не обязана равняться частоте процессора, но обычно врлде равняется.
QueryPerformanceCounter - сам счётчик.
Sobaka_ru
2 / 2 / 0
Регистрация: 16.12.2010
Сообщений: 75
27.10.2011, 14:59  [ТС]     Кеш процессора #6
То что вы тут писали ваще ничего из этого не понял... Ну так что с прогой???

Добавлено через 1 час 16 минут
Цитата Сообщение от LosAngeles Посмотреть сообщение
для начала неплохо бы проверить доступна ли вообще rdtsc, в одном из cr есть кажись битик который разрешает команду на любом кольце или только на нулевом, если он равен единице то накроется твоя программулина медным тазом
Это не моя программа, это дается в методичке как пример, а саму программу нужно написать...

Добавлено через 19 часов 34 минуты
C
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <intrin.h>
#include <windows.h>
 
// следующий размер массива: взято из lat_mem_rd
int step(int k) {
    if(k < 1024) k = k * 2;
    else if(k < 4*1024) k += 1024;
    else {
        int s;
        for (s = 32*1024; s <= k; s *= 2)   ;
        k += s / 16;
    }
    return k;
}
 
#define TWICE(x) x x
#define MB (1024*1024)
 
int main()
{
    // ОПРЕДЕЛЕНИЕ ТАКТОВОЙ ЧАСТОТЫ
    LARGE_INTEGER perfcnt1, perfcnt2; __int64 tsc1, tsc2;
    QueryPerformanceCounter(&perfcnt1); tsc1=__rdtsc();
    // нагрузка (не обязательно нашим процессом)
    Sleep(500);
    // замер
    QueryPerformanceCounter(&perfcnt2); tsc2=__rdtsc();
    perfcnt2.QuadPart -= perfcnt1.QuadPart;
    QueryPerformanceFrequency(&perfcnt1);
    // результат
    const double MHz = (double)(tsc2-tsc1)*perfcnt1.QuadPart/perfcnt2.QuadPart/1e6;
    printf("Clock rate: %.0f MHz\n", MHz);
 
    // ЗАМЕР ВРЕМЕНИ ДОСТУПА К ПАМЯТИ
    // информация о горизонтальном сегменте графика
    typedef struct segment_t segment;
    struct segment_t {
        int size_l, size_r;  // размеры краёв, в байтах
        double level, total; // время доступа, в циклах
        int width;           // ширина, в замеренных точках
        segment* next;
    };
    // график с постоянной величиной шага
    typedef struct {
        int step_size_bytes;
        segment data;
    } segments;
 
    // пробуем шесть величин шага
    segments allsegs[]={{128}, {256}, {512}, {1024}, {2048}, {4096}, {0}};
    for(segments *cursegs = allsegs;
            int step_size = cursegs->step_size_bytes/sizeof(void*);
            cursegs++) {
 
        printf("\rTesting stride: %d          \n", cursegs->step_size_bytes);
 
        int iters = 1<<28; // обращений к массиву на каждом проходе
        int state = 0;     // начальное состояние - снаружи ступеньки
        segment* curseg = &(cursegs->data); // текущий сегмент
 
        // предыдущие два размера массива, и результаты на них
        int a_size_bytes, b_size_bytes;
        double a, b; 
 
        // на каждой итерации данного цикла выделяется всё большая память
        for(int arr_size_bytes = 1<<12; arr_size_bytes <= 1<<29;
                                        arr_size_bytes = step(arr_size_bytes)) {
            const int arr_size = arr_size_bytes / sizeof(void*);
 
            void **x = (void**)malloc(arr_size_bytes); // выделяем память
 
            // заполняем память указателями с шагом step_size
            int k;
            for(k = 0; k < arr_size; k += step_size) {
                x[k] = x + k + step_size;
            }
            x[k-step_size] = x;
            const int arr_iters = k / step_size; // число заполненных элементов массива
 
            // не меньше четырёх полных проходов по массиву
            if(iters < 4*arr_iters) iters = 4*arr_iters;
 
            // указатель для обращения к массиву в основном цикле
            void **p = x;
 
            // счётчик тактов до выполнения команд
            const __int64 ticks_start = __rdtsc();
 
            // основной цикл -- его время выполнения мы замеряем
            for(int j = 0; j < iters; j+=256) {
                TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE(TWICE( p=(void**)*p; ))))))))
            }
 
            // счётчик тактов после выполнения команд
            const __int64 ticks_end = __rdtsc();
 
            // количество затраченных тактов процессора, в среднем на одно обращение
            // множим на !!p (единицу), чтобы оптимизатор не выкинул её как неиспользуемую
            const double cycles = (double)!!p * (ticks_end-ticks_start) / iters;
 
            // отображение результатов
            printf("\r%f MB - %.2f cycles    ", (double)arr_size_bytes/MB, cycles);
 
            free(x); // освобождаем память
 
            // скорректируем число итераций, чтобы каждый проход занимал меньше секунды
            while(cycles/MHz*iters > 1e6) iters >>= 1;
 
            // левый край ступеньки?
            if(!state && (curseg->width>2) && (fabs(a-curseg->level)<(a*.1)) &&
                    (b>(curseg->level*1.1)) && (cycles>(curseg->level*1.1))) {
                curseg->size_r = a_size_bytes;
                curseg = curseg->next = (segment*)calloc(1, sizeof(segment));
                state = 1;
                b = 0; // правый край должен быть строго правее левого
            }
            // правый край ступеньки?
            if(state && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) {
                curseg->size_l = a_size_bytes;
                state = 0;
            }
            // первые две точки учитываем всегда
            if(!state && ((curseg->width<=2) || (fabs(cycles-curseg->level)<cycles*.1))) {
                curseg->total += cycles;
                curseg->width++;
                curseg->level = curseg->total / curseg->width;
            }
            // приняли широкий всплеск за ступеньку?
            if(!state && (cycles<curseg->level*.9) && (fabs(cycles-a)<(a*.1)) && (fabs(cycles-b)<(b*.1))) {
                curseg->total = a + b + cycles;
                curseg->width = 3;
                curseg->level = curseg->total / curseg->width;
            }
 
            // сдвигаем историю
            a_size_bytes = b_size_bytes; b_size_bytes = arr_size_bytes;
            a = b; b = cycles;
        }
    }
 
    // АНАЛИЗ ПОЛУЧЕННЫХ ДАННЫХ
    int TLB = 0; // последний проанализированный уровень -- TLB?
    for(int cache_level = 1;;cache_level++) {
 
        // размер и время доступа к кэшу
        int cache_size = allsegs[0].data.size_r, step_count = 0;
        if(!cache_size) break; // самый высший уровень (основная память)
 
        double latency, total = 0;
        if(TLB) // время доступа к кэшу следующего уровня уже определено
            cache_level--;
        else
            latency = allsegs[0].data.level;
 
        int less=0, same=0, more=0; // для определения медианы "на ходу"
 
        // для всех испробованных размеров шага
        for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) {
            segment* next = cursegs->data.next; // следующий уровень кэша
            if(!next) { // с текущим размером шага, натыкаемся на основную память
                printf("Missing results for L%d! Step size %d, array size %f MB\n",
                        cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_l/MB);
                cache_size = 0;
                break;
            }
            // если следующий уровень мало отличается, объединим
            while(fabs(cursegs->data.level-next->level)<cursegs->data.level*.2) {
                cursegs->data.size_r = next->size_r;
                cursegs->data.total += next->total;
                cursegs->data.width += next->width;
                cursegs->data.level = cursegs->data.total / cursegs->data.width;
                cursegs->data.next = next->next;
                free(next);
                next = cursegs->data.next;
                // реинициализация
                if(cursegs==allsegs) {
                    cache_size = cursegs->data.size_r;
                    if(!TLB) latency = cursegs->data.level;
                }
            }
            // если очередная ступенька совпала с расчётной
            if(cursegs->data.size_r == cache_size)
                same++;
            // если очередная ступенька чуть отличается от расчётной
            else if(cursegs->data.size_r == step(cache_size))
                more++;
            else if(step(cursegs->data.size_r) == cache_size)
                less++;
            // если ступенька намного левее расчётной: эффект TLB
            else if(cursegs->data.size_r < cache_size/2) {
                // измеренный до сих пор размер -- ненастоящий
                cache_size = cursegs->data.size_r;
                more = less = 0; same = 1;
                // добавим фиктивные ступеньки с тем же уровнем
                for(segments *prevsegs = allsegs; prevsegs<cursegs; prevsegs++) {
                    segment* second = (segment*)malloc(sizeof(segment));
                    *second = prevsegs->data;
                    prevsegs->data.next = second;
                    prevsegs->data.size_r = second->size_l = cache_size;
                }
            }
            // если отличающихся ступенек больше, чем расчётных
            if(less>same) {
                cache_size = cursegs->data.size_r;
                more = same; same = less; less = 0;
            } else if (more>same) {
                cache_size = cursegs->data.size_r;
                less = same; same = more; more = 0;
            }
            if(!TLB && fabs(latency-cursegs->data.level)<latency*.1) {
                total += cursegs->data.level;
                latency = total / ++step_count;
            }
        }
        if(!cache_size) break; // определение размера кэша не удалось
 
        // ассоциативность кэша и параметры TLB
        int min_way_size = 0, max_way_size = 0, next_step_at = 2*cache_size;
        // задержка, добавляемая временем доступа к TLB
        double additional = (allsegs[0].data.next->level - latency) / 2;
        if(additional<0) additional=0; // в пределах погрешности
        TLB = 1; // считаем за TLB, пока не убедимся в противном
        for(segments *cursegs = allsegs; cursegs->step_size_bytes; cursegs++) {
            segment* next = cursegs->data.next; // следующий уровень кэша
            // если все веи заполнены, левые границы ступенек совпадают
            if(cursegs->data.size_r <= cache_size) {
                if(max_way_size && (max_way_size != next->size_l - cache_size)) {
                    printf("Inconsistent results for L%d! Step size %d, array size %f MB\n",
                            cache_level, cursegs->step_size_bytes, (double)next->size_l/MB);
                }
                min_way_size = cursegs->step_size_bytes; // шаг не больше вея
                max_way_size = next->size_l - cache_size; // размер вея -- ширина ступеньки
                // если ступенька не вертикальная, значит известен точный размер вея
                if(next->size_l > step(cache_size)) min_way_size = max_way_size;
            // при недополнении веев, ступенька сдвинута вдвое вправо
            } else if(cursegs->data.size_r > step(cache_size)) {
                if(cursegs->data.size_r != next_step_at)
                    printf("Inconsistent results for L%d! Step size %d, array size %f MB\n",
                            cache_level, cursegs->step_size_bytes, (double)cursegs->data.size_r/MB);
                if (!max_way_size)
                    max_way_size = cursegs->step_size_bytes / 2; // шаг как минимум в два вея
                next_step_at *= 2; // следующая ступенька должна быть ещё вдвое правее
            }
 
            // похоже на TLB, если дополнительная задержка удваивается при удвоении шага
            double new_additional = cursegs->data.next->level - latency;
            if((fabs(new_additional - additional*2) < new_additional*.1) || (additional<latency*.1))
                additional = new_additional;
            else // не похоже на TLB
                TLB = 0;
 
            // закончили с первым сегментом
            cursegs->data = *next;
            free(next);
        }
        if(TLB)
            printf("TLB size: %d, latency: %.2f cycles (%.2f ns)\n"
                   "    way size: min. %d, max. %d\n",
                cache_size/4096, additional/2, (additional/2)/MHz*1000,
                min_way_size/4096, max_way_size/4096);
        else
            printf("L%d size: %d KB, latency: %.2f cycles (%.2f ns)\n"
                   "   way size: min. %d KB, max. %d KB\n",
                cache_level, cache_size/1024, latency, latency/MHz*1000,
                min_way_size/1024, max_way_size/1024);
    }
    return 0;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}
 Комментарий модератора 
Используйте теги форматирования кода!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.02.2015, 20:27     Кеш процессора
Еще ссылки по теме:

C++ Получить температуру процессора
C++ Кэш процессора (__cpuid) C++
C++ Не обновляется кеш для потоков

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AndrSlav
44 / 44 / 6
Регистрация: 20.12.2013
Сообщений: 241
01.02.2015, 20:27     Кеш процессора #7
Здравствуйте.
На просторах инета нашел код для определения размера кэша L2.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int _tmain(int argc, _TCHAR* argv[])
{    
    int CPUInfo[4] = {-1};
    int nCacheLineSize = 0;
    int nL2Associativity = 0;
    int nCacheSizeK = 0;
 
__cpuid(CPUInfo, 0x80000006);
    nCacheLineSize = CPUInfo[2] & 0xff;
    nL2Associativity = (CPUInfo[2] >> 12) & 0xf;
        nCacheSizeK = (CPUInfo[2] >> 16) & 0xffff;
 
    printf_s("Cache Line Size = %d\n", nCacheLineSize);
    printf_s("L2 Associativity = %d\n", nL2Associativity);
    printf_s("Cache Size = %dK\n", nCacheSizeK);
 
   char ch;
   std::cin>>ch;
 
return  0;
}
А как для L1 и L3? С ассемблером дела никогда не имел. В инете же нашел описание откуда берутся данные для L1 и L3, но как их достать (код)?

Добавлено через 28 минут
p.s. функция __cpuid:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void __cpuid(int* CPUInfo, int InfoType)
{
   asm {
    push ebx
    push esi
    mov eax, InfoType
    cpuid
    mov esi, CPUInfo
    mov [esi], eax
    mov [esi + 4], ebx
    mov [esi + 8], ecx
    mov [esi + 12], edx
    pop esi
    pop ebx
   }
}
Добавлено через 1 час 45 минут
Методом тыка попробовал (для L3), но нули выводит:
C++
1
2
3
4
__cpuid(CPUInfo, 0x80000006);
    nCacheLineSize = CPUInfo[3] & 07777;//0xff;
    nL2Associativity = (CPUInfo[3] >> 12) & 077;//0xf;
    nCacheSizeK = (CPUInfo[3] >> 18) & 07777777;//0xffff;
Yandex
Объявления
01.02.2015, 20:27     Кеш процессора
Ответ Создать тему
Опции темы

Текущее время: 12:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru