# Ćwiczenia 6, grupa cz. 16-18, 4 kwietnia 2024

###### tags: `SYK24` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak | X | X | X | X | X | X | | | | | |
Bartosz Borecki | X | X | X | X | X | X | | X | X | X | |
Karol Burczyk | X | X | X | | | | | | | | |
Yelyzaveta Ilman | X | X | ==X== |X | X | X | X | X | | | |
Antoni Kamiński | | | | | | | | | | | |
Jan Kamyk | X | X | X | X | X | | | X | | | |
Bartosz Kruszewski | X | X | X | X | X | X | X | X | X | X | X |
Hanna Laszkiewicz | X | ==X== | X | X| X | X | X | X | | | |
Kaja Matuszewska | | | | | | | | | | | |
Dominik Muc | | | | | | | | | | | |
Krzysztof Ostrowski | ==X== | X | X | X | X | X | X | X | X | X | |
Franciszek Przeliorz | | | | | | | | | | | |
Yaryna Rachkevych | X | X | X | X |==X==| X | X | X | X | X | |
Mikołaj Kalitka | | | | | | | | | | | |
Piotr Thamm | X | X | X | X | X | X | X | | | | |
Taras Tsehenko | | | | | | | | | | | |
Wiktor Małek| X | X | X | X | X | X | X | X | X | X | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Krzysztof Ostrowski
:::


>1. Licznik rozkazów przekazuje aktualną instrukcję
>
>2. Do **A1** trafia miejsce $y$ w pamięci
> Stała $imm$ jest rozszerzana do $32$ bitów
>
>3. Wartość $y$ trafia do **ALU**
> Wartość stałej $imm$ trafia do **ALU**
>
>4. **ALU** przekazuje wynik
>
>5. Wynik zostaje zapisany do **A3**
> RegWrite $= 1$
>
>6. Do licznika dodajemy 4 bajty -> następna instrukcja

## Zadanie 2
:::success
Autor: Hanna Laszkiewicz


:::

## Zadanie 3
:::success
Autor: Yelyzaveta Ilman


$x = y$ **binop** $z$
to jest instrukcja typu $r$ (instrukcja arytmetyczna logiczna)

Z licznika pobieramy tą instrukcję i odczytujemy w Instruction Memory (**faza Fetch**)
Mamy **3** multipleksery jednobitowe.
**Dekodujemy** instrukcję.
Kodowanie jest skonstruowane w taki sposób, żeby na bitach:
* $25:21$ - numer **y** - **A1**
* $20:16$ - numer **z** - **A2**

A dla wyznaczenia, na jakich bitach będzie **x** jest potrzebny **I-szy** multiplekser.

#### **I-szy** multiplekser:
* $20:16$ - zakodowany numer rejestru który chcemy zapisać
* $15:11$ - instrukcja typu r
* wejście sterujące **RegDst** jest ustawione na $1$, bo to jest instrukcja typu **r**
* po przejściu przez I-szy multiplekser, x zapisujemu na **A3**

#### **II-gi** multiplekser:
* ma dwie grupy wejść, w zależności od tego, podamy 0 czy 1, to przekieruje na swoje wyjście odpowiednią magistralę.
* jeżeli to jest instrukcja typu r, to podajemy 0 i na wyjściu będzie **RD2**
* jeżeli instrukcja typu lw - 1 i **Sign Extend** (rozszerza do 32 bitów)

Teraz musimy do **WD3** przekierować nie wynik **Data Memory**, jak ostatnio, tylko wynik operacji **$x = y$ binop $z$**
Dlatego jest nam potrzebny **III-ci** multiplekser
#### **III-ci** multiplekser:
* bierzemy kopię **ALUResult** i za pomocą multipleksera decydujemy, co zostanie przekierowane do WD3:
1. instrukcja typu r -> **ALUResult**
2. instrukcja typu lw -> **ReadData**
3. instrukcja typi sw -> nie jest nam istotne

:::

## Zadanie 4
:::success
Autor: Marcin Banak


#### Znaczenie operacji $ if \; x \; relop \; y \; goto \; L $

Operacja polega na obliczeniu $x$ relop $y$, a w przypadku wystąpienia wyniku > 0, na wykonaniu skoku licznika instrukcji do adresu $PC + L$.

_$PC$ to aktaulny stan licznika instrukcji._

#### Obliczanie adresu skoku

$BTA = (PC + 4) + (L << 2)$

Adresy instrukcji są ułożone w pamięci co 4 bajty. Więc dwa ostatnie bity adresu są zawsze równe 00. Przesunięcie $L$ o << 4 pozwala na uzyskanie czterokrotnie zwiększonego zakresu skoku, bez utraty dokładności.

$L$ w takim przypadku oznacza przesunięcie o indeks intrukcji, ponieważ zawsze przesuwamy o $L * 4$ bajty.

$L$ jest zakodowane w systemie U2, więc możliwe są skoki "do tyłu".

$(PC + 4)$ to aktualny adres następnej do wykonania instrukcji.

_Prezentowanie następnego adresu instrukcji zamiast aktualnego jest podytkowane konwencją, w celu ułatwienia odczytywania schematu działania procesora_

#### Ograniczenie

W związku z tym, że $L$ musi się zmieścić w instrukcji obok $x$ i $y$, które zajmują po 4 bity to zakres skoku jest ograniczony.

#### Dodatkowe elementy

- **<<2**: przesunięcie $L$ o dwa bity w lewo (mnożenie przez 4).
- **PCBranch**: obliczenie BTA.
- **Branch**: pozwala na kompatybilność instrukcji wykonujących skok, z tymi które go nie wykonują.
- **PC'**: pozwala ustalić, czy wykonujemy skok, czy standardowe przesunięcie adresu o 4 bajty.

Wartości sterujące elementami są odpowiednio ustawiane po odczytaniu instrukcji.

#### Wykonanie operacji

1. Przekazanie numeru instrukcji do rejstru rozkazów.
2. Oczytanie instrukcji przez rejestr rozkazów i przesłanie inforacji o niej do pliku rejestrów, oraz informacji o typie operacji do ALU.
3. Odczytanie wartości zmiennych $x$ i $y$ przez rejestr plików i przesłanie ich do ALU.
4. Rozszerzenie reprezentacji L do 32-bitów.
5. Przesunięcie L << 2.
6. Dodanie przesuniętego L do PC w PCBranch.
7. Ustalenie na podstawie wyniku z ALU, czy należy wykonać skok.
8. Wykonanie skoku, czyli przesunięcie adresu o wynik z PCBranch.

:::
## Zadanie 5
:::success
Autor: Yaryna Rachkevych
a)
Wystarczy ustawić wartość dla multipleksera **AluSrc** na 1. Reszta identycznie jak dla x = y binop y z.

b)
W przypadku, w którym skok ma się odbyć do intrukcji o indeksie L, wystarczy przemnożyć wartość stałej L przez 4, czyli wykonacać przesunięcie bitowe w lewo o 2. (Mnożymy przez 4 ponieważ instrukcje zajmują równo 4 bajty i są zapisane po kolei obok siebie). Następnie ustawiamy licznik rozkazów na obliczoną wartość.

:::

## Zadanie 6
:::success
Autor: Piotr Thamm


:::

## Zadanie 7
:::success
Autor: Wiktor Małek

$I_1 := x=(y+ imm)$
$I_2 := (x +imm) = y$
$I_3 := \textrm{if x relop y goto L}$
$I_4 := x =y \space binop \space z$

$T(I_1)= 1075ps$
$T(I_2)= 900ps$
$T(I_3)= 700ps$
$T(I_4)= 850ps$

Najdłuższy cykl w niezmodyfikowanym procesorze: $T(I_1) = 1075ps$
Aby obliczyć przyspieszenie, najpierw należy policzyć długość cyklu w naszym zmodyfikowanym procesorze:

Nowy czas $=0.25 * T_1 + 0.11 * T_2 + 0.12 * T_3 + 0.52 * T_4 = 268.75 + 99 + 84 + 442 = 893.75ps$

Czyli aby uzyskać rzeczywisty zysk należy wziąć liczbe instrukcji w oryginalnym programi i pomnożyć przez 1075(usatlona długosć cyklu), następnie podliczyć czas wykoniania tych instrukcji dla zmiennej długości cyklu i porównać wartości.

:::

## Zadanie 8
:::success
Autor: Bartosz Borecki

:::

## Zadanie 9
:::success
Autor: Bartosz Kruszewski
:::

*rysunek został zmodyfikowany ręcznie w programie graficznym, nie jest to rysunek ze slajdów*

#### Intuicja

Jeżeli chcielibyśmy wykonać instrukcję $swap \; x \; y$ w jednym cyklu procesora to musielibyśmy wykonać następujące działania:

- odczytanie wartości z rejestru $x$
- odczytanie wartości z rejestru $y$
- zapisanie wartości z rejestru $x$ do $y$
- zapisanie wartości z rejestru $y$ do $x$

#### Problemy

W dotychczasowo omawianym modelu procesora **plik rejestrów** umożliwia odczytanie dwóch wartości w jednym cyklu, natomiast możemy wykonać zapis tylko do jednego rejestru.

Stąd modyfikacja jaką należałoby wykonać obejmowałaby **plik rejestrów** i dodanie wejść A4, WD4, WE4.

#### Modyfikacje procesora

- dodanie wejścia **A4**
- dodanie wejście **WD4** oraz **WE4**
- połączenie **A1** bezpośrednio z **A4** (**A4** jest używane tylko do ***SWAPA***)
- połączenie **RD1** bezpośrednio z **WD4** (**WD4** jest używane tylko do ***SWAPA***)
- dodanie multipleksera z wejścia z **RD2** oraz z wyjściem z wynikiem obliczeń dla **RD3**, który będzie wybierał wejście do **RD3** (dzięki temu zachowujemy kompatybilność z pozostałymi instrukcjami)

#### Ustawienia Control Unit

- ustawiamy **RegDst** na $0$, wtedy do **A3** trafi wartość z **A2**
- ustawiamy **WD3Src** na $1$, wetdy do **WD3** trafi wartość z **RD2**
- ustawiamy **WE4** na $1$, wtedy wartość z **WD4** zostanie zapisana do rejestru o adresie **A4**

#### Koszt

- $3$ dodatkowe wejśćia w **pliku rejestrów**
- $2$ dodatkowe wyjścia z **ControlUnit**
- $1$ dodatkowy multiplekser
- trochę dodatkowych ścieżek (mogą powodować problemy z rozmieszczeniem elementów i ostatecznie zwiększyć rozmiar procesora)

## Zadanie 10
:::success
Autor: Krzysztof Ostrowski
:::

> 1. Licznik rozkazów przekazuje aktualną instrukcję
> 2. Do **A1** trafia miejsce $y$ w pamięci
> Do **A2** trafia miejsce $x$ w pamięci
> $imm$ jest rozszerzane do 32 bitów
> 3. **ALU** sumuje wartość $y$ i $imm$
> 4. Do referencji $x$ zostaje zapisana wartość z **ALU**
> (MemWrite $= 1$)
> 5. Do licznika dodajemy 4 bajty -> następna instrukcja

## Zadanie 11
:::success
Autor: Bartosz Kruszewski
:::
#### Zamiana instrukcji x = \*(y+ imm)

- $t = y + imm$ $(825ps)$

- $x = *t$

PC -> IM -> RF -> DM -> MX -> RF

T_c = 50 + 250 + 150 + 250 + 25 + 150 = 875

#### Zamiana instrukcji \*(x+ imm) = y

- $t = x + imm$ $(825ps)$

- $*t = y$

PC -> IM -> RF -> DM

T_c = 50 + 250 + 150 + 250 = 700

#### Nowa długość cyklu

Dokonując powyższej zamiany instrukcji sprawiamy, że maksymalny cykl będzie wynosił $875$ (operacja $x = *t$).

#### Nowe czasy działania

Teraz x = \*(y+ imm) oraz \*(x+ imm) = y wymagają użycia dwóch cyklów zamiast jednego.

#### Obliczenia

Czas działania starego procesora: $N * 1075$
Czas działania nowego procesora:

N * (2 * 0.25 + 2 * 0.11 + 0.12 + 0.52) * 875 =
= N * 1.36 * 875 = N * 1190

Więc stary procesor działa szybciej dla programu o podanej charakterystyce.

Natomiast mając program o innej charaktyce, gdzie operacje korzystające z pamięci występują rzadziej to jego czas działania wynosi:

N * (2 * 0.05 + 2 * 0.05 + 0.2 + 0.7) * 875 =
= N * 1.1 * 875 = N * 962.5

Wtedy nowy procesor działa szybciej.