---
# System prepended metadata

title: 'Ćwiczenia 1, grupa cz. 12-14, 10. marca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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
:::
![](https://i.imgur.com/CtYVDLo.png)
*  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:
![](https://i.imgur.com/boV1OV6.png)

![](https://i.imgur.com/mLobU3v.png)
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]$.
![](https://i.imgur.com/y58vJrW.jpg)


## Zadanie 3

:::success
Autor: Jakub Fila
:::
![](https://i.imgur.com/fqpQFsF.png)

## Zadanie 4

:::success
Autor: Filip Komorowski
:::

![](https://i.imgur.com/AxOLpba.png)

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
:::

![](https://i.imgur.com/54R6Vft.png)

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$
![](https://i.imgur.com/MrX0Y6t.png)
![](https://i.imgur.com/HVQjq3T.png)

![](https://i.imgur.com/ctcgTNH.png)
$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$
![](https://i.imgur.com/pW9W80n.png)
$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
:::

![](https://i.imgur.com/D006QG4.png)
![](https://i.imgur.com/L9djWsY.jpg)
![](https://i.imgur.com/m9nEkgQ.jpg)

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
:::
![](https://i.imgur.com/e4zbiS3.png)
![](https://i.imgur.com/mr6wBcr.png)
![](https://i.imgur.com/UMMedS8.png)