謝尚鑾，惠 鋒，劉 佩，王晨陽，張 立

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

1 引言

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

目前，公開的面向異構(gòu)FPGA 的多路選擇器工藝映射方法較少。多路選擇器是數(shù)字系統(tǒng)的常見元件，在低功耗應(yīng)用領(lǐng)域更是扮演了主要角色，但其邏輯資源開銷大[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ī)等分支控制語句解析得到，每個(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 多路選擇器簡稱為N 選1 單元。

在保證邏輯等價(jià)的前提下，N 選1 單元可分解為2 層的樹狀結(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ì)的多路選擇器樹[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é)果的性能。需要說明的是，解析所得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 單元直接映射為LUT3。

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 單元來連接分解出的兩部分待選信號(hào)并以目標(biāo)單元的最高位選擇信號(hào)sK-1作為其選擇信號(hào)，從而實(shí)現(xiàn)相關(guān)條件分支的無關(guān)變量優(yōu)化，使不規(guī)則單元分解所得樹狀結(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條件分支的無關(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映射為LUT3。更新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映射為LUT3。若當(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 最終被映射為LUT3，則執(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++ 語言實(shí)現(xiàn)并封裝為應(yīng)用程序YXsyn，利用Verilog 語言描述的多路選擇器單元測(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ù)界著名的開源綜合工具ABC[15]與Xilinx 公司的FPGA 配套支持工具Vivado[16（]version 2018.3）與YXsyn進(jìn)行LUT 開銷、時(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è)為LUT 的1/6。

YXsyn 與ABC 的實(shí)驗(yàn)結(jié)果對(duì)比如圖4 所示，圖4（a）為LUT 開銷數(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)化工藝映射算法，但無法支持專用多路選擇器的映射，而本文通過將N選1 單元分解為若干層基準(zhǔn)單元并基于模板完成映射，實(shí)現(xiàn)了對(duì)專用多路選擇器的高效利用。經(jīng)統(tǒng)計(jì)，YXsyn 與ABC 相比可平均減少20.82%的LUT 開銷和29.51%的時(shí)延。另外，結(jié)構(gòu)化映射算法包括分割枚舉、分割排序與最佳分割選取等諸多環(huán)節(jié)，時(shí)間復(fù)雜度高，而YXsyn 的步驟相對(duì)簡潔，其平均運(yùn)行速度比ABC 快4.28 倍。

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

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

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

YXsyn 的時(shí)延性能優(yōu)于Vivado 的主要原因是本文設(shè)計(jì)的分解操作可優(yōu)化相關(guān)條件分支中的無關(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)見圖2。由于在s4s2=2’b11 時(shí)便可定位i20，因此本文將i20條件分支中的無關(guān)變量s0，s1，s3優(yōu)化，并將其與s4集成為1 個(gè)與門以實(shí)現(xiàn)對(duì)MUXF7 的利用，最終使信號(hào)的最長輸出路徑為LUT6→MUXF7→LUT5，見圖6（b）中紅色標(biāo)識(shí)線，電路時(shí)延為2.17 s；而Vivado 將i20的條件分支完整實(shí)現(xiàn)，信號(hào)的最長輸出路徑為LUT6→LUT6→LUT5，見圖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 開銷與時(shí)延。本文方法適用于2 級(jí)專用多路選擇器與6輸入LUT 相集成的芯片架構(gòu)，為了擴(kuò)大其適用范圍，后續(xù)將對(duì)不同廠商、不同系列的FPGA 架構(gòu)進(jìn)行對(duì)比與分析，在此基礎(chǔ)上引入更多類型的模板并豐富N 選1 單元的分解方式，提高本文方法的兼容性。