Ac a Uni . Sapien iae, In o ma ica, 3, 2 (2011) 172–191
Modula exponen ia ion o ma ices on
FPGA-s
Tam´as HERENDI
Uni e si y o Deb ecen
email: [email p o ec ed]
Roland S´ando MAJOR
Uni e si y o Deb ecen
email: [email p o ec ed]
Abs ac . We desc ibe an e icien FPGA implemen a ion o he expo-
nen ia ion o la ge ma ices. The esea ch is ela ed o an algo i hm o
cons uc ing uni o mly dis ibu ed linea ecu ing sequences. The design
u ilizes he special p ope ies o bo h he FPGA and he used ma ices o
achie e a e y signi ican speedup compa ed o adi ional a chi ec u es.
1 In oduc ion
Field-p og ammable ga e a ays (FPGA) o e a numbe o special op ions in
compu a ion. U ilizing he unique p ope ies o an FPGA, some algo i hms
ha a e imp ac ical o implemen on a mo e adi ional a chi ec u e can be-
come bo h con enien o c ea e and esou ce-e icien . The p og ammable a -
ay o look-up ables commonly ound on an FPGA p o ide bo h lexibili y
in c ea ing logic o sui speci ic needs and na u ally lend hemsel es o g ea
pa allelism in compu a ions.
Fas ope a ions on ma ices a e o g ea p ac ical in e es . Ways o speed
up ce ain ma ix calcula ions s ill ind hei way in o nume ous applica ions.
Fas e implemen a ions o ma ix algo i hms can be achie ed ei he om a
“so wa e” poin o iew, by imp o ing upon he algo i hm i sel , o om a
Compu ing Classi ica ion Sys em 1998: B.2.4
Ma hema ics Subjec Classi ica ion 2010: 65F60 11Y55
Key wo ds and ph ases: pseudo andom numbe gene a o s, linea ecu ing sequences,
uni o m dis ibu ion, ma ix exponen ia ion, pa allel a i hme ic, FPGA design, ha dwa e
accele a ion o compu a ions, ha dwa e implemen a ion o compu a ions
172
Modula exponen ia ion o ma ices on FPGA-s 173
“ha dwa e” poin o iew, by using as e o di e en ly s uc u ed a chi ec-
u es.
Theo e ical imp o emen s on ma ix algo i hms include S assen’s algo-
i hm [12] and he Coppe smi h-Winog ad algo i hm [2]. The nai e algo i hm
o ma ix mul iplica ion is a well-known Θ(n3)algo i hm. S assen’s algo-
i hm uses an idea simila o he Ka a suba-mul iplica ion. I has a ime
complexi y o O(nlg 7)by di iding he ma ices in o sub-ma ices. Then by
mul iplying hem in a di e en a angemen , i manages an o e all lowe mul i-
plica ion coun compa ed o he classical algo i hm. Resea ch implemen ing i
on he Cell B oadband Engine can be ound in [5]. S assen’s algo i hm and i s
applicabili y o he p ojec is b ie ly discussed in Sec ion 7. The Coppe smi h-
Winog ad algo i hm u he imp o es he complexi y o O(n2.376)by combin-
ing he idea o S assen wi h he Salem-Spence heo em. [9] discusses and
compa es he pe o mance o implemen a ions o hese algo i hms.
Nume ous esea ch has been done on c ea ing e icien ealiza ions o di e -
en ma ix ope a ions on di e en a chi ec u es. [8] and [10] bo h use FPGAs
o pe o m ma ix in e sion.
The design p esen ed he e is an implemen a ion o ma ix mul iplica ion
on an FPGA. Wo ks o simila na u e can be ound in [1] and [4], dealing
wi h FPGA con igu a ions used o loa ing poin ma ix mul iplica ion. [11]
uses an FPGA design o digi al signal p ocessing. [3] discusses ano he FPGA
implemen a ion o accele a ing ma ix mul iplica ion.
The esea ch in his pape is ela ed o an algo i hm o he cons uc ion o
pseudo andom numbe gene a o s. I equi es he exponen ia ion o la ge ma-
ices o an ex emely high powe . This allows o nume ous op imiza ions o
be made on he FPGA implemen a ion, esul ing in an ex emely as design.
A speedup ac o o ∼200 is achie ed compa ed o a highly op imized p og am
on a mo e adi ional a chi ec u e.
We gi e he de ails o a design implemen ed on a Vi ex-5 XC5VLX110T
FPGA ha mul iplies wo 896 ×896 sized ma ices. The ma ices a e de ined
o e he mod 4 esidue class ing. Using his p ope y and he ac ha he
ha dwa e uses 6-LUTs (Lookup Tables), we desc ibe i s a module ha com-
pu es he do p oduc o ec o s aken om Z28
4in a single clock cycle a
100MHz clock speed. Wi h hese modules we cons uc a ma ix mul iplie
module ha compu es he C∈Z20×20
4p oduc ma ix o A∈Z20×28d
4and
B∈Z28d×20
4in dclock cycles a 100MHz. The signi icance o he alue 28
in he implemen a ion and i s expe imen al de e mina ion is also discussed.
Finally, we desc ibe how o use hese modules o mul iplying ma ices aken
om Z896×896
4. The p oposed algo i hm deals wi h he managemen o s o ed
174 T. He endi, R. Majo
da a in such a way ha i can be accomplished comple ely in pa allel wi h
he compu a ions. The esul ing design comple es he mul iplica ion in 64800
clock cycles a 100MHz.
Fu u e wo k o inc easing he size o he used ma ices, and u he op i-
mizing he design’s pe o mance using S assen’s algo i hm is also desc ibed.
2 Ma hema ical backg ound
The p esen wo k is ini ia ed by a me hod o he cons uc ion o uni o mly
dis ibu ed pseudo andom numbe gene a o s. (See [7].) The gene a o uses
ecu ing sequences modulo powe s o 2 o he o m
un≡ad−1un−1+ad−2un−2+· · · +a0un−dmod 2s, ai∈{0, 1, 2, 3}, s ∈Z+
The heo e ical backg ound can be ound in [6].
The cons uc ion assumes ha he alues a0, a1,...,ad−1a e such ha
xd−ad−1xd−1−· · · −a0≡(x−1)2P(x)mod 2
holds o some P(x)i educible polynomial. I is p ac ical o choose P(x) o
ha e maximal o de , since he o de o Pis closely ela ed o he pe iod leng h
o he co esponding ecu ing sequence. The sequence unob ained his way
does no necessa ily ha e uni o m dis ibu ion, howe e exac ly one o he
ollowing ou sequences does:
u(0)
n≡ad−1u(0)
n−1+ad−2u(0)
n−2+· · · +a1u(0)
n−d+1+a0u(0)
n−dmod 2s
u(1)
n≡ad−1u(1)
n−1+ad−2u(1)
n−2+· · · +a1u(1)
n−d+1+ (a0+2)u(1)
n−dmod 2s
u(2)
n≡ad−1u(2)
n−1+ad−2u(2)
n−2+· · · + (a1+2)u(2)
n−d+1+a0u(2)
n−dmod 2s
u(3)
n≡ad−1u(3)
n−1+ad−2u(3)
n−2+· · · + (a1+2)u(3)
n−d+1+ (a0+2)u(3)
n−dmod 2s.
Fo he de ails see [7]. Finding he sequence wi h uni o m dis ibu ion is o
in e es . Le
M(u) =







0 1 . . . 0 0
.
.
..
.
.....
.
..
.
.
0 0 . . . 1 0
0 0 . . . 0 1
a0a1. . . ad−2ad−1







Modula exponen ia ion o ma ices on FPGA-s 175
be he companion ma ix o sequence u. To ind which o he abo e se-
quences has a uni o m dis ibu ion, we ha e o compu e M(u)2d+1−2mod 4.
I M(u)2d+1−2mod 4equals he iden i y ma ix, hen he pe iod leng h o un
is 2d+1−2, which means i is no he sequence we a e sea ching o .
The exponen ia ion o ma ices o high powe s can quickly become ime
consuming on adi ional compu e s. The aim o he p ojec was o u ilize
he special p ope ies o an FPGA o achie e a signi ican upg ade in speed
compa ed o implemen a ions on mo e adi ional a chi ec u es.
3 Ha dwa e used in he implemen a ion
The p ojec was implemen ed on a Xilinx XUPV505-LX110T de elopmen
pla o m. The boa d ea u es a a ie y o po s o communica ion wi h he
de ice. As a i s app oach he RS-232 se ial po was used o send da a
be ween he boa d and a PC. A high-speed PCI Exp ess connec ion is also
a ailable i he amoun o da a ans e ed would necessi a e i s use.
The boa d’s mos p ominen ea u e is he Vi ex-5 XC5VLX110T FPGA.
The FPGA’s main ool o compu a ion is he a ay o 6-inpu look-up ables,
a anged in o 17280 Slices, wi h ou look-up ables ound in each Slice, adding
up o a o al o 69120 LUTs. A single 6-inpu LUT can s o e 64 bi s o da a,
whe e i s six inpu bi s a e used as an add ess o iden i y he single bi o da a
ha is o be ou pu ed. By manipula ing he 64 bi con en o he look-up
able, i can be con igu ed o ca y ou a bi a y Boolean unc ions wi h a
mos six inpu bi s. In ou design hey a e used o c ea e LUTs pe o ming
a mul iply-accumula e unc ion, which a e hie a chically a anged in o la ge
and mo e complex modules. One ou o ou LUTs on he de ice can also be
used as a 32 bi deep shi egis e ; hese a e he basis o implemen con aine s
s o ing he da a, which is di ec ly ed o he compu a ional module.
A ached o he boa d, he e is a 256MB DDR2 SODIMM module, which
is used o s o ing da a exceeding he amoun ha can be p ac ically s o ed
on he FPGA.
4 S uc u e o modules used in he compu a ion
The basic elemen s o he design a e he LUTs deno ed by L(a, b, s) = c, whe e
a, b, c and sa e wo-digi bina y numbe s. The unc ion ca ied ou by Lis a
mul iply-accumula e ( o sho : MA) unc ion, i.e.:
c≡(a·b) + smod 4 .
176 T. He endi, R. Majo
Le a=2α1+α0,b=2β1+β0,s=2σ1+σ0,c=2γ1+γ0, whe e
α0, α1, β0, β1, σ0, σ1, γ0, γ1∈{0, 1}, and L= (l1, l0)whe e l1and l0a e wo
single bi LUTs, acco ding o he ollowing:
•l0(α0, β0, σ0) = γ0
•l1(a, b, s) = γ1
Figu e 1: The s uc u e o L(a, b, s)
We ema k ha while l0needs only h ee inpu bi s o accomplish i s unc-
ion, l1 equi es all six bi s o inpu .
The LUTs l0and l1we e con igu ed o he alues shown in Table 1 and
Table 2 o pe o m he mul iply-accumula e unc ion.
PPPPPPPP
P
(α0, β0)
σ00 1
(0,0) 0 1
(0,1) 0 1
(1,0) 0 1
(1,1) 1 0
Table 1: Con en s o l0
Wi h he help o hese basic uni s one can compu e he do p oduc wo
wo ec o s u= (u0, u1,...,un−1)and = ( 0, 1,..., n−1). Le us de ine a
module m= (L[0], L[1],...,L[n−1]) by cascading nMA uni s deno ed by L[i].
In his module mwe use he ou pu o a gi en MA uni as he sum inpu o
he nex uni , i.e. si+1=ci o i=0, 1, . . . , n −2, whe e siand cia e he s
inpu and cou pu o L[i].
The e o mis a unc ion ha accep s a pai o ec o s u, o wo-digi
numbe s o leng h nand ou pu s on cn−1 he wo-digi do -p oduc o he wo
ec o s, i.e. m(u, ) = w.

Modula exponen ia ion o ma ices on FPGA-s 177
PPPPPPPP
P
(a, b)
s0123
(0,0) 0 0 1 1
(0,1) 0 0 1 1
(0,2) 0 0 1 1
(0,3) 0 0 1 1
(1,0) 0 0 1 1
(1,1) 0 1 1 0
(1,2) 1 1 0 0
(1,3) 1 0 0 1
(2,0) 0 0 1 1
(2,1) 1 1 0 0
(2,2) 0 0 1 1
(2,3) 1 1 0 0
(3,0) 0 0 1 1
(3,1) 1 0 0 1
(3,2) 1 1 0 0
(3,3) 0 1 1 0
Table 2: Con en s o l1
Figu e 2: The s uc u e o m(u, )
In o al, he numbe o LUTs used in mis 2n. No e ha ec o s o a bi a y
leng h can be used in he compu a ion i we connec he ou pu o module m
o he sum inpu o L[0](cn−1=s0), and hen i e a i ely shi uand on o
he module’s inpu by nelemen s a a ime:
178 T. He endi, R. Majo
Func ion i e a ed m(u, )// k=leng h(u) = leng h( )
1. De ine κ=dk
ne, 0, u0∈Zκ·n
4
2. o i=0 o κ·n−1do // ill and uwi h 0’s
3. i i<k hen 0
i= ielse 0
i=0
4. i i<k hen u0
i=uielse u0
i=0
5. end o
6. De ine emp, u emp, w, le w=0
7. o i=0 o κ−1do // shi 0and u0 o emp and u emp
8. emp = ( 0
i·n, 0
1+(i·n),..., 0
n−1+(i·n))
9. u emp = (u0
i·n, u0
1+(i·n),...,u0
n−1+(i·n))
10. w=w+m( emp, u emp)
11. end o
12. e u n w
end Func ion
He e u0and 0a e he ex ensions o uand by 0’s.
We shall see ha he numbe chosen o nis c i ical in se ing many cha -
ac e is ics o he en i e p ojec . The expe imen used o de e mining nwill
be discussed in he ollowing chap e .
Ou aim is o ob ain a module ha pe o ms he ma ix mul iplica ion o
A, B ∈Zk×k
4, whe e Z4is he mod 4 esidue class ing. In he ollowing, le
C∈Zk×k
4be he ou pu ma ix, such ha C=A×B. Fu he mo e, le aibe
he i h ow o ma ix Aand le bjbe he j h column o ma ix B.
The mul iplie uni s deno ed by ma e used o c ea e mo e complex mod-
ules in a hie a chical manne . Fi s , by aking en mmul iplie blocks we
c ea e a ow o mul iplie s R= (m0, m1,...,m9). This is used o compu e en
consecu i e elemen s o a single ow o he ou pu ma ix:
R(ai, bj, bj+1,...,bj+9)=(ci,j, ci,j+1,...,ci,j+9),
whe e ci,j =ai·bj. The inpu ec o aiis used by all en mul iplie uni s o R.
The leng h o hese ec o s, as men ioned abo e, can be a bi a y, bu ec o s
o leng h g ea e han nwill need o be i e a i ely shi ed o he inpu o R.
By aking en ow mul iplie s we can c ea e a uni M10×10 = (R0, R1,...,R9)
which ou pu s a 10 ×10 sub-ma ix o C:
Modula exponen ia ion o ma ices on FPGA-s 179
M10×10(ai, ai+1,...,ai+9, bj, bj+1,...,bj+9) =





ci,j ci,j+1· · · ci,j+9
ci+1,j ci+1,j+1· · · ci+1,j+9
.
.
....
ci+9,j ci+9,j+1· · · ci+9,j+9





.
Finally, ou such uni s a e a anged so ha a 20 ×20 sub-ma ix o Ccould
be ob ained as ou pu :
M20×20(ai, ai+1,...,ai+19, bj, bj+1,...,bj+19) =





ci,j ci,j+1· · · ci,j+19
ci+1,j ci+1,j+1· · · ci+1,j+19
.
.
....
ci+19,j ci+19,j+1· · · ci+19,j+19





.
The M20×20’s inpu s a e wen y ec o s om bo h ma ices Aand B. Because
o ha dwa e cons ain s — in pa icula he numbe o LUTs on he used de ice
— a la ge a angemen o mul iplie s would be imp ac ical o implemen . The
module M20×20 is comp ised o 400 mmul iplie uni s. Figu e 3 shows he
hie a chy o uni s used o build M20×20.
Figu e 3: The s uc u e o M20×20
The M20×20 uni can be used i e a i ely o mul iply ma ices o a bi a y
size, p oducing 20×20 sub-ma ices o he ou pu ma ix Cwi h each i e a ion.
A e inpu ing wen y ows om ma ix Aand wen y columns om ma ix
Band ob aining he desi ed ou pu , we can simply epea he p ocess o a
180 T. He endi, R. Majo
se o ows and columns o Aand B espec i ely, un il we ob ain he en i e
ou pu ma ix C:
Func ion la ge ma ix mul (A, B)
1. De ine κ=dk
20 e,A0, B0, C0∈Zκ·n×κ·n
4
2. o i=0 o 20κ −1do
3. o j=0 o 20κ −1do
4. i i<kand j < k a0
ij =aij else a0
ij =0
5. i i<kand j < k b0
ij =bij else b0
ij =0
6. end o end o
7. o i=0 o κ−1do
8. o j=0 o κ−1do
9. C0[i,j
i+19,j+19] = M20×20(ai, ai+1,...,ai+19, bj, bj+1,...,bj+19)
10. end o end o
11. e u n C0[0,0
k−1,k−1]
end Func ion
He e
C0[i,j
k,l] = 




c0
i,j c0
i,j+1· · · c0
i,l
c0
i+1,j c0
i+1,j+1· · · c0
i+1,l
.
.
....
c0
k,j c0
k,j+1· · · c0
k,l





.
No e ha in he nai e algo i hm la ge ma ix mul (A, B), du ing he main
loop (lines 7-10), o each wen y ows ead om A, he en i e ma ix Bis ead.
Du ing he whole p ocedu e, ma ix Awill be ead en i ely exac ly once, while
ma ix Bwill be ead κ imes. Me hods imp o ing on his numbe a e desc ibed
in sec ion 6.
Since o almos all p ac ical cases he size ko ma ices A, B ∈Zk×k
4will be
g ea e han he pa ame e n, he ec o s aken om hese ma ices will need
o be i e a i ely shi ed on o he inpu o he mul iplie M20×20,nelemen s
a a ime. The e o e, an e icien way o bo h s o e and hen use he ec o s
aken om he ma ices is he c ea ion o FIFO ype con aine s made o shi
egis e s.
Le d
nbe a shi egis e o wid h nand dep h d. I means ha d
ncan s o e
a mos d ec o s o leng h n, o equi alen ly a single ec o o leng h a mos
nd. We choose dsuch ha nd ≥k, hus i can s o e one ow o column om
he inpu ma ices Ao B. Le he ec o illing d
nbe = ( 0, 1, . . . , d−1),
Modula exponen ia ion o ma ices on FPGA-s 187
New ows a e loaded in a a slowe pace han columns a e. By he ime all
columns a e ead once, he con en s o he ow-s o es ha e shi ed exac ly o
he nex segmen o da a needed, he nex (z−1)·20 ows. A e ma ix Bis
comple ely ead once, he ow-s o es a e illed wi h ows a(z−1)˙
20 →a2(z−1)·20−1.
Reading ows and columns p oceeds in his manne un il we’ e comple ely
ead ma ix Aonce. Fo his eason, i is p ac ical o choose zsuch ha
(z−1)|κ. All oge he we ead ma ix Bκ
z−1 imes and ma ix Aonce.
Du ing each z−1i e a ions shown in Figu e 6, wen y new columns and (z−1)·20
κ
new ows a e loaded in o he column-s o e and ow-s o e cu en ly unused by
he compu a ion. When he unused ow-s o e is illed wi h wen y new ows, i
becomes ac i e, o be used in he ollowing i e a ions. The ow-s o e con aining
he ows wi h he leas index becomes inac i e in he compu a ion and s a s
accep ing he new ows ead.
Figu e 7: P og ession o compu a ions h ough ma ix C
Func ion imp o ed ma ix mul (A, B)
1. De ine z, κ =dk
20 e,A0, B0, C0∈Zκ·n×κ·n
4
2. o i=0 o 20κ −1do
3. o j=0 o 20κ −1do
4. i i<kand j<k hen a0
ij =aij else a0
ij =0
5. i i<kand j<k hen b0
ij =bij else b0
ij =0
6. end o end o

188 T. He endi, R. Majo
7. Fill he ow-s o es wi h ows a0→a(z−1)·20−1
8. Fill he column-s o es wi h columns b0−b19
9. Fo i=1 o κ2
z−1
Do in pa allel: |pe o m z−1i e a ions o he compu a ion
|READ he nex 20 columns mod κ·20
|READ he nex (z−1)·20
κ ows mod κ·20
|WRITE he esul o he p e ious z−1i e a ions
11. e u n C0[0,0
k−1,k−1]
end Func ion
The possible alues o he pa ame e s used in his sec ion depend on he
used ha dwa e.
The size o he ma ices used in he implemen a ion a e de e mined by
pa ame e s n=28 and d=32. The LUTs on he de ice ha comp ise he Td
20n
con aine s can be con igu ed as d=32 bi deep shi egis e s. Fo his eason
he ma ices a e o size 896 ×896. Rows wi h leng h k=896 a e he la ges
ha can be s o ed in con aine s ha a e one LUT deep, making hem any
la ge would double he numbe o LUTs needed o c ea ing a Td
20n. Because
o he limi ed numbe o LUTs which can be used o s o age pu poses, z=10
was chosen. This yields ha wel e Td
20n con aine s a e de ined in he design.
Dealing wi h ma ices la ge han k=896 is pa o u u e wo k.
Fo con enience, ime quan i ies a e measu ed in clock cycles a 100MHz,
he clock speed o he M20×20 mul iplie .
The alue o δdepends on he DDR2 RAM used. The de ice was used a
200MHz, and has a 64 bi wide physical da a bus.
F om hese alues we de e mine he ollowing pa ame e s:
•κ=d896
20 e=45,
•K(imp o ed ma ix mul ) = κ
z−1κ+κ=45
9·45 +45 =270,
•δ=140 clock cycles a 100MHz,
•Φ(imp o ed ma ix mul ) = K(imp o ed ma ix mul )δ+κδ =270·
140 +45 ·140 =44100 clock cycles a 100MHz,
•Γ(imp o ed ma ix mul ) = dκ2=32 ·452=64800 clock cycles a
100MHz.
Modula exponen ia ion o ma ices on FPGA-s 189
The goal o Γ(imp o ed ma ix mul )> Φ(imp o ed ma ix mul )is a-
chie ed, meaning ha he unning ime o he design is equal o he ime used
by he compu a ion.
The speedup p o ided by he con igu a ion can be shown by compa ing i s
pe o mance o a simila implemen a ion c ea ed on a mo e adi ional a chi-
ec u e. A highly op imized C++ p og am was c ea ed o a machine using
an In el E8400 3GHz Dual Co e p ocesso wi h 2GB RAM. The algo i hm is
s ongly specialized o he ask, making use o all a ailable op ions o in-
c easing pe o mance. I uses 64 bi long a iables o pe o m mul iplica ion
on 16 pai s o wo-digi elemen s a once in pa allel on bo h p ocesso co es.
The unning ime o he mul iplica ion o ma ices o he same size is o e
100 ms. The FPGA implemen a ion, as men ioned abo e, achie es a un ime
o ∼0.6 ms. On a e age, a speedup ac o o 200 is eached using he desc ibed
FPGA design.
7 Fu u e wo k
The u u e cou se o esea ch will ocus on inc easing he size o he used
ma ices.
As men ioned in he p e ious sec ion, simply inc easing he dep h do he
Td
20n con aine s would be imp ac ical. Since a single LUT on he de ice can
only be con igu ed as a 32 bi deep shi egis e , se ing d > 32 would double
he numbe o LUTs needed o a Td
20n, and he design is al eady using well
o e hal o he de ice’s LUTs ha can be con igu ed his way (13440 ou o
17280, o be exac ). Inc easing he size o he ma ices his way would equi e
he es uc u ing o bo h he mul iplie module and he algo i hm used o
memo y managemen .
Ins ead, he cu en ly implemen ed module can be used as a basic uni o
he mul iplica ion o la ge ma ices. Then he en ies o he la ge ma ices
a e 896 ×896 blocks.
This also allows o u he op imiza ion using S assen’s algo i hm. Suppose
we double he ma ix sizes, in e p e ing hem as ma ices wi h ou blocks.
Using he classical algo i hm, mul iplying wo 1792×1792 sized ma ices would
ake eigh mul iplica ion o he blocks. Using a di ide-and-conque s a egy,
we can exchange one mul iplica ion o a ew ex a addi ions.
A11 A12
A21 A22·B11 B12
B21 B22=−D2+D4+D5+D6D1+D2
D3+D4D1−D3+D5−D7,
190 T. He endi, R. Majo
whe e
D1=A11(B12 −B22)
D2= (A11 +A12)B22
D3= (A21 +A22)B11
D4=A22(B21 −B11)
D5= (A11 +A22)(B11 +B22)
D6= (A12 −A22)(B21 +B22)
D7= (A11 −A21)(B11 +B12).
This algo i hm, wi h i s O(nlg 7) ime complexi y, could speed up he design on
la ge ma ices. We should no e howe e , ha he speed o he ex a addi ions
ha e o be ca e ully conside ed. Since he mul iplica ion is al eady ex emely
as , a simila imp o emen may also be necessa y o addi ions i he o e all
pe o mance upg ade is o emain signi ican .
Acknowledgemen s
Resea ch suppo ed by he T´
AMOP 4.2.1/B-09/1/KONV-2010-0007 p ojec
and TARIPAR3 p ojec g an N . TECH 08-A2/2-2008-0086.
Re e ences
[1] F. Bensaali, A. Ami a, R. So udeh, Floa ing-poin ma ix p oduc on
FPGA, IEEE/ACS In e na ional Con e ence on Compu e Sys ems and
Applica ions, Amman, Jo dan, 2007, pp. 466–473. ⇒173
[2] D. Coppe smi h, S. Winog ad, Ma ix mul iplica ion ia a i hme ic p o-
g essions, J. Symbolic Compu . 9, 3 (1990) 251–280. ⇒173
[3] N. Da e,K.Fleming, M. King, M. Pellaue , M. Vijaya agha an, Ha dwa e
accele a ion o ma ix mul iplica ion on a Xilinx FPGA, MEMOCODE
’07 P oc. 5 h IEEE/ACM In e na ional Con e ence on Fo mal Me hods
and Models o Co-Design, Nice, F ance, 2007, pp. 97–100. ⇒173
Modula exponen ia ion o ma ices on FPGA-s 191
[4] Y. Dou, S. Vassiliadis, G. K. Kuzmano , G. N. Gaydadjie , 64-bi
loa ing-poin FPGA ma ix mul iplica ion, P oc. 2005 ACM/SIGDA
13 h in e na ional symposium on Field-p og ammable ga e a ays, Mon-
e ey, CA, USA, 2005, pp. 86–95. ⇒173
[5] T. J. Ea nes , S assen’s Algo i hm on he Cell B oadband Engine, 2008,
h p://mc2.umbc.edu/docs/ea nes .pd ⇒173
[6] T. He endi, Uni o m dis ibu ion o linea ecu ences modulo p ime pow-
e s, J. Fini e Fields Appl. 10, 1 (2004) 1–23. ⇒174
[7] T. He endi, Cons uc ion o uni o mly dis ibu ed linea ecu ing se-
quences modulo powe s o 2 ( o appea ). ⇒174
[8] A. I u k, S. Mi zaei, R. Kas ne , An E icien FPGA Implemen a ion o
Scalable Ma ix In e sion Co e using QR Decomposi ion, UCSD Techni-
cal Repo , CS2009-0938, 2009. ⇒173
[9] B. Kaka ado , Ul a- as ma ix mul iplica ion, An empi ical analysis
o highly op imized ec o algo i hms, S an o d Unde g adua e Resea ch
Jou nal 3(2004) 33–36. ⇒173
[10] M. Ka koo i, J. R. Ca alla o, C. Dick, FPGA implemen a ion o ma ix
in e sion using QRD-RLS algo i hm, P oc. 39 h Asiloma Con e ence on
Signals, Sys ems, and Compu e s, Paci ic G o e, CA, USA, 2005, pp.
1625–1629. ⇒173
[11] S. M. Qasim, A. A. Telba, A. Y. AlMaz oo, FPGA design and implemen-
a ion o ma ix mul iplie a chi ec u es o image and signal p ocessing
applica ions, IJCSNS In e na ional Jou nal o Compu e Science and
Ne wo k Secu i y 10, 2 (2010) 168–176. ⇒173
[12] V. S assen, Gaussian elimina ion is no op imal, Nume . Ma h. 13 (1969)
354–356. ⇒173
Recei ed: May 17, 2011 •Re ised: Oc obe 11, 2011