Я пишу математический код, который должен быстро умножать большие числа. Он разбивается на умножения массива целых чисел с одним целым числом. В С++ это выглядит так (на 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.
