黃志洪楊海鋼楊立群李 威江政泓林 郁（中國科學(xué)院電子學(xué)研究所 北京 100190）（中國科學(xué)院大學(xué) 北京 100049）

基于與非錐的新型FPGA邏輯簇互連結(jié)構(gòu)研究

黃志洪①②楊海鋼*①楊立群①②李 威①江政泓①②林 郁①
①（中國科學(xué)院電子學(xué)研究所 北京 100190）②（中國科學(xué)院大學(xué) 北京 100049）

該文針對新型FPGA可編程邏輯單元與非錐（And-Inverter Cone， AIC）的結(jié)構(gòu)特性，提出一系列方案以得到優(yōu)化的邏輯簇互連結(jié)構(gòu)，包括：移除輸出級交叉矩陣，單級反相交叉矩陣，低負(fù)載電路優(yōu)化，將反饋和輸出選擇功能分開，限制AIC輸出級數(shù)的基礎(chǔ)上移除中間級交叉矩陣，與LUT架構(gòu)進(jìn)行混合等。通過大量的實(shí)驗(yàn)，得出針對面積延時(shí)積最優(yōu)的AIC簇互連結(jié)構(gòu)，與Altera公司的FPGA芯片Stratix-IV結(jié)構(gòu)相比，該結(jié)構(gòu)邏輯功能簇本身面積減小9.06%， MCNC應(yīng)用電路集在基于優(yōu)化的AIC FPGA架構(gòu)上實(shí)現(xiàn)的平均面積延時(shí)積減小40.82%， VTR應(yīng)用電路集平均面積延時(shí)積減小17.38%；與原有的AIC結(jié)構(gòu)相比，簇面積減小23.16%， MCNC應(yīng)用電路集平均面積延時(shí)減小27.15%， VTR應(yīng)用電路集平均面積延時(shí)積減小15.26%。

與非錐（AIC）；AIC簇；單級反相交叉矩陣；簇互連結(jié)構(gòu)

1 引言

FPGA（Field-Programmable Gate Arrays）由于具有開發(fā)周期短、產(chǎn)品上市速度快、市場適應(yīng)能力強(qiáng)和不同工藝節(jié)點(diǎn)產(chǎn)品升級容易等優(yōu)點(diǎn)，使得其逐步在互聯(lián)網(wǎng)、通信、圖像處理諸多領(lǐng)域都得到了越來越廣泛的應(yīng)用，F(xiàn)PGA 也已從最早實(shí)現(xiàn)小型的邏輯電路轉(zhuǎn)向?qū)崿F(xiàn)大的應(yīng)用電路乃至整個數(shù)字系統(tǒng)［1，2］。當(dāng)前主流的商用FPGA器件的邏輯基本單元普遍采用基于查找表（Look Up Table， LUT）的邏輯結(jié)構(gòu)［3］，k位輸入查找表能夠?qū)崿F(xiàn) 22k種功能，其高度功能靈活性和可配置性是過去30年FPGA器件快速發(fā)展和廣泛應(yīng)用根本原因之一。然而，查找表功能的高靈活性也帶來了相應(yīng)的面積損耗代價(jià)，而且隨著芯片集成度越來越高，查找表邏輯結(jié)構(gòu)的可擴(kuò)展性制約逐漸成為FPGA器件發(fā)展的瓶頸。2012年，瑞士洛桑理工大學(xué) Parandeh等人［4，5］提出了一種基于與非錐（And-Inverter Cone， AIC）結(jié)構(gòu)的新型FPGA邏輯單元。得益于綜合工具的進(jìn)步，如abc中Boolean SAT 解決方案的采用［6］，使得電路在映射成為有向無環(huán)圖 AIG（And-Inverter Graph）時(shí)能夠在該圖不同深度上找到可復(fù)用的大量子圖，使得基于AIC結(jié)構(gòu)的FPGA能夠在最大程度上利用已有的邏輯單元，提高邏輯利用率。本文通過比較AIC與LUT的結(jié)構(gòu)特點(diǎn)，分析原AIC邏輯簇的不成熟和局限，改進(jìn)面向AIC的映射工具，建立完整的適用于AIC邏輯結(jié)構(gòu)的FPGA架構(gòu)評估CAD流程，并基于此提出適用于與非錐結(jié)構(gòu)特點(diǎn)的改進(jìn)AIC簇互連結(jié)構(gòu)設(shè)計(jì)方案，通過大量的仿真和實(shí)驗(yàn)，得到優(yōu)化的基于AIC結(jié)構(gòu)的邏輯簇。

2 AIC邏輯單元及其簇結(jié)構(gòu)

2.1 LUT的結(jié)構(gòu)局限及AIC的適用機(jī)理

LUT通過更改存儲單元中的數(shù)值來實(shí)現(xiàn)不同邏輯功能。如圖1所示，k位輸入的LUT需要通過一個“2k位選1”多路選擇器和2k位SRAM來實(shí)現(xiàn)編程功能，假定一個多路選擇器單元面積為Sm，一位SRAM面積為Ss，則基于LUT的邏輯單元電路的面積為SL=2k（Sm+Ss）。面積隨k增加呈指數(shù)增長。假定“2k位選1”多路選擇器通過主流芯片常用的基于4輸入選擇器的多級選擇實(shí)現(xiàn)，每級4輸入選擇器的延時(shí)為Tm，則總延時(shí)TL=kTm/2，延時(shí)隨k呈線性增長。

AIC邏輯單元電路及多級AIC錐結(jié)構(gòu)如圖2所示，K輸入AIC只需要通過log2k層次的與非選擇單元實(shí)現(xiàn)，假定每個與非錐單元面積為Sa，則總的面積 SA=（2D-1）Sa，其中D為K位輸入AIC實(shí)現(xiàn)所需的層次數(shù)，D=log2K，所以， SA=（K -1）Sa，邏輯單元電路總面積SA隨著輸入位數(shù)k線性增長。假定每級 AIC延時(shí)為 Ta，則總的延時(shí)為 TA= log2kTa，隨k呈對數(shù)增長。

圖1 4輸入查找表結(jié)構(gòu)

圖2 AIC邏輯單元以及改進(jìn)型可編程AIC單元

對于一個K輸入LUT，一共有N=2K個SRAM配置位，通過 2N不同的配置方案，可以實(shí)現(xiàn) 2N不同的功能。也就是說可以實(shí)現(xiàn)K輸入情況下的任意邏輯功能，有著極其強(qiáng)大的可編程能力。然而這種可編程能力也帶來了面積、延時(shí)和功耗的代價(jià)。以K=4的LUT結(jié)構(gòu)為例，一個4輸入的LUT通過不同的配置，能夠?qū)崿F(xiàn)一共216=65536種邏輯功能。以4輸入LUT實(shí)現(xiàn)VTR電路集中的各電路，一共采樣了411799個配置查找表，其中僅出現(xiàn)了942種不同的配置，占所有可能配置的1.437%，因此，查找表的可編程功能存在較大的冗余。此外，LUT只有一個輸出端，無法復(fù)用可配置資源。

根據(jù)最小項(xiàng)表達(dá)式和根據(jù)德摩根律［7］，我們可知，任何函數(shù)通過邏輯運(yùn)算都能夠改寫成為與非單元的組合表達(dá)式。因而可將任意的函數(shù)映射到AIC組合結(jié)構(gòu)上。AIC結(jié)構(gòu)中單個單元能夠?qū)崿F(xiàn)的功能雖然簡單，但是堆疊起來能實(shí)現(xiàn)的功能則變得豐富，其特有的多個中間層輸出結(jié)構(gòu)特點(diǎn)，使得本身的資源能夠得到充分的利用。

2.2 改進(jìn)型可編程AIC單元

AIC基本單元的結(jié)構(gòu)如圖2中BAE （Basic AIC Element）所示，為了使AIC基本單元在第1級即能

2.3 AIC簇結(jié)構(gòu)

一個或者多個不同層次的AIC通過互連形成的可編程邏輯模塊，稱之為 AIC簇。Altera公司StratixIV 中與之相對應(yīng)的是邏輯功能簇 LAB（Logic Array Block），為了驗(yàn)證基于 AIC結(jié)構(gòu)的FPGA的可行性并探索合適的AIC簇架構(gòu)，文獻(xiàn)［8］采用了全定制設(shè)計(jì)方法，在Cadence的Virtuso設(shè)計(jì)平臺上，采用 40 nm標(biāo)準(zhǔn)CMOS工藝，實(shí)現(xiàn)了Stratix-IV的邏輯功能簇［9］作為對比的參照基準(zhǔn)。其結(jié)構(gòu)如圖3所示，其中一個LAB由10個自適應(yīng)功能單元ALM（Adaptive Logic Module）組成。每個邏輯功能簇有52個輸入端，每個ALM模塊為6輸入查找表結(jié)構(gòu)，并有兩個輸出端口，一個LAB共20個輸出端［10］。

通過采用Cadence公司的仿真工具spectre對電路進(jìn)行仿真，獲得前仿性能參數(shù)，乘以經(jīng)驗(yàn)常數(shù)獲得后仿性能參數(shù)。與Stratix-IV芯片數(shù)據(jù)比對，關(guān)鍵模塊性能參數(shù)如6輸入查找表延時(shí)性能，D觸發(fā)器建立、保持時(shí)間、傳輸時(shí)間，整個邏輯簇面積等都與之基本相近［8，11］。

通過同樣的定制設(shè)計(jì)方法，根據(jù)文獻(xiàn)［4］設(shè)計(jì)了AIC簇的電路結(jié)構(gòu)，如圖4所示。該AIC簇結(jié)構(gòu)中，有3個層次為6級的AIC邏輯功能塊即AIC6。每個AIC6為對稱結(jié)構(gòu)，有64個輸入端。由通道通過連接盒提供 64個輸入引腳，通過輸入級交叉矩陣（input crossbar）模塊進(jìn)行選擇后為3個AIC6提供輸入。限定 AIC6從第 2層次開始提供輸出，即AIC6_2，共 31個輸出端。通過中間級交叉矩陣（middle crossbar）模塊進(jìn)行選擇，并提供寄存輸出和邏輯輸出，最后再通過輸出級交叉矩陣（output crossbar）模塊選擇得到20個輸出，最終送到全局互連通道資源上。

該AIC簇結(jié)構(gòu)中，有3個AIC6邏輯功能塊，每個AIC6為對稱結(jié)構(gòu)，有64個輸入端。由通道通過連接盒提供64個輸入引腳，通過輸入級交叉矩陣（input crossbar）模塊進(jìn)行選擇后為3個AIC6提供輸入。限定AIC6從第2層次開始提供輸出，共31個輸出端。通過中間級交叉矩陣模塊進(jìn)行選擇，并提供寄存輸出和邏輯輸出，最后再通過輸出級交叉矩陣模塊選擇得到20個輸出，最終送到全局互連通道資源上。其中，各級交叉矩陣的電路實(shí)現(xiàn)方式均采用二級陣列多路選擇器電路實(shí)現(xiàn)，與主流的Altera公司的stratix系列產(chǎn)品相同［11］。

通過仿真獲得性能參數(shù)，通過 VPR7.0流程［12］獲得面積和延時(shí)參數(shù)，與Stratix-IV FPGA相比，不同應(yīng)用電路采用AIC簇結(jié)構(gòu)實(shí)現(xiàn)有著不同的性能參數(shù)結(jié)果，部分電路結(jié)果較差，部分電路有更優(yōu)的面積和時(shí)延性能。

圖3 StratixIV邏輯功能簇結(jié)構(gòu)

然而，文獻(xiàn)［8］中的設(shè)計(jì)和評估仍有多方面的不足。深入分析AIC邏輯功能塊，與LUT結(jié)構(gòu)一個重要區(qū)別是，AIC邏輯功能塊有著更多的輸入和輸出，且由于不同層次眾多輸出的存在，可以復(fù)用功能模塊的中間節(jié)點(diǎn)輸出，從而大大提高了邏輯運(yùn)算單元的利用率和運(yùn)算密度，也有利于提升應(yīng)用電路的性能。然而眾多的輸入輸出在帶來豐富局部布線資源，提升布線靈活性的同時(shí)，也帶來了電路實(shí)現(xiàn)的面積和延時(shí)損耗。在設(shè)計(jì)中出現(xiàn)的輸入級、中間級、輸出級交叉矩陣模塊，即使是在較優(yōu)設(shè)計(jì)中，在整個AIC簇結(jié)構(gòu)中所占的面積為79.89%，延時(shí)占AIC簇總延時(shí)43.3%至70.7%。這些豐富的資源在實(shí)際電路應(yīng)用中存在冗余，導(dǎo)致AIC簇在面積和速度指標(biāo)上的惡化。同時(shí)，原有的面向AIC的映射工具存在一定的限制，如原AIC映射工具僅支持AIC每個層次都需輸出；AIC單元層次為D時(shí)，輸入端個數(shù)必須大于2D等。這些限制制約了AIC簇設(shè)計(jì)的靈活性，也導(dǎo)致AIC簇性能無法進(jìn)一步提升。

圖4 文獻(xiàn)［8］ AIC簇結(jié)構(gòu)

3 AIC簇互連結(jié)構(gòu)設(shè)計(jì)方案及其性能評估

3.1 面向AIC的映射工具及結(jié)構(gòu)評估流程

針對原有的映射工具存在的問題，基于開源的abc軟件［13］對新的工藝映射工具進(jìn)行了開發(fā)［14］?？删庉嫽成鋷斓囊?，使得應(yīng)用電路在映射階段就能更準(zhǔn)確建立映射代價(jià)函數(shù)，充分考慮到映射結(jié)果的代價(jià)，從而得到更符合要求的映射電路。AIC的獨(dú)立輸入個數(shù)，輸出層次、輸出個數(shù)的結(jié)構(gòu)參數(shù)可調(diào)節(jié)化處理，使得對AIC結(jié)構(gòu)參數(shù)的實(shí)驗(yàn)?zāi)芨鼮殪`活自由。

集成新的工藝映射工具，本文所采用的新的AIC結(jié)構(gòu)評估CAD流程如圖5所示：通過設(shè)定預(yù)選參數(shù)完成電路設(shè)計(jì)、仿真驗(yàn)證、電路及管子參數(shù)優(yōu)化獲得準(zhǔn)確的電路信息，并基于此統(tǒng)計(jì)不同類型的映射單元的面積、延時(shí)庫，提供電路基本結(jié)構(gòu)參數(shù)，完成面積和延時(shí)模型的建立。本文選取學(xué)術(shù)界

經(jīng)典的20個最大的MCNC電路［15］和VTR中的大部分電路［10］，除去個別規(guī)模過大非常耗時(shí)的電路，作為完整的測試電路集完成整個評估流程。本文電路設(shè)計(jì)平臺為 Cadence公司的 Virtuso，并通過spectre進(jìn)行仿真驗(yàn)證。

3.2 AIC簇互連結(jié)構(gòu)改進(jìn)方案

3.2.1輸出級交叉矩陣的移除和基于LUT的邏輯簇LAB的設(shè)計(jì)不同，基于與非元錐結(jié)構(gòu)的AIC簇為了使輸出能靈活跳轉(zhuǎn)到不同的通道線，在連接至通道資源之前設(shè)計(jì)了輸出級交叉矩陣。雖然該交叉矩陣提供了更為靈活的布線資源，但是實(shí)際電路中，由于通道之間的跳轉(zhuǎn)靈活性，輸出本身可以通過連接有限根不同的通道傳輸?shù)讲煌壿嬆K參與下一步運(yùn)算。輸出級交叉開關(guān)的存在，在占用面積開銷的同時(shí)，也為應(yīng)用電路帶來了延時(shí)代價(jià)。本文合理利用互連通道的可置換特點(diǎn)，有效利用布線資源靈活度，將輸出級交叉矩陣的功能部分上移至通道開關(guān)完成，嘗試移除輸出級交叉矩陣，即實(shí)現(xiàn)AIC簇結(jié)構(gòu)如圖6所示。

圖5 集成改進(jìn)映射工具的CAD結(jié)構(gòu)評估流程

圖6 移除輸出級交叉矩陣的AIC簇結(jié)構(gòu)

通過CAD流程實(shí)驗(yàn)，可得MCNC和VTR電路集在基于改進(jìn)AIC簇FPGA實(shí)現(xiàn)的關(guān)鍵路徑延時(shí)和面積，與Stratix-IV和文獻(xiàn)［8］FPGA14中的AIC結(jié)構(gòu)相比，延時(shí)和面積性能改進(jìn)比對如圖7所示。

移除輸出級交叉矩陣的AIC簇結(jié)構(gòu)與Stratix-IV結(jié)構(gòu)相比，在MCNC應(yīng)用電路和VTR應(yīng)用電路平均面積延時(shí)積分別減小了33.92%和 9.88%；與文獻(xiàn)［8］中AIC結(jié)構(gòu)相比，平均面積延時(shí)積分別減小了18.65%和 7.56%。

3.2.2單級反相交叉矩陣和低負(fù)載電路優(yōu)化Stratix-

IV中的各級交叉矩陣采用了經(jīng)典的二級多路選擇器來實(shí)現(xiàn)信號選擇和復(fù)用功能［11］，該結(jié)構(gòu)包含兩級反相器即緩沖器，中間通過上拉管實(shí)現(xiàn)因傳輸管帶來的電壓損失的電平恢復(fù)。這種設(shè)計(jì)的主要考慮因素是保持輸出信號和輸入信號的同相性，以及確保本級輸出有較好的驅(qū)動能力。

文獻(xiàn)［8］中邏輯功能簇在輸入級交叉矩陣和中間級交叉矩陣均采用了同樣的電路結(jié)構(gòu)。這種結(jié)構(gòu)中，為了很好地驅(qū)動連線上較大的負(fù)載，通常會采用尺寸較大的第2級反相器。其中，輸入級交叉矩陣中的多路選擇器最后一級反相器面積占該模塊總面積的 14.6%，中間級交叉矩陣中的多路選擇器最后一級反相器占該模塊總面積的16.1%。

圖7 移除輸出級交叉矩陣AIC簇結(jié)構(gòu)延時(shí)和面積比對

進(jìn)一步分析可以發(fā)現(xiàn)，AIC可編程邏輯電路在輸入端和輸出端均有著可通過 SRAM 進(jìn)行信號正反相選擇的特點(diǎn)，即不管是輸入級交叉矩陣還是中間級交叉矩陣是否能夠保持輸入信號和輸出信號的同相性，甚至在輸出級交叉矩陣未移除情況下，可編程AIC都能通過簡單的正反相選擇實(shí)現(xiàn)所需的功能。

而且，對輸入級交叉矩陣中的多路選擇器，每個多路選擇器僅需驅(qū)動 AIC6中的一個輸入端，中間級交叉矩陣中的多路選擇器，也同樣是一個多路選擇器僅需驅(qū)動一個寄存器和一個二選一選擇器，負(fù)載都在可控范圍內(nèi)，采用雙級反相器組成的緩沖器造成了很大的浪費(fèi)。192個多路選擇器組成的輸入級交叉矩陣，48個多路選擇器組成的中間級交叉矩陣，加上移除的輸出級交叉矩陣，在整個AIC簇模塊中占了79.89%的面積。

因此，本文提出了適用于AIC架構(gòu)的單級反相交叉矩陣（Inverter-Suffixed Crossbar， ISC），即由單級多路選擇器構(gòu)成，并針對不同級交叉矩陣，重新考慮面積和延時(shí)的折中，對所用到晶體管尺寸進(jìn)行仿真優(yōu)化，不僅大大減少了面積開銷，而且?guī)砹烁骷壗徊婢仃囆阅艿倪M(jìn)一步提升。在保持設(shè)計(jì)選擇器功能和個數(shù)不變的情況下，改進(jìn)后的輸入級交叉矩陣延時(shí)由文獻(xiàn)［8］中的203.2 ps變成113.28 ps，提升 44.3%，每個多路選擇器面積由文獻(xiàn)［8］中的212.9MWTA［3］（Minimum Width Transistor Area）變成188.75NWTA，減小11.37%。中間級交叉矩陣延時(shí)由文獻(xiàn)［8］中的 118.4 ps變成 76.72 ps，提升35.3%，每個多路選擇器面積由文獻(xiàn)［8］中的152.3NWTA變成104.2NWTA，減小27.5%。

文獻(xiàn)［8］中AIC輸出連接到中間級交叉矩陣時(shí)為了使信號有較好的上升和下降性能，在中間級交叉矩陣前設(shè)計(jì)了93個緩沖器A。信號通過2選1選擇器后送入輸出級交叉矩陣前，同樣加入了緩沖器B，以滿足其多負(fù)載的驅(qū)動需求。利用AIC運(yùn)算單元能夠?qū)崿F(xiàn)正反相選擇的特性，可將緩沖器A， B均換成一級反相器C， D實(shí)現(xiàn)。進(jìn)一步仿真優(yōu)化，適度增大AIC中的與非門以及二選一選擇器傳輸門的管子尺寸，可以增大驅(qū)動能力，因此進(jìn)一步移除反相器C，使得整體面積在減小的同時(shí)，延時(shí)得以進(jìn)一步減小。通過優(yōu)化負(fù)載電路后獲得的新AIC簇結(jié)構(gòu)如圖8所示，運(yùn)算模塊面積為2738.99NWTA，相比于文獻(xiàn)［8］中 AIC6運(yùn)算模塊的面積 3290.07NWTA，減少了16.7%， AIC不同級輸出延時(shí)平均減少14.71%。

通過實(shí)驗(yàn)，可得該結(jié)構(gòu)的電路延時(shí)和面積比對如圖9所示，與Stratix-IV結(jié)構(gòu)相比，在MCNC應(yīng)用電路和 VTR應(yīng)用電路平均面積延時(shí)積分別減小了36.03%和 13.7%；與文獻(xiàn)［8］中AIC結(jié)構(gòu)相比，平均面積延時(shí)積分別減小了21.25%和 11.48%。

3.2.3拆分輸出和反饋文獻(xiàn)［8］中AIC錐運(yùn)算結(jié)果通過中間級交叉矩陣后，通過2選1選擇器mux2s1來實(shí)現(xiàn)邏輯和寄存輸出的選擇功能，其輸出同時(shí)反饋回輸入級交叉矩陣，即文獻(xiàn)［8］中的AIC簇的反饋和輸出實(shí)際上共用2選1選擇器的輸出，這種設(shè)計(jì)雖然節(jié)省整體實(shí)現(xiàn)面積，但如果一旦有AIC錐運(yùn)算結(jié)果同時(shí)需作為輸出和反饋，且輸出和反饋分別需要寄存和組合邏輯輸出應(yīng)用時(shí)，便會增加布線難度。同時(shí)，由于文獻(xiàn)［8］中緩沖器B需要反饋接入輸入級交叉矩陣中 96個多路選擇器的同時(shí)驅(qū)動多根通道線，導(dǎo)致緩沖器B的尺寸較大，且延時(shí)性能較差。

圖8 采用單級反相交叉矩陣和低負(fù)載電路優(yōu)化后AIC簇結(jié)構(gòu)

本文提出將AIC簇的反饋和輸出分開，不再共用2選1選擇器的輸出，同時(shí)由于寄存器單元的面積較大，為了避免寄存器單元數(shù)目的增加，采用了共用寄存器的方案，僅增加2選1選擇器數(shù)目，且通過兩個反相器輸出，實(shí)現(xiàn)架構(gòu)如圖10所示。采用該結(jié)構(gòu)，雖然在電路實(shí)現(xiàn)面積上有所增大，但此時(shí)反饋和輸出都能獨(dú)立靈活地選用組合邏輯輸出和寄存輸出，且由于將驅(qū)動拆分成兩個反相器，負(fù)載近似減半，管子尺寸可以減小的同時(shí)提高了反相器的延時(shí)性能。通過 VTR流程實(shí)驗(yàn)，統(tǒng)計(jì)可得電路延時(shí)和面積比對如圖11所示。采用拆分輸出和反饋后的AIC簇結(jié)構(gòu)與Stratix-IV結(jié)構(gòu)相比，在MCNC應(yīng)用電路和 VTR應(yīng)用電路平均面積延時(shí)積分別減小了39.69%和14.75%；與文獻(xiàn)［8］中AIC結(jié)構(gòu)相比，平均面積延時(shí)積分別減小了25.75%和12.56%。3.2.4中間級交叉矩陣采用全連通交叉矩陣實(shí)現(xiàn)文獻(xiàn)［8］中AIC簇的中間級交叉矩陣采用的結(jié)構(gòu)為最小化交叉矩陣（minimal crossbar）［16］，即采用48個輸入個數(shù)為16，輸出個數(shù)為1的多路選擇器mux16s1實(shí)現(xiàn)。本文嘗試采用全連通交叉矩陣（full crossbar）結(jié)構(gòu)，即采用48個輸入個數(shù)為31，輸出個數(shù)為1的多路選擇器mux31s1實(shí)現(xiàn)，這種結(jié)構(gòu)在簇實(shí)現(xiàn)面積

圖9 采用單級反相交叉矩陣和低負(fù)載電路優(yōu)化后AIC簇結(jié)構(gòu)延時(shí)比對

圖10 拆分輸出和反饋的AIC簇結(jié)構(gòu)

圖11 拆分輸出和反饋的AIC簇結(jié)構(gòu)延時(shí)比對

上變得大，但提供了更高的布線靈活性。通過 CAD流程，可得結(jié)果如下：采用全連通交叉矩陣結(jié)構(gòu)比采用最小化交叉矩陣結(jié)構(gòu) MCNC

應(yīng)用電路平均關(guān)鍵路徑延時(shí)減小 5.54%，平均面積增大2.98%，面積延時(shí)積減小2.72%， VTR應(yīng)用電路平均關(guān)鍵路徑延時(shí)減小 4.02%，平均面積增大

2.02%，面積延時(shí)積減小2.07%。即可知，采用全連通交叉矩陣結(jié)構(gòu)比最小化交叉矩陣結(jié)構(gòu)性能可獲得更高的提升。

3.2.5限制AIC6的輸出級數(shù)文獻(xiàn)［8］中AIC簇的設(shè)計(jì)受限于原AIC映射工具的約束，一旦選定AIC錐的級數(shù)D， AIC錐輸出個數(shù)即為 2（D-2）- 1，并因此制約了AIC簇結(jié)構(gòu)的探索自由度。本文中，由于映射工具的改進(jìn)，AIC錐的輸出級數(shù)能夠自由設(shè)定，考慮到實(shí)際映射結(jié)果中存在大量層數(shù)為2級和3級的輸出，本文嘗試將AIC錐的輸出限制為3級以上輸出，即1級和2級均不再提供輸出，用AIC6_3進(jìn)行標(biāo)示。AIC錐級數(shù)為 D時(shí)，輸出個數(shù)為2（D-2）- 1，即AIC6_3的輸出個數(shù)為15個。

本文提出在輸出交叉矩陣移除的基礎(chǔ)上，進(jìn)一步將中間級交叉矩陣移除。該結(jié)構(gòu)由于中間級交叉矩陣的移除，可以進(jìn)一步減少整個AIC簇面積的同時(shí)，減少AIC錐運(yùn)算結(jié)果輸出和反饋所需經(jīng)過的模塊，進(jìn)一步減小延時(shí)。改進(jìn)AIC簇結(jié)構(gòu)如圖12所示。

本文同時(shí)嘗試對AIC簇中的3個AIC6中的2個、1個限制其為3級以上輸出，其它仍保持2級以上輸出，分別通過前文所述的 CAD流程，最終可得3AIC6_3面積和延時(shí)結(jié)果最好，電路面積和延時(shí)比對如圖13所示。

與Stratix-IV結(jié)構(gòu)相比，該結(jié)構(gòu)在MCNC應(yīng)用電路和 VTR應(yīng)用電路平均面積延時(shí)積分別減小了40.82%和17.38%；與文獻(xiàn)［8］中AIC結(jié)構(gòu)相比，平均面積延時(shí)積分別減小了27.15%和 15.26%。

3.3 改進(jìn)結(jié)構(gòu)實(shí)驗(yàn)結(jié)果分析和比較

通過 VTR流程對上述結(jié)構(gòu)進(jìn)行評估，統(tǒng)計(jì)各結(jié)構(gòu)的實(shí)現(xiàn)結(jié)果如表1所示，其中A表示面積減少的百分比，D表示關(guān)鍵路徑延時(shí)減小的百分比，P表示面積延時(shí)積減小的百分比。各結(jié)構(gòu)都是在前一結(jié)構(gòu)基礎(chǔ)上進(jìn)一步嘗試和探索，但各結(jié)構(gòu)又有自身特點(diǎn)。相比于采用單級反相交叉矩陣的AIC架構(gòu)2，拆分反饋和輸出后的AIC架構(gòu)3由于AIC簇本身的面積增大，因此在實(shí)現(xiàn)不同應(yīng)用電路集的面積性能上，改善較少或者基本相近，但延時(shí)性能在不同應(yīng)用電路集上卻基本更優(yōu)。相比于拆分反饋和輸出后仍保持2級以上輸出的AIC結(jié)構(gòu)3，限制AIC輸出級數(shù)為3級以上輸出的AIC結(jié)構(gòu)4雖然在MCNC電路集延時(shí)性能上改善較少，但由于其面積更小，從而面積延時(shí)積改善指標(biāo)上更具優(yōu)勢，而且在VTR電路集上性能更好。因此從面積延時(shí)積角度考慮實(shí)驗(yàn)結(jié)果，限制AIC輸出級數(shù)為3級以上輸出AIC結(jié)構(gòu)4最優(yōu)。

圖12 限制AIC6的輸出級數(shù)的AIC簇結(jié)構(gòu)

圖13 限制AIC6的輸出級數(shù)的AIC簇結(jié)構(gòu)延時(shí)比對

本文同時(shí)將輸出限制為3級以上的AIC6_3結(jié)構(gòu)4和stratix-IV的LUT結(jié)構(gòu)混合，形成新的FPGA架構(gòu)5進(jìn)行試驗(yàn)。由于VTR工具的限制，僅能實(shí)現(xiàn)對列的改動，因此本文仍采用文獻(xiàn)［4］中按列混合的方式，即AIC簇和LAB簇的比例為1:3，在每3列stratix-IV的LUT結(jié)構(gòu)的LAB簇中間插入一列AIC簇。

通過 CAD流程，與 Stratix-IV結(jié)構(gòu)相比，MCNC應(yīng)用電路在該混合架構(gòu)上實(shí)現(xiàn)時(shí)平均面積延時(shí)積減小40.12%， VTR應(yīng)用電路平均面積延時(shí)積減小8.79%；與文獻(xiàn)［8］中AIC結(jié)構(gòu)相比，MCNC應(yīng)用電路平均面積延時(shí)積減小26.28%， VTR應(yīng)用電路平均面積延時(shí)積減小6.44%。所得結(jié)果與純AIC6_3結(jié)構(gòu)相比，所得的電路性能并沒有得到進(jìn)一步改善，原因是由于本文映射時(shí)的所采用的代價(jià)函數(shù)將延時(shí)性能作為第一要素考慮導(dǎo)致的。

表1 不同改進(jìn)結(jié)構(gòu)與Stratix-IV LUT以及文獻(xiàn)［8］中AIC結(jié)構(gòu)實(shí)現(xiàn)性能比較（%）

4 結(jié)論

本文深入剖析AIC與LUT的結(jié)構(gòu)特點(diǎn)，通過集成改進(jìn)型面向AIC的映射工具，建立完整的適用于基于AIC邏輯結(jié)構(gòu)的FPGA架構(gòu)評估CAD流程?；诖耍槍IC結(jié)構(gòu)特點(diǎn)，提出移除輸出級交叉矩陣，單向交叉矩陣，優(yōu)化負(fù)載電路，并提出將反饋和輸出選擇功能分開，限制AIC輸出級數(shù)的基礎(chǔ)上移除中間級交叉矩陣，并與LUT架構(gòu)進(jìn)行混合等AIC簇互連設(shè)計(jì)改進(jìn)方案，經(jīng)過大量實(shí)驗(yàn)，最終得出針對面積延時(shí)積優(yōu)化的AIC簇互連結(jié)構(gòu)。

相比于傳統(tǒng)Stratix-IV基于LUT簇結(jié)構(gòu)，文獻(xiàn)［8］所提出的AIC簇結(jié)構(gòu)在部分電路延時(shí)性能上有一定優(yōu)勢，但其面積過大，限制了其性能的提升。本文提出的優(yōu)化結(jié)構(gòu)在邏輯功能簇本身實(shí)現(xiàn)面積上相比文獻(xiàn)［8］中的 AIC簇結(jié)構(gòu)減少 23.16%，相比于Stratix-IV LUT簇結(jié)構(gòu)減少9.06%，從而使得基于AIC結(jié)構(gòu)FPGA邏輯簇在一定程度上展現(xiàn)出其潛在的優(yōu)勢。

與Stratix-IV結(jié)構(gòu)相比，本文得到的優(yōu)化結(jié)構(gòu)實(shí)現(xiàn) MCNC應(yīng)用電路時(shí)平均面積延時(shí)積減小了40.82%， VTR應(yīng)用電路平均面積延時(shí)積減小了17.38%；與文獻(xiàn)［8］中AIC簇結(jié)構(gòu)相比，MCNC應(yīng)用電路平均面積延時(shí)積減小了27.15%， VTR應(yīng)用電路平均面積延時(shí)積減小了15.26%。

［1］ Kuon I and Rose J. Measuring the gap between FPGAs and ASICs［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2007， 26（2）: 203-215.

［2］ Mayer-Lindenberg F. Design and application of a scalable embedded systems’ architecture with an FPGA based operating infrastructure［C］. 9th Euromacro Conference on Digital System Design， Croatia， 2006: 189-196.

［3］ Betz V， Rose J， and Marquardt A. Architecture and CAD for Deep-Submicron FPGAs［M］. Netherlands， Kluwer Academic Publishers， 1999: 15-20.

［4］ Parandeh-Afshar H， Benbihi H， Novo D， et al.. Rethinking FPGAs: elude the flexibility excess of LUTs with and-inverter cones［C］. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays， Monterey，2012: 119-128.

［5］ Parandeh-Afshar H， Zgheib G， Novo D， et al.. Shadow and-inverter cones［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL）， Porto，2013: 1-4.

［6］ Mishchenko A， Chatterjee S， and Brayton R. DAG-aware AIG rewriting: a fresh look at combinational logic synthesis［C］. Proceedings of the 43rd Design Automation Conference，San Francisco， 2006: 532-536.

［7］ 埃伯哈德， 蔡德勒等， 編. 李文林， 等譯.《數(shù)學(xué)指南-實(shí)用數(shù)學(xué)手冊》［M］. 北京: 科學(xué)出版社， 2012: 875.

［8］ Zgheib G， Yang L， Huang Z， et al.. Revisiting and-inverter cones［C］. Proceedings of the 2014 ACM/SIGDA international symposium on Field-Programmable Gate Arrays. ACM，Monterey， 2014: 45-54.

［9］ Altera Corporation. Stratix IV Device Handbook， vols.1 and 2.［OL］ https://www.altera.com/content/dam/altera-www /global/en_US/pdfs/literature/hb/strastr-iv/stratix4_hand book.pdf， 2012.

［10］ Murray K E， Whitty S， Liu S， et al.. Titan: enabling large and complex benchmarks in academic CAD［C］. Proceedings of the 23rd International Conference on Field-Programmable Logic and Applications， Porto， Portugal， 2013: 1-8.

［11］ Lewis D， Ahmed E， Baeckler G， et al.. The stratix II logic and routing architecture［C］. Proceedings of the 2005 ACM/ SIGDA 13th ACM International Symposium on Field-Programmable Gate Arrays， Monterey， 2005: 14-20.

［12］ Luu J， Goeders J， Wainberg M， et al.. VTR 7.0: Next generation architecture and CAD system for FPGAs［J］. ACM Transactions on Reconfigurable Technology and Systems（TRETS）， 2014， 7（2）: 6:1-6:30.

［13］ Brayton R and Mishchenko A. ABC: an academic industrialstrength verification tool［C］. Computer Aided Verification，Edinburgh， 2010: 24-40.

［14］ 江政泓， 林郁， 黃志洪， 等. 面向AIC結(jié)構(gòu)的FPGA映射工具［J］. 電子與信息學(xué)報(bào)， 2015， 37（7）: 1769-1773. Jiang Zheng-hong， Lin Yu， Huang Zhi-hong， et al.. Mapper for AIC-based FPGAs［J］. Journal of Electronics & Information Technology， 2015， 37（7）: 1769-1773.

［15］ Yang S. Logic synthesis and optimization benchmarks User Guide， version 3.0［OL］. http://ddd.fit.cvut.cz/prj/ Benchmarks/LGSynth91.pdf， 1991.

［16］ Lemieux G， Leventis P， and Lewis D. Generating highlyroutable sparse crossbars for PLDs［C］. Proceedings of the 8th ACM/SIGDA International Symposium on FPGA， Monterey，California， 2000: 155-64.

黃志洪： 男，1984年生，博士生，助理研究員，研究方向?yàn)榭删幊踢壿嫿Y(jié)構(gòu)設(shè)計(jì)、嵌入式存儲器通道結(jié)構(gòu).

楊海鋼： 男，1960年生，研究員，研究方向?yàn)閿?shù)?；旌闲盘柤呻娐吩O(shè)計(jì)、超大規(guī)模集成電路設(shè)計(jì)等.

楊立群： 女，1989年生，博士生，研究方向?yàn)镕PGA架構(gòu)開發(fā)、FPGA CAD工具開發(fā).

李 威： 女，1983 年生，助理研究員，研究方向?yàn)榭删幊绦酒Y(jié)構(gòu)設(shè)計(jì).

江政泓： 男，1990年生，博士生，研究方向?yàn)镕PGA架構(gòu)開發(fā)、FPGA的映射算法.

林 郁： 男，1982年生，助理研究員，研究方向?yàn)镕PGA的CAD輔助設(shè)計(jì)、FPGA高層綜合.

Interconnect Architecture of a Novel And-inverter Cone Based FPGA Cluster

Huang Zhi-hong①②Yang Hai-gang①Yang Li-qun①②
Li Wei①Jiang Zheng-hong①②Lin Yu①①
①（Institute of Electronics， Chinese Academy of Sciences， Beijing 100190， China）
②（University of Chinese Academy of Sciences， Beijing 100049， China）

With deep understanding of the characteristics of And-Inverter Cone （AIC）， an alternative logic element for FPGA， a series of improvements are proposed to get an optimized interconnect architecture inside the logic cluster. The enhancements include removing the output crossbar， adopting Inverter-Suffixed Crossbar （ISC），optimizing the low load circuit path， dividing the feedback and output function， restricting the output level of AIC and removing the middle crossbar， mixing with the LUT element. An optimized architecture is derived through amounts of experiments. Compared to Stratix IV， Altera， the area of cluster is reduced by 9.06%.Implemented on the new AIC architecture， the average area-delay product of MCNC benchmarks are reduced by 40.82%； the average area-delay product of VTR benchmarks is reduced by 17.38%. Compared to the original AIC-based FPGA architecture， the area of AIC cluster is reduced by 23.16%. Implemented on the new AIC architecture， the average area-delay product of MCNC benchmarks are reduced by 27.15%； the average area-delay product of VTR benchmarks are reduced by 15.26%.

And-Inverter Cone （AIC）； AIC cluster； Inverter-Suffixed Crossbar （ISC）； Cluster interconnect architecture

The National Natural Science Foundation of

TN402

A

1009-5896（2015）12-3030-11

10.11999/JEIT150249

2015-02-12；改回日期：2015-09-16；網(wǎng)絡(luò)出版：2015-11-01

*通信作者：楊海鋼 yanghg@mail.ie.ac.cn

國家自然科學(xué)基金（61271149）

China （61271149）