Asembler

Optymalizowanie programw dla Pentium

Daniel Lewandowski

W poprzednim artykule przedstawiem sposoby lepszego wykorzystania cache'u oraz parzystoci instrukcji procesora. Tym razem chciabym przedstawi jak mona poprawi wydajno tych czci kodu, ktre intensywnie korzystaj z koprocesora (FPU).

Koprocesor jest jednostk przeznaczon do wykonywania operacji na liczbach zmiennoprzecinkowych. Wczeniejszy generacje procesorw albo nie posiaday tej jednostki lub bya ona montowana oddzielnie od procesora na pycie gwnej. Sytuacja ta zmienia si w nowszych generacjach procesorw 486. W przypadku Pentium koprocesor jest montowany razem z procesorem tworzc tym samym jedn ko. Koprocesor Pentium ma podobnie jak procesor dwa ukady pipeline, ktre umoliwiaj jednoczesne wykonywanie dwch instrukcji w szczeglnym przypadku. Oglnie ukady te umoliwiaj wykonywanie instrukcji w ten sposb, e ich wykonanie nakada si w czasie. Oznacza to, e dwie instrukcje bd wykonywane krcej ni suma ich wykonania i duej ni najdusza z nich. Obydwie sytuacje w artykule bd nazywa parzystoci (mona znale pewn analogi midzy nakadaniem si czasu wykonania instrukcji koprocesora do parzystoci niedoskonaej procesora). Pentium jest pierwszym procesorem z serii x86, ktrego jednostka zmiennoprzecinkowa posiada pipeline. Aby wykorzysta nowe moliwoci Pentium potrzebna jest odpowiednia optymalizacja kodu.

Dziaania na danych w pamici. 

W przypadku procesora zaleca si jak najmniejsze odwoywanie si do pamici, a wiksze wykorzystanie dziaa na rejestrach. W przypadku koprocesora dziaania na pamici zamiast na rejestrach stosu nie powoduje adnych dodatkowych cykli zwizanych z odczytem lub zapisem do pamici.

Pseudo-parzysto kodu koprocesora. Instrukcje koprocesora nie mog by wykonywane jednoczenie jak instrukcje procesora. Niekiedy wykonywanie tych instrukcji nakada si na siebie (overlapping). Oczywicie ten sposb wykonywania instrukcji znacznie przypiesza kod, jednak taka sytuacja jest obarczona kilkoma warunkami, ktre musz zosta spenione. Przypadek, gdy instrukcje wykonywane s jednoczenie wystpuje gdy:
- pierwsza instrukcja (wykonywana w U-pipe) to: FLD, FADD, FSUB, FMUL, FDIV, FCOM, FUCOM, FTST, FBAS, FCHS lub FABS
- druga instrukcja (V-pipe) to FXCH
- nastpn instrukcj po FXCH jest instrukcja koprocesora; w innym przypadku wykonanie FXCH zajmuje dodatkowy cykl
- instrukcja FXCH jest pobierana z cache'u - podobnie jak w przypadku procesora koprocesor nie zna dugoci instrukcji dopki ich nie wykona i nie zaznaczy tych wielkoci w cache'u, std wynika, e instrukcja ta moe by uywana do dostpu do gbszych rejestrw koprocesora zamiast wczytywanie i zapisywania ich w pamici Jeeli chodzi o nakadanie czasu wykonania instrukcji to sytuacja taka nie moe nastpi gdy nastpna instrukcja wymaga wyniku poprzedniej instrukcji np.:

     FADD ST(0), [a] ; cykl 1-3
     FADD ST(1), [b] ; cykl 2-4
     FADD ST(3), [c] ; cykl 3-5
     FADD ST(3), [d] ; cykl 6-8

Opnienie wynika std, e ta operacja dodawania wymaga wyniku poprzedniej operacji i musi czeka na jej wykonanie Poniewa wikszo instrukcji dziaa tylko na stosie koprocesora - ST(0) nastpna instrukcja musi czeka na zakoczenie pierwszej. Instrukcja FXCH umoliwia zmian takiego stanu rzeczy. Jak wspomniaem w pewnych okolicznociach moe by ona wykonywana parzycie z poprzedni instrukcj. Instrukcja FXCH w rzeczywistoci nie przenosi fizycznie zawartoci rejestrw, tylko zamienia ich nazwy.
Zamiana nazw rejestrw nigdy nie powoduje dodatkowych opnie Wrcz przeciwnie - moliwa jest zamiana rejestrw wicej ni raz w cigu jednego cyklu. np. Poniszy program realizuje nastpujce instrukcje (pseudo-kod): 
a1+a2+a3+a4 b1+b2+b3+b4 c1+c2+c3+c4

Jak wida powysze instrukcje mona zrealizowa nastpujco:

     FLD [c1] ; cykl 1
     FADD [c2] ; cykl 2-4
     FADD [c3] ; cykl 5-7
     FADD [c4] ; cykl 8-10
     FLD [b1]  ; cykl 9
     FADD [b2] ; cykl 10-12
     FADD [b3] ; cykl 13-15
     FADD [b4] ; cykl 16-18
     FLD [a1]  ; cykl 17
     FADD [a2] ; cykl 18-20
     FADD [a3] ; cykl 21-23
     FADD [a4] ; cykl 24-26

w wyniku czego otrzymujemy:

     ST(0)= a1+a2+a3+a4
     ST(1)= b1+b2+b3+b4
     ST(2)= c1+c2+c3+c4

w 26 cykli. Jakby nie patrze jest to wynik do kiepski. Powyszy kod mona jednak zapisa nieco inaczej, w ten sposb aby dziaa szybciej:

     FLD [a1]   ; cykl 1
     FADD [a2]  ; cykl 2-4
     FLD [b1]   ; cykl 3
     FADD [b2]  ; cykl 4-6
     FLD [c1]   ; cykl 5
     FADD [c2]  ; cykl 6-8
     FXCH ST(2) ; cykl 6
     FADD [a3]  ; cykl 7-9
     FXCH ST(1) ; cykl 7
     FADD [b3]  ; cykl 8-10
     FXCH ST(2) ; cykl 8
     FADD [c3]  ; cykl 9-11
     FXCH ST(1) ; cykl 9
     FADD [a4]  ; cykl 10-12
     FXCH ST(2) ; cykl 10
     FADD [b4]  ; cykl 11-13
     FXCH ST(1) ; cykl 11
     FADD [c4]  ; cykl 12-14
     FXCH ST(2) ; cykl 12

W powyszym przykadzie otrzymujemy to samo co wczeniej ale tylko w 14 cyklach. Daje to - z grubsza liczc - 50% przypieszenia.

Powyszy przykad tworz trzy oddzielne wtki a, b, c. W celu najszybszego ich wykonania uywana jest instrukcja FXCH. Uywajc jej mamy dostp do wierzchoka stosu ST(0) i ominicia jakichkolwiek opnie wynikajcych z oczekiwania na zakoczenie instrukcji z niego korzystajcej (patrz opnienia w pierwszym przykadzie). Ukadanie takiego kodu wymaga "rcznego" wykonania kodu tak jak by to zrobi procesor i w kadym kroku trzeba bada rejestry koprocesora po wykonaniu kadej instrukcji. Jako wynik otrzymujemy zwykle kod dziaajcy znacznie szybciej od jego pierwowzoru. Przy tworzeniu kodu naley wykorzysta nastpujce informacje:
- wszystkie wersje instrukcji FADD, FSUB, FMUL i FILD zajmuj 3 cykle i istnieje moliwo naoenie czasu ich wykonania
- wykonanie nastpnej instrukcji FADD, FSUB, FILD, po poprzedzajcej j podobnej instrukcji, rozpoczyna si w nastpnym cyklu
- instrukcja FMUL rozpoczyna si dopiero w drugim cyklu po rozpoczciu poprzedniej instrukcji FMUL lub pary FMUL/FXCH np.:

     a3=a1*a2
     b3=b1*b2
     c3=c1*c2

     FLD [a1]   ; cykl 1
     FLD [b1]   ; cykl 2
     FLD [c1]   ; cykl 3
     FXCH ST(2) ; cykl 3
     FMUL [a2]  ; cykl 4-6
     FXCH       ; cykl 4
     FMUL [b2]  ; cykl 5-7 (opnienie)
     FXCH ST(2) ; cykl 5
     FMUL [c2]  ; cykl 7-9 (opnienie)
     FXCH       ; cykl 7
     FSTP [a3]  ; cykl 8-9
     FXCH       ; cykl 10 (nieparzysta z FSTP [a3] - FSTP nie jest parzysta z adn instrukcj w czasie zapisu do pamici zamiana rejestrw nie jest moliwa)
     FSTP [b3]  ; cykl 11-12
     FSTP [c3]  ; cykl 13-14

W tym przypadku mamy dwa opnienia: przed FMUL [b2] i FMUL [c2]. W obu przypadkach poprzednie mnoenie rozpoczyna si w poprzednim cyklu co powoduje owo wanie opnienie. Taki kod mona poprawi wstawiajc, w miar moliwoci inne instrukcje (FLD, FADD, FSUB), midzy dwie instrukcje FMUL. Rozdzielanie takie moe by rwnie wykonane za pomoc instrukcji procesora (o tym dalej).

     FLD [a1]   ; cykl 1
     FMUL [a2]  ; cykl 2-4
     FLD [b1]   ; cykl 3
     FMUL [b2]  ; cykl 4-6
     FLD [c1]   ; cykl 5
     FMUL [c2]  ; cykl 6-8
     FXCH ST(2) ; cykl 6
     FSTP [a3]  ; cykl 7-8
     FSTP [b3]  ; cykl 9-10
     FSTP [c3]  ; cykl 11-12

Oczywicie sytuacja gdy mamy do wykonania trzy rne wtki zdarza si rzadko. Zwykle mamy do czynienia z jednym, duym wyraeniem. W takim wypadku naley podzieli wyraenie na kilka mniejszych wtkw (sze dodawa rozkadamy na trzy wtki po 2 dodawania). Nie wszystkie instrukcje koprocesora mog by parzyste. Czasami wykonanie instrukcji koprocesora moe przysoni wykonanie instrukcji procesora np. Wykonanie FDIV zajmuje 39 cykli i nastpna instrukcja koprocesora moe by wykonana dopiero w dwch ostatnich cyklach, natomiast w czasie wykonywania FDIV, oprcz pierwszego cyklu, procesor moe wykonywa swoje instrukcje:

     FDIV       ; cykl 1-39
     FXCH       ; cykl 1-2 (nieparzyste z instrukcj procesora)
     CMC        ; cykl 3-4
     RCR EAX, 1 ; cykl 5
     INC EBX    ; cykl 5
     FADD [x]   ; cykl 38-40
     FXCH       ; cykl 38
     FMUL       ; cykl 40-42 (instrukcja czeka na wykonanie dzielenia)

Jeeli nie mamy adnej instrukcji procesora, ktra moe by przysonita przez FDIV lub FSQRT, to mona wstawi dowolny odczyt spod adresu, do ktrego odwouje si nastpna instrukcja koprocesora. np.

     FDIV QWORD PTR [EBX]
     CMP [ESI], EAX
     FMUL QWORD PTR [ESI]

W tym przypadku instrukcja CMP [ESI], EAX wymusza zaadowanie do cache'u danych spod adresu [ESI]. W ten sposb FMUL nie powoduje powstania opnie zwizanych z odczytem danych. 

Dziaania zmiennoprzecinkowe na liczbach cakowitych.

Zaleca si unikania uywania instrukcji FIADD, FISUB itp. zamiast tego naley uy FILD i odpowiedniej operacji zmiennoprzecinkowej. np.:

uycie jednej instrukcji na liczbach cakowitych:

     FIADD [a] ; cykl 1-4

uycie kilku instrukcji zmiennoprzecinkowych:

     FILD [a]   ; cykl 1
     FADD ST(1) ; cykl 2-4

Ale cykle 3,4 mog by uyte przez inne instrukcje. Natomiast FIADD nie pozwala na to. 

     Instrukcja FST(P) 

Jeeli instrukcja zapisuje wynik operacji, ktra zakoczya dziaanie w poprzednim cyklu to wykonanie FST(P) zajmuje dodatkowy 1 cykl. Dodatkowo w czasie wykonywania tej instrukcji adna inna instrukcja koprocesora lub procesora nie moe by wykonywana rwnolegle.

Dzielenie i mnoenie zmiennoprzecinkowe a staoprzecinkowe 

Procesor wykorzystuje jednostk zmiennoprzecinkow do wykonywania mnoenia liczb cakowitych - instrukcje FMUL i (i)mul nie mog by wykonywane rwnolegle. Inaczej wyglda sytuacja w przypadku instrukcji FDIV i (i)div. Obie instrukcje maj swoje oddzielne ukady i tym samym mamy moliwo wykonania dwch dziele w czasie jednej operacji. Pozwala to znaczne przypieszenie tych fragmentw kodu, ktre intensywnie korzystaj z dzielenia a czas wykonania powinien by jak najkrtszy (wyznaczanie delt w przypadku teksturowania, cieniowania itp.). np.

     FILD [b1]
     FILD [b2]
     MOV EAX, [a1]
     MOV EBX, [a2]
     XOR EDX, EDX ;jeeli chcemy wykona instrukcj IDIV to zamiast tej linii naley wpisa: MOV EDX, EAX; 
     SAR EDX, 31
     FDIV
     DIV EBX
     FISTP [b]
     MOV [a], EAX

W tym przykadzie instrukcja DIV wykonywana jest w czasie rwnolegle z FDIV. Opnienie wnosi tu powolna instrukcja FISTP ale i tak cao jest szybsza ni dwie oddzielne instrukcje dzielenie staoprzecinkowego.

Literatura:

[1] "Optimizations for Intel's 32-Bit Processors"
[2] "How to optimize for the Pentium processor" Agner Fog

