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

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

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

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

01

尋路者：基于協(xié)商的 FPGA 性能優(yōu)化布線算法

一句話總結(jié)：歷史最強(qiáng) FPGA 布線算法，沒有之一。

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

作者：Larry McMurchie， Carl Ebeling

發(fā)表時間：1995 年

推介人：Sinan Kaptanoglu（Microsemi 公司）

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

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

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

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

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

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

02

FPGA 布線架構(gòu)：分段與緩沖及其對速度和邏輯密度的優(yōu)化

一句話總結(jié)：對 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（華盛頓大學(xué)）

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

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

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

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

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

03

從高層描述自動生成 FPGA 布線架構(gòu)

一句話總結(jié)：通過自動處理 FPGA 布線架構(gòu)研究中繁瑣的部分，推進(jìn)了整個研究領(lǐng)域的跨越式發(fā)展。

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

作者：Vaughn Betz， Jonathan Rose

發(fā)表時間：2000 年

推介人：Scott Hauck（華盛頓大學(xué)）

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

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

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

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

04

時序驅(qū)動的 FPGA 布局算法

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

英文名：Timing-driven placement for FPGAs

作者：Alexander （Sandy） Marquardt， Vaughn Betz， Jonathan Rose

發(fā)表時間：2000 年

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

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

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

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

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

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

05

在商用計算機(jī)上的高質(zhì)量、確定性的 FPGA 并行布局算法

一句話總結(jié)：利用多核處理器顯著降低 FPGA 項(xiàng)目編譯時間的標(biāo)志性工作

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

作者：Adrian Ludwin， Vaughn Betz， Ketan Padalia

發(fā)表時間：2008 年

推介人：Jonathan Rose

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

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

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

這個工作還就內(nèi)存架構(gòu)對并行算法性能的影響進(jìn)行了深入分析。值得注意的是，它表明不同的內(nèi)存結(jié)構(gòu)對算法性能的影響很大。

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

結(jié)語

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