Najszybszy sposób na obliczenie rzędu wielkości w zespole x86

12

Zadanie jest proste: napisz asembler, który oblicza rząd wielkości liczby całkowitej przy użyciu jak najmniejszej liczby cykli zegara.

  • Rząd wielkości jest zdefiniowany jako log10, a nie log2.
  • Zakres ważny wkład jest 0do włącznie. Zachowanie danych wejściowych poza tym zakresem jest niezdefiniowane.1012
  • Wartości należy zaokrąglić w dół do najbliższej liczby całkowitej, z wyjątkiem tego, że przy danych wejściowych 0wyjście powinno być 0. (Można to uznać za najlepszą reprezentację ujemnej nieskończoności możliwą w liczbach całkowitych bez znaku).
  • Musi być montażem x86.
  • Liczba całkowita musi być wartością czasu wykonywania , a nie liczbą całkowitą statyczną / wbudowaną. Nie wiemy więc, co to jest w czasie kompilacji.
  • Załóżmy, że masz już załadowaną liczbę całkowitą do rejestru. (Ale w celu zwiększenia przejrzystości należy uwzględnić ustawienie wartości w rejestrze).
  • Nie można wywoływać żadnych zewnętrznych bibliotek ani funkcji.
  • Bezpłatnie korzystać z dowolnych instrukcji dostępnych w dokumentach firmy Intel .
  • Nie C.
  • Dowolna z ~ 7 architektur Intel Core jest akceptowalna (wymienionych na stronie 10 ). Idealnie Nehalem (Intel Core i7).

Zwycięską odpowiedzią jest ta, która wykorzystuje najmniejszą możliwą liczbę cykli zegara. Oznacza to, że może mieć najwięcej operacji na sekundę. Przybliżone podsumowania cyklu zegara znajdują się tutaj: http://www.agner.org/optimize/instruction_tables.pdf . Obliczanie cykli zegara może nastąpić po opublikowaniu odpowiedzi.

math fastest-algorithm assembly Lance Pollard
źródło
Czy „FYL2X” i inne instrukcje FPU są dozwolone?
Cyfrowa trauma
1
Czy wynikiem powinna być liczba całkowita? Jeśli tak, w jaki sposób należy go zaokrąglić?
Cyfrowa trauma
3
Więc wejście i wyjście są liczbami całkowitymi, tak? Ale wejście może być tak duże, jak 10 ^ 12, więc jest za duże na 32-bitowy int. Czy zatem przyjmujemy 64-bitową liczbę całkowitą?
Paul R
3
Czy kryterium wygranej opiera się na maksymalnej lub średniej liczbie cykli? A jeśli to średnia, jaki jest rozkład nakładów?
Runer112
2
Który procesor jest celem? W połączonym dokumencie wymieniono ponad 20 różnych procesów (AMD, Intel, inne) i występują znaczne różnice w opóźnieniach.
Cyfrowa trauma

Odpowiedzi:

8

7 cykli, stały czas

Oto rozwiązanie oparte na mojej odpowiedzi na to SO Pytanie . Używa BSR do zliczania, ile bitów jest potrzebnych do utrzymania liczby. Sprawdza, ile cyfr dziesiętnych jest potrzebnych do przedstawienia największej liczby, jaką może pomieścić wiele bitów. Następnie odejmuje 1, jeśli faktyczna liczba jest mniejsza niż najbliższa potęga 10 z taką liczbą cyfr.

    .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

Kompiluje na GCC 4.6.3 dla Ubuntu i zwraca wartość w kodzie wyjścia.

Nie jestem pewien interpretacji tej tabeli cykli dla dowolnego nowoczesnego procesora, ale używając metody @ DigitalTrauma na procesorze Nehalim, mam 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
źródło
Och - widziałem DigitalTrauma po tym, jak zacząłem pisać moje. Podobne pomysły. Korzystając z jego metodologii liczenia, myślę, że dostaj 3,1,1,1 = 6 dla BSR, MOV, CMP, SBB
AShelly
Tak, myślę, że twoje bije moje. Po prostu pokazuje: a) nie jestem programistą a) b) najlepiej jest zostawić nas samych zwykłym śmiertelnikom ;-)
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.
kot
1
w prawo, aw następnym wierszu jest napisane: „Załóżmy, że masz już liczbę całkowitą załadowaną do rejestru. (Ale w celu zachowania przejrzystości uwzględnij ustawienie wartości w rejestrze)”. Tak właśnie zrobiłem.
AShelly
zamień movzx eax na mov al. Górne 24 bity eaxa będą już wynosić zero, więc zx jest zbędny (i jest drogi).
Peter Ferrie
6

Najlepszy przypadek 8 cykli, Najgorszy przypadek 12 cykli

Ponieważ pytanie nie jest jasne, opieram to na opóźnieniach Ivy Bridge.

Podejście polega na użyciu instrukcji bsr(odwrotne skanowanie bitów) jako log2 biedaka (). Wynik jest używany jako indeks do tabeli skoków, która zawiera wpisy dla bitów od 0 do 42. Zakładam, że biorąc pod uwagę, że operacja na danych 64-bitowych jest niejawnie wymagana, to użycie bsrinstrukcji jest OK.

W najlepszych przypadkach dane wejściowe z możliwością zbierania mogą odwzorować bsrwynik bezpośrednio na wielkość. np. dla danych wejściowych z zakresu 32-63 bsrwynikiem będzie 5, który jest odwzorowany na wielkość 1. W tym przypadku ścieżka instrukcji to:

Instruction    Latency

bsrq                 3
jmp                  2
movl                 1
jmp                  2

total                8

W najgorszym przypadku dane wejściowe bsrzostaną odwzorowane na dwie możliwe wielkości, więc wpis z możliwością zbierania dodaje jeszcze jedną wartość, cmpaby sprawdzić, czy wartość wejściowa jest> 10 n . Np. Dla danych wejściowych z zakresu 64-127 bsrwynik będzie wynosić 6. Odpowiedni wpis , który można przesuwać, sprawdza, czy dane wejściowe> 100, i odpowiednio ustawia wielkość wyjściową.

Dodatkowo dla ścieżki najgorszego przypadku mamy dodatkową instrukcję mov, aby załadować 64-bitową wartość natychmiastową do użycia w cmp, więc ścieżka instrukcji najgorszego przypadku to:

Instruction    Latency

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

total               12

Oto kod:

    /* 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 */

Zostało to wygenerowane głównie z danych wyjściowych asemblera gcc dla kodu C w wersji proof-of-concept, który napisałem . Zauważ, że kod C używa obliczalnego goto do implementacji tabeli skoków. Używa również __builtin_clzll()wbudowanego gcc, który kompiluje się do bsrinstrukcji (plus an xor).

Rozważałem kilka rozwiązań, zanim doszedłem do tego:

  • FYL2Xobliczyć logarytm naturalny, a następnie FMULprzez niezbędną stałą. Prawdopodobnie wygrałoby to, gdyby był to konkurs [tag: instrukcja: golf]. Ale FYL2Xma opóźnienie 90-106 dla mostu Ivy.

  • Zakodowane wyszukiwanie binarne. To może faktycznie być konkurencyjne - zostawię to komuś innemu do wdrożenia :).

  • Kompletna tabela wyników. Jestem pewien, że jest teoretycznie najszybszy, ale wymagałby tabeli przeglądowej 1 TB - jeszcze niepraktycznej - może za kilka lat, jeśli Prawo Moore'a będzie nadal obowiązywać.

Cyfrowa trauma
źródło
W razie potrzeby mogę obliczyć średnie opóźnienie dla wszystkich dozwolonych danych wejściowych.
Cyfrowy uraz
jmpi jccnie mają opóźnień, tylko koszty przepustowości. Prognozowanie gałęzi + wykonywanie spekulacyjne oznaczają, że zależności sterujące nie są częścią łańcuchów zależności danych.
Peter Cordes,