Измерение задержки каждого уровня иерархии памяти

Question

Я хочу измерить латентность каждого уровня иерархии памяти, от L1 до основной памяти. Итак, я пытался понять программу 1-single.c на https://gist.github.com/jiewmeng/3787223. Почему индекс массива вычисляется по [(i * 16) & lengthMod]?

Значения [(i * 16) & lengthMod] и i * 16 всегда будут одинаковыми. Например,

i=0, [(i * 16) & lengthMod]=0, [i*16]=0 
i=1, [(i * 16) & lengthMod]=16, [i*16]=16 
i=2, [(i * 16) & lengthMod]=32, [i*16]=32 
i=3, [(i * 16) & lengthMod]=48, [i*16]=48 
i=4, [(i * 16) & lengthMod]=64, [i*16]=64 
i=5, [(i * 16) & lengthMod]=80, [i*16]=80 
......................................... 

Итак, я попытался запустить программу заменяющую [(я * 16) & lengthMod] с [я * 16] но, программа разбился каждый раз. Вот как я понял, что для этой побитовой операции должна быть веская причина. Может кто-нибудь объяснить, почему массив вычисляется по [(i * 16) & lengthMod]?

Answer 1

В цикле for:

for (i = 0; i < steps; i++) { 
    arr[(i * 16) & lengthMod] *= 10; 

steps составляет 256 МБ и arr[] имеют 4 МБ элементов. Таким образом, если вы измените доступ к массиву на arr[i * 16], вы быстро переполните массив и введите неопределенную область поведения.

В исходном коде у вас есть:

lengthMod = sizes[s] - 1; 

где sizes[] определяется проводить различные полномочия 2 до 4 Мб. Таким образом, когда вы делаете (i * 16) & lengthMod, вы гарантируете, что доступ к массиву никогда не будет равен или превышает sizes[s] и, следовательно, предотвратит появление переполнения массива.

Answer 2

В большинстве последних процессоров размер кэша линии 64Б

Элементы массива индексы 0,1,2 ... один элемент 4B размер Cacheline/один размер элемента = 64/4 = 16

каждая строка кэша имеет 16 элементов (=> 64B) Так будет, как массив от 0 до 15 элементов в cacheline 0 от 16 до 31 элементов в cacheline 1 32 до 47 элементов в cacheline 2 ...

Если вы получаете доступ к любому элементу, затем кэшли ne этого элемента будет доставлен в память.

Так доступ к элементу 0-й принести cacheline0 в кэш доступа к 16-элемент принесет следующий line1 кэш в кэш ..

Вам не нужно получить доступ ко всем элементам; вам просто нужно получить доступ к одному элементу строки кэша, чтобы принести все остальные 15 элементов!

Вот почему вы там видели * 16