Powolna instrukcja jmp

Question

Jako kontynuację mojego pytania The advantages of using 32bit registers/instructions in x86-64, zacząłem mierzyć koszty instrukcji. Mam świadomość, że zostało to zrobione wiele razy (na przykład Agner Fog), ale robię to dla zabawy i samokształcenia.

Mój kod badania jest dość prosty (dla uproszczenia tutaj jako pseudo kod, w rzeczywistości w asemblerze):

for(outer_loop=0; outer_loop<NO;outer_loop++){ 
    operation #first 
    operation #second 
    ... 
    operation #NI-th 
} 

Ale jeszcze kilka rzeczy, które należy rozważyć.

1. Jeśli wewnętrzna część pętli jest duża (duży NI>10^7) cała zawartość pętli nie pasuje do pamięci podręcznej instrukcji, a więc muszą być ładowane w kółko, dzięki czemu prędkość RAM zdefiniować czas potrzebny na wykonanie. Na przykład dla dużych części wewnętrznych, xorl %eax, %eax (2 bajty) jest o 33% szybszy niż xorq %rax, %rax (3 bajty).
2. Jeśli jest mały i cała pętla łatwo mieści się w pamięci podręcznej instrukcji, wówczas xorl %eax, %eax i xorq %rax, %rax są równie szybkie i mogą być wykonywane 4 razy na cykl zegara.

Jednak ten prosty model nie zawiera wody dla instrukcji jmp. Dla jmp -instruction mój kod test wygląda następująco:

for(outer_loop=0; outer_loop<NO;outer_loop++){ 
    jmp .L0 
    .L0: jmp .L1 
    L1: jmp L2 
    .... 
} 

a wyniki:

1. dla "dużych" rozmiarach pętli (już dla NI>10^4) I Działanie 4.2 ns/jmp -instruction (oznaczałoby 42 bajty załadowane z pamięci RAM lub około 12 cykli zegara na moim komputerze).
2. Dla małych rozmiarów pętli (NI<10^3) Zmierzam instrukcję 1 ns/jmp- (czyli około 3 cykli zegara, co wydaje się wiarygodne - tabele Agner Fog pokazują koszty 2 cykli zegara).

Instrukcja jmp LX używa kodowania 2-bajtowego eb 00.

Tak, moje pytanie: Co może być wyjaśnienie wysokiego kosztu jmp -instrukcja w "dużych" pętli?

PS: Jeśli chcesz ją wypróbować na komputerze, można pobrać skrypty z here, wystarczy uruchomić sh jmp_test.sh w src -folder.

---

Edit: wyniki doświadczalne potwierdzające teorię BTB rozmiarze Piotra.

Poniższa tabela przedstawia cykli na instrukcję dla różnych wartości ǸI (względem NI = 1000):

|oprations/ NI  | 1000 | 2000| 3000| 4000| 5000| 10000| 
|---------------------|------|------|------|------|------|------| 
|jmp     | 1.0 | 1.0 | 1.0 | 1.2 | 1.9 | 3.8| 
|jmp+xor    | 1.0 | 1.2 | 1.3 | 1.6 | 2.8 | 5.3| 
|jmp+cmp+je (jump) | 1.0 | 1.5 | 4.0 | 4.4 | 5.5 | 5.5| 
|jmp+cmp+je (no jump) | 1.0 | 1.2 | 1.3 | 1.5 | 3.8 | 7.6| 

Jak widać:

1. Dla instrukcji jmp, grupę (jeszcze nieznane) zasoby stają się rzadkie, a to prowadzi do spadku wydajności dla ǸI większego niż 4000.
2. Ten zasób nie jest udostępniany z takim instruktorem jony jako xor - degradacja wydajności kopie nadal dla NI około 4000, jeśli jmp i xor są wykonywane po sobie.
3. Ale ten zasób jest udostępniany je jeśli skok jest wykonany - na jmp + je po drugim, zasób staje się rzadkością na NI około 2000.
4. Jednak jeśli je nie skakać w ogóle, zasób staje skąpe po raz kolejny dla NI około 4000 (4 linia).

Matt Godbolt's branch-prediction reverse engineering articles ustala, że ​​pojemność bufora docelowego oddziału wynosi 4096 pozycji. To jest bardzo mocny dowód na to, że brakujące wartości BTB są powodem obserwowanej różnicy przepustowości między małymi i dużymi pętlami jmp.

Answer 1

TL: DR: moje bieżące przypuszczenia kończą się wpisami BTB (branch target buffer). Zobacz poniżej.

---

Nawet jeśli jmp s są no-ops, CPU nie posiada dodatkowych tranzystorów do wykrywania tego szczególnego przypadku. Są obsługiwane tak jak każdy inny jmp, co oznacza konieczność ponownego uruchomienia instrukcji z nowej lokalizacji, tworząc bąbelek w potoku.

Aby dowiedzieć się więcej o skokach i ich wpływie na potokowe procesory, Control Hazards in a classic RISC pipeline powinno być dobrym wstępem do tego, dlaczego gałęzie są trudne dla potokowych procesorów. Przewodniki Agnera Fog wyjaśniają praktyczne implikacje, ale sądzę, że zakładają one pewną wiedzę ogólną.

---

Twój CPU Intel Broadwell has a uop-cache, który buforuje dekodowane instrukcje (odrębne od 32kiB L1 I-cache).

Rozmiar pamięci podręcznej uop wynosi 32 zestawy po 8 sposobów, z 6 odcieniami w linii, łącznie 1536 odcieni (jeśli każda linia jest zapakowana w 6 uops, o doskonałej wydajności). 1536 Uops zawiera się między 1000 a 10000 testowanych rozmiarów. Przed edycją przewidywałem, że odcięcie od wolnego do szybkiego będzie około 1536 pełnych instrukcji w pętli. Nie zwalnia to wcale, dopóki nie przekroczy 1536 instrukcji, więc myślę, że możemy wykluczyć efekty pamięci podręcznej. To nie jest tak proste pytanie, jak myślałem. :)

Uruchamianie z pamięci podręcznej uop (mały rozmiar kodu) zamiast dekoderów instrukcji x86 (duże pętle) oznacza, że ​​etapów, które rozpoznają instrukcje jmp, jest mniej etapów. Możemy więc oczekiwać, że bańki ze stałego strumienia skoków będą mniejsze, mimo że są poprawnie przewidywane.

Uruchamianie z dekoderów ma dać większą karę błędnego rozgałęzienia gałęzi (jak może 20 cykli zamiast 15), ale nie są to błędnie rozgałęzione gałęzie.

---

Choć CPU nie musi przewidzieć, czy oddział jest podjęte lub nie, może nadal korzystać z zasobów oddział przewidywania przewidzieć, że blok kodu zawiera podjętą oddział przed jego dekodowane.

Caching fakt, że istnieje gałąź w określonym bloku kodu, oraz jej docelowy adres, pozwala frontendowi rozpocząć pobieranie kodu z docelowego oddziału, zanim kodowanie jmp rel32 zostanie faktycznie zdekodowane. Pamiętaj, że dekodowanie instrukcji x86 o zmiennej długości jest trudne: nie wiesz, gdzie zaczyna się jedna instrukcja, dopóki nie zostanie zdekodowana poprzednia. Nie można więc po prostu dopasować strumienia instrukcji do bezwarunkowych skoków/wywołań, gdy tylko zostaną pobrane.

Moja obecna teoria mówi, że zwalniasz, gdy zabraknie wpisów bufora docelowego.

Zobacz także What branch misprediction does the Branch Target Buffer detect?, która ma dobrą odpowiedź i dyskusję w tym numerze Realworldtech thread.

Jedna bardzo ważna kwestia: BTB przewiduje, który blok ma zostać pobrany jako następny, a nie dokładne miejsce docelowe konkretnej gałęzi w bloku pobierania. Więc zamiast przewidywać cele dla wszystkich oddziałów w bloku FETCH the CPU just needs to predict the address of the next fetch.

---

Tak, przepustowość pamięci mogą być wąskim gardłem przy uruchamianiu bardzo wysoką przepustowość rzeczy jak XOR zerowania, ale jesteś uderzenie innego wąskiego gardła z jmp. CPU miałby czas, aby pobrać 42B z pamięci, ale to nie jest to, co robi. Prefetch może łatwo nadążyć z 2 bajtami na 3 zegary, więc powinno być prawie zero zera I-cache chybi.

W twoim xor z/bez testu REX, główna przepustowość pamięci mogła być w rzeczywistości wąskim gardłem, jeśli testowałeś z wystarczająco dużą pętlą, aby nie pasować do pamięci podręcznej L3. Zużywa 4 * 2B na cykl na CPU ~ 3GHz, który ma około max 25GB/s DDR3-1600MHz. Nawet pamięć podręczna L3 byłaby wystarczająco szybka, by nadążyć za 4 * 3B na cykl.

To interesujące, że pamięć główna BW jest wąskim gardłem; Początkowo domyślałem się, że dekodowanie (w blokach po 16 bajtów) będzie wąskim gardłem dla 3-bajtowych XOR-ów, ale myślę, że są one wystarczająco małe.

---

Należy również pamiętać, że jest to o wiele bardziej normalny pomiar czasów w rdzeniach cykli. Jednak twoje pomiary w ns są przydatne, gdy patrzysz na pamięć, jak sądzę, ponieważ niskie taktowanie dla oszczędzania energii zmienia stosunek częstotliwości rdzenia do szybkości pamięci. (np. wąskie gardła pamięci są mniejszym problemem przy minimalnej szybkości zegara procesora).

Do testowania porównawczego w cyklach zegarowych należy użyć perf stat ./a.out. Istnieją inne użyteczne liczniki wydajności, które są niezbędne do próby zrozumienia charakterystyki wydajności.

Zobacz x86-64 Relative jmp performance dla perf-counter wyniki Core2 (8 cykli na jmp), a niektóre nieznane mikroarchitektura gdzie ~ 10c na jmp.

---

Szczegóły nowoczesnych cech wydajności procesora są dość trudne do zrozumienia nawet w mniej lub bardziej warunkach białoskrzynkowe (czytanie Intela podręcznik optymalizacji, a co oni opublikowany dotyczące wewnętrznych CPU). Utkniesz wcześnie i często, jeśli będziesz nalegać na testowanie w czarnych skrzynkach, gdzie nie będziesz czytać artykułów takich jak artykuły arstechnica o nowym projekcie procesora, albo o bardziej szczegółowych rzeczach, takich jak David Kanter's Haswell microarch overview lub podobnych zapisach Sandybridge. Połączyłem wcześniej.

Jeśli utkniesz wcześniej i często jesteś w porządku i dobrze się bawisz, zawsze rób to, co robisz. Ale trudniej jest odpowiedzieć na twoje pytania, jeśli nie znasz tych szczegółów, jak w tym przypadku. :/np. moja pierwsza wersja tej odpowiedzi zakładała, że ​​przeczytałeś wystarczająco dużo, aby wiedzieć, czym była pamięć podręczna uop.