Approximate Logic Synthesis Using Boolean Matrix Factorization
Approximate Logic Synthesis Using Boolean Matrix Factorization
复制标题
基于布尔矩阵分解的近似逻辑综合
DOI：
10.1109/tcad.2021.3054603
复制
发表时间：
2021-01
影响因子：
2.9
通讯作者：
Jingxiao Ma;S. Hashemi;S. Reda
中科院分区：
文献类型：
--
作者：
Jingxiao Ma;S. Hashemi;S. Reda
近似计算是一种新兴的计算范例，通过放宽对完全精度的要求，在硬件指标（例如设计面积和功耗）方面提供优势。在电路设计中，一个主要挑战是从输入精确电路自动合成近似电路，需要最少的专家输入。在这项工作中，我们提出了一种基于布尔矩阵分解的近似逻辑综合方法，其中可以以受控方式近似任意输入电路。我们的方法能够自动计算电路真值表的主要元素、基数，然后组合这些基数以近似原始真值表。这种压缩可以显着降低硬件实现的复杂性，同时引入不同程度的不准确性。此外，在我们的方法中，分解算法可以根据应用的需要进行微调，以有效地提高对逼近程度的控制。在这项工作中，我们提供了一种统一的方法，使分解算法能够利用半环代数、域代数以及两者的组合进行真值表分解。此外，我们还提供自动电路分区方法和设计空间探索启发式来导航搜索空间。我们使用全套开源工具来实现我们的方法，并在许多代表性电路上彻底评估我们的方法，展示我们提出的近似逻辑综合方法的好处。最后，我们将我们的方法与现有的近似设计库进行比较，并展示最先进的性能。
Approximate computing is an emerging computing paradigm offering benefits in hardware metrics, such as design area and power consumption, by relaxing the requirement for full accuracy. In circuit design, a major challenge is to synthesize approximate circuits automatically from input exact circuits requiring minimal expert input. In this work, we present a method for approximate logic synthesis based on the Boolean matrix factorization, where an arbitrary input circuit can be approximated in a controlled fashion. Our methodology enables automatic computation of the dominant elements, bases, of the truth table of the circuit, and later combines the bases to approximate the original truth table. Such compression can reduce the complexity of the hardware implementation significantly, while introducing variable degrees of inaccuracy. Furthermore, in our approach, the factorization algorithm can be fine tuned as required by the application, to effectively improve control over degree of approximation. In this work, we provide a unified approach enabling the factorization algorithm to utilize semiring algebra, field algebra, and a combination of both for truth table factorization. In addition, we provide an automatic circuit partitioning approach and a design space exploration heuristic to navigate the search space. We implement our methodology using a full stack of open-source tools, and thoroughly evaluate our methodology on a number of representative circuits showcasing the benefits of our proposed methodology for approximate logic synthesis. Finally, we compare our methodology against an existing library of approximate designs and demonstrate state-of-the-art performance.