Jak działa przewidywanie gałęzi, jeśli nadal trzeba sprawdzać warunki?


30

Czytałem popularną odpowiedź na temat przewidywania gałęzi z https://stackoverflow.com/q/11227809/555690 i coś mnie dezorientuje:

  • Jeśli dobrze zgadłeś, nadal trwa.
  • Jeśli pomyliłeś się, kapitan zatrzyma się, cofnie i krzyknie na ciebie, aby przełączyć przełącznik. Następnie może ponownie uruchomić inną ścieżkę.

Jeśli dobrze zgadniesz za każdym razem, pociąg nigdy nie będzie musiał się zatrzymywać.

Jeśli zbyt często się mylicie, pociąg poświęci dużo czasu na zatrzymywanie się, tworzenie kopii zapasowych i restartowanie.

Ale to, czego nie rozumiem: aby wiedzieć , czy przypuszczenie było dobre czy złe, trzeba dokonać sprawdzenia stanu anyway . Jak więc działa przewidywanie gałęzi, jeśli tak czy inaczej nadal wykonujesz tę samą kontrolę warunkową?

Próbuję powiedzieć, czy przewidywanie gałęzi nie jest dokładnie takie samo jak brak przewidywania gałęzi, ponieważ i tak wykonujesz te same kontrole warunkowe? (oczywiście się mylę, ale nie rozumiem)


1
Ten artykuł na wiki wyjaśnia całkiem nieźle.
Enderland

8
Nowoczesny procesor jest przetwarzany potokowo i może wykonywać kilka czynności jednocześnie. W związku z tym może zacząć odgadywać, gdy wciąż zastanawia się, czy poprawnie zgadł. Jeśli przypuszczenie było słuszne, rurociąg nadal działa. W przypadku błędnego odgadnięcia potok jest odrzucany, a wykonywanie rozpoczyna się od punktu „właściwej odpowiedzi”.
markspace

2
Literatura pokrewna: rurociąg . Poleciłbym również ponownie przeczytać zaakceptowaną odpowiedź na to pytanie SO, ponieważ odpowiada ona na twoje pytanie tutaj.

Odpowiedzi:


19

Oczywiście warunek jest sprawdzany za każdym razem. Ale do czasu sprawdzenia jest już daleko do potoku procesora. W międzyczasie inne instrukcje również weszły do ​​rurociągu i są na różnych etapach realizacji.

Zwykle po warunku natychmiast następuje warunkowa instrukcja rozgałęzienia, która albo rozgałęzia się, jeśli warunek uzyska wartość PRAWDA, albo przepada, jeśli warunek ma wartość FAŁSZ. Oznacza to, że istnieją dwa różne strumienie instrukcji, które mogą być ładowane do potoku po instrukcji warunku i instrukcji rozgałęzienia, w zależności od tego, czy warunek ma wartość PRAWDA, czy FAŁSZ. Niestety, natychmiast po załadowaniu instrukcji warunku i instrukcji rozgałęzienia, CPU nie wie jeszcze, co oceni warunek, ale nadal musi ładować rzeczy do potoku. Wybiera więc jeden z dwóch zestawów instrukcji na podstawie zgadnięcia, co oceni warunek.

Później, gdy instrukcja warunku przechodzi przez rurociąg, nadszedł czas na ocenę. W tym czasie procesor dowiaduje się, czy jego domysł był właściwy, czy zły.

Jeśli przypuszczenie okaże się słuszne, gałąź poszła we właściwe miejsce, a właściwe instrukcje zostały załadowane do rurociągu. Jeśli okaże się, że zgadywanie było błędne, wówczas wszystkie instrukcje, które zostały załadowane do potoku po instrukcji warunkowej gałęzi były błędne, należy je odrzucić, a pobieranie instrukcji musi rozpocząć się ponownie od właściwego miejsca.

Poprawka

W odpowiedzi na komentarz StarWeaver, aby zorientować się, co CPU musi zrobić, aby wykonać jedną instrukcję:

Rozważmy coś tak prostego, jak to, MOV AX,[SI+10]co my, ludzie naiwnie myślimy, jako „załaduj AX słowem o SI plus 10”. Z grubsza procesor musi:

  1. emitować zawartość komputera („rejestr licznika programu”) na magistralę adresową;
  2. odczytać kod operacji z magistrali danych;
  3. Przyrost PC;
  4. zdekoduj kod operacji, aby dowiedzieć się, co z nim zrobić;
  5. wyślij zawartość komputera na magistralę adresową;
  6. odczytać operand instrukcji (w tym przypadku 10) z magistrali danych;
  7. Przyrost PC;
  8. podaj operand i SI do sumatora;
  9. wyślij wynik sumatora do magistrali adresowej;
  10. odczytać AX z magistrali danych.

To aż 10 kroków. Niektóre z tych kroków zostaną zoptymalizowane nawet w procesorach niepotokowych, na przykład procesor prawie zawsze zwiększa PC równolegle z następnym krokiem, co jest łatwe, ponieważ PC jest bardzo specjalnym rejestrem, który jest nigdy nie używane do żadnego innego zadania, więc nie ma możliwości rywalizacji między różnymi częściami procesora o dostęp do tego konkretnego rejestru. Ale wciąż mamy 8 kroków do tak prostej instrukcji i zauważmy, że już zakładam pewien stopień wyrafinowania w imieniu procesora, na przykład zakładam, że nie będzie potrzeby wykonywania całego dodatkowego kroku dla sumator do faktycznego przeprowadzenia dodawania, zanim wynik będzie można odczytać z niego,

Teraz zastanów się, że istnieją bardziej skomplikowane tryby adresowania, takie jak MOV AX, [DX+SI*4+10], a nawet znacznie bardziej skomplikowane instrukcje, takie jak MUL AX, operandktóre faktycznie wykonują pętle wewnątrz procesora, aby obliczyć ich wynik.

Chodzi mi tutaj o to, że metafora „poziomu atomowego” jest daleka od odpowiedniej dla poziomu instrukcji procesora. Może być odpowiedni dla poziomu kroku potoku, jeśli nie chcesz schodzić zbyt daleko w dół do faktycznego poziomu bramki logicznej.


2
Huh, zastanawiam się, czy częścią problemu, który ludzie (w tym ja) mają na temat zrozumienia tego, jest to, że bardzo trudno (i tak dla mnie) wyobrazić sobie procesor posiadający tylko częściową wiedzę na temat pojedynczej instrukcji; albo mieć kilka niedokończonych instrukcji „przechodzących przez piec do pizzy”… przynajmniej dla mnie to wrażenie przesunięcia skali do atomu, gdy jestem przyzwyczajony do pracy z elementami między zestawem prostowników a poziomem tokarki.
StarWeaver,

1
@StarWeaver Podobał mi się twój komentarz, więc poprawiłem swoją odpowiedź, aby się do niego odnieść.
Mike Nakis,

1
Wow, niezłe odkrycie. Zazwyczaj zapominam, ile kosztuje tylko przenoszenie słów w bardziej przydatne miejsca. Nadal wizualizuję procesor jako zestaw pieców do pizzy z napędem pasowym: 3.
StarWeaver,

Warto pamiętać, że pytanie o przepełnienie stosu powiązane z PO - pytanie o 1,3 miliona wyświetleń, które prawdopodobnie wprowadziło ponad milion programistów do nieznanego wcześniej faktu, że nawet „przewidywanie gałęzi” istnieje - pokazuje przykład w Javie . Dla ludzi takich jak ja, którzy są przyzwyczajeni do pracy na poziomie abstrakcji, który zapewniają nam języki takie jak Java, nawet MOV AX,[SI+10]jest obcy, a nie „prosty”; większość programistów dzisiaj nigdy nie pisała asemblera. Nie „naiwnie myślimy” o tym, że coś znaczy.
Mark Amery

@ Mark Bardzo dobrze, dobrze, myślałem, że to raczej oczywiste, że przez „my ludzie” mam na myśli „my ludzie, którzy odważą się pisać asembler”. Chodzi o to, że nawet programiści w asemblerze nie myślą o rurociągu przez cały czas, a nawet wcale.
Mike Nakis

28

Pomyśl o tym jak o podróży bez GPS. Dojeżdżasz do skrzyżowania i myślisz, że musisz skręcić, ale nie jesteś do końca pewien. Więc skręć, ale poproś pasażera o sprawdzenie mapy. Może zanim skończysz kłócić się o to, gdzie jesteś. Gdybyś miał rację, jesteś o trzy mile dalej niż byłbyś, gdybyś zatrzymał się i kłócił przed skrętem. Jeśli się myliłeś, musisz się odwrócić.

Potoki procesora działają w ten sam sposób. Zanim zdołają sprawdzić stan, są już na dobrej drodze. Różnica polega na tym, że nie muszą jechać trzy mile wstecz, po prostu tracą przewagę. Oznacza to, że próba nie jest szkodliwa.


2
To wyjaśnienie jest zgrabne.
sharptooth

2

Z mojego zrozumienia, przewidywanie gałęzi jest najbardziej przydatne, gdy warunek, który musisz sprawdzić, wymaga wyniku czegoś, co jest drogie lub wciąż w toku, a w przeciwnym razie kręcisz kciukami, czekając, aż wartość oceni warunek.

Dzięki takim funkcjom, jak wykonanie poza kolejnością, możesz użyć przewidywania rozgałęzień, aby rozpocząć wypełnianie pustych miejsc w potoku, których w przeciwnym razie procesor nie byłby w stanie wykorzystać. W sytuacji, gdy z jakiegoś powodu nie ma żadnych bezczynnych cykli w rurociągu, to tak, nie ma korzyści z przewidywania rozgałęzień.

Ale kluczem jest to, że procesor rozpoczyna pracę dla jednej z przewidywanych gałęzi, ponieważ nie może jeszcze ocenić samego warunku.


1

Skrócona forma:

Niektóre procesory mogą rozpocząć pracę nad nową instrukcją przed ukończeniem starej. Są to procesory wykorzystujące przewidywanie gałęzi.

Przykład pseudokodu:

int globalVariable;
int Read(int* readThis, int* readThat)
{
    if ((globalVariable*globalVariable % 17) < 5)
       return *readThis;
    else
       return *readThat;
}

Powyższy kod sprawdza warunek i na podstawie wyniku musi zwrócić wartość zapisaną w miejscu w pamięci addThislub wartość zapisaną w readThat. Jeśli przewidywanie gałęzi przewiduje, że warunek będzie true, CPU już odczyta wartość zapisaną w miejscu pamięci addThispodczas wykonywania obliczeń niezbędnych do oceny ifinstrukcji. To jest uproszczony przykład.


1

Tak, warunek jest sprawdzany w obu kierunkach. Zaletą przewidywania gałęzi jest to, że można wykonywać pracę zamiast czekać na wynik sprawdzenia stanu.

Powiedzmy, że musisz napisać esej, który może dotyczyć tematu A lub tematu B. Z poprzednich esejów wiesz, że twój nauczyciel lubi temat A lepiej niż B i wybiera go częściej. Zamiast czekać na jego decyzję, możesz zacząć pisać esej na temat pierwszego tematu. Teraz są dwa możliwe wyniki:

  1. Zacząłeś swój esej na niewłaściwy temat i musisz porzucić to, co napisałeś do tej pory. Musisz zacząć pisać o innym temacie i to tyle samo czasu, ile czekałeś.
  2. Zgadłeś dobrze i już wykonałeś pracę.

Nowoczesne procesory przez większość czasu pracują na biegu jałowym, ponieważ czekają na odpowiedzi We / Wy lub wynik innych obliczeń. Ten czas może zostać wykorzystany na wykonanie przyszłych prac.

Nawet jeśli musisz odrzucić to, co robisz w tym czasie bezczynności - najprawdopodobniej będzie bardziej skuteczne, jeśli będziesz w stanie odgadnąć, którą ścieżkę wybierze program. Nowoczesne procesory mają tę zdolność.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.