基于分解的多路選擇器工藝映射方法設(shè)計(jì)

謝尚鑾，惠 鋒，劉 佩，王晨陽(yáng)，張 立

（無(wú)錫中微億芯有限公司，江蘇無(wú)錫 214072）

1 引言

FPGA 芯片以配置靈活、開(kāi)發(fā)周期短等特點(diǎn)而被廣泛應(yīng)用于圖像處理、汽車電子、人工智能等領(lǐng)域，其設(shè)計(jì)流程包括綜合、裝箱、布局布線和碼流生成等環(huán)節(jié)。工藝映射是綜合的重要步驟，可將由寄存器傳輸級(jí)（RTL）描述文件解析所得的邏輯單元與芯片上的各類器件進(jìn)行綁定以獲得工藝網(wǎng)表，是物理實(shí)現(xiàn)數(shù)字系統(tǒng)的關(guān)鍵。

查找表（LUT）是FPGA 的主要邏輯資源，K 輸入LUT 可以實(shí)現(xiàn)任意K 變量的邏輯函數(shù)，針對(duì)僅由LUT與時(shí)序器件組成的同構(gòu)FPGA，已存在成熟的結(jié)構(gòu)化映射算法[1-3]，相關(guān)工作以動(dòng)態(tài)規(guī)劃算法為基礎(chǔ)，通過(guò)分割枚舉、分割排序、最佳分割選取等步驟用K-可行錐集覆蓋邏輯網(wǎng)表，最后將每個(gè)K-可行的錐綁定到K輸入LUT。隨著設(shè)計(jì)水平的不斷提高，商業(yè)FPGA 通過(guò)在片上嵌入多種專用功能模塊來(lái)縮小與專用集成電路在性能上的差距，其中既有與LUT 一起集成于可編程邏輯塊（CLB）的專用多路選擇器與進(jìn)位鏈，也有集成在FPGA 特定位置的存儲(chǔ)器與數(shù)字信號(hào)處理器硬核[4]。為了支持異構(gòu)FPGA 的工藝映射，研究人員做了諸多努力。在工業(yè)界，F(xiàn)PGA 三大廠商Xilinx、Altera和Lattice 提供的綜合工具不公開(kāi)相關(guān)映射技術(shù)。在學(xué)術(shù)界，JAMIESON 等[4]介紹了異構(gòu)FPGA 的層次化映射流程；路寶珠等[5-6]通過(guò)區(qū)域重組技術(shù)打破專用功能模塊與LUT 的層次邊界，減小了映射解的面積和延時(shí)開(kāi)銷，并且實(shí)現(xiàn)了對(duì)專用進(jìn)位鏈的映射支持；徐宇等[7]提出存儲(chǔ)單元的優(yōu)化映射算法，合理利用片上存儲(chǔ)器滿足用戶的存儲(chǔ)需求。

目前，公開(kāi)的面向異構(gòu)FPGA 的多路選擇器工藝映射方法較少。多路選擇器是數(shù)字系統(tǒng)的常見(jiàn)元件，在低功耗應(yīng)用領(lǐng)域更是扮演了主要角色，但其邏輯資源開(kāi)銷大[8-10]，若可高效地將該類單元映射至專用功能模塊，將有助于節(jié)省芯片邏輯資源并加速數(shù)據(jù)交換。本文針對(duì)Xilinx 公司的Virtex-7 系列FPGA 架構(gòu)[11]，提出一種基于分解的多路選擇器工藝映射方法。

2 基礎(chǔ)知識(shí)介紹

2.1 多路選擇器

多路選擇器一般由RTL 描述文件的“case”、“if-else”及有限狀態(tài)機(jī)等分支控制語(yǔ)句解析得到，每個(gè)單元的N 個(gè)待選信號(hào)、K（K=lb N）位選擇信號(hào)及各路信號(hào)與其他單元的連接關(guān)系等均可被識(shí)別。K 位選擇信號(hào)可形成2K個(gè)條件分支，設(shè)計(jì)者利用其中N 個(gè)分支對(duì)待選信號(hào)進(jìn)行一對(duì)一綁定以實(shí)現(xiàn)選擇輸出[10]，若N=2K，所有條件分支均被利用，此時(shí)稱多路選擇器是規(guī)則的；否則，稱多路選擇器是不規(guī)則的。

將每個(gè)多路選擇器的選擇信號(hào)從最低位至最高位的順序編碼為s0，s1，...，sK-1；同時(shí)將待選信號(hào)按照對(duì)應(yīng)選擇信號(hào)組成的二進(jìn)制碼值升序排列，依次編碼為i0，i1，...，iN-1。為了表述方便，本文將N 選1 多路選擇器簡(jiǎn)稱為N 選1 單元。

在保證邏輯等價(jià)的前提下，N 選1 單元可分解為2 層的樹(shù)狀結(jié)構(gòu)，第1 層為1 個(gè)T 選1 單元，2≤T≤N-1；第2 層為T 個(gè)子單元U0，U1，...，UT-1，對(duì)應(yīng)待選信號(hào)數(shù)量為m0，m1，...，mT-1，每個(gè)子單元的輸出為T 選1 單元的1 個(gè)待選信號(hào)且m0+m1+...+mT-1=N，對(duì)于其中任一單元Ui，2≤mi≤N-1；第2 層的各子單元可繼續(xù)遞歸分解，形成層數(shù)更多、單元粒度更細(xì)的多路選擇器樹(shù)[8-10,12-14]。

2.2 LUT 與專用多路選擇器的集成方式

Virtex-7 芯片的每個(gè)CLB 包含2 片Slice，而每片Slice 又包含4 個(gè)6 輸入LUT、8 個(gè)時(shí)序器件、1 個(gè)專用進(jìn)位鏈以及兩級(jí)專用多路選擇器。為了便于觀察，完整的Slice 結(jié)構(gòu)未畫出，僅展示LUT 與專用多路選擇器的集成方式，LUT 與專用多路選擇器的集成方式如圖1 所示。與LUT 相連的2 個(gè)1 級(jí)多路選擇器為MUXF7，與2 個(gè)MUXF7 相連的2 級(jí)多路選擇器為MUXF8，MUXF7/MUXF8 均能接受外部輸入作為選擇信號(hào)，但MUXF7 僅能接受前向2 個(gè)LUT 的輸出作為待選信號(hào)，MUXF8 僅能接受前向2 個(gè)MUXF7 的輸出作為待選信號(hào)。

圖1 LUT 與專用多路選擇器的集成方式[8]

3 多路選擇器工藝映射實(shí)現(xiàn)

在異構(gòu)FPGA 的設(shè)計(jì)流程中，解析所得多路選擇器、存儲(chǔ)器等單元不參與邏輯優(yōu)化而直接實(shí)現(xiàn)工藝映射，以避免邊界知識(shí)丟失[5-6]。該操作不僅可為專用功能模塊的利用提供基礎(chǔ)，還可減輕邏輯優(yōu)化環(huán)節(jié)的壓力從而支持對(duì)超大規(guī)模電路的處理，但其難點(diǎn)在于為相關(guān)單元尋找對(duì)應(yīng)的“最優(yōu)映射方案”?；诖?，本文為多路選擇器設(shè)計(jì)了一種有效的映射方法。

3.1 規(guī)則單元的映射步驟設(shè)計(jì)

利用Slice 內(nèi)部附加的專用多路選擇器可優(yōu)化映射8 選1 單元與16 選1 單元，其中8 選1 單元僅需要2 個(gè)LUT 與1 個(gè)MUXF7，16 選1 單元僅需要4 個(gè)LUT、2 個(gè)MUXF7 與1 個(gè)MUXF8，而4 選1 單元直接映射至LUT 即可[8]，相關(guān)單元的優(yōu)質(zhì)工藝網(wǎng)表如圖2 所示。已知規(guī)則的2K選1 單元可分解成1 個(gè)2i選1單元與2i個(gè)2j選1 單元（i+j=K，i≥1，j≥1），若選擇上述3 類單元為基準(zhǔn)單元并保存相應(yīng)工藝網(wǎng)表作為模板，再將2K選1 單元分解為若干層基準(zhǔn)單元并由模板實(shí)現(xiàn)映射，有助于提升映射結(jié)果的性能。需要說(shuō)明的是，解析所得2 選1 單元僅3 個(gè)輸入，若將其直接映射至LUT 會(huì)造成邏輯資源的浪費(fèi)，因此該類單元交由邏輯優(yōu)化環(huán)節(jié)處理，不在本文方法作用域中。

圖2 相關(guān)單元的優(yōu)質(zhì)工藝網(wǎng)表

本文所設(shè)計(jì)的2K選1 單元映射方式為規(guī)則映射，具體步驟如下。

（1）已知2K選1 單元的選擇信號(hào)編碼為s0，s1，...，sK-1，待選信號(hào)編碼為i0，i1，...，iN-1，將其作為目標(biāo)單元，分解為1 個(gè)2i選1 單元與2i個(gè)16n選1 單元，i=K%4，n=K/4。若i=0，目標(biāo)單元直接形成16n選1 單元，不需分解；否則，將目標(biāo)單元的待選信號(hào)按編碼升序等分為2i組，每組的2K-i個(gè)待選信號(hào)分別作為一個(gè)16n選1單元的待選信號(hào)，并以2i個(gè)16n選1 單元的輸出作為2i選1 單元的待選信號(hào)；將目標(biāo)單元從低至高的（K-i）位選擇信號(hào)s0，s1，...，sK-i-1同時(shí)作為所有16n選1 單元的選擇信號(hào)，并以sK-i，sK-i＋1，...，sK-1作為2i選1 單元的選擇信號(hào)。此時(shí)若n=1，直接跳轉(zhuǎn)步驟（3）；否則，將所有16n選1 單元依次傳入步驟（2）以執(zhí)行遞歸分解操作，之后轉(zhuǎn)到步驟（3）。

（2）將16n選1 單元作為目標(biāo)單元分解為1 個(gè)16選1 單元和16 個(gè)16n-1選1 單元。將目標(biāo)單元的待選信號(hào)按照編碼升序等分為16 組，每組的24(n-1)個(gè)待選信號(hào)分別作為一個(gè)16n-1選1 單元的待選信號(hào)，并以16個(gè)16n-1選1 單元的輸出作為16 選1 單元的待選信號(hào)；將目標(biāo)單元從低至高的4 (n-1) 位選擇信號(hào)s0，s1，...，s4(n-1)-1同時(shí)作為所有16n-1選1 單元的選擇信號(hào)，并以s4(n-1)，s4(n-1)+1，s4(n-1)+2，s4n-1作為16 選1 單元的選擇信號(hào)?；谶f歸原則，將每個(gè)16n-1選1 單元作為新的目標(biāo)單元繼續(xù)分解直至n=2。

（3）調(diào)用模板實(shí)現(xiàn)分解所得子單元的映射，分解出的2 選1 單元直接映射為L(zhǎng)UT3。

3.2 不規(guī)則單元的映射步驟設(shè)計(jì)

3 選1 單元僅5 個(gè)輸入信號(hào)，可直接映射至LUT；而對(duì)于N≥5 的不規(guī)則單元，本文將其分解為若干個(gè)規(guī)則子單元并送入規(guī)則映射流程，繼續(xù)借助模板實(shí)現(xiàn)映射。以選擇信號(hào)編碼為s0，s1，...，sK-1，待選信號(hào)編碼為i0，i1，...，iN-1的不規(guī)則單元為目標(biāo)，本文為之設(shè)計(jì)的映射步驟如下。

（1）若目標(biāo)單元N-2(K-1)=1，跳轉(zhuǎn)步驟（2）；否則，跳轉(zhuǎn)步驟（3）。

（2）將目標(biāo)單元分解為2 選1 單元A 與2(K-1)選1單元B，以i0，i1，...，i2(K-1)-1作為B 的待選信號(hào)，以s0，s1，...，sK-2作為其選擇信號(hào)；以B 的輸出與iN-1作為A的待選信號(hào)，以sK-1作為其選擇信號(hào)。執(zhí)行B 的規(guī)則映射，結(jié)束分解。

（3）將目標(biāo)單元分解為2 選1 單元A、2(K-1)選1 單元B 及N-2(K-1)選1 單元C，其中，以i0，i1，...，i2(K-1)-1作為B 的待選信號(hào)，以s0，s1，...，sK-2作為其選擇信號(hào)；以B、C 的輸出作為A 的待選信號(hào)，以sK-1作為其選擇信號(hào)；令R=lb[N-2(K-1)]，以i2（K-1），i2（K-1）+1，...，iN-1作為C 的待選信號(hào)，以s0，s1，...，s「R?-1作為其選擇信號(hào)。執(zhí)行B 的規(guī)則映射，若此時(shí)R≤2，將C 直接映射至LUT，結(jié)束分解；若R＞2 且=R，執(zhí)行C 的規(guī)則映射，結(jié)束分解；否則，基于遞歸原則將C 作為新的目標(biāo)單元繼續(xù)分解，更新N=N-2(K-1)，將待選信號(hào)重編碼為i0，i1，...，iN-1，轉(zhuǎn)回步驟（1）。

在步驟（2）~（3）中，每次僅用1 個(gè)2 選1 單元來(lái)連接分解出的兩部分待選信號(hào)并以目標(biāo)單元的最高位選擇信號(hào)sK-1作為其選擇信號(hào)，從而實(shí)現(xiàn)相關(guān)條件分支的無(wú)關(guān)變量?jī)?yōu)化，使不規(guī)則單元分解所得樹(shù)狀結(jié)構(gòu)更緊湊。129 選1 單元的分解如圖3 所示，其選擇信號(hào)為s0，s1，...，s7且待選信號(hào)為i0，i1，...，i128，分解得到128選1 單元B 與2 選1 單元A。其中i128在s7=1’b1 時(shí)即可定位，因此本文將i128條件分支的無(wú)關(guān)變量s0，s1，...，s6優(yōu)化，令i128為A 的待選信號(hào)并由s7直接選擇輸出。

圖3 129 選1 單元的分解

另外，遞歸分解所得2 選1 單元還將前后相連形成帶優(yōu)先級(jí)的選擇器鏈，為了進(jìn)一步優(yōu)化面積與時(shí)延，本文將鏈上的單元盡可能映射為MUXF7 或MUXF8，具體步驟設(shè)計(jì)如下。

（1）將選擇器鏈上的P 個(gè)單元按照選擇信號(hào)編碼值升序標(biāo)識(shí)為A0，A1，...，AP-1，對(duì)于任一單元Ai，將其待選信號(hào)分別稱為b0、b1，在選擇信號(hào)為0 時(shí)Ai輸出b0，否則輸出b1。在A0中，若b0由LUT 驅(qū)動(dòng)而b1為非組合邏輯單元的輸出信號(hào)q，則創(chuàng)建與門單元D，以sK-1與q 為D 的輸入信號(hào)，更新b1為D 的輸出。若D 存在，將其映射至LUT，初始化i=0，轉(zhuǎn)入步驟（2）。

（2）對(duì)于目標(biāo)單元Ai，若i

（3）將Ai+1的待選信號(hào)分別稱為a0、a1，在選擇信號(hào)為0 時(shí)Ai+1輸出a0，否則輸出a1，a1即Ai的輸出信號(hào)。當(dāng)a0由MUXF7 驅(qū)動(dòng)時(shí)，若b0由LUT 驅(qū)動(dòng)，則將Ai映射為MUXF7，若此時(shí)b1由專用多路選擇器驅(qū)動(dòng)，將該器件用LUT 替換；當(dāng)a0不是由LUT 驅(qū)動(dòng)時(shí)，若b0與b1均由MUXF7 驅(qū)動(dòng)，則Ai可映射為MUXF8；若b0與b1均由LUT 驅(qū)動(dòng)而且2 個(gè)LUT 的不相同輸入信號(hào)數(shù)大于5，則Ai可映射為MUXF7；其余情況，將Ai映射為L(zhǎng)UT3。更新i=i+1，跳回步驟（2）。

（4）i=P-1，若b0由LUT 驅(qū)動(dòng)，則AP-1可映射為MUXF7，若此時(shí)b1由專用多路選擇器驅(qū)動(dòng)，將該器件用LUT 替換；若b0與b1均由MUXF7 驅(qū)動(dòng)，則AP-1可映射為MUXF8；其余情況，將AP-1映射為L(zhǎng)UT3。若當(dāng)前選擇器鏈源于N>16 的不規(guī)則單元，且其中有多個(gè)單元均映射至LUT 并互連形成子網(wǎng)表，則借助結(jié)構(gòu)化映射算法實(shí)現(xiàn)相關(guān)網(wǎng)表的再映射，避免浪費(fèi)邏輯資源。

3.3 映射后優(yōu)化

標(biāo)記N 選1 單元分解出的所有2 選1 單元，若任一單元A 最終被映射為L(zhǎng)UT3，則執(zhí)行A 的映射后優(yōu)化，在不增加LUT 的基礎(chǔ)上減少專用多路選擇器數(shù)量。

（1）當(dāng)A 有且僅有1 個(gè)待選信號(hào)由專用多路選擇器驅(qū)動(dòng)時(shí)，則將A 與該模塊互連所得子網(wǎng)表用1 個(gè)LUT5 替代。

（2）當(dāng)A 的待選信號(hào)均由專用多路選擇器驅(qū)動(dòng)時(shí)，若這2 個(gè)模塊的選擇信號(hào)相同，則將A 與其互連形成的子網(wǎng)表用1 個(gè)LUT6 替代；若選擇信號(hào)不相同，確定其中選擇信號(hào)編碼值最大的一個(gè)，將A 與該模塊互連形成的子網(wǎng)表用1 個(gè)LUT5 替代。

4 實(shí)驗(yàn)及分析

本文方法以C++ 語(yǔ)言實(shí)現(xiàn)并封裝為應(yīng)用程序YXsyn，利用Verilog 語(yǔ)言描述的多路選擇器單元測(cè)試?yán)右则?yàn)證。YXsyn 可支持任意N 選1 單元的映射，為了驗(yàn)證其正確性，對(duì)用戶設(shè)計(jì)中使用頻率較高的3 選1 單元至128 選1 單元等126 個(gè)測(cè)試?yán)M(jìn)行了試驗(yàn)，其中每個(gè)單元的輸入與輸出位寬均設(shè)為8 bit，未利用的條件分支均綁定至缺省信號(hào)0。選擇學(xué)術(shù)界著名的開(kāi)源綜合工具ABC[15]與Xilinx 公司的FPGA 配套支持工具Vivado[16（]version 2018.3）與YXsyn進(jìn)行LUT 開(kāi)銷、時(shí)延等性能的對(duì)比，3 個(gè)應(yīng)用程序均在Linux 系統(tǒng)、配置為Intel Core 3.40 GHz 處理器、16 GB 內(nèi)存的PC 平臺(tái)上運(yùn)行，映射結(jié)果的時(shí)延參照文獻(xiàn)[8]所述模型進(jìn)行估算，以LUT 的時(shí)延為1 個(gè)單位，將I/O 緩沖器與連線的時(shí)延設(shè)為0，將MUXF7/MUXF8 的時(shí)延設(shè)為L(zhǎng)UT 的1/6。

YXsyn 與ABC 的實(shí)驗(yàn)結(jié)果對(duì)比如圖4 所示，圖4（a）為L(zhǎng)UT 開(kāi)銷數(shù)據(jù)對(duì)比，圖4（b）為時(shí)延數(shù)據(jù)對(duì)比，圖4（c）為運(yùn)行速度數(shù)據(jù)對(duì)比，運(yùn)行速度為運(yùn)行時(shí)間的倒數(shù)。3 個(gè)子圖均為散點(diǎn)圖形式，其中每個(gè)點(diǎn)代表1 個(gè)單元。雖然ABC 集成了強(qiáng)大的結(jié)構(gòu)化工藝映射算法，但無(wú)法支持專用多路選擇器的映射，而本文通過(guò)將N選1 單元分解為若干層基準(zhǔn)單元并基于模板完成映射，實(shí)現(xiàn)了對(duì)專用多路選擇器的高效利用。經(jīng)統(tǒng)計(jì)，YXsyn 與ABC 相比可平均減少20.82%的LUT 開(kāi)銷和29.51%的時(shí)延。另外，結(jié)構(gòu)化映射算法包括分割枚舉、分割排序與最佳分割選取等諸多環(huán)節(jié)，時(shí)間復(fù)雜度高，而YXsyn 的步驟相對(duì)簡(jiǎn)潔，其平均運(yùn)行速度比ABC 快4.28 倍。

圖4 YXsyn 與ABC 的實(shí)驗(yàn)結(jié)果對(duì)比

YXsyn 與Vivado 的實(shí)驗(yàn)結(jié)果對(duì)比如圖5 所示，圖5（a）為L(zhǎng)UT 開(kāi)銷數(shù)據(jù)對(duì)比，圖5（b）為時(shí)延數(shù)據(jù)對(duì)比，由于Vivado 報(bào)告的運(yùn)行時(shí)間實(shí)際上包括硬件信息載入、時(shí)序約束配置等操作的開(kāi)銷，因此無(wú)法準(zhǔn)確對(duì)比YXsyn 與Vivado 的運(yùn)行速度，不記錄相關(guān)數(shù)據(jù)。經(jīng)統(tǒng)計(jì)，YXsyn 與Vivado 相比可平均減少1.01%的LUT開(kāi)銷與5.61%的時(shí)延，可充分說(shuō)明其實(shí)用性。

圖5 YXsyn 與Vivado 的實(shí)驗(yàn)結(jié)果對(duì)比

YXsyn 的時(shí)延性能優(yōu)于Vivado 的主要原因是本文設(shè)計(jì)的分解操作可優(yōu)化相關(guān)條件分支中的無(wú)關(guān)變量，使子單元間的連接更加緊湊。以21 選1 單元為例，圖6（a）為Vivado 映射結(jié)果，圖6（b）為YXsyn 映射結(jié)果，其中8 選1 單元A0與A1分別對(duì)待選信號(hào)i0，i1，...，i7與i8，i9，...，i15進(jìn)行選擇，其工藝網(wǎng)表包含1 級(jí)LUT與1 級(jí)MUXF7，時(shí)延為1.17 s，詳細(xì)結(jié)構(gòu)見(jiàn)圖2。由于在s4s2=2’b11 時(shí)便可定位i20，因此本文將i20條件分支中的無(wú)關(guān)變量s0，s1，s3優(yōu)化，并將其與s4集成為1 個(gè)與門以實(shí)現(xiàn)對(duì)MUXF7 的利用，最終使信號(hào)的最長(zhǎng)輸出路徑為L(zhǎng)UT6→MUXF7→LUT5，見(jiàn)圖6（b）中紅色標(biāo)識(shí)線，電路時(shí)延為2.17 s；而Vivado 將i20的條件分支完整實(shí)現(xiàn)，信號(hào)的最長(zhǎng)輸出路徑為L(zhǎng)UT6→LUT6→LUT5，見(jiàn)圖6（a）紅色標(biāo)識(shí)線，電路時(shí)延為3.00 s。

圖6 映射結(jié)果示例

5 結(jié)論

針對(duì)Xilinx 公司的Virtex-7 系列FPGA 架構(gòu)，本文提出基于分解的多路選擇器工藝映射方法，首先將N 選1 單元遞歸分解為若干層基準(zhǔn)單元，接著利用預(yù)設(shè)的模板實(shí)現(xiàn)其映射。實(shí)驗(yàn)結(jié)果表明該方法具有優(yōu)越的多目標(biāo)優(yōu)化能力，可以有效減少映射結(jié)果的LUT 開(kāi)銷與時(shí)延。本文方法適用于2 級(jí)專用多路選擇器與6輸入LUT 相集成的芯片架構(gòu)，為了擴(kuò)大其適用范圍，后續(xù)將對(duì)不同廠商、不同系列的FPGA 架構(gòu)進(jìn)行對(duì)比與分析，在此基礎(chǔ)上引入更多類型的模板并豐富N 選1 單元的分解方式，提高本文方法的兼容性。