Tôi đang viết mã toán học cần nhân số lớn nhanh. Nó phân tách thành phép nhân của một mảng các số nguyên với một số nguyên duy nhất. Trong C++ này trông như thế này (trên của unsigned):Tối ưu hóa bộ kết hợp x64 Vòng lặp MUL
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
}
tôi trải ra vòng lặp này bằng tay, chuyển nó đến 64 bit và làm việc trên đầu ra trình biên dịch .asm để tối ưu hóa nó hơn nữa. Vòng lặp chính hiện tại trông giống như sau:
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
Khi tôi đo điểm chuẩn này, tôi nhận thấy khoảng 6,3 chu kỳ trên avarage mỗi phép nhân trên Core2 Quad của tôi.
Câu hỏi của tôi là: tôi có thể tăng tốc độ này bằng cách nào đó không? Thật không may, tôi thấy không có cách nào để tránh một trong những bổ sung và phép nhân luôn luôn cần RDX: RAX, vì vậy tôi cần phải di chuyển dữ liệu xung quanh và không thể sắp xếp "nhân song song".
Có ý tưởng nào không?
Cập nhật: Sau một số thử nghiệm khác, tôi đã quản lý tốc độ lên tới khoảng 5.4 chu kỳ trên MUL 64 bit (bao gồm tất cả thêm, di chuyển và vòng lặp). Tôi đoán đây là điều tốt nhất bạn có thể nhận được trên một Core2, vì Core2 không có lệnh MUL rất nhanh: nó có thông lượng là 3 và độ trễ là 6 (resp. 7). Sandy bridge sẽ tốt hơn nhiều với thông lượng là 1 và độ trễ của chu kỳ 3 (resp. 4).
Về số lượng thấp hơn nhiều đối với GMP: tôi nhận được điều đó từ mã nguồn của họ và có vẻ như với tôi rằng đó là một con số lý thuyết. Nhưng điều chắc chắn là nó là một con số được tính cho một CPU AMD K9. Và từ những gì tôi đã đọc, tôi thu thập các AMD có một đơn vị MUL nhanh hơn các chip Intel (cũ hơn).
Bạn có thể muốn xem xét một số quy trình lắp ráp trong GMP. Họ có một chức năng mà thực hiện chính xác điều này và được viết trong lắp ráp cho hầu hết các bộ vi xử lý bao gồm x64. – Mysticial
GMP thực sự có hỗ trợ tốt cho một mul_basecase nhanh và appearantly phải mất một số 2.35 chu kỳ mỗi MUL, rất tốt đẹp. Nếu tôi hiểu nó một cách chính xác, chúng nhân hai vectơ xen kẽ nhau, điều đó dường như giữ cho các phụ thuộc thấp và cải thiện việc xử lý tràn. – cxxl