精华内容
下载资源
问答
  • 逻辑综合
    千次阅读
    2020-12-21 11:13:54

    逻辑综合系列主要说明以下问题:

    • 为什么要逻辑综合
    • 逻辑综合的基本原理
    • 逻辑综合需要提供哪些文件
    • 逻辑综合过程中施加约束
    • 逻辑综合能产生那些结果

    综合是前端设计的重要步骤之一,其过程是将行为描述的电路、RTL级的电路转换到门级,其目的在于:决定电路门级结构,寻求时序与面积的平衡,寻求功耗与时序的平衡,增强电路的测试性。常见的工具是synoosys公司的 Design Compiler,将HDL语言描述的电路转换到基于工艺库的门级网表。

    逻辑综合的步骤为:转译(Translation)、优化(Optimize)、映射(Mapping)

    DC在综合过程中会将电路划分为以下的处理对象:

      

    1. Design:整个需要综合的电路,即我们待综合的对象
    2. Port:最外部的端口,一般是电路与外部交互的IO口
    3. Clock:由于时钟上的任何问题都会对电路造成重要的影响,所以时钟需要单独处理
    4. Cell:被例化的模块
    5. Reference:例化模块的原电路
    6. Pin:Cell自身的引脚,注意与Port的区别
    7. Net:内部连线

    用Design Compiler做综合的流程如下:

    其实施流程为:

    1. 预综合过程(pre-synthesis process)
    2. 施加设计约束(contrainting design)
    3. 设计综合(synthesizing design)
    4. 后综合过程(post-synthesis process)

      ①准备设计文件,DC 的设计输入文件一般为 HDL 文件。

      ②指定库文件,需要指定的库文件包括:

    链接库(link library) 、目标库(target library) 、符号库(symbol library)、综合库(synthetic library)

      下面是库的解释,具体的解释在后面有说,这里先进行简单地概述一下:

     Link library & target library

        Link  library 和 target  library 统称为 technology  library(即工艺库,习惯称之为综合库),technology  library  由半导体制造商提供,包含相关 cell 的信息及设计约束标准,其中:

        Target library:    在门级优化及映射的时候提供生成网表的 cell,即DC 用于创建实际电路的库。

        Link library:      提供设计网表中的 cell,可以跟target_library使用同一个库,但是 DC 不用 link library中的 cell 来综合设计。

      当 DC 读入设计时,它自动读入由 link library 变量指定的库。当连接设计时,DC 先搜寻其内存中已经有的库,然后在搜寻由 link  library 指定的库。

      注:当读入的文件是门级网表时,需要把 link library 指向生成该门级网表的库文件,否则 DC 因不知道网表中门单元电路的功能而报错。 关于工艺库里面的具体内容,后面会专门进行说明。

      Symbol library

      Symbol library 提供 Design Vision GUI 中设计实现的图形符号,如果你使用脚本模式而不使用 GUI,此库可不指定 Symbol library

      Synthetic library

       即为 Designware library ,名字上翻译是综合库,但却常称之为IP库,而不是直译。特殊的 Designware library 是需要授权的(比如使用多级流水线的乘法器),默认的标准 Designware 由 DC 软件商提供,无需指定。

      Create_mw_lib :主要使用DC的物理综合的时候,需要生成物理库

      ③读入设计 :

    设计的读入过程是将设计文件载入内存,并将其转换为 DC 的中间格式,即GTECH 格式,GTECH 格式由“soft macros”  如  adders, comparators 等组成,这些组件来自 synopsys  的 synthetic lib,每种组件具有多种结构。

    读入设计有两种实现方法实现方法:read  和  analyze & elaborate(实际上

    read 是 analyze  与  elaborate 的打包操作  ),下面介绍二者在使用中的区别:

     

    从中可以看到,analyze & elaborate  可以自由指定设计库,并生成 GTECH中间文件前生成.syn 文件存储于 work 目录下,便于下次 elaborate 节省时间,我们一般选择  analyze & elaborate 的方法读入设计。

      ④定义设计环境: 

    定义对象包括工艺参数(温度、电压等),I/O 端口属性(负载、驱动、扇出),统计 wire-load 模型,设计环境将影响设计综合及优化结果。

      ⑤设置设计约束: 

    设计约束包括设计规则约束和优化约束,设计规则约束(design  rule constraint)由工艺库决定,在设计编译过程中必须满足,用于使电路能按功能要求正常工作。设计优化约束定义了 DC 要达到的时序和面积优化目标,该约束由用户指定,DC 在不违反设计规则约束的前提下,遵循此约束综合设计。

      ⑥选择编译策略: 

    对于层次化设计,DC 中有两种编译策略供选择,分别为 top down 和 bottom up。在 top down 策略中,顶层设计和子设计在一起编译,所有的环境和约束设置针对顶层设计,虽然此种策略自动考虑到相关的内部设计,但是此种策略不适合与大型设计,因为 top down 编译策略中,所以设计必须同时驻内存,硬件资源耗费大。在 bottom up 策略中,子设计单独约束,当子设计成功编译后,被设置为 dont_touch 属性,防止在之后的编译过程中被修改,所有同层子设计编译完成后,再编译之上的父设计,直至顶层设计编译完成。Bottom  up 策略允许大规模设计,因为该策略不需要所有设计同时驻入内存。

      ⑦编译: 

    用 Compile 命令执行综合与优化过程,还可以利用一些选项指导编译和优化过程。

      ⑧分析及解决设计中存在的问题 

    DC  可以产生一些报告以反应设计的综合和优化结果,如:时序、面积、约束等报告,这些报告有助于分析和解决设计中存在的问题以改善综合结果,我们还可以利用 check_design 命令检验综合的设计的一致性。

      ⑨存储设计数据 

    DC 不会自动存储综合后的设计结果,因而需要在离开 DC 时手动存储设计数据。比如存储网表、延时信息等数据文件。

    更多相关内容
  • DC逻辑综合学习资料

    2020-11-26 14:38:03
    比较系统的讲解了DC逻辑综合的步骤,概念等关键内容,整合了S家官方学习资料和网络资源以及自己本人经验,纯粹是本人亲自做的PPT,比较适合有一定基础的初学者。交流过程中如有疑问,欢迎指正批评。
  • 逻辑综合工具designCompiler使用教程
  • 逻辑综合

    千次阅读 2020-03-22 23:50:50
    4.1 逻辑综合概述 4.1.1 逻辑综合的概念 综合(synthesis):就是把思想转换为实现欲想功能的可制造的设计。综合是约束驱动 和基于路径的。 在这里,综合也就是把行为级或 RTL 级的 HDL 描述转换为门级电路的过程,...

    4.1 逻辑综合概述
    4.1.1 逻辑综合的概念

     

    综合(synthesis):就是把思想转换为实现欲想功能的可制造的设计。综合是约束驱动 和基于路径的。
    在这里,综合也就是把行为级或 RTL 级的 HDL 描述转换为门级电路的过程,用公式表示 就是:
    综合等于  = 翻译  + 优化  + 映射
    ( Synthesis  = Transiation  + Optimization  + Mapping  ) 用图形表示就是:(见图 4.1)

    2009102711035694078.jpguploading.4e448015.gif转存失败重新上传取消


    图 4.1 综合的概念

    4.1.2 逻辑综合的工具介绍

    。工具操作界面

    设计编译器(Design Compiler 简称 DC)是 Synopsys 综合工具的核心。综合一个设计 时,可以选用两种界面: A 。设计分析器(Design Analyzer 简称 DA)-图形窗口界面。 B 。 dc_shell—命令行界面。
    DA 图形窗口界面的启动:%da
    dc_shell 命令行界面的启动;%dc_shell
    dc_shell 界面的提示符为:dc_shell  >
    dc_shell 命令行界面支持两种脚本语言:dcsh 模式和 dctcl 模式。
    dcsh 是使用源于 Synopsys 的语言。 dctcl 使用工具命令语言( Tool Command Langugae )。
    dcsh 模式和 dctcl 模式比较
    tcl 是一种开放型的工业标准语言。它比 dc_shell 更加强大。
    启动 dcsh 模式用 dc_shell 命令,启动 dctcl 模式用 dc_shell  -t

     

    2009102711034757644.jpguploading.4e448015.gif转存失败重新上传取消


    如果你已经有了 dcsh 的 setup 文件或脚本文件(.scr),你想转换为 Tcl 的 setup 文件和约束文件,则我们只需执行下面命令即可.
    setup 文件的转换:
    设 dcsh 的 setup 文件为.synopsys_dc.setup.old,要转换为 Tcl 的 setup 文
    件.synopsys_dc.setup 则
    % dc-transcript  .synopsys_dc.setup.old  .synopsys_dc.setup 脚本文件的转换:
    设 dcsh 的约束文件为 old_scriptfile.scr,dctcl 的约束文件为 tcl_script.tcl ,则 % dc-transcript old_scriptfile.scr tcl_script.tcl
    由于 dcsh 和 dctcl 是可以转换的,以下的介绍中,在支持 dcsh 的地方,将都用 dcsh 命令。
    。Synopsys 格式
    大多数 Synopsys 产品都支持和共享一个公用的中间结构--”db”格式。 db 文件是描述
    文本数据的二进制已编译表格式。 DC 可以读和写以下的所有格式: Verilog , VHDL ,
    EDIF 。
    逻辑综合的流程
    流程图如图 4.2 :
     

    2009102711044763181.jpguploading.4e448015.gif转存失败重新上传取消
    图 4.2 逻辑综合设计流程

    4.2  setup 文件,库以及一些基本概念
    4.2.1    setup 文件

    把行为级描述转换为门级电路,在映射过程种,必须有技术库的支持,否则它将找不 参照的元器件。为此我们在综合前必须在 setup 文件中设置好综合所需的技术库。这里所 需的技术库的格式为.db 和.sdb 格式。技术库的描述略。
    Synopsys 的设计编译器(Design Compiler,简称 DC)提供了三个同名的 setup 文
    件.synopsys_dc.setup 。一个为安装目录下的 setup 文件,它提供系统管理员指定的系统变量设置。一个为你根目录下的 setup 文件,它提供你的工作环境变量的设置:公司的名 字,你的名字,背景色。这是由用户指定的 DC 值。
    一个为你工作目录下的 setup 文件,它规定了你设计所指定的 DC 值,如:
    search path, target library, link library  , symbol library.
    启动 DC 工具时,它依次读入这三个文件,且读的越后的文件优先级别更高,即相同的

    变量,后面的设置值将覆盖前面的设置。
     根目录下的 setup 例子如下:
    company  =  “ your_company”;
    designer  =  “your_name”;
    view_blackground  =  “black”;
    工作目录下的 setup 文件例子如下:
    dcsh 模式:
    searsh_path  =  {}  + search_path
    link_library  =  {MTC45000.db};
    target_library  =  {MTC45000.db};
    symbol_library  =  {MTC45000.sdb};
    define_design_lib work  -path work  ;
    Tcl 模式:
    set search_path  [concat  [list]  $search_path]
    set link_library  [list MTC45000.DB]
    set target_library  [list MTC45000.db]
    set symbol_library  [list MTC45000.sdb]
    define_design_lib work  -path work
    说明:
    search_path:为 DC 提供未分析设计标准的搜寻路径,亦即你的技术库的搜寻路径。
     如果你的库不是放在 DC 的安装目录下的库的目录下,则你还需修改你的 search+path,
     指定库的目录。方法是:
    dcsh 模式:
    search_path  =  {directory}  + search_path dctcl 模式:
    set search_path  [concat  [list directory]  $search_path] link_library:
    指明了你的设计所参照的子设计的位置。 DC 根据 link_library 寻找它所参照的设 计。如果参考设计的完整名字在 link_library 里没有定义,则需在 search_path 中包括这 参考设计的路径。 link_library 定义了被单独使用的元器件的库的名字。即,
    link_library 里的元器件是不被 DC 所 inferred 的。


    4.2.2 库

    target_library:
    指明了在你优化设计时用到的元器件的库。
    symbol library:指明了含技术库元件的图形描述的库。


    4.2.3 对象
    在进行综合时,我们经常会遇到一些对象的概念。搞清楚这些概念具体是指代什幺是 很有必要的。
    Design: 对应于执行一定逻辑功能的电路描述。 design 可以是独立的一个,也可以含有其他的子设计。子设计虽然可以是设计的一部分,但是 Synopsys 也把它看成是一个设计。
     Cell: 是 design 中的子设计的一个 instance 。在 Synopsys 的术语中, cell 和
    instance 被认为是一样的。
    Reference: cell 或 instance 参考的源设计的定义。
    Port: 指主要 inputs,outputs 或 design 的 IO 管脚。
    Pin: 对应于设计中的 cell 的 input,output,或 IO 管脚。
    Net: 这是信号的名字,即通过连接 ports 与 pins 或 pins 与 pins 而把一个设计连在一 起的的金属线的名字。
    Clock: 作为时钟源的 port 或 pin..
    library: 对应于设计的综合目标或参考连接的工艺指定单元的集合。 具体示例如图 4.3 :
     

    2009102711053411992.jpguploading.4e448015.gif转存失败重新上传取消

    图 4.3  对象

     

    4.3 设计分块

    分块(partitioning):把复杂的设计分成各个小部分的过程。
    Partitioning  = Divide  +Conquer
    概念如图 4.4

    2009102711054386054.jpguploading.4e448015.gif转存失败重新上传取消 
    图 4.4 分块的概念


     

    分块是成功的进行综合和布局布线的关键。传统上的分块是根据逻辑功能,而不考虑综合的。固定的边界降低了综合结果的质量,使优化难以进行。正确的给设计分块能大大的增 强设计结果,而且降低编译的时间和简化脚本的管理。
    以下是分块的几条建议:
    1.   把相关的组合逻辑保留在同一模块中;
    2.   考虑设计的重用;
    3.   根据它们的功能划分模块;
    4.   把结构逻辑和随机逻辑分开;
    5.   合理的块大小(每个块最大大约为 10K 个门);
    6.   把顶层分块出来(独立 I/OPads,边界扫描 Boundary Scan  ,核心逻辑,Clocks);
    7.   顶层避免存在 glue-logic;
    8.   把状态机和其他逻辑独立开来;
    9.   避免在一个块中存在多时钟;
    10.  把用来同步多个时钟的块独立出来;
    11.  分块时考虑你的版图设计。
    块的产生: entity 和 module 语句定义了层次的块。 entity 或 module 的示例也产生了一个新层。算术电路(  +,-  ,*,。。)的 inference 也能产生新层。 process 和 always 语句不会产生层次。
    逻辑优化并不能穿过块的界线。最好的分块是把相关的组合逻辑和它的目的寄存器聚集在同一个块中。这样组合优化技术能被完全的利用,时序优化也可以吸收一些组合逻辑到复杂的触发器中(JK,T,Clock-enabled)。好的分块如图 4.5 所示:

     

    2009102711060981073.jpguploading.4e448015.gif转存失败重新上传取消

    图 4.5 最佳的分块

    什幺是 glue-logic :就是用一个组合逻辑把几个块结合起来,这个组合逻辑就是 glue logic.由于这 glue logic 不能被吸收,优化是被限制的,要删除这 glue logic,我们把这 NAND 放进后面的逻辑电路中。这样 glue logic 就可以和其他逻辑一起优化了。顶层设计只 能是一个结构的网表,不需要被编译。换句话说,就是顶层不能含 glue logic ,当然其他 层最好也是不要存在 glue logic 。
    分块时各个块的大小最好不要相差太大,因为,太小多余的边界将限制优化,太大编 译的时间又太长。尽量减少不必要的层。编写 HDL 源代码时每一个块的输出最好都是通过 寄存器实现,这样可以可以简化约束的说明和方便优化。 input delay 和 output delay 可 以不用设置。块的名字必须和文件名相同,否则在分析是将会出错。
    初始的分块由 HDL 定义。不满意的话, DC 可以进行调整。 DC 分块的命令是 group 与 ungroup.
    例如我们把两个块 U1,U2 合并为一个块 U23,则转到当前层后 group  {U1,U2}  -cell_name U23
    ungroup  {U23}
    命令的具体应用请查看在线帮助。


    4.4 读进设计

    DC 的输入格式可以是 Verilog HDL,VHDL 等硬件描述语言,可编程逻辑阵列(PLA), EDIF2000 ,格式。
    对于 HDL 格式, DC 要求用 analyze 和 elaborate 读进设计。
    analyze :读进 VHDL,或 Verilog 文件,检查语法和可综合逻辑,并把设计已中间格式 存在设计工作库(WORK)中。 analyze 后,在 DA(Design Analyzer)中并看不到有什幺东西出 现。 analyze 命令可以同时对若干个文件执行操作。
    elaborate :从工作库中把 analyze 后的中间文件转换为一个设计。 elaborate 命令 用综合的操作符代替 HDL 的操作符,且决定正确的总线大小。 elaborate 命令后,在 DA 中 你可以看到出来了一个一个的模块。一个文件一个,即一个 entity 或 module 一个。
    elaborate 一次只能对一个文件进行操作。这点需要注意。
    在这里我们需要提醒一下的是, entity 或 module 的名字,即设计的名字必须和文件
     

    名相同。因为 analyze 后它存在 WORK 里的名字是设计的名字(entity or module)而不是你源程序的文件名,所以如果你 elaborate 的是文件名,那幺如果设计和文件名不同, DC 将 找不到你的设计,出现 error 。当然如果你不厌其烦的特别让 elaborate 他的设计名,这 问题就不存在了。
    对于其他非 HDL 文件, DC 用 read 命令读进设计。
    read 命令并不产生中间文件,而是之间把他转换为了 DC 里的符号。
    理论上, read 可以读进所以的设计,不管是不是 HDL 文件,但是建议对 HDL 文件用 analyze 和 elaborate 读。
    对于 VHDL 的 package 文件,我们应该用 read 命令读,且必须在读进 VHDL 源程序前读。
     

    4.5 设计约束
    为了从 DC 中能得到合适的结果,设计者必须通过描述其的设计环境,目标任务和设计规则来系统的约束其设计。约束包含时序和面积信息。它们通常是从规格说明中提取出来的。 DC 用这些约束去综合和优化设计以符合其目标任务。本文只讲些最常用的约束命令,且不会讲的很详细。约束命令的具体用法请 参照在线帮助。
     

    4.5.1 设计环境
    几个环境变量含义如图 4.6 所示:

     

    2009102711065763366.jpguploading.4e448015.gif转存失败重新上传取消
    图 4.6 环境变量
     

     

    2009102711070628369.jpguploading.4e448015.gif转存失败重新上传取消
    图 4.7 时序图

    set_operating_conditions :描述了设计的工艺,电压和温度等条件。通常以
    WORST,TYPICAL,BEST 的情况进行描述。技术库通常具有正常情况的的特性。为了查找芯片

    商提供的运行环境,我们可以用 report_lib libname 命令。
    set_operating_conditions  例子:
    dc_shell> current_design  =  “addtwo”
    dc_shell> set_operating_conditions  -max  “typ_124_4.50” 最坏(即最慢)的运行条件是最低的电压和最高的温度。
    最好(即最快)的运行条件是最高的电压和最低的温度。
    对于设置 the best case 的运行条件是:
    set_operating_conditions  -max WORSTC_OPCONDS  -min BESTC_OPCONDS
    如果你想检查你的设置,你可以用 report_port  -verbose,write_script 和 report_design 命令。
    set_load: 定义了输出单元总的驱动能力。
    set_load   
    例子:
    直接指定一个值: dc_shell> set_load  4 find  (port OUT1)
    利用 load_of(lib/cell/pin)命令把技术库的门作为负载数的衡量: dc_shell> set_load load_of(CBA/AN2/A) find  (port OUT1)
    load_of(lib/cell/pin)可以乘以系数:
    dc_shell> set_load load_of(CBA/IVA/A)  *  3 find  (port OUT1)
    set_driving_cell: 模拟了驱动输入管脚的的驱动单元的驱动电阻。定义了信号到达输入管脚的传输时间,可以直接指明驱动输入管脚的外部实际单元。
     

    展开全文
  • Tcl与Design Compiler 八DC的逻辑综合与优化下.pdf
  • eew.zip_逻辑综合

    2022-09-21 08:39:40
    基于矩阵初等变换的量子逻辑电路综合的新方法.
  • DC.zip_逻辑综合DC

    2022-09-22 23:57:24
    利用DC_进行逻辑综合(DC课件整理),很有用的资料!有助于理解
  • 你要学好Verilog的必备知识。FPGA是什么,FPGA芯片里面有什么,零基础学FPGA不要开始就拿个开发板照着别人的东西去编程。很多开发板的程序写的很烂,我也做过一段时间的开发板设计,我觉得很大程度上,开发板在...
  • 逻辑综合知识点总结 持续更新中...

    千次阅读 多人点赞 2021-04-14 14:21:09
    逻辑综合知识点总结


    什么是逻辑综合


    逻辑综合,是将较高层次的描述自动地转换到较低抽象层次描述的一种方法。这里是指将RTL级的描述转换为门级网表的过程。

     逻辑综合要求的输入除RTL描述的程序模块或者原理图文件或波形文件外,还需要另外两个输入文件,第一个输入就是综合工具支持的工艺库(如TTL工艺库,MOS工艺库,CMOS工艺库),这些工艺库中包含一些标准的单元。在综合时,综合工具会将RTL级代码描述的设计用工艺库中的标准单元转化为逻辑电路。另一种输入是约束条件,用于决定综合过程中的逻辑优化方法。约束条件中一般包含时间,面积,速度,功耗,负载要求和优化方法等,甚至还包含综合时需要注意的设计规则。

    逻辑综合输出的结果是:门级网表

    逻辑综合步骤:
    第一步 (compile):
     将RTL描述转换成为未优化的门级布尔描述(如与门,或门,触发器,锁存器等)。该过程不受用户控制,最终转换结果是一种中间结果,格式随不同综合工具而异,对用户不透明,将RTL描述中的IF,CASE,LOOP语句及条件信号代入和选择信号代入语句等转换成中间的布尔表达式。

    第二步 (logic optimization):
     布尔优化过程,是将一个非优化的布尔描述转化成一个优化的布尔描述的过程。主要是采用某种优化方法,如资源分配、公共子表达式、代码移位、公因子提取、交换律和结合律的运用、死代码消除及常量合并等都是一些基本的优化方法,这一步也称为工艺无关的综合。
    图1
    第三步 (technology mapping):
     门级映射过程,取出经优化的布尔描述,并利用从工艺库中得到的逻辑和定时上的信息去生成门级网表,确保得到的门级网表能达到设计的性能和面积要求。这一步也称为工艺相关的综合(工艺映射),流程图如图。

     我们最终将根据优化的布尔描述,工艺库和用户提出的约束条件,将输出一个优化的网表,该网表的结果是以工艺库单元为基础而建成的。


    compile


    在这里以Verilog开源仿真工具Icarus Verilog为例解释这两个名词的具体含义,这一部分参考自 iVerilog的工作原理,Icarus Verilog是由Stephen Williams开发的Verilog仿真工具,官网http://iverilog.icarus.com,代码开源在https://github.com/steveicarus/iverilog

    在这里插入图片描述

     编译就是从接收命令行参数开始,到预处理(verilog宏展开,文件include,条件编译),Verilog语法解析(关键字识别、语法解析),最后转换成内部的数据结构(就是用各种class、结构体,如module、net、scope、generate、statement、expression等)的过程。

     简单的讲,就是识别Verilog文件,转成内部的数据库。经过编译后,各个Verilog文件在库里是独立的。


    elaboration


     elaboration就是把库里的数据,有机的组织成一个树型结构,树的顶端是root,往下是tb或者设计顶层,然后是例化的子模块。如下图:

     elaboration的过程中还需要处理parameter的传播、defparam的覆盖,根据generate语句来产生实际的电路等。另外Verilog的系统函数(如 f i n i s h 、 finish、 finishdisplay、$dumpfile等)也是在这一步进行识别,然后与仿真器预实现的函数库(.so或.a)进行关联。

     经过处理后,这个树型结构就可以准确的表达整个设计(包括testbench)。

     elaboration还会根据优化选项进行一定的优化,简化树型结构。比如,去除设计层次,用信号命名来表示原层次关系。还可以进行边界优化,合并组合逻辑,合理的优化会很大程度上加速仿真。


    术语表


    Onset Offset Dont’care(DCset)


    在二级逻辑以及多值逻辑综合优化工具espresso中常会听到关于Onset和Offset的说法,这种说法在电路的PLA逻辑表示中尤为突出,而且在电路的BDD逻辑表示中也有涉及,假定给定一个电路的函数及其真值表如下:

    在这里插入图片描述

    • Onset
      函数的Onset是指所有使得函数最终的真值值等于1的最小项的和,例如对于本例的函数而言,Onset=a'bc+ab'c+abc=ac+bc
    • Offset
      同理可推导,Offset是指所有使得函数最终的真值值等于0的最小项的和,例如对于本例的函数而言,Offset=a'bc+a'b'c+a'bc'+ab'c'+abc'
    • Dontcare(DCset)
      Dontcare在本例中没有得到体现,但是通过上面两例可以推导出一个函数的DCset就是指当函数最终的真值值存在无关项的时候,所有使得函数f结果为无关项x的最小项的和。
      在这里插入图片描述

    Boolean space(B^n)


    一个电路函数所有取值的可能性,共有2^n种可能性。
    在这里插入图片描述
    所以对于一个具有n变量的电路逻辑函数,共具有2^n个节点,同时具有2^(2^n)个不同的函数。


    TFI TFO logic network


    • logic network

    Logic networks are directed acyclic graphs (DAGs) composed of logic gates and realizing Boolean functions, which are functions defined over the Boolean space B = { 0 , 1 } , taking primary inputs as inputs and presenting the function outputs at the primary outputs. In this paper, we work with and-inverter graphs (AIGs), but this framework can also be applied to other types of logic networks.

    • TFI TFO
      该节点所有的扇入(出)节点,一次递归到pi或者po。

    A gate in a logic network usually computes a simple function of its fan-ins, and passes the resulting value to all of its fanouts. In the case of AIGs, a gate is always an AND gate, and the inverters are represented by complemented wires with no cost (that is, they do not add to the circuit size). We also refer to a gate as a node. The transitive fan-in (TFI) or the transitive fan-out (TFO) of a node n is a set of nodes such that there is a path between n and these nodes in the direction of fan-in or fan-out, respectively.


    literal Cubes List of cubes


    literal通常会翻译为文字,一个文字是指一个变量x或者其反变量x',例如文字x代表逻辑函数f,则f={x|x=1},文字x'代表逻辑函数g,则g={x'|x'=0},如下。
    在这里插入图片描述
    Cube是电路逻辑函数的一种表示方式,放在这里作为一种常用术语以作了解。cube是指一系列文字函数的和(文字数的结合),防止翻译有误,附上英文引用:

    A cube is defined as the AND of a set of literals functions (‘conjunction’ of literals).

    假设对于一个函数C=x1'x2x3',则它用cube表示如下:
    在这里插入图片描述
    同时有以下几点需要注意:

    • 如果C属于函数fC是一个cube,那么C是函数f的一个蕴涵项。
    • 如果C属于布尔空间B^nCk个文字数,那么|C|包含2^(n-k)个顶点。
      在这里插入图片描述
    • 一个具有n个变量的蕴涵项是一个最小项。

    List of cubes说白了就是一系列cubes的集合 (sum of cubes),等价于积之和 (sum of products, SOP),下文中将会有介绍,这里不再做赘述。


    DAG FI != PI FO != PO CONE support MFFC


    详见本节后附图示例!!!

    • DAG
      一个电路可以被表示为一个有向无环图 (Directed Acyclic Graph) C(G,N),其中G代表具体的逻辑门,而N表示连接这些逻辑门的有向边,对于每一个门G都被赋予了一个具体的布尔逻辑函数Fg,该门会根据具体的输入计算出输出。

    • FI
      Fanin和primary input的概念不能混淆,前者表示当前该节点所有的前导节点,即该节点的所有扇入–》FI(g)={g'|(g',g) belongs to N},而后者表示该电路所有的原始输入。

    • FO
      同上,Fanout和primary output的概念也不能混淆,前者表示当前该节点所有的后导节点,即该节点的所有扇出–》FO(g)={g'|(g',g) belongs to N},而后者表示该电路所有的原始输入。

    • CONE
      一个门gCONE是指该门所有的传导性扇入FI以及它本身。

    The CONE(g) of a gate g is the transtive fanin of g and g itself

    • SUPPORT
      一个门g的SUPPORT是指该门g的所有原始输入PI。

    The SUPPORT(g) of a gate g are all inputs inn its cone.

    • MFFC
      一个节点n或者门g的MFFC是指该门g的扇入CONE的一个子集,该子集中包含了一些节点,这些节点满足的条件是每一条经过这些节点到最终输出PO的路径都需要经过该门g或者该节点n,这样一个FI CONE的子集才能被称作为MFFC。
      说白了就是一旦该节点被去除,其部分前导节点不能到达PO的话,那么这些前导节点的集合就是MFFC。

    A maximum fanout free cone (MFFC) of a node n is a subset of the fanin cone containing only nodes such that every path from these nodes to the POs passes through n. Informally, if a node is removed, the nodes in its MFFC are also removed.

    图示例:对于节点⑥而言,所有的FI CONE为{1,2,4},没有一个扇入满足MFFC的条件,所以该节点不具有MFFC,但是对于节点⑤而言,它的MFFC是 {3}。
    在这里插入图片描述

    Tautology

    找到满足条件的解使得函数的值为 0.

    Find an assignment to the inputs that evaluate a given vertex to “0”.

    SAT

    找到一组满足条件的解使得函数的值为 1.

    Find an assignment to the inputs that evaluate a given vertex to “1”.

    这意味着在对于一个存在反相器的Netlist边进行求解时,SAT和Tautology是等价的

    cover

    如果函数f是由一系列cube构成的,那么这些cube的集合叫做这个函数f的cover,示例如下。

    A set of cubes that represents f is called a cover of f.

    在这里插入图片描述

    cont’d…

    Experienced optimization guide from papers.

    • Scalable Logic Synthesis using a Simple Circuit Structure, Sec 2.4, Alan, 2006

    A tree-like(non-reconvergent) structure does not lead to any don’t-cares in the local space of the node,don’t care may not get better qor for this kind of structure.

    1.常用函数逻辑表示


    1.1逻辑函数的最小项


    根据逻辑函数的概念,一个函数的表达式不是惟一的,例如:
    在这里插入图片描述
    在最后一个函数的表达式中。我们可以看到:

    • 每个乘积项都包含了全部输入变量;
    • 每个乘积项中的输入变量可以是原变量或者反变量;
    • 同一输入变量的原变量和反变量不会同时出现在同一乘积项中

    这样的乘积项我们称之为最小项。

    为什么称它为最小项呢?因为对于n个输入,变量的取值组合有2^n种,在这所有的组合中,只有一种是的乘积项的值取1,其他的组合都使得乘积项取0.

    全部由最小项相加构成的与-或表达式称之为最小项表达式,这是与-或的标准表达式,也可以被称为标准积之和式(Sum-of-Product,SOP)


    1.2 SOP表示


    由函数的最小项的表达式可以看出,任何一个函数都可以表示为SOP的形式,这个不难理解,表达式如下:
    在这里插入图片描述
    其中mi代表最小项,ai表示该最小项取值1或者0。

    1.2.1 SOP变换(RM逻辑)

    由前所述,我们知道在一个最小项里面,原变量和反变量不可能同时存在,所以对于任意两个最小项mimj(i not equal j)而言,它们“与”的结果都是0,因此“或”运算符可以替换为“异或(Exclusive-OR)”运算符,转换后的表达式如下:
    公式一
    在这里插入图片描述
    其中bi代表1或者0,pi代表乘积项(i not equal j),更准确的说应该是最小项。

    结合前面已经讲到过的,现在我们引入函数不相交的概念,首先我们对于前面的函数SOP表示进行重新的定义:
    则任意一个n变量函数都可以被表示如下:
    在这里插入图片描述
    Pi 表示乘积项,k表示乘积项的个数,U表示乘积项之间的逻辑“或”关系,把所有乘积项的集合定义为S,在这里需要注意的是,乘积项与最小项是不同的概念,乘积项包含最小项,对于每一个乘积项Pi,可以改写为最小项的形式:
    在这里插入图片描述
    其中x表示变量。
    定义1:

    对于两个变量xixj,把它们的相交计算记作:
    在这里插入图片描述
    则存在以下表达式,其中“-”表示不确定项:
    在这里插入图片描述
    定义2

    对于两个乘积项,pw和pv(pw、pv属于S且w不等于v),两者的相交运算记作:
    在这里插入图片描述
    pwpv存在i位上(i<=i-1):
    在这里插入图片描述
    则表示pwpv不相交,当函数SOP形式的任意两项不相交时,可以将乘积项直接写成以下形式:

    公式二
    在这里插入图片描述
    需要注意的是,这里与公式一的区别在于,公式一是对于最小项可以直接做“异或运算,而这里是在任意两两乘积项不相交的前提下直接做异或运算,也可以称作为传统的Reed-Muller(RM)逻辑,即只包含“与”“异或”运算符。

    • 示例

    在这里举一个例子,例如对于以下表达式,通过定义可以发现两个乘积项是满足不相交定理的,所以可以直接对两个乘积项进行“异或”操作:
    在这里插入图片描述

    1.2.2 shannon分解

    根据前面介绍的SOP的基础知识可以知道,对于任意一个函数,都可以表示为以下的形式(香农展开):
    在这里插入图片描述
    另一种理解的方式如下,可以理解为二选一的MUX,除去变量x或者其反变量后的表达式为MUX的两个输入,而x为选择变量:
    在这里插入图片描述

    • 下面通过一个例子对香农分解进行更好的解释:
      在这里插入图片描述

    我们会发现到最后一个函数通过香农分解化为了最小项SOP的形式。

    1.2.3 shannon cofactor

    通过前面的介绍已经知道,任何一个函数都可以通过香农展开写成以下形式:
    在这里插入图片描述
    其中对于两个子函数,分别被称为positive-cofactornegative-cofactor,并且它们等价于表达式F(xi=1)F(xi=0)
    在这里插入图片描述
    因此,香农展开可以被写作下面这种简单的形式:
    在这里插入图片描述
    此时表达式F(xi=1)是positive cofactor,F(xi=0)是negative cofactor。香农展开也可以通过简单的展开进行证明如下(0同理):
    在这里插入图片描述

    1.2.4 Boolean Derivatives(布尔导数)

    TODO


    1.3 BDD

    在这里插入图片描述


    1.3.1 BDD

    BDD简称为二元决策树,是一种规范的电路(布尔函数、算术函数、代数函数)逻辑表示方式,BDD电路表示主要是基于香农展开:
    在这里插入图片描述
    在这里插入图片描述

    是一种相对于布尔函数而言具有相对紧凑的数据结构,BDD满足以下几个要素:

    • 具有一个根节点root,两个字节点01
    • 每一个节点都有两个子节点,对应着一个具体的变量
    • 是一个香农因子展开树,该项是针对于BDD而言,ROBDD不具备此项

    例如对于一个给定电路的逻辑函数如下,最简单(naive way)的BDD表达方式是根据真值表一步一步向下表示如下:
    在这里插入图片描述
    其实BDD所实现函数的功能就是通过指定所有指向1的路径,也就是我们前面所说的Onset,如下示例:
    在这里插入图片描述
    以下是BDD电路逻辑表示的一些优点,为了保证理解的准确性,这里不做翻译,请查看以下引用部分。

    • By tracing paths to the 1 node, we get a cover of pair wise disjoint cubes.
    • The power of the BDD representation is that it does not explicitly enumerate all paths; rather it represents paths by a graph whose size is measures by its nodes and not paths.
    • A DAG can represent an exponential number of paths with a linear number of nodes.
    • BDDs can be used to efficiently represent sets
        interpret elements of the onset as elements of the set
        f is called the characteristic function of that set

    1.3.2 OBDD

    输入变量是有序的排列,即从根节点到最终的0-1的每一条路径的变量顺序一致,示例如下:
    在这里插入图片描述

    1.3.3 ROBDD

    ROBDD全称为reduced ordered BDD,其实从英文全称就可以看出来与BDD相比,ROBDD主要差异体现在reducedordered两个方面:

    • Reduced
      任何具有两个相同子节点的节点都会被移除,这一过程在一些文献中也被称作为结构性哈希,目的同此

    • Ordered
      子节点上的因子变量在所有路劲上始终遵循着同一变量顺序,例如:
      在这里插入图片描述
      接下来给出一个BDD和ROBDD的具体电路表示示意图,可以一目了然的看出二者的差距,当然,具体的BDD逻辑表示会根据用户定义的变量顺序不同而不同。
      在这里插入图片描述
      除此之外,ROBDD还要遵循两个减少(reduction)规则:

    • Rule1:如果任意节点的两个子节点是相同的,那么该节点将会被删除

    • Rule2: 如果两个图有同构(isomorphic)图,将会用其中一个来替换它们

    这两条规则使得每一个节点都可以代表一个不同的逻辑函数,这里针对两条规则举两个示例。

    • Rule1
      在这里插入图片描述
    • Rule2
      在这里插入图片描述

    1.3.4 BDD的实现…

    1.3.5 BDD的应用场景…


    1.4 AIG


    -AIG related

     A combinational And-Inverter Graph (AIG) is a Boolean network composed of two-input ANDs and inverters. To derive an AIG, the SOPs of the nodes in a logic network are factored, the AND and OR operations of the factored forms are converted into two-input ANDs and inverters using DeMorgan’s rule, and these two-input ANDs are added to the AIG manager in a topological order. The size (area) of an AIG is the number of its nodes; the depth (delay) is the number of nodes on the longest path from the PIs to the POs. The goal of AIG minimization is to reduce both area and delay.

    • 结构哈希

    Structural hashing of AIGs ensures that all constants are propagated and there is no two-input AND nodes with identical fanins (up to a permutation). Structural hashing is performed on-the-fly by hash-table lookups when AND nodes added to an AIG manager, which helps reduce the AIG size.

    • cut

     A cut C of a node n is a set of nodes of the network, called leaves of the cut, such that each path from a PI to n passes through at least one leaf. Node n is called the root of cut C. The cut size is the number of its leaves. A trivial cut of a node is the cut composed of the node itself. A cut is K-feasible if the number of leaves in the cut does not exceed K. A cut is dominated if there is another cut of the same node, which is contained, set-theoretically, in the given cut.

    • 示例

    1.5 MIG…



    1.6 XMG…


    2.优化算法

    2.1 Lazy Man’s Logic Synthesis

    paper: Lazy Man’s Logic Synthesis Wenlong, Yang Lingli Wang, Alan Mishchenko

    2.1.1 Contributions

    一种基于预先计算存储库的电路优化方法。

    • A new way of performing logic synthesis. Instead of deriving new circuit structures during runtime of a logic synthesis algorithm, the structure is retrieved from a precomputed library.
    • A new way of accumulating circuit structures in a library and hashing them using a semi-canonical form, which trades speed of computation for reduced memory.
    • Analysis of the logic synthesis benchmarks to show the number of frequently occurring semi-canonical classes of 12-input functions and how much memory is needed to represent a realistic library of these functions.
    • Promising results of delay optimization after FPGA mapping into 4-LUTs and 6-LUTs, obtained using the proposed approach to logic synthesis.

    2.1.2 Why proposed ?

    总结:保存更多的电路snapshot,期望对于节点进行替换达到面积或者delay最好。

     Different tools perform logic synthesis in different ways resulting in different circuit structures. These differences occur because implementations use heuristics and pursue different optimization goals. As a result, there is no “best” circuit structure for a given function. Sometimes even a suboptimal structure may be useful. For example, the result of technology mapping depends on the initial circuit structure [10]. In some cases, a suboptimal circuit before mapping leads to a better result after mapping.
     This is why, in many applications, it is desirable to have multiple structural representations of each function. Hence, it is necessary to run different tools and different scripts and produce several structural snapshots of the same design. However, maintaining multiple tools or routinely applying multiple synthesis scripts is expensive and inefficient.
     The proposed approach named “lazy man’s logic synthesis” learns from the output of different tools applied to various designs and creates a library of AIG structures. When these structures are available and compactly recorded, there is no need to perform traditional logic synthesis. It is enough to check whether a function is already present in the library. The process of looking up is made fast by hashing functions using an affordable semi-canonical form described in this paper.

    2.1.3 Background

    • AIG related
      Please refer to Section 1.4.
    • NPN equivalent

    Two functions are NPN-equivalent if one of them can be obtained from the other by negation and/or permutation of the inputs and outputs

    • positive minterm

    A positive minterm is a complete assignment of input variables, which makes the function evaluate to 1.

    2.1.4 Algorithm

    总结:基于预先计算存储库的优化算法。

    LMS is based on collecting, storing, and re-using circuit structures of Boolean functions with 6-12 input variables. Since the total number of completely-specified Boolean functions of N variables is 2(2N), storing all of them is infeasible for N > 4. For larger values of N, only the functions occurring frequently in the benchmarks should be considered. We call such functions practical and give frequency statistics in the experimental results section.

    为何只考虑NPN等价类?

    However, even the number of practical functions can be very large. To reduce this number and memory needed to store them in a library, they can be broken into equivalence classes using a canonical form. In this case, only representatives of equivalence classes are stored in the library.

    • Algorithm 1: Generating semi-canonical form

    对于多输入变量的函数,并不计算所有的NPN等价类,只是根据所跑的benchmark计算practical的类,因此称作semi-canonical form,好处是可以节省大量的run time。
    在这里插入图片描述

    Details: The procedure takes the truth table of a Boolean function and transforms it into a semi- canonical form. This form is the Boolean function of the representative of the equivalence class, to which the given function belongs. First, the output of the function is complimented based on the number of 1s in it. Then, the phase of each variable is decided by the number of the 1s in the negative and positive cofactors. Lastly, the variable ordering is determined by sorting variables using the number of 1s in their cofactors. Variables uCanonPhase and pCanonPerm record the changes in the truth table. They are returned to the calling procedure and later used to determine how to unpermute the subgraphs stored in the library, when this subgraph is used to synthesize a given function.

    • Algorithm 2: Adding structures to library

    预先计算存储的库如何创建

    All the optimized structures are stored in the same AIG manager. A library of N-input functions contains also functions with less than N-inputs, but they are remapped to structures which depend on the variables with the smallest variable indexes. Each circuit structure stored in the AIG is identified by a separate primary output.

    In this paper, we use the LUT mapper if in ABC as a structural cut browser to generate a fixed number of K-input cuts for each node in benchmark circuits.
    在这里插入图片描述

    Here are the commands for library construction implemented in ABC as part of this work:

    1. rec_start: Starts the LMS recorder.
    2. rec_add: Explores cuts of the current network using the cut browser and add useful AIG structures to the library.
    3. rec_filter: Removes those structures form the library, whose semi-canonical classes appear less frequently than the limit given by
      the user.
    4. rec_merge: Merges two previously computed libraries, by combining their circuit structures without the cut browser.
    5. rec_ps: Prints statistics for the currently loaded library.
    6. rec_use: Transforms the internal library to the current network in ABC, so it can be written into a file.
    7. rec_stop: Deletes the current library. Useful before the computation of a new library begins or when it is desirable to free
      the memory used by the currently stored library.
    • Algorithm 3: Perform LMS on subject graph.
      在这里插入图片描述
      优势:
    • SOP balancing uses only one AIG structure derived from an SOP of the function, while LMS has multiple structures to choose from,
      including those derived by SOP balancing, if these were harvested
      during library computation.
    • LMS scales to larger functions (up to 12 inputs and more), while SOP balancing works in practice only when the number of variables does not exceed 8.

    2.1.5 Result

    • 如何创建library

    Before the experiment, rec_start is called. After the experiment, rec_use is called, followed by writing the library into a file.
    read file; st; rec_add; // add the original AIG structures
    • dc2; rec_add; // add structures derived by dc2
    • if -K 8; bidec; st; rec_add;
    • if -K 8; mfs; st; rec_add;
    • if -K 8; bidec; st; rec_add;
    • if -g -K 6; st; rec_add;// add structures created by SOP balancing
    • if -g -K 6; st; rec_add;

    • 实验步骤比较对象
    • Map: st; resyn2; if -K 4 or 6
    • MapC: st; resyn2; dch -f; if -K 4 or 6
    • SOPBC: st; if -gm -K 6; st; resyn2; dch -f; if -K 4 or 6
    • LMSC: st; if -ym -K 6; st; resyn2; dch -f; if -K 4 or 6
    • 实验结果

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2.2 window based resubstitution

    2.2.1 Contributions

    提出了一种可拓展性更强、效率更高的综合算法。

    This paper proposes a resurgence of rewriting and peephole optimization. However, instead of structural matching and rule-based synthesis used in the classical approach, the proposed local transformations rely on efficient modern techniques, such as precomputation, reconvergence analysis, cut enumeration, Boolean matching, exhaustive simulation of small logic cones, and local resource-aware decision procedures based on Boolean satisfiability.

    2.2.2 Why proposed ?

    有效的将工艺无关和工艺相关的优化分离开,同时也能保持更好的可拓展性、更快的速度、更简洁等,而它能保持住这些特性的原因在于:

    • AIG作为同构网络,处理速度较快
    • Instead of graph isomorphic and SOP-based optimization, Boolean functions of a group of AIG nodes is computed in terms of various fanin cuts. Several exhaustive and selective cut computations can be used, including a recent development that can efficiently enumerate all cuts up to 12 inputs.
    • The Boolean functions of cuts are represented using truth tables. Due to the high speed of bit-parallel manipulation, sub-problems arising in local optimization are often solved, without using SAT or BDDs, by exhaustive simulation, which scales up to 16 inputs.

    2.2.3 Background

    • 详见术语表以及section 1.4.

    Exhaustive simulation

    Exhaustive simulation is a practical way of checking equivalence of Boolean function of a node whose size does not exceed 16 inputs. Exhaustive simulation is performed using bitwise simulation of the cone with 2^k different input patterns, where k is the number of leaves. Another way of looking at exhaustive simulation is that it computes the truth-table of the root in terms of the elementary truth-tables set at the leaves.

    Windowing

    如何根据一个节点创建该节点的window,示例如下:
    在这里插入图片描述
    算法的细节可以通过下图进行深入的理解:
    在这里插入图片描述
    图解:

    Figure 2.3.2 shows a 1 × 1 window for node N in a DAG. The nodes labeled I1 , O1 , S, L, and R are in correspondence with the pseudo-code in Figure 2.3.1. The window’s roots (top) and leaves (bottom) are shaded. Note that the nodes labeled by P do not belong to TFI and TFO of N, but represent reconvergent paths in the vicinity of N. The left-most root and right-most root are not in the TFO of N and can be dropped, as explained above

    Reconvergence-driven cut computation

    当从节点输出开始的路径在到达 PO 之前再次相遇时,就会发生重新收敛.

    Reconvergence occurs when the paths starting at the output of a node meet again before reaching the POs. Reconvergence is inevitable due to logic sharing in multi-level logic networks, but excessive reconvergence is often redundant.

    • 基于重新收敛的cut计算

    Present a simple and efficient cut computation algorithm, which computes a cut close to a given size (if such cut exists) while heuristically maximizing the cut volume and the number of reconvergent paths subsumed in the cut.
    在这里插入图片描述

    2.2.4 Algorithm

    Rewriting

    • what is rewriting ?

    贪心算法在预先计算具有更(最)小面积的库中寻找等价的子电路替换当前的节点,以减少AIG网络的节点数目。

    Rewriting is a fast greedy algorithm for minimizing the number of AIG nodes by iteratively selecting AIG subgraphs rooted at a node and replacing them with smaller pre-computed subgraphs, while preserving the functionality of the node.

    ABC中的拓展包括以下几点:

    Using 4-input cuts instead of two-level subgraphs.
    • Restricting rewriting to preserve the number of logic levels.
    • Developing several variations of AIG rewriting that look at
    larger subgraphs and/or attempt to reduce the delay.
    • Experimental tune-up for logic synthesis applications.

    理论上会使用所有的222种NPN类函数,实际上用到的只是其中一部分,原因如下:

      For the purposes of AIG rewriting, all 4-feasible cuts of the nodes are found by the fast cut enumeration procedure. For each cut, the Boolean function is computed and its NPN-class is determined by table lookup. Manipulation of 4-variable functions is fast because they are represented using truth tables stored as 16-bit bit-strings. Altogether there are 222 NPN equivalence classes of 4-variable functions, of which only about 100 appear as functions of 4-feasible cuts in any of the available benchmarks, and only about 40 of these have been found experimentally to lead to improvements in rewriting. The unifying characteristic of these 40 remaining NPN-classes is that they are decomposable using simple disjoint-support decomposition.
     All non-redundant AIG implementations of the representative functions of the 40 equivalence classes are pre-computed in advance and stored in the hash table, hashed by the truth table of their NPN-class. The AIG subgraphs are stored in a shared DAG with approximately 2,000 nodes. This DAG is compiled into our program as an integer array, which noticeably reduced the setup time of the rewriting package.

    • Algorithm
      4-input rewriting algorithm
      在这里插入图片描述

    After trying all available subgraphs, the one that leads to the largest improvement at a node is used at the node. If there is no improvement but “zero-cost replacement” is enabled, a new subgraph that does not increase the number of nodes is used.

    • Example

    Example. Figure 3.1.2 shows three AIG subgraphs for the function F = abc. They are pre-computed and stored. Figure 3.1.3 shows two instances of AIG rewriting. The upper part of the figure shows the situation when Subgraph 1 is detected in the circuit and replaced by Subgraph 2. The lower part of the figure shows two nodes AND(a, b) and AND(a, c) already present in the network. In this case, Subgraph 2 can be replaced by Subgraph 1. In both cases, the network has one node less.

    在这里插入图片描述

    Resubstitution

    • what is resubstitution ?
      对于当前节点,重新使用网络中已经出现过的节点进行表示(真值值相同),如果在某些方面,例如节点数或者depth取得更好的效果,就会被接受。

    Resubstitution expresses the function of a node using other nodes (called divisors) already present in the network. The transformation is accepted if the new implementation of the node is in some sense better than its current implementation using the immediate fanins.

    • Some backgrounds

    In the case of an AIG, the best outcome of resubstitution is when the whole MFFC of the node can be freed and the node’s function can be expressed using other nodes, currently outside of the node’s MFFC. This outcome corresponds to a 0-resubstitution when no new nodes are added to the AIG while the MFFC is removed. Similarly, if the MFFC is composed of more than one node, and there is no 0 resubstitution, the best outcome is given by a 1 resubstitution, which exists if the function of the node, whose MFFC is being considered, can be expressed using the available node and exactly one additional node.

    • re-substitution example
      在这里插入图片描述
      In the AIG shown in Figure 3.2.2 (left), node g has MFFC of size 2 composed of nodes g and p. One node can be saved if node g is replaced by the complement of node f, which does not belong to the original AIG but can be added on top of the already present nodes n and m, as shown in Figure 3.2.2 (right). Indeed, g = a(b + c + d), f = n + m = a(b + c) + ad = a(b + c + d). This resubstitution is an example of applying the algebraic distributive transform.

    Redundancy removal

    #TODO

    2.2.5 Results

    #TODO

    2.3 Rewriting

    paper: DAG-aware AIG rewriting: A fresh look at combinational logic synthesis, Alan, 2006.
    #TODO

    3. 储备知识

    3.1 what is blif ?

    伯克利实验室提出的一种表示逻辑电路的方法。

    The goal of BLIF is to describe a logic-level hierarchical circuit in textual form.

    • example

    .names v3 v6 j u78 v13.15
    1–0 1
    -1-1 1
    0-11 1

    释义如下,

     In a given row of the single-output-cover, “1” means the input is used in uncomplemented form, “0” means the input is complemented, and “–” means not used. Elements of a row are AND ed together, and then all rows are OR ed.

    The translation of the above sample logic-gate into a sum-of-products notation would be as follows:
    v13.15 = (v3 u78’) + (v6 u78) + (v3’ j u78)
    To assign the constant “0” to some logic gate j, use the following construct:
    .names j
    To assign the constant “1”, use the following:
    .names j
    1

    这里只给出了很基本的一种组合逻辑blif格式,如果想了解更多关于blif的内容,请参考文章:Berkeley Logic Interchange Format ( BLIF )

    3.2 setup time和hold time

    请参考本人另外一篇博客: setup time和hold time

    3.3 弄懂时序逻辑

    部分内容转自
    一文详解时序逻辑
    基本RS触发器(推荐)


    组合电路是根据当前输入信号的组合来决定输出电平的电路,换言之,就是现在的输出不会被过去的输入所左右,也可以说成是,过去的输入状态对现在的输出状态没有影响的电路。

    时序电路和组合电路不同,时序电路的输出不仅受现在输入状态的影响,还要受过去输入状态的影响。

    那么,如何才能将过去的输入状态反映到现在的输出上呢?时序电路到底需要些什么呢?

    人类总是根据过去的经验,决定现在的行动,这时我们需要的就是—记忆,同样时序电路也需要这样的功能,这种能够实现人类记忆功能的元器件就是触发器

    按结构和功能,触发器可以分为RS型、JK型、D型和T型,在这里,我们只讲解比较有代表性的类型,RS型和D型。

    3.3.1 RS 触发器

    • 电路图:

    基本含义:
    S是Set 的首字母,也就是设置端,R 是Reset 的首字母,也就是复位端

    触发器属于时序逻辑电路,与组合逻辑电路不同,组合逻辑电路的输出状态只取决于同时刻的输入信号状态。基本RS触发器把输出信号引回到输入信号,形成一个反馈。这样使得输出信号的状态不但取决于同时刻输入信号的状态,也与输出之前的状态有关。

    输出信号的状态就是(Q^(N+1) 次态) 同时刻输入信号的状态就是(S、R) 输出之前的状态就是(Q^N 现态)

    • 真值表

    H/L代表高/低电平,初始态:Q=L、Q#=H、R=L、S=L,表中Q0和Q0#表示的是输入变化以前的输出,RS触发器是最简单的触发器,主要用于防止机械式开关的误操作。:

    在这里插入图片描述
    对照逻辑表达式和真值表更容易记忆
    在这里插入图片描述

    3.3.2 D触发器(A Flip Flop, DFF)

    D触发器的工作原理:在一个脉冲信号(一般为晶振产生的时钟脉冲)上升沿或下降沿的作用下,将信号从输入端D送到输出端Q,如果时钟脉冲的边沿信号未出现,即使输入信号改变,输出信号仍然保持原值。

    在这里插入图片描述

    对应真值表和表达式可以更好理解,摘自百度百科。
    在这里插入图片描述
    在这里插入图片描述

    3.3.3 寄存器

    由于触发器内由记忆功能,因此可以利用触发器方便的构成寄存器。由于一个触发器能够存储一位二进制码,所以把n个触发器的时钟端口连接起来就能构成一个存储n位二进制码的寄存器

    按照功能的不同,可将寄存器分为基本寄存器移位寄存器两大类。基本寄存器只能并行送入数据,也只能并行输出。移位寄存器中的数据可以在移位脉冲作用下依次逐位右移或左移,数据既可以并行输入、并行输出,也可以串行输入、串行输出,还可以并行输入、串行输出,或串行输入、并行输出,十分灵活,用途也很广。

    More details u can refer to this presentation [寄存器讲解]

    展开全文
  • 逻辑综合技术的发展巳经把硬件描述语言 ( HDL ) 推到了数字设计技术的最前沿 逻辑综合工具显著地缩短了设计周期。设计者可以在吏高的抽象层次上进行设计,因而减少了设计时间­。 逻辑综合 简而言之,逻辑综合是在...

    逻辑综合技术的发展巳经把硬件描述语言 ( HDL ) 推到了数字设计技术的最前沿。逻辑综合工具显著地缩短了设计周期。设计者可以在吏高的抽象层次上进行设计,因而减少了设计时间­。

    逻辑综合

    简而言之,逻辑综合是在标准单元库和特定的设计约束的基础上,把设计的高层次描述转换成优化的门级网表的过程。
    标准单元库可以包含简单的单元,例如与门、或门和或非门等基本逻辑门、也可以包含宏单元,例如加法器、多路选择器和特殊的触发器。标准单元库也就是大家熟知的工艺库。在过去逻辑综合用的是设计者的大脑。
    在这里插入图片描述
    计算机辅助逻辑综合工具的出现已经把高层次描述向逻辑门的转化过程自动化了。设计者不需要在脑子里实现逻辑综合,他们现在可以把精力集中在体系结构的方案设计的高层次描述, 精确的设计约束和标准单元库中的单元优化上。这些都作为计算机辅助逻辑综合工具的输入。该综合工具在内部进行几次反复,然后生成最优化的门级描述。同时,设计者不必在屏幕或者纸上画高层次描述而是用HDL 描述高层次设计。VerilogHDL 已经成为一种流行的编写高层次描述的 HDL。图展示了整个过程。
    在这里插入图片描述
    自动化的逻辑综合已经非常有效地减少了高层次设计到门级网表的转化时间。它使设计者 以把更多的时间用于更高层次的描述上。因为把设计转换到门级网表所需的时间大大减少了。

    Verilog HDL综合

    为了逻辑综合的目的 ,目前都在寄存器传输级( RTL ) 层次用硬件描述语言 ( HDL ) 编写设计。术语 RTL 用于表示 HDL 的一种风格 。该风格的 HDL 描述采用了数据流和行为结构相结合的方式。 逻辑综合工具接受寄存器传输级 HDL 描述并把它转化为优化的门级网表。Verilog 和 VHDL 是两种最流行的在 RTL 级上描述功能的HDL语言 。本章讨论基于RTL 的 Verilog HDL 逻辑综合 用于把行为描述转换成RTL 描述的行为综合工具发展缓慢。但是基于 RTL 的综合已经成为当前最流行的设计方法 。 因此只讨论基于RTL 的综合。

    逻辑综合工具并不能完全处理编写的任意结构。一般周期到周期的任何RTL Verilog 结构能被综合工具接受。可进行逻辑综合的语句如下:
    在这里插入图片描述提供的是周期到周期的RTL描述。因此, 这些语言结构用于逻辑综合工具的方式有一些限制。例如, while 和 forever 循环必须由@(posedge cloc k) 或@(negedge clock)语句终止循环,以此强制具有周期到周期的行为,避免组合反馈。另一个限制是逻辑综合忽略所有由#<delay> 结构指定的时序延迟。因此,综合前后Verilog 的仿真结果可能不同。设计者必须尽量减少使用这些有可能导致Verilog 的前后仿真结果不一致的描述风格。此外, 逻辑综合工具也不支持initial结构的转换,因而设计者必须使用复位机制来取代initial结构, 进行电路信号的初始化。
    建议明确地指定信号和变量宽度。定义未指定宽度的变量可能产生庞大的门级网表,因为综合工具可能根据变量定义生成不必要的逻辑。

    要注意和x与z有关的操作符不能用于逻辑综合。如===
    在这里插入图片描述

    部分Verilog结构的解释

    赋值语句

    assign out=(a&b)|c; //转换为:

    在这里插入图片描述在这里插入图片描述always:always语句可用于生成时序和组合逻辑。对于时序逻辑来说, always 语句必须由时钟信号clk 的变化所控制。

    always @(posedge clk)
    q<=d;

    在这里插入图片描述
    函数语句

    function [4:0] fulladd;
    input [3:0] a,b;
    input c_in;
    begin
    	fulladd=a+b+c_in;
    end
    endfunction
    

    逻辑综合流程

    现在我们已经理解了逻辑综合工具如何把基本Verilog语言结构转换成门级描述,下面讨论从RTL描述转换到最优化门级描述的综合设计流程。
    在这里插入图片描述

    RTL 描述
    设计者在高层次上使用RTL结构描述设计。设汁者在功能验证上耗费一定的时间,以确保RTL描述的功能正确无误。功能验证之后, 再把RTL 描述输人到逻辑综合工具中。

    翻译

    在这里插入图片描述未经优化的中间表示
    在这里插入图片描述

    逻辑优化
    在这里插入图片描述
    工艺映射和优化
    在这里插入图片描述
    工艺库
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述工作环境因素也需要作为逻辑综合工具的输入。

    优化后的门级描述

    在这里插入图片描述

    门级网表的验证

    逻辑综合工具生成的优化后的门级网表必须验证其功能的正确性。另外,如果时序和面积约束太严格,综合工具有时不能完全满足这些要求,这时需要在门级网表层次进行独立的时序验证。

    功能验证

    最初为设计编写的RTL 模块和其综合后的门级模块可以用同一个测试激励模块进行测试。比较它们的输出结果,找出其中的不一致。对数值比较器而言,所示的程序模块是验证其功 能是否正确的一个简单测试激励文件。
    在这里插入图片描述的输出结果的不同之处。还有另一件事需要考虑:门级描述是基于VAND, VNAND 等库单元的,Verilog 仿真器不能理解这些单元的意义。因此为了仿真门级描述, ABC 公司必须提供一个仿真库, abc_100.v。仿真库必须用Verilog HDL 原语 and和nand等描述 VAND 和VNAND 等。(UDP中的specify)

    比较 RTL 和门级网表的仿真输出只是功能验证过程的一部分。有许多种技术可用以来确保逻辑综合生成的门级网表在功能上正确无误。一种技术是以 C++编写高层次结构描述 , 将执行这个高层次结构描述后获得的输出与RTL 或者门级描述的仿真输出相比较。另一种称为等价性检查 。

    时序验证也是验证的重要方面。

    逻辑综合建模技巧

    在这里插入图片描述
    不一定对称。
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    在这里插入图片描述要学会用状态机分析

    展开全文
  • 逻辑优化、逻辑验证、逻辑综合所需的ISCAS测试基准电路
  • 进而提出了基于全加器以及CRM型PLA网络的逻辑综合,还举例说明了逻辑综合过程.该综合的PLA网络是以或、符合二种运算作为基本运算的,类似于与、异或的电路实现,CRM型对称函数常常可以导致使用较少的门及较少的连线...
  • 工具: Synopsys Design Compiler(DC) Cadence Genus Synthesis Input文件: 1,RTL文件.v 2,SDC约束文件 3,library ***.db(逻辑综合需要基于特定的综合库,不同的库中,门电路基本标准单元(standard cell)的...
  • 同济大学计算机系数字逻辑课程综合实验报告学 号 1651390 姓 名 刘思源 专 业 信息安全 授课老师 郭玉臣 目录 一、 实验内容 3 二、 温湿度检
  • 逻辑综合重点解析(Design Compiler篇)

    万次阅读 多人点赞 2019-02-02 17:54:54
    逻辑综合重点解析(Design Compiler篇) 前言 3 1、逻辑综合(Logic Synthesis)分为哪三个步骤? 4 2、当你拿到一个ddc格式的文件,你是否能够知道这是一个已经综合过的设计? 4 3、使用Design Compiler进行...
  • 数字逻辑综合工具-DC-06 ——综合优化过程 编译的策略:Top-down (做设计有两种策略:top-down 和 bottom-up) 设计一定是一种层次化的结构,一层一层地去例化 Top-down只有一层的约束,针对某些模块,可能会有一些...
  • 1.1 登录方法 1.2 进入实验目录 2.1 设置软件环境 2.2 进入逻辑综合运行目录 2.3 定义时序约束 2.4 使用命令输入运行逻辑综合 2.4.1
  • DC逻辑综合-概述

    2020-07-06 14:44:16
    逻辑综合-概述 逻辑综合 Synopsys Design Compiler 综合工具 verilog code --> 可生产门级电路 电路逻辑优化 面积,功耗...... 时序分析及优化 DFT(Design For Test) 转化两保证:功能正确,时序满足要求...
  • 1. ASM 流程图: 2. 状态转移真值表: 3. 次态函数表达式: 4. 控制命令逻辑表达式: 1. 时钟分频模块(CLK_DIV)
  • 数字IC设计学习笔记(一)——逻辑综合简介

    千次阅读 多人点赞 2019-05-21 10:50:17
     逻辑综合的重要意义:逻辑综合是由各种约束条件驱动的,这些约束条件包括工作环境、时间、面积、功耗等等。综合的最终目标是产生满足这些约束条件的结果。其中 最重要的是时间约束 ,通常把满足时间约束称为 时序...
  • 在逆向逻辑综合过程中,为了保证综合结果的准确性,需要将输入全集作为待处理数据集合,大大增加了整个处理过程的时空开销.论文深入分析了现有的逻辑综合基本运算,并结合逆向逻辑综合的数据特点,提出了效能更优的...
  • 逻辑综合(Synthesis)概述

    千次阅读 2020-04-24 16:47:54
    概念: 逻辑综合是IC前端设计的重要步骤,就是将行为级/RTL级的电路转换为门级网表的过程。 目的:决定电路的门级结构。寻求电路时序和面积的平衡, 功耗和时序的平衡,增强电路的测试性。 逻辑综合三阶段:...
  • 分析了量子电路可逆逻辑综合的意义、研究现状和研究进展,给出了相关的研究方法和目前量 子可逆逻辑综合研究中存在的主要问题,提出了量子可逆逻辑综合中的最小量子代价、最小化垃圾 信息位、最小化门的数量和可逆逻辑...
  • DesignCompiler学习(1)- 逻辑综合简介

    千次阅读 2020-10-18 16:33:05
    DC逻辑综合详解DC软件简介逻辑综合DC命令 DC软件简介 DC( Design Compiler )为Synopsys公司逻辑合成工具。DC得到全球60多个半导体厂商、380多个工艺库的支持。据最新Dataquest的统计,Synopsys的逻辑综合工具占据91%...
  • 逻辑综合——施加约束

    千次阅读 2020-12-23 21:55:52
    Design Compiler时一个约束驱动(constraint-driven)的综合工具,它的结果与设计者施加的约束条件密切相关。
  • 实验02-逻辑综合与等价性检查思考题1
  • 数字电路后端设计逻辑综合.ppt
  • 数字集成电路原理与设计:L8 逻辑综合.pdf
  • 2016年逻辑综合真题答案.doc

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 235,784
精华内容 94,313
关键字:

逻辑综合

友情链接: torpedo.rar