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