《針對FPGA協處理器的高速布局布線算法研究》是依託北京大學，由羅國傑擔任負責人的青年科學基金項目。
基本介紹
- 中文名：針對FPGA協處理器的高速布局布線算法研究
- 項目負責人：羅國傑
- 項目類別：青年科學基金項目
- 依託單位：北京大學
項目摘要,結題摘要,
項目摘要
FPGA協處理器能支持可重構計算，在特定套用中實現高性能低能耗的計算。然而，FPGA程式的編譯時間（高層次綜合、邏輯綜合、布局布線）遠遠大於同等功能的CPU程式的編譯時間。漫長的編譯時間降低開發效率，阻礙了軟體工程師套用FPGA協處理器與可重構計算。在FPGA編譯過程里，布局布線占了大概四分之三的時間；為了縮短編譯時間，我們打算開發高速的布局布線器，實現比現有布局布線器快10倍至100倍的效果。首先，我們會對現有布局器做最最佳化研究，並開發一個高質量的支持現代異構FPGA體系結構的布局器。之後，我們將採用算法加速（採用解析式算法和高層次方法）和並行加速的手段，來使我們的布局器以及一個基於協商的布線器達到最大的加速效果。另外，我們將開發一套開放原始碼的FPGA物理綜合流程，以推動可重構計算的研究。
結題摘要
FPGA協處理器能支持可重構計算，在特定套用中能實現高性能低能耗的計算。然而，FPGA程式的編譯時間遠遠大於同等功能的CPU程式的編譯時間。漫長的編譯時間降低開發效率，阻礙了軟體工程師套用FPGA協處理器與可重構計算。在FPGA編譯過程里，布局布線占了大概四分之三的時間；為了縮短編譯時間，我們打算開發高速的布局布線器，實現比現有布局布線器快10倍至100倍的效果。 項目成功實現了：1、現有FPGA布局器的最最佳化研究。我們通過構造具有已知最優布局線長的異質FPGA網表，從而定量評估DSP、BRAM等異質模組對於布局線長的影響。 2、布局布線算法的高速並行方法的設計。我們提出基於網表位置信息最最佳化遞歸劃分的粗粒度並行的FPGA布線方法，實現了7倍的加速效果，是目前學術界發表的加速比最大的FPGA並行布線方法。另外，我們提出基於通用圖形處理器細粒度並行的FPGA布線方法，實現了6倍的加速效果；預計該技術使用多塊通用圖形處理器能實現15倍的加速效果，或者疊加上述的粗粒度並行布線方法實現42倍的加速效果。對於布局問題，我們提出布局後的觸發器聚集算法，利用算法最佳化和多執行緒技術將核心計算加速了25倍，快速有效地降低了30%的時鐘功耗。3、支持異質FPGA物理設計自動化的並行算法開發平台。我們利用現有FPGA開發工具的TCL語言界面，搭建了支持大規模集群的分散式布局算法開發平台；該平台支持新興的分散式計算框架Spark編程，並能演示一個分散式詳細布局算法的例子。4、FPGA套用的加速。針對基於Mumford-Shah模型的圖像同時重建及分割算法，我們提出了使用異步並行更新技術的FPGA加速設計；相比通用圖形處理器，速度和能效分別提高了1.2倍和58倍。本項目已發表國內外會議論文7篇和專利申請1項。
