Я пишу математический код, который должен быстро умножать большие числа.Он разбивается на умножения массива целых чисел с одним целым числом.В C ++ это выглядит так (для unsigned's):
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, поэтому мне нужно перемещать данные и не могу что-то «умножить параллельно».
Любые идеи кто-нибудь?
Обновление: После еще одного тестирования мне удалось довести скорость до примерно 5,4 цикла на 64-битный MUL (включая все операции добавления, перемещения и зацикливания).Я думаю, это лучшее из того, что вы можете получить на Core2, поскольку у Core2 нет очень быстрой инструкции MUL: она имеет пропускную способность 3 и задержку 6 (соответственно 7) циклов.Песчаный мост будет намного лучше с пропускной способностью 1 и задержкой в 3 (соответственно 4) цикла.
Что касается гораздо меньшего числа для GMP: я получил это из их исходного кода, и мне кажется, чтоэто теоретическое число.Но точно то, что это число рассчитано для процессора AMD K9.И из того, что я прочитал, я понимаю, что у AMD более быстрый модуль MUL, чем у (старых) чипов Intel.