thêm vs mul (IA32-Lắp ráp)

Question

Tôi biết rằng thêm là nhanh hơn so với mul chức năng.

Tôi muốn biết làm thế nào để đi về việc sử dụng thêm thay vì mul trong đoạn mã sau để làm cho nó hiệu quả hơn.

Mẫu mã:

  mov eax, [ebp + 8]    #eax = x1 
      mov ecx, [ebp + 12]    #ecx = x2 
      mov edx, [ebp + 16]    #edx = y1 
      mov ebx, [ebp + 20]    #ebx = y2 

      sub eax,ecx      #eax = x1-x2 
      sub edx,ebx      #edx = y1-y2 

      mul edx       #eax = (x1-x2)*(y1-y2) 

Answer 1

thêm nhanh hơn mul, nhưng nếu bạn muốn nhân hai giá trị chung, mul là xa nhanh hơn bất kỳ vòng lặp thêm hoạt động .

Bạn không thể sử dụng nghiêm trọng thêm để làm cho mã đó chạy nhanh hơn với mul. Nếu bạn cần nhân với một số giá trị không đổi nhỏ (chẳng hạn như 2), thì có thể bạn có thể sử dụng thêm để tăng tốc độ. Nhưng đối với trường hợp chung - không.

Answer 2

Khi nói đến hướng dẫn lắp ráp, tốc độ thực hiện bất kỳ lệnh nào được đo bằng chu kỳ đồng hồ. Lệnh Mul luôn lấy chu kỳ đồng hồ nhiều hơn rồi thêm thao tác, nhưng nếu bạn thực hiện cùng lệnh thêm trong vòng lặp thì chu kỳ xung nhịp tổng thể để nhân phép sử dụng lệnh thêm sẽ là cách nhiều hơn sau đó chỉ lệnh mul đơn. Bạn có thể có một cái nhìn trên URL sau đây mà nói về chu kỳ đồng hồ của đơn add/mul instruction.So theo cách đó bạn có thể làm toán học của bạn, cái nào sẽ nhanh hơn.

http://home.comcast.net/~fbui/intel_a.html#add

http://home.comcast.net/~fbui/intel_m.html#mul

Tôi đề nghị là sử dụng hướng dẫn mul thay vì sau đó đưa thêm vào trong vòng lặp, là sau đó là giải pháp rất hiệu quả.

Answer 3

Tôi phải lặp lại các câu trả lời bạn đã có - để nhân rộng, bạn tốt nhất sử dụng MUL - sau khi tất cả là những gì nó có!

Trong một số trường hợp cụ thể, nơi bạn biết bạn sẽ muốn nhân với giá trị cố định cụ thể mỗi lần (ví dụ, trong việc lập chỉ mục pixel trong bitmap) thì bạn có thể xem xét. vào một (nhỏ) số lượng SHL và ADDs - ví dụ:

Hiển thị 1280 x 1024 - mỗi dòng trên màn hình hiển thị là 1280 pixel.

1280 = 1024 + 256 = 2^10 + 2^8

y * 1280 = y * (2^10) + y * (2^8) = ADD (SHL y, 10), (SHL y, 8)

... cho rằng xử lý đồ họa có khả năng cần phải được nhanh chóng, một cách tiếp cận đó có thể giúp bạn tiết kiệm chu kỳ đồng hồ quý giá.

Answer 4

Trừ khi phép nhân của bạn khá đơn giản, add rất có thể sẽ không hoạt động tốt hơn mul. Có nói rằng, bạn có thể sử dụng add để làm phép nhân:

Multiply by 2: 
    add eax,eax   ; x2 
Multiply by 4: 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
Multiply by 8: 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
    add eax,eax   ; x8 

Họ làm việc độc đáo cho quyền hạn của hai người. Tôi không nói họ nhanh hơn. Họ chắc chắn cần thiết trong những ngày trước khi hướng dẫn phép nhân ưa thích. Đó là từ một người nào đó mà linh hồn đã được trui rèn trong địa ngục-cháy đó là những Mostek 6502, Zilog Z80 và RCA1802 :-)

Bạn thậm chí có thể nhân với phi quyền lực bằng cách đơn giản lưu trữ kết quả tạm thời:

Multiply by 9: 
    push ebx    ; preserve 
    push eax    ; save for later 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
    add eax,eax   ; x8 
    pop ebx    ; get original eax into ebx 
    add eax,ebx   ; x9 
    pop ebx    ; recover original ebx 

Tôi thường khuyên bạn nên viết mã của bạn chủ yếu để dễ đọc và chỉ lo lắng về hiệu suất khi bạn cần. Tuy nhiên, nếu bạn đang làm việc trong công cụ lắp ráp, bạn cũng có thể đã là tại điểm đó. Nhưng tôi không chắc "giải pháp" của tôi thực sự có thể áp dụng được cho tình huống của bạn vì bạn có một phép nhân tùy ý.

Bạn nên, tuy nhiên, luôn luôn cấu hình mã của bạn trong môi trường đích để đảm bảo rằng những gì bạn đang thực hiện là thực sự nhanh hơn. Assembler không thay đổi khía cạnh tối ưu hóa đó.

---

Nếu bạn thực sự muốn xem một số lắp ráp mục đích tổng quát hơn cho việc sử dụng add để làm phép nhân, đây là một thói quen mà sẽ mất hai giá trị unsigned trong ax và bx và trả lại sản phẩm trong ax. Nó sẽ không xử lý tràn một cách tao nhã.

START: MOV AX, 0007 ; Load up registers 
     MOV BX, 0005 
     CALL MULT  ; Call multiply function. 
     HLT    ; Stop. 

MULT: PUSH BX   ; Preserve BX, CX, DX. 
     PUSH CX 
     PUSH DX 

     XOR CX,CX  ; CX is the accumulator. 

     CMP BX, 0  ; If multiplying by zero, just stop. 
     JZ  FIN 

MORE: PUSH BX   ; Xfer BX to DX for bit check. 
     POP DX 

     AND DX, 0001 ; Is lowest bit 1? 
     JZ  NOADD  ; No, do not add. 
     ADD CX,AX 

NOADD: SHL AX,1  ; Shift AX left (double). 
     SHR BX,1  ; Shift BX right (integer halve, next bit). 
     JNZ MORE  ; Keep going until no more bits in BX. 

FIN: PUSH CX   ; Xfer product from CX to AX. 
     POP AX 

     POP DX   ; Restore registers and return. 
     POP CX 
     POP BX 
     RET 

Nó dựa trên thực tế là 123 nhân 456 giống hệt:

123 x 6 
+ 1230 x 5 
+ 12300 x 4 

mà là giống như cách bạn được dạy nhân trở lại trong lớp học/tiểu học. Nó dễ dàng hơn với nhị phân vì bạn chỉ nhân với số không hoặc một (nói cách khác là thêm hoặc không thêm).

X86 khá cũ của trường (8086, từ phiên DEBUG - Tôi không thể tin rằng chúng vẫn thực sự bao gồm thứ đó trong XP) vì đó là lần cuối cùng tôi được mã hóa trực tiếp trong trình biên dịch. Có gì cần nói cho các ngôn ngữ cấp cao :-)

Answer 5

Nếu bạn nhân hai giá trị mà bạn không biết trước, không thể đánh bại lệnh nhân trong bộ ghép x86.

Nếu bạn biết trước giá trị của một trong các toán hạng, bạn có thể đánh bại lệnh nhân bằng cách sử dụng một số lượng nhỏ số lần thêm. Điều này làm việc đặc biệt tốt khi toán hạng đã biết là nhỏ, và chỉ có một vài bit trong biểu diễn nhị phân của nó. Để nhân giá trị không xác định x với giá trị đã biết bao gồm 2^p + 2^q + ... 2^r bạn chỉ cần thêm x * 2^p + x * 2^q + .. x * 2 * r nếu bit p, q , ... và r được đặt. Đây có thể dễ dàng thực hiện trong lắp ráp bởi trái chuyển và nói thêm:

; x in EDX 
; product to EAX 
xor eax,eax 
shl edx,r ; x*2^r 
add eax,edx 
shl edx,q-r ; x*2^q 
add eax,edx 
shl edx,p-q ; x*2^p 
add eax,edx 

Vấn đề chính với điều này là phải mất ít nhất 4 đồng hồ để làm điều này, giả sử một CPU superscalar hạn chế bởi phụ thuộc đăng ký.Nhân thường mất 10 hoặc ít hơn đồng hồ trên CPU hiện đại và nếu chuỗi này dài hơn thời gian , bạn cũng có thể nhân lên.

Để nhân với 9:

mov eax,edx ; same effect as xor eax,eax/shl edx 1/add eax,edx 
shl edx,3 ; x*2^3 
add eax,edx 

này nhịp đập nhân; chỉ nên lấy 2 đồng hồ.

Điều ít nổi tiếng hơn là sử dụng lệnh LEA (địa chỉ hiệu quả tải), để thực hiện nhanh chóng theo từng hằng số nhỏ. LEA chỉ mất một đồng hồ duy nhất trong trường hợp xấu nhất thời gian thực thi của nó thường có thể là bằng cách chồng chéo với các hướng dẫn khác bằng CPU siêu cứng.

LEA về cơ bản là "thêm hai giá trị có số nhân không đổi nhỏ". Nó tính t = 2^k * x + y cho k = 1,2,3 (xem sách hướng dẫn tham chiếu của Intel) cho t, x và y là bất kỳ thanh ghi nào. Nếu x == y, bạn có thể nhận được 1,2,3,4,5,8,9 lần x, nhưng sử dụng x và y làm sổ đăng ký riêng cho phép kết quả trung gian được kết hợp và được chuyển sang thanh ghi khác ví dụ, để t), và điều này hóa ra là rất tiện dụng. Sử dụng nó, bạn có thể hoàn thành một nhân với 9 sử dụng một chỉ dẫn duy nhất:

lea eax,[edx*8+edx] ; takes 1 clock 

Sử dụng LEA một cách cẩn thận, bạn có thể nhân bởi một loạt các hằng số đặc biệt trong một số ít các chu kỳ:

lea eax,[edx*4+edx] ; 5 * edx 
lea eax,[eax*2+edx] ; 11 * edx 
lea eax,[eax*4] ; 44 * edx 

Để thực hiện điều này, bạn phải phân tách hệ số không đổi của bạn thành nhiều yếu tố/số tiền khác nhau liên quan đến 1,2,3,4,5,8 và 9. Điều đáng chú ý là bạn có thể thực hiện bao nhiêu hằng số nhỏ và vẫn sử dụng 3-4 hướng dẫn.

Nếu bạn cho phép sử dụng các hướng dẫn đơn đồng hồ thông thường khác (ví dụ: SHL/SUB/NEG/MOV) bạn có thể nhân với một số giá trị không đổi mà LEA tinh khiết không thể tự làm. Để nhân với 31:

lea eax,[4*edx] 
lea eax,[8*eax] ; 32*edx 
sub eax,edx; 31*edx ; 3 clocks 

Chuỗi LEA tương ứng dài:

lea eax,[edx*4+edx] 
lea eax,[edx*2+eax] ; eax*7 
lea eax,[eax*2+edx] ; eax*15 
lea eax,[eax*2+edx] ; eax*31 ; 4 clocks 

Tìm ra những trình tự này là một chút khó khăn, nhưng bạn có thể thiết lập một cuộc tấn công có tổ chức.

Vì LEA, SHL, SUB, NEG, MOV là tất cả các lệnh đồng hồ đơn nhất và đồng hồ không nếu chúng không phụ thuộc vào các hướng dẫn khác, bạn có thể tính toán chi phí exeuction của bất kỳ trình tự như vậy. Điều này có nghĩa là bạn có thể thực hiện một thuật toán lập trình động để tạo chuỗi tốt nhất có thể có của các hướng dẫn như vậy. Điều này chỉ hữu ích nếu số lượng đồng hồ nhỏ hơn số nguyên nhân cho CPU cụ thể của bạn (Tôi sử dụng 5 đồng hồ làm quy tắc chung), và nó không sử dụng hết tất cả các thanh ghi hoặc ít nhất nó không không sử dụng đăng ký đã được bận rộn (tránh bất kỳ sự cố tràn).

Tôi đã thực sự xây dựng bộ biên dịch này vào trình biên dịch PARLANSE và rất hiệu quả để tính toán các mảng cấu trúc A [i], trong đó kích thước của phần tử cấu trúc trong A là hằng số đã biết.Một người thông minh có thể nhớ cache câu trả lời để nó không phải là phải được tính toán lại mỗi lần nhân cùng một hằng số xảy ra; Tôi đã không thực sự làm điều đó bởi vì thời gian để tạo ra các chuỗi như vậy là ít hơn bạn mong đợi.

Điều thú vị là in ra các chuỗi các lệnh cần thiết để nhân với tất cả các hằng số từ 1 đến 10000. Hầu hết trong số đó có thể được thực hiện trong trường hợp xấu nhất 5-6. Kết quả là, trình biên dịch PARLANSE hầu như không bao giờ sử dụng một số nhân thực tế khi lập chỉ mục ngay cả các mảng cấu trúc lồng nhau tối thiểu .