ABC對(duì)輸入MV文件的解決方案

　　論文關(guān)鍵字：ABC  MV文件時(shí)序　綜合

　　論文摘要：ABC是一款時(shí)序電路的綜合和驗(yàn)證的軟件系統(tǒng)。ABC為查找表和標(biāo)準(zhǔn)塊整合了基于AIGs（這個(gè)圖只有與門(mén)和非門(mén)）的邏輯優(yōu)化和基于技術(shù)映射的最優(yōu)延遲DAG（無(wú)回路有向圖）。MV是一種為描述時(shí)序?qū)哟坞娐废到y(tǒng)而設(shè)計(jì)的，它能以層次形式來(lái)描述電路系統(tǒng)。ABC提供了對(duì)輸入MV文件的支持，但其對(duì)MV文件的時(shí)序支持有限，本文討論了其解決方案。

　　1 電路邏輯綜合的一些常用方法

　　1.1 使用SIS優(yōu)化

　　輸入.mv文件，經(jīng)過(guò)mv2blif軟件處理后，產(chǎn)生.blif文件，然后送入SIS綜合軟件處理，生成優(yōu)化后的blif文件，如下圖所示：

 SHAPE  \* MERGEFORMAT

　　圖 1.1

　　1.2 使用ABC優(yōu)化

　　輸入.mv文件，經(jīng)過(guò)mv2blif軟件處理后，產(chǎn)生.blif文件，然后送入ABC處理，生成優(yōu)化后的blif文件，如下圖所示：

 　　SHAPE  \* MERGEFORMAT

　　圖 1.2

　　1.3 對(duì)比兩種方法

　　使用SIS優(yōu)化已經(jīng)是比較陳舊的方法，現(xiàn)在更多的是使用ABC進(jìn)行優(yōu)化。我們知道，數(shù)據(jù)結(jié)構(gòu)和算法是一個(gè)軟件能否成功應(yīng)用的核心，SIS在近幾年一些最新的改變中沒(méi)能提供一個(gè)良好的編程，比如對(duì)技術(shù)映射和延遲的整合。而且SIS在處理大型電路顯得力不從心，效率低下。而ABC使用了一種更為簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)AIGs(由兩輸入的與門(mén)和非門(mén)組成的多層邏輯網(wǎng))，使得電路綜合和驗(yàn)證的質(zhì)量和運(yùn)行時(shí)間方面都得到很大改進(jìn)。ABC提供了時(shí)序和組合的綜合算法，其現(xiàn)在版本在優(yōu)化延遲和啟發(fā)式的縮小電路面積方面已能優(yōu)化包含100K門(mén)和10K時(shí)序元素的門(mén)級(jí)設(shè)計(jì)。

　　但ABC本身就能輸入.mv文件，我們能否省去Mv2blif的步驟，讓ABC直接讀入mv，從而也能減少錯(cuò)誤，提高效率，因?yàn)樵俸玫能浖�或多或少總�?huì)存在一些錯(cuò)誤，少用一個(gè)軟件意味著我們能減少更多的錯(cuò)誤。所以下面就是我們想要得到的版本：

 SHAPE  \* MERGEFORMAT

　　2 研究中發(fā)現(xiàn)問(wèn)題及其原因      

　　2.1 ABC中采用的網(wǎng)絡(luò)介紹

　　在讀入特定電路設(shè)計(jì)文件經(jīng)過(guò)軟件處理，就形成當(dāng)前的網(wǎng)絡(luò)。ABC通過(guò)一系列對(duì)當(dāng)前網(wǎng)絡(luò)的轉(zhuǎn)換來(lái)處理這個(gè)電路設(shè)計(jì)類似于SIS。ABC中的網(wǎng)絡(luò)有其特定類型，包括NetList，Logic Network和AIG網(wǎng)絡(luò)，下面簡(jiǎn)要介紹各個(gè)網(wǎng)絡(luò)。

　　2.1.1 NetList網(wǎng)絡(luò)

　　如果編程者在輸入文件中加入一個(gè)新的類型，想成功通過(guò)解析就必須熟悉NetList網(wǎng)絡(luò)的表示形式，因?yàn)榻馕鲆粋�(gè)輸入文件，NetList網(wǎng)絡(luò)是必然被創(chuàng)建的。NetList可以說(shuō)是一個(gè)基本原始的網(wǎng)絡(luò)表示形式，它與輸入文件的設(shè)計(jì)一一對(duì)應(yīng)，包含nets，logic nodes，latches和PI/PO 端點(diǎn)。每個(gè)net有一個(gè)唯一的名字。Nodes和latches是由它們所驅(qū)動(dòng)的net來(lái)區(qū)分。每個(gè)nodes和latches只有一個(gè)輸出。每個(gè)PI端點(diǎn)、Node和latch驅(qū)動(dòng)一個(gè)net。同樣每個(gè)latch、PO端點(diǎn)和功能結(jié)點(diǎn)（有一個(gè)或多個(gè)輸入）由一個(gè)net驅(qū)動(dòng)。一個(gè)net能驅(qū)動(dòng)有僅只有一個(gè)latch、node或者PO端點(diǎn)。例如，一個(gè)net不能同時(shí)驅(qū)動(dòng)一個(gè)node和一個(gè)latch。在NetList中，net與net之間不能相連，非net結(jié)點(diǎn)與非net結(jié)點(diǎn)也不能相連，只能通過(guò)net相連。功能結(jié)點(diǎn)采用SOPs或者AIGs來(lái)表示。

　　2.1.2 Logic Network網(wǎng)絡(luò)

　　一個(gè)logic network實(shí)際上是一個(gè)netlist去掉nets后的網(wǎng)絡(luò)，SIS就是用logic network網(wǎng)絡(luò)所表示。在ABC，默認(rèn)的表示是AIG網(wǎng)絡(luò)，但logic network是一種很有效的中間過(guò)渡網(wǎng)絡(luò)表示形式。在logic network網(wǎng)絡(luò)中只保留 了PI/PO/latch/latch-input/latch-output這幾種數(shù)據(jù)結(jié)構(gòu)的名字，丟棄了內(nèi)部node的名字。因?yàn)锳BC采用AIG進(jìn)行深層次的綜合時(shí)，一些AIG操作很難保存AIG結(jié)點(diǎn)的名字，比如重寫(xiě)。在logic network中，nodes 能與另一個(gè)nodes直接相連。PI/PO端點(diǎn)與node直接相連。一個(gè)PO端點(diǎn)與一個(gè)PI端點(diǎn)如果有一樣的名字和功能，能直接相連。一個(gè)PI端點(diǎn)可能有兩個(gè)扇出但沒(méi)有扇入。一個(gè)PO端點(diǎn)只有一個(gè)輸入但沒(méi)有輸出。端點(diǎn)并不是一個(gè)node也沒(méi)有邏輯功能。指向端點(diǎn)的指針集合不能通過(guò)一個(gè)內(nèi)部node的DFS遍歷方法來(lái)獲取。在logic network網(wǎng)絡(luò)中，指向PI/PO端點(diǎn)的指針集合儲(chǔ)存在相應(yīng)的數(shù)組。

　　2.1.3 AIG網(wǎng)絡(luò)

　　AIG網(wǎng)絡(luò)是ABC中所采用網(wǎng)絡(luò)的內(nèi)部主要表示形式。AIG是ABC所特有的，其每個(gè)node是兩輸入的與門(mén)和一個(gè)扇入/扇出邊，并且這個(gè)邊有一個(gè)可選屬性指示是否對(duì)該邊進(jìn)行取反。在構(gòu)造AIG的同時(shí)，AIG能被壓縮通過(guò)使用一級(jí)結(jié)構(gòu)散列，它使得每一對(duì)邊最多只能做為一個(gè)結(jié)點(diǎn)輸入。這樣，結(jié)構(gòu)散列就能保證：對(duì)于每個(gè)與門(mén)結(jié)點(diǎn)，就沒(méi)有其它帶相同子結(jié)點(diǎn)的與門(mén)；沒(méi)有僅一個(gè)輸入的結(jié)點(diǎn)；每個(gè)與門(mén)的層次就能反應(yīng)輸入的層次。所有這些，使得操作AIGs比較操作Logic networks要快很多。

　　2.2 發(fā)現(xiàn)問(wèn)題及其根本原因

　　在研究的過(guò)程中，我們發(fā)現(xiàn)會(huì)產(chǎn)生ABC輸入mv文件經(jīng)過(guò)優(yōu)化后的blif 文件的輸入輸出的個(gè)數(shù)與原先讀入mv文件的輸入輸出個(gè)數(shù)的不一致問(wèn)題。這是因?yàn)锳BC輸入mv文件時(shí)，主要經(jīng)過(guò)了兩步處理。輸入mv時(shí)，ABC把mv文件轉(zhuǎn)成了NetList，這一步是完全正確的，但在NetList轉(zhuǎn)成AIG時(shí)，出現(xiàn)了問(wèn)題，ABC把latch的輸入當(dāng)成了主輸出，把latch的輸出當(dāng)成了主輸入，從而造成了有幾個(gè)latch，就多了幾個(gè)輸出輸入。

　　筆者認(rèn)為根本原因在于，ABC對(duì)mv文件中的時(shí)序電路支持得有限，在將時(shí)序轉(zhuǎn)化為組合的過(guò)程中，也就是在NetList轉(zhuǎn)成AIG時(shí)，采用了不正確的方式去除了Latch，從而造成了有幾個(gè)latch，就多了幾個(gè)輸出輸入。

　　3 問(wèn)題的解決方案及生成blif

　　3.1 解決問(wèn)題

　　在嘗試直接把NetList網(wǎng)絡(luò)轉(zhuǎn)成AIG網(wǎng)絡(luò)時(shí)，來(lái)處理這個(gè)問(wèn)題，都?xì)w于失敗。最后不得不考慮在生成的中間網(wǎng)絡(luò)上找解決方法。

       首先，ABC處理mv文件的過(guò)程如下：

        SHAPE  \* MERGEFORMAT

　　然后，我們查看了ABC處理blif文件的過(guò)程，如下：

 　　SHAPE  \* MERGEFORMAT

　　經(jīng)過(guò)討論，我們?cè)囅肽懿荒軜?gòu)造出如下的一種處理方法來(lái)解決問(wèn)題：

　　經(jīng)過(guò)研究，我們發(fā)現(xiàn)這條路是可行的。但在解決的過(guò)程中我們發(fā)現(xiàn)，.mv文件生成的NetList網(wǎng)絡(luò)與.blif文件生成的NetList網(wǎng)絡(luò)存在不同。在前面Mv2blif軟件的實(shí)現(xiàn)方法中尋求靈感，我們?cè)囍鴮⑦@兩個(gè)相同類型網(wǎng)絡(luò)轉(zhuǎn)化，最后我們成功解決了這個(gè)問(wèn)題，從而實(shí)現(xiàn)了ABC對(duì).mv文件能直接進(jìn)行處理，并且解決了輸入輸出個(gè)數(shù)與原先的輸入輸出個(gè)數(shù)的不一致的問(wèn)題。最終實(shí)現(xiàn)了如下版本：

 SHAPE  \* MERGEFORMAT

　　3.2 生成blif文件

       ABC中讀入mv文件后形成AIG網(wǎng)絡(luò)，要想輸出blif文件，可進(jìn)行如下操作：

        SHAPE  \* MERGEFORMAT

　　4 算法實(shí)現(xiàn)及舉例

　　對(duì)網(wǎng)絡(luò)中的功能node進(jìn)行轉(zhuǎn)換，以下是轉(zhuǎn)換node從AIG功能到BDD功能的算法，對(duì)于網(wǎng)絡(luò)只需要用一個(gè)遍歷，把其所有node轉(zhuǎn)換即可。

DdNode * cuddBddAndRecur( DdManager * manager, DdNode * f, DdNode * g)

{

    DdNode *F, *fv, *fnv, *G, *gv, *gnv;

    DdNode *one, *r, *t, *e;

    unsigned int topf, topg, index;

    statLine(manager);   //循環(huán)次數(shù)加1

    one = DD_ONE(manager);    //返回manger->one，即常數(shù)結(jié)點(diǎn)1

//得到結(jié)點(diǎn)的正則狀態(tài)，如果結(jié)點(diǎn)取過(guò)反，則返回沒(méi)有取反的狀態(tài)

F = Cudd_Regular(f);              

G = Cudd_Regular(g);

    if (F == G) {

       if (f == g) return(f);

       else return(Cudd_Not(one));               //Cudd_Not為取反

    }

    if (F == one) {

       if (f == one) return(g);

       else return(f);

    }

    if (G == one) {

       if (g == one) return(f);

       else return(g);

    }

    /* 檢查緩存 */

if (F->ref != 1 || G->ref != 1) {

//如果已經(jīng)有對(duì)f和g取與的情況，則直接返回

       r = cuddCacheLookup2(manager, Cudd_bddAnd, f, g);      if (r != NULL) return(r);

    }

    topf = manager->perm[F->index];

topg = manager->perm[G->index];

    /* 計(jì)算因子 */

    if (topf <= topg) {

       index = F->index;

       fv = cuddT(F);

       fnv = cuddE(F);

       if (Cudd_IsComplement(f)) {

           fv = Cudd_Not(fv);

           fnv = Cudd_Not(fnv);

       }

    } else {

       index = G->index;

       fv = fnv = f;

    }

    if (topg <= topf) {

       gv = cuddT(G);

       gnv = cuddE(G);

       if (Cudd_IsComplement(g)) {              //判斷g結(jié)點(diǎn)是否取過(guò)反

           gv = Cudd_Not(gv);             //對(duì)gv結(jié)點(diǎn)取反

           gnv = Cudd_Not(gnv);

       }

    } else {

       gv = gnv = g;

    }

    t = cuddBddAndRecur(manager, fv, gv);

    e = cuddBddAndRecur(manager, fnv, gnv);

    if (t == e) {

       r = t;

    } else {

       if (Cudd_IsComplement(t)) {

//如果已經(jīng)存在以Cudd_Not(t),Cudd_Not(e)為孩子的結(jié)點(diǎn)，則返回，如沒(méi)有，則重//新創(chuàng)建一個(gè)，并且把index賦值于它。

           r = cuddUniqueInter(manager,(int)index,Cudd_Not(t),Cudd_Not(e));

           r = Cudd_Not(r);           //對(duì)r結(jié)點(diǎn)取反

       } else {

           r = cuddUniqueInter(manager,(int)index,t,e);

       }

    }

    if (F->ref != 1 || G->ref != 1)

       cuddCacheInsert2(manager, Cudd_bddAnd, f, g, r);    //加入緩存機(jī)制

    return(r);

} /* end of cuddBddAndRecur */

　　這里根據(jù)算法，我們舉例說(shuō)明結(jié)點(diǎn)功能為AIG，表達(dá)式為a*b的情況，其轉(zhuǎn)換成BDD功能，如下所示：

       圖4  AIG：表示a*b的功能                      BDD：表示a*b的功能

　　5

　　本文簡(jiǎn)要介紹了傳統(tǒng)的綜合方法，并介紹了NetList、Logic Network與AIG的網(wǎng)絡(luò)形式，在實(shí)現(xiàn)從MV文件經(jīng)過(guò)ABC處理并優(yōu)化生成BLIF文件的過(guò)程中，分析了過(guò)程中產(chǎn)生問(wèn)題的根本原因，并解決了ABC對(duì)讀入MV文件的不足，是通過(guò)轉(zhuǎn)換了其讀入MV文件過(guò)程中的網(wǎng)絡(luò)形式來(lái)解決這個(gè)問(wèn)題。最后給出了結(jié)點(diǎn)從AIG到BDD功能的轉(zhuǎn)換算法，和一個(gè)簡(jiǎn)單的實(shí)例。

　　參考文獻(xiàn)

　　[1] The VIS Group．BLIF-MV．University of Berkeley, May 1996．

　　[2] MVSIS Group．MVSIS Manual．UC Berkeley, February 2001．

　　[3] RÜDIGER EBENDT, GÖRSCHWIN FEY, ROLF DRECHSLER．ADVANCED BDD OPTIMIZATION．University of Bremen, 2005．

　　[4] Berkeley Logic Synthesis and Verification Group．ABC: A System for Sequential Synthesis and Verification．December 2005 Release．http://www-cad.eecs.berkeley.edu/~alanmi/abc．

　　[5] J. Cong and Y. Ding, “FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs”, IEEE Trans．CAD, vol. 13(1), January 1994, pp. 1-12．

　　[6] IWLS 2005 Benchmarks．http://iwls.org/iwls2005/benchmarks.html．

　　[7] S. Yang．Logic synthesis and optimization benchmarks. Version 3.0．Tech. Report.　Microelectronics Center of North Carolina, 1991．

　　[8] The SIS Group．Berkeley Logic Interchange Format (BLIF)．University of Berkeley,

July 1992．

　　[9] Joachim Pistorius, Mike Hutton, Alan Mishchenko, Robert Brayton．Benchmarking Method and Designs Targeting Logic Synthesis for FPGAs．University of Berkeley, 2007．

【ABC對(duì)輸入MV文件的解決方案】相關(guān)文章：

ABC—STORM 哲學(xué)宇宙模型和宇宙哲學(xué)03-05

未來(lái)十年?duì)I銷回歸ABC03-29

淺談?dòng)⒄Z(yǔ)教學(xué)中的輸入與輸出06-05

人力資源ABC管理法的核算方式03-25

基于DVCC8086的輸入與輸出系統(tǒng)設(shè)計(jì)03-20

PLC輸入/輸出點(diǎn)的合理使用及擴(kuò)展方法01-10

文件自動(dòng)分類系統(tǒng)Delphi03-08

關(guān)于法學(xué)論文的文件擬寫(xiě)02-26

文件信息與檔案信息的研究03-21