Оптимизация x64 ассемблера MUL loop

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

void muladd(unsigned* r, const unsigned* a, unsigned len, unsigned b) {
   unsigned __int64 of = 0;  // overflow
   unsigned i = 0;  // loop variable
   while (i < len) {
      of += (unsigned __int64)a[i] * b + r[i];
      r[i] = (unsigned)of;
      of >>= 32;
      ++i;
   }
   r[i] = (unsigned)of;  // save overflow
}

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

mov   rax, rdi                             ; rdi = b
mul   QWORD PTR [rbx+r10*8-64]             ; rdx:rax = a[i] * b; r10 = i
mov   rsi, QWORD PTR [r14+r10*8-64]        ; r14 = r; rsi = r[i]
add   rax, rsi
adc   rdx, 0
add   rax, r11                             ; r11 = of (low part)
adc   rdx, 0
mov   QWORD PTR [r14+r10*8-64], rax        ; save result
mov   r11, rdx

; this repeats itself 8 times with different offsets

Когда я сравниваю это, я нахожу, что для моего Core2 Quad требуется около 6,3 циклов при умножении на умножение.

Мой вопрос: могу ли я как-то ускорить это? К сожалению, я не вижу возможности избежать одного из добавлений, и для умножения всегда нужен RDX: RAX, поэтому мне нужно перемещать данные и не может сортировать "размножаться параллельно".

Любые идеи кто-нибудь?

Update: После некоторого тестирования мне удалось довести скорость до примерно 5,4 циклов на 64-битный MUL (включая все накладные расходы, перемещение и цикл). Я думаю, что это самое лучшее, что вы можете получить на Core2, поскольку Core2 не имеет очень быстрой инструкции MUL: он имеет пропускную способность 3 и латентность 6 (соответственно 7) циклов. Песчаный мост будет намного лучше с пропускной способностью 1 и латентностью 3 (соответственно 4) цикла.

Что касается гораздо меньшего числа для GMP: я получил это из своего исходного кода, и мне кажется, что это теоретическое число. Но то, что является уверенным в том, что это число, которое было рассчитано для процессора AMD K9. И из того, что я прочитал, я понял, что у AMD есть более быстрая единица MUL, чем у более старых чипов Intel.

Ответы

Ответ 1

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

Я бы попытался выполнить предварительную выборку [i] и r [i]

если gcc использует функцию __builtin_prefetch() или инструкцию PREFETCHT0 в ассемблере

http://gcc.gnu.org/onlinedocs/gcc-3.3.6/gcc/Other-Builtins.html

Когда это работает, результаты могут быть значительными. До тех пор, пока цикл длится тысячу или около итераций, я предварительно выбрал [i + 64] и r [i + 64] в качестве отправной точки и посмотрю, какая разница в вашем процессоре. Возможно, вам придется попробовать большие расстояния перед выборкой.

Ответ 2

Похоже, ваша рутина может выиграть от SSE. PMULLD и PADDD выглядят как соответствующие инструкции. Не знаете, почему ваш компилятор не производит SSE.

Ответ 3

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

Ответ 4

Есть ли какое-либо важное значение перед вызовом?

Если это так, и вы накапливаете на нем, то прекратите читать сейчас.

Если это не так (т.е. вы всегда накапливаетесь на нули) и предполагаете, что вы вызываете эту функцию на массивах, значительно больших размеров кеша, тогда я бы искал способ устранить необходимость читать из r и преобразовать "сохранить результат" MOV в MOVNT (_mm_stream_ps в intrinsics).

Это может значительно повысить производительность. Как? В настоящее время ваши кэши извлекают строки кэша из строки, получая строки кэша из r и записывая строки кэша обратно в r. С так называемыми потоковыми хранилищами вы просто извлекаете строки кэша из строки и записываете прямо в r: гораздо меньше трафика шины. Если вы посмотрите на любую современную реализацию emc CRT, она переключится на использование потоковых хранилищ выше некоторого порога, связанного с размером кеша (и запустите почти в два раза быстрее, чем memcpy, используя обычные ходы).