ABC对输入MV文件的解决方案

　　论文关键字：abc mv文件时序　综合

　　论文摘要：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.1 abc中采用的网络介绍
　　在读入特定电路设计文件经过软件处理，就形成当前的网络。abc通过一系列对当前网络的转换来处理这个电路设计类似于sis。abc中的网络有其特定类型，包括netlist，logic network和aig网络，下面简要介绍各个网络。

　　2.1.1 netlist网络
　　如果编程者在输入文件中加入一个新的类型，想成功通过解析就必须熟悉netlist网络的表示形式，因为解析一个输入文件，netlist网络是必然被创建的。netlist可以说是一个基本原始的网络表示形式，它与输入文件的设计一一对应，包含nets，logic nodes，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.2 logic network网络
　　一个logic network实际上是一个netlist去掉nets后的网络，sis就是用logic network网络所表示。在abc，默认的表示是aig网络，但logic network是一种很有效的中间过渡网络表示形式。在logic network网络中只保留 了pi/po/latch/latch-input/latch-output这几种数据结构的名字，丢弃了内部node的名字。因为abc采用aig进行深层次的综合时，一些aig操作很难保存aig结点的名字，比如重写。在logic network中，nodes 能与另一个nodes直接相连。pi/po端点与node直接相连。一个po端点与一个pi端点如果有一样的名字和功能，能直接相连。一个pi端点可能有两个扇出但没有扇入。一个po端点只有一个输入但没有输出。端点并不是一个逻辑node也没有逻辑功能。指向端点的指针集合不能通过一个内部node的dfs遍历方法来获取。在logic network网络中，指向pi/po端点的指针集合储存在相应的数组。

　　2.1.3 aig网络
　　aig网络是abc中所采用网络的内部主要表示形式。aig是abc所特有的，其每个node是两输入的与门和一个扇入/扇出边，并且这个边有一个可选属性指示是否对该边进行取反。在构造aig的同时，aig能被压缩通过使用一级结构散列，它使得每一对边最多只能做为一个结点输入。这样，结构散列就能保证：对于每个与门结点，就没有其它带相同子结点的与门；没有仅一个输入的结点；每个与门的层次就能反应输入的层次。所有这些，使得操作aigs比较操作logic networks要快很多。

　　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;

unsigned int topf, topg, index;

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

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

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

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) {

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 {

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);

} /* end of cuddbddandrecur */

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

图4 aig：表示a*b的功能 bdd：表示a*b的功能

　　5 总结

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

　　参考文献

　　[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．~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．．

　　[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．