2006 szybkie mnozenie

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–1

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–2

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)

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–3

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)

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–4

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–5

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–6

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–7

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–8

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–9

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)

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–10

Algorytm Baugha-Wooley’a

zamiana ujemnych iloczynów cz ciowych na dodatnie:

+

+

=

=

+

+

=

1

2

0

1

2

1

2

0

1

1

2

2

)

1

(

2

2

2

m

k

i

m

i

i

m

k

m

k

i

i

i

m

m

a

x

a

x

,

+

+

=

=

+

+

=

1

2

0

1

2

1

2

0

1

1

2

2

)

1

(

2

2

2

k

m

j

k

j

j

m

k

k

m

j

j

j

k

k

x

a

x

a

.

korekcyjne dodawanie argumentów:

(1–a

k–1

) 2

k+m–2

+ a

k–1

2

k–1

2

k+m–1

+ (1–x

m–1

) 2

k+m–2

+ x

m–1

2

m–1

a

4

(1–x

0

)

a

3

x

0

a

2

x

0

a

1

x

0

a

0

x

0

a

4

(1–x

1

)

a

3

x

1

a

2

x

1

a

1

x

1

a

0

x

1

a

4

(1–x

2

)

a

3

x

2

a

2

x

2

a

1

x

2

a

0

x

2

a

4

(1–x

3

)

a

3

x

3

a

2

x

3

a

1

x

3

a

0

x

3

(1–a

4

)

a

4

1

(1–x

3

)

x

3

s

8

s

7

s

6

s

5

s

4

s

3

s

2

s

1

s

0

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–11

Akumulacja iloczynów cz ciowych w kodzie U2

Poniewa

=
=

=
=

+

+

=

+

2

0

1

1

1

2

0

1

1

2

2

)

1

(

2

2

2

p

i

i

i

i

p

p

p

p

i

i

i

i

p

p

z

z

z

z

,

wi c ka dy iloczyn cz ciowy 2

i

x

i

A mo na zast pi przez:

bł d!!

)

(

1

2

0

1

1

2

2

]

2

)

(

2

))

(

1

[(

2

i

i

m

i

m

j

j

j

j

i

m

m

i

i

i

A

a

x

a

x

A

x

+

+

=
=

+

=

+

=

Iloczyn mo na wi c obliczy jako (

0

gdy

0

;

1

gdy

)

(

=

=

=

=

i

i

j

i

j

i

j

x

x

a

x

a

a

):

=

+

+

+

=

=

=

=

2

0

1

1

2

0

2

0

1

1

1

1

1

2

2

2

2

2

2

k

j

j

i

j

k

i

k

m

i

i

k

j

j

m

j

k

m

k

m

x

a

x

a

x

a

x

a

X

A

+

+

+

=

=

=

=

=

1

2

0

)

(

1

)

(

1

2

0

2

0

2

0

)

1

(

1

)

1

(

1

1

2

2

2

)

1

(

2

2

2

)

1

(

2

2

k

k

j

j

i

j

k

i

k

m

i

i

k

j

j

k

j

j

m

j

k

m

k

m

a

a

a

a

,

Ostatecznie otrzymujemy:

1

1

2

0

2

0

)

(

1

)

(

1

2

0

)

1

(

1

)

1

(

1

1

2

2

2

2

)

1

(

2

1

2

)

1

(

2

2

+

=

=

=

+

+

+

+

+

=

k

m

k

m

i

k

j

j

i

j

k

i

k

i

k

j

j

m

j

k

m

k

m

a

a

a

a

X

A

czyli:

1

2

0

)

(

)

1

(

1

1

2

2

)

~

(

2

2

=

+

+

+

+

+

+

=

k

m

i

i

i

m

m

k

m

A

A

AX

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–12

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

13

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

14

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 + 2 log k–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!

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

15

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

16

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

),

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

17

Matryca z przekodowaniem Bootha-McSorleya

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

18

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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

19

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.

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

20

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

3

X

#

oraz A

#

X

3

)

– 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

background image

Szybkie mno enie

© Janusz Biernat, 11-06-Szybkie mnozacze.doc

FAM–

21

Mno enie U2 – jeszcze inne przekodowanie

Zast pienie ujemnych iloczynów w

+

+

=

=

2

0

1

1

2

0

1

1

2

2

2

2

m

j

j

j

m

m

k

i

i

i

k

k

x

x

a

a

1

2

0

1

1

2

2

0

1

1

2

0

1

1

2

2

)

1

(

2

2

2

2

=

+

+

=

+

=

+

+

=

=

m

k

i

m

i

m

i

m

k

k

i

m

i

m

i

k

i

i

i

m

m

x

a

x

a

a

x

,

1

2

0

1

1

2

2

0

1

1

2

0

1

1

2

2

)

1

(

2

2

2

2

=

+

+

=

+

=

+

+

=

=

k

m

j

k

j

j

k

m

k

m

j

k

j

j

k

m

j

j

j

k

k

x

a

x

a

x

a

,


Wyszukiwarka

Podobne podstrony:
2004 szybkie mnozenie
Szybkie mnożenie pałeczki Napiera, matematyka, zabawy matematyczne(1)
2006 szybkie sumatory
Załącznik nr1 do strzelania szybkiego nr 15 w dniu 03 08 2006 2
puchar swiata 2006 www prezentacje org
Gospodarka płynami kwiecień 2006
Znaki taktyczne i szkice obrona, natarcie,marsz maj 2006
Prowadzenie kliniczne pacjentów z dobrym widzeniem M Koziak 2006
prezentacja cwiczen 2006

więcej podobnych podstron