- 相關(guān)推薦
ABC對輸入MV文件的解決方案
論文關(guān)鍵字：ABC MV文件時序 綜合
論文摘要：ABC是一款時序電路的綜合和驗證的軟件系統(tǒng)。ABC為查找表和標準塊整合了基于AIGs（這個圖只有與門和非門）的邏輯優(yōu)化和基于技術(shù)映射的最優(yōu)延遲DAG（無回路有向圖）。MV是一種為描述時序?qū)哟坞娐废到y(tǒng)而設計的，它能以層次形式來描述電路系統(tǒng)。ABC提供了對輸入MV文件的支持，但其對MV文件的時序支持有限，本文討論了其解決方案。
1 電路邏輯綜合的一些常用方法
1.1 使用SIS優(yōu)化輸入.mv文件，經(jīng)過mv2blif軟件處理后，產(chǎn)生.blif文件，然后送入SIS綜合軟件處理，生成優(yōu)化后的blif文件，如下圖所示：
SHAPE \* MERGEFORMAT
圖 1.1
1.2 使用ABC優(yōu)化輸入.mv文件，經(jīng)過mv2blif軟件處理后，產(chǎn)生.blif文件，然后送入ABC處理，生成優(yōu)化后的blif文件，如下圖所示：
SHAPE \* MERGEFORMAT
圖 1.2
1.3 對比兩種方法使用SIS優(yōu)化已經(jīng)是比較陳舊的方法，現(xiàn)在更多的是使用ABC進行優(yōu)化。我們知道，數(shù)據(jù)結(jié)構(gòu)和算法是一個軟件能否成功應用的核心，SIS在近幾年一些最新的改變中沒能提供一個良好的編程，比如對技術(shù)映射和延遲的整合。而且SIS在處理大型電路顯得力不從心，效率低下。而ABC使用了一種更為簡單的數(shù)據(jù)結(jié)構(gòu)AIGs(由兩輸入的與門和非門組成的多層邏輯網(wǎng))，使得電路綜合和驗證的質(zhì)量和運行時間方面都得到很大改進。ABC提供了時序和組合的綜合算法，其現(xiàn)在版本在優(yōu)化延遲和啟發(fā)式的縮小電路面積方面已能優(yōu)化包含100K門和10K時序元素的門級設計。
但ABC本身就能輸入.mv文件，我們能否省去Mv2blif的步驟，讓ABC直接讀入mv，從而也能減少錯誤，提高效率，因為再好的軟件或多或少總會存在一些錯誤，少用一個軟件意味著我們能減少更多的錯誤。所以下面就是我們想要得到的版本：
SHAPE \* MERGEFORMAT
2 研究中發(fā)現(xiàn)問題及其原因
2.1 ABC中采用的網(wǎng)絡介紹在讀入特定電路設計文件經(jīng)過軟件處理，就形成當前的網(wǎng)絡。ABC通過一系列對當前網(wǎng)絡的轉(zhuǎn)換來處理這個電路設計類似于SIS。ABC中的網(wǎng)絡有其特定類型，包括NetList，Logic Network和AIG網(wǎng)絡，下面簡要介紹各個網(wǎng)絡。
2.1.1 NetList網(wǎng)絡如果編程者在輸入文件中加入一個新的類型，想成功通過解析就必須熟悉NetList網(wǎng)絡的表示形式，因為解析一個輸入文件，NetList網(wǎng)絡是必然被創(chuàng)建的。NetList可以說是一個基本原始的網(wǎng)絡表示形式，它與輸入文件的設計一一對應，包含nets，logic nodes，latches和PI/PO 端點。每個net有一個唯一的名字。Nodes和latches是由它們所驅(qū)動的net來區(qū)分。每個nodes和latches只有一個輸出。每個PI端點、Node和latch驅(qū)動一個net。同樣每個latch、PO端點和功能結(jié)點（有一個或多個輸入）由一個net驅(qū)動。一個net能驅(qū)動有僅只有一個latch、node或者PO端點。例如，一個net不能同時驅(qū)動一個node和一個latch。在NetList中，net與net之間不能相連，非net結(jié)點與非net結(jié)點也不能相連，只能通過net相連。功能結(jié)點采用SOPs或者AIGs來表示。
2.1.2 Logic Network網(wǎng)絡一個logic network實際上是一個netlist去掉nets后的網(wǎng)絡，SIS就是用logic network網(wǎng)絡所表示。在ABC，默認的表示是AIG網(wǎng)絡，但logic network是一種很有效的中間過渡網(wǎng)絡表示形式。在logic network網(wǎng)絡中只保留 了PI/PO/latch/latch-input/latch-output這幾種數(shù)據(jù)結(jié)構(gòu)的名字，丟棄了內(nèi)部node的名字。因為ABC采用AIG進行深層次的綜合時，一些AIG操作很難保存AIG結(jié)點的名字，比如重寫。在logic network中，nodes 能與另一個nodes直接相連。PI/PO端點與node直接相連。一個PO端點與一個PI端點如果有一樣的名字和功能，能直接相連。一個PI端點可能有兩個扇出但沒有扇入。一個PO端點只有一個輸入但沒有輸出。端點并不是一個node也沒有邏輯功能。指向端點的指針集合不能通過一個內(nèi)部node的DFS遍歷方法來獲取。在logic network網(wǎng)絡中，指向PI/PO端點的指針集合儲存在相應的數(shù)組。
2.1.3 AIG網(wǎng)絡AIG網(wǎng)絡是ABC中所采用網(wǎng)絡的內(nèi)部主要表示形式。AIG是ABC所特有的，其每個node是兩輸入的與門和一個扇入/扇出邊，并且這個邊有一個可選屬性指示是否對該邊進行取反。在構(gòu)造AIG的同時，AIG能被壓縮通過使用一級結(jié)構(gòu)散列，它使得每一對邊最多只能做為一個結(jié)點輸入。這樣，結(jié)構(gòu)散列就能保證：對于每個與門結(jié)點，就沒有其它帶相同子結(jié)點的與門；沒有僅一個輸入的結(jié)點；每個與門的層次就能反應輸入的層次。所有這些，使得操作AIGs比較操作Logic networks要快很多。
2.2 發(fā)現(xiàn)問題及其根本原因在研究的過程中，我們發(fā)現(xiàn)會產(chǎn)生ABC輸入mv文件經(jīng)過優(yōu)化后的blif 文件的輸入輸出的個數(shù)與原先讀入mv文件的輸入輸出個數(shù)的不一致問題。這是因為ABC輸入mv文件時，主要經(jīng)過了兩步處理。輸入mv時，ABC把mv文件轉(zhuǎn)成了NetList，這一步是完全正確的，但在NetList轉(zhuǎn)成AIG時，出現(xiàn)了問題，ABC把latch的輸入當成了主輸出，把latch的輸出當成了主輸入，從而造成了有幾個latch，就多了幾個輸出輸入。
筆者認為根本原因在于，ABC對mv文件中的時序電路支持得有限，在將時序轉(zhuǎn)化為組合的過程中，也就是在NetList轉(zhuǎn)成AIG時，采用了不正確的方式去除了Latch，從而造成了有幾個latch，就多了幾個輸出輸入。
3 問題的解決方案及生成blif
3.1 解決問題在嘗試直接把NetList網(wǎng)絡轉(zhuǎn)成AIG網(wǎng)絡時，來處理這個問題，都歸于失敗。最后不得不考慮在生成的中間網(wǎng)絡上找解決方法。
首先，ABC處理mv文件的過程如下：
SHAPE \* MERGEFORMAT
然后，我們查看了ABC處理blif文件的過程，如下：
SHAPE \* MERGEFORMAT
經(jīng)過討論，我們試想能不能構(gòu)造出如下的一種處理方法來解決問題：
經(jīng)過研究，我們發(fā)現(xiàn)這條路是可行的。但在解決的過程中我們發(fā)現(xiàn)，.mv文件生成的NetList網(wǎng)絡與.blif文件生成的NetList網(wǎng)絡存在不同。在前面Mv2blif軟件的實現(xiàn)方法中尋求靈感，我們試著將這兩個相同類型網(wǎng)絡轉(zhuǎn)化，最后我們成功解決了這個問題，從而實現(xiàn)了ABC對.mv文件能直接進行處理，并且解決了輸入輸出個數(shù)與原先的輸入輸出個數(shù)的不一致的問題。最終實現(xiàn)了如下版本：
SHAPE \* MERGEFORMAT
3.2 生成blif文件ABC中讀入mv文件后形成AIG網(wǎng)絡，要想輸出blif文件，可進行如下操作：
SHAPE \* MERGEFORMAT
4 算法實現(xiàn)及舉例
對網(wǎng)絡中的功能node進行轉(zhuǎn)換，以下是轉(zhuǎn)換node從AIG功能到BDD功能的算法，對于網(wǎng)絡只需要用一個遍歷，把其所有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é)點1
//得到結(jié)點的正則狀態(tài)，如果結(jié)點取過反，則返回沒有取反的狀態(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)有對f和g取與的情況，則直接返回
r = cuddCacheLookup2(manager, Cudd_bddAnd, f, g); if (r != NULL) return(r);
}
topf = manager->perm[F->index];
topg = manager->perm[G->index];
/* 計算因子 */
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é)點是否取過反
gv = Cudd_Not(gv); //對gv結(jié)點取反
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é)點，則返回，如沒有，則重//新創(chuàng)建一個，并且把index賦值于它。
r = cuddUniqueInter(manager,(int)index,Cudd_Not(t),Cudd_Not(e));
r = Cudd_Not(r); //對r結(jié)點取反
} else {
r = cuddUniqueInter(manager,(int)index,t,e);
}
}
if (F->ref != 1 || G->ref != 1)
cuddCacheInsert2(manager, Cudd_bddAnd, f, g, r); //加入緩存機制
return(r);
} /* end of cuddBddAndRecur */
這里根據(jù)算法，我們舉例說明結(jié)點功能為AIG，表達式為a*b的情況，其轉(zhuǎn)換成BDD功能，如下所示：
圖4 AIG：表示a*b的功能 BDD：表示a*b的功能
5
本文簡要介紹了傳統(tǒng)的綜合方法，并介紹了NetList、Logic Network與AIG的網(wǎng)絡形式，在實現(xiàn)從MV文件經(jīng)過ABC處理并優(yōu)化生成BLIF文件的過程中，分析了過程中產(chǎn)生問題的根本原因，并解決了ABC對讀入MV文件的不足，是通過轉(zhuǎn)換了其讀入MV文件過程中的網(wǎng)絡形式來解決這個問題。最后給出了結(jié)點從AIG到BDD功能的轉(zhuǎ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對輸入MV文件的解決方案】相關(guān)文章：
未來十年營銷回歸ABC03-29
淺談英語教學中的輸入與輸出06-05
人力資源ABC管理法的核算方式03-25
基于DVCC8086的輸入與輸出系統(tǒng)設計03-20
PLC輸入/輸出點的合理使用及擴展方法01-10
文件自動分類系統(tǒng)Delphi03-08
關(guān)于法學論文的文件擬寫02-26
文件信息與檔案信息的研究03-21