Przetwarzanie potokowe

przetwarzanie potokowe: sposób sekwencyjnego przetwarzania danych, przyśpieszający pracę komputera. Duża ilość instrukcji ‘nachodzi’ na siebie w trakcie wykonania. Korzysta ono z podobieństw pomiędzy instrukcjami w trakcie wykonania. Każdy fragment przetwarzania potokowego zawiera część instrukcji – fragmenty te nazywamy pipe stages albo pipe segments.

Czas pomiędzy wykonaniem każdego segmentu to jeden cykl procesora.

Przy idealnych warunkach, czas wykonania instrukcji na procesorze z przetwarzaniem potokowym jest równy: czasowi wykonania na procesorze bez przetwarzania/ilości pipe stages.

RISC (ex. MIPS)

• wszystkie operacje na zmiennych operują na zmiennych w rejestrach

• jedyne operacje oddziałujące na pamięć to load i store

• jest niewielka ilość instrukcji, zazwyczaj o jednym rozmiarze

• rozgałęzienia są uwarunkowane

Prosta implementacja bez przetwarzania potokowego składa się z pięciu instrukcji:

1. Instruction fetch cycle (IF)
   pobranie instrukcji

2. Instruction decode/register fetch cycle (ID)
   instrukcja zostaje odkodowana, przeczytana, (zostaje wykonany test równości na namierzony możliwy cel)

3. Execution/effective address cycle (EX)
   może nastąpić odwołanie do pamięci, z rejestru do pamięci, z rejestru do immediate

4. Memory access (MEM)
   load/store – informacja zostaje oczytana lub zapisana w pamięci

5. Write-back cycle (WB)
   operacje arytmetyczne na rejestrach lub zapisywanie danych w przypadku instrukcji load

Pięcio-krokowy pipeline: każdy cykl zegara staje się jednym krokiem pipeline. Kroki te mogą być wykonywane równolegle. Mimo, iż wykonanie instrukcji zabiera 5 cykli zegara, CPI (cycles per instruction) zmienia się na 1.

Problemy:

• jednostka logiczna nie można na raz wykonywać obliczeń ORAZ obliczać efektywnego adresu

• unikanie problemów opiera się na:

  • osobnych odnośnikach pamięci do instrukcji i danych (zaimplementowanych jako caches)

  • rejestry są używane w dwóch krokach – czytanie w ID i zapisywanie w WB

  • aby rozpocząć nową instrukcję w każdym kroku, trzeba zwiększyć licznik programu (program counter) cyklu, a to może nastąpić tylko w kroku IF (pierwszym), w przygotowaniu na kolejną instrukcję (czyli po pobraniu)

Pipeline registers – umieszczone pomiędzy poszczególnymi krokami pipeline, z dopasowanym czasem; gdy osiągną ten czas, są w nich zapisywane ostateczne dane z poprzedniego cyklu (pozwala to na unikniecie problemów przy opóźnieniach).

Przyśpieszenie zyskane od pipeline zależy od długości poszczególnych cykli – nawet jeśli na każdą instrukcję jest przewidywany jeden, rzeczy typu dostęp do pamięci mogą zająć, na przykład, cztery takty; takt zegara jest dopasowany do najwolniejszego zadania.

Konflikty pipeline:

• konflikt zasobów (gdy kilka instrukcji żąda jednego zasobu)

• konflikt danych (jeśli argument instrukcji potrzebuje danych wyliczonych przez instrukcję bezpośrednio poprzedzającą)
  //forwarding

• konflikt sterowania (podczas wykonania instrukcji sterujących, jak skoku warunkowego)
  //przewidywanie skoków

w tym miejscu na wykładzie są wzory których nie chciało mi się przepisywać

Hazard strukturalny

Wykonywanie wielu instrukcji na raz wymaga, aby potokowanie funkcjonalnych części oraz duplikacja źródeł zezwalała na wszystkie możliwe wykonania instrukcji w potoku. Jeśli jakaś kombinacja instrukcji nie może być wykonana ze względu na konflikt źródeł, procesor doświadcza hazardu, i niektóre części operacji nie są w pełny potokowane.

Sytuacja ta może zajść, gdy potrzebujemy dostępu do pamięci, rejestrów albo procesora.

W celu rozwiązana problemu, jedna z instrukcji zostaje zatrzymana do czasu, gdy wymagane źródło jest dostępne. Tego typu pauza jest nazywana „pipeline bubble”.

Nie mogą zajść dwa ‘memory access’ w jednym czasie

Koszty hazardu

Odnośniki do danych zajmują 40% procesu; idealne CPI jest równe 1; cykl zegara dla procesora z hazardem jest 1,5 raza większy niż dla procesora bez hazardu. Ogólnie, procesor bez hazardu jest 1,3 raza szybszy.

Data Hazard

Zachodzi, kiedy w kolejnych instrukcjach są niezbędne dane uzyskane w poprzednich. Np., w pierwszym add R1,R2,R3; w kolejnym mul R4,R1,R5.

Rozwiązanie: forwarding (bypassing albo short-circuiting)

• wynik działań logicznych – ALU – można stworzyć bajpasy pamiędzy ALU pierwszej instrukcji I alu kolejnej instrukcji

• metoda z oczekiwaniem – wartości są zapisane w blokach po danej instrukcji i można ich już używać;

• The load instruction can bypass its results to the AND and OR instructions, but not to the DSUB, since that would mean forwarding the result in “negative time”.

• The Load instruction has a delay or latency that cannot be eliminated by forwarding alone (we need to add pipeline interlock).

Branch Hazard

W przypadku rozgałęzienia, procedura następująca zostaje odczytana od razu – dopier wtedy, gdy program wyliczy swój przeskok, zostaje ona zatrzymana, a fetch part zostaje zrestartowana, gdy znamy już następnika instrukcji branch.

Redukcja strat

• freeze/flush – zatrzymywanie lub usuwanie każdej instrukcji po rozgałęzieniu do czasu poznania jego celu;

• przewidywanie, że skok się nie wykona – rozpoczynanie kolejnej instrukcji i wykonywanie jej do czasu, aż nie jest pewne, że skok się wykonał

• przewidywanie, że skok się wykona - analogicznie

Opóźniony skok (Delayed Branch)

Krok następujący po rozgałęzieniu zostaje wykonany niezależnie od tego, czy skok się dokona, czy nie.

Optymalizacja wykonania pętli:

• zmniejszanie zależności danych i zależności nazw

• zmniejszenie zależności nazw – używanie większej ilości rejestrów