Student: Shangkun LI Student ID: 20307130125 Department of Physics

Repository: https://github.com/ShangkunLi/Logic_Synthesis_phyLS.git

本Project主要通过调用phyLS逻辑综合框架进行逻辑综合。

• Documentation
  • 目录
  • 1 项目说明
    • 1.1 功能说明
    • 1.2 文件结构
  • 2 代码说明
    • 2.1 Balance算法实现思路
    • 2.2 Rewrite算法实现思路
  • 3 编译及结果
    • 3.1 编译
    • 3.2 结果

本项目利用phyLS提供的逻辑综合工具代码框架，完善其中的balance和rewrite功能。然后利用该工具对10个benchmarks进行逻辑综合，并记录结果。

Logic_Synthesis_phyLS   # 项目文件夹
├── phyLS   # 子项目文件夹（phyLS文件夹）
│   ├── benchmarks  # 测试用例
│   ├── build   # 编译文件夹
│   ├── CMakeLists.txt  # CMake文件，用于生成Makefile
│   ├── docs    # Documentation
│   ├── lib # 依赖的library
│   ├── LICENSE
│   ├── README.md   # 说明文档
│   └── src # 源文件
└── README.md   # 说明文档（本文）

本项目主要基于已有的phyLS架构实现了balance和rewrite的功能。该部分可分为两部分构成：

1. 介绍balance算法的实现思路
2. 介绍rewrite算法的实现思路

在逻辑综合优化中，我们常常使用AIG来表示逻辑电路，从而简化优化流程的目的。所谓AIG，是指And-Invertor Graph， 是由二输入与门和反相器组合成的简单逻辑单元。

1. AND-Balance

   Balance按照拓扑顺序应用，并选择多输入与门的最小延迟树分解。 利用AND-Balance算法时，balancing分两步，covering和tree-balancing。

   其中covering将子集之间没有反相器且没有外部扇出的两输入与门组合在一起形成一个多输入与门：

   

   Tree-balancing将covering得到的多输入与门分解为两输入与门，试图减少AIG的深度：

   

2. SOP-Balance for Small AIG：

   在规模较小的AIG图（输入变量数<10）中，我们可以根据真值表计算出逻辑函数，并将逻辑函数用SOP（Sum of Products）表示出来。随后对SOP表示形式的AIG图应用AND-Balance算法，就可以实现balance。

   如下图所示，我们可以将逻辑电路从4层减少到3层.

   

3. SOP-Balance for Large AIG:

   实际的AIG往往规模很大，这就不能用SOP的方式实现balancing。

   但我们可以通过将整个AIG划分为多个区域，对于每个区域使用SOP-Balance算法的方式实现balancing。这也是本Project中使用的方法。

   本Project中通过foreach_co()函数对每个Node实现遍历，并通过balance_rec()对每个Node的对应的割集进行SOP-Balance。

在phyLS中的算法调用代码请见phyLS/src/core/balance.hpp

Rewrite过程中是指通过执行AIG的重写过程，实现AIG节点数的减少和逻辑层级的减少。

具体过程中，我们首先对每一个割集的子图进行遍历，每一个子图都隶属于某一个NPN等价类，将该子图的等价类记录下来。

如果某一子图可以被同一等价类中的某一个子图替换掉，则将该子图的引用数减1，直到该子图的引用数减为0，将该子图移除。同时，如果有新的子图加入，则需要考虑新加入子图的开销。移除旧子图获得的收益减去新加入子图的开销，就是总的收益。如此对所有子图进行遍历，将保留总收益最大的替换操作即可实现rewrite。

在phyLS中的算法调用代码请见phyLS/src/core/rewrite.hpp

其中关于AIG的子图库的选择有多种，我们在此提供了两种选择，并用Complete AIG Database实现本实验。

示例如图所示。

从远程仓库下载源代码

git clone https://github.com/ShangkunLi/Logic_Synthesis_phyLS.git --recurse-submodules

创建编译目标文件夹

cd phyLS
mkdir build && cd build

进行编译

cmake ..
make

执行程序

./bin/phyLS

对20个benchmarks分别进行测试，分别记录其优化前和进行balancing、rewriting优化后的相关结果。