# Ćwiczenia 2, grupa cz. 10-12, 7 marca 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | | | | X | | X | | |
Michał Chawar | X | X | X | | X | | X | | |
Julia Cygan | X | | | | X | | X | | |
Maciej Dengusiak | ==X== | |X | | X | | X | | X |
Patryk Flama | X | | X | | ==X== | | X | | X |
Szymon Fluder | X | | X | X | ==X== | X | X | | |
Aleksandra Jędrzejak | | | | | | | | | |
Mikołaj Karapka | X | | X | | X | | ==X== | | X |
Viktoriia Kashpruk | X | | X |X | X | | X | | ==X== |
Wiktor Małek | X | | ==X== | X | X | X | X | | X |
Błażej Molik | X | | X | | X | | X | | X |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | X | | X | | | | | | |
Lucjan Pucelak | X | | X | | X | | X | | X |
Aleksandra Sęk | X | | | | X | | | | |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | | | | | | | | | |
Katarzyna Trzos | X | | X | | X | | X | | X |
Piotr Warząchowski | X | | X | | X | | X | | X |
Olga Zaborska | X | | X | | X | | | | X |
:::

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

## Zadanie 1
:::success
Autor: Maciej Dengusiak

### Schemat sumatora prefiksowego:

### Działanie sumatora prefiksowego:
> Sumator prefiksowy pozwala nam przyspieszyć operację sumowania n-bitowych liczb

Zamiast liniowo przechodzić po kolejnych bitach i obliczać kolejne przeniesienia $c_{out}$
pomysłem jest podzielić bity na bloki.
Następnie budując tak drzewo binarne możemy każdy blok obliczać równolegle i dalej podawać wyniki.

Korzystamy zasadniczo z dwóch operacji:
- Propagacji: Obliczenie $c_{out}$ w zależności od $c_{in}$ oraz $a_{i}$ i $b_{i}$

- Generacji: Obliczenie $c_{out}$ niezależnie od $c_{in}$

Propagację i generowanie dla bloku bitów możemy uogólnić przy użyciu wzoru:
Przeniesienie bloku kończące się na pozycji i-tej zostało:
Wygenerowane w tym bloku ($G_{i:j}$) lub (+) spropagowane z poprzedniego bloku ($P_{i:j}C_{j-1}$)

### Obliczenia:

- Bity propagowania: $P_{i:j}$ = $P_{i:k}$ * $P_{k-1:j}$
- Bity generacji: $G_{i:j}$ = $G_{i:k}$ + $P_{i:k}$ * $G_{k-1:j}$

Dla każdej kolejnej warstwy obliczenia wykonujemy równolegle. W czasie stałym $O(1)$.

### Czas działania:

Dzięki zwrównolegleniu obliczeń w warstwach mamy czas obliczenia wartości 2 bramek dla każdej z warstw równolegle oraz po bramce na początku i 2 na koncu co daje łącznie czas:
$$3n + 2log_{2}n$$

### Rozmiar układu:

Z powyższego rysunku wynika, że mamy:
- Dla n elementów obliczających bity jednopozycyjne po 2 bramki = $2n$
- Dla ${log_{2}n}$ poziomów sumatora po $\frac{n}{2}$ elementów każdy po 3 bramki = $3*\frac{n}{2}*log_{2}n$
- Dla n bitów wychodzących po 2 bramki = $2n$

Łącznie mamy: $4n+\frac{3}{2}nlog_{2}n$

:::

## Zadanie 2
:::success
Autor: Michał Chawar
:::


Ten sumator działa na tej samej zasadzie co poprzedni, jednak inaczej organizuje grupy bitów, na podstawie których na danym poziomie oblicza generację i propagację.

Na drugim poziomie grupujemy nie tylko co dwa bity na $\frac{n}{2}$ grup, lecz każdy bit grupuje się z jego przodkiem, tworząc $n-1$ grup.

Na trzecim poziomie do każdą z tych grup (rozpoczynającą się - patrząc od lewej - od pozycji $i$, a kończącą na $i-1$) rozszerza się o grupę poprzednią (tj. najbliższą z prawej grupę rozłączną pod względem pozycji - rozpoczynającą się od pozycji $i-2$, a kończącą na $i-3$). W ten sposób możemy już dobrać tylko $n-2$ grupy.

Na kolejnych poziomach czynimy analogicznie - widzimy więc, że na poziomie $j+2$ będzie $n-2^j$ grup po $2^j$ bitów, jednak grupy te nie są (w przeciwieństwie do poprzedniego zadania) rozłączne. Pojawi się więc zwiększenie liczby bramek (przy zachowaniu struktury układów częściowych), choć czas pozostanie taki sam - poziomów będzie $k$ ($n=2^k$).

$$T=2k + 3$$$$B=n \cdot B_{\square} + (n \cdot k - \sum_{j=0}^{k-1}2^j) \cdot B_{\blacksquare} + n \cdot B_{S} = n \cdot B_{\square} + [nk - (2^k-1)] \cdot B_{\blacksquare} + n \cdot B_{S} = $$ $$ = 2n + 3(nk + 1 - n) + 2n = n(3k + 1) + 3 = 198$$

## Zadanie 3
:::success
Autor: Piotr Warząchowski
:::
Drzewowy sumator z przeniesieniem równoległym, znany również jako drzewkowy sumator z przeniesieniem równoległym lub sumator drzewkowy, jest rodzajem sumatora, który jest zaprojektowany w celu przyspieszenia procesu dodawania przez zmniejszenie opóźnienia przeniesienia między bitami. Działa na zasadzie jednoczesnego generowania przeniesień dla różnych bitów i ich agregacji w strukturze drzewa, co pozwala na jednoczesne obliczanie wielu przeniesień.

### **Zasada działania**

Drzewowy sumator z przeniesieniem równoległym składa się z trzech głównych części:

1. **Generatory przeniesienia (G) i propagatory przeniesienia (P):** Dla każdej pary bitów wejściowych generowane są sygnały przeniesienia (G) i propagacji (P). Generator przeniesienia wskazuje, że nastąpi przeniesienie niezależnie od przeniesienia wejściowego, natomiast propagator wskazuje, że przeniesienie wejściowe zostanie przekazane na wyjście.
2. **Drzewo przeniesień:** Sygnały G i P są łączone w strukturze drzewa, która agreguje przeniesienia w sposób hierarchiczny, umożliwiając równoległe obliczanie przeniesień dla różnych grup bitów. Struktura drzewa skraca ścieżkę krytyczną przeniesienia.
3. **Sumatory końcowe:** Po wygenerowaniu wszystkich przeniesień, sumatory końcowe obliczają sumy poszczególnych bitów, korzystając z sygnałów propagacji i przeniesień z drzewa przeniesień.

### **Czas działania**

Czas działania drzewowego sumatora z przeniesieniem równoległym jest zdecydowanie krótszy niż w tradycyjnych sumatorach szeregowych, ponieważ opóźnienie przeniesienia jest znacznie zmniejszone dzięki równoległemu przetwarzaniu. Czas działania jest proporcjonalny do logarytmu z liczby bitów *n*, czyli *O*(log*n*), co jest znaczącą poprawą w porównaniu do liniowej zależności w sumatorach szeregowych.

### **Rozmiar**

Rozmiar, czyli liczba bramek logicznych potrzebnych do zbudowania drzewowego sumatora z przeniesieniem równoległym, jest większy niż w przypadku sumatorów szeregowych ze względu na potrzebę implementacji drzewa przeniesień i dodatkowych generatorów i propagatorów przeniesień. Liczba bramek zależy od konkretnej implementacji, ale generalnie rośnie szybciej niż liniowo z liczbą bitów n*n*, choć wolniej niż w przypadku kwadratowej zależności.
:::

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

Białe kwadraciki to full-addery

Blok C to:


plus full addery które są nad z tą różnicą że blok A gdy jest częścią bloku C nie realizuje połączenia xorami w Si, tylko wyznacza same Pi, Gi

## Zadanie 5
:::success
Autor: Patryk Flama
:::

Wiemy że pomnożenie n-bitowych liczb A i B da wynik co najwyżej 2n-bitowy, potrzebujemy więc dodatkowego rejestru na przechowywanie wyniku długości 2n (oszczędzamy miejsce przesuwając część wyniku do nieużywanej częci rejestru A)
Na koniec wynik będzie się znajdował w rejestrach P i A (mniej znaczące bity w A)


Algorytm bazuje na pisemnym mnożeniu bitów, gdzie iterujemy się po bitach jednej liczby (A), mnożymy ją z drugą liczbą (B) i dodajemy do wyniku po odpowiednim przesunięciu.
Z obserwacji - zawsze dodajemy albo 0 albo B, zamiast przesuwać dodawaną liczbę, możemy przesuwać wynik (gdzie będzie on stopniowo przechodził do rejestru A).

// dla każdego bitu z A (od najmniej znaczącego)
n razy:
    jeżeli a0 == 0:
        P += 0
    w pp:
        P += B
    
    // przesuń wynik w prawo
    A >>= 1
    a{n-1} = p0
    P >>= 1
    p{n-1} = carry_out

A=9=1001
B=3=0011
P=0000
carry_out|P|A=0000|1001

1. 0|0000|100**1** $\rightarrow$ 0|0011|1001 $\rightarrow$ 0|0001|1100
2. 0|0001|110**0** $\rightarrow$ 0|0001|1100 $\rightarrow$ 0|0000|1110
3. 0|0000|111**0** $\rightarrow$ 0|0000|1110 $\rightarrow$ 0|0000|0111
4. 0|0000|011**1** $\rightarrow$ 0|0011|0111 $\rightarrow$ 0|0001|1011

Więc wynik to 00011011 = 27 = 9*3

## Zadanie 6
:::success
Autor: Szymon Fluder
## Zadanie 6

a)
Tutaj trzeba minimalnie zmienić, bo trzeba robić przesunięcie arytmetyczne w P.

b)
używamy tych zasad

Przykład z książki

### Algorytm

rejestry: A,B,P, a_old, a_lsb
a_old = 0u
for i in [1..n]:
    a_lsb = A & 1u
    if (a_lsb == 0 && a_old == 1):
        P = P + B
    else if(a_lsb == 1 && a_old == 0):
        P = P - B  // albo P + (~B + 1)
    //poniżej shifty
    a_old = A & 1u
    A = A >> 1
    A = A + (P & 1u) << (n-1) // ustawienie MSB A
    P = P >> 1 // przesunięcie arytmetyczne!

## Wersja prostsza algorytmu
$$A*B = (-2^{n-1}*a_{n-1} + \Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B = (-2^{n-1}*a_{n-1}) * B + (\Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B $$

Niech $A' = \Sigma^{n-2}_{i=0} 2^{i}*a_{i}$. Wtedy
$A*B = ((-2^{n-1}*a_{n-1}) * B) + A'*B$.

Mnożymy $A'*B$ algorytmem z punktu a) --- liczba kroków algorytmu to $n-1$. W n-tym kroku odejmujemy od naszej sumy częśćiowej liczbę $a_{n-1}*B$.

Jak przekształcić sumator w układ odejmujący?

$C-D = C + (-D)$, zapis bitowy liczby $-D = \neg(D) + 1$
Czyli $C-D = C + \neg(D) + 1$.

Korzystając z ww. faktów:
### Algorytm

rejestry: A, B, P
for i in [1..n-1]:
    if (A & 1u):  // tego ifa da sie pozbyć
        P = P + B
    A = A >> 1  // dla uproszczenia operacji poniżej, uznajemy że to jest przesunięcie logiczne
    A = A + (P & 1u) << (n-1)  // ustawienie MSB A
    P = P >> 1  // to musi być przesunięcie arytmetyczne!
if (A & 1u):
    P = P - B // albo P + ~B + 1, ale wtedy może wystąpić overflow
A = A >> 1
A = A + (P & 1u) << (n-1)  // ustawienie MSB A
P = P >> 1

**tym można zastąpić pierwszy if**

ones_mask = ~0u;
a_lsb = A & 1u;
P = P + (B & ~(ones_mask + a_lsb));

**problem techniczny**
Najlepiej zrobić tak, aby rejestr P miał n+1 bitów. Zabezpieczymy się w ten sposób przed przepełnieniem, które może wystąpić w ostatniej operacji algorytmu. Stanie się to, gdy B jest równe 0.

### Mnożenie za pomocą tego algorytmu
A = $-9$ = 10111~(2)~
B = $-3$ = 11101~(2)~
P = 00000~(2)~

*po pierwszej iteracji*
A = 11011
P = 11110
*po drugiej iteracji*
A = 11101
P = 11101
*po trzeciej iteracji*
A = 01110
P = 11101
*po czwartej iteracji*
A = 10111
P = 11110
*po odjęciu B od P*
A = 11011
P = 00000
$-9 \cdot -3 = 27$
00000 11011~(2)~ = 27~(10)~
:::

## Zadanie 7
:::success
Autor: Mikołaj Karapka
**Działanie układu:**
* Na początku wypełniamy zerami bity **przeniesienia** i **sumy** w **P**.
* Wykonujemy pierwszą operację arytmetyczną: Przenosimy najmniej znaczący bit sumy **P** do **A** oraz przesuwamy rejestr **A** w celu zwolnienia miejsca na kolejny bit.
* Skoro pozycja bitów zmienia się **o jeden w prawo**, to możemy dodać bit przeniesienia **o jeden cykl później** na to samo miejsce, z którego go dostaliśmy.
* Dodawanie bitów działa **niezależnie** od siebie, ponieważ nie przenosimy między nimi wartości przeniesienia. Zwiększa to znacznie prędkość procesu.
* **Wynik** jest reprezentowany jako **suma** i **przeniesienie** w rejestrze **P**.
* W celu otrzymania **konkretnego wyniku**, konieczne jest połączenie **sumy** i **przeniesienia** za pomocą standardowego sumatora.
:::

## Zadanie 8
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 9
:::success
Autor: Viktoriia Kashpruk
:::

### Dzielenie z odzyskiwaniem (Division with Restoring)
Na początek mamy 3 rejestry:
**A** - bity liczby a
**B** - bity liczby b
**P** - pusty z zerami
1. **Inicjalizacja:**
- Ustaw `A` i `P` na wartość dzielnej, a `B` na wartość dzielnika.

2. **Dla każdego kroku `i` od `n` do `1`:**
a. **Shift (przesunięcie) w lewo:**
- `A, P` ← `A * 2, P * 2`
b. **Odejmowanie dzielnika:**
- `P` ← `P - B`
c. **Sprawdzenie i ustawienie bitu:**
- Jeżeli `P` jest ujemne, to `A_i` ← `0`, w przeciwnym razie `A_i` ← `1`
d. **Przywracanie wartości `P`:**
- Jeżeli `P` jest ujemne, to `P` ← `P + B`

3. **Wynik:**
- Wynik dzielenia jest w `A`, reszta z dzielenia w `P`.