Как я могу уменьшить влияние производительности на транспонированный порядок доступа к массиву?

Question

У меня есть алгоритм, написанный на C, который обрабатывает пару двумерных массивов (например, с размером Y x X) для создания другого двумерного массива того же размера. Все три массива содержат 32-битные поплавки и имеют одинаковый размер Y x X, где Y может составлять несколько десятков, а X - около миллиона.

К сожалению:

• все массивы должны быть в row-major order (сканирование через X получает доступ к непрерывной памяти),
• алгоритм требует, чтобы внутренний цикл для сканирования по Y размерности.

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

Что я могу сделать для уменьшения влияния производительности на несмежные обращения к памяти?

(.. NB Это был long shot, но я пробовал различные образцы инструкций предвыборки, чтобы принести в наступающих колонн, но все безрезультатно)

Следующая (обновлена) код демонстрирует проблему:

#include <stdio.h> 
#include <stdlib.h> 

#define NX 1000000 
#define NY 30 

int main() { 
    float *a = malloc(sizeof(float) * NY * NX); 
    float *b = malloc(sizeof(float) * NY * NX); 
    float *c = malloc(sizeof(float) * NY * NX); 

    size_t y, x, offset; 
    float v; 

    for(x=0; x<NX; x++) { 
     v = 1; 
     for(y=0; y<NY; y++) { 
      offset = x + NX * y; 
      if(a[offset] < 0) { 
       v = 2; 
      } 
      c[offset] = v * b[offset]; 
     } 
    } 

    free(a); 
    free(b); 
    free(c); 
} 

На тестовой машине с процессором E5520 с частотой 2,27 ГГц это занимает ~ 1 с для выполнения, хотя это только чтение ~ 220 МБ и запись ~ 110 МБ.

Answer 1

Похоже, что ваш шаблон доступа не должен быть настолько вредным. Это заставляет меня задаться вопросом, является ли ваша реальная проблема branch prediction.

Обычно переносимый доступ к данным осуществляется в кусках, чтобы сохранить кеш здоровым, но ваш вход настолько короток на оси внутреннего цикла, что кэшированное чтение первой строки должно быть действительным к моменту, когда вы перейдете его в свою внешний контур.

У вас есть три массива 30 элементов высотой по ширине строки кэша, возможно, 128 байтов (я ожидаю меньше, но все меняется). Это всего лишь 12 КБ кеша, который вам нужен для того, чтобы верхняя строка оставалась резидентом.

Вы можете попробовать изменить v на небольшой массив и продолжить движение в вертикальных полосах. Даже если это фактически не помогло использовать ваш кеш, оно, по крайней мере, дало бы подсказку компилятору, что его можно оптимизировать с помощью SIMD.

Вы также можете попробовать эту опасную оптимизацию, чтобы устранить ветви:

for(x=0; x<NX; x++) { 
    uint32_t v = 0; 
    for(y=0; y<NY; y++) { 
     offset = x + NX * y; 
     v |= (((uint32_t *)a)[offset] & 0x80000000) >> 8; 
     ((uint32_t *)c)[offset] = ((uint32_t *)b)[offset] + v; 
    } 
} 

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