雙精度浮點(diǎn)矩陣乘法器的fpga實(shí)現(xiàn)

雙精度浮點(diǎn)矩陣乘法器的fpga實(shí)現(xiàn)

實(shí)時(shí)矩陣法的計(jì)算具有重要的工程實(shí)際意義。這是系統(tǒng)中最重要的操作，具有實(shí)時(shí)預(yù)處理和實(shí)時(shí)數(shù)字預(yù)處理的復(fù)雜性（通常為o（ni））。計(jì)算性能直接影響整個(gè)系統(tǒng)的性能。例如，在應(yīng)用模型預(yù)測控制（pmc）時(shí)，最大且最耗時(shí)的部分是矩陣法。在模型輸出電壓模型c的系統(tǒng)中，矩陣中的元素通常是兩個(gè)精度的浮點(diǎn)的數(shù)量，計(jì)算的實(shí)時(shí)性要求非常高。pc機(jī)和ps（數(shù)字日志處理器）的計(jì)算無法滿足系統(tǒng)的需要。雙向?qū)崟r(shí)浮點(diǎn)矩陣法的性能已成為該系統(tǒng)實(shí)際應(yīng)用的瓶頸。此外，在這些系統(tǒng)中，許多參與乘法計(jì)算的矩陣中都包含稀疏矩陣。如何使用稀疏矩陣的特點(diǎn)來提高計(jì)算的性能也是一個(gè)重要的實(shí)際工程意義。近年來，現(xiàn)場編程門矩陣（f）裝置的最高計(jì)算性能和平均值計(jì)算性能超過了通用軟件。當(dāng)f型矩陣法的硬件速度轉(zhuǎn)換為最佳選擇時(shí)，這是當(dāng)前的一個(gè)熱點(diǎn)研究問題。目前,使用FPGA實(shí)現(xiàn)矩陣乘法計(jì)算的研究已經(jīng)取得了一些成果.在定點(diǎn)矩陣乘法方面,Amira等人在FPGA上實(shí)現(xiàn)了8位定點(diǎn)數(shù)的矩陣乘法.該設(shè)計(jì)的一個(gè)主要缺點(diǎn)是其所需要的I/O帶寬與矩陣的規(guī)模成比例增加,限制了該設(shè)計(jì)的可擴(kuò)展性.Jang等人提出了一個(gè)基于FPGA的定點(diǎn)矩陣乘法算法,該算法只需要固定的I/O帶寬,但每個(gè)計(jì)算單元內(nèi)部的所需的存儲單元大小與問題規(guī)模是成比例的.在浮點(diǎn)矩陣乘法方面,Zhuo等人提出了在FPGA中實(shí)現(xiàn)矩陣乘法的2種并行算法,并針對這2種算法進(jìn)行了性能分析比較.對于不同規(guī)模的矩陣乘法問題,該設(shè)計(jì)可通過對FPGA的重配置來實(shí)現(xiàn).但是配置文件大、重配置時(shí)間長是該設(shè)計(jì)的一個(gè)主要缺陷.Dou等人給出一個(gè)線性排布的計(jì)算單元結(jié)構(gòu)來實(shí)現(xiàn)矩陣乘法,并且設(shè)計(jì)了一個(gè)雙精度浮點(diǎn)乘加器單元,提高了計(jì)算性能.Campbell等人提出了一個(gè)各個(gè)計(jì)算單元之間不存在任何通訊的并行矩陣乘法器結(jié)構(gòu),但其所需要的存儲空間隨著矩陣維數(shù)的增加而增加,并且矩陣乘法器的效率較低.在稀疏矩陣與向量的乘法方面,也已有一些研究成果,但以上所有成果都無法對稀疏矩陣之間的乘法進(jìn)行優(yōu)化.本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)具有較高的計(jì)算性能、且有良好的可擴(kuò)展性的基于FPGA的實(shí)時(shí)雙精度浮點(diǎn)矩陣乘法器,并針對工程應(yīng)用中普遍存在的稀疏矩陣乘法進(jìn)行了優(yōu)化.通過不同維數(shù)的稠密矩陣乘法及稀疏矩陣乘法的仿真實(shí)驗(yàn),證實(shí)本設(shè)計(jì)達(dá)到了較高的計(jì)算性能.1計(jì)算ci對于矩陣乘法C=A×B,其中A、B和C分別為M×L、L×N和M×N維矩陣,其計(jì)算方法為Ci,j=∑k=1LAi,k×Bk,jCi,j=∑k=1LAi,k×Bk,j;1≤i≤M,1≤j≤N.上述算法的計(jì)算復(fù)雜性為2×M×L×N,即為O(n3).根據(jù)此算法,本文了設(shè)計(jì)一個(gè)包含P×P個(gè)處理單元(processingelement,PE)的并行雙精度浮點(diǎn)矩陣乘法器來降低計(jì)算復(fù)雜性,并針對稀疏矩陣乘法的特點(diǎn)進(jìn)行了優(yōu)化.設(shè)計(jì)中所涉及的所有操作數(shù)均為符合IEEE754-1985標(biāo)準(zhǔn)的64位雙精度浮點(diǎn)數(shù).1.1浮點(diǎn)加法器計(jì)算ab+cPE是構(gòu)成浮點(diǎn)矩陣乘法器的基本單元.每個(gè)PE中包含一個(gè)浮點(diǎn)乘加單元和一個(gè)用于存儲計(jì)算結(jié)果的存儲單元,其結(jié)構(gòu)如圖1所示.圖1中a和b是浮點(diǎn)乘法器的2個(gè)64位輸入,a和b的乘積結(jié)果作為浮點(diǎn)加法器的一個(gè)輸入.c是一個(gè)64位存儲單元,用于存儲當(dāng)前乘加操作的中間結(jié)果,并為浮點(diǎn)加法器提供另一個(gè)輸入.當(dāng)輸入a和b都有效后,乘加器開始計(jì)算a×b+c;當(dāng)計(jì)算結(jié)束時(shí),輸出信號Valid被置為有效,Output輸出計(jì)算結(jié)果.同時(shí),計(jì)算結(jié)果也被存入存儲單元c,以備下次乘加操作使用.當(dāng)需要開始計(jì)算一個(gè)新的元素時(shí),將輸入信號New_OP置為有效,乘加器會將原有的計(jì)算結(jié)果和存儲單元c的值清0,重新開始進(jìn)行乘加計(jì)算.1.2基于pe單元的并行矩陣乘法器假設(shè)在FPGA芯片中可以實(shí)現(xiàn)P2個(gè)PE單元,根據(jù)矩陣乘法的簡單并行算法,將這些PE單元排列成如圖2所示的P×P陣列形式.在進(jìn)行C=A×B的矩陣乘法時(shí),輸入矩陣A和B分別按列和按行輸入到PE陣列.在陣列中,同一行的所有PE單元共用一個(gè)矩陣A的輸入數(shù)據(jù);而同一列的所有PE單元共用一個(gè)矩陣B的輸入數(shù)據(jù).每個(gè)PE單元除本身包含一個(gè)存儲中間結(jié)果的存儲單元外,在矩陣乘法器中還為每個(gè)PE配置了一個(gè)存儲最終結(jié)果的存儲單元.這樣可以使得主處理器在讀出本次乘法計(jì)算結(jié)果的同時(shí),矩陣乘法器可以進(jìn)行下次乘法計(jì)算,提高了乘法器的計(jì)算效率.通過這種PE的陣列結(jié)構(gòu),可以完成任意維數(shù)的矩陣乘法計(jì)算.假設(shè)2個(gè)相乘的矩陣A和B分別為M×L和L×N維矩陣,對任意的M、L和N值,可通過下述算法計(jì)算結(jié)果矩陣C:從以上算法可以看出,使用并行矩陣乘法器進(jìn)行計(jì)算時(shí),前2層循環(huán)的次數(shù)分別是傳統(tǒng)串行算法的1/P,即計(jì)算復(fù)雜性下降為O(n3/P2).同時(shí)由于該并行矩陣乘法器設(shè)計(jì)中的各個(gè)PE單元相對獨(dú)立,可以方便地?cái)U(kuò)展到多片F(xiàn)PGA并行計(jì)算的結(jié)構(gòu).當(dāng)系統(tǒng)的計(jì)算性能需要提高時(shí),可以通過增加矩陣乘法器的個(gè)數(shù)來實(shí)現(xiàn).1.3預(yù)處理模塊設(shè)計(jì)在多數(shù)實(shí)際工程應(yīng)用中,參與矩陣乘法計(jì)算的輸入矩陣中包含有稀疏矩陣.因此,增加矩陣乘法器對稀疏矩陣的支持,提高稀疏矩陣的計(jì)算效率也顯得更為重要.為實(shí)現(xiàn)這一目標(biāo),本設(shè)計(jì)在上述矩陣乘法器前增加一個(gè)預(yù)處理模塊,結(jié)構(gòu)如圖3所示.預(yù)處理模塊主要完成以下功能:1)針對稀疏矩陣中包含零元素較多的特點(diǎn),避免零元素塊參與計(jì)算以縮短計(jì)算時(shí)間.預(yù)處理模塊首先將當(dāng)前要計(jì)算的矩陣塊所對應(yīng)的輸入矩陣的元素值依次讀入.一旦當(dāng)前讀入A的一列值或者B的一行值都為0,即跳過此次計(jì)算,繼續(xù)讀入A下一行和B下一列的值;否則,將當(dāng)前讀入的值排入計(jì)算隊(duì)列后,再繼續(xù)讀入后續(xù)元素.2)將計(jì)算隊(duì)列中的數(shù)值依次送入矩陣乘法器進(jìn)行計(jì)算.該預(yù)處理模塊能夠避免零元素塊的計(jì)算,從而減少了稀疏矩陣乘法中一些無效的計(jì)算.同時(shí),在乘法器進(jìn)行計(jì)算時(shí),預(yù)處理模塊可以同時(shí)進(jìn)行輸入數(shù)據(jù)的讀取并將非零元素排入計(jì)算隊(duì)列,最大限度地減少矩陣乘法器的空閑時(shí)間,提高計(jì)算效率,使得矩陣乘法器能夠保持較高的平均計(jì)算性能.2fpga控制器設(shè)計(jì)下面以在FPGA上實(shí)現(xiàn)的并行矩陣乘法器來對上述設(shè)計(jì)的性能進(jìn)行分析.在本文中,選用XilinxVirtex-4SX55芯片來實(shí)現(xiàn)該設(shè)計(jì).PE單元中的浮點(diǎn)乘法器和加法器使用Xilinx公司提供的FloatingPointIP核實(shí)現(xiàn).通過對該器件中DSP48單元、CLB單元等資源進(jìn)行綜合考慮,選定矩陣乘法器中PE單元的個(gè)數(shù)為5×5.本設(shè)計(jì)中所使用的FPGA開發(fā)環(huán)境和仿真環(huán)境為XilinxISEFoundation8.2i及MentorGraphicsModelsim6.1f.2.1fpga內(nèi)部資源在理想情況下,每個(gè)PE單元在一個(gè)時(shí)鐘周期內(nèi)可以完成一次雙精度浮點(diǎn)乘法操作和一次雙精度浮點(diǎn)加法操作,因此整個(gè)矩陣乘法器的計(jì)算性能可由下式得出:PERFpeak=2×P2×f.式中:PERFpeak表示乘法器峰值計(jì)算性能(每秒百萬次浮點(diǎn)操作),P2為PE單元的個(gè)數(shù),f為乘法器工作頻率.通過綜合、布局布線等步驟在XC4VSX55FPGA上實(shí)現(xiàn)該設(shè)計(jì),FPGA內(nèi)部資源使用情況如表1,圖4所示為FPGA中2個(gè)DSP48單元及一些Slice單元布線后的結(jié)果.根據(jù)布線后仿真的結(jié)果,該矩陣乘法器在未作優(yōu)化的情況下工作頻率可達(dá)60MHz.由此得出,該設(shè)計(jì)的峰值雙精度浮點(diǎn)計(jì)算性能可以達(dá)到3000MFLOPS.目前業(yè)界最強(qiáng)大的浮點(diǎn)DSP,AnalogDevice公司的TigerSHARCTS201,所能達(dá)到的單精度浮點(diǎn)峰值計(jì)算能力為3600MFLOPS,而雙精度浮點(diǎn)計(jì)算由于DSP硬件并不直接支持,計(jì)算能力已經(jīng)遜色于在FPGA上實(shí)現(xiàn)的矩陣乘法器.2.2算法性能分析矩陣乘法器的平均計(jì)算性能可以通過2個(gè)稠密矩陣相乘的計(jì)算時(shí)間來獲得,如下式所示:PERF=F/t.式中:PERF表示矩陣乘法器平均計(jì)算性能,F為雙精度浮點(diǎn)操作次數(shù),t為計(jì)算時(shí)間.本文分別通過2個(gè)100×100的矩陣相乘和2個(gè)200×200的矩陣相乘的計(jì)算實(shí)例來進(jìn)行分析,結(jié)果如表2所示.在稠密矩陣乘法計(jì)算中,若FPGA的I/O帶寬小于一定值,矩陣乘法器中的計(jì)算單元會出現(xiàn)空閑狀態(tài),帶寬成為制約計(jì)算性能的因素;當(dāng)I/O帶寬達(dá)到或者高于這個(gè)值后,矩陣乘法器計(jì)算性能則被每個(gè)PE單元的計(jì)算能力所制約.在本文的設(shè)計(jì)中,只要I/O帶寬達(dá)到2.4GByte/s,便不會對整個(gè)矩陣乘法器的計(jì)算性能有所影響.由表2可以看出,本文中設(shè)計(jì)的矩陣乘法器的稠密矩陣平均計(jì)算性能可以保持在峰值計(jì)算性能的50%左右.而當(dāng)今的DSP和通用微處理器在進(jìn)行稠密矩陣乘法計(jì)算時(shí),平均浮點(diǎn)計(jì)算性能通常只能保持在其峰值的10%～33%.由此可以看出在平均計(jì)算性能方面,基于FPGA的設(shè)計(jì)也已經(jīng)超越了DSP和通用微處理器.2.3稀疏矩陣計(jì)算時(shí)域內(nèi)雙密度估計(jì)的結(jié)果本設(shè)計(jì)中的預(yù)處理電路由于能夠避免0元素塊參與計(jì)算,縮短了矩陣計(jì)算所需的時(shí)間.對于不同的稀疏矩陣,能夠縮短的計(jì)算時(shí)間是不同的,這主要取決于矩陣本身的稀疏程度、矩陣內(nèi)部非零元素的排布方式及矩陣乘法器所能達(dá)到的I/O帶寬.以2個(gè)100×100矩陣相乘為例,首先假定其中的輸入矩陣A為一個(gè)對角陣,其計(jì)算時(shí)間結(jié)果如表3所示.由于在稀疏矩陣計(jì)算中,矩陣乘法器中的計(jì)算單元經(jīng)常處于空閑狀態(tài),不會成為制約計(jì)算性能的瓶頸,而I/O帶寬成為制約性能的主要因素.由表3中的數(shù)據(jù)可以看出,若A為對角陣,則當(dāng)FPGA的峰值I/O帶寬達(dá)到9.6GByte/s時(shí),矩陣乘法器的計(jì)算時(shí)間僅為稠密矩陣乘法計(jì)算時(shí)的31.7%,大大縮短了計(jì)算時(shí)間.對于其他非零元素隨機(jī)排布的稀疏矩陣,根據(jù)其稀疏程度和FPGA峰值I/O帶寬的不同,也能夠縮短一定的計(jì)算時(shí)間.同樣以2個(gè)100×100的矩陣相乘為例,輸入矩陣A為一個(gè)稠密矩陣,輸入矩陣B為具有如圖5所示隨機(jī)排布的含有1052個(gè)非零元素的稀疏矩陣,N為維數(shù),其計(jì)算時(shí)間結(jié)果如表4.由表中實(shí)驗(yàn)結(jié)果可以看出,對于稠密矩陣相乘,矩陣乘法器內(nèi)部的乘加器計(jì)算單元為制約計(jì)算性能的瓶頸,因此對I/O帶寬的要求并不是很高.而在稀疏矩陣相乘時(shí),只要能適當(dāng)提高矩陣乘法器輸入的I/O帶寬,本文中提出的設(shè)計(jì)結(jié)構(gòu)就能夠大大提高稀疏矩陣乘法的計(jì)算性能.3在其他稀疏矩陣中進(jìn)行并行計(jì)算的設(shè)計(jì)筆者設(shè)計(jì)了一個(gè)矩陣乘法器,并在XilinxXC4VSX55FPGA上進(jìn)行了實(shí)現(xiàn).通過實(shí)驗(yàn)分