как развертывание повлияет на число циклов на количество элементов CPE

  1. как рассчитать CPE (количество циклов на элемент) с помощью этих фрагментов кода?
  2. в чем разница в CPE между двумя приведенными фрагментами кода?

У меня есть этот кусок кода

void randomFunction(float a[],float Tb[],float c[],long int n){
        int i,j,k;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j)
                for(k=0;k<n-1;k++){ 
                                temp+= a[i*n+k] * Tb[j*n+k];
                }
    
}

Это сборка для самого внутреннего цикла из GCC10.3 -O2 (https://godbolt.org/z/cWE16rW1r), для версии функции с локальным float temp=0;, которое она возвращает, поэтому цикл не будет оптимизирован:

.L4:
    movss   (%rcx,%rax), %xmm0
    mulss   (%rdx,%rax), %xmm0
    addq    $4, %rax
    addss   %xmm0, %xmm1
    cmpq    %rax, %rsi
    jne     .L4

Теперь я пытаюсь «оптимизировать это», используя разворачивание.

void randomUnrollingFunction(float a[],float Tb[],float c[],long int n){
    int i,j,k;
    for(i=0;i<n;++i)
        for(j=0;j<n;++j)
            for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
                            temp+= a[i*n+k] * Tb[j*n+k];
                            temp+= a[i*n+k+1]* Tb[j*n+k+1];
            }

}

Мне интересно, каков предполагаемый CPE, который будет достигнут при этом развертывании с коэффициентом 2.
CPE - это количество циклов / количество инструкций.

Это информация о задержке: информация о задержке

Спасибо за любую помощь заранее!


c x86 assembly cpu-architecture loop-unrolling
person Megan Darcy    schedule 24.06.2021    source источник
comment
Похоже, вы можете оптимизировать это дальше. Сделайте j своим самым внутренним циклом, тогда вы сможете переместить умножение на a[i*n+k] наружу.   -  person valdo    schedule 24.06.2021
comment
Ах да, но меня интересует количество CPE, как оно меняется, когда я делаю эту текущую оптимизацию? @валдо   -  person Megan Darcy    schedule 24.06.2021
comment
Ваша сборка синтаксиса AT&T искажена. Отсутствуют запятые, отсутствует $ в непосредственном операнде (4 — это операнд памяти с абсолютным адресом 4), отсутствует % в именах регистров.   -  person Peter Cordes    schedule 24.06.2021
comment
@PeterCordes извините за то, что я это исправил. был недосмотр   -  person Megan Darcy    schedule 24.06.2021
comment
@valdo: k - единственный индекс, который обращается к непрерывной памяти в обеих входных матрицах. Дополнительный mulss на adds дешевле, чем промахи кеша, которые вы понесете из-за многократного перехода вниз по столбцам Tb[], если только вы не сделали гораздо больше оптимизации, такой как блокировка кеша или развертывание для использования всех 16 плавающих элементов 64-байтной строки кеша. (Предпочтительно использовать SIMD для параллельного выполнения 4 в векторе XMM вместо использования только младшего скалярного элемента, поэтому требуется только 4 вектора SSE). С выровненными входными данными это будет означать, что вы коснетесь каждой строки кэша только один раз.   -  person Peter Cordes    schedule 24.06.2021
comment
Обратите внимание, что если бы не узкое место с задержкой, ваш цикл был бы узким местом во внешнем интерфейсе на Haswell (4 операции слияния доменов за цикл), а не во внутренних функциональных модулях. Цикл состоит из 5 объединенных доменных операций, предполагающих макрослияние cmp/jne и то, что Haswell может поддерживать микрослияние источников памяти, несмотря на режим индексированной адресации. (Sandybridge не стал бы ламинировать его.) Но благодаря последовательной зависимости от ADDSS (которая фактически переносится через внешние циклы) единственное, что имеет значение, — это цепочка зависимостей.   -  person Peter Cordes    schedule 24.06.2021
comment
Даже неправильное предсказание ветвления на последней итерации внутреннего цикла (когда ветвь не выполняется, а не выполняется нормально), это просто даст серверной части больше времени для обработки этих ожидающих операций ADDSS, в то время как клиентская часть разбирается сама. и начинается со следующего внутреннего цикла. См. также Почему mulss занимает всего 3 цикла на Haswell, в отличие от таблиц инструкций Agner? (Развертывание циклов FP с несколькими аккумуляторами)   -  person Peter Cordes    schedule 24.06.2021
comment
@PeterCordes, насколько ошибочный прогноз влияет на CPE? также как мне рассчитать значение CPE для каждого фрагмента?   -  person Megan Darcy    schedule 24.06.2021
comment
temp не объявлено. По какой-то причине я предположил, что он должен быть глобальным или вне каких-либо циклов. Но на самом деле это матмул, в котором вы удаляли хранилище в c[] = temp; после каждого самого внутреннего цикла, верно? Цепочки зависимостей (например, где temp повторно инициализируется до нуля) имеют значение, как вы можете видеть из последнего раздела моего ответа.   -  person Peter Cordes    schedule 24.06.2021
comment
Таким образом, фактическая стоимость этого ошибочного прогноза ветки зависит от того, где сразу после него temp сбрасывается до 0. Если это так, вы теряете циклы, которые могли бы быть потрачены на независимую addss работу, которая пересекается с предыдущей цепочкой отложений.   -  person Peter Cordes    schedule 24.06.2021

Ответы (1)


arrow_upward
2
arrow_downward

Ваш цикл полностью ограничивается задержкой addss (добавление с плавающей запятой) при 3 циклах на 1 элемент. Выполнение вне очереди позволяет другой работе выполняться в тени этого. Предполагая, что у вашего Haswell-подобного процессора есть пропускная способность памяти, чтобы поддерживать 1

Этот способ развертывания не помогает вообще, не изменяя цепочку последовательных зависимостей, если только вы не скомпилировали с -ffast-math или чем-то еще, чтобы позволить компилятору превратить его в

temp1 += a[...+0]* Tb[...+0];
temp2 += a[...+1]* Tb[...+1];

Или добавьте пары, прежде чем подавать их в эту последовательную зависимость, например

temp +=  a[]*Tb[] + a[+1]*Tb[+1];

Одна длинная последовательная цепочка зависимостей является худшей, а также численно невеликой: попарное суммирование (или, особенно, просто шаг в этом направлении с использованием нескольких аккумуляторов) было бы численно лучше, а также работало бы лучше. (Программа Simd matmul дает разные числовые результаты).

(Если ваши несколько аккумуляторов представляют собой 4 элемента вектора SIMD, вы можете выполнить в 4 раза больше работы с тем же шаблоном ассемблерных инструкций. Но тогда вам нужно развернуть несколько векторов, потому что addps имеет те же характеристики производительности, что и у addss на современных процессорах x86.)

Сноска 1: два последовательных потока чтения по 4 байта каждый за 3 цикла; конечно, настольный Haswell мог бы не отставать, и, возможно, даже Xeon, конкурирующий со многими другими ядрами за пропускную способность памяти. Но чтение из [], вероятно, попадает в кеш, потому что a[i*n+k] постоянно повторяет одну и ту же строку, пока мы не перейдем к следующей итерации внешнего цикла. Таким образом, только 1 строка из a[] должна оставаться горячей в кеше (чтобы получить совпадения на следующей средней итерации), пока мы сканируем строку из Tb. Таким образом, a[] должно поступать из DRAM всего один раз, если n не огромно, но мы перебираем все Tb[] по порядку n раз.

Более подробная версия

См. Какие соображения учитываются при прогнозировании задержки для операций на современные суперскалярные процессоры и как их вычислить вручную? - ищите цепочки зависимостей (в данном случае addss в %xmm1). Также краткое введение в графы потоков данных.

Затем найдите узкие места пропускной способности в серверной и клиентской части. В вашем случае доминирует задержка. (Предполагая, что внешний интерфейс соответствует этому внутреннему интерфейсу Haswell, хотя это не займет много времени, чтобы справиться с этим узким местом задержки серверной части. Кроме того, я ненавижу, что они нумеруют свои функциональные блоки от 1 , вместо того, чтобы следовать нумерации портов Intel 0,1,5,6, имеющих ALU.Суммер FP Haswell находится на порту 1, а порты 2/3 являются модулями загрузки/хранения-AGU и т. д.)

ADDSS имеет задержку в 3 цикла, поэтому temp += ... может выполняться только один раз за 3 цикла. Операции load/MULSS просто независимо подготавливают входные данные для ADDSS, и служебные данные цикла также не зависят.

Обратите внимание, что если бы не узкое место с задержкой, ваш цикл был бы узким местом во внешнем интерфейсе на реальном Haswell (4 операции с объединенным доменом за цикл), а не на внутренних функциональных модулях. Цикл состоит из 5 объединенных доменных операций, предполагающих макрослияние cmp/jne и то, что Haswell может поддерживать микрослияние источников памяти, несмотря на режим индексированной адресации. (Sandybridge не ламинирует его.)

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

Но благодаря последовательной зависимости от ADDSS (которая фактически переносится через внешние циклы) единственное, что имеет значение, — это цепочка зависимостей.

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

Поскольку вы развернули таким образом, что не изменяет последовательную зависимость, это не имеет никакого значения для производительности, за исключением крошечного n. (Для крошечного n все это потенциально может перекрывать часть этой работы с независимыми работать в вызывающем абоненте до/после вызова. В этом случае может быть полезно сохранить инструкции, а также позволить внеочередному exec видеть дальше. -the-impact-of-lfence-on-a-loop-with-two-long-dependency-chains-fo">Понимание влияния lfence на цикл с двумя длинными цепочками зависимостей при увеличении длины случай, когда OoO exec может (частично) перекрывать две независимые цепочки imul dep, которые в программном порядке идут одна за другой.

Конечно, в этот момент вы рассматриваете код, выходящий за рамки того, что вы показываете. И даже для n = 10 это 10 ^ 3 = 1000 внутренних итераций, а ROB Haswell составляет всего 192 микрооперации с RS 60 записей. (https://www.realworldtech.com/haswell-cpu/3/ ).

Разворачивание полезным способом

См. также Почему mulss занимает всего 3 цикла на Haswell, в отличие от таблиц инструкций Agner? (Развертывание циклов FP с несколькими накопителями) re: развертывание способами, которые действуют, создают больший параллелизм на уровне инструкций, скрывая цепочки зависимостей FP.

Развертывание по-другому, суммирование только один раз в temp за итерацию цикла, сохранит те же циклы за итерацию, но при этом удвоит количество обрабатываемых элементов.

            for(k=0;k<n-1;k+=2){//this is the unrolled portion by 2
                            temp +=  (a[i*n+k] * Tb[j*n+k]  +
                                      a[i*n+k+1]* Tb[j*n+k+1]);
            }

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

В вашей таблице функциональных блоков не указан FMA (плавное умножение-сложение), но он есть в реальном Haswell с идентичной производительностью для FP mul. Это не сильно поможет, если таковые имеются, потому что ваша текущая структура цикла выполняет 2 загрузки на mul+add, поэтому сокращение до 2 загрузок и одного FMA по-прежнему будет узким местом при нагрузках. Может помочь с пропускной способностью интерфейса?

Что может помочь уменьшить нагрузку, так это развертывание одного из внешних циклов с использованием как a[i*n+k], так и a[(i+1)*n+k] с одним Tb[j*n+k]. Это, конечно, меняет порядок вычислений, поэтому недопустимо для компилятора без -ffast-math, потому что FP-математика не является строго ассоциативной.

Это сокращение матмула, позволяющее гораздо лучше оптимизировать

(Эээ, подождите, ваш код не показал, где temp был повторно инициализирован или для чего был c[] arg. Я просто предположил, что это было глобально или что-то в этом роде, но, вероятно, вы на самом деле вырезали обычную функцию matmul, которая сохраняет отдельный temp после каждого внутреннюю итерацию до c[], убрав это. В этом случае выполнение OoO между отдельной итерацией среднего цикла актуально для среднего размера n. Но вы не показываете размеры планировщика / ROB, и это не что-то, что вы можете легко смоделировать; вам нужно на самом деле сравнить.Так что этот раздел, вероятно, применим только к вопросу, который я придумал, а не к тому, что вы хотели задать!)

Кажется, что ваши циклы суммируют элементы результата matmul, но все еще структурированы как matmul. то есть сделать скалярное произведение строки x столбца, но вместо того, чтобы сохранять это в матрицу N x N result[...], вы просто суммируете результат.

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

Например, вам не нужно транспонировать b в Tb, просто используйте b (если только он уже не был транспонирован естественным образом, в этом случае все в порядке). Ваши матрицы квадратные, так что это не имеет значения вообще.

Кроме того, вы можете просто загрузить один или пару элементов из a[] и зациклиться на Tb[], выполняя эти продукты с операциями FMA, по одной загрузке на FMA, в 10 или 12 векторных аккумуляторов. (Или, конечно, заблокируйте это, чтобы зациклить непрерывную часть Tb, которая может оставаться горячей в кеше L1d.)

Это может приблизиться к максимальной пропускной способности Haswell, равной 2x 256-битным FMA за такт = 8 (float элементов на вектор YMM) x 2 FMA/такт x 2 FLOP/FMA = 32 FLOP/такт.

person Peter Cordes    schedule 24.06.2021