对基于随机比特序列运算的电路的自动综合算法的研究

Traditional arithmetic circuits operate on numbers encoded with binary radix. An alternative to binary radix encoding is to represent a value by a stream of random bits, where the value is represented by the probability of ones in that stream. With this representation, complex arithmetic operations can be implemented with very simple digital circuits. The representation is also much more fault-tolerant than binary radix encoding. Designing circuits computing on stochastic bit streams offers a promising way to design reliable circuits with emerging unreliable nanoscale devices. However, such circuits are currently designed manually: there are no automatic ways to synthesize them. In this project, we will develop algorithms for synthesizing digital circuits operating on stochastic bit streams. We will target both combinational circuits and sequential circuits. We will explore novel data structures that combine the classic logic optimization techniques with probabilistic computation. These novel data structures will be applied to develop algorithms for synthesizing combinational circuits. We will also analyze sequential circuits operating on stochastic bit streams and study what kind of computation they can perform. We will develop methods to synthesize sequential circuits that compute on stochastic bit streams. Computer-aided design tools will be developed and released to offer designers convenience in designing such circuits.

传统的算数运算电路都是对二进制编码的数据进行计算的。与二进制编码不同的一种数据编码方式是利用一串随机比特序列来表示一个数值。在这种编码方式下，复杂的算数运算可以通过很简单的数字电路来实现。这种编码相比于二进制编码具有很强的容错性。面对未来集成电路中器件的可靠性下降这一问题，设计基于随机编码的电路是一种潜在的解决方法。然而，现有的基于随机编码计算的电路都是人为的设计，尚没有自传动综合这类电路的算法提出。本课题将对这类电路的自动综合算法开展研究，针对组合逻辑电路与时序逻辑电路分别提出综合方法。我们将把传统的逻辑优化技术结合到概率性计算之中，开发出新的数据结构，并依此提出有效的算法来综合最优的基于随机编码计算的组合逻辑电路。同时，本课题将对时序逻辑电路在随机编码下实现的计算进行分析，把握其输入输出间的规律，提出自动综合电路的算法。我们将开发相应的计算机辅助设计软件，为设计者设计这类电路提供便捷。

基于随机比特序列的计算是一种非传统的数字电路计算方式。它用一串随机比特序列来编码一个实数值。利用它设计的电路具有面积小和容错性高的优势。面向这种新的计算模式，需要新的自动综合电路的方法。本项目对此开展了研究，主要分为以下5方面：.1. 如何综合最优的产生目标概率值的组合逻辑电路。基于随机比特序列进行计算的电路的输入是以特定概率取1的随机序列。而这种电路常用的设计是一种基于多路选择器的架构。针对这种设计，我们利用其常数概率值输入随机比特序列并不需要相互独立的特点，提出了一种方法可以综合产生常数概率值随机比特序列的电路。利用该算法综合出的电路相比之前的优化设计可减少高达34%的面积。.2. 如何综合最优的基于随机比特序列进行计算的组合逻辑电路。我们首先提出了一种通用的基于组合逻辑电路的随机计算电路的模型。这一基本的形式可以实现任意的多变量线性函数。在此基础上，提出了如何将任意给定的计算目标映射到这一模型上，并如何综合最优的电路设计。实验表明利用该算法生成的电路面积相比之前的方法得到的结果减少高达70%。.3. 如何综合并行的时序逻辑电路来实现任意目标函数。时序逻辑电路在输入为随机比特的情况下可以建模为一个马尔科夫链。之前的设计方法利用它的稳态分布实现所需的计算。然而，为了使马尔科夫链达到稳态分布，需要时序逻辑电路工作足够多的时钟周期。我们提出了一种方法可以利用马尔科夫链的初始分布来实现目标函数，从而为通过并行来降低计算时间提供了可行性。实验表明利用所提的这种方法可以很好地实现所需的计算并达到加速的目的。.4. 提出了一种通过线性变换来减小基于随机比特计算电路面积的方法。在我们之前的研究中曾提出一种基于Bernstein多项式来综合基于随机比特序列计算的电路的方法。这一方法具有普适性。但是对于某些目标函数，其综合出的电路面积较大。我们提出了采用线性变换来改变目标函数以达到减小电路面积的方法。实验结果表明，在误差相同的情况下，利用这一新的方法得到的电路的面积较之前的方法减小至少30%。.5. 针对二值分类应用，提出了对基于随机比特计算的电路的加速方法。对于二值分类应用，它们往往是将最终的计算结果与一个阈值相比较，根据比较结果的大小来判断是属于哪一类。我们利用这类应用不需要较高精度计算结果的特点，提出了一种加速最终判断的模块。实验表明利用这一模块可以将计算速度提高4.86倍。