# Ćwiczenia 1, grupa cz. 12-14, 10. 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 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | X | X | X | X | | | | X |
Adam Ciężkowski | | | | | | | | | |
Jacek Długopolski | | | | | | | | | |
Jakub Fila | X | | X | X | | X | | | |
Krzysztof Grynkiewicz | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | | | | x |
Hubert Jabłoński | X | | X | X | | X | X | | X |
Antoni Kamiński | | | | | | | | | |
Paweł Karaś | X | | X | X | | X | | | X |
Emil Kisielewicz | | | | | | | | | |
Kacper Komenda | | | | | | | | | |
Filip Komorowski | X | X | X | ==X== | X | X | | | X |
Piotr Piesiak | ==x==| x | x | x | x | x | | | x |
Artur Krzyżyński | x | x | x | x | x | | | | x |
Patryk Mazur | X | | X | X | | | | |==X==|
Szymon Mleczko | X | | X | X | X | X | X | X | X |
Michał Mróz | X | x |==X==| X | X | | | | X |
Dominik Olejarz | | | | | | | | | |
Magdalena Słonińska | X | | | | | | | | X |
Joanna Stachowicz | | | | | | | | | |
Adam Szeruda | X | X | X | X | X | | X | | X |
Kamil Tasarz | X | | X | X | X | | | | X |
Michał Zieliński | 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: Piotr Piesiak
:::
* n bitowy RCA będzie miał n pełnych sumatorów. Pełny sumator wykonuje operacje:
$$S_i = A_i \oplus B_i \oplus C_i \\ C_i = A_iB_i + A_iC_{i-1} + B_iC_{i-1} $$
lub inaczej
$$C_i = G_{i} + C_{i-1}P_i \\ C_i = A_iB_i + (C_{i-1}(A_i\oplus B_i))$$
Układ pełnego sumatora wygląda:

Czas działania pełnego sumatora to jego maksymalna głębokość -> 3.
Zatem n bitowy sumator działa w czasie 3n jednostek.
* Wystarczy sprawdzić czy ostatnie przeniesienie $C_n$ jest prawdziwe

Funkcje logiczne zdefiniowane przez układ sumatora:

(p xor q) = (p and not q) or (not p and q)

S = (A xor B) xor Cin

## Zadanie 2

:::success
Autor: Artur Krzyżyński
:::
Główna idea to to, że dodawanie traktując liczby ze znakiem jako $n+1$ bitowe bez znaku to dodawanie modulo $2^{n+2}$, gdzie $[0,2^{n+1})$ są jakby dodatnie, a w $[2^{n+1}, 2^{n+2})$ ujemne, bo modulo $2^{n+2}$ przedział $[2^{n+1}, 2^{n+2})$ = $(-2^{n+1}, 0]$.

## Zadanie 3

:::success
Autor: Jakub Fila
:::

## Zadanie 4

:::success
Autor: Filip Komorowski
:::


a)
Czas działania układu:
czas równoległego liczenia RCA + wybór multiplekserów+ przejścia przez bramki

Zgodnie z podejściem z Appendixa - ustalmy czas obliczania RCA k-bitowego na k jednostek czasu, a wybór multipleksera oraz przejścia przez bramki logiczne na 1.

Wtedy czas działania powyższego układu można oszacować przez 6(najdłuższe RCA) + 1 czyli w sumie 7 jednostek czasu.

b)
Skoro każdy blok ma rozmiar k oraz mamy d par równoległych bloków, mamy $n = k*d$.

* Intuicja - małe k może być dobre. Błędna.

* Rozwiązanie:
Gdy $k = \sqrt{n}$, czas obliczania równoległego oraz następującego po nim przejścia sekwencyjnego trwają tyle samo. To daje nam czas liczenia rzędu $O(\sqrt{n})$, czyli duże usprawnienie w stosunku do podejścia liniowego.

czas działania układu jest <= k + 2*((n-k)/k) + 2

f(k) = k + 2*((n-k)/k) + 2, założyć że ta funkcja jest ciągła i policzyć minimum

## Zadanie 5

:::success
Autor: Daniel Boguszewski
:::


Jednostkowy czas działania przedstawionego układu: $1 + (3\cdot 3) + 1$.
Kolejne sumatory oczekują na odpowiedź poprzednika -"wewnętrzne" sumatory oczekują na sygnał $C_{in}$. W tym czasie bramka AND oczekuje na propagację od sumatora "powyżej", po czym dopiero przesyła sygnał do bramki OR. W przedstawionym układzie odbywa się to 3 razy, co w połączeniu z sumatorami na początku i końcu układu daje czas 11.

Jeżeli przyjąć, że sumator działa w czasie $T_k$ (gdzie k to ilość bitów rozpatrywana w dodawaniu), to ogólny czas działania wynosi $$2T_k + ([n / k] - 2)(T_k + t_{and} + t_{or}),$$gdy $n > 2k$. Dodatkowo jeśli zachodzi $$[n / l]T_l - [n / k]T_k < ([n / k] - [n / l])(t_{and} + t_{or}),$$ gdzie $l > k$, wtedy optymalnym jest wykorzystanie większej (o $[n / k] - [n / l]$) liczby sumatorów. $[\cdot]$ - powała.

## Zadanie 6

:::success
Autor: Michał Zieliński
:::

### Treść
Opracuj sumator złożony z bloków (podobnie jak w poprzednim zadaniu), w którym każdy blok jest sumatorem RCA z dodatkowym układem obliczającym przeniesienie z tego bloku. Ten dodatkowy układ może korzystać jedynie z przeniesienia wejściowego danego bloku oraz bitów argumentów do zsumowania w danym bloku. Ideę tego układu oprzyj na liczeniu propagacji przeniesienia i generowania przeniesienia przez dany blok. Będzie to tzw. blokowy sumator z przeniesieniem równoległym (ang. carry-lookahead adder, CLA). Narysuj swój n-bitowy sumator dla n=16 i rozmiaru bloku k=4.
### Rozwiązanie
Aby obliczyć i-ty bit wyniku korzystaliśmy z $s_i = a_ib_ic_i + a_ib_ic_i + a_ib_ic_i + a_ib_ic_i$.
Teraz użyjemy
$c_i = g_{i-1} + p_{i-1}c_{i-1}, g_{i-1} =a_{i-1}b_{i-1}, p_{i-1} =a_{i-1} + b_{i-1}$
Czyli mamy
$c_i = g_{i-1} + p_{i-1}g_{i-2} + p_{i-1}p_{i-2}g_{i-3} + ⋯ + p_{i-1}p_{i-2}⋯p_1g_0 + p_{i-1}p_{i-2}⋯p_1p_0c_0$

$PG = p_0 \cdot p_1 \cdot p_2 \cdot p_3$
$GG = g_5+g_2\cdot p_3+g_1 \cdot p_3 \cdot p_2+g_0 \cdot p_3 \cdot p_2 \cdot p_1$
$C_{4} = G_0 + P_0 \cdot C_0$
$C_{8} = G_4 + G_0 \cdot P_4 + C_0 \cdot P_0 \cdot P_4$
$C_{12} = G_8 + G_4 \cdot P_8 + G_0 \cdot P_4 \cdot P_8 + C_0 \cdot P_0 \cdot P_4 \cdot P_8$
$C_{16} = G_{12} + G_8 \cdot P_{12} + G_4 \cdot P_8 \cdot P_{12} + G_0 \cdot P_4 \cdot P_8 \cdot P_{12} + C_0 \cdot P_0 \cdot P_4 \cdot P_8 \cdot P_{12}$

## Zadanie 7

:::success
Autor: Hubert Jabłoński
:::


Drzewowy sumator z przeniesieniem równoległym polega na tym, aby jednocześnie liczyć sumę dwóch liczb oraz ich przeniesienie.

Korzysta ono z faktu, że przeniesienie może zostać generowane (gdy $a_ib_i=1$) lub propagowane (gdy $a_i + b_i=1$).

$c_i = g_{i-1}+p_{i-1}c_{i-1}$

Układ ten jak nazwa wskazuje ma strukturę drzewa, a zatem "wysokość" tego układu wynosi $\log_2{n}$, a szerokość $n$.

Aby policzyć przenisienie, wpierw musimy policzyć wszystkie $P_{i,k}$ i $G_{i,k}$, co zajmuje $\log_2{n}$ czasu. Po ich policzeniu, możemy z łatwością policzyć kolejne przeniesienia i wprowadzić je do układów sumujących, co zajmuje ponownie $\log_2{n}$. Także czasowo zajmie to na ogół $2\log_2{n}$

W układach $A$ są $4$ bramki, a w $B$ - $5$ bramek.

Jest $n$ bramek typu $A$ i $\frac{n}{2}+
\frac{n}{4}+...+\frac{n}{2^{\log_2{n}}}$ bramek $B$. Czyli na ogół będziemy mieli $9n$ bramek. Jeśli pomyślimy o tym jednak w notacji dużego $O$. To będzie ich $O(n\log_2{n})$

## Zadanie 8

:::success
Autor: Szymon Mleczko
:::
https://miro.com/welcomeonboard/UnRZejkzRG11QTUycnJ2VHdVd2Y0WWJTY0E2TGptZkNsUHZDQmI3cVlZd3ZZamlWckhUT21RRkQyT3AycnhkdHwzMDc0NDU3MzU1MTM0MjAyNjky?invite_link_id=822750448175
czas działania (sufit(log2(n/k)))*4 +2 + (k-1)2 +1
rozmiar 5(sufit(log2(n/k)))+5n+6n/k
Kombinacja sumatora drzewowego zsumatorem RCA pozwala optymalizować wielkość układów
## Zadanie 9

:::success
Autor: Patryk Mazur
:::