基于FPGA多通道采樣系統(tǒng)設(shè)計論文資料
基于FPGA多通道采樣系統(tǒng)設(shè)計論文資料,基于,fpga,通道,采樣系統(tǒng),設(shè)計,論文,資料
畢業(yè)設(shè)計(論文)中期檢查表 系(部)填表日期: 年 月 日班 次 學(xué)生姓名 題目名稱基于FPGA多通道采樣系統(tǒng)設(shè)計題目來源教改、科研 結(jié)合生產(chǎn)實際 教師自選課題 實習(xí)單位課題題目類型理論研究 實驗研究 工程設(shè)計 工程技術(shù)研究軟件開發(fā)指導(dǎo)教師 工作地點(diǎn)校內(nèi):計算機(jī)系實驗室校外:設(shè)計時間年 月 日至 年 月 日工作量及難度太大大小適 中很 難較 難一 般簡 單題目價值實用價值題目推廣價值題目科研價值題目課題主要內(nèi)容利用所學(xué)的知識,設(shè)計、制作基于FPGA的多通道采樣系統(tǒng)。(1)八通道采集,其中至少包括一路音頻信號;(2)采樣速率大于44.1KHZ;(3)12位采樣數(shù)據(jù);完成情況全部完成大部分完成完成一半大部分未完成存在困難1 系統(tǒng)工作不穩(wěn)定,在工作完一段時間會停止工作,需要重新配置才可以使芯片工作2 采樣后的數(shù)據(jù)輸出有問題解決辦法把AD的4條控制線重新焊接,可以解決系統(tǒng)工作穩(wěn)定的問題預(yù)期成績優(yōu) 秀良 好中 等及 格不及格建議 檢查教師簽名: 教務(wù)處實踐教學(xué)科制表說明:1、本表由檢查畢業(yè)設(shè)計的指導(dǎo)教師如實填寫;2、此表要放入畢業(yè)設(shè)計(論文)檔案袋中;3、各系分類匯總后報教務(wù)處實踐教學(xué)科備案。畢業(yè)設(shè)計(英文)資料翻譯院 (系) : 專 業(yè): 學(xué)生姓名: 學(xué) 號: 年 月 日高速FPGA器件的頂層設(shè)計 鳴謝在開始這份報告之前,我想感謝下面這些人,他們幫助我完成了這個項目,沒有他們的幫助,我是不可能完成這個項目。我要感謝我的主管韋力拉克教授,他在整個項目進(jìn)行中給了我很多的建議和鼓勵,他還告訴我也面對在項目中遇到的困難。我要感謝楊教授,他讓我運(yùn)用他的硬件運(yùn)算法則。他還給我說明的例子源文件好讓了解他的理論。我還要謝謝他卓越的多媒體的教程。這些多媒體教程包括了很多讓我明白圖像進(jìn)程原理的概念。我還要感謝阿塔夫和雪瑞。他們是兩個PHD的研究生,他們在項目執(zhí)行和應(yīng)用上幫了我很多。摘要在這個項目中,我發(fā)現(xiàn)了一個高質(zhì)量硬件設(shè)計的體系方法,有了這個方法,我成功地在高速硬件上運(yùn)行了一個經(jīng)典的凝膠圖像算法。在這份報告中,我還會提到一個新器件,這種新硬件可以通過重新排列代碼來自動完成高質(zhì)量的硬件優(yōu)化。這樣它可以運(yùn)行在最小的時鐘周期中。這份報告分為5個章節(jié)第一節(jié)是介紹:主要包括背景和所有相關(guān)的工作,還有一些我在這個項目上投資。第二節(jié)是優(yōu)化:在這一節(jié)中,我將著重描述用于優(yōu)化的新器件。我還將論證一些器件可以自動優(yōu)化的過程。第三節(jié)是硬件拓展:在這節(jié)中,我將歸納幾步改變一個軟件,然后下載到硬件中。這些包括許多能改進(jìn)性能或者保存硬件資源的器件。第四節(jié)是范例分析:凝膠圖像過程。在這節(jié)中,我將用凝膠圖像過程作為一個例子來說明在第二節(jié)中討論的硬件的資源和性能的影響。我還會比較兩種器件和軟件的應(yīng)用的性能,軟件的版本是:Pilchard 和 RC1000第五節(jié)是結(jié)論,包括評估成就和期望的特性工作網(wǎng)上也有這篇論文。網(wǎng)址:http:/www.doc.ic.ac.uk/mcn99/project/report.pdf第一節(jié):說明自從Handel-C5.a類C硬件語言的出現(xiàn),一個完全的頂層的FPGA設(shè)計方法就被認(rèn)識到。然而許多開發(fā)者當(dāng)他們要設(shè)計高速運(yùn)行的硬件的時候仍然停留在底層的語言上,比如VHDL這是因為開發(fā)者在底層的方法有許多實際電路的控制方法。但底層的設(shè)計在FPGA芯片規(guī)模逐漸變大的時候可能會達(dá)到極限。開發(fā)人員將不能用底層的設(shè)計來開發(fā)包括幾十億個門的高速電路。這個時候頂層的設(shè)計就可以達(dá)到要求了。這個項目的目的就是介紹一套系統(tǒng)的方法來設(shè)計頂層的高速硬件性能。1.1背景和相關(guān)工作在這節(jié)中,我將介紹一些材料來方便讀者了解這篇論文中的一些概念。1.1.1 現(xiàn)場可編程門陣列(FPGAs)1像許多的可變成邏輯器件(PLDs)一樣,FPGA是一塊可編程的硬件,然而, PLDs的資源消耗和時間延時限制了其大小。而FPGA可以很輕易在一塊集成芯片上設(shè)計一個有幾百萬個門的電路。FPGA的可再編程特性允許開發(fā)人員用比使用一塊VLSI芯片更少的開發(fā)時間和更少的開發(fā)成本來設(shè)計。值得一提的是FPGA以每年兩倍容量的發(fā)展。因為最新的芯片上有幾百萬個門,所以FPGA是開發(fā)復(fù)雜應(yīng)用的系統(tǒng)理想開發(fā)平臺。因此我在開發(fā)它的應(yīng)用。Pilchard 2Pilchard是一個基于現(xiàn)場可編程門陣列(FPGA)的可配置的計算平臺,它可以插在一臺標(biāo)準(zhǔn)的個人電腦的133MHZ同步的動態(tài)RAM和雙向存儲器模塊(DIMMS)的插槽中。相比于傳統(tǒng)的利用PCI接口的FPGA器件,由于DIMM接口的寬帶寬和低延時,Pilchard允許數(shù)據(jù)在更短的時間傳出電腦或者傳入電腦。然而由于DIMM接口原本不是設(shè)計為I/O接口的,所以需要額外的控制信號來表示數(shù)據(jù)讀寫過程的開始和結(jié)束。因此,由于Pilchard的發(fā)展和運(yùn)用,頂層的性能設(shè)計方法好過底層的結(jié)構(gòu)設(shè)計。這就證明了為什么一個用高性能的FPGA的頂層設(shè)計的系統(tǒng)方法是很有必要的。RC1000 3 RC1000是一個專為可配置的計算應(yīng)用的32的PCI卡,它以庫的形式全支持的程序包在適合這設(shè)備的電路設(shè)計,它在連在FPGA或者主CPU的板子還有4個SRAM(每個2M字節(jié)),這塊板子可以配置成可以運(yùn)行在4000KHZ到100MHZ的頻率中。這個器件在很多方面是不同于Pilchard的,在這份報告中,我將表明發(fā)展在這項目內(nèi)一般介紹,并且可能在應(yīng)用開發(fā)在不同設(shè)備上適用。1.1. 4 VHDL 4 VHDL是一門在當(dāng)今市場上最好的可編程邏輯器件設(shè)計語言,VHDL的頂層設(shè)計取決于他能讓設(shè)計者很快得將大型電路設(shè)計出來然后放到市場上。它可以用庫文件保存起來,以便以后的再應(yīng)用,由于VHDL是一門標(biāo)準(zhǔn)語言(IEEE標(biāo)準(zhǔn) 1076)。VHDL能像其他獨(dú)立器件設(shè)計一樣提供方便的代碼來同步和仿真,VHDL還很容易將一個可編程邏輯轉(zhuǎn)化為一個ASIC功能 。這門語言的缺點(diǎn)是還不夠高級,開發(fā)人員必須掌握組件的硬件特性。因此,我決定用另外一門更高級的硬件語言-i.e.Handel-C。1.1.5 Handel-C 5Handel-C是一門類似于C語言的編程語言,它可以用于將硬件圖像通過編程下載到FPGA或者ASICs中,Handel-C為了支持很少的硬件優(yōu)化而加入了一些在C中沒有的額外的特性。其中一個是這門語言支持指定每個信號的寬度,這樣優(yōu)化可以用Handel-C編譯的額外資源來完成優(yōu)化。Handel-C編譯的目的是為了能直接用xnf或者edif格式通過編程下載到硬件器件中。Handel-C好過VHDL的是它不需要開發(fā)人員掌握太多底層硬件知識,而VHDL必須要求掌握。它是一門完全的頂層設(shè)計語言!圖一顯示我采用的轉(zhuǎn)換Handel-C程序到硬件中,盡管每一步都需要很多工具,但用戶不需要了解硬件的細(xì)節(jié),因為用戶只需要點(diǎn)幾個按紐就可以轉(zhuǎn)換文件到下一步,就像這樣。圖1.1 Handel-C的設(shè)計流程Handel-C編程硬件比特流EDIF網(wǎng)格文件 編譯 布局和布線 下載1.1.6 Handel-C語言的擴(kuò)展 7一個PH.D的學(xué)生李東尤發(fā)明了一門支持硬件和軟件的語言,他的方法是把C和Handel-C綁在一起,在這門語言中,用戶可以指定哪個部分用于軟件,哪個部分用于硬件。在這個項目中,他還開發(fā)了很多友好的用語FPGA器件和主機(jī)的通信接口,然而支持這門語言的器件還相當(dāng)有限,這就是我為什么不選擇這門語言的原因。1.2 主要成就我已開發(fā)出一種簡單而有效的優(yōu)化方法,這種方法可以重新排列代碼,這樣可以運(yùn)行在最小時鐘周期。我已開發(fā)出針對高速器件設(shè)計出一個體系的頂層硬件設(shè)計流程我實現(xiàn)在硬件運(yùn)行復(fù)雜的2D凝膠圖像過程第二章 優(yōu)化在這章中,我將論述很多的方法來優(yōu)化頂層代碼,優(yōu)化是我們開發(fā)和運(yùn)用的主要部分,類似于由于有限的CPU資源而運(yùn)行的PC軟件。這一章的主要目標(biāo)放在怎樣自動優(yōu)化這些進(jìn)程,我們還將討論一些相等進(jìn)程,以便衡量優(yōu)化后速度到底提高了多少2.1 性能優(yōu)化這是在開發(fā)潛能類似于程序在相同時鐘周期運(yùn)行在不相矛盾的操作來獲得速度上的增加,在通常的運(yùn)用中,十幾或者幾百個操作在電腦上并行運(yùn)行,然而電腦因為硬件資源的有限是不能并行操作的。但是設(shè)計特殊的能并行操作的硬件是有可能的。重要是速度能達(dá)到。這就是為什么FPGA的應(yīng)用有時候比相應(yīng)運(yùn)行在低時鐘的FPGA的軟件(當(dāng)然我們也需要考慮到物價指數(shù),但是PC機(jī)的CPU仍然可以快速獨(dú)立地運(yùn)行)。這有我們可以運(yùn)用的技術(shù)。2.1.1 平衡每條路徑的延遲平衡每條路徑的延遲是很重要,因為硬件的時鐘最快也就是最長延時的那條路徑。因此因為如果有某一條路徑上延時十分嚴(yán)重,當(dāng)其他的路徑能夠以非常高的速度運(yùn)行的時候那么我們就浪費(fèi)資源。通過平衡延時能確保并行優(yōu)化是最理想的。一條路徑的延時定義為: = + (2.1)這里的是一條路徑的總延時; 是邏輯延時; 是線路上的延時因此,為了減少延時就是減少和的其中一個或者兩個都減少,這里有兩步主要步驟化復(fù)雜的操作為簡單的操作用一些預(yù)定義的組件和布線約束 化復(fù)雜的操作首先,最簡單的步驟是把復(fù)雜的步驟分成學(xué)多簡單的操作,這個步驟有效得減少了每一步的邏輯操作,因此減少了等式2.1中。在軟件編程中,復(fù)雜操作通常比相同結(jié)構(gòu)的簡單操作運(yùn)行要快甚至更快,這是因為編譯器會為我們優(yōu)化結(jié)構(gòu)操作。而硬件中,一個復(fù)雜的操作就意味著要用很長的時間來完成,而簡單操作就不需要很長的時間。圖2.1表明了把一個復(fù)雜的操作分成許多簡單的操作。在這個例子中,我們可以看出有時候額外的寄存器我們可以看出為了使操作足夠簡單,通過額外的寄存器把中間計算結(jié)果存起來是很有必要的。圖2.1:復(fù)雜操作的分解簡單操作int temp;temp=c*d; temp+=b; a+=tem p; 復(fù)雜操作a+= b+ c*d 預(yù)定義布置和布線組件如果第一種方法不能滿足用戶要求或者時序上的限制不能滿足,我們可以用FPGA芯片開發(fā)者提供的延時分析,來找出延時最長的一條線路。例如,我們可以用Xinlinx ISE Foundation 4的延時分析來分析Xinlinx公司的FPGA芯片,在找到最長的線路后,我們就知道哪個操作運(yùn)行太慢了。這個時候,我們就應(yīng)該試試這兩種方法來提高運(yùn)行速度。第一種方法是自己嘗試寫一個限制文件明確地布局和布線,這樣相比于一些不是很好的自動布局和布線的工具可以提高工作效率。然后我們可以在布局和布線之前把這些限制文件包括到進(jìn)程中。然而這種方法需要開發(fā)人員有相當(dāng)多FPGA芯片知識,這包括關(guān)于芯片支持的一些能減少延時的原始組件和布局布線之間的關(guān)系等方面的知識。第二種方法相比來說簡單一些,就是用一些預(yù)定義好的元器件來布局和布線,這些都是芯片開發(fā)人員做好的,簡單來說就是芯片開發(fā)人員已做好了,你只是調(diào)用就行了。就Xinlinx來說,他有一個叫做代碼生成器的編程軟件,他就像上面說的一樣可以直接調(diào)用的。Handel-C菜單中指定了怎樣把這些組件包括到Handel-C編程菜單中,然而用戶需特別注意這些組件的輸入和輸出的時序。由于Handel-C語言的局限性,輸入信號要晚一個周期進(jìn)入組件,這一步會減少等式2.1中,因為邏輯塊的較佳的布局和信號的布線會使延時明顯得減少。進(jìn)程自動的可能性以上,我們討論了兩種方法來達(dá)到這一步,這一步是很難實現(xiàn)自動,因為很難定義哪個操作是復(fù)雜的哪個不是,這取決于我們用到的器件和芯片還有程序的功能。我們需要一個嚴(yán)格時序限制的器件。一個16位的乘法器相比于其他不能運(yùn)行在高速的器件來說可以認(rèn)為是一個復(fù)雜的器件。當(dāng)一個操作不能運(yùn)行在高速環(huán)境上,再去把這個操作再去分成一些可以運(yùn)行在高速的分操作簡直是浪費(fèi)。然而我們可以再借用李的觀點(diǎn)來把這些操作實現(xiàn)自動化。當(dāng)編譯源文件的時候,我們可以包含我們要用的器件信息和時序限制,器件庫包含有每個邏輯單元的延時時間。它還包括FPGA開發(fā)工具怎樣對信號布線的信息。這樣編譯器可以估計每路的, ,,然后和限制的時序延時比較,如果不能達(dá)到,編譯器會用上面提到的第二種方法來平衡每路的延時,直到符合限制條件。2.1.2 基本的并行操作這是實際的性能優(yōu)化的最簡單的第一步,下面的操作可以使進(jìn)程自動化。連續(xù)掃描程序,盡量把更多的操作聯(lián)合在一個時鐘周期中,直到違背了資料相依的條件,然后在下一時鐘周期重復(fù)這樣的操作。因為我們已經(jīng)討論怎樣在更盡快的部分內(nèi)發(fā)現(xiàn)數(shù)據(jù)從屬性,這個過程可能被自動做。圖2.2是一個簡單的例子,我們看到如果沒有并行操作,將需要8個時鐘周期來完成8個操作,然而如果用并行操作,只需要2個時鐘周期就可以完成這些操作。 A=1; 操作1Par B=2; 操作2A=1;操作1 C=3; 操作3B=2;操作2 D=4; 操作4C=3;操作3 A=A+1; 操作5D=4;操作4 B=B+2; 操作6C=C+3; 操作7ParD=D+4; 操作8A=A+1;操作5操作5是依賴與操作1的,B=B+2;操作6但并不依賴操作1,操作2C=C+3;操作7操作3,操作4之間,就像D=D+4;操作8在操作5,操作 6,操作7操作8之間一樣。2.1.3 重新排列代碼順序有時候,一個程序可以有高度的并行性,但操作執(zhí)行的順序的方法在上面提到的。例如,圖2.3中的代碼是跟圖2.2中的代碼功能是一樣的,但如果我們用基本的并行操作,將需要4個時鐘周期來完成這個操作,而不是2個時鐘周期。我們有是可以通過重新排列代碼的順序,這樣程序可以運(yùn)行盡可能少的時鐘周期,例如上面代碼可以改成圖2.2一樣的順序,這樣我們又可以用“基本平行”方法。由于這些進(jìn)程可以被編譯器自動進(jìn)行,編譯器將需要有相當(dāng)多編程的知識和原因,我已研究出一個方法來實現(xiàn)這些進(jìn)程的自動化。1.首先,選擇一部分代碼開始, 最好在局部循環(huán)中。2.用變量名作為索引和標(biāo)簽來建一個空表,標(biāo)簽的格式是var:n,其中var是一個變量的名稱,n是指定的操作順序的個數(shù)。3.連續(xù)掃描代碼,對每一個變量的任務(wù)(任一修正/設(shè)定初值), 在下面被列出的規(guī)則之后分配標(biāo)簽到操作:第一步:查詢表格,找到標(biāo)注的變量的標(biāo)簽第二步(a)如果沒有發(fā)現(xiàn)入口,變量就是先前定義,把這個程序入口加入表格,內(nèi)容(標(biāo)簽)指定為as:形式。 第三步(a1)如果變量是一個常量或者是一個從外部輸入的信號量。指定其標(biāo)簽為VARname:1,這里的VARname是定義的變量名。 第三步(a2)如果變量的值取決于其他的變量,從表格中取出這些變量的標(biāo)簽,定義這些變量的標(biāo)簽從我們?nèi)〉米畲蟮拇涡蚣?得到。例如,如果 a=b + e,如果b是d:3,e是e:4,這樣a的標(biāo)簽應(yīng)該是e:5第二步(b)如果有程序入口,變量就是在前面已經(jīng)定義的,直接取得這些變量的標(biāo)簽。第三步(b)更新在第三步(a1)和第三步(a2)中改變了的變量標(biāo)簽,但是由于一個變化當(dāng)發(fā)現(xiàn)最大的次序標(biāo)簽的時候,我們應(yīng)該包括比較的它本身的標(biāo)簽。 舉例來說, 如果a = b+c 而c和b的標(biāo)簽是和上面的相同的,但是a的標(biāo)簽已存在表格中,值為a:5,這樣新的標(biāo)簽將會是a:6.注意在做比較的時候,我們要視常數(shù)的次序為0。第四步:用我們剛才指定的標(biāo)簽把這些操作連接起來。4.將所用的操作做了標(biāo)簽后,我們就要調(diào)整操作了,把有相同次序的操作放到一起。5.現(xiàn)在,“基本平行”方法將會回到運(yùn)行最少周期的程序代碼上了。相同次序的將會放到一個塊中。6.重復(fù)從第二步開始的各個步驟,直到整個程序都被轉(zhuǎn)換。這個方法的可行性是把所有的操作放到最近的一個時鐘周期執(zhí)行,這樣,經(jīng)過修改后的代碼只用最少的時鐘周期就可以執(zhí)行完成了。很顯然這種方法可以很容易實現(xiàn)自動化,通過聯(lián)合這種方法和前面的“基本平行”的方法,一個令人驚訝的效率很高的并行工作工具被發(fā)展! 圖2.4顯示出這種方法怎樣工作的例子圖2.3 未優(yōu)化代碼A=1; 周期1Par B=2; 周期2A=1;周期1 C=3; 周期3A=A+1; D=4; 周期4 A=A+1; 周期5Par B=B+2; 周期6B=1;周期2C=C+3; 周期7 B=B+2;D=D+4; 周期8 Par周期3C=3; C=C+3; Par周期4 D=4; D=D+4;圖2.4重新排列代碼的步驟2.1.4 增加寄存器來儲存中間結(jié)果僅僅通過重新排列代碼有時候是不夠的,如果我們發(fā)現(xiàn)有許多針對一個變量的操作,而其他的變量只有幾步的操作,這樣就會出現(xiàn)在前面幾個時鐘周期有很多的操作,而到了后面的時鐘周期卻沒有了幾步操作。這樣,我們能平衡每個時鐘周期的操作呢?可能解決這個問題的辦法就是增加寄存器來儲存中間結(jié)果,而且這樣可以在很短的時間計算中間變量的值,由于這需要很的理論和邏輯單元,而且這項操作很復(fù)雜,所以可以很難實現(xiàn)自動化操作。圖2.5是這種方法的一個例子,我們可以看到在修改代碼之前需要3個時鐘周期在修改程序后只需要2個時鐘周期。圖2.5 用存儲器來儲存中間變量2.1.5 流水線操作流水線操作是在一個操作中有多任務(wù)的時候一種執(zhí)行方法,亨利絲和帕得森在他們的書第三節(jié)是這樣介紹這個流水線操作的具體方法:流水線操作就像是一個裝配線,在一個自動裝配線上有許多步驟,每個步驟完成一個裝備小汽車的操作,盡管在不同的小汽車上,但每個步驟都是并行作業(yè)的。理想狀況下,我們可以在每個時鐘周期后來執(zhí)行下一個操作,這樣,流水線操作就是滿負(fù)載的,生產(chǎn)量在每個時鐘周期將會是一項任務(wù)不論它花多少時鐘周期來完成這項操作,因此,當(dāng)一個任務(wù)需要100個時鐘周期來完成,而且你有足夠多的任務(wù)來讓生產(chǎn)線一滿負(fù)荷,這樣將花大約100倍的時間來完成所有的任務(wù),但速度決定不會達(dá)到100,因為:流水線需要額外的控制邏輯,因此需要增加成本。流水線需要額外的寄存器來儲存中間變量,因此增加延時。此外,開發(fā)人員要知道操作不會在很段的時間就完成了,因此流水線操作是一個理想的相同的計算大數(shù)據(jù)操作。這有當(dāng)我們用流水線操作的時候必須注意到的幾點(diǎn):當(dāng)沒有足夠硬件資源來處理交錯的任務(wù)的時候,哈澤德式結(jié)構(gòu)就會發(fā)生。例如,我們不能在一個時鐘周期來多次來讀一個RAM里的數(shù)據(jù)。解決的方法是在流水線操作中確保有足夠多的硬件資源。因為你用的寄存器儲存的中間變量的值在每個周期可能會改變,所以寄存器中數(shù)據(jù)會丟失,除非你有足夠多寄存器來儲存中間變量。這樣,如果在一個流水線的一個狀態(tài)在很多狀態(tài)以后才用到,這樣我們就需要增加額外的寄存器來儲存和傳遞中間變量的值,這樣任務(wù)進(jìn)入一個新的狀態(tài)的時候,任務(wù)想要讀數(shù)據(jù)的數(shù)據(jù)就有數(shù)據(jù)可以讀。當(dāng)操作需要數(shù)據(jù)沒有準(zhǔn)備好,哈澤德式數(shù)據(jù)就會產(chǎn)生。當(dāng)進(jìn)入一個新的流水線操作的時候我們需要很小心設(shè)計流水線操作,以防止哈澤德式數(shù)據(jù)的產(chǎn)生。 圖2.6是一個把Handle-C程序轉(zhuǎn)換成流水線操作的例子,運(yùn)行的結(jié)果是數(shù)據(jù)輸入5階次方。 圖2.7顯示出上面例子的效果。 圖2.6 轉(zhuǎn)換為流水線操作圖2.7流水線的效果2.2 空間優(yōu)化空間優(yōu)化跟時間優(yōu)化完全不同,時間優(yōu)化通常是在同時用更多資源執(zhí)行更多的操作來獲得高速操作,而空間優(yōu)化關(guān)心是這樣用最少的資源來完成操作。這在FPGA設(shè)計中相當(dāng)重要,因為我們用的資源越少,我們可以在片子上有更多的操作。我們現(xiàn)在就來討論一些空間優(yōu)化的方法。2.2.1 變量的最佳寬度記住在4.1標(biāo)準(zhǔn)寬度中變量的轉(zhuǎn)化方向,事實上,如果我知道一個我們要用的值的上限和下限范圍,我們就會發(fā)現(xiàn)有些位在大多數(shù)情況是用不到的。例如:一個0-1024的變量就不需要用32位,11位的整型就足夠了。一個位數(shù)少的就只需要小的寄存器來儲存了。位數(shù)低的比位數(shù)高的相同操作需要更少的邏輯門,等式2.1中提到,是的一個組成部分,因此,這種優(yōu)化不僅節(jié)省了很多資源,還減少了,從而減少了?;始覍W(xué)院的學(xué)生阿塔夫正在研究這個項目8。這個項目主要的目標(biāo)是通過限定浮點(diǎn)型變量的最佳寬度來自動資源優(yōu)化。他的方法是仿真足夠多的數(shù)據(jù),然后通過統(tǒng)計學(xué)的原理來找出變量的最佳寬度。2.2.2 組件的再運(yùn)用如果相同寬度的不同操作數(shù)的相同操作在不同的時鐘周期中要運(yùn)行多次,我們就可以建立一個可以應(yīng)用于不同操作數(shù)組件。這種方法不影響電路的延時,但節(jié)省了復(fù)制組件的門!為了能更多的運(yùn)用這些組件,我們甚至可以放棄限制條件,這樣短操作數(shù)的操作可以運(yùn)用這寫共享組件。這是因為長操作很短操作是一樣的??赡苡幸蓡柺牵捎谟昧瞬⑿枰嗪芏噙壿媶卧獣黾与娐返难訒r。是的,原則上,我們可以用足夠的邏輯單元就會操作變快,然而FPGA器件并不支持不同操作不同時鐘,時鐘的頻率時最長那條路徑來決定,因此,共享組件對程序的影響不會很大。在Handel-C中,共享表達(dá)式可以很容易定義共享組件,圖2.8是這樣的一個簡單例子,想要了解更詳細(xì)的信息,參考Handel-C的用戶指南和DK1設(shè)計步驟是很有用的。圖2.8 Handel-C中的共享表達(dá)式2.3 評估 如果我們不知道估計結(jié)果,這樣就無法知道優(yōu)化是否達(dá)到效果,因此,在這節(jié)中,我們將討論有關(guān)估計的相關(guān)手法。我將給出一些等式,這樣,開發(fā)人員就可以對操作做出判斷。是否值得在硬件中編程?如果結(jié)果達(dá)不到預(yù)期結(jié)果,器件再高級點(diǎn)是否可以值得這樣做,或者可以想到能達(dá)到更高速度的其他方法。這些都是我們這節(jié)要回答的問題。2.3.1 等式 =+ + (2.2) 現(xiàn)在我們將介紹一些其他的等式來幫助我們估計結(jié)果。 假設(shè)硬件在執(zhí)行的過程中不需要經(jīng)常配置,這樣0因此,等式變?yōu)椋?= + (2.3)可以通過下面等式得: =n*t (2.4)這里的n時鐘的個數(shù),n是時鐘的延時T可以通過下面等式確定: t=1/c (2.5)這里c是時鐘頻率 因此 =n/c (2.6)n可以在電路編譯后的仿真中得到,c可以從延時報告中得到。同理我們可以得到 =w/b (2.7)這里的w是每項操作主機(jī)和FPGA芯片需要交換的字節(jié)數(shù),b是器件和PC機(jī)通信的接口的帶寬。 把連在一起得: =w/b+n/c (2.8)從這個等式中,我們可以看到優(yōu)化并不是只是減少時鐘的個數(shù)和提高時鐘的頻率,我們還要考慮到通信的數(shù)據(jù)量,有時候,高速并不因為你能很快傳遞數(shù)據(jù),而是因為很好傳遞數(shù)據(jù)的方法。例如:如果我們能很輕松處理數(shù)據(jù)以便數(shù)據(jù)在n操作只能被讀一次,然后每個操作中w等于o+i/n,這里o是輸出到主機(jī)的數(shù)據(jù)量,而i是從主機(jī)輸出的數(shù)據(jù)量。2.3 等式的推理我們知道軟件的,所以我們就可以知道期間是否可以達(dá)到我們想要的速度。如果不知道,我們將試著去推出來。1. 首先,w/b是比大一點(diǎn)嗎?如果是,不管硬件運(yùn)行多快,對整體的速度的提高一點(diǎn)用處都沒有,因為大部分的時間都用來傳遞數(shù)據(jù),除非你利用一個高帶寬的通信接口,這樣就不值得在硬件上執(zhí)行這個程序了。2. 假設(shè)c不變,w/b相對與相當(dāng)?shù)男?。例如:時鐘的頻率是不變的,計算n需要達(dá)到這個速度,這樣我們就應(yīng)該考慮更多的并行處理方法來達(dá)到這個周期數(shù)3. 如果你覺得不好處理n,那么就假設(shè)n是定值,這樣計算c是否可以提高速度,然后考慮當(dāng)前的方法是否可以運(yùn)行在這樣的速度上,如果你用更高級的芯片是否可以提高速度?;蛘吣闶欠衿谕隳苓\(yùn)行的速度的芯片進(jìn)入市場。4. 是否你的方法有局限性,例如:如果你讀同時存儲器中一個地址,可能你的方法能以10倍的速度運(yùn)行。5. 最后,你的程序是否可以在硬件的其他可以開發(fā)的并行執(zhí)行的位置執(zhí)行。2.4 小結(jié) 在這章中,我討論了很多優(yōu)化操作,我介紹了通過重新排列代碼來使你的的程序能并行執(zhí)行在最段的周期中,在后面,我介紹了優(yōu)化操作中很重要的一個計算等式,在等式中,我們了解到操作的執(zhí)行速度不僅跟FPGA芯片運(yùn)行速度和你能減少多少個時鐘周期,還跟怎樣減少FPGA芯片跟主機(jī)通信的資源有關(guān)。第三章:系統(tǒng)的頂層硬件設(shè)計在這章中,我將介紹這樣把軟件編程轉(zhuǎn)換到硬件的一般的5個步驟,我將在后面的幾個小節(jié)中具體介紹這5個步驟。3.1 設(shè)計步驟Handel-C中,開發(fā)人員把軟件編程轉(zhuǎn)換為硬件電路的一般步驟如圖3.1所示。如下所示:1. 第一步是編程分析,編程分析通常是確定程序中哪塊要轉(zhuǎn)換為硬件。這步是很重要的,因為這步?jīng)Q定了操作的最后結(jié)果,基本方法是找出一個程序哪一個部分重復(fù)執(zhí)行,因此這個部分的速度將很明顯影響整個電路的速度。2. 第二步是直接轉(zhuǎn)換,這一步是直接把軟件編程不優(yōu)化直接轉(zhuǎn)化到硬件電路中,這樣是為了確保硬件執(zhí)行結(jié)果能跟軟件一樣。3. 第三步是平衡延時,這是為了平衡硬件每個部分的延時,這一步很重要,因為硬件的時鐘延時會是每個通路的最長的那個延時,因此,如果某一個通路的延時比其他的都要長,這就意味著我們浪費(fèi)很多資源,因為其他的通路不能運(yùn)行在更高的速度。4. 第四步是優(yōu)化,一次運(yùn)用一種優(yōu)化算法是很重要的。應(yīng)用優(yōu)化算法后,我們就要看程序是否達(dá)到要求,如果沒有達(dá)到,就回到第三不,如果達(dá)到了,就繼續(xù)下面的第五步。5. 最后一步是估算,就是估計程序的硬件電路的實際結(jié)果,然后對下面的問題做一個結(jié)論。硬件是否提高了程序的運(yùn)行速度?如果沒有,在哪一塊能,我們可以用其他的方法來執(zhí)行這個程序嗎?等。我們可以看到最后3個步驟事實是我們前面討論的優(yōu)化,剩下的我們將在這章中討論。圖3.1 硬件開發(fā)步驟第一步:程序分析。確定程序哪個部分需要轉(zhuǎn)換第二步:把軟件不優(yōu)化直接轉(zhuǎn)化為硬件第三步:平衡每路的延時第四步:優(yōu)化,每次應(yīng)用一個優(yōu)化算法,檢查是否符合條件要求,如果不符合,回來第三步第五步:估計實際結(jié)果,寫結(jié)論3.2 編程分析在這一節(jié)中,我們將討論硬件頂層設(shè)計的第一步。程序分析是最五個步驟中最重要的一步,以為如果在硬件上選擇了錯誤的部分,那么對程序的影響將不會很明顯或者可以忽略。3.2.1 程序分析的四個指導(dǎo)原則 我研究出程序分析的四個指導(dǎo)原則,開發(fā)人員并不需要必須征尋,但可以給開發(fā)人員知道程序的哪個部分可以轉(zhuǎn)換。原則1:選擇重復(fù)執(zhí)行的部分原因很明顯,如果我們選擇在硬件中很少運(yùn)行的部分,盡管這個部分可以高速運(yùn)行,但對實際程序的運(yùn)行并不起很大的作用,因為它在硬件中很少執(zhí)行。我們最好選擇在有限的硬件中執(zhí)行程序的內(nèi)循環(huán)。然而,因為技術(shù)的提高,今天,隨著FPGA芯片的越來越大,集成的百萬個門和實時的在線配置,把整個程序都寫到硬件中都是有可能的。原則2:選擇數(shù)據(jù)依賴性小的模塊在硬件執(zhí)行的那部分程序是不能太依賴數(shù)據(jù),F(xiàn)PGA芯片一般是比PC機(jī)的CPU要慢一點(diǎn),這就為什么需要外加邏輯電路來配置FPGA器件。因此程序的并行操作才可以到達(dá)高速。太依賴數(shù)據(jù)將會減少并行的操作,因為這塊的數(shù)據(jù)取決于其他塊的數(shù)據(jù)將會影響程序的并行操作。原則3:選擇通信少的模塊 硬件執(zhí)行時間是 = + + (3.1) 這里的表示總的執(zhí)行時間表示重新配置的時間表示主機(jī)和FPGA芯片傳遞數(shù)據(jù)的時間表示實際的數(shù)據(jù)執(zhí)行時間從等式3.1可以看到,完成所有硬件操作的時間不但取決于數(shù)據(jù)執(zhí)行時間,而且還包括了FPGA芯片配置時間(),傳遞初始數(shù)據(jù)和從FPGA芯片中讀數(shù)據(jù)的時間(),如果我們不需要實時重新配置FPGA芯片,在我們第一次配置器件的時候,就是零,然而每次執(zhí)行程序的時候,就不會是零,總共的時間取決于主機(jī)和器件交換的數(shù)據(jù)量很交換的頻率。如果有大量的數(shù)據(jù)要傳送,當(dāng)Tcomm占Texec的大部分的時候,高速運(yùn)行可能就達(dá)不到。然而在某些情況下是有辦法來解決這個問題的。例如,如果在順序執(zhí)行的時候,大部分的數(shù)據(jù)是一樣的,我們在第一次操作后就把這些數(shù)據(jù)留在FPGA芯片中,這樣順序執(zhí)行的Tcomm包括在傳遞不同數(shù)據(jù)的時間中。原則4:如果可以,盡量避免浮點(diǎn)型的計算 眾所周知,PC機(jī)比FPGA芯片能更好得計算浮點(diǎn)型數(shù)據(jù),由于專用的CPU和很好并行硬件設(shè)計,所以推薦有CPU來處理浮點(diǎn)型數(shù)據(jù),盡管FPGA有支持浮點(diǎn)型數(shù)據(jù)計算的庫,但它不能像運(yùn)行整形數(shù)據(jù)計算那樣快,然而,現(xiàn)在有很多商業(yè)界,學(xué)術(shù)界都在研究這個操作,所以我可以預(yù)見這個原則過不了多久就用不上了。盡管這樣,我還是要推薦避免浮點(diǎn)型數(shù)據(jù)操作,如果開發(fā)人員碰到浮點(diǎn)型的計算,應(yīng)該試著考慮可否用整形數(shù)據(jù)計算來代替浮點(diǎn)型的計算。所有的硬件開發(fā)操作中,這些操作是最難實現(xiàn)自動完成的。因為這涉及到考慮程序到底是做什么的,因此很難找到一個實現(xiàn)自動的規(guī)則,然而,可以從現(xiàn)在的編譯器借鑒一些方法來使這一步簡單點(diǎn),例如:亨利絲和帕得森研究的編譯器的方法,從而發(fā)現(xiàn)數(shù)據(jù)依賴而且很有可能可以除去這中依賴性。3.3直接轉(zhuǎn)換在這節(jié)中,我們將看到開發(fā)過程的第二步。就是把軟件編程直接轉(zhuǎn)化成硬件語言,這一步不涉及任何優(yōu)化,把優(yōu)化留在后面是因為我們必須確保硬件編程能和軟件編程有同樣的結(jié)果,這樣可以方便調(diào)試,如果我們把優(yōu)化放在前面,這樣如果有錯誤有發(fā)生時,我們就很難調(diào)試程序,因為我們不知道問題出在哪一步。這個部分是很直接,因為Handel-C是一門頂層設(shè)計語言。僅僅需要加一些代碼來讓主機(jī)和FPGA器件之間通信,這部分代碼要符合等式3.1中通信用時(),它的工作之一是從主機(jī)取出和裝入進(jìn)程需要的數(shù)據(jù),另一個工作是把FPGA器件處理后的數(shù)據(jù)傳回主機(jī)。上面提到,這一步很重要。找到一個能每項操作傳送最少數(shù)據(jù)方法是很重要的,一種可行的方法是把盡量多可以再用的數(shù)據(jù)用FPGA的RAM儲存起來。另外一種方法是把數(shù)據(jù)分割成若干部分以便FPGA芯片能儲存起來,反復(fù)利用這些數(shù)據(jù),直到它被清除出器件。通信的編碼很難實現(xiàn)自動完成,因為不同的芯片和主機(jī)通信的方式不同。然而,去年,一個卓越的工學(xué)士李東尤提出可以解決這個問題的方案。他開發(fā)出一種新的語言,這種語言把軟件編程和硬件語言統(tǒng)一在一起。有了這個軟件,用戶可以定義哪些部分由硬件完成,哪些部分由軟件完成。指定器件后,他的編譯器通過器件庫自動生成通信代碼,因此,如果要編譯器支持一個新的器件,用戶可以很簡單把它寫進(jìn)庫里。這種方法可以使一般的開發(fā)人員不必花太多的時間在寫器件的通信代碼。3.4 小結(jié)在這個章節(jié)中,我們討論了高速FPGA芯片的頂層設(shè)計的一般步驟,在第二部分,我還提到了怎樣解決通信中的最少數(shù)據(jù)量的問題。第四章:例程分析:2-D凝膠圖像處理在這章里,我們將討論在第二章提到的現(xiàn)實生活中的應(yīng)用。我們將以2-D凝膠圖像的處理作為例子來說明第二章中提到的開發(fā)步驟。我們還將比較流水線操作和RC1000操作的性能,遺憾的是,由于一些困難,我還沒研究出2-D凝膠圖像的處理的流水線操作,這在后面的章節(jié)將會細(xì)細(xì)討論。4.1 2-D凝膠圖像處理2-D凝膠圖像處理是一個用研究的技術(shù),它的目的是在不同時間將兩張圖像來匹配凝膠模型,然而,因為不同大小的圖像很難對準(zhǔn),所以很難正確和有效的匹配模型,最近S.Vesser博士,M.J.Dunn博士和 G. Z.Yang博士的一片論文中提到一個新奇的技術(shù),這種技術(shù)是基于圖像強(qiáng)度分配比選擇圖像特性佳的原則。方法是使用凝膠圖像處理一個多解析度表示法而且開發(fā)事實最佳的匹配的近似值能被從低解析度圖像有效率地吸取。在這一步,最重要是找出程序執(zhí)行次數(shù)最多的內(nèi)循環(huán),否則對程序的影響不會很明顯,所以我們必須掌握這種方法工作的算法。下面是用于編程的簡短算法。第一步:設(shè)定層為第0層;第二步:設(shè)定解析度為5來模糊圖像I1,I2;第三步:嚴(yán)格優(yōu)化轉(zhuǎn)換參數(shù)t為;第四步:如果l小于5,繼續(xù)下面第五步,否則結(jié)束;第五步:細(xì)化t第六步:如果沒有完成所有的t矩陣ai,j;ai+1,j;ai,j+1;ai+1,就執(zhí)行第七步,否則執(zhí)行第八步;第七步:將控制點(diǎn)ci,j;ci+1,j;ci,j+1;ci+1,j+1最佳化是由使用 BFGS 取f(c)=corr(l1, tc(I2)的最大值得到,然后回到第六步;第八步:增加設(shè)計層次l第九步:設(shè)定解析度為5+l來模糊圖像I1,I2,然后回到第四步;基本上,運(yùn)算法則的主意是把兩個輸入圖像 (I1,I2) 分為特定數(shù)目的區(qū)塊(柵極)。當(dāng)圖像2(I2) 的柵極形狀被控制點(diǎn)(ci,j; ci+1,j; ci,j+1; ci+1,j+1)決定的時候, 圖像1(I1) 的柵極在外形上總是尖銳的.一個目標(biāo)圖像(tc(I2) 是通過轉(zhuǎn)換對I1的對應(yīng)I2中尖銳的柵極圖素,這樣是為了符合I1中的矩形像素。阻止控制點(diǎn)的操作和相似性就可以在 I1 和Tc(I2)之間被計算。相似性是在 2個圖像之間的圖素的關(guān)聯(lián)。然后派生出將會用來調(diào)整控制點(diǎn),以使在I2和Tc(I2)之間的相似性將會增加。重復(fù)執(zhí)行程序,直到相似性的達(dá)到滿意。上面的整個程序在圖像的不同解析度將會被執(zhí)行。從低的解析度到高解析度的操作。 柵極的數(shù)目是程序工作的解析度決定。源自較低的解析度的控制點(diǎn)將會決定較高的解析度的程序開始控制點(diǎn)。很顯然計算的哪一步是用時最多, 就是第7步的“控制點(diǎn)的優(yōu)化”。因此我選擇這一個部份作為我們硬件操作的出發(fā)點(diǎn)。4.2.2原則4:盡量避免浮點(diǎn)型數(shù)據(jù)的計算因此我們選擇執(zhí)行時間最長的那個部分?,F(xiàn)在應(yīng)該看看這部分是否適合在硬件執(zhí)行,實現(xiàn)是適當(dāng)?shù)摹?因為控制點(diǎn)的優(yōu)化算法是用包括許多浮點(diǎn)型數(shù)據(jù)計算的算出的,所以在第一眼看去,程序是不符合這個規(guī)則的。 在現(xiàn)階段,我們應(yīng)該做第一件事物是看是否可以用整型數(shù)據(jù)計算來代替浮點(diǎn)計算。一個有用的方法是依大小決定浮點(diǎn)型數(shù)據(jù)的數(shù)值,以便特定量整型數(shù)據(jù)的最低重要整型數(shù)據(jù)位表現(xiàn)在十位后面的數(shù)值。 但是正常地,浮點(diǎn)型數(shù)據(jù)能比相同的寬度整型數(shù)據(jù)適應(yīng)數(shù)值范圍大。 這就意味著,當(dāng)把它傳遞到整數(shù)的時候,我們要丟掉浮點(diǎn)型數(shù)據(jù)的某些有效數(shù)據(jù)位。丟掉這些有效數(shù)據(jù)位對這程序運(yùn)行的影響不是很大。遺憾的是,我認(rèn)識到這不是程序的主體,事實上,一些運(yùn)算過程的中間結(jié)果有很大的數(shù)據(jù),特別是程序運(yùn)行在很多像素參加處理的時候。這就意味著丟掉一些有效數(shù)據(jù)位對程序的最后影響是很明顯的,但是,當(dāng)我們更深入了解程序的時候,我們就會發(fā)現(xiàn)優(yōu)化其實是可以分成兩個部分的。相似性和導(dǎo)出的轉(zhuǎn)換和計算BFGS優(yōu)化僅僅第二個部分才會涉及到浮點(diǎn)型數(shù)據(jù)的計算,第一部分可以在整型數(shù)據(jù)上執(zhí)行,現(xiàn)在,我們就要問個問題:第一個部分也是程序執(zhí)行最頻繁的那個部分嗎?在回答這個問題之前,讓我們來看看下面這個等式:c=w*i*CPI (4.1)這里的w是程序中數(shù)據(jù)單元的個數(shù) i是每個數(shù)據(jù)單元指令的平均值CPI是每個指令執(zhí)行的平均周期 c是程序執(zhí)行總共時鐘周期現(xiàn)在我可以告訴答案是第一個部分就是程序執(zhí)行最頻繁的那個部分,盡管兩個部分執(zhí)行的時間是一樣的,第一部分的確是計算量最大的,原因是兩者圖像的大部分像素都參與到第一部分的計算,而第二部分只須計算控制點(diǎn)的工作,控制點(diǎn)要比圖像的像素點(diǎn)要少得多。因此第一部分的等式4.1中的w要比第二部分的等式4.1中w要大很多,但兩個部分中的i和CPI接近相等的。i之所以相等是因為每個數(shù)據(jù)的計算量差不相等的,CPI相等是因為CPU的流水線是滿的,應(yīng)為這兩部分的操作需要相當(dāng)多的計算操作。因此,通過等式4.1,我們可以知道,第一部分的c要比第二部分的c要大很多。因為CPU的時鐘是固定的,所以我們可以計算出第一部分是程序計算量最大的部分。 4.2.3 原則2:選擇數(shù)據(jù)依賴少的部分選擇的這部分的代碼是符合這個標(biāo)準(zhǔn)嗎?答案是符合。因為對于每個目標(biāo)像素,它的數(shù)值完全地在來自Image2的4個像素,而且不影響其他目標(biāo)像素。這就意味著在流水線操作可以同時操作所有的目標(biāo)像素,這樣就對數(shù)據(jù)的依賴性很小,相似性和導(dǎo)出計算也對數(shù)據(jù)的依賴性很小,這樣是因為他們是從對數(shù)據(jù)依賴性很小的目標(biāo)像素計算得到的。 4.2.4原則3:選擇消耗通信資源少的部分由等式2.1知,是的一個部分。因此,不能很大也很重要。在前面的章節(jié)中提到, =w/b,這里b是要通信的數(shù)據(jù)被通信接口的帶寬分成字節(jié)數(shù)。要通信的數(shù)據(jù)量w=I1+I2+cp+Tc(I2)+d+s 這里I1,I2是源圖像,cp是控制點(diǎn)數(shù)組,(I2)是被轉(zhuǎn)換的圖像,d是一個能確定中間結(jié)果的數(shù)組,s是一個能決定相似性的中間結(jié)果的數(shù)組,在最高的解析層次,每個像素的大小是512位*512位,有17*17的控制點(diǎn),每個控制點(diǎn)也4位的x,y,每個控制點(diǎn)有6個8位的d數(shù)據(jù)。每個8位數(shù)據(jù)有5個s數(shù)據(jù),因此總共要傳遞的數(shù)據(jù)有80256個字節(jié),在Pilchard系統(tǒng)中,的64位100M的DIMM接口的帶寬是8*100MHZ=800MB/s,因此,是80256/80010241024s,這比0.001s還要小,對于RC1000,32位的PCI33的帶寬是433=132MB/s,因此,它的是80256/13210241024s,這個大約是0.01s。因為程序的運(yùn)行時間通常是3s左右,因為我們能繼續(xù)執(zhí)行程序。High Level Design For High Speed FPGA DevicesMan. Ng mcn99Department of ComputingImperial CollegeJune 13, 2002AcknowledgementBefore starting the report, I would like to thank the following people for helping me throughout the project. Without their help, it would be impossible for me to finish the project:I would like to thank my supervisor Dr. Wayne Luk for giving me a lot of useful advices and encouragement throughout the project. He also guided me towards the problems I should focus on during the implementation. I would like to thank Professor Yang for letting me to implement his gel-image processing algorithm on hardware. He also gave me references and example sources to understand the theories underneath. And I would like to thank for his teaching in his excellent multimedia course. The course conveyed many useful concepts for me to understand the gel image processing I would like to thank Altaf and Shay. They are two Ph.D research students who helped me a lot throughout the implementation of the application.AbstractIn the project, I have discovered a systematic approach for high-level hardware design. With this approach, I successfully implemented the sophisticated gel image processing on high speed hardware. In the report, I will also introduced a new technique which can automate the process of high level hardware performance optimization by rearranging the code sequence so that the it can be run at minimum number of clock cycles. The report will be split into 4 Chapters:Chapter 1 is Introduction. It includes the background, all the related works and my contribution to the project.Chapter 2 is Optimization. In this chapter, I will focus on the techniques for optimization. I will also demonstrate some techniques which can automate the optimization process.Chapter 3 is Hardware Development. In this chapter, I will generalize the steps of converting a software programme into hardware. These include several techniques which can improve the performance or save the hardware resources.Chapter 4 is Case Study : Gel Image Processing. In this chapter, I will use gel image processing as an example to show the effect on resource and performance of the techniques discussed in chapter 2. In this chapter, I will also compare the performance of the application between two devices and the software version: Pilchard and RC1000.Chapter 5 is Conclusion. It includes the assessed achievements and expected future works.There is also an online version available for this report, the URL is:http:/www.doc.ic.ac.uk/mcn99/project/report.pdfChapter 1IntroductionSince the emergent of Handel-C 5, a C-like hardware language, a complete high level FPGA design approach is realized. However, most of developers will stick on the lower-level language such as VHDL when they are aiming to design high performance hardware. It is because developers have greater control on the actual circuit implementation in low-level approach. But low-level design probably will reach its limit when FPGA chips grow bigger and bigger. Developers will not be able to develop new application quick enough with low level design which consists of billions of gates. A high-level approach will then be the answer. The purpose of this project is to introduce a systematic way of developing high performance hardware under high-level approach.1.1 Background and Related WorksIn this section, I am going to present the materials that are necessary to understand the content of this report.1.1.1 Field Programmable Gate Arrays(FPGAs) 1Like Programmable Logic Devices(PLDs), FPGA is a piece of hardware which is programmable. However, while the size of PLDs is limited by power consumption and time delay, FPGA can easily implement designs with million of gates on a single IC. The re-programmable nature of FPGA allows developers implements design with shorter development times and lower cost than an equivalent custom VLSI chips. It worths mentioning that development of FPGA is faster than Moores Law with capacity doubling every year. With millions of gates available on the newest chip, FPGA is an ideal platform to develop reconfigurable system which is capable of execute complicate application at performance. Therefore, FPGA is the chip I am developing application for.1.1.2 Pilchard 2Pilchard is a reconfigurable computing platform employing a field programmable gate array(FPGA) which plugs into a standared personal computers 133MHz synchronous dynamic RAM Dual In-line Memory Modules(DIMMS)slot. Comparing to traditional FPGA devices which are utilizing the PCI nterface, Pilchard allows data to be transferred to and from the host computer in much shorter time, due to the higher bandwidth as well as the lower latency of the DIMM interface. However, as DIMMS is not originally designed for Input/Output(I/O), extra control signals will be needed for Pilchard to indicate the start and the end of data processing. As a result, high level behavioral design approach is preferable to low level structural design approach for developing applications for Pilchard. Thats proves why it is vital to have a systematic way of high level development for high performance FPGA.1.1.3 RC1000 3RC1000 is a 32-bit PCI card designed for reconfigurable computing applications. It has full board support package in Handel-C with libraries which ease the circuit design for this device. It also features 4 SRAM banks(2Mbytes each) on the board which can be accessed by the FPGA or host CPU. The board can be configured to be run between 4000KHz to 100MHz. This device is very different from Pilchard in many aspects. In the report, I will show that the development steps introduced in this project is general and can be applicable to application development on different devices.1.1.4 VHDL 4VHDL is one of the first high-level languages emerged in the market for designing applications with programmable logic devices. VHDL provides high-level language constructs that enable designers to describe large circuits and bring products to market rapidly. It supports the creation of design libraries in which to store components for reuse in subsequent designs.Because it is a standard language (IEEE standard 1076), VHDL provides portability of code between synthesis and simulation tools, as well as device-independent design. It also facilitates converting a design from a programmable logic to an ASIC implementation. The disadvantage of this language is it is not completely high level, the language still expects user to know the hardware behaviors of the components. Therefore, I decided to use another even higher level hardware language, i.e. Handel-C.1.1.5 Handel-C 5Handel-C is a high level C-like programming language designed for compiling program into hardware images of FPGAs or ASICs. Handel-C provides some extra features which are not appeared in C to support few hardware optimizations. One of those is the language supports specifying the width of each signal so that just optimization can be achieved by targeting the exact resources needed by Handel-C compilers. Handel-C compilers target hardware directly by mapping the program into hardware at the netlist level in xnf or edif format. The advantage of Handel-C over VHDL is that it doesnt expect users to know too much about the hardware in low level which VHDL does. It is a completely high level language! Figure 1.1 shows the design flows I will adopted in converting Handel-C program to hardware. Although several tools are involved in different steps, but users wont need to worry about the hardware detail. Because what users need to do is just clicking several buttons to launch the program for converting the file into next step, it is as simply as that.1.1.6 Extending the Handel-C language 7Dong U Lee, a Ph.D students, has invented a language which supports both hardware and software. His approach is to combine both C and Handel-C language. In the language, user can specify which part is done by software and which part is done by hardware. In the project, he also developed an more friendly interface for communication between the host and the FPGA device. However, the number of devices currently supported by this language is limited. Thats why I finally gave up on using this language.1.2 Contribution I have developed an easy but efficient optimization method which can rearrange code so that it can be run in minimum of cycles. I have developed a systematic design flow for high level hardware design target for high speed devices I have implemented the complicated 2D gel image processing on hardwareChapter 2OptimizationIn this chapter, I am going to discuss various methods to optimization the high level code. Optimization is the main part which we try to exploit and utilize parallelism to achieve speed up which PC software normally is not able to do so because of the limited resources of CPU. The main focus of this chapter will be on how to automate these optimizations processes. We will also discuss some evaluation equation so to measure the speedup we can achieve after optimization.2.1 Performance OptimizationThis is exploiting the potential parallelism of the program and then run different non-conflicting operations at the same clock cycle to acquire speed up. In normal applications, tens of even hundreds of operations which run sequentially on PCs CPU may be able to run in parallel. However, PC cant run them in parallel because of the limited hardware resource. But by designing specific hardware to run as many operations as possible in parallel, significant speed up can obtain. This is the main reason why application on FPGA can sometimes run faster than the corresponding software version even though FPGA hardware run at much slower clock speed(of course we also need to take account of the CPI, but even then PC CPU can still do the same individual operation much faster). There are several techniques we could apply:2.1.1 Balance The Delay Of Each PathBalancing the delay of each pat is important because the hardware clock speed will at most be the same as the path with longest delay. Therefore, if the delay of one particular path is much later than the others, then it means we have wasted resource as other paths is capable of running at much higher speed. By balancing the delay, it can make sure that the the 5 parallel optimization will be optimal in later stage. The delay of a path can be defined as:Tdelay = Tlogic + Trouting (2.1)where Tdelay is the total delay of the pathTlogic is the delay due to logicTrouting is the delay due to routingTherefore, reducing the delay is done by reducing one of the Tlogic or Trouting or both. There are 2 main steps to achieve this: Break up complex operation into simple operations; Use components with pre-defined placement and routing constraintsBreaking Up Complex OperationFirst of all, the simplest step to do is to break the complicated operation into several simpler operations. This step effiectively reduce the logic in each operation thus reduce Tlogic in equation 2.1. In software program, the effect of complicated operation normally will run as quick or even quicker than the simpler operations with the same result as the compiler will optimize the instructions execution for us. However, for hardware, a complex operation mean it needs a longer clock to finish, while other simpler operations need not take that long to finish. Figure 2.1 shows an example of breaking up a complex operation into simple operations. In this example, we can see that sometimes extra registers are needed to store intermediate result of the calculation to make the operation simple enough.Predefined Placement and Routing ComponentIf the result of the first method is not satisfactory enough or the timing constraints still isnt met, we can then use a timing analyzer provided by the FPGA chip developer to find out the longest paths. For example, we can use Timing Analyzer coming along with Xilinx ISE Foundation 4 for timing analysis of Xilinx FPGA chips. After finding out the longest path, we will then know which operation run too slow. At this time, we could try 2 methods to increase the speed of this operation. The first is try to write a constraint file ourselves which specify explicitly the placement and routing of this component. This could enhance the timing as the tools which automatic do the placement and routing is normally not very smart.Then we will include this constraint file before the placement and routing process. However, this approach require the developer to have fair amount of knowledge on the FPGA chip they are using. This includes knowledge on the primitives component supported by the chip and the relative placement and routing of these primitives which can achieve the minimum delay. The second approach is easier, it is to use the macro of the predefined placement and routing components defined by the chip developer. Put it simpler, the chip developer has done the job for you, and we should just use it! For Xilinx, they have a program called Core Generator which does exactly what I mentioned. How to include these components in Handel-C program is specified in Handel-C menu. However, users must know that the timing of output and input of these components requires extra care. Because of the language limitation of Handel-C. The input signal will always arrive one cycle late into the component. This step will reduce Trouting of equation 2.1 because by nicely placing the logic blocks the routing of the signal will be much shorter thus the delay due to routing will significantly reduced.Possibility of Automating This ProcessAbove, we have discussed 2 methods to achieve this step. This step is difficult to be automated, because it is difficult to define what is complex operations and what isnt. This depends on the device and chip we use as well as the functionality of the program . For device which need a very restricted timing constraint. A 16 bits multiplication may be considered as complex while for some other device which cannot run at high speed, it may be a waste to break up the operations into very simple one which can run at very high speed as the device wont be run at that speed anyway.However, we can borrow the idea from Lee again to make automation of this process possible. While compiling the source, we can include information about the device we are using as well as the timing constraint. The library of the device will include the delay of each logic unit. It will also include some information on how the FPGA development tools will route the signals. Then the compiler will be able to approximate the Tlogic and Trouting thus Tdelay of each path. The result will then be compared with the timing constraints specified. If violation is detected, the compiler will use the 2 methods mentioned above to balance the delay of each path until the constraint is met.2.1.2 Basic ParallelismThis is the first step of the actual performance optimization process and is the easiest. The following rules can be applied to automate the process.Scan through the program sequentially. Group as many operations as possible into one clock cycle until there is violation of data dependency. Then repeat the process again for the next cycle. As we have discussed how to detect data dependency in earlier section, this process is possible to be done automatically. Figure 2.2 is a simple example on how to achieve this. We can see that without parallel execution, it takes 8 cycles to complete the 8 operations. However, with parallel execution, it takes only 2 cycles.2.1.3 Re-arrange Code SequenceSometimes, a program can have high parallelism, but the execution sequence of the operations prevents the method just mentioned above to achieve that level. For example, the code in figure 2.3 will have the same effect on the above example shown in figure 2.2. But if we use the ”basic parallelism” method. We will need 4 cycles to finish the operations instead of 2.We can solve the problem by re-arranging code sequence of the code so that the code can run in least cycles as possible. For example, the code above can first change to the same sequence as in 2.2. Then we will apply ”basic parallelism” method again. For this process to be automated by compiler, the compiler will need to have fair amount knowledge and reasoning on the program. I have discovered a method to automate this process:1. Firstly, choose a group of codes to start with, preferably in the innermost loop.2. Create an empty table with variables names as index and labels as value. The label is at the formal var:n where var is the name of a variable and n is the number specifying the operation sequence.3. Scan through the code sequentially. For each variable assignment(Either modification/initialization), assign a label to the operation following the rules listed below:step 1 search the table to find out the label of the variable being assigned to.step 2a if no entry is found, the variable is first being assigned. Add an entry in the table, the content(label) is specified as:step 3ai if the variable is assigned a constant value or a signal from outside the block we are working with, specify the label as varname:1 where varname is the name of the variable being assigned.step 3aii if the variable value depends on other variables, get the labels of these variables from the table. Assign the label of the variable same as the labels we got with the biggest order but with the order incremented by 1. Eg, for a = b + c, if label for b is d:3 and c is e:4, then label for a should be e:5.step 2b if an entry is found, the variable has been assigned before.Get the label of that variable.step 3b Update the label of the variable as specified in step 3ai and step 3aii but with a change that when finding the biggest order label, we should include label of itself in the comparison. Forexample, if a = b + c and the labels of b, c are same as above but the label of a this time exists in the table with value a:5 then the new label will be a:6. Note that we can treat constant as having order of 0 when doing comparison.step 4 associate the operation with the label we just specified.4. After labelling all the operations, we will rearrange the operations such that operations with the same order are placed together.5. Now ”basic parallelism” method will return code which can run in minimum cycles which is the same as the highest order of the labels within the block.6. Then we can work with one outer loop, repeat from step two again until the whole program is covered.The method works because what it does is to push all operations to execute at the earliest cycles. As the result, the modified code must be able to execute at minimum number of cycles. It is obvious that this method can be automated quite easily. By combining this method with the basic parallelism method mentioned before, a surprising efficient parallelisation tools is developed!Figure 2.4 shows examples of how the method works.2.1.4 Add Register To Store Intermediate ResultJust re-arranging the operations sometimes is still not enough. If we find that there are a lot of operations on the same variable while other variables just got few operations on them. Then we will come out with many operations in the first few cycles while there are just operations on that variable in the last few cycles. So, can we balance the operations in each cycles?The possible solution is to add registers to store Intermediate Result of the variable and run the calculation of the Intermediate result concurrently to shorten the cycles taken. This technique doesnt always work and is difficult to automated. Because this requires a lot of reasoning and logics. Figure 2.5 shows an example of this technique. We can see that bef
收藏