131 1300 0010
很多世界頂尖的“建筑師”可能是你從未聽說過的人，他們設計并創造出了很多你可能從未見過的神奇結構，比如在芯片內部的復雜體系。制造芯片的基本材料源于沙子，但芯片本身已經成為人們當代生活不可或缺的東西。如果你使用手機、電腦，或者通過互聯網收發信息，那么你就無時無刻不在受益于這些建筑師們的偉大工作。
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
發表時間：1995 年
推介人：Sinan Kaptanoglu（Microsemi 公司）
Carl Ebeling（現任華盛頓大學教授）
這項工作可以算是過去二十年中影響 FPGA 技術發展的最重要的成果之一。這項成果對工業界和學術界都產生了極其深遠的影響。最重要的是，這個工作將 FPGA 的布線研究，從一個結果波動極大的問題，轉化為一個能夠很好控制的優化問題。時至今日，幾乎所有的 FPGA 廠商都在使用這項工作提出的協商擁塞（NegoTIated CongesTIon）的布線算法，或者是由這個算法引申出來的其他布線方法。此外，學術界最為廣泛使用的 FPGA 架構設計和分析工具 VPR，就是基于這項成果而開發的。
通常來說，有些研究成果會立刻對學術界帶來啟發，而有些則會首先被低估一段時間，然后才會被人們完全理解。這項成果就屬于后者。很多研究 FPGA 設計工具的工作都是提出一些新的想法，使用基準測試對這些想法進行實驗，然后比當時的其他工作取得 5%到 10%的提升，諸如此類。并不是說這些工作不夠優秀，但大多數的工作所取得的成就和影響都是暫時的，因為會不斷出現新的 CAD 工作取得更好的結果。
在 1995 年，大多數 FPGA 研究者都認為這項工作也只不過是又一個取得了 10%性能提升的成果，和其他研究并無二致。只有很少的人認識到，這項成果帶來的是改變整個游戲規則的根本性創新，它將在今后的幾十年里經受住其他工作的挑戰，而且不會被其他布線算法所超越。幸運的是，在隨后的幾年里，學術界和工業界都漸漸認識到，這項成果所提出的理念已經達到了前所未有的高度。
這項工作首先闡述了協商的基本思想，以及處理一階擁塞的方法。然后分析了二階擁塞，見下圖，并引入了對“歷史成本（history cost）”的需求。之后將這個概念進行了推廣，并將布線延時引入考量。最后給出了這個算法的偽代碼，以及一些實驗結果。相比于當時的其他商用工具，這個方法能取得 11%的效果提升。
客觀的說，盡管這是一項出色的工作，但它在表述時的清晰程度并非完美。當你每次審視這項工作時，都能體會出一些細微的差別。
時至今日，我們已經能夠廣泛而成功的使用協商擁堵算法來處理 FPGA 的布線問題了。盡管如此，這個方法為何如此有效，學術界在理論層面上仍然莫衷一是。例如，我們能完全理解和分析退火算法是如何工作和收斂的，但對于協商擁堵算法的理解還遠遠達不到這個層次。也就是說，人們還沒有對這個思想構建起足夠嚴謹的理論體系。因此，這項工作仍將繼續激發研究者們對這一課題的進一步研究。
02 FPGA 布線架構：分段與緩沖及其對速度和邏輯密度的優化
一句話總結：對 VPR 工具的跨越式優化，從而直接影響高端商業 FPGA 的成形和發展。
英文名：FPGA RouTIng Architecture: Segmentation and Buffering to Optimize Speed and Density
作者：Vaughn Betz, Jonathan Rose
發表時間：1999 年
推介人：Carl Ebeling（華盛頓大學）
Vaughn Betz（現任多倫多大學教授）
這項工作在 VPR 中加入了對時序優先布線算法的支持，并對延時進行了精確估計。這使得 VPR 可以對 FPGA 互聯網絡結構進行更加深入的研究。通常來說，FPGA 上 90%的面積都是用來進行可編程布線的，而關鍵路徑延時里有 80%都是布線延時。因此，如何構建正確的 FPGA 互聯網絡，對于性能和資源消耗來說都是至關重要的。隨著 FPGA 面積的不斷增加，這一點更為明顯，因為根據 Rent 法則，電路中導線數量的增長必須快于邏輯單元數量的增長。
然而，架構師經常習慣于根據直覺和以往的經驗做出決策，而不是根據基準測試和理論分析。CAD 工具通常針對單一架構進行優化，因此如果架構進行了變更，工具的性能和有效性就會不可避免的下降。此外，如果要量化互聯對性能的影響，就需要有基于時序驅動的綜合、布局和布線算法。
這項工作在 VPR 中引入了一種用來精確估計延時的 Elmore 模型，并闡述了一種使用 VPR 對 FPGA 布線架構進行分析和評估的方法。這使得 FPGA 架構師可以通過一種架構描述語言（architecture description language），對 FPGA 架構進行建模和分析，然后工具就可以自動對這種架構進行適配。
這項成果首先假設了一個傳統的島型 FPGA 架構，然后嘗試使用最優的方法對連線進行分段，并將這些分段連接起來。通過使用 VPR，可以自動對大部分的參數空間進行探索，從而得到對于給定的參數的最優布線結果。
這項成果最大的貢獻在于它所使用的方法論和工具。僅僅在幾年之后，Altera 在構建 Stratix 架構時就采用了相似的設計方法，以及基于 VPR 的工具包。這進一步表明，創新既需要跳出固有的思維模式，也要使用先進的工具來評估這些新的想法，兩者缺一不可。
03 從高層描述自動生成 FPGA 布線架構
一句話總結：通過自動處理 FPGA 布線架構研究中繁瑣的部分，推進了整個研究領域的跨越式發展。
英文名：Automatic Generation of FPGA Routing Architectures from High-Level Descriptions
作者：Vaughn Betz, Jonathan Rose
發表時間：2000 年
推介人：Scott Hauck（華盛頓大學）
FPGA 的架構研究是非常復雜的，有的時候即使是為了回答最簡單的問題，都需要付出相當程度的努力。在很多情況下，FPGA 架構師會認為他們的一些新想法，諸如更大的邏輯塊、新型的進位鏈等等，理應會極大的提升系統的功耗、性能、面積、穩定性等指標。然而，為了證明這些想法的可行性，就需要設計工具和實際應用來對這些想法進行驗證。同時，也需要結合很多和這些想法無關的 FPGA 架構細節，以組成一個完整的系統。在工具層面，大名鼎鼎的 Pathfinder 和 VPR 的出現，已經為大多數邏輯映射工作提供了一個穩定而高效的后端平臺。
然而，對于 FPGA 互聯架構來說，仍然有著很多細節問題需要注意。例如，連線長度、互聯方法、邏輯塊結構，等等。這些問題往往與希望研究的主要問題無關，但都是必須統籌考慮的問題。盡管單向導線（unidirectional wires）也許是個好的想法，但如果我們將其用于所有的互聯節點，那么面積和容抗的增加將迅速掩蓋這個想法帶來的優點和好處。那么，如果我們只將其用于 50%的互聯節點，然后將所有的邏輯塊輸出連接到奇數號導線、將所有邏輯塊輸入連接到偶數號導線呢？如果我們又想到了其他的互聯架構和方式呢？在這項成果面世之前，這些問題都是無法求解的。
因此，解決這類問題的重點，是這項成果所展示的架構描述語言，以及 VPR 中的架構生成器。簡單來說，這項成果專注于處理那些布線架構中沒人關心、但卻非常重要的細節問題，比如：邏輯塊是如何連接的？如何保證連線之間的交互不會對系統產生不確定影響？交換架構是如何組織排列的？當設計中存在長導線時，如何保證這條穿過芯片多個區域的連線以合理的方式進行分段？……等等等等。而這項成果就是用來解決這些在 FPGA 架構研究中的細微問題。
正是如此，盡管這項工作并沒有專注于架構研究的重點和流行的部分，但它極大的幫助了這個領域向前推進了一大步。通過提供更加高效的工具，這項工作使研究人員更有生產力，從而在另外一個角度幫助 FPGA 架構研究帶來了大量創新。
04時序驅動的 FPGA 布局算法
一句話總結：現代 FPGA CAD 工具中的核心布局與時序優化算法。
英文名：Timing-driven placement for FPGAs
作者：Alexander (Sandy) Marquardt, Vaughn Betz, Jonathan Rose
發表時間：2000 年
推介人：Jason Cong（加州大學洛杉磯分校）
Jonathan Rose（現任多倫多大學教授）
眾所周知，VPR 是 FPGA 學術界最流行的開源 CAD 軟件，幾乎每個新的 FPGA 架構研究都使用了 VPR。而這項成果就詳細闡述了在 VPR 中使用的時序驅動的布局算法。在這項成果中介紹的 T-VPlace 算法，除了廣受好評和廣泛使用之外，它還對 FPGA 的布局算法有著三個重要的貢獻。
第一，在 T-VPlace 算法中，時序優化的過程是通過最小化延時與導線長度的加權和實現的。這個計算過程通過一個基于模擬退火（simulated annealing）的優化引擎完成。其中，每個節點的權值是該節點時序臨界性的多項式函數。這項工作的結果表明，這種權值函數能夠得到很好的時序收斂。此外，導線長度和時序都可以根據前一次的迭代進行自主歸一化，這使得算法有著很好的穩定性。
第二，這項工作表明，每個節點的時序裕量（timing slack）不需要隨著邏輯單元的移動而不斷更新。只需要在對每個溫度進行的迭代完成之后，再進行精確的基于路徑的時序分析即可。使用未更新的時序裕量通常并不會對時序優化造成影響，反而會大幅提升 T-VPlace 算法的性能和效率。不過，后來的工作也表明，在高度流水線化的設計中，如果使用未更新的時序裕量會對性能造成負面影響。
第三，在一個給定的分段可編程互聯架構中，在源 - 匯節點間的延時不能簡單的通過其曼哈頓距離來估計。然而，如果在布局期間使用一個布線器來計算每個源 - 匯節點之間的延時也是非常不現實的。因此，通過利用 FPGA 架構中的對稱性，T-VPlace 算法使用了一個預先計算的延時查找表，根據水平和垂直方向的距離作為索引，從而實現對延時的快速查找。
通過以上三種技術，使得 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
發表時間：2008 年
推介人：Jonathan Rose
FPGA 業界當前面臨的最關鍵的問題之一是設計工具編譯的時間過長，這一方面是由于計算機處理器的性能并沒有質的飛躍，另外一方面是由于 FPGA 的大小隨著半導體制造工藝的發展而不斷增加。為了應對這個問題，一個有效的方法是使用多個處理器核心進行并行編譯。
這項成果旨在應對 FPGA CAD 流程中最慢的部分之一，即布局的并行化問題。在這個工作中，采用了幾項非常獨特而重要的方法。例如，這是目前首個，也是唯一一個嘗試對工業級布局軟件進行并行化的工作，并最終將成果轉化為成功的商用軟件。在此之前，盡管有很多工作試圖對布局算法做并行化處理，它們其實都是基于學術版本的算法，也就是說，這些工作并不需要應對海量的器件數據庫、復雜的時序分析、以及在商業版軟件中會遇到的各種細節問題。
此外，這項工作對算法的確定性（determinism）做了重要闡述。算法的確定性指，不管使用多少個處理器運行算法，它的結果都會是完全相同的。盡管在學術界中存在爭議，但在商業軟件中確定性對于復現結果以及調試都是不可或缺的。這項成果表明，需要做一系列細致的工作以保證算法的確定性。此外，這項成果也證明了這些工作對性能的損失很小。
這個工作還就內存架構對并行算法性能的影響進行了深入分析。值得注意的是，它表明不同的內存結構對算法性能的影響很大。
總體來說，這項成果對算法性能取得了很大的提升：在布局階段，使用 4 個處理器內核可以得到 2.2 倍的性能提升。對于大型設計，這樣的性能提升會節省好幾個小時的運行時間。在一個完整的 FPGA 編譯流程中，還存在著很多耗時的階段，這也意味著需要做更多的工作，才能最終將 FPGA 項目的編譯時間進一步縮短。但是，這個成果為實現這一目標做出了巨大的貢獻，也是其他后續工作值得參考的典范。
結語
這五個 FPGA 布局布線算法領域的重要工作，有的奠定了幾乎所有現代商用 FPGA 的布線算法基礎，有的大幅改進了 FPGA 布局、布線、時序優化等環節的算法性能，有的則對 FPGA CAD 軟件進行了跨越式提升。更重要的是，這些工作所采用的方法論、思維方式、前瞻性與實用性的統一、以及嚴謹的治學態度，都為之后的學術和工業研究樹立了最高的典范。
