Wstęp do Informatyki

Wykład 9

RISC – Komputery o

zredukowanej liście

rozkazów

Autor: Dr hab. Marek J.

Greniewski

Innowacje od czasu

komputera von Neumana

•

Koncepcja rodziny

. Wprowadzona w 1964 roku

przez IBM w S/360 i

wkrótce potem przez DEC w

PDP8. Koncepcja zakładała oddzielenie

architektury od organizacji komputera.

•

Mikroprogramowana jednostka sterująca

.

Zasugerowana przez Wilkesa w 1951 roku,

zrealizowana w 1964 roku w IBM S/360.

•

Pamięć podręczna

. Wprowadzona w modelu 85

IBM S/360 w 1968 roku.

•

Przetwarzanie potokowe

: rozkazów i przetwarzanie

wektorowe.

•

Wieloprocesorowość

. Bardzo szeroka kategoria

zróżnicowanych rozwiązań.

•

Komputery RISC

. Architektura wprowadzona

wbrew wcześniejszym tendencjom – wzbogacania

listy rozkazów.

Charakterystyka

projektów RISC

• Ograniczony i prosty zbiór rozkazów

, co zaprzeczało

dotychczasowej tendencji wzbogacania list

rozkazów dla upodobnienia listy do złożonych

wyrażeń języków wysokiego rzędu. Co miało na

celu:

– Ułatwienia zadania programistom tworzącym kompilatory
– Poprawienie efektywności wykonywania, ponieważ

złożone rozkazy mogły być realizowane w postaci

mikroprogramu

– Wspieranie nawet bardzo złożonych i wyrafinowanych

języków wysokiego rzędu.

• Duża liczba rejestrów roboczych lub zastosowanie

kompilatorów do optymalizacji wykorzystania

rejestrów.

• Dążenie do optymalizacji potoku rozkazów.

Porównanie wybranych

procesorów

Własność

Komputer CISC

Komputery RISC

Superskalarne

IBM VAX Intel

Motorola MIPS

IBM Intel

370/168 11/780 80486

88000 R4000

RS/6000 80960

Rok powstania

1973 1978 1989

1988 1991

1990 1989

Liczba rozkazów

208 303 235

51 94

184 62

Długość rozkazu

2÷6 2÷57 1÷11

4 4

4 4,8

w bajtach

Tryby adresowania

4 22 11

3 1

2 11

Liczba rejestrów

16 16 8

32 32

32 23 ÷256

roboczych

Pamięć sterująca

420 480 246

-- --

-- --

w K bitów

Pamięć podręczna

64 64 8

16 128

32 ÷ 64 0,5

w K bajtów

Porównania RISC i CISC

własności wykonywania

rozkazów

• Używane operacje

. Określają działania wykonywane

przez procesor i jego współpracę z pamięcią.

• Używane argumenty

. Rodzaje argumentów i

częstość ich używania determinuje organizację
pamięci służącej do ich przechowywania oraz tryby
adresowania.

• Szeregowanie rozkazów

. Określa organizację

sterowania oraz przetwarzania potokowego.

Operacje

•

Przeprowadzono szereg badań porównawczych celem
przeanalizowania zachowania się programów pisanych w
językach wysokiego rzędu.

•

Między innymi stwierdzono, że dominowały operacje
przypisania (instrukcja ASSIGN), co sugeruje ważność
przemieszczania danych.

•

Wystąpił też duży udział skoków warunkowych (instrukcje IF,
LOOP). Instrukcje te są realizowane w języku maszynowym za
pomocą rozkazów porównania i rozgałęzienia. Sugeruje to
ważność mechanizmu sterowania szeregowaniem rozkazów.

•

Stwierdzono więc, które instrukcje występują najczęściej i
wobec czego powinny być optymalnie realizowane. Jednakże
wyniki te nie ujawniają, które instrukcje zajmują najwięcej
czasu przy wykonywaniu typowego programu.

Ważona względna

częstotliwość operacji w

językach programowania

Operacja Występowanie Ważona wg Ważona wg
dynamiczne rozkazów masz. Odwołań do pamięci

Pascal C Pascal C Pascal C

ASSIGN

45 38 13 13 14 15

LOOP

5 3 42 32 33 26

CALL

15 12 31 33 44 45

IF

29 43 11 21 7 13

GOTO

-- 3 -- -- -- --

Inne

6 1 3 1 2 1

Argumenty

• Stosunkowo mało czasu poświęcono na badanie

występowania różnych rodzajów argumentów.

• Wspomniane na poprzedzającym slajdzie badania

obejmowały również dynamiczną częstość występowania

klas zmiennych (porównaj następny slajd).

• Zgodność wyników dla programów pisanych językach

Pascal i C – wskazują, że większość odwołań dotyczyła

prostych zmiennych skalarnych, a ponad 80% tych

skalarów to zmienne lokalne.

• Odniesienia do tablic i innych struktur danych wymaga

uprzedniego odwołania się do indeksów lub wskaźników,

które na ogół są lokalnymi skalarami.

• Można więc przyjąć, że ma miejsce przewaga odwołań do

skalarów, a te z kolei są w wysokim stopniu skalarami

lokalnymi.

Dynamiczny udział %

argumentów

Pascal C Średnio

Stałe całkowite

16 23 20

Zmienne skalarne

58 53 55

Tablice/struktury

26 24 25

Wywołania procedur

•

Wywołania procedur i powroty są ważną własnością
programów pisanych w językach wysokiego poziomu.

•

Udowodniono, że operacje wywołania procedur i powroty – to
najbardziej czasochłonne operacje w skompilowanych
programach napisanych w językach wysokiego poziomu.

•

W innych badaniach zostało stwierdzone, że 98% dynamicznie
wołanych procedur używa mniej niż 6 argumentów, zaś 92% z
nich używa mniej niż 6 lokalnych zmiennych skalarnych.
Potwierdziły to badania prowadzone na Berkeley RISC.

•

Z badań wynika, że znaczną część odwołań stanowią lokalne
zmienne skalarne. Odwołania te, dotyczą stosunkowo
niewielkiej liczby zmiennych.

Argumenty procedur i

lokalne zmienne skalarne

Udział wykonywanych

Kompilator

Małe programy

wywołań

interpreter

numeryczne

podprogramów z:

i składopis

> 3 argumentami

0÷7%

0 ÷5%

> 5 argumentami

0 ÷3%

0%

> 8 słowami argumentów

1 ÷ 20%

0 ÷ 6%

i skalarów lokalnych
> 12 słowami argumentów

1 ÷ 6%

0 ÷ 3%

i skalarów lokalnych

Pracochłonność

projektowania logiki i

topologii wybranych

procesorów

Procesor Tranzystory Projektowanie logiki Projektowanie topologii
(tysięcy) (osobomiesięcy) (osobomiesięcy)

RISC I

44 15 12

RISC II

41 18 12

M68000

68 100 70

Z8000

18 60 70

Intel iAPx-432

110 170 90

Wnioski

• Wiele zespołów w wyniku przeprowadzonych badań doszło do

wniosku, że dążenie do dostosowania listy rozkazów do
wyrażeń języków wysokiego poziomu, nie jest najbardziej
efektywną strategią projektowania.

• Natomiast najkorzystniejszą metodą wsparcia języka wysokiego

poziomu jest optymalizacja najbardziej czasochłonnych
składników typowych programów pisanych w tych językach.

• Uogólniając wyniki prac badawczych można stwierdzić, że

architekturę RISC można w całości scharakteryzować za
pomocą trzech elementów:

– Architektura RISC wymaga dużej liczby rejestrów.
– Architektura RISC daje możliwość efektywnego zorganizowania

złożonych potoków – natomiast nieefektywna jest w RISC prosty potok.

– Opłacalnym jest projektowanie uproszczonych (zredukowanych) list

rozkazów ze względu na projektowanie procesora jako jednego układu
scalonego VLSI.

Okna

rejestrów

Parametry

RoboczeCzasowe

Czasowe

Robocze

Parametry

Czasowe

Robocze

Parametry

Rejestry globalne

Wywołanie

/

powrót

Wywołanie

/

powrót

Poziom J - 1

Poziom
J

Poziom J + 1

Nakładające
się okna
rejestrów
lokalnych kolejnych
poziomów wywołań
procedur

Rejestry globalne np. o adresach 0÷7
są widoczne z każdego poziomu
wywołania procedur, natomiast
rejestry lokalne procedury (12 rejestrów),
są widoczne z poziomu procedury (np. z
adresami 8÷31). Rejestry czasowe
poziomu J – 1, stają się rejestrami
parametrów poziomu J.

Cykliczno-buforowa

organizacja nakładających

się okien

Powrót

Wywołanie

Wskaźnik bieżącego okna

Wskaźnik okna
zachowanego

A.

p

ar

am

et

ry

D.

c

za

so

we

A. robocze

A. c

zas

ow

e

B. p

ara

me

try

B

.

ro

b

o

cz

e

B.

cz

as

ow

e

C.

pa

ra

me

try

C. robocze

C. c

za

so

we

D.

pa

ram

etr

y

D

.

ro

b

o

cz

e

Tablica rejestrów a pamięć

podręczna

Adres

Porównanie

Wybór

Z

n

a

cz

n

ik

i

Dane

Dekoder

Nr okna

Rejestr

Rozkaz

Rejestry

Dane

Rozkaz

Pamięć

podręczna

Dane

(a) Tablica rejestrów

z mechanizmem

okna

(b) Pamięć podręczna

Podejście oparte

na kolorowaniu grafów

Rejestry fizyczne

R1

R2

R3

Rejestry logiczne

określone przez kompilator

A B C D E F

D

E

F

E

D

B

A

C

Graf składa się z sześciu rejestrów
logicznych, które należy odwzorować
na trzy rejestry fizyczne.

Jak widać z kolorowania grafu trzema
kolorami, rejestr R1 można użyć jako
rejestry logiczne A i D, rejestr R2 jako
rejestr logiczny B, rejestr R3 jako rejestry
logiczne C i E. Rejestr logiczny F należy
odwzorować jako słowo pamięci.

Rozmiary programów dla

różnych komputerów w

porównaniu do RISC I

Badania: D. Patterson M. Katevenis
J. Heath

liczba 11 programów C 12 programów C
5 programów C

RISC I

1,0 1,0

1,0

VAX-11/780

0,8 0,67

M68000

0,9

0,9

Z8002

0,9

1,12

PDP-11/70

0,9 0,71

Własności RISC

• Rozkaz o pojedynczej długości słowa (zwykle 4 bajty), oraz proste

rozkazy (brak rozkazów typu łączenia operacji pobierania z pamięci

albo zapisu do pamięci – z operacjami arytmetycznymi, np. dodaj

do pamięci) –

tzw. wskaźnik złożoności dekodowania

.

• Proste formaty rozkazów –

tzw. wskaźnik złożoności dekodowania

.

• Operacje rejestr – rejestr, przy czym adres rejestru dla liczb

całkowitych ma co najmniej 5 bitów (czyli nie mniej niż 32 rejestry

całkowitoliczbowych), zaś adres rejestru dla liczb zmienno-

przecinkowych ma co najmniej 4 bity (czyli nie mniej niż 16

rejestrów zmiennoprzecinkowych) –

umożliwia pisanie sprawnych

kompilatorów

.

• Jeden rozkaz na cykl –

co daje łatwość przetwarzania potokowego

.

• Co najwyżej jeden argument rozkazu adresowany jest do pamięci –

co daje łatwość przetwarzania potokowego

.

• Proste tryby adresowania i mała ich liczba, zwykle mniejsza niż 5 i

brak adresowania pośredniego –

co daje łatwość przetwarzania

potokowego

.

Przetwarzanie potokowe

w RISC

• Większość rozkazów jest typu rejestr – rejestr,

a cykl rozkazów ma następujące dwie fazy:

– I

. Pobranie rozkazu.

– E

. Wykonanie rozkazu. Wykonywana jest operacja

ALU, przy czym dane wejściowe pobierane są z
rejestrów i do rejestrów są kierowane wyniki.

• W przypadku operacji ładowania i zapisu

wymagane są trzy fazy:

– I

. Pobranie rozkazu.

– E

. Wykonanie rozkazu. Obliczanie adresu w

pamięci.

– D

. Pamięć. Operacja rejestr – pamięć albo pamięć –

rejestr.

Wykonywanie

sekwencyjne

Ładuj
A := M

Ładuj
B := M

Dodaj C :=
A + B

Zapisz M :
= C

Rozgałęziaj X

Czas
(13 cykli)

I E D

I

E

E

E

E

I

D

I

I

D

Wykonywanie potokowe 2 -

etapy

Ładuj
A := M

Ładuj
B := M

Dodaj C :=
A + B

Zapisz M :
= C

Rozgałęziaj X

NOOP

Czas
(12 cykli)

I E D

I

E

E

E

E

I

D

I

I

D

i E

Wykonywanie potokowe 3 -

etapy

Ładuj
A := M

Ładuj
B := M

NOOP

Dodaj C :=
A + B

Zapisz M :
= C

Rozgałęziaj X

NOOP

Czas
(8 cykli)

I E D

I E D

E

I

D

I E

I E

I E

I E

Wykonywanie potokowe 4 -

etapy

Ładuj
A := M

Ładuj
B := M

NOOP

Dodaj C :=
A + B

Zapisz M :
= C

Rozgałęziaj X

NOOP

NOOP

Czas
(10 cykli)

I E1

D

I

E2

E2

E1

E2

I

D

I

I

D

E2

E1

E1

E2

E2

E1

E2

E1

E2

E1

I

I

I

E1

Optymalizacja

przetwarzania potokowego

I

• Dzięki prostocie i regularności rozkazów RISC schematy

przetwarzania potokowego mogą być efektywnie stosowane.

• Istnieje pewne zróżnicowanie czasu wykonywania rozkazów i jest

możliwe przystosowanie potoku do tej sytuacji. Zależność
danych oraz rozgałęzienia redukują ogólną szybkość
wykonywania programu.

• W celu skompensowania tych zjawisk opracowano metody

reorganizacji kodu. Przy

rozgałęzieniu opóźnionym

jako metodzie

zwiększania efektywności potoku używa się rozgałęzienia, które
nie daje wyniku, aż do zakończenia następnego rozkazu.

• Np. zmieniając miejscami rozkazy 101 i 102. Przed rozkazem

ADD pobierany jest rozkaz JUMP. Zauważmy jednak, że rozkaz
ADD jest pobierany zanim rozkaz JUMP ma szanse zmienić stan
licznika. Co zapewnia zachowanie oryginalnej semantyki
programu.

Optymalizacja

przetwarzania

potokowego II

•

Podobne podejście można zastosować, zwaną jako

ładowanie opóźnione

, może być zastosowana odnośnie

rozkazu LOAD.

•

W przypadku rozkazu LOAD rejestr docelowy operacji jest

blokowany przez procesor. Następnie procesor kontynuuje

wykonywania strumienia rozkazów aż do osiągnięcia

rozkazu wymagającego tego rejestru, poczym pozostaje

bezczynny aż do zakończenia wykonania rozkazu LOAD.

•

Jeśli kompilator może tak zmienić kolejność rozkazów,

żeby w toku ładowania w potoku mogła być wykonywana

użyteczna praca, to efektywność wzrośnie.

•

Projektowanie potoku rozkazów nie może być prowadzone

w oderwaniu od innych zabiegów optymalizacyjnych

stosowanych w systemie. Np. szeregowanie rozkazów w

potoku oraz dynamiczne przydzielanie rejestrów muszą

być rozpatrywane łącznie.

Rozgałęzienie: normalne,

opóźnione i

zoptymalizowane

Adres

Rozgałęzienie normalne Rozgałęzienie opóźnione Rozgałęzienie zoptymalizowane

----------------------------------------------------------------------------------------------------------------------

100

LOAD X, A LOAD X, A LOAD X, A

101

ADD 1, A ADD 1, A

JUMP 105

102

JUMP

105

JUMP

106

ADD 1, A

103

ADD A, B

NOOP

ADD A, B

104

SUB C, B ADD A, B SUB C, B

105

STORE A, Z SUB C, B STORE A, Z

106

STORE A, Z

Zastosowanie

opóźnionego rozgałęzienia

I E

I E

I E

I E

I E D

D

I E

I E

I E

D

E

I

D

100 LOAD X, A

101 ADD I, A

102 JUMP 106

103 NOOP

106 STORE A, Z

100 LOAD X, A

101 JUMP 105

102 ADD I, A

105 STORE A, Z

(a) Wstawiony rozkaz pusty (b) rozkazy odwrócone

Potok rozkazów procesora

MIPS

• Dzięki uproszczonej architekturze (lista rozkazów) procesor MIPS

może osiągać bardzo efektywne przetwarzanie potokowe.

• Pierwsze, doświadczalne systemy RISC i pierwsza generacja

komercyj-nych procesorów RISC osiągały szybkość wykonywania

sięgającą jednego rozkazu w jednym cyklu zegarowym.

• Aby zwiększyć tę wydajność, opracowano dwie klasy

procesorów, umożli-wiające wykonywanie wielu rozkazów w

cyklu zegara:

– Super-skalarną

, w której jest powielany każdy etap potoku, co umożliwia

przetwarzanie równoczesne w potoku dwu lub więcej rozkazów.

– Super-potokową

, w której stosuje się większą liczbę bardziej

rozdrobnionych etapów potoku, dzięki czemu w potoku może

równocześnie znajdować się więcej rozkazów.

• W systemie super-potokowym te same układy elektroniczne są

używane kilkakrotnie w czasie jednego cyklu dzięki wstawieniu

rejestrów rozszczepiających każdy etap.

• Procesor MIPS

jest procesorem

super-potokowym

.

Schemat potoku

procesora MIPS

IFF

IS

IFF

IS

EX

DF

DS

TC

WB

WB

TC

RF

EX

DF

DS

RF



1

2



1



2



1



2



1



2

Cykl zegara

IFF

– pobieranie rozkazu pierwsza połowa

IS

- pobieranie rozkazu druga połowa

RF

- pobranie argumentu z rejestru

EX

– wykonywanie operacji

DF

– pamięć podręczna danych pierwsza

połowa

DS

– pamięć podręczna danych druga

połowa

TC

– sprawdzenie znacznika

WB

– zapisywanie w tablicy rejestrów

Etapy potoku procesora

MIPS

• IFF

-

Pobieranie rozkazu pierwsza połowa

. Adres wirtualny jest

przekazywany do pamięci podręcznej rozkazów oraz do bufora

translacji adresów TLB (translation look-aside buffer).

• IS

-

Pobieranie rozkazu druga połowa

. Pamięć podręczna rozkazu

przekazuje rozkaz, a TLB generuje adres fizyczny.

• RF

-

Równolegle trzy działania na tablicy rejestrów

(dekodowanie

rozkazu i sprawdzenie warunków współzależności; badanie wskaźnika

pamięci podręcznej rozkazów; pobranie argumentów z tablicy

rejestrów).

• EX

-

Wykonywanie rozkazu

(trzy przypadki: operacja rejestr-rejestr;

obliczanie adresu wirtualnego dla operacji pobrania albo zapisu; dla

rozkazów rozgałęzionych obliczanie wirtualnego adresu docelowego i

sprawdzenie warunków rozgałęzienia).

• DF

–

Pierwszy etap dostępu do pamięci podręcznej danych

. Adres

wirtualny jest przekazany do pamięci podręcznej danych oraz do TLB.

• DS

– Drugi etap dostępu do pamięci danych. Pamięć podręczna danych

przekazuje dane, a TLB generuje adres fizyczny.

• TC

–

Sprawdzanie wskaźnika

. W przypadku operacji ładowania i zapisu

sprawdzany jest wskaźnik pamięci podręczne.

• WB

–

Zapis

. Wynik operacji jest zapisywany w tablicy rejestrów.

Porównanie architektur RISC i

CISC

• Porównanie architektur RISC i CISC można podzielić na dwie

kategorie:

– Ilościowa

– dążenie do porównania rozmiarów programów i szybkości

realizacji.

– Jakościowa

– dotyczy porównania wspierania kompilatorów języków

wysokiego rzędu oraz wpływ na możliwości projektowania obwodów VLSI.

• Większość prac nad oceną ilościową została wykonana przez

zespoły pracujące nad systemami RISC. Istnieje kilka

problemów dotyczących przeprowadzenia porównań:

– Nie ma pary komputerów RISC i CISC, które są w pełni porównywalne.
– Nie istnieje rozstrzygający zbiór testów, a wydajność zależy od

oprogramowania.

– Trudno jest oddzielić wpływ sprzętu od sprawności kompilatorów.
– Większość prac porównawczych dotyczyła „komputerów zabawek”, a nie

seryjnie produkowanych.

• Ocena jakościowa dotyczy sukcesu rynkowego komputerów

RISC, który jak dotąd nie jest jednoznaczny.

• Rozwiązania RISC i CISC wzajemnie się przenikają, różnice są

już dziś małe i stają się coraz mniejsze!

Procesory super-skalarne

• Termin super-skalarny, użyty po raz pierwszy w roku 1987,

odnosi się do procesora, który został zaprojektowany pod

kątem zwiększenia wydajności działając jednak na skalarnych

danych a nie na wektorach danych.

• Rozwiązanie takie stwarza wiele złożonych problemów

projektowych związanych z potokowym przetwarzaniem

rozkazów.

• Projekty super-skalarne pojawiły się niewiele później niż

procesory RISC.

• Architektura RISC sprzyja zastosowaniu rozwiązania super-

skalarnego, ale rozwiązania super-skalarne mogą być

stosowane również w CISC.

• Podczas gdy okres dojrzewania – między początkiem badań

nad RISC, a ukazaniem się komercyjnych komputerów RISC

wyniósł blisko osiem lat, to pierwsze komputery super-skalarne

ukazały się w niecałe dwa lata od wymyślenia terminu „super-

skalarny”.

Porównanie

rozwiązań

I

D

W

E

Gdzie:
I – pobieranie rozkazu
D – dekodowanie
E – wykonanie
W – zapis opóźniony

System super-
skalarny

System super-potokowy

System potokowy

0 1 2 3 4 5 6 7 8

Czas w cyklach podstawowych

Ograniczenia

równoległego

wykonywania rozkazów

•

Prawdziwa zależność danych

– ma miejsce jeśli kolejny

rozkaz ma wykorzystać wyniki swego poprzednika, co
powoduje oczekiwanie.

•

Zależność proceduralna

– rozkazy następujące po

rozgałęzieniu (dokonanym lub nie dokonanym) wykazują
zależność proceduralną od rozgałęzienia i nie mogą być
wykonywane przed zakończeniem rozgałęzienia.

•

Konflikt dotyczący zasobów

– polega na jednoczesnym

rywalizowaniu dwóch lub wielu rozkazów o te same
zasoby (pamięć główna, pamięć podręczna, magistrale,
porty tablic rejestrów oraz jednostek funkcjonalnych).

•

Zależność wyjściowa

, nazywana także zależnością odczyt

- zapis.

•

Anty-zależność

, nazywana także zależnością zapis - zapis.

Dwa popularne procesory

super-skalarne

• PowerPC
• Pentium