Cara tercepat untuk menghitung urutan besarnya dalam perakitan x86

12

Tugasnya sederhana: menulis perakitan yang menghitung urutan besarnya bilangan bulat menggunakan sesedikit mungkin siklus clock.

  • Urutan besarnya didefinisikan sebagai log10, bukan log2.
  • Kisaran input yang valid adalah 0hingga , inklusif. Perilaku untuk input di luar rentang itu tidak ditentukan.1012
  • Nilai harus dibulatkan ke bilangan bulat terdekat, dengan pengecualian bahwa input yang diberikan 0output harus 0. (Anda dapat menganggap ini sebagai representasi terbaik dari infinity negatif yang dimungkinkan pada bilangan bulat tak bertanda).
  • Harus berupa perakitan x86.
  • Integer harus berupa nilai runtime , bukan integer statis / inline. Jadi kita tidak tahu apa itu pada waktu kompilasi.
  • Asumsikan bahwa Anda sudah memiliki bilangan bulat yang dimuat ke dalam register. (Tetapi sertakan pengaturan nilai dalam register dalam jawaban untuk kejelasan).
  • Tidak dapat memanggil perpustakaan atau fungsi eksternal apa pun.
  • Bebas menggunakan salah satu instruksi yang tersedia dalam dokumen Intel .
  • Tidak ada C.
  • Salah satu dari ~ 7 arsitektur Intel Core dapat diterima (dicantumkan pada halaman 10 ). Idealnya Nehalem (Intel Core i7).

Jawaban yang menang adalah yang menggunakan siklus jam sesedikit mungkin. Artinya, ia dapat memiliki operasi paling banyak per detik. Ringkasan perkiraan siklus jam ada di sini: http://www.agner.org/optimize/instruction_tables.pdf . Menghitung siklus jam dapat terjadi setelah jawaban diposting.

math fastest-algorithm assembly Lance Pollard
sumber
Apakah 'FYL2X' dan instruksi FPU lainnya diperbolehkan?
Digital Trauma
1
Haruskah hasilnya bilangan bulat? Jika demikian, bagaimana seharusnya dibulatkan?
Digital Trauma
3
Jadi input dan output keduanya bilangan bulat, ya? Tetapi inputnya bisa sebesar 10 ^ 12, jadi itu terlalu besar untuk int 32 bit. Jadi, apakah kita mengasumsikan input integer 64 bit?
Paul R
3
Apakah kriteria kemenangan didasarkan pada jumlah maksimum atau rata-rata siklus? Dan jika rata-rata, apa distribusi input?
Runer112
2
Prosesor mana yang ditargetkan? Dokumen yang ditautkan mencantumkan lebih dari 20 proses yang berbeda (AMD, Intel, yang lain) dan ada variasi yang cukup besar dalam latensi.
Digital Trauma

Jawaban:

8

7 siklus, waktu konstan

Inilah solusi berdasarkan jawaban saya untuk Pertanyaan SO ini . Menggunakan BSR untuk menghitung berapa banyak bit yang diperlukan untuk memegang nomor tersebut. Itu terlihat berapa banyak angka desimal yang diperlukan untuk mewakili jumlah terbesar yang dapat menampung banyak bit. Maka mengurangi 1 jika angka aktual kurang dari kekuatan terdekat 10 dengan angka yang banyak.

    .intel_syntax noprefix
    .globl  main
main:
    mov rdi, 1000000000000              #;your value here
    bsr rax, rdi
    movzx   eax, BYTE PTR maxdigits[1+rax]
    cmp rdi, QWORD PTR powers[0+eax*8]
    sbb al, 0
    ret
maxdigits:
    .byte   0
    .byte   0
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .byte   1
    .byte   2
    .byte   2
    .byte   2
    .byte   3
    .byte   3
    .byte   3
    .byte   3
    .byte   4
    .byte   4
    .byte   4
    .byte   5
    .byte   5
    .byte   5
    .byte   6
    .byte   6
    .byte   6
    .byte   6
    .byte   7
    .byte   7
    .byte   7
    .byte   8
    .byte   8
    .byte   8
    .byte   9
    .byte   9
    .byte   9
    .byte   9
    .byte   10
    .byte   10
    .byte   10
    .byte   11
    .byte   11
    .byte   11
    .byte   12
powers:
    .quad   0
    .quad   10
    .quad   100
    .quad   1000
    .quad   10000
    .quad   100000
    .quad   1000000
    .quad   10000000
    .quad   100000000
    .quad   1000000000
    .quad   10000000000
    .quad   100000000000
    .quad   1000000000000

Kompilasi pada GCC 4.6.3 untuk ubuntu dan mengembalikan nilai dalam kode keluar.

Saya tidak percaya diri menafsirkan tabel siklus untuk prosesor modern mana pun, tetapi menggunakan metode @ DigitalTrauma, pada prosesor Nehalim, saya mendapatkan 7 ?

ins        uOps Latency
---        -    - 
BSR r,r  : 1    3
MOVZX r,m: 1    -
CMP m,r/i: 1    1 
SBB r,r/i: 2    2
ASHelly
sumber
Oh - melihat DigitalTrauma setelah saya mulai menulis milik saya. Ide serupa. Menggunakan metodologi penghitungannya saya pikir dapatkan 3,1,1,1 = 6 untuk BSR, MOV, CMP, SBB
AShelly
Yap, saya pikir milikmu mengalahkan milikku. Hanya pergi untuk menunjukkan a) Saya bukan programmer perakitan dan b) perakitan sebaiknya dibiarkan oleh manusia belaka ;-)
Digital Trauma
The integer must be a runtime value, not a static/inline integer. So we don't know what it is at compile time.
kucing
1
benar, dan baris berikutnya mengatakan: "Asumsikan bahwa Anda sudah memiliki bilangan dimasukkan ke dalam register. (Tetapi termasuk menetapkan nilai dalam register dalam jawaban untuk kejelasan)." Itulah yang telah saya lakukan.
AShelly
ganti movzx eax dengan mov al. 24 bit teratas dari eax sudah akan nol, jadi zx redundan (dan mahal).
peter ferrie
6

Kasus terbaik 8 siklus, Kasus terburuk 12 siklus

Karena tidak jelas dalam pertanyaan, saya mendasarkan latensi Ivy Bridge ini.

Pendekatan di sini adalah dengan menggunakan bsrinstruksi (bit scan reverse) sebagai log2 orang miskin (). Hasilnya digunakan sebagai indeks ke dalam tabel lompatan yang berisi entri untuk bit 0 hingga 42. Saya berasumsi bahwa mengingat operasi pada data 64bit secara implisit diperlukan, maka penggunaan bsrinstruksi adalah OK.

Dalam input kasus terbaik, entri jumptable dapat memetakan bsrhasilnya langsung ke besarnya. mis. Untuk input dalam kisaran 32-63, bsrhasilnya adalah 5, yang dipetakan dengan besaran 1. Dalam hal ini, jalur instruksi adalah:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

Dalam input kasus terburuk, bsrhasilnya akan memetakan ke dua besaran yang mungkin, sehingga entri jumptable melakukan satu tambahan cmpuntuk memeriksa apakah inputnya> 10 n . Misalnya untuk input dalam kisaran 64-127, bsrhasilnya akan menjadi 6. Entri jumptable yang sesuai kemudian memeriksa apakah input> 100 dan mengatur besarnya output yang sesuai.

Selain untuk jalur kasus terburuk, kami memiliki instruksi mov tambahan untuk memuat nilai langsung 64bit untuk digunakan di cmp, jadi jalur instruksi kasus terburuk adalah:

Instruction    Latency

bsrq                 3
jmp                  2
movabsq              1
cmpq                 1
ja                   2
movl                 1
jmp                  2

total               12

Ini kodenya:

    /* Input is loaded in %rdi */
    bsrq    %rdi, %rax
    jmp *jumptable(,%rax,8)
.m0:
    movl    $0, %ecx
    jmp .end
.m0_1:
    cmpq    $9, %rdi
    ja  .m1
    movl    $0, %ecx
    jmp .end
.m1:
    movl    $1, %ecx
    jmp .end
.m1_2:
    cmpq    $99, %rdi
    ja  .m2
    movl    $1, %ecx
    jmp .end
.m2:
    movl    $2, %ecx
    jmp .end
.m2_3:
    cmpq    $999, %rdi
    ja  .m3
    movl    $2, %ecx
    jmp .end
.m3:
    movl    $3, %ecx
    jmp .end
.m3_4:
    cmpq    $9999, %rdi
    ja  .m4
    movl    $3, %ecx
    jmp .end
.m4:
    movl    $4, %ecx
    jmp .end
.m4_5:
    cmpq    $99999, %rdi
    ja  .m5
    movl    $4, %ecx
    jmp .end
.m5:
    movl    $5, %ecx
    jmp .end
.m5_6:
    cmpq    $999999, %rdi
    ja  .m6
    movl    $5, %ecx
    jmp .end
.m6:
    movl    $6, %ecx
    jmp .end
.m6_7:
    cmpq    $9999999, %rdi
    ja  .m7
    movl    $6, %ecx
    jmp .end
.m7:
    movl    $7, %ecx
    jmp .end
.m7_8:
    cmpq    $99999999, %rdi
    ja  .m8
    movl    $7, %ecx
    jmp .end
.m8:
    movl    $8, %ecx
    jmp .end
.m8_9:
    cmpq    $999999999, %rdi
    ja  .m9
    movl    $8, %ecx
    jmp .end
.m9:
    movl    $9, %ecx
    jmp .end
.m9_10:
    movabsq $9999999999, %rax
    cmpq    %rax, %rdi
    ja  .m10
    movl    $9, %ecx
    jmp .end
.m10:
    movl    $10, %ecx
    jmp .end
.m10_11:
    movabsq $99999999999, %rax
    cmpq    %rax, %rdi
    ja  .m11
    movl    $10, %ecx
    jmp .end
.m11:
    movl    $11, %ecx
    jmp .end
.m11_12:
    movabsq $999999999999, %rax
    cmpq    %rax, %rdi
    ja  .m12
    movl    $11, %ecx
    jmp .end
.m12:
    movl    $12, %ecx
    jmp .end

jumptable:
    .quad   .m0
    .quad   .m0
    .quad   .m0
    .quad   .m0_1
    .quad   .m1
    .quad   .m1
    .quad   .m1_2
    .quad   .m2
    .quad   .m2
    .quad   .m2_3
    .quad   .m3
    .quad   .m3
    .quad   .m3
    .quad   .m3_4
    .quad   .m4
    .quad   .m4
    .quad   .m4_5
    .quad   .m5
    .quad   .m5
    .quad   .m5_6
    .quad   .m6
    .quad   .m6
    .quad   .m6
    .quad   .m6_7
    .quad   .m7
    .quad   .m7
    .quad   .m7_8
    .quad   .m8
    .quad   .m8
    .quad   .m8_9
    .quad   .m9
    .quad   .m9
    .quad   .m9
    .quad   .m9_10
    .quad   .m10
    .quad   .m10
    .quad   .m10_11
    .quad   .m11
    .quad   .m11
    .quad   .m11_12
    .quad   .m12
    .quad   .m12
    .quad   .m12

.end:
/* output is given in %ecx */

Ini sebagian besar dihasilkan dari output assembler gcc untuk kode C proof-of-concept yang saya tulis . Perhatikan kode C menggunakan goto yang dapat dihitung untuk mengimplementasikan tabel lompatan. Ia juga menggunakan __builtin_clzll()gcc builtin, yang mengkompilasi bsrinstruksi (plus an xor).

Saya mempertimbangkan beberapa solusi sebelum sampai pada yang ini:

  • FYL2Xuntuk menghitung log natural, maka FMULdengan konstanta yang diperlukan. Ini mungkin akan memenangkan ini jika ini adalah kontes [tag: instructions: golf]. Tetapi FYL2Xmemiliki latency 90-106 untuk jembatan Ivy.

  • Pencarian biner dengan kode keras. Ini mungkin sebenarnya kompetitif - saya akan menyerahkannya kepada orang lain untuk diimplementasikan :).

  • Tabel hasil pencarian lengkap. Ini saya yakin secara teoritis tercepat, tetapi akan membutuhkan tabel pencarian 1TB - belum praktis - mungkin dalam beberapa tahun jika Hukum Moore terus berlaku.

Trauma Digital
sumber
Jika perlu saya dapat menghitung latensi rata-rata untuk semua input yang diizinkan.
Digital Trauma
jmpdan jcctidak memiliki latensi, hanya biaya throughput. Prediksi cabang + eksekusi spekulatif berarti dependensi kontrol bukan bagian dari rantai ketergantungan data.
Peter Cordes