一种基于最速下降法与二分法的概率电路仿真方法

摘要

本发明公开了基于最速下降与二分法的概率电路仿真方法，包括如下步骤：(1)确定概率单元与输出信号间的对应关系，同时还要确定两者之间的“梯度”关系；(2)获取针对每一个单独输出信号概率单元组合矩阵；利用二分法调整错误概率达到所需精度要求；(3)整体优化以得到最终结果，令每一个概率单元的取值分别取第二步中每一列的最大值和最小值，得到两组概率组合并分别仿真，找到两组测试中错误概率位于目标值两侧且差值最大的一个输出信号，再次利用二分法优化最终结果，重复上面的步骤直到所有的输出的错误概率值达到了所需的精度。本方法的优势在于调整概率值时能够更精准的选择需调整的概率单元，更准确的调整其错误概率取值，获得更多的能量节省。

说明书

技术领域

本发明涉及基于概率电路仿真技术，涉及快速调整概率单元的概率取值，具体涉及一种基于最速下降法与二分法的概率电路仿真方法。

背景技术

随着IC产业的发展，芯片处理速度快速提高的同时，能耗也随之不断增大，而随着互补金属氧化物半导体CMOS器件尺寸进入纳米时代，各类内部干扰因素对CMOS器件电学特性的影响也愈发明显。同时，随着各类电子产品的加速普及，人们在期望获得更高硬件性能的同时，也希望能够降低设备功耗。针对上述问题，研究者们提出了PCMOS(Probabilistic complementary metal-oxide semiconductor)概率器件的概念，即输出并非确定，而是存在概率性错误的CMOS器件。而为了将PCMOS概率电路应用于实际系统中，就要解决如何对其进行仿真建模的问题。基于现场可编程门阵列FPGA的硬件仿真方法具有仿真速度快，仿真过程高度可控等优势，是一种极佳的仿真方式。

三步矩阵构建法可以应用于概率电路仿真过程中概率模块的错误调整，且算法思路较简单，很容易实现。但该算法最大的问题在于，其调整过程太过繁琐，且缺乏一定的规律性，当待测电路较为复杂时，应用这种方法就需要非常多次的尝试调整与仿真，因而应对大规模电路，该过程需要耗费大量的时间，严重影响了其应用范围。最速下降和二分法则分别能够很好的解决。

三步矩阵构建法的调整过程需要面对两个问题：一是多个概率单元都对目标输出有影响时，如何确定优先修改哪些；而是确定要修改的概率单元后，如何有效调整其概率值以最快接近目标输出。最速下降法和二分法则分别能够很好的解决这两个问题。

二分法与最速下降法组合的核心思想在于，在验证概率单元与各输出是否有关的同时，计算其概率梯度，即输出错误概率差与输出概率差之比，再依据概率梯度针对每一输出信号进行调整，更快的得到概率矩阵，最后利用概率梯度针对整体输出进行概率调整，以得到最终结果。利用概率梯度这一概念寻找当前对输出影响最大概率单元，利用二分法对其错误概率进行调整，从而更精准的调整错误概率，使得优化结果更快的收敛。

发明内容

本发明的目的是提供一种基于最速下降法与二分法的概率电路仿真方法，在此情况下可以更快更精准的调整错误概率，在一定程度上解决了因缺乏规律性而导致调整与仿真耗时大的问题。

为了实现上述目的，本发明的技术方案为：

一种基于最速下降法与二分法的概率电路仿真方法，其特征在于包括如下步骤：

(1)确定概率单元与输出信号两者之间的“梯度”关系；每个概率单元错误概率依次置为两组不同的值，观察是否出现错误，计算两次错误概率差，即梯度；

(2)利用最速下降法与二分法得到错误概率取值矩阵，依次针对每一输出信号，对概率单元错误概率随机撒点，获取距离目标值两侧最近的两组概率；找到两组概率值中概率差与梯度乘积最大的概率单元，将最大的概率单元错误概率设为两组中对应概率中间值，再次仿真，三组值中找到距离目标值两侧最近的两组概率；重复步骤(2)直至输出错误概率达到所需的概率精度要求；

(3)令每一个概率单元的取值分别取步骤(2)中每一列的最大值和最小值，得到两组概率组合分别仿真；找到两组测试中错误概率位于目标值两侧且差值最大的一个输出信号；找到与该输出有关的概率单元中，概率差与梯度乘积最大的概率单元，将其错误概率设为两组中对应概率中间值，再次仿真，三组值中找到距离目标值两侧最近的两组概率，重复以上步骤(3)直至输出错误概率达到所需的概率精度要求。

所述步骤(1)中，确定概率单元与输出信号两者之间的“梯度”关系，其中梯度G_mn为

$G_{mn}=\frac{{\mathrm{po}}_{mn2}-{\mathrm{po}}_{mn1}}{{\mathrm{pe}}_{mn1}-{\mathrm{pe}}_{mn2}}---(1-1)$

其中，m和n分别表示为有m个输出信号和n个概率单元；pe_mn1和pe_mn2为每个概率单元分别设置的两个不同的错误概率值，仿真之后，po_mn1为受pe_mn1影响的输出信号的错误概率，po_mn2为受pe_mn2影响的输出信号的错误概率。

所述步骤(1)中，根据计算G_mn的方法，测试完所有的概率单元之后，就得到概率“梯度”矩阵G：

其中，矩阵G中每一行对应一个输出信号，每一列对应一个概率单元，矩阵中的值表示输出信号在该概率单元维度上的“梯度”，即错误概率下降梯度。

所述步骤(2)具体为：

(21)对电路中某一个输出信号k，从得到的矩阵中获取与输出信号k相关的概率单元，对该概率单元的错误概率取值进行随机撒点，即随机产生若干种概率组合，仿真测试之后，获得相应的输出错误概率；

(22)从其中大于预设输出错误概率的组合中，选取最小的一组记为P_A(p_k1a，p_k2a…p_kna)，从小于预设值的组合中选取最大的一组记为P_B(p_k1b，p_k2b…p_knb)；

(23)根据步骤(1)中得到的梯度关系，找到两组概率组合中概率差值与对应梯度的乘积绝对值最大的一个概率单元的编号x，对应的计算式为以下式(1-3)；

$\begin{array}{c}\max (G_{kx}*|p_{kxb}-p_{kxa}\left|\right)\\ =\max \{G_{k1}*\left|p_{k1b}-p_{k1a}\right|,G_{k2}*\left|p_{k2b}-p_{k2a}\right|,\mathrm{...}{G}_{kn}\left|p_{knk}-p_{kna}\right|\}\end{array}---(1-3)$

(24)根据式(1-3)得到的编号x，令编号x的错误概率取值为P_A和P_B中对应取 值的中间值，即利用二分法调整为式(1-4)；

$p_{kxc}=\frac{p_{kxa}+p_{kxb}}{2}---(1-4)$

(25)完成对概率取值的一次修改，修改后的两组概率组合分别为P_A’(p_k1a，p_k2a…p_kxc…p_kna)和P_B’(p_k1b，p_k2b…p_kxc…p_knb)；

(26)在分别计算P_A，P_B，P_A’,P_B’四种概率组合中，输出错误概率分别从正负两个方向最接近预设值的两组，重复步骤(22)－(25)直到获得的错误概率达到所需的概率精度要求；

(27)再针对下一输出信号，重复步骤(22)－(26)，直到所有的输出信号全部处理完毕，这样也就得到了错误概率取值矩阵E:

其中，每一行对应一个输出信号，每一列对应一个概率单元。

所述步骤(3)中，具体步骤为：

(31)令每一个概率单元的取值分别取步骤(2)中得到的错误概率取值矩阵E式(1-5)当中每一列的最大值和最小值，得到两组概率组合，分别记作P_MAX和P_MIN

$\begin{array}{c}{P}_{MAX}=\{p_{MAX1},p_{MAX2}\mathrm{...}{p}_{MAXn}\}\\ =\{\max (p_{11},p_{21}\mathrm{...}{p}_{m1}),\max (p_{12},p_{22}\mathrm{...}{p}_{m2})\mathrm{...}\max (p_{1n},p_{2n}\mathrm{...}{p}_{mn})\}\end{array}---(1-6),$

$\begin{array}{c}{P}_{MIN}=\{p_{MIN1},p_{MIN2}\mathrm{...}{p}_{MINn}\}\\ =\{\min (p_{11},p_{21}\mathrm{...}{p}_{m1}),\min (p_{12},p_{22}\mathrm{...}{p}_{m2})\mathrm{...}\min (p_{1n},p_{2n}\mathrm{...}{p}_{mn})\}\end{array}---(1-7);$

(32)将P_MAX和P_MIN代入式(1-8)中，得到Y_MAX＝{Y_MAX1,Y_MAX2…Y_MAXm}和Y_MIN＝{Y_MIN1,Y_MIN2…Y_MINm}

其中为系统转移矩阵；

(33)找到后一种情况中两个错误概率值差值最大的一个输出信号，再针对该输出信号利用式(1-3)的方法，找到对应概率差值与梯度乘积最大的一个概率单元，再利用式(1-4)将其概率值设为两组概率组合中对应概率值的中间值，再次进行仿真测试。

本发明利用概率梯度这一概念寻找当前对输出影响最大概率单元，利用二分法对其错误概率进行调整，从而更精准的调整错误概率，使得优化结果更快的收敛。相比原来的三步矩阵的方式复杂度要降低，耗费的时间与仿真次数也要降低。针对每一个输出，能够较为准确的找到与之相关的概率单元，同时也能够快速的调整概率单元的取值以达到所需概率输出精度，提高了仿真效率。

附图说明

图1为本发明基于最速下降法与二分法的概率电路大致仿真方法流程图。

图2为本发明基于最速下降法与二分法的概率电路详细仿真方法流程图。

具体实施方式

通过以下的描述并结合附图，本发明将变得更加清晰，附图用于解释本发明的实施例。

本发明最速下降与二分法是基于FPGA的概率电路仿真方法，在输出概率允许在某一范围内，通过调整概率单元的概率取值达到最节能的状态。使用最速下降与二分法提高仿真的效率，减小仿真次数。

如图1所示，本发明的包括步骤如下：(1)确定概率单元与输出信号两者之间的“梯度”关系；每个概率单元错误概率依次置为两组不同的值，观察是否出现错误，计算两次错误概率差，即梯度；

(2)利用最速下降法与二分法得到错误概率取值矩阵，依次针对每一输出信号，对概率单元错误概率随机撒点，获取距离目标值两侧最近的两组概率；找到两组概率值中概率差与梯度乘积最大的概率单元，将最大的概率单元错误概率设为两组中对应概率中间值，再次仿真，三组值中找到距离目标值两侧最近的两组概率；重复步骤(2)直至输出错误概率达到所需的概率精度要求；

(3)令每一个概率单元的取值分别取步骤(2)中每一列的最大值和最小值，得到两组概率组合分别仿真；找到两组测试中错误概率位于目标值两侧且差值最大的一个输出信号；找到与该输出有关的概率单元中，概率差与梯度乘积最大的概率单元，将其错误概率设为两组中对应概率中间值，再次仿真，三组值中找到距离目标值两侧最近的两组概率，重复以上步骤(3)直至输出错误概率达到所需的概率精度要求。

如图2所示，本发明具体步骤如下：

步骤S1，确定概率单元与输出信号间的对应关系以及“梯度”关系，对每一个概率单元分别设置不同的错误概率，记作pe_mn1和pe_mn2，分别仿真一段时间，记录受其影响的输出信号两次不同的错误概率，分别记作po_mn1和po_mn2。其中n表示概率单元的编号，m表示输出信号的编号，这样就可以计算出梯度G_mn；

$G_{mn}=\frac{{\mathrm{po}}_{mn2}-{\mathrm{po}}_{mn1}}{{\mathrm{pe}}_{mn1}-{\mathrm{pe}}_{mn2}}---(1-1)$

步骤S2，重复步骤S1直到所有的概率单元都测试完毕，记下所有的差值就可以得到概率梯度矩阵G

步骤S2所得到的矩阵每一行对应一个输出信号，每一列对应一个概率单元，矩阵中的值表示输出信号在该概率单元维度上的“梯度”，即错误概率下降速度，这样每一行中的最大值所对应的概率单元就是该输出错误概率下降最快的维度。

步骤S3，利用最速下降与二分法得到概率矩阵，针对电路中的某一个输出信号，如输出k，从第一步得到的矩阵中获取与之相关的概率单元，对其错误概率取值进行随机撒点，即随机产生若干种概率组合，仿真测试若干个时钟周期，获得相应的输出错误概率

步骤S4，在步骤S3得到的组合中选取大于输出错误概率最小的一组记为P_A(p_k1a，p_k2a…p_kna)，从小于预设值的组合中选取最大的一组记为P_B(p_k1b，p_k2b…p_knb)。再根据第一步中得到的梯度关系，找到两组概率组合中概率差值与其梯度的乘积绝对值最大的一个概率单元的编号x。

$\begin{array}{c}\max (G_{kx}*|p_{kxb}-p_{kxa}\left|\right)\\ =\max \{G_{k1}*\left|p_{k1b}-p_{k1a}\right|,G_{k2}*\left|p_{k2b}-p_{k2a}\right|,\mathrm{...}{G}_{kn}\left|p_{knk}-p_{kna}\right|\}\end{array}---(1-3)$

步骤S5，根据步骤S4得到的编号，令其错误概率取值为P_A和P_B中对应取值的中间值，即利用二分法调整；

$p_{kxc}=\frac{p_{kxa}+p_{kxb}}{2}---(1-4)$

这样就完成了对概率取值的一次修改，修改后的两组概率组合分别为P_A’(p_k1a，p_k2a…p_kxc…p_kna)和P_B’(p_k1b，p_k2b…p_kxc…p_knb)。在分别计算P_A，P_B，P_A’，P_B’四种概率组合中，输出错误概率分别从正负两个方向最接近预设值的两组

步骤S6，针对下一输出信号重复上面的步骤S3-S5，直到所有的输出信号全部处理完毕，这样也就得到了错误概率取值矩阵E；

步骤S7，利用最速下降与二分法优化得到结果，令每一个概率单元的取值分别取第二步中每一列的最大值和最小值，得到两组概率组合，分别记作P_MAX和P_MIN；

$\begin{array}{c}{P}_{MAX}=\{p_{MAX1},p_{MAX2}\mathrm{...}{p}_{MAXn}\}\\ =\{\max (p_{11},p_{21}\mathrm{...}{p}_{m1}),\max (p_{12},p_{22}\mathrm{...}{p}_{m2})\mathrm{...}\max (p_{1n},p_{2n}\mathrm{...}{p}_{mn})\}\end{array}---(1-6)$

$\begin{array}{c}{P}_{MIN}=\{p_{MIN1},p_{MIN2}\mathrm{...}{p}_{MINn}\}\\ =\{\min (p_{11},p_{21}\mathrm{...}{p}_{m1}),\min (p_{12},p_{22}\mathrm{...}{p}_{m2})\mathrm{...}\min (p_{1n},p_{2n}\mathrm{...}{p}_{mn})\}\end{array}---(1-7)$

步骤S8，P_MAX和P_MIN两组概率值分别进行仿真测试，获取其输出概率，即将P_MAX和P_MIN代入下式；

经过上式的计算可以得到Y_MAX＝{Y_MAX1,Y_MAX2…Y_MAXm}和Y_MIN＝{Y_MIN1,Y_MIN2…Y_MINm}

步骤S9，找到两个错误概率差值最大的一个输出信号，根据步骤S4的方法找到对应概率差值与梯度乘积的最大的一个概率单元，再利用步骤S5用到的二分法将其概率值设为两组概率组合中对应概率值的中间值，再次进行仿真测试；

重复步骤S7-S9，直到所有输出的错误概率值都达到了所需的精度；结束。

以上结合了流程图对本发明进行了较为详细的描述。二分速降法最大的优势在于调整概率值能够更精准的选择需调整的概率单元，更准确的调整其错误概率取值，避免了随机调整时因缺少方向性而造成的无效仿真问题。以及因缺少规律性而造成的改善过小的问题，从而可大大减少需进行的仿真次数，提高仿真速度，进而扩大了利用FPGA对PCMOS电路进行仿真的应用范围。