Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
1
Prawa ł czno ci i przemienno ci dodawania
a
+ b + c + d + e + f + g + h + i + … = { [ ( a + b ) + ( c + d ) ] + [ ( e + f ) + ( g + h ) ] } + { [ ( i + …
a
+ b + c + d + e + f + g + h + i + … = [ ( a + b + c ) + ( d + e + f ) + ( g + h + i ) ] + [ ( …
prawo ł czno ci dodawania w systemie pozycyjnym
∑
∑
∑
∑
−
−
=
−
−
=
−
−
=
−
−
=
+
+
+
=
+
+
+
=
+
+
+
1
1
1
1
...)
(
...
...
k
m
i
i
i
i
i
k
m
i
i
i
k
m
i
i
i
k
m
i
i
i
c
b
a
c
b
a
C
B
A
β
β
β
β
dodawanie wieloargumentowe jednopozycyjne – suma w systemie pozycyjnym
i
m
i
m
i
i
i
i
i
i
i
u
u
u
u
c
b
a
β
β
β
β
β
)
...
(
...)
(
)
(
)
2
(
2
)
1
(
1
)
0
(
+
+
+
+
+
=
+
+
+
• suma jest wielocyfrowa (co najmniej dwucyfrowa)
ł czno i przemienno dodawania w systemie pozycyjnym
∑ ∑
∑ ∑
∑ ∑
−
−
=
=
−
−
−
=
=
=
−
−
=
=
=
=
+
+
+
1
0
)
(
1
1
)
(
1
1
)
(
)
(
)
2
(
)
1
(
)
(
...
n
q
i
m
r
r
r
r
i
i
n
q
i
k
p
p
i
i
k
p
n
q
i
i
p
i
k
u
x
x
X
X
X
β
β
β
β
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
2
Dodawanie wieloargumentowe jednopozycyjne w systemach naturalnych
i
m
i
m
i
i
i
i
i
i
i
u
u
u
u
x
x
x
β
β
β
β
β
)
...
(
...)
(
)
(
)
2
(
2
)
1
(
1
)
0
(
)
3
(
)
2
(
)
1
(
+
+
+
+
=
+
+
+
przy tym
}
1
,...,
1
,
0
{
,
)
(
)
(
−
∈
β
j
i
j
i
u
x
suma k składników mo e by m-cyfrowa
1
)
1
(
)
1
(
1
0
1
1
)
(
)
(
−
≤
−
=
−
≤
⇒
−
≤
≤
∑
∑
=
=
m
k
j
k
j
j
i
j
i
k
x
x
β
β
β
β
]
1
)
1
(
[
log
+
−
=
β
β
k
m
β
β
β
β
β
β
11
...
11
1
...
)
1
/(
)
1
(
2
1
=
+
+
+
=
−
−
≤
−
−
m
m
m
k
dodawanie mo na wykona dwuetapowo:
• obliczy wielopozycyjne sumy przej ciowe (w dowolnej kolejno ci)
• doda liczby wielocyfrowe skomponowane z sum przej ciowych
→ je li liczba składników jest ≤
β
+1, to suma jest dwucyfrowa i wynosi
β
β
β
β
β
<
−
+
+
+
≤
−
+
+
+
=
+
+
+
r
x
x
x
r
x
x
x
r
u
v
i
i
i
i
i
i
i
i
)
1
(
)
2
(
)
1
(
)
1
(
)
2
(
)
1
(
1
...
0
gdy
}
...
,
{
}
,
{
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
3
Dodawanie wieloargumentowe w systemach naturalnych
→ je li liczba argumentów k >
β
+1, to dodawanie mo na wykona etapami
(0)
(0)
a
k
–1
a
k
–2
…
a
–m
+3
a
–m
+2
a
–m
+1
a
–m
(0)
(0)
b
k
–1
b
k
–2
…
b
–m
+3
b
–m
+2
b
–m
+1
b
–m
(0)
(0)
c
k
–1
c
k
–2
…
c
–m
+3
c
–m
+2
c
–m
+1
c
–m
(0)
(0)
d
k
–1
d
k
–2
…
d
–m
+3
d
–m
+2
d
–m
+1
d
–m
…
…
…
…
…
…
…
…
…
>
β
+1
a
rg
u
m
en
tó
w
+
(0)
(0)
p
k
–1
p
k
–2
…
p
–m
+3
p
–m
+2
p
–m
+1
p
–m
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
(0)
(0)
(0)
x
k
–1
(0)
x
k
–2
…
(0)
x
–m
+3
(0)
x
–m
+2
(0)
x
–m
+1
(0)
x
–m
(0)
(1)
x
k
–1
(1)
x
k
–2
…
(1)
x
–m
+3
(1)
x
–m
+2
(1)
x
–m
+1
(1)
x
–m
(0)
(2)
x
k
–1
(2)
x
k
–2
…
(2)
x
–m
+3
(2)
x
–m
+2
(2)
x
–m
+1
(2)
x
–m
(0)
(0)
≤
β
+1
a
rg
.
+
…
…
…
…
…
…
…
…
…
…
(0)
u
k
+1
(0)
u
k
(0)
u
k
–1
(0)
u
k
–2
…
(0)
u
–m
+3
(0)
u
–m
+2
(0)
u
–m
+1
(0)
x
–m
2
a
rg
…
(1)
u
k
(1)
u
k
–1
(1)
u
k
–2
…
(1)
u
–m
+3
(1)
u
–m
+2
(1)
u
–m
+1
…
s
k
s
k
s
k
–1
s
k
–2
s
–m
+3
s
–m
+2
(0)
u
–m
+1
(0)
x
–m
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
4
Redukcja argumentów w drzewie CSA
sumator (k,m) – układ obliczaj cy m-pozycyjn sum k liczb jednocyfrowych
]
1
)
1
(
[
log
+
−
=
β
β
k
m
)
0
(
)
1
(
)
1
(
..
i
i
m
i
u
u
u
−
(k,m)
(k,m)
(k,m)
(k,m)
)
0
(
1
)
1
(
1
)
1
(
1
..
−
−
−
−
i
i
m
i
u
u
u
)
1
(
1
−
+
−
m
m
i
u
)
1
(
−
−
m
m
i
u
)
1
(
2
−
+
−
m
m
i
u
)
2
(
2
)
1
(
2
−
−
i
i
x
x
)
1
(
2
−
−
m
i
u
..
...
)
2
(
)
1
(
)
(
)
2
(
)
1
(
m
k
i
k
i
k
i
i
i
x
x
x
x
x
−
+
..
...
)
2
(
1
)
1
(
1
)
(
1
)
2
(
1
)
1
(
1
m
k
i
k
i
k
i
i
i
x
x
x
x
x
−
−
+
−
−
−
−
Struktura redukcji argumentów w drzewie CSA zbudowanym z modułów (k,m)
∑ ∑
∑ ∑
∑ ∑
−
−
=
=
−
−
−
=
=
=
−
−
=
=
=
=
+
+
+
1
0
)
(
1
1
)
(
1
1
)
(
)
(
)
2
(
)
1
(
)
(
...
n
q
i
m
r
r
r
r
i
i
n
q
i
k
p
p
i
i
k
p
n
q
i
i
p
i
k
u
x
x
X
X
X
β
β
β
β
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
5
Redukcja argumentów w dwójkowym drzewie CSA
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
x
x
x
x
x
x
)
6
(
1
)
5
(
1
)
4
(
1
)
3
(
1
)
2
(
1
)
1
(
1
−
−
−
−
−
−
i
i
i
i
i
i
x
x
x
x
x
x
)
6
(
1
)
5
(
1
)
4
(
1
)
3
(
1
)
2
(
1
)
1
(
1
+
+
+
+
+
+
i
i
i
i
i
i
x
x
x
x
x
x
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
Skala redukcji operandów w wielopoziomowym dwójkowym drzewie CSA
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
6
Dwójkowe sumatory wieloargumentowe (CSA)
(3,2)
v
0
x
0
y
0
z
0
(2,2)
(3,2)
v
1
x
1
y
1
z
1
(3,2)
(3,2)
v
2
x
2
y
2
z
2
(3,2)
(3,2)
v
3
x
3
y
3
z
3
(3,2)
s
0
s
1
s
2
s
3
s
4
s
5
re
d
u
kt
o
r
sumator ko cowy
FA
FA
FA
FA
Czteropozycyjny sumator czterooperandowy CSA
czas dodawania = czas redukcji + czas dodawania ko cowego
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
7
Sumowanie k dwójkowych operandów n-pozycyjnych (CSA)
Pojedynczy układ (3,2) redukuje dokładnie jeden operand 1-bitowy
→ do redukcji k operandów n-bitowych potrzeba n(k–2) układów (3,2)
→ k
L
operandów na poziomie L ⇒
2
/
1
L
L
L
k
k
k
+
≤
+
na poziomie L+1
• jeden poziom CSA redukuje 3 operandy do 2 – skala redukcji 3/2
• dwa poziomy CSA redukuj 4 operandy do 2 – skala redukcji
2
• trzy poziomy CSA redukuj 6 operandów do 2 – skala redukcji
3
3
L
L
L
k
)
(
2
)
2
(
2
2
3
≤
≤
(lepsza ocena)
L
L
L
k
)
(
2
)
3
(
2
2
3
3
≤
≤
(L
≥3)
Redukcja liczby operandów w wielopoziomowej strukturze CSA
liczba poziomów L
1
2
3
4
5
6
7
8
9
10
2
L
)
2
/
3
(
3
4
6 10 15 22 34 51 76 115
maksymalna liczba operandów
3
4
6
9 13 19 28 42 63 94
L
L
44224957
,
1
2
)
3
(
2
3
⋅
≅
⋅
3
5
6
9
13 18 26 38 54 78
L
L
41421356
,
1
2
)
2
(
2
⋅
≅
3
4
6
8
12 16 23 32 46 65
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
8
Konstrukcja wielopoziomowego sumatora CSA (1)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (log k dodatkowych bitów):
1
2
)
1
2
(
...
0
1
2
,...,
,
0
log
2
1
2
1
−
<
−
≤
+
+
+
≤
⇒
−
≤
≤
+
k
n
n
k
n
k
k
X
X
X
X
X
X
• oszacowanie szeroko ci:
k
n
w
log
+
=
• liczba elementów reduktora CSA: n(k–2)
• oszacowanie gł boko ci:
)
2
(log
)
3
(log
3
2
log
)
5
,
1
(log
1
1
k
L
k
−
−
≤
≤
• czas dodawania:
n
L
T
log
2
4
+
≥
Konstrukcja jest rekurencyjna (top-down lub bottom-up – drzewo Wallace’a)
top-down
(od góry)
1. przył cz po 3 sygnały wej ciowe o tej samej wadze do wej modułu (3,2)
2. sygnały nieprzył czone przeka na ni szy poziom CSA
3. wytwórz wyj cia wszystkich modułów (3,2) (lub (2,2)) – maj ró ne wagi!
4. zbierz sygnały o tych samych wagach
5. powtarzaj 1–4 dopóki liczba sygnałów o jakiej wadze 2
i
przekracza 2.
6. doł cz sumator ko cowy (najlepiej szybki: CLA, PPA, COSA)
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
9
Schemat konstrukcji wielopoziomowego drzewa CSA (1)
przykład – 7 argumentów 4-bitowych (w=3+3, L=4)
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
10
Schemat konstrukcji wielopoziomowego drzewa CSA (2)
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
11
Dwójkowe sumatory wieloargumentowe U2 (CSA)
Wytworzenie poprawnej sumy k argumentów n-bitowych (wyrównaj krótsze!)
wymaga k-krotnego rozszerzenia zakresu (log k dodatkowych bitów):
1
log
2
1
1
log
1
2
1
1
2
...
2
1
2
,...,
,
2
−
+
−
+
−
−
<
+
+
+
≤
−
⇒
−
≤
≤
−
k
n
k
k
n
n
k
n
X
X
X
X
X
X
Rozszerzenie zakresu o m = log
2
k
pozycji
• doł czenie m bitów rozszerzenia lewostronnego
o
wada: wiele argumentów stałych (bity rozszerzenia)
o
drzewo CSA (k+m)-bitowe
• zamiana argumentów na dodatnie z korekcj , zgodnie z zale no ci
∑
∑
−
=
−
−
−
−
=
−
−
+
−
+
−
=
+
−
2
0
1
1
1
2
0
1
1
2
2
)
1
(
2
2
2
k
i
i
i
k
k
k
k
i
i
i
k
k
x
x
x
x
→ zakodowanie stałej −n2
k
−1
(na m+k bitach {r
k
+m
−1
, … , r
k
−1
, 0, 0,…, 0})
√ znaczna redukcja liczby stałych bitów
√ prostsze drzewo CSA
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
12
Zliczanie jedynek (lub zer) w słowie n-bitowym
(prawie) trzykrotna redukcja na I poziomie sumatora
• je li n=3k, to na II poziomie jest k operandów 2-bitowych
• je li n
≠
3k, to na II poziomie jest n/3 operandów 2-bitowych
Parametry układu (bez 2-bitowego sumatora wyj ciowego)
• liczba modułów CSA – n–2
• liczba poziomów CSA – 1+ liczba poziomów redukcji n/3 operandów,
czyli
1
3
log
)
1
3
/
(log
3
1
1
3
log
1
3
/
log
+
−
≤
≤
+
−
−
n
L
n
• liczba bitów wyniku – log
2
n
zliczanie zer – liczba jedynek w słowie zanegowanym jest równa
liczbie zer w słowie oryginalnym
zliczanie wzorców bitowych – przekształcenie słowa wej ciowego przez funkcj
f
(x
i
, x
i
+1
,…, x
i+p
)=1
⇔ {x
i
, x
i
+1
,…, x
i+p
}
≡wzorzec
i zliczanie jedynek funkcji f
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
13
Alternatywne konstrukcje wielopoziomowego drzewa CSA*
od góry (top-down)
od dołu (bottom-up) – drzewo Wallace’a
liczba operandów
struktura
liczba operandów
struktura
N
= N
0
(N
0
/3)
∗(3,2)
L
k
L
−1
< N < k
L
(N
−k
L
−1
)
∗(3,2)+
(N
0
/3)
∗2+|N
0
|
3
=N
1
(N
1
/3)
∗(3,2)
L
−1
k
L
−2
+ k
L
−2
/2 = k
L
−1
k
L
−1
/3
∗(3,2)+|k
L
−1
|
3
… …
… …
…
… …
… …
(6/3)
∗2+0=4
1+1
∗(3,2)
2
3 + 3/2 = 4 = k
2
3/2 ∗(3,2)+1
(4/3)
∗2+1=3
1
∗(3,2)
1
2 + 3/2 = 3 = k
1
2/2 ∗(3,2)
redukcja od poziomu L,
łatwiejsza konstrukcja drzewa
kumulacja operandów od poziomu 1
2
/
1
L
L
L
k
k
k
+
=
+
, k
0
= 2
L
operandy struktura
operandy struktura
operandy
struktura
7
21
7
∗(3,2)
27
9
∗(3,2)
20…27 1…8
∗(3,2)+…
6
7
∗2=14 2+4∗(3,2)
9
∗2=18
6
∗(3,2)
8
∗2+3=19
6
∗(3,2)+1
5
4
∗2+2=10 1+3∗(3,2)
6
∗2=12
4
∗(3,2)
6
∗2+1=13
4
∗(3,2)+1
4
3
∗2+1=7 1+2∗(3,2)
4
∗2=8 2+2∗(3,2)
4
∗2+1=9
3
∗(3,2)
3
2
∗2+1=5 2+1∗(3,2)
2
∗2+2=6
2
∗(3,2)
2
∗3=6
2
∗(3,2)
2
1
∗2+2=4 1+1∗(3,2)
2
∗2=4 1+1∗(3,2)
2
∗2=4
1
∗(3,2)+1
1
1
∗2+1=3
1
∗(3,2)
1
∗2+1=3
1
∗(3,2)
1
∗2+1=3
1
∗(3,2)
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
14
Dwójkowy sumator CSA tylko z modułów (3,2) i (2,2)*
(3,2)
v
0
x
0
y
0
z
0
(2,2)
(3,2)
v
1
x
1
y
1
z
1
(3,2)
(3,2)
v
2
x
2
y
2
z
2
(3,2)
(3,2)
v
3
x
3
y
3
z
3
(3,2)
s
0
s
1
s
2
s
3
s
4
s
5
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
(2,2)
sumator
ko cowy
(~RCA)
Czteropozycyjny sumator czterooperandowy CSA
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
15
Sumatory (k, m) w systemach dwójkowych*
β
=2 ⇒
1
2
−
≤
m
k
,
)
1
(
log
2
+
=
k
m
• elementarny sumator (3,2) – sumator 1-bitowy
• licznik (k,m) – binarny sumator (k,m)
o
– koduje liczb jedynek z k wej na m wyj ciach
o
– drzewo (3,2) lub projekt indywidualny, np. licznik (4,3)
)
(
)
(
)
0
(
v
z
y
x
u
⊕
⊕
⊕
=
)
)(
(
)
)(
(
)
)(
(
)
1
(
y
x
v
z
v
x
z
y
v
z
y
x
u
+
⊕
+
+
⊕
+
+
⊕
=
xyzv
u
=
)
2
(
• reduktor (k,2) – koduje liczb jedynek z k wej na 2 wyj ciach sumy
i pewnej liczbie wyj przeniesie (kumulacja przeniesie )
k
> 3 operandów wej ciowych ⇒ redukcja w układzie wielopoziomowym
• kolumny reduktorów (k,2) o wagach 2
i
– kumulacja przeniesie
• drzewo – gał zie liczników (3,2) o wagach 2
i
i redukcja przeniesie
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
16
Liczniki jedynek (k, m) i reduktory (k, 2)*
c
i
+1,i
c
i
+2,i
c
i,i–
2
s
i
+1
s
i
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
i
x
x
x
x
x
x
x
(3,2)
(3,2)
(3,2)
(3,2)
(4,3)
(3,2)
(3,2)
(3,2)
(3,2)
(3,2)
)
7
(
)
6
(
)
5
(
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
i
i
i
x
x
x
x
x
x
x
Licznik (7,3)
Reduktor (7,2)
(3,2)
s
i
+2
s
i
+1
s
i
c
i,i–
1
c
i
+1,i
c
i
+2,i
s
i
+1
s
i
c
i,i–
2
c
i,i–
1
)
4
(
)
3
(
)
2
(
)
1
(
i
i
i
i
x
x
x
x
Reduktor (4,2)
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
17
Liczniki wielokolumnowe
)
,
,
,...,
(
0
1
1
m
k
k
k
s
−
*
Dodawanie operandów o rosn cych wagach (k
i
o wadze
β
i
, i = 0,1,…,s)
suma na m pozycjach – wektor o l składowych:
– jednooperandowa s-pozycyjna suma o wadze
0
2 ,
– wielooperandowe przeniesienie wektorowe o wagach operandów (2
s
)
i
Warunek zakodowania wyniku na m pozycjach
∑
−
=
−
≥
−
1
0
)
1
(
1
s
i
i
i
m
k
β
β
β
w systemie dwójkowym
∑
−
=
≥
−
1
0
2
1
2
s
i
i
i
m
k
warunek realizowalno ci licznika (k, k, ..., k, m)
)
1
2
(
1
2
−
≥
−
s
m
k
m
≤2s ⇒ suma k operandów s-pozycyjnych jest najwy ej 2-operandowa
)
1
2
(
1
2
1
2
2
−
≥
−
≥
−
s
m
s
k
⇒
1
2
+
≤
s
k
Sumatory CSA
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc, 30 wrze nia 2009
CSA–
18
Parametry optymalnych liczników s-kolumnowych*
s
1
2
3
4
5
6
7
m=
2s
2
4
6
8
10 12 14
k
3
5
9
17 33 65 129
2
2
2
2
2
a)
b)
s
i
2
i
2 +1
s
i
2 +3
c
i
2 +4
c
i
2 +2
c
i
2
i
2 +1
i
2 +2
i
2 +3
i
2 +4
2
2
2
2
2
s
s
c
c
s
i
3
i
3 +1
i
3 +2
i
3 +4
i
3 +3
i
3
i
3 +1
i
3 +2
i
3 +4
i
3 +3
2
i
2
t
i
2
u
i
2
v
i
2
w
i
2
x
i
2
y
i
2
z
i
2
2
i
2 +1
i
2 +1
t
i
2 +1
u
i
2 +1
v
i
2 +1
w
i
2 +1
x
i
2 +1
y
i
2 +1
z
2
i
2
i
3 +1
3
t
i
3
i
3 +1
t
u
u
v
v
w
w
x
x
y
y
z
z
2
i
3 +2
t
u
v
w
x
y
z
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
i
3
i
3 +1
i
3 +2
Schemat dodawania w układach: a) (7,7,5), b) (7,7,7,5)
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
1
rok
1. C||S/P
← (S/P) + x
i
(A)
Krok
2. C||S/P||X/P
← 2
–1
(C||S/P||X/P) = ShR(C||S/P||X/P)
Krok
3. i = i +1. Je li i < k+m, wró do kroku 1.
Wynik
: A
⋅X = (S/P||X/P)
P
SHR (
×β
−1
)
S
X
A
Iloczyn cz
ciowy
Schemat blokowy układu mno
cego: S/P – rejestr sum cz ciowych,
X/P – rejestr mno nika, A – rejestr mno nej, C – rejestr przeniesienia
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
2
Schematy przy pieszonego mno enia
CSA
CPA
CPA
x
0
A
x
1
A
x
2
A
x
3
A
x
0
A
x
1
A
x
2
A
x
3
A
akumulacja równoległa
CSA
CSA
akumulacja sekwencyjna
CSA
• akumulacja równoległa – drzewiasta struktura CSA,
• akumulacja sekwencyjna – liniowa struktura CSA, matryca mno ca
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
3
Akumulacja iloczynów cz ciowych
• sumatory wielooperandowe CSA
ró ne wagi iloczynów cz ciowych
ró na liczba operandów jednej wagi
A 9 8 7 6 5 4 3 2 1 0 A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o
o o o o o o o o o
o o o o o o o
matryca mno
ca
drzewo CSA
drzewo CSA
• szybka redukcja operandów w najdłu szej kolumnie
• redukcja do 1 operandów najni szych wag (krótsze ko cowe dodawanie)
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
4
Optymalizacja struktury CSA (1)
redukcja maksymalna
drzewo Wallace’a
A 9 8 7 6 5 4 3 2 1 0
A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
o o o o o o o o o o
o o o o o o
o o
CSA, poziom 3 – wej cia układów (3,2) lub (2,2)
A 9 8 7 6 5 4 3 2 1 0
A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o
o o o o o o o o o o
CSA, poziom 3 – wynik redukcji: wyj cia układów (3,2) lub (2,2)
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
5
Optymalizacja struktury CSA (1)
A 9 8 7 6 5 4 3 2 1 0
A 9 8 7 6 5 4 3 2 1 0
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o
o o o o o o o o o o o
CSA, poziom 2
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o
o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
6
Matrycowe układy mno
ce – schemat mno enia
a
4
a
3
a
2
a
1
a
0
×
x
4
x
3
x
2
x
1
x
0
a
4
x
0
a
3
x
0
a
2
x
0
a
1
x
0
a
0
x
0
+
a
3
x
1
a
2
x
1
a
1
x
1
a
0
x
1
a
4
x
1
s
41
s
31
s
21
s
11
c
41
c
31
c
21
c
11
+
a
3
x
2
a
2
x
2
a
1
x
2
a
0
x
2
a
4
x
2
s
52
s
42
s
32
s
22
c
52
c
42
c
32
c
22
+
a
3
x
3
a
2
x
3
a
1
x
3
a
0
x
3
a
4
x
3
s
63
s
53
s
43
s
33
c
63
c
52
c
42
c
32
+
a
3
x
3
a
2
x
3
a
1
x
3
a
0
x
3
a
4
x
3
s
74
s
64
s
54
s
44
+
c
74
c
64
c
54
c
44
s
9
s
8
s
7
s
6
s
5
s
4
s
3
s
2
s
1
s
0
sji oraz cji – sumy i przeniesienia na pozycji j w i-tym kroku akumulacji
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
7
Matryca mno
ca kodu naturalnego (Brauna)
a
4
x
0
HA
a
0
x
1
HA
a
1
x
1
HA
a
2
x
1
HA
a
3
x
1
a
4
x
1
FA
a
0
x
2
FA
a
1
x
2
FA
a
2
x
2
FA
a
3
x
2
a
4
x
2
FA
a
0
x
3
FA
a
1
x
3
FA
a
2
x
3
FA
a
3
x
3
a
4
x
3
FA
a
0
x
4
FA
a
1
x
4
FA
a
2
x
4
FA
a
3
x
4
a
4
x
4
HA
FA
FA
FA
p
9
p
8
p
7
p
6
p
5
p
4
p
3
p
2
p
1
p
0
CSA
CSA
CSA
CPA
a
0
x
0
a
1
x
0
a
2
x
0
a
3
x
0
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
8
Multiplikator Brauna (Braun multiplier)
HA
HA
HA
HA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
HA
x
0
x
1
x
2
x
3
x
4
a
4
a
2
a
1
a
3
a
0
s
0
s
1
s
3
s
2
s
4
s
5
s
6
s
7
s
8
s
9
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
9
Matrycowe układy mno
ce kodu U2
iloczyny cz ciowe lub iloczyny elementarne mog by liczbami ujemnymi
.
2
2
2
2
2
2
2
2
2
2
2
0
1
1
2
0
1
1
2
0
2
0
2
1
1
2
0
1
1
2
0
1
1
−
+
−
+
+
=
=
+
−
⋅
+
−
∑
∑
∑
∑
∑
∑
−
=
−
−
−
=
−
−
−
=
+
−
=
−
+
−
−
−
=
−
−
−
=
−
−
k
i
i
i
m
m
m
j
j
j
k
k
k
i
j
i
i
j
m
j
k
m
k
m
m
j
j
j
m
m
k
i
i
i
k
k
a
x
x
a
a
x
a
x
x
x
a
a
• wagi operandów (1-bitowych iloczynów) mog by ujemne
→ wystarczy zmieni znaki wag wej i wyj niektórych sumatorów
• zast pienie sumatorów FA realizuj cych dodawanie x +y +z= 2c +s
układami odejmuj cymi FS (x
−y −z= −2c +s) lub FS
D
(x
+y −z= 2c −s)
• struktura logiczna FS i FS
D
identyczna
• przeciwne wagi wej i wyj , bo
x
−y −z= −(z+y −x) oraz −(2c −s) = −2c + s
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
10
Matryca mno
ca kodu uzupełnieniowego
HS
HA
HA
HA
FS
FS
FA
FA
FS
FS
FS
FA
FS
FS
FS
FS
FS
FS
FS
HS
x
0
x
1
x
2
x
3
x
4
a
4
a
2
a
1
a
3
a
0
s
0
s
1
s
3
s
2
s
4
s
5
s
6
s
7
s
8
s
9
(
• – wej cia o ujemnej wadze)
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
11
Konstrukcja matrycy mno
cej
• negowanie bitów najwy szego iloczynu cz ciowego (dopełnianie),
• dodanie stałych koryguj cych
1
2
−
k
i –
1
2
−
+m
k
oraz
1
2
−
m
(uzupełnianie)
(1) 0 0 0
1
1
♦ o o o o o o o
♦ o o o o o o o
♦ o o o o o o o
♦ o o o o o o o
(
♦– negacja najbardziej znacz cego bita operandu, o – negacja bita)
• koryguj ca „1” na pozycji k–1 (2
k
–1
) ⇒ s + 1 = 2c
+
+ s* ⇒ s* = 1
⊕s, c
+
= s
• dodanie 2
m
–1
– modyfikacja półsumatora pozycji m–1 w pierwszej linii
x
+ y + 1 = 2c
+
+ s ⇒
y
x
s
⊕
=
,
y
x
c
+
=
+
lub
y
x
s
⊕
=
,
y
x
c
⋅
=
+
• dodanie –2
n+l
–1
– korekcja przeniesienia z najwy szej pozycji iloczynu ,
zgodnie z zale no ci c
–
+ 1 = 2c
+
+ s, czyli c
+
= c
–
oraz s = 1
⊕c
–
• matryca kwadratowa (k = m) – (2
k
–1
+2
k
–1
=2
k
) ⇒ korekcja na pozycji k
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
12
Matryca mno
ca kodu uzupełnieniowego
HA
HA
HA
HA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
FA
x
0
x
1
x
2
x
3
x
4
a
4
a
2
a
1
a
3
a
0
s
0
s
1
s
3
s
2
s
4
s
5
s
6
s
7
s
8
s
9
c
9
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
13
Charakterystyki matryc mno
cych
zło ono
(mno nik m-bitowy, mno na k-bitowa)
• A = 8(m–1)k (dodatkowa bramka AND na ka dy akumulowany bit)
• T= 3(m–1)+ T
CPA
(k)
≥ 3m+ 2logk–1
(odpowiednie ł czenie poziomów daje opó nienie 6 na dwóch poziomach)
podatno na przetwarzanie potokowe
(pipelining)
• dla danej pary operandów w danej chwili jest wykonywane dodawanie
tylko na jednym poziomie układu matrycowego,
• na innych poziomach mo na w tym samym czasie wykona wcze niejsze
lub pó niejsze fazy mno enia innych par operandów
• niezb dne rozbudowanie o dodatkowe układy transmituj ce wyniki
dodawania na mniej znacz cych pozycjach oraz układ synchronizacji.
• przepustowo układu zale y od szybko ci ko cowego dodawania
w seryjnym mno eniu ko cowy CPA jako kaskada CSA
szybko bliska szybko ci dodawania 1-bitowego!
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
14
Optymalne ł czenie poziomów CSA w matrycy mno
cej*
s
#
c
#
s
#
c
#
a
0
x
i
c
i
+1
a
1
x
i
a
2
x
i
a
0
x
i
+1
a
1
x
i
+1
opó nienie przez 2 poziomy – (2+4) lub (4+2), czyli zawsze 6
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
15
Realizacja przekodowania Bootha-McSorleya w matrycy*
• mo liwe zastosowanie algorytmu Bootha/McSorleya
a
v
+1
x
r
+1
x
r
x
r
–1
a
v
s
r
+v
FA
s
r
+v+2
r
= 2i + p, v = j + p
( p = 0 – prosty)
( p = 1 – alternatywny)
• „brak podwojenia” = x
r
⊕x
r
–1
,
• „odejmowanie” = x
r
+1
,
• „brak zerowania” = (x
r
⊕x
r
+1
) + (x
r
⊕x
r
–1
),
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
16
Strukturalizacja układów mno
cych
• układ mno cy kn× kn – zło enie układów mno cych n× n:
∑
∑
∑
∑
∑
∑
−
=
−
+
−
=
−
−
=
=
−
−
=
−
=
+
=
=
2
2
1
1
1
0
0
1
0
1
0
2
2
2
2
k
k
j
k
k
j
i
i
j
i
jn
k
j
j
i
i
j
i
jn
k
s
sn
s
k
s
sn
s
X
A
X
A
X
A
AX
,
albo w postaci skróconej
∑
∑
−
=
−
+
−
=
−
=
2
2
0
)
1
,
min(
)
1
,
0
max(
2
k
j
k
j
k
j
i
i
j
i
jn
X
A
AX
gdzie
∑
−
=
+
=
1
0
2
n
j
j
j
ni
i
a
A
,
∑
−
=
+
=
1
0
2
n
j
j
j
ni
i
x
X
.
wyrównywanie
(alignment)
• ka dy 2n-pozycyjny iloczyn
i
s
i
X
A
−
ma wag
s
n
2
]
,
,...,
,
[
)
(
0
1
1
1
1
0
s
s
s
s
s
X
A
X
A
X
A
X
A
−
−
=
AX
• efekt – akumulacja 2k−1 wielooperandów ró nego rozmiaru
zamiast k
2
operandów o identycznej wielko ci
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
17
Wyrównanie operandów
2
7n
2
6n
2
5n
2
4n
2
3n
2
2n
2
n
2
0
0
3
X
A
1
3
X
A
0
2
X
A
2
3
X
A
1
2
X
A
0
1
X
A
3
3
X
A
2
2
X
A
1
1
X
A
0
0
X
A
3
2
X
A
2
1
X
A
1
0
X
A
3
1
X
A
2
0
X
A
3
0
X
A
Wyrównanie operandów w układzie mno
cym 4n
×4n
• w kodzie U2 i U1 – niezb dne uwzgl dnienie rozszerzenia znakowego
efekt – liczba operandów w j-ej grupie wynosi 2j
+1 osi gaj c maksimum 4k−3,
→ niweczy to zysk wynikaj cy ze strukturalizacji.
→ przekonstruowanie sumatora wielooperandowego CSA.
Szybkie mno enie
© Janusz Biernat
, AK1-8-09-Sumatory CSA i multyplikatory.doc
FAM–
18
Mno enie wielokrotnej precyzji
Mno enie liczb dodatnich
• bezpo rednie zastosowanie schematu wyrównania
Mno enie długich liczb znakowanych (U2)
• najwy sze iloczyny (... A
H
X
#
oraz A
#
X
H
)
– mno enie liczby dodatniej przez znakowan !
– dodawanie dodatniej i znakowanej !
Rozwi zanie 1:
• przekodowanie na dodatnie (podobnie jak w mno eniu bez rozszerze )
• korekcja (podobnie jak w mno eniu bez rozszerze )
Rozwi zanie 2:
• przekodowanie na warto ci bezwzgl dne
• mno enie dodatnich i wytworzenie znaku
• przekodowanie iloczynu na kod uzupełnieniowy