基于变步长随机行走算法的IC电源网络动态分析

汤战勇, 郝 杰, 郭 军, 刘宝英

(西北大学 信息科学与技术学院, 西安 710127)

随着集成电路(IC)规模的扩大, 芯片设计精度也越来越高, 使电路中晶体管数目及所对应的电路方程规模不断增加. 传统LU分解法求解大规模模拟电路的时间较长, 因此很难高效满足现代芯片的发展需求. 为设计更稳定有效的集成电路, 文献[1]提出了相应的解决算法, 即模型缩减法、 时域频域变换法和近似算法. 其中模型缩减法和时域频域变换法面对大规模电路求解, 其分析矩阵的运算量较大, 且计算时间较长. 近似算法是指用近似的方法解决优化问题的算法, 其在可证明的解决方法和运行时间范围内能得到保证质量的解. 文献[2]研究了随机行走方法在电路网络分析中的应用. 随机行走算法对无穷大或相对无穷大解空间问题能求得符合要求的近似解, 在许多领域应用广泛[3-6]. 为满足大规模电路设计需求, 文献[7]采用随机行走算法对不同规模及特点的电源电路进行分析, 并研究了其在电源网络上的加速技术及改进措施.

传统随机行走算法加速技术具有局限性, 即在电路电压幅值变化较小的情形下不能有效缩短运行时间. 针对此问题, 本文在满足精度要求的前提下提出变步长加速策略, 其基本原理是在信息重用加速策略的基础上, 根据动态检测出的电路电压幅值大小灵活地改变时间步长, 从而有效缩短运行时间.

1 随机行走算法

图1 随机行走问题示意图

对解决空间无穷大或接近无穷大的问题, 随机行走是一种有效的方法[8]. 图1为随机行走问题描述模型, 其中x点为一位醉酒行走者的起始点, home节点可被认为是旅店或其家, 其他交叉点则表示岔道路口, 交点间的线段可被认为是街道. 行走者要从x点回到home点, 则有3条路可选择, 但由于其醉酒, 他会随机挑选一条路走, 则走这3条路的概率分别可设为Px,1,Px,2,Px,3. 从3条路中他任选一条路都会先到达一个岔道路口, 而过该路口所交费用为mx, 继续走至home节点时获得奖励并停止此次行走. 此时, 其最终所获奖励值或行走多次后的平均奖励值为醉汉从x节点出发到home点奖励的期望值, 用公式表示为

(1)

其中:E(x)表示期望奖励值；Px,i为醉汉从x节点出发去第i个相邻道路的概率值；mx为通过岔道路口的路费. 醉汉从x点去各相邻道路的总概率表达式为

(2)

解决随机行走问题的基本理论是大数定律, 即当某实验重复发生次数达到足够数量时, 事件A发生次数与总实验次数之比会接近于其真实概率值. 在理想状态下, 实验次数越多, 最终观测事件的发生概率会越接近真实值. 例如： 在掷骰子实验中, 所抛骰子次数足够多时, 任意一面向上出现的概率会接近其真实值1/6. 因此, 可在大数定律的基础上根据中心极限定理进行求解. 中心极限定理是指在全部样本中随机抽取一定容量n的部分样本, 当容量达到一定规模时, 其样本分布与高斯正态概率密度分布趋于相似, 即实验次数越多, 实验值与真实值相近的概率越高. 假设满足正态分布随机抽样实验结果为X1,X2,…,Xn, 可求得样本均值为

(3)

样本方差为

(4)

最少实验次数为

(5)

式(5)是根据文献[9-10]得到的随机行走的结束判断式. 设在误差允许范围内,M为最少实验次数, 允许误差为Δ, 绝对误差区间为[-Δ,+Δ], 置信概率为P, 置信概率所得系数为β. 在该次数下得到的实验统计平均值可表示为实验期望值μ的近似值.

2 随机行走算法在电路分析中的应用

图2为典型的IC芯片电源网络等效电路模型, 实际上是一个电阻-电容(RC)电路网络, 为避免问题过于复杂, 该电路图仅含有电阻、 电容和电源, 其中任意一个电路节点结构示意图如图3所示.

图2 RC电路网络

由Kirchhoff电流电压定律和欧姆定律可得：

简化式(6)可得节点x的电压表达式为

(7)

其中：Vi为相邻节点电压;gi为电导参数； degree(x)为电路节点x的度. 对比式(1)与式(7)可见, 公式结构相似, 即对电路节点分析与经典随机行走算法分析一致, 因此可推得节点x到其相邻节点i的概率值表达式为

(8)

相对应的路费表达式为

(9)

由上述结论可将电路节点类比为随机行走算法分析中的岔道路口, 电路元件与道路相对应, 电压源和接地节点都与home节点相对应, 电路节点x到其相邻节点i概率分析与每条道路概率分析相同, 电网节点的路费求解与每个岔道路口所交费用相同. 对于含电容电路的瞬态分析, 可利用Norton等效方法处理电容等动态元件, 即令电容C等效成电导为C/Δt的电压源, Δt是时间步长, 被等效的电压源电压V是上一时刻相邻节点的电压值. 在电路分析领域, 由于随机行走算法在电源网络分析上的等价性, 可进一步扩展应用到RC动态分析上, 因而简化的电阻电源网络既能按照随机行走算法进行分析, 也能对一般的电容电阻网络进行瞬态分析, 即可将一个RC电路网络表示成一个一般的电阻电源网络, 并利用随机行走算法进行分析.

3 改进的随机行走算法

3.1 随机行走算法在电路网络中的加速分析

图4 某步长随机行走结果

随机行走算法在分析动态电路网络时, 可采用信息重用的策略加速算法. 首先, 假设在某一时刻, 从节点Ns,0出发, 进行M次随机行走实验, 结果分析如图4所示, 其中: 节点Ns,0,Ns,1,Ns,2,…,Ns,k是随机行走过程访问的节点; 访问次数为V1,V2,…,Vk;Ws,k为Ns,k节点路费. 此时从节点Ns,0出发所获总报酬平均值表达式为

(10)

由于行走经过各路径概率和电路拓扑结构不变, 因而下个时间步从节点Ns,0出发, 仍会访问相同的节点, 且次数Vi保持不变. 因此, 只需将新的参数Ws,i代入便可求出下个时间步长下节点的电压值. 可见, 从任一节点出发, 只需在第一个时间步长上进行M次随机行走实验, 并记录下必要的行走信息, 后续工作便不用再进行实际行走, 只需更新数据, 从而节省了大量时间. 该加速策略记录行走信息虽会占用内存空间, 但达到了用空间换时间的目的.

针对稳态RC电路采用随机行走算法, 若要关注所有电路节点的电压, 获得更高的电压测算精确度, 则需随机行走次数M足够大. 对规模越大的电源电路, 算法的耗时越多, 随机行走算法可通过并行行走减少运算时间. 对随机行走, 由于其具有先天可并行性, 所以从每个节点出发行走的实验可并行运行.

区别于传统并行方法, 文献[11-12]采用了一种伪并行方法. 假设某次随机行走轨迹如图5所示. 对于节点Ns, 从出发开始, 依次通过节点N1,N2,…,Nm-1, 至home节点结束, 最终完成一次从节点Ns出发的行走实验, 所获总报酬为rews. 此时, 在该随机行走过程中实际也完成了一次以节点N1出发的行走实验, 如图6所示.

图5 从Ns出发的随机行走轨迹

图6 从N1出发的随机行走轨迹

由图6可见, 从N1出发的总报酬为rews-fs(fs为图5中经过节点Ns的路费). 对于图6中从Ns出发轨迹上的其他节点情形相同, 因此可推得行走轨迹上的节点都并行完成了一次行走实验. 区别于一般意义的真并行, 这种并行行走称为伪并行. 此外, 结合行走重用技术, 记录所有非home节点的随机行走结果, 所需总时间为

Tr=tr+2tr+…+mtr,

(11)

其中tr为记录数据的平均时间. 按相同轨迹完成随机行走实验, 所需时间为

Ts=ts+2ts+…+mts,

(12)

其中ts是每行走一步所用的平均时间, 通常随机行走一步的时间多于记录时间, 即ts>tr. 因此, 对于大规模RC电路又节省了一部分时间.

3.2 变步长加速算法

图7 SPICE测试下节点电压变化曲线

本文提出的变步长加速方法是对传统信息重用方法的延伸. 信息重用方法是将瞬态电路各节点到达稳态后的总时长划为若干个步长h, 在记录随机行走结果的基础上, 通过逐步迭代使其达到稳态. 对一般RC电路, 各电路节点电压是变化的. 图7为在真实电路数据的RC电源电路中被SPICE电路模拟器测试的一个节点电压变化曲线. 由图7可见, 在达到稳定点过程中, 节点电压的变化幅度越来越小, 如果按照固定步长h进行动态电路分析, 则需较多的迭代次数, 会消耗较多的计算时间. 因此, 可根据电压变化幅度调整步长大小, 实现变步长随机行走, 在满足精度要求的前提下, 减少迭代次数, 从而缩短运行时间.

变步长策略为： 基于上述电源电路加速分析可获得任意一个节点在随机行走过程中的总报酬平均值, 其下一步的总报酬平均值可采用变步长信息重用技术求得. 按预先设定的精度要求设置阈值区间检测电压的幅值变化, 用当前时刻的总报酬值减去该节点上一时刻的总报酬值为X, 如果设阈值区间为Y, 则与信息复用的关系如下：

1) 若X>Y, 则继续按当前步长进行信息复用；

2) 若X≤Y, 则采用变换后的步长进行信息复用.

若上一时刻为t=0, 则节点的总报酬值为随机行走过程中得到的总报酬值.

3.3 变步长随机行走算法的时间复杂度

随机行走算法的最差时间复杂度为O(LMN), 其中:L为行走的步数；M为行走次数;N为电路节点数. 传统加速技术第一次是基于随机行走的运算, 其余时间步的电压均采用信息重用技术运算. 采用信息重用技术运算过程中, 假设从任意节点出发访问过的节点有P个, 则需更新的数据有NP个. 设每个节点数据的平均更新时间为γ, 则每个时间步更新数据的时间为NPγ. 因此, 在信息重用过程中, 设有k个时间步, 则总迭代时间为kNPγ. 传统加速技术的总计算时间为t=0时电路随机行走运行时间与该电路的信息复用时间之和. 在考虑给定的误差范围、 置信概率及时间步长后, 上述参数M和k也变为固定值, 而L和P是只与电路拓扑结构相关, 与电路规模大小无关的值, 即它们是有限值. 因而可推得传统随机行走加速算法的执行时间是关于节点数N的一次多项式, 其时间复杂度为O(N).

变步长随机行走加速算法总时间为第一时刻随机行走计算时间(t=0)、 既定步长迭代时间(节点电压幅值变化大的时间段)与加大步长迭代时间(节点电压幅值变化微小的时间段)之和. 上述传统加速算法有k个时间步长, 假设在变步长中有U个原始时间步长, (k-U)/α个加大的时间步长(α是满足精度要求下关于增大步长的系数,α>1), 则变步长信息重用运算时间为

(13)

加速比R为

(14)

在设置的电路电压精度范围内, 随着E的减小或α的增大, 算法的运行效率逐步提高； 其时间复杂度也为O(N), 远优于传统SPICE电路模拟器中LU分解法的时间复杂度O(N3), 虽与传统随机行走加速算法相同, 也是线性增长的, 但变步长加速算法的斜率却远小于传统加速算法的斜率. 随着电路规模的扩大, 节省时间越来越多.

3.4 实验分析

为验证本文提出的加速算法的有效性, 采用规模为256节点的RC电路网络进行精度对比实验, 设α=2, 阈值大小为0.5, 实验结果列于表1. 由表1可见, 当RC电源电路达到稳态时, 利用本文算法进行实验得到的4个节点数据与采用标准SPICE电路模拟器计算所得的实验数据相比, 误差均在预先设置的范围(约0.5)内, 证明了该算法对电源电路电压求解满足精度要求.

表1 精度实验对比

图8 SPICE与变步长数据变化精度比较

图8为将表1中N017节点在其变步长加速算法实验中得到的数据变化曲线与其SPICE电路模拟器下得到的数据变化曲线对比结果. 由图8可见, 该节点电压在达到稳定的动态变化过程中, 两条数据曲线的误差在任何时刻都不超过0.1, 完全满足预先设置的误差范围和精度要求.

图9 基于节点的传统加速与变步长加速时间效率对比

图10 基于阈值的传统加速与变步长加速时间效率对比

4 变步长随机行走算法的运行空间优化

4.1 随机行走算法空间复杂度

对随机行走加速策略进行分析可知, 需在每一时间步各节点数值已知的情形下才能得到目标节点的电压波形图. 因此需对整个电源网络的节点进行随机行走实验, 故算法加速策略的研究都基于整个电源网络进行分析, 程序的运行空间复杂度较大. 因此需尽量在运行期间减少使用存储空间, 实现算法的运行空间优化. 为解决该问题, 本文将基于随机行走算法具有局部特征的前提下对是否需对整个电源网络使用随机行走策略进行分析. 若能在对目标节点进行求解时不存储与目标节点关联性低或无关联性的节点, 使程序在运行前不存储无关节点数据, 在运行期间不记录其路径, 便可达到算法运行空间优化的目的.

4.2 随机行走算法空间局部性特征分析

为描绘节点电压随时间的变化曲线, 结合随机行走问题描述, 需将时间步长调整到节点去往电容的概率与去往电阻的概率大致相同, 否则当去往电阻的概率大于去往电容的概率情形发生时, 节点只会在电源网络中做无休止的随机行走运动. 当去往电阻的概率小于去往电容的概率时, 节点会大概率仅行走到home节点便直接结束. 同理, 对电阻也存在类似问题, 因此设定相同的电阻值. 否则将导致路径太短无法满足对目标节点电压求解的要求, 或者路径太长超过设定行走路径步数限制而不被记录, 都会使节点做无意义的行走, 进而降低效率. 故在电路节点去往相邻电阻和电容的概率值基本相同的条件下, 观察离目标节点远的节点对目标节点值的影响.

图11 RC电路的节点

以如图11所示的RC电路节点为例, 若电路节点Vx通过相邻的电阻去往周围节点的概率与该节点去往电容C3的概率大致相同, 与随机行走问题模型对应后, 则可得节点x到第i个相邻节点的概率为

(15)

由于概率都大致相同, 因此可推得：p=1/i. 结合图4, 若在此随机行走路径上各节点相邻节点数均为i个, 且该路径不存在重复的节点, 则节点V0沿该行走路径走到节点V3的概率是(1/i)3, 依次类推, 当行走到节点Vk时, 发生的概率是(1/i)k. 真实电源网络中节点所连接的相邻节点与电容等元件的数量都大于2个, 假设k为最小值2的情形, 则当电路节点V0经过10个节点(不包括路过折返的重复电路节点)到达V10时发生的概率仅为1/1 024. 因此仅在节点所连接的电阻与其他元件最少的情形下, 电路节点V10的每一时间步长下所更新的电压数值对实验中想测算的目标节点V0的电压几乎没有影响, 通过上述分析可知, 节点随机行走的运行轨迹具有局部性特征. 因此对目标节点进行求解时不存储与目标节点关联性低或无关联性的电路节点, 使程序在运行过程中空间得到优化可行.

4.3 实 验

随机行走算法在IC电源网络上进行分析具有局部性特征, 因此可通过仅存储与目标节点相关的电源网络部分节点达到运行空间优化的目的. 下面通过对比实验, 并结合实验结果进行分析, 证明结论的合理性和正确性. 为保证实验顺利运行, 实验中设定电路节点间的电阻值基本相同.

图12为电阻电容基本相同且电路节点数为100时的RC电路， 对目标节点为N044进行测算(行走次数为500). 由图12可见, 在时间步长设定合理的情形下, 该电路节点的运行轨迹基本在横坐标为2～8、 纵坐标为3～8的区域内行走. 图13为电阻电容基本相同且电路节点数为10 000的RC电路， 对目标节点为N4949进行测算(行走次数为500). 由图13可见, 在时间步长设定合理的情形下, 该电路节点的运行轨迹基本在横坐标为46～54、 纵坐标为46～54的区域内行走.

图12 电阻电容基本相同且电路节点数为100时的等效电路

图13 电阻电容基本相同且电路节点数为10 000的等效电路

图14为电阻大于电容且电路节点数为10 000的电源电路， 对目标节点为N4949进行测算(行走次数为500). 由图14可见, 在时间步长设定不变的情形下, 利用随机行走算法得到电路节点的运行轨迹略扩大了其在电路网络中的行走范围, 该电路节点的运行范围在横坐标为43～58、 纵坐标43～57的区域内行走. 图15为电容大于电阻且电路节点数为10 000的电源电路， 对目标节点为N4949进行测算(行走次数为500). 由图15可见, 在时间步长设定不变的情形下, 利用随机行走算法得到电路节点的运行轨迹略小于其在电路网络中的行走范围, 该电路节点的运行范围在横坐标为47～53、 纵坐标为48～52的区域内行走.

图14 电阻大于电容且电路节点数为10 000的电源电路

图15 电容大于电阻且电路节点数为10 000的电源电路

通过上述实验结果对比分析可知, 在仅对单个目标节点进行测算的情形下, 电源网络规模的增大和电路节点数目的增多， 并未使测算电路节点的运行轨迹发生明显改变. 因此, 电路规模的大小对目标电路节点的运行轨迹所在区域无影响, 而影响目标节点运行轨迹的因素是电路的拓扑结构. 所以, 在保证电路拓扑结构不变的情形下， 对确定目标节点进行测算可通过减少读入与目标节点无关的电源网络节点数据达到优化随机行走算法运行空间的目的.

综上所述, 本文在分析随机行走算法的基础上, 提出了一种变步长随机行走加速算法, 使随机行走的效率和性能都有了较大提高. 在算法时间效率提升的前提下, 证明了随机行走算法具有空间局部性特征, 在此基础上提出了运行空间优化策略, 使随机行走算法运行空间得到释放.