很多世界頂尖的“建筑師”可能是你從未聽說過的人，他們設計并創(chuàng)造出了很多你可能從未見過的神奇結構，比如在芯片內部的復雜體系。制造芯片的基本材料源于沙子，但芯片本身已經(jīng)成為人們當代生活不可或缺的東西。如果你使用手機、電腦，或者通過互聯(lián)網(wǎng)收發(fā)信息，那么你就無時無刻不在受益于這些建筑師們的偉大工作。

FPGA 是芯片的其中一種，從上世紀八十年代誕生起，F(xiàn)PGA 已經(jīng)從簡單的可編程門陣列，發(fā)展成為了有著大量可編程邏輯的復雜片上系統(tǒng)。除了硬件結構之外，F(xiàn)PGA 的開發(fā)工具和應用場景也都取得了長足的進步和擴展，F(xiàn)PGA 在整個半導體行業(yè)的重要性也在不斷增強。FPGA 芯片的演進，離不開這些“建筑師”的不斷發(fā)明創(chuàng)造。

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

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

01 尋路者：基于協(xié)商的 FPGA 性能優(yōu)化布線算法
一句話總結：歷史最強 FPGA 布線算法，沒有之一。

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

作者：Larry McMurchie, Carl Ebeling

發(fā)表時間：1995 年

推介人：Sinan Kaptanoglu（Microsemi 公司）

Carl Ebeling（現(xiàn)任華盛頓大學教授）

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

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

在 1995 年，大多數(shù) FPGA 研究者都認為這項工作也只不過是又一個取得了 10%性能提升的成果，和其他研究并無二致。只有很少的人認識到，這項成果帶來的是改變整個游戲規(guī)則的根本性創(chuàng)新，它將在今后的幾十年里經(jīng)受住其他工作的挑戰(zhàn)，而且不會被其他布線算法所超越。幸運的是，在隨后的幾年里，學術界和工業(yè)界都漸漸認識到，這項成果所提出的理念已經(jīng)達到了前所未有的高度。

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

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

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

02 FPGA 布線架構：分段與緩沖及其對速度和邏輯密度的優(yōu)化
一句話總結：對 VPR 工具的跨越式優(yōu)化，從而直接影響高端商業(yè) FPGA 的成形和發(fā)展。

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

作者：Vaughn Betz, Jonathan Rose

發(fā)表時間：1999 年

推介人：Carl Ebeling（華盛頓大學）

Vaughn Betz（現(xiàn)任多倫多大學教授）

這項工作在 VPR 中加入了對時序優(yōu)先布線算法的支持，并對延時進行了精確估計。這使得 VPR 可以對 FPGA 互聯(lián)網(wǎng)絡結構進行更加深入的研究。通常來說，F(xiàn)PGA 上 90%的面積都是用來進行可編程布線的，而關鍵路徑延時里有 80%都是布線延時。因此，如何構建正確的 FPGA 互聯(lián)網(wǎng)絡，對于性能和資源消耗來說都是至關重要的。隨著 FPGA 面積的不斷增加，這一點更為明顯，因為根據(jù) Rent 法則，電路中導線數(shù)量的增長必須快于邏輯單元數(shù)量的增長。

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

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

這項成果首先假設了一個傳統(tǒng)的島型 FPGA 架構，然后嘗試使用最優(yōu)的方法對連線進行分段，并將這些分段連接起來。通過使用 VPR，可以自動對大部分的參數(shù)空間進行探索，從而得到對于給定的參數(shù)的最優(yōu)布線結果。

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

03 從高層描述自動生成 FPGA 布線架構
一句話總結：通過自動處理 FPGA 布線架構研究中繁瑣的部分，推進了整個研究領域的跨越式發(fā)展。

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

作者：Vaughn Betz, Jonathan Rose

發(fā)表時間：2000 年

推介人：Scott Hauck（華盛頓大學）

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

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

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

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

04時序驅動的 FPGA 布局算法
一句話總結：現(xiàn)代 FPGA CAD 工具中的核心布局與時序優(yōu)化算法。

英文名：Timing-driven placement for FPGAs

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

發(fā)表時間：2000 年

推介人：Jason Cong（加州大學洛杉磯分校）

Jonathan Rose（現(xiàn)任多倫多大學教授）

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

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

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

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

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

05   在商用計算機上的高質量、確定性的 FPGA 并行布局算法
一句話總結：利用多核處理器顯著降低 FPGA 項目編譯時間的標志性工作

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

作者：Adrian Ludwin, Vaughn Betz, Ketan Padalia

發(fā)表時間：2008 年

推介人：Jonathan Rose

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

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

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

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

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

結語
這五個 FPGA 布局布線算法領域的重要工作，有的奠定了幾乎所有現(xiàn)代商用 FPGA 的布線算法基礎，有的大幅改進了 FPGA 布局、布線、時序優(yōu)化等環(huán)節(jié)的算法性能，有的則對 FPGA CAD 軟件進行了跨越式提升。更重要的是，這些工作所采用的方法論、思維方式、前瞻性與實用性的統(tǒng)一、以及嚴謹?shù)闹螌W態(tài)度，都為之后的學術和工業(yè)研究樹立了最高的典范。