Szybkie mno enie
Schematy przy pieszonego mno enia
x0 A x0 A
x1 A
x1 A
CSA
x2 A
x2 A
x3 A
CSA
x3 A
CSA
CSA
CPA
CPA
akumulacja równoległa akumulacja sekwencyjna
" akumulacja równoległa  drzewiasta struktura CSA,
" akumulacja sekwencyjna  liniowa struktura CSA, matryca mno ca
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 1
 Szybkie mno enie
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)
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 2
 Szybkie mno enie
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)
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 3
 Szybkie mno enie
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
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 4
 Szybkie mno enie
Matrycowe układy mno ce  schemat mno enia
a4 a3 a2 a1 a0
x4 x3 x2 x1 x0
×
a4x0 a3x0 a2x0 a1x0 a0x0
+ a3x1 a2x1 a1x1 a0x1
a4x1 s41 s31 s21 s11
c41 c31 c21 c11
+ a3x2 a2x2 a1x2 a0x2
a4x2 s52 s42 s32 s22
c52 c42 c32 c22
+ a3x3 a2x3 a1x3 a0x3
a4x3 s63 s53 s43 s33
c63 c52 c42 c32
+ a3x3 a2x3 a1x3 a0x3
a4x3 s74 s64 s54 s44
+ c74 c64 c54 c44
s9 s8 s7 s6 s5 s4 s3 s2 s1 s0
sji oraz cji  sumy i przeniesienia na pozycji j w i-tym kroku akumulacji
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 5
 Szybkie mno enie
Matryca mno ca kodu naturalnego (Brauna)
a4x0 a3x0 a2x0 a1x0 a0x0
CSA
a3x1 a2x1 a1x1 a0x1
HA HA HA HA
a4x1
CSA
a3x2 a2x2 a1x2 a0x2
FA FA FA FA
a4x2
a3x3 a2x3 a1x3 a0x3
FA FA FA FA
a4x3
CSA
a3x4 a2x4 a1x4 a0x4
FA FA FA FA
a4x4
FA FA FA HA
CPA
p9 p8 p7 p6 p5 p4 p3 p2 p1 p0
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 6
 Szybkie mno enie
Multiplikator Brauna (Braun multiplier)
a4 a3 a2 a1 a0
x0
s0
x1
HA HA HA HA
s1
x2
FA FA FA FA
s2
x3
FA FA FA FA
s3
x4
FA FA FA FA
s4
FA FA FA HA
s9 s8 s7 s6 s5
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 7
 Szybkie mno enie
Matrycowe układy mno ce kodu U2
iloczyny cz ciowe lub iloczyny elementarne mog by liczbami ujemnymi
m-2
öÅ‚
ëÅ‚- ak-12k-1 + k-2 2i öÅ‚
j
ìÅ‚- xj 2 =
÷Å‚
ìÅ‚ ÷Å‚
"a Å‚Å‚ Å" ëÅ‚ xm-12m-1 + "
i
íÅ‚ i=0 j=0
íÅ‚ Å‚Å‚
m-2 k-2 m-2 k-2
ëÅ‚ öÅ‚
ëÅ‚-
j
= xm-1ak-12m+k-2 + xjai 2i+ j + ak-12k-1 xj 2 + xm-12m-1 i 2i öÅ‚.
ìÅ‚- ÷Å‚
ìÅ‚ ÷Å‚
" " " "a Å‚Å‚
j=0 i=0 j=0 íÅ‚ i=0
íÅ‚ Å‚Å‚
" 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 FSD (x+y-z=2c-s)
" struktura logiczna FS i FSD identyczna
" przeciwne wagi wej i wyj , bo
x-y-z=-(z+y-x) oraz -(2c-s)=-2c+s
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 8
 Szybkie mno enie
Matryca mno ca kodu uzupełnieniowego
a4 a3 a2 a1 a0
x0
s0
x1
HS HA HA HA
s1
x2
FS FS FA FA
s2
x3
FS FS FS FA
s3
x4
FS FS FS FS
s4
FS FS FS HS
s9 s8 s7 s6 s5
("  wej cia o ujemnej wadze)
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 9
 Szybkie mno enie
Algorytm Baugha-Wooley a
zamiana ujemnych iloczynów cz ciowych na dodatnie:
k -2 k-2
- xm-12m-1 i 2i = xm-1ëÅ‚- 2k+m-2 +
ìÅ‚ ÷Å‚
"a "(1- ai )2i+m-1 + 2m-1 öÅ‚,
i=0 íÅ‚ i=0 Å‚Å‚
m-2 m-2
ëÅ‚
j j+k -1 -1
- ak -12k -1 j 2 = ak -1 2k +m-2 + ÷Å‚
ìÅ‚-
"x "(1- x )2 + 2k öÅ‚.
j
j=0 j=0
íÅ‚ Å‚Å‚
korekcyjne dodawanie argumentów:
(1 ak 1) 2k+m 2+ak 1 2k 1
2k+m 1 + (1 xm 1) 2k+m 2+xm 1 2m 1
a4(1 x0) a3x0 a2x0 a1x0 a0x0
a4(1 x1) a3x1 a2x1 a1x1 a0x1
a4(1 x2) a3x2 a2x2 a1x2 a0x2
a4(1 x3) a3x3 a2x3 a1x3 a0x3
(1 a4) a4
1 (1 x3) x3
s8 s7 s6 s5 s4 s3 s2 s1 s0
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 10
 Szybkie mno enie
Akumulacja iloczynów cz ciowych w kodzie U2
i= p-2 i= p-2
Poniewa - zp-12p-1 + zi 2i = -2p-1 + (1- zp-1)2p-1 + zi 2i ,
" "
i=0 i=0
wi c ka dy iloczyn cz ciowy 2i xi A mo na zast pi przez:
j=m-2
j (
bł d!! 2i xi A = [(1- (xiam-1))2m-1 + (xiaj )2 ] = -2i+m-1 + 2i A+i)
"
j=0
Iloczyn mo na wi c obliczy jako (a(ji) = ajxi = a gdy xi =1; 0 gdy xi = 0):
j
k -2 m-2 k -2
ëÅ‚
j i -1 j
AÅ" X = -2m-1 ak -1xm-12k -1 + ÷Å‚ ìÅ‚- ÷Å‚
ìÅ‚-
"a xm-12 öÅ‚ + "2 ëÅ‚ ak xi 2k + "a xi 2 öÅ‚ =
j -1 j
j=0 i=0 j=0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
k-2 k-2 m-2 k-2
ëÅ‚
( j j i ( (i) j
= 2m-1 akm1-1) 2k-1 + ÷Å‚ ìÅ‚ ÷Å‚
ìÅ‚
"(1- a(jm-1))2 - "2 öÅ‚ + "2 ëÅ‚(1- aki-)1)2k-1 + "a 2 - 2k-1 öÅ‚,
- j
j=0 j=0 i=0 j=0
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Ostatecznie otrzymujemy:
k -2 m-2 k -2
Å„Å‚ üÅ‚ Å„Å‚ üÅ‚
( -1) j i ( ) -1 (i) j
A X = 2m-1òÅ‚akm1 2k -1 + 2 + 2k -1 - 2m+k -1
òÅ‚(1- żł
- "(1- a(jm-1) )2 +1żł + "2 ół aki-1)2k + "a j
j=0 i=0 j=0
ół þÅ‚ þÅ‚
czyli:
m-2
~(
(
AX = -2m+k -1 + 2m-1(-A+m-1)) + 2i A+i) + 2k -1
"
i=0
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 11
 Szybkie mno enie
Konstrukcja matrycy mno cej
" negowanie bitów najwy szego iloczynu cz ciowego (dopełnianie),
" dodanie stałych koryguj cych 2k -1 i  2k +m-1 oraz 2m-1 (uzupełnianie)
1
(1) 0 0 0 1
o o o o o o o
f&
o o o o o o o
f&
o o o o o o o
f&
o o o o o o o
f&
(f& negacja najbardziej znacz cego bita operandu, o  negacja bita)
" koryguj ca  1 na pozycji k 1 (2k 1) Ò! s+1=2c++s* Ò! s*=1•"s, c+=s
" dodanie 2m 1  modyfikacja półsumatora pozycji m 1 w pierwszej linii
x+y+1=2c++s Ò! s = x •" y, c+ = x + y lub s = x •" y , c+ = x Å" y
" dodanie  2n+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)  (2k 1+2k 1=2k) Ò! korekcja na pozycji k
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 12
 Szybkie mno enie
Matryca mno ca kodu uzupełnieniowego
a4 a3 a2 a1 a0
x0
s0
x1
HA HA HA HA
s1
x2
FA FA FA FA
s2
x3
FA FA FA FA
s3
x4
FA FA FA FA
s4
FA FA FA FA
c9 s9 s8 s7 s6 s5
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 13
 Szybkie mno enie
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)+TCPA(k)e" 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!
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 14
 Szybkie mno enie
Optymalne ł czenie poziomów CSA w matrycy mno cej
a2xi
a0xi
a1xi
c# s# c# s#
a1xi+1 a0xi+1
ci+1
opó nienie przez 2 poziomy  (2+4) lub (4+2), czyli zawsze 6
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 15
 Szybkie mno enie
Realizacja przekodowania Bootha-McSorleya w matrycy
" mo liwe zastosowanie algorytmu Bootha/McSorleya
sr+v av+1 av
xr 1
xr
xr+1
r = 2i + p, v = j + p
FA
( p = 0  prosty)
( p = 1  alternatywny)
sr+v+2
"  brak podwojenia = xr•"xr 1,
"  odejmowanie = xr+1,
"  brak zerowania = (xr•"xr+1)+(xr•"xr 1),
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 16
 Szybkie mno enie
Matryca z przekodowaniem Bootha-McSorleya
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 17
 Szybkie mno enie
Strukturalizacja układów mno cych
" ukÅ‚ad mno cy kn×kn  zÅ‚o enie ukÅ‚adów mno cych n×n:
j
k -1 k -1 k -1 2k -2 k -1
ëÅ‚
jn jn
AX = As 2sn öÅ‚ëÅ‚ X 2sn öÅ‚ = 2 Ai X + 2 Ai X ,
ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚
" " " " " "
s j-i j-i
íÅ‚ s=0 Å‚Å‚íÅ‚ s=0 Å‚Å‚ j=0 i=0 j=k i= j-k +1
albo w postaci skróconej
min( j,k -1)
2k -2
jn
AX = 2 Ai X
" "
j-i
j=0 i=max(0, j-k +1)
n-1 n-1
j j
gdzie Ai = xni+ j 2 .
"a 2 , Xi = "
ni+ j
j =0 j=0
wyrównywanie (alignment)
" ka dy 2n-pozycyjny iloczyn Ai Xs-i ma wag 2ns
(AX)s = [As X ,As-1 X1,...,A1 X ,A0 X ]
0 s-1 s
" efekt  akumulacja 2k-1 wielooperandów ró nego rozmiaru
zamiast k2 operandów o identycznej wielko ci
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 18
 Szybkie mno enie
Wyrównanie operandów
27n 26n 25n 24n 23n 22n 2n 20
A3 X
0
A3 X1 A2 X
0
A3 X2 A2 X1 A1 X
0
A3 X A2 X A1 X1 A0 X
3 2 0
A2 X3 A1 X A0 X1
2
A1 X A0 X
3 2
A0 X
3
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.
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 19
 Szybkie mno enie
Mno enie wielokrotnej precyzji
Mno enie liczb dodatnich
" bezpo rednie zastosowanie schematu wyrównania
Mno enie długich liczb znakowanych (U2)
" najwy sze iloczyny (... A3X# oraz A#X3)
 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
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 20
 Szybkie mno enie
Mno enie U2  jeszcze inne przekodowanie
k-2 m-2
öÅ‚
j
Zast pienie ujemnych iloczynów w ëÅ‚- ak-12k-1 + ìÅ‚- xj 2
÷Å‚
ìÅ‚ ÷Å‚
"a 2i öÅ‚ Å" ëÅ‚ xm-12m-1 + "
i
íÅ‚ i=0 Å‚Å‚ j=0
íÅ‚ Å‚Å‚
k-2 k-2 k-2
- xm-12m-1 i 2i = - xm-12i+m-1 = -2k +m-2 +
"a "a "(1- ai xm-1)2i+m-1 + 2m-1,
i
i=0 i=0 i=0
m-2 m-2 m-2
j j+k-1 +m-2 j+k -1
- ak -12k -1 xj 2 = -
" "a x 2 = -2k + "(1- ak x )2 + 2k-1,
k-1 j -1 j
j=0 j=0 j=0
© Janusz Biernat, 11-06-Szybkie mnozacze.doc FAM 21