ABC对输入MV文件解决方案

论文关键字：ABCMV文件时序综合

论文摘要：ABC是一款时序逻辑电路的综合和验证的软件系统。ABC为查找表和标准块整合了基于AIGs（这个图只有与门和非门）的逻辑优化和基于技术映射的最优延迟DAG（无回路有向图）。MV是一种为描述时序层次电路系统而设计的语言，它能以层次形式来描述电路系统。ABC提供了对输入MV文件的支持，但其对MV文件的时序支持有限，本文讨论了其解决方案。

1电路逻辑综合的一些常用方法

1.1使用SIS优化

输入.mv文件，经过mv2blif软件处理后，产生.blif文件，然后送入SIS综合软件处理，生成优化后的blif文件，如下图所示：

SHAPE\*MERGEFORMAT

图1.1

1.2使用ABC优化

输入.mv文件，经过mv2blif软件处理后，产生.blif文件，然后送入ABC处理，生成优化后的blif文件，如下图所示：

SHAPE\*MERGEFORMAT

图1.2

1.3对比两种方法

使用SIS优化已经是比较陈旧的方法，现在更多的是使用ABC进行优化。我们知道，数据结构和算法是一个软件能否成功应用的核心，SIS在近几年一些最新的改变中没能提供一个良好的编程环境，比如对技术映射和延迟的整合。而且SIS在处理大型电路显得力不从心，效率低下。而ABC使用了一种更为简单的数据结构AIGs(由两输入的与门和非门组成的多层逻辑网)，使得电路综合和验证的质量和运行时间方面都得到很大改进。ABC提供了时序和组合的综合算法，其现在版本在优化延迟和启发式的缩小电路面积方面已能优化包含100K门和10K时序元素的门级设计。

但ABC本身就能输入.mv文件，我们能否省去Mv2blif的步骤，让ABC直接读入mv，从而也能减少错误，提高效率，因为再好的软件或多或少总会存在一些错误，少用一个软件意味着我们能减少更多的错误。所以下面就是我们想要得到的版本：

SHAPE\*MERGEFORMAT

2研究中发现问题及其原因

2.1ABC中采用的网络介绍

在读入特定电路设计文件经过软件处理，就形成当前的网络。ABC通过一系列对当前网络的转换来处理这个电路设计类似于SIS。ABC中的网络有其特定类型，包括NetList，LogicNetwork和AIG网络，下面简要介绍各个网络。

2.1.1NetList网络

如果编程者在输入文件中加入一个新的类型，想成功通过解析就必须熟悉NetList网络的表示形式，因为解析一个输入文件，NetList网络是必然被创建的。NetList可以说是一个基本原始的网络表示形式，它与输入文件的设计一一对应，包含nets，logicnodes，latches和PI/PO端点。每个net有一个唯一的名字。Nodes和latches是由它们所驱动的net来区分。每个nodes和latches只有一个输出。每个PI端点、Node和latch驱动一个net。同样每个latch、PO端点和功能结点（有一个或多个输入）由一个net驱动。一个net能驱动有仅只有一个latch、node或者PO端点。例如，一个net不能同时驱动一个node和一个latch。在NetList中，net与net之间不能相连，非net结点与非net结点也不能相连，只能通过net相连。功能结点采用SOPs或者AIGs来表示。

2.1.2LogicNetwork网络

一个logicnetwork实际上是一个netlist去掉nets后的网络，SIS就是用logicnetwork网络所表示。在ABC，默认的表示是AIG网络，但logicnetwork是一种很有效的中间过渡网络表示形式。在logicnetwork网络中只保留了PI/PO/latch/latch-input/latch-output这几种数据结构的名字，丢弃了内部node的名字。因为ABC采用AIG进行深层次的综合时，一些AIG操作很难保存AIG结点的名字，比如重写。在logicnetwork中，nodes能与另一个nodes直接相连。PI/PO端点与node直接相连。一个PO端点与一个PI端点如果有一样的名字和功能，能直接相连。一个PI端点可能有两个扇出但没有扇入。一个PO端点只有一个输入但没有输出。端点并不是一个逻辑node也没有逻辑功能。指向端点的指针集合不能通过一个内部node的DFS遍历方法来获取。在logicnetwork网络中，指向PI/PO端点的指针集合储存在相应的数组。

2.1.3AIG网络

AIG网络是ABC中所采用网络的内部主要表示形式。AIG是ABC所特有的，其每个node是两输入的与门和一个扇入/扇出边，并且这个边有一个可选属性指示是否对该边进行取

反。在构造AIG的同时，AIG能被压缩通过使用一级结构散列，它使得每一对边最多只能做为一个结点输入。这样，结构散列就能保证：对于每个与门结点，就没有其它带相同子结点的与门；没有仅一个输入的结点；每个与门的层次就能反应输入的层次。所有这些，使得操作AIGs比较操作Logicnetworks要快很多。

2.2发现问题及其根本原因

在研究的过程中，我们发现会产生ABC输入mv文件经过优化后的blif文件的输入输出的个数与原先读入mv文件的输入输出个数的不一致问题。这是因为ABC输入mv文件时，主要经过了两步处理。输入mv时，ABC把mv文件转成了NetList，这一步是完全正确的，但在NetList转成AIG时，出现了问题，ABC把latch的输入当成了主输出，把latch的输出当成了主输入，从而造成了有几个latch，就多了几个输出输入。

笔者认为根本原因在于，ABC对mv文件中的时序电路支持得有限，在将时序转化为组合的过程中，也就是在NetList转成AIG时，采用了不正确的方式去除了Latch，从而造成了有几个latch，就多了几个输出输入。

3问题的解决方案及生成blif

3.1解决问题

在尝试直接把NetList网络转成AIG网络时，来处理这个问题，都归于失败。最后不得不考虑在生成的中间网络上找解决方法。

首先，ABC处理mv文件的过程如下：

SHAPE\*MERGEFORMAT

然后，我们查看了ABC处理blif文件的过程，如下：

SHAPE\*MERGEFORMAT

经过讨论，我们试想能不能构造出如下的一种处理方法来解决问题：

经过研究，我们发现这条路是可行的。但在解决的过程中我们发现，.mv文件生成的NetList网络与.blif文件生成的NetList网络存在不同。在前面Mv2blif软件的实现方法中寻求灵感，我们试着将这两个相同类型网络转化，最后我们成功解决了这个问题，从而实现了ABC对.mv文件能直接进行处理，并且解决了输入输出个数与原先的输入输出个数的不一致的问题。最终实现了如下版本：

SHAPE\*MERGEFORMAT

3.2生成blif文件

ABC中读入mv文件后形成AIG网络，要想输出blif文件，可进行如下操作：

SHAPE\*MERGEFORMAT

4算法实现及举例

对网络中的功能node进行转换，以下是转换node从AIG功能到BDD功能的算法，对于网络只需要用一个遍历，把其所有node转换即可。

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

{

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

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

unsignedinttopf,topg,index;

statLine(manager);//循环次数加1

one=DD_ONE(manager);//返回manger->one，即常数结点1

//得到结点的正则状态，如果结点取过反，则返回没有取反的状态

F=Cudd_Regular(f);

G=Cudd_Regular(g);

if(F==G){

&nbs

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

elsereturn(Cudd_Not(one));//Cudd_Not为取反

}

if(F==one){

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

elsereturn(f);

}

if(G==one){

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

elsereturn(g);

}

/*检查缓存*/

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

//如果已经有对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结点是否取过反

gv=Cudd_Not(gv);//对gv结点取反

gnv=Cudd_Not(gnv);

}

}else{

&nbs

p;gv=gnv=g;

}

t=cuddBddAndRecur(manager,fv,gv);

e=cuddBddAndRecur(manager,fnv,gnv);

if(t==e){

r=t;

}else{

if(Cudd_IsComplement(t)){

//如果已经存在以Cudd_Not(t),Cudd_Not(e)为孩子的结点，则返回，如没有，则重//新创建一个，并且把index赋值于它。

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

r=Cudd_Not(r);//对r结点取反

}else{

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

}

}

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

cuddCacheInsert2(manager,Cudd_bddAnd,f,g,r);//加入缓存机制

return(r);

}/*endofcuddBddAndRecur*/

这里根据算法，我们举例说明结点功能为AIG，表达式为a*b的情况，其转换成BDD功能，如下所示：

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

5总结

本文简要介绍了传统的逻辑综合方法，并介绍了NetList、LogicNetwork与AIG的网络形式，在实现从MV文件经过ABC处理并优化生成BLIF文件的过程中，分析了过程中产生问题的根本原因，并解决了ABC对读入MV文件的不足，是通过转换了其读入MV文件过程中的网络形式来解决这个问题。最后给出了结点从AIG到BDD功能的转换算法，和一个简单的实例。

参考文献

[1]TheVISGroup．BLIF-MV．UniversityofBerkeley,May1996．

[2]MVSISGroup．MVSISManual．UCBerkeley,February2001．

[3]RÜDIGEREBENDT,GÖRSCHWINFEY,ROLFDRECHSLER．ADVANCEDBDDOPTIMIZATION．UniversityofBremen,2005．

[4]BerkeleyLogicSynthesisandVerificationGroup．ABC:ASystemforSequentialSynthesisandVerification．December2005Release．．

[7]S.Yang．Logicsynthesisandoptimizationbenchmarks.Version3.0．Tech.Report.MicroelectronicsCenterofNorthCarolina,1991．

[8]TheSISGroup．BerkeleyLogicInterchangeFormat(BLIF)．UniversityofBerkeley,

July1992．

[9]JoachimPistorius,MikeHutton,AlanMishchenko,RobertBrayton．BenchmarkingMethodandDesignsTargetingLogicSynthesisforFPGAs．UniversityofBerkeley,2007．