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

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

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

這 25 個(gè)研究成果按研究領(lǐng)域分為架構(gòu)、EDA 工具、電路、應(yīng)用等大類，每項(xiàng)成果都由一名該領(lǐng)域的頂級(jí)學(xué)者做推介。接下來(lái)，我將在幾篇文章里，分別介紹這這些改變了 FPGA 發(fā)展進(jìn)程的重要研究成果。本文是布局布線算法篇。關(guān)于 FPGA 架構(gòu)領(lǐng)域的重要?jiǎng)?chuàng)新，請(qǐ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ā)表時(shí)間：1995 年

推介人：Sinan Kaptanoglu（Microsemi 公司）

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

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

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

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

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

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

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

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

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

作者：Vaughn Betz, Jonathan Rose

發(fā)表時(shí)間：1999 年

推介人：Carl Ebeling（華盛頓大學(xué)）

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

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

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

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

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

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

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

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

作者：Vaughn Betz, Jonathan Rose

發(fā)表時(shí)間：2000 年

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

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

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

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

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

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

英文名：Timing-driven placement for FPGAs

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

發(fā)表時(shí)間：2000 年

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

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

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

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

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

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

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

05   在商用計(jì)算機(jī)上的高質(zhì)量、確定性的 FPGA 并行布局算法
一句話總結(jié)：利用多核處理器顯著降低 FPGA 項(xiàng)目編譯時(shí)間的標(biāo)志性工作

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

作者：Adrian Ludwin, Vaughn Betz, Ketan Padalia

發(fā)表時(shí)間：2008 年

推介人：Jonathan Rose

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

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

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

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

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

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