Modular exponentiation of matrices on FPGA-s

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