Уменьшить задержки с хроническими промахами в кеш.

Если это важно, то нужно для архитектуры core 2 duo не ниже.

Есть функция, которая из гигантского массива (больше гига) считывает значение.

Код (Text):

1. unsigned char poluchaem(int& j0,int& j1,int& j2,int& j3)
2. {
3.    return massiv[j0][j1][j2][j3];
4. }

Индексы рассчитываются по сложному алгоритму и абсолютно не упорядочены. Функция вызывается очень часто, и дело усугубляется тем, что вынужден использовать тип char чтобы вписаться в размер оперативки. Есть такая же функция для записи.

Для эксперементов написал такую прогу.

Код (Text):

1. const int razmer=100;
2. unsigned char massiv_0[razmer][razmer][razmer][razmer];
3. unsigned char massiv_1[razmer][razmer][razmer][razmer];
4. unsigned char massiv_2[razmer][razmer][razmer][razmer];
5.  
6. //набиваем все массивы случайными числами;
7.  
8. QueryPerformanceCounter(&begin_time);
9. for(int i=0;i<1024*1024;i++)
10. {
11.     int j0=rand()%razmer;
12.     int j1=rand()%razmer;
13.     int j2=rand()%razmer;
14.     int j3=rand()%razmer;
15.     //бог с ним с переполнением, просто для примера
16.     massiv_0[j0][j1][j2][j3]=
17.     massiv_1[j1][j2][j3][j0]+
18.     massiv_2[j2][j3][j0][j1];
19. }
20. QueryPerformanceCounter(&end_time);

Без учета задержек все должно выполняться с одинаковой скоростью не зависимо от razmer. По факту: при росте общего размера массивов от размера L1 кеша до ГБ скорость падает больше чем в 100 раз.

Возвращаясь к первоначальной функции. Можно с момента получения индексов и высчитывания указателя написать много кода, а потом уже обратиться к значению. Нашел такую функцию, но что-то не помогает.
void _mm_prefetch(char * p , int hint ); // hint = _MM_HINT_T0, _MM_HINT_T1, _MM_HINT_T2, _MM_HINT_NTA

Типа получится

Код (Text):

1. unsigned char* ptr=index(j0,j1,j2,j3);
2. _mm_prefetch(ptr,_MM_HINT_T0);
3. …
4. //много кода
5. …
6. unsigned char a=*ptr;

В ассемблере только начальные знания, но, т.к. очень нужно, разберусь.

Спасибо.

 

Дружок, какие промахи в кэш, когда ты прыгаешь по всему массиву?
Дай бог, что бы страничных прерываний не было.

 

меняйте алгоритм.

 

Обязательно использовать четырёхмерный массив?

Посмотри какой из индексов чаще меняется в твоей программе - он должен быть последним. То есть структура массива должна быть такой, чтобы часто запрашиваемые данные распологались ближе друг к другу в памяти. Тогда в большинстве случаев они будут браться из кеша.

 

Алгоритм поменяю, если смогу. Хочется тут разобраться

_mm_prefetch(ptr,_MM_HINT_T0);

Просто про эту функцию подскажите, как ее правильно использовать на core 2 duo.
Какой лучше 2 параметр и нужно ли выравнивать ptr или процессор сам это делает.

Пока придумал такого плана

Код (Text):

1. const int razmer=100;
2. const int chislo_progonov=1024*1024;
3. const int razmer_bufera_predviborki=4;//поиграться с этим коэф.
4.  
5. unsigned char* ptr_0[razmer_bufera_predviborki];
6. unsigned char* ptr_1[razmer_bufera_predviborki];
7. unsigned char* ptr_2[razmer_bufera_predviborki];
8.  
9. //тут случайно, на самом деле алгоритм
10. //но заранее не предсказуемо
11. void generator(int& j0,int& j1,int& j2,int& j3)
12. {
13.     j0=rand()%razmer;
14.     j1=rand()%razmer;
15.     j2=rand()%razmer;
16.     j3=rand()%razmer;
17. };
18.  
19. //предвыборка
20. void predviborka(int& i)
21. {
22.     int& j0,j1,j2,j3;
23.     generator(j0,j1,j2,j3);
24.  
25.     ptr_0[i]=&massiv_0[j0][j1][j2][j3];
26.     _mm_prefetch(ptr_0[i],_MM_HINT_T0);
27.  
28.     ptr_1[i]=&massiv_1[j1][j2][j3][j0];
29.     _mm_prefetch(ptr_1[i],_MM_HINT_T0);
30.  
31.     ptr_2[i]=&massiv_2[j2][j3][j0][j1];
32.     _mm_prefetch(ptr_2[i],_MM_HINT_T0);
33. };
34.  
35. //начало в холостую
36. for(int i=0;i<razmer_bufera_predviborki;i++)
37. {
38.     predviborka(i);
39. };
40.  
41. //должно быть быстрее
42. for(int i=0;i<chislo_progonov-razmer_bufera_predviborki;i++)
43. {
44.     //бог с ним с переполнением, просто для примера
45.     *ptr_0[i%razmer_bufera_predviborki]=
46.     *ptr_1[i%razmer_bufera_predviborki]+
47.     *ptr_2[i%razmer_bufera_predviborki];
48.     predviborka(i+razmer_bufera_predviborki);
49. }
50.  
51. //досчитать
52. for(int i=chislo_progonov-razmer_bufera_predviborki;i<chislo_progonov;i++)
53. {
54.     //бог с ним с переполнением, просто для примера
55.     *ptr_0[i%razmer_bufera_predviborki]=
56.     *ptr_1[i%razmer_bufera_predviborki]+
57.     *ptr_2[i%razmer_bufera_predviborki];
58. }

 

sashaz

Как говориться, должно, да не обязано
Префетч рулит только на достаточно большой дистанции. Говоря твоими словами, нужно "много кода" между префетчами, причем этот код должен обращаться только к уже загруженным в кэш данным (или вообще не обращаться). В этом случае префетч позволяет заблоговременно выдавать процессору запрос на подгрузку данных из ОЗУ и выполнять ее полностью или частично во время исполнения кода. В твоем же примере весь код состоит из нескольких элементарных действий, выполняемых за единицы тактов, в то время как на загрузку каждого из 3-х операндов со случайными адресами требуется не менее сотни-другой тактов. Т.е. время исполнения кода пренебрежимо мало по сравнению с временем ожидания загрузки и префетч здесь практически ничего не даст.
PS: При чисто случайном доступе к объему данных, намного превышающему размер L2, ловить нечего. Нужно уточнить задачу и попытаться как-то упорядочить данные