03.06 FPGA 20年最有影響力的25個研究成果

很多世界頂尖的“建築師”可能是你從未聽說過的人,他們設計並創造出了很多你可能從未見過的神奇結構,比如在芯片內部的複雜體系。製造芯片的基本材料源於沙子,但芯片本身已經成為人們當代生活不可或缺的東西。如果你使用手機、電腦,或者通過互聯網收發信息,那麼你就無時無刻不在受益於這些建築師們的偉大工作。

FPGA是芯片的其中一種,從上世紀八十年代誕生起,FPGA 已經從簡單的可編程門陣列,發展成為了有著大量可編程邏輯的複雜片上系統。除了硬件結構之外,FPGA 的開發工具和應用場景也都取得了長足的進步和擴展,FPGA 在整個半導體行業的重要性也在不斷增強。FPGA 芯片的演進,離不開這些“建築師”的不斷髮明創造。

幾年前,這些 FPGA 的頂級建築師們選出了自上世紀九十年代起的 20 年以來 FPGA 領域最有影響力的 25 個研究成果。通過這些重要的成果,我們會理解 FPGA 是如何發展至今,並且知道 FPGA 技術未來將會發展向何處。

這 25 個研究成果按研究領域分為架構、EDA工具、電路、應用等大類,每項成果都由一名該領域的頂級學者做推介。接下來,我將在幾篇文章裡,分別介紹這這些改變了 FPGA 發展進程的重要研究成果。本文是佈局佈線算法篇。關於 FPGA 架構領域的重要創新,請參見這兩篇:《系統架構篇》和《微架構篇》。

01

尋路者:基於協商的 FPGA 性能優化佈線算法

一句話總結:歷史最強 FPGA 佈線算法,沒有之一。

英文名:Pathfinder: A Negotiation-Based Performance-Driven Router for FPGAs

作者:Larry McMurchie, Carl Ebeling

推介人:Sinan Kaptanoglu(Microsemi 公司)

FPGA 20年最有影响力的25个研究成果

Carl Ebeling(現任華盛頓大學教授)

這項工作可以算是過去二十年中影響 FPGA 技術發展的最重要的成果之一。這項成果對工業界和學術界都產生了極其深遠的影響。最重要的是,這個工作將 FPGA 的佈線研究,從一個結果波動極大的問題,轉化為一個能夠很好控制的優化問題。時至今日,幾乎所有的 FPGA 廠商都在使用這項工作提出的協商擁塞(Negotiated Congestion)的佈線算法,或者是由這個算法引申出來的其他佈線方法。此外,學術界最為廣泛使用的 FPGA 架構設計和分析工具 VPR,就是基於這項成果而開發的。

通常來說,有些研究成果會立刻對學術界帶來啟發,而有些則會首先被低估一段時間,然後才會被人們完全理解。這項成果就屬於後者。很多研究 FPGA 設計工具的工作都是提出一些新的想法,使用基準測試對這些想法進行實驗,然後比當時的其他工作取得 5%到 10%的提升,諸如此類。並不是說這些工作不夠優秀,但大多數的工作所取得的成就和影響都是暫時的,因為會不斷出現新的 CAD工作取得更好的結果。

在 1995 年,大多數 FPGA 研究者都認為這項工作也只不過是又一個取得了 10%性能提升的成果,和其他研究並無二致。只有很少的人認識到,這項成果帶來的是改變整個遊戲規則的根本性創新,它將在今後的幾十年裡經受住其他工作的挑戰,而且不會被其他佈線算法所超越。幸運的是,在隨後的幾年裡,學術界和工業界都漸漸認識到,這項成果所提出的理念已經達到了前所未有的高度。

這項工作首先闡述了協商的基本思想,以及處理一階擁塞的方法。然後分析了二階擁塞,見下圖,並引入了對“歷史成本(history cost)”的需求。之後將這個概念進行了推廣,並將佈線延時引入考量。最後給出了這個算法的偽代碼,以及一些實驗結果。相比於當時的其他商用工具,這個方法能取得 11%的效果提升。

FPGA 20年最有影响力的25个研究成果

客觀的說,儘管這是一項出色的工作,但它在表述時的清晰程度並非完美。當你每次審視這項工作時,都能體會出一些細微的差別。

時至今日,我們已經能夠廣泛而成功的使用協商擁堵算法來處理 FPGA 的佈線問題了。儘管如此,這個方法為何如此有效,學術界在理論層面上仍然莫衷一是。例如,我們能完全理解和分析退火算法是如何工作和收斂的,但對於協商擁堵算法的理解還遠遠達不到這個層次。也就是說,人們還沒有對這個思想構建起足夠嚴謹的理論體系。因此,這項工作仍將繼續激發研究者們對這一課題的進一步研究。

02

FPGA 佈線架構:分段與緩衝及其對速度和邏輯密度的優化

一句話總結:對 VPR 工具的跨越式優化,從而直接影響高端商業 FPGA 的成形和發展。

英文名:FPGA Routing Architecture: Segmentation and Buffering to Optimize Speed and Density

作者:Vaughn Betz, Jonathan Rose

推介人:Carl Ebeling(華盛頓大學)

FPGA 20年最有影响力的25个研究成果

Vaughn Betz(現任多倫多大學教授)

這項工作在 VPR 中加入了對時序優先佈線算法的支持,並對延時進行了精確估計。這使得 VPR 可以對 FPGA 互聯網絡結構進行更加深入的研究。通常來說,FPGA 上 90%的面積都是用來進行可編程佈線的,而關鍵路徑延時裡有 80%都是佈線延時。因此,如何構建正確的 FPGA 互聯網絡,對於性能和資源消耗來說都是至關重要的。隨著 FPGA 面積的不斷增加,這一點更為明顯,因為根據 Rent 法則,電路中導線數量的增長必須快於邏輯單元數量的增長。

然而,架構師經常習慣於根據直覺和以往的經驗做出決策,而不是根據基準測試和理論分析。CAD 工具通常針對單一架構進行優化,因此如果架構進行了變更,工具的性能和有效性就會不可避免的下降。此外,如果要量化互聯對性能的影響,就需要有基於時序驅動的綜合、佈局和佈線算法。

這項工作在 VPR 中引入了一種用來精確估計延時的 Elmore 模型,並闡述了一種使用 VPR 對 FPGA 佈線架構進行分析和評估的方法。這使得 FPGA 架構師可以通過一種架構描述語言(architecture description language),對 FPGA 架構進行建模和分析,然後工具就可以自動對這種架構進行適配。

FPGA 20年最有影响力的25个研究成果

這項成果首先假設了一個傳統的島型 FPGA 架構,然後嘗試使用最優的方法對連線進行分段,並將這些分段連接起來。通過使用 VPR,可以自動對大部分的參數空間進行探索,從而得到對於給定的參數的最優佈線結果。

這項成果最大的貢獻在於它所使用的方法論和工具。僅僅在幾年之後,Altera 在構建 Stratix 架構時就採用了相似的設計方法,以及基於 VPR 的工具包。這進一步表明,創新既需要跳出固有的思維模式,也要使用先進的工具來評估這些新的想法,兩者缺一不可。

03

從高層描述自動生成 FPGA 佈線架構

一句話總結:通過自動處理 FPGA 佈線架構研究中繁瑣的部分,推進了整個研究領域的跨越式發展。

英文名:Automatic Generation of FPGA Routing Architectures from High-Level Descriptions

作者:Vaughn Betz, Jonathan Rose

推介人:Scott Hauck(華盛頓大學)

FPGA 的架構研究是非常複雜的,有的時候即使是為了回答最簡單的問題,都需要付出相當程度的努力。在很多情況下,FPGA 架構師會認為他們的一些新想法,諸如更大的邏輯塊、新型的進位鏈等等,理應會極大的提升系統的功耗、性能、面積、穩定性等指標。然而,為了證明這些想法的可行性,就需要設計工具和實際應用來對這些想法進行驗證。同時,也需要結合很多和這些想法無關的 FPGA 架構細節,以組成一個完整的系統。在工具層面,大名鼎鼎的 Pathfinder 和 VPR 的出現,已經為大多數邏輯映射工作提供了一個穩定而高效的後端平臺。

然而,對於 FPGA 互聯架構來說,仍然有著很多細節問題需要注意。例如,連線長度、互聯方法、邏輯塊結構,等等。這些問題往往與希望研究的主要問題無關,但都是必須統籌考慮的問題。儘管單向導線(unidirectional wires)也許是個好的想法,但如果我們將其用於所有的互聯節點,那麼面積和容抗的增加將迅速掩蓋這個想法帶來的優點和好處。那麼,如果我們只將其用於 50%的互聯節點,然後將所有的邏輯塊輸出連接到奇數號導線、將所有邏輯塊輸入連接到偶數號導線呢?如果我們又想到了其他的互聯架構和方式呢?在這項成果面世之前,這些問題都是無法求解的。

FPGA 20年最有影响力的25个研究成果

因此,解決這類問題的重點,是這項成果所展示的架構描述語言,以及 VPR 中的架構生成器。簡單來說,這項成果專注於處理那些佈線架構中沒人關心、但卻非常重要的細節問題,比如:邏輯塊是如何連接的?如何保證連線之間的交互不會對系統產生不確定影響?交換架構是如何組織排列的?當設計中存在長導線時,如何保證這條穿過芯片多個區域的連線以合理的方式進行分段?……等等等等。而這項成果就是用來解決這些在 FPGA 架構研究中的細微問題。

正是如此,儘管這項工作並沒有專注於架構研究的重點和流行的部分,但它極大的幫助了這個領域向前推進了一大步。通過提供更加高效的工具,這項工作使研究人員更有生產力,從而在另外一個角度幫助 FPGA 架構研究帶來了大量創新。

04

時序驅動的 FPGA 佈局算法

一句話總結:現代 FPGA CAD 工具中的核心佈局與時序優化算法。

英文名:Timing-driven placement for FPGAs

作者:Alexander (Sandy) Marquardt, Vaughn Betz, Jonathan Rose

推介人:Jason Cong(加州大學洛杉磯分校)

FPGA 20年最有影响力的25个研究成果

Jonathan Rose(現任多倫多大學教授)

眾所周知,VPR 是 FPGA 學術界最流行的開源 CAD 軟件,幾乎每個新的 FPGA 架構研究都使用了 VPR。而這項成果就詳細闡述了在 VPR 中使用的時序驅動的佈局算法。在這項成果中介紹的 T-VPlace 算法,除了廣受好評和廣泛使用之外,它還對 FPGA 的佈局算法有著三個重要的貢獻。

第一,在 T-VPlace 算法中,時序優化的過程是通過最小化延時與導線長度的加權和實現的。這個計算過程通過一個基於模擬退火(simulated annealing)的優化引擎完成。其中,每個節點的權值是該節點時序臨界性的多項式函數。這項工作的結果表明,這種權值函數能夠得到很好的時序收斂。此外,導線長度和時序都可以根據前一次的迭代進行自主歸一化,這使得算法有著很好的穩定性。

第二,這項工作表明,每個節點的時序裕量(timing slack)不需要隨著邏輯單元的移動而不斷更新。只需要在對每個溫度進行的迭代完成之後,再進行精確的基於路徑的時序分析即可。使用未更新的時序裕量通常並不會對時序優化造成影響,反而會大幅提升 T-VPlace 算法的性能和效率。不過,後來的工作也表明,在高度流水線化的設計中,如果使用未更新的時序裕量會對性能造成負面影響。

第三,在一個給定的分段可編程互聯架構中,在源 - 匯節點間的延時不能簡單的通過其曼哈頓距離來估計。然而,如果在佈局期間使用一個佈線器來計算每個源 - 匯節點之間的延時也是非常不現實的。因此,通過利用 FPGA 架構中的對稱性,T-VPlace 算法使用了一個預先計算的延時查找表,根據水平和垂直方向的距離作為索引,從而實現對延時的快速查找。

FPGA 20年最有影响力的25个研究成果

通過以上三種技術,使得 T-VPlace 可以高效的產生高質量的時序優化結果。事實上,前兩種技術同樣可以被應用於集成電路設計中的標準單元佈局。可以說,T-VPlace 算法是現代 FPGA 佈局佈線算法的基石。作者所在的 RightTrack 公司在 2000 年被 Altera 收購後,T-VPlace 及其優化技術就被整合進 Altera 的 Quartus 設計軟件中,並被世界上成千上萬的 FPGA 設計者所使用至今。

05

在商用計算機上的高質量、確定性的 FPGA 並行佈局算法

一句話總結:利用多核處理器顯著降低 FPGA 項目編譯時間的標誌性工作

英文名:High-Quality, Deterministic Parallel Placement for FPGAs on Commodity Hardware

作者:Adrian Ludwin, Vaughn Betz, Ketan Padalia

推介人:Jonathan Rose

FPGA 業界當前面臨的最關鍵的問題之一是設計工具編譯的時間過長,這一方面是由於計算機處理器的性能並沒有質的飛躍,另外一方面是由於 FPGA 的大小隨著半導體制造工藝的發展而不斷增加。為了應對這個問題,一個有效的方法是使用多個處理器核心進行並行編譯。

這項成果旨在應對 FPGA CAD 流程中最慢的部分之一,即佈局的並行化問題。在這個工作中,採用了幾項非常獨特而重要的方法。例如,這是目前首個,也是唯一一個嘗試對工業級佈局軟件進行並行化的工作,並最終將成果轉化為成功的商用軟件。在此之前,儘管有很多工作試圖對佈局算法做並行化處理,它們其實都是基於學術版本的算法,也就是說,這些工作並不需要應對海量的器件數據庫、複雜的時序分析、以及在商業版軟件中會遇到的各種細節問題。

此外,這項工作對算法的確定性(determinism)做了重要闡述。算法的確定性指,不管使用多少個處理器運行算法,它的結果都會是完全相同的。儘管在學術界中存在爭議,但在商業軟件中確定性對於復現結果以及調試都是不可或缺的。這項成果表明,需要做一系列細緻的工作以保證算法的確定性。此外,這項成果也證明了這些工作對性能的損失很小。

這個工作還就內存架構對並行算法性能的影響進行了深入分析。值得注意的是,它表明不同的內存結構對算法性能的影響很大。

總體來說,這項成果對算法性能取得了很大的提升:在佈局階段,使用 4 個處理器內核可以得到 2.2 倍的性能提升。對於大型設計,這樣的性能提升會節省好幾個小時的運行時間。在一個完整的 FPGA 編譯流程中,還存在著很多耗時的階段,這也意味著需要做更多的工作,才能最終將 FPGA 項目的編譯時間進一步縮短。但是,這個成果為實現這一目標做出了巨大的貢獻,也是其他後續工作值得參考的典範。

FPGA 20年最有影响力的25个研究成果

結語

這五個 FPGA 佈局佈線算法領域的重要工作,有的奠定了幾乎所有現代商用 FPGA 的佈線算法基礎,有的大幅改進了 FPGA 佈局、佈線、時序優化等環節的算法性能,有的則對 FPGA CAD 軟件進行了跨越式提升。更重要的是,這些工作所採用的方法論、思維方式、前瞻性與實用性的統一、以及嚴謹的治學態度,都為之後的學術和工業研究樹立了最高的典範。


分享到:


相關文章: