Скорость проблемы с огромным массивом C с использованием 64-битной Visual C

Question

Мне нужно прочитать огромное количество данных в буфер (около 20 гигабайт).У меня есть 192 ГБ очень быстрого DDram, поэтому нет проблем с объемом памяти.Однако я обнаружил, что следующий код работает медленнее и медленнее, чем дальше он попадает в буфер.Профилировщик Visual C говорит мне, что 68% из 12-минутного времени выполнения находятся в 2 операторах внутри цикла в myFunc ().Я использую win7, 64-битную на очень быстрой dell с 2 процессорами, 6 физическими ядрами каждое (24 логических ядра), и все 24 ядра полностью работают при этом.

#define TREAM_COUNT 9000
#define ARRAY_SIZE ONE_BILLION

#define offSet(a,b,c,d) ( ((size_t)  ARRAY_SIZE * (a)) + ((size_t) TREAM_COUNT * 800 * (b)) + ((size_t) 800 * (c)) + (d) )

void myFunc(int dogex, int ptxIndex, int xtreamIndex, int carIndex)
{
     short *ptx  =  (short *) calloc(ARRAY_SIZE * 20, sizeof(short));

    #pragma omp parallel for
    for (int bIndex = 0; bIndex < 800; ++bIndex)
          doWork(dogex, ptxIndex, carIndex);
}

 void doWork(int dogex, int ptxIndex, int carIndex)
{

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex)
    {
         short ptxValue     =  ptx[ offSet(dogex, ptxIndex,   treamIndex, carIndex) ];
         short lastPtxValue =  ptx[ offSet(dogex, ptxIndex-1, treamIndex, carIndex) ];

         // ....
    }

}

Answer 1

Код выделил 20 блоков по одному миллиарду коротких целых.В 64-битном Windows-боксе короткое int составляет 2 байта.Таким образом, выделение составляет ~ 40 гигабайт.

Вы говорите, что 24 ядра, и все они исчерпаны.Код, как он есть, не показывает какой-либо параллелизм.Способ параллелизации кода может оказать глубокое влияние на производительность.Возможно, вам потребуется предоставить дополнительную информацию.

-

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

Во-первых, с двумя физическими процессорамииз шести ядер вы будете полностью насыщать свою шину памяти.Вероятно, у вас в любом случае есть архитектура NUMA, но в коде нет никакого контроля над тем, где размещается ваш calloc () (например, у вас может быть много кода, хранящегося в памяти, для достижения которого требуется несколько прыжков).

Гиперпоточностьвключенный.Это эффективно вдвое уменьшает размер кэша.Поскольку код привязан к шине памяти, а не к вычислениям, гиперпоточность вредна.(Сказав, что, если вычисления в любом случае постоянно находятся за пределами кеша, это не сильно изменится).

Неясно (так как некоторые / много?) Код удаляется, как осуществляется доступ к массиву имодель доступа и оптимизация этого шаблона для обеспечения оптимизации кэша являются ключом к производительности.

Что я вижу в том, как рассчитывается offset (), так это то, что код постоянно требует генерации новых поисков виртуальных и физических адресов- для каждого из которых требуется что-то вроде четырех или пяти обращений к памяти.Это само по себе невероятное быстродействие.

Мой основной совет - разбить массив на блоки размером 2 кеша, дать один блок каждому ЦП и позволить ему обрабатывать этот блок.Вы можете сделать это параллельно.На самом деле, вы можете использовать гиперпоточность для предварительной загрузки кэша, но это более продвинутый метод.

Answer 2

Я думаю, проблема этого кода в том, что у него есть схема доступа к памяти.Тот факт, что каждый поток обращается к памяти с большими (2 * 800 байт) приращениями, имеет 2 отрицательных последствия:

1. При запуске все потоки обращаются к одному и тому же фрагменту памяти, который предварительно загружен в кэш L2 / L3и эффективно используется каждым потоком.Позже потоки работают с немного другой скоростью и получают доступ к разным частям памяти, что приводит к очистке кэша (один поток загружает данные в кэш и удаляет оттуда данные, которые еще не были прочитаны другими потоками и нуждались в этом).В результате один и тот же фрагмент памяти считывается в кэш несколько раз (в худшем случае - 12 раз по количеству потоков в одном процессоре).Так как шина памяти относительно медленная, это замедляет всю программу.
2. Кэш L1 также используется не очень эффективно: только небольшая часть данных в каждой строке кэша используется ядрами ЦП.

Решение состоит в том, чтобы позволить каждому потоку последовательно обращаться к памяти (например, при обмене c и d аргументами макроса offSet(a,b,c,d)).

Answer 3

Вы должны попытаться получить доступ к массиву более линейным способом, если это возможно.Это, вероятно, вызывает чрезмерное количество кешей.

Answer 4

Эта оптимизация избавит от медленных умножений:

    ...
    int idx1 = offSet(dogex, ptxIndex,   0, carIndex);
    int idx2 = offSet(dogex, ptxIndex-1,   0, carIndex);

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex)
    {             
         short ptxValue     =  ptx[ idx1 ];
         short lastPtxValue =  ptx[ idx2 ];
         idx1+=800;
         idx2+=800;             ...