C++: загадочно огромное ускорение от хранения одного операнда в регистре


Я пытался получить представление о влиянии наличия массива в кэше L1 на память, синхронизируя процедуру, которая масштабирует и суммирует элементы массива, используя следующий код (я знаю, что я должен просто масштабировать результат на " a "в конце; дело в том, чтобы сделать как умножение, так и добавление в цикле - до сих пор компилятор не выяснил, чтобы разложить "a"):

double sum(double a,double* X,int size)
{
    double total = 0.0;
    for(int i = 0;  i < size; ++i)
    {
        total += a*X[i];
    }
    return total;
}

#define KB 1024
int main()
{
    //Approximately half the L1 cache size of my machine
    int operand_size = (32*KB)/(sizeof(double)*2);
    printf("Operand size: %dn", operand_size);
    double* X = new double[operand_size];
    fill(X,operand_size);

    double seconds = timer();
    double result;
    int n_iterations = 100000;
    for(int i = 0; i < n_iterations; ++i)
    {
        result = sum(3.5,X,operand_size);
        //result += rand();  
    }
    seconds = timer() - seconds; 

    double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
    printf("Vector size %d: mflops=%.1f, result=%.1fn",operand_size,mflops,result);
    return 0;
}

обратите внимание, что процедуры timer () и fill () не включены для краткости; их полный источник можно найти здесь, Если вы хотите запустить код:

http://codepad.org/agPWItZS

Итак, вот где это становится интересным. Это выход:

Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8

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

g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp

я замечаю одну странность в цикле функции sum:

L55:
    movsd   (%r12,%rax,8), %xmm0
    mulsd   %xmm1, %xmm0
    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)
    incq    %rax
    cmpq    48, %rax
    jne L55

в инструкции:

    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)

укажите, что он хранит значение "total" в sum() в стеке и читает и записывает его на каждой итерации цикла. Я изменил сборку так, что этот операнд хранится в регистре a:

...
addsd   %xmm0, %xmm3
...

это небольшое изменение создает огромный прирост производительности:

Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8

tl; dr Мой вопрос: почему замена одного места памяти доступа с регистром, ускорить код так много, учитывая, что одно место должно храниться в кэше L1? Какие архитектурные факторы делают это возможным? Кажется очень странным, что многократная запись одного местоположения стека полностью уничтожит эффективность кэша.

приложение

моя версия gcc:

Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)

мой процессор:

Intel Xeon X5650

3 68

3 ответа:

вероятно, это комбинация более длинной цепочки зависимостей, а также неправильного предсказания нагрузки*.


Более Длинная Цепочка Зависимостей:

во-первых, мы определяем критические пути зависимости. Затем мы смотрим на задержки инструкций, предоставляемые: http://www.agner.org/optimize/instruction_tables.pdf (стр. 117)

в неоптимизированной версии, критический путь зависимости это:

  • addsd -72(%rbp), %xmm0
  • movsd %xmm0, -72(%rbp)

внутренне, это, вероятно, распадается на:

  • нагрузка (2 цикла)
  • addsd (3 цикла)
  • магазин (3 цикла)

если мы посмотрим на оптимизированную версию, это просто:

  • addsd (3 цикла)

таким образом, у вас есть 8 циклов против 3 циклов. Почти в 3 раза.

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


Load-store Misprediction:

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

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

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

как это актуально здесь:

Излишне говорить, что современные процессоры смогут выполнять несколько итераций этого цикла одновременно. Таким образом, процессор будет пытаться выполнить нагрузку (addsd -72(%rbp), %xmm0) прежде чем он закончит магазине (movsd %xmm0, -72(%rbp)) из предыдущей итерации.

результат? Предыдущий магазин конфликтует с нагрузкой-таким образом, неправильное предсказание и откат.

*обратите внимание, что я не уверен в имени "Load Prediction". Я только читал об этом в документах Intel, и они, похоже, не дали ему имени.

Я бы предположил, что проблема не в доступе к кэшу/памяти, а в процессоре (выполнение вашего кода). Здесь есть несколько видимых узких мест.

номера производительности здесь были основаны на коробках, которые я использовал (либо sandybridge, либо westmere)

Пиковая производительность для скалярной математики составляет 2,7 ГГц X2 флоп/часы x2 так как процессор может делать сложение и умножение одновременно. Теоретическая эффективность кода 0.6/(2.7*2) = 11%

пропускная способность необходимый: 2 двойника на ( + ) и (x) - > 4bytes / Flop 4 байта * 5.4 GFLOPS = 21.6 GB / s

если вы знаете, что он был недавно прочитан, скорее всего, в L1 (89GB/s), L2 (42GB/s) или L3(24GB/s), поэтому мы можем исключить кэш B/W

память susbsystem составляет 18,9 ГБ / С, поэтому даже в основной памяти пиковая производительность должна приближаться к 18,9 / 21,6 ГБ / с = 87,5 %

  • может потребоваться пакетная обработка запросов (через развертывание) как можно раньше

даже при спекулятивном исполнении, tot += a *X[i] добавления будут сериализованы, потому что tot(n) нужно будет eval'D до того, как tot(n+1) можно будет запустить

сначала разверните цикл
двигаюсь я на 8-е и делаю

{//your func
    for( int i = 0; i < size; i += 8 ){
        tot += a * X[i];
        tot += a * X[i+1];
        ...
        tot += a * X[i+7];
    }
    return tot
}

использовать несколько аккумуляторов
Это разрушит зависимости и позволит нам избежать остановки на конвейере добавления

{//your func//
    int tot,tot2,tot3,tot4;
    tot = tot2 = tot3 = tot4 = 0
    for( int i = 0; i < size; i += 8 ) 
        tot  += a * X[i];
        tot2 += a * X[i+1];
        tot3 += a * X[i+2];
        tot4 += a * X[i+3];
        tot  += a * X[i+4];
        tot2 += a * X[i+5];
        tot3 += a * X[i+6];
        tot4 += a * X[i+7];
    }
    return tot + tot2 + tot3 + tot4;
}

обновление После запуска этого на коробке SandyBridge у меня есть доступ к: (2.7 GHZ SandyBridge with -O2-march=native -mtune=уроженца

исходный код:

Operand size: 2048  
Vector size 2048: mflops=2206.2, result=61.8  
2.206 / 5.4 = 40.8%

Улучшен Код:

Operand size: 2048  
Vector size 2048: mflops=5313.7, result=61.8  
5.3137 / 5.4 = 98.4%  

Я не могу воспроизвести это, потому что мой компилятор (gcc 4.7.2) сохраняет total в реестр.

Я подозреваю, что основная причина медлительности не связана с кэшем L1, а скорее связана с зависимостью данных между хранилищем в

movsd   %xmm0, -72(%rbp)

и нагрузка на последующую итерацию:

addsd   -72(%rbp), %xmm0