Оптимизация циклов for для массивов в C99 с различной индексацией - PullRequest
Новая
       16

Оптимизация циклов for для массивов в C99 с различной индексацией

0 голосов
/ 08 августа 2010

Я хочу ускорить умножение массива в C99.

Это оригинал для петель: 

for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            total[j]+= w[j][i] * x[i];
        }
    }

Мой босс попросил меня попробовать это, но это не улучшило скорость: 

for(int i=0;i<n;i++) {
        float value = x[i];
        for(int j=0;j<m;j++) {
            total[j]+= w[j][i] * value;
        }
    }

Есть ли у вас другие идеи (кроме openmp, которые я уже использую) о том, как я мог бы ускорить эти циклы for? Я использую:

gcc -DMNIST=1 -O3 -fno-strict-aliasing -std=c99 -lm -D_GNU_SOURCE -Wall -pedantic -fopenmp

Спасибо!

Ответы [ 4 ]

2 голосов
/ 08 августа 2010

Одна из теорий заключается в том, что тестирование на ноль быстрее, чем тестирование на j<m. Так что с помощью цикла от j=m до j>0 теоретически вы можете сэкономить несколько наносекунд на цикл. Однако, как показал недавний опыт, это не имеет для меня никакого значения, поэтому я думаю, что это не относится к текущим процессорам.

Другая проблема связана с разметкой памяти: если ваш внутренний цикл обращается к фрагменту памяти, который не распределен, но непрерывен, скорее всего, у вас будет больше преимуществ от самого низкого кеша, доступного в вашем ЦП.

В вашем текущем примере может помочь переключение раскладки w с w[j][i] на w[i][j]. Также поможет выравнивание ваших значений на границах 4 или 8 байтов (но вы обнаружите, что это уже относится к вашим массивам)

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

1 голос
/ 08 августа 2010

Прямо сейчас каждые две последовательные внутренние операции (т.е. total[j]+= w[j][i] * x[i]) записывают в разные местоположения и читают из удаленных местоположений. Вы можете получить некоторую производительность, локализуя операции чтения и записи (таким образом, увеличивая нагрузку на внутренний кэш), например, переключая цикл j и цикл i, чтобы цикл j был внешним i петля внутренняя.

Таким образом, вы будете локализовать чтение и запись:

  • Запись в память будет в одно и то же место для всех i с.
  • Чтение из памяти будет последовательным для w[j][i] и x[i].

Подведем итог: 

for(int j=0;j<m;j++) {
    for(int i=0;i<n;i++) {
        total[j]+= w[j][i] * x[i];
    }
}
0 голосов
/ 31 августа 2010

Если вы знаете, что x, total и w не дублируют друг друга, вы можете получить довольно ощутимое усиление, переставив индексы цикла и избегая записи в total[j] каждый раз через цикл: 

for(int j=0;j<m;j++) {
    const float * const w_j = w[j];      
    float total_j = 0;
    for(int i=0;i<n;i++)
        total_j += w_j[i] * x[i];
    total[j] += total_j;
}

Тем не менее, BLAS является правильным ответом, в большинстве случаев для такого рода вещей.Наилучшее решение будет зависеть от n, m, времени предварительной выборки, глубины конвейера, развертывания цикла, размера строк вашего кэша и т. Д. Вы, вероятно, не хотите выполнять тот уровень оптимизации, который сделали другие людипод одеялом.

0 голосов
/ 31 августа 2010

Если это действительно имеет значение:

  1. Ссылка на настроенную библиотеку CBLAS. Есть из чего выбирать, некоторые бесплатные и некоторые коммерческие. Некоторые платформы уже имеют одну в системе.
  2. Замените код звонком на cblas_dgemv.

Это необычайно хорошо понимаемая проблема, и многие умные люди написали для нее хорошо настроенные библиотеки. Используйте один из них.

...