# Ćwiczenia 4, grupa cz. 14-16, 31. marca 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | |
Mateusz Burdyna | | | | | | | | |
Dariusz Ciesielski | | | | | X | X | X | |
Dawid Dudek |==X== | X | X | X | X | X | X | |
Mikołaj Dworszczak | | | | | | | | |
Przemysław Grochal | | | | | | | | |
Adam Jarząbek | | | | | | | | |
Anna Karykowska | | | | X | X | X | X | |
Oleś Kulczewicz | | | | | | | | |
Pola Marciniak | | | | | | | | |
Mikołaj Mroziuk | | | | | x | x | x | |
Marcelina Oset | x | | | | x | x |==x==| |
Natalia Piasta | | | | | X | X | X | |
Krzysztof Piekarczyk | | | | | | | | |
Marcin Płaza | | | | | X | X | X | |
Paweł Richert | | | | | X | X | ==X== | |
Rafał Starypan | X | X | X | | X | X | X | |
Dawid Strojek | | | | | X | | | |
Mateusz Suszek | | | | | X | X | X | |
Wojciech Śniady | | | | | X | X | X | |
Volha Tsekalo | | | | | ==X== | X | X | |
Yana Vashkevich | | | | | X | X | X | |
Konrad Woźniak | | | | | ==X== | X | X | |
Natalia Czerep | | | | | | | | |
Joanna Stachowicz | | | | | X | X | X | |
:::

Tu można do-deklarować zad. 8 z listy 3:

Dawid Dudek
Rafał Starypan

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

## Zadanie 1

:::success
Autor: Dawid Dudek
:::


równania Z8:

rozwiazanie:

## Zadanie 2

:::success
Autor: Rafał Starypan
:::
### Bazujemy na klasycznych analizach zmiennych dostępnych. Wystarczająca zmianą jest nowe zdefiniowanie $kill$ i $gen$:

Elementami zbiorów analizy są pary [VAR, EXPR], gdzie EXPR to wyrażenie dostępne w zmiennej VAR.

$kill_{AE}([ x:= a]^{l}) = \{<x, a'> | a' \in AExp_{*}\} \cup \{<y, a> | x \in a\}$ gdzie y jest zmienna w programie
$kill_{AE}([skip]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia
$kill_{AE}([b]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia

$gen_{AE}([ x:= a]^{l}) = \{<x, a>\} \quad jeżeli \quad x \notin a \quad wpp. \{\}$
$gen_{AE}([skip]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia
$gen_{AE}([b]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia

Jest to analiza typu "MUST". Wynika to z faktu iż działamy analogicznie do klasycznej analizy 'Available Variables' (w szczególności widzimy że w definicji mamy zapis 'na WSZYSTKICH ścieżkach')

Jest to analiza typu "FORWARD", ponieważ analizujemy jakie wyrażenia zostały już WCZEŚNIEJ obliczone i przypisane do zmiennej (w szczególności bez późniejszych zmian itp.)

## Zadanie 3

:::success
Autor: Rafał Starypan
:::
Skoro analiza jest typu MUST to algorytm stałopunktowy na starcie "wypełniamy" zbiorami pełnymi.

Korzystamy z definicji KILL/GEN takich jak w z2. Przypomnijmy:

$kill_{AE}([ x:= a]^{l}) = \{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\}$
$kill_{AE}([skip]^{l}) = \emptyset$
$kill_{AE}([b]^{l}) = \emptyset$

$gen_{AE}([ x:= a]^{l}) = \{<x, a>\} \quad jeżeli \quad x \notin a \quad wpp. \emptyset$
$gen_{AE}([skip]^{l}) = \emptyset$
$gen_{AE}([b]^{l}) = \emptyset$

Bazujemy na równaniach:
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

$AE_{exit}(1) = AE_{entry}(1) \setminus (\{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\})$
$AE_{exit}(2) = AE_{entry}(2) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$
$AE_{exit}(3) = AE_{entry}(3) \setminus (\{<i, a'> | a' \in AExp_{*}\} \cup \{<i, a> | i \in a\})$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \setminus (\{<t, a'> | a' \in AExp_{*}\} \cup \{<l, a> | t \in a\}) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus (\{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\})$
$AE_{exit}(7) = AE_{entry}(7) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$
$AE_{exit}(8) = AE_{entry}(8) \setminus (\{<i, a'> | a' \in AExp_{*}\} \cup \{<l, a> | i \in a\})$
$AE_{exit}(9) = AE_{entry}(9) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$

Przypisujemy jedynie do zmiennej t wartość x+y
oraz do zmiennej i wartość i+1

Które można (dla naszego zadania przekształcić do postaci):
$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3) \setminus \{<i, i+1>\}$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \setminus \{<t, x+y>\} \cup \{<t, x+y>\} = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{<i, i+1>\} = AE_{entry}(8) \setminus \{<i, i+1>\}$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

Skracając:
$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3) \setminus \{<i, i+1>\}$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{<i, i+1>\}$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

Nigdy nie dodajemy <i, i+1> wieć można skrócić powyższe:

$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8)$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

### Etap 0
$AE_{entry}(1) = ... = AE_{entry}(9) = \{<t, x+y>\}$
$AE_{exit}(1) = ... = AE_{exit}(9) = \{<t, x+y>\}$

### Etap 1
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \{<t, x+y>\}$
$AE_{entry}(3) = \{<t, x+y>\}$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \{<t, x+y>\}$
$AE_{entry}(8) = \{<t, x+y>\}$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{<t, x+y>\}$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \{<t, x+y>\}$
$AE_{exit}(9) = \emptyset$

### Etap 2
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{<t, x+y>\}$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \{<t, x+y>\}$
$AE_{exit}(9) = \emptyset$

### Etap 3
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 4
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 5
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 6 (bez zmian)
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

## Zadanie 4

:::success
Autor: Anna Karykowska
:::



Zmienna jest żywa na wyjściu z bloku jeśli istnieje ścieżka z tego bloku do użycia tej zmiennej, które nie redefiniuje jej.

*Powiemy, że zmienna jest zemdlona jeśli jest martwa lub jeśli jest używana wyłącznie do obliczenia wartości zmiennych zemdlonych.*

*W przeciwnym przypadku zmienną nazwiemy silnie żywą.*

Weźmy równania z oryginalnej Live Variables Analysis:


Potrzebujemy zmienić funkcję generującą dla przypadku z przypisaniem wartości do zmiennej, ponieważ chcemy wykluczyć zmienne zemdlone.


Analiza jest backward i may.

## Zadanie 5

:::success
Autor: Konrad Woźniak
:::





## Zadanie 6

:::success
Autor: Mateusz Suszek
:::

a)

t1 := a*a  /a^2
t2 := b*b  /b^2
x  := t1*a /a^3
t1 := t1*4 /4*a^2
t1 := t1*b /4*a^2*b
x  := x+t1 /a^3+4*a^2
t2 := t2*4 /4*b^2
t2 := t2*a /4*a*b^2
x  := x+t2 /a^3+4*a^2*b+4*a*b^2
t2 := t2/a /4*b^2
t2 := t2/4 /b^2
t2 := t2*b /b^3
x  := x+t2 /a^3+4*a^2*b+4*a*b^2+b^3

b)

mem[0] := a*a
mem[8] := a*b
mem[16] := b*b
mem[24] := 4*a
mem[32] := 4*b
x  := mem[0] * a     /a^3
t1 := mem[24]*mem[8] /4*a^2*b
x  := x + t1         /a^3+4*a^2*b
t1 := mem[32]*mem[8] /4*a*b^2
x  := x+t1           /a^3+4*a^2*b+4*a*b^2
t1 := mem[16]*b      /b^3
x  := x + t1         
/a^3+4*a^2*b+4*a*b^2+b^3

## Zadanie 7

:::success
Autor: Paweł Richert
i := 0
F: if i >= n goto G
a := 0
D: if a >= n goto E
p = a*4
if arr[p] <= arr[p+1] goto H
t4 := arr[p]
arr[p] := arr[p+1]
arr[p+1] := t4
H:a := a + 1
goto D
E:i := i + 1
goto F
G: ...

:::

## Zadanie 8

:::danger
Autor: do-deklarować
:::

## Zadanie 8
:::success
Autor: Jan Dalecki
:::


### 1. Układ sekwencyjny z jednym CSA

Posiadamy jeden moduł carry-save adder, który w pierwszym cyklu przeprowadzi obliczenia na b0A, b1A, b2A. Wynik takiego pośredniego obliczenia będziemy zapisywać w dwóch rejestrach Reg0 i Reg1, które na początku przechowują wartości b0A, b1A. Do 3 wejścia CSA podajemy w każdym cyklu kolejne wartości b2A, b3A i b4A.

Układ ten symuluje układ kombinacyjny z 3 sumatorami CSA. Każdy cykl to przejście do kolejnego poziomu. Po 3 cyklu na wyjściu RCA otrzymamy wynik mnożenia.

Reg2:0 przechowuje wyniki p0, p1, p2 które są uzyskiwane na każdym poziomie w układzie kombinacyjnym.

### 2. Układ sekwencyjny z 3 CSA

W tym układzie pamiętamy każde obliczenia wykonane przez sumatory CSA. Dzięki temu możemy skrócić czas na obliczenie dużej liczby kolejnych par liczb. Bez pamięci czas zegara byłby ograniczony przez czas obliczenia całego układu. Wprowadzając rejestry możemy zwiększyć częstotliwość zegara, który ograniczamy jedynie czasem RCA.