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

时间:2021-03-14 18:39:23 计算机网络毕业论文 我要投稿

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

//如果已经有对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 {

       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.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文件的解决方案】相关文章:

《智能ABC输入法》教学反思11-19

ASP的chr(0)文件上传漏洞原理及解决方案11-12

Faded歌曲mv11-26

陈绮贞旅行的意义mv08-26

日语输入法的输入规则04-13

浅谈管理态度的ABC10-31

赵雷《家乡》MV09-02

用PHP脚本在Linux系统上读取输入和对文件进行操作11-23

职称英语abc区别11-15