направление итерации в массиве
Скажем, у нас есть два массива a а также b фундаментального типа (скажем, float) и нам нужно рассчитать a[i] + b[i] за каждый действительный индекс i, а также сохранить результат. Каков наилучший способ перебора массивов для максимизации попаданий в кэш? Это спереди назад, сзади спереди или что-то еще?
Решение
Для такого рода операций вы должны использовать автоматическую векторизацию вашего компилятора. Итерация маленькая i к большому i, Кроме того, ответ зависит от того, что вы подразумеваете под «сохранить результат» и число n предметов предметов, которые вы собираетесь перебрать.
Если ты имеешь ввиду c[i] = a[i] + b[i] а также n не слишком маленький, тогда автоматический векторизатор вашего компилятора оптимизирует это лучше всего без каких-либо изменений. Даже MSVC сделает это правильно (по крайней мере, для SSE). Ваш компилятор должен будет сделать некоторые корректировки для n, не кратного 4 (или 8 для AVX) и выравнивания, но эта стоимость будет амортизироваться по n, и эти накладные расходы будут иметь незначительный эффект, за исключением небольших n, Если n мал, то вы можете рассмотреть вопрос о выравнивании. Насколько маленький маленький, должно быть определено, но я предполагаю, что это намного меньше, чем 100.
Если ты имеешь ввиду sum + = a[i] + b[i], сокращение, то вам нужно подумать об этом. Это цепочка зависимостей, поэтому вам нужно развернуть цикл 3-10 раз. Кроме того, вам нужно использовать модель с плавающей запятой Арифметика с плавающей запятой не ассоциативна, и без нее не будет авто-векторизация так добавь -ffast-math в GCC (/fp:fast в MSVC). Если вы развернете цикл и будете использовать смягченную модель с плавающей запятой, то GCC, ICC, Clang и MSVC должны эффективно векторизовать ваше сокращение.
Другие решения
Чтобы использовать возможность предварительной выборки из кеша, вам необходимо последовательно читать массивы спереди назад.
Кроме того, массивы должны быть выровнены по SSE (16 байт). Еще более важно то, что элементы (например, поплавки) будут выровнены по их размеру (4 байта для поплавков). Это важно, чтобы данные не пересекали строки кэша (медленное чтение).
После выравнивания массивов вы можете использовать SSE / AVX для чтения, добавления и сохранения результатов, выполняя 4 или 8 операций в одной инструкции.
Редактировать:
Вы можете прочитать больше о предварительной загрузке кэша Вот и в глубоком описании в Руководство разработчика Intel SW.
detector