針對一個固定集合的應用設計一個有效減少線路面積的可重組式硬體

Abstract

可重組式硬體不但提供了利用硬體加速的效能，也同時保留軟體使用的彈性，在市面上有一種稱作FPGA（可程式化邏輯陣列）的產品就是此種硬體的先驅者，其已廣泛使用在I/C產品的雛型驗證中。目前FPGA的發展趨勢在於使用較多的運算單元來達成大量的運算，為了因應運算單元的增加，必須提高繞線的能力，因此FPGA上會有許多的稱為繞線元件線和電閘，高度的繞線能力需求將使得FPGA大部分的硬體面積被繞線元件所佔用。 本篇論文的目的在於提供運算最大平行度的前提下，尋求所需盡量小的繞線面積。藉由針對特定領域的應用來設計可重組式硬體，如此一來祇需要有限度的繞線能力，自然減少對於繞線元件的需求；因此本論文的重點在於提出減少繞線面積的演算法。我們從特定領域的應用中，選出值得以可重組式硬體加速的迴圈，並將它們轉換成資料流程圖，找出資料流程圖以可重組式硬體來實現時，需要用到哪些運算單元和繞線元件。這個步驟稱為Placement and Routing，一般的做法是先配置資料流程圖上所有的運算應該用可重組式硬體上哪個運算單元實現，之後再找出運算跟運算之間的資料傳送路徑在可重組式硬體上的繞線路徑。這樣的做法使得繞線時的路徑會受限於出發點和到達點的位置，雖然繞線快速，但不見得有效減少繞線面積。因此我們所提出的方法為邊放邊繞，在放置每一個運算到可重組式硬體上時，同時考慮如何繞出資料傳送路徑所增加的繞線面積最小，這個步驟的繞線是已知出發點位置，找出到達點對應的運算單元及繞線路徑，使得所需增加的繞線面積最小。我們採用了貪婪演算法，每次找出目前所需最小繞線面積，並以盡量不增加新路線為原則，繞線時優先利用硬體上已存在的未使用路線片段。基於這個原則，先被選出放置的運算對於後面運算的放置位置具有影響性，因此運算被選出放置的順序亦在我們考慮之內。 實驗結果顯示，我們的方法繞出來的面積比用傳統VPR（Versatile Placement and Routing）方法繞時少了28.2%，可以有效降低硬體的成本，當可重組式硬體需求的運算單元增多時，我們的方法不但可避免因大量的繞線元件需求限制晶片上可容納的運算單元數量，同時可以減少耗電甚至於因繞線而引起的延遲。