当前位置:首页 >> >>

用神经网络求解时延、功耗和连线三重驱动的布局问题


 第 20 卷第 9 期  1999 年 9 月

半 导 体 学 报
CH I ESE JOU RNAL O F SEM ICONDU CTO R S N

. V o l 20,N o. 9 Sep. , 1999

( 北京大学计算机科学技术研究所 北京 100871)   ( 杭州电子工业学院 CAD 所 杭州 310037)

摘要 本文应用 Kohonen 自组织神经网络求解时延、 功耗和连线三重驱动的门阵列布局问题. 算法用自组织学习算法和分配算法确定关键单元的位置, 用迭代改善的方法确定非关键单元的 位置, 从而获得关键线网最短、 散热大的单元离得尽可能远并且单元连线总长尽可能短的布局. 本文还介绍了面向线网和功耗的样本矢量的概念, 与面向单元的样本矢量相比, 面向线网和功 耗的样本矢量不仅可以直接处理多端线网, 而且能够描述时延信息和热信息. 实验表明这是一 种有效的方法.

CCACC: 7410D , 5120

1 引言

随着集成电路工艺的迅猛发展, 人们对集成电路的性能要求日益提高, 研究人工神经网 络在性能驱动的集成电路布局中的应用, 是一个有现实意义的研究课题. 时延、 功耗和连线是性能驱动的集成电路布局中应该考虑的问题 本文应用 Kohonen 自 . 组织神经网络求解时延、 功耗和单元总连线长度三重驱动的门阵列布局问题 算法分三步: . 第一步: 用自组织学习算法确定关键单元的基本位置. 其中, 关键路径上的线网称为关 键线网, 关键线网所联单元和热源单元称为关键单元, 其它的单元均为非关键单元. 第二步: 用分配算法处理关键单元映射的重叠现象. 第三步: 用迭代改善的方法确定非关键单元的位置. 在迭代改善过程中, 以连线总长度 最短为优化目标. 这样就可以在保证关键线网连线最短、 热源单元离得尽可能远的前提下, 使得单元间连线总长尽可能短.

2 神经网络模型

Kohonen 自组织神经网络是由输入层和输出层组成的双层神经网络. 输入层中的每一
 3 本文研究得到国家自然科学基金和国家 “九五” 重点科技攻关项目资助 胡卫明 1968 年出生, 计算机博士、 博士后, 主要从事 IC 2CAD、 人工神经网络和 G IS 的研究工作

1998203203 收到, 1998206225 定稿

严晓浪 1947 年出生, 博士导师, 从事 IC 2CAD 和设计自动化领域的教学与科研

用神经网络求解时延、 功耗和连线 三重驱动的布局问题3
     胡卫明         李翠超 朱育松 严晓浪

798

半 导 体 学 报

20 卷

个神经元, 通过权与输出层的每一个神经元相联 设 X ∈R M 为输入模式向量, W 为权值矩阵, . N T 代表一种运算, 一般有两种 Y ∈R 为输出节点的匹配响应, 在 t 时刻有 Y = W ( t) X ( t ). T 形式: ( 1) 点积运算, 即 Y = W ( t) ?X ( t ) , 输入样本 X 与权的内积最大值为竞争优胜者; ( 2) . Euclidean 距离运算, 即 Y = ‖ ( t) - X ( t) ‖g , 竞争得胜的神经元对应最小的输出值 W 在输出层中, 竞争是这样进行的: 对于 “赢” 的那个神经元 c, 在其周围 N c 的区域内神经 元在不同程度上得到兴奋, 而在 N c 以外的神经元都被抑制, 即: Α( t) ( x i ( t) - w ij ( t) ) Π j ∈ N c dw ij d t = 0 Πj | N c . N c 随着 t 的增大逐渐缩小, Α( t) 随 t 的增大逐渐减小 网络的学习过程就是网络的连接权根据训练样本进行自适应、 自组织的过程, 经过一定 次数的训练以后, 网络能够把拓扑意义下相似的输入样本映射到相近的输出节点上. 网络能 够实现从输入到输出的非线性降维映射.

3 样本矢量的建立

面向单元的样本矢量[ 2, 3 ] ( 文献 [ 2 ] 对间接连接单元的连接度只做一次修正, 文献 [ 3 ] 对 此做了改进, 较好地解决了非直接连接单元的连接度问题) 是以单元间的连接度作为它们之

间相似性量度的, 网络自组织的结果使得连接度大的单元被映射到布局平面上邻近的位置 上 它有三个不足之处: ( 1) 不能直接表达时延信息. ( 2) 不能直接表达热信息 ( 3) 虽能直接 . . 处理两端线网, 但对于多端线网在产生单元连接矩阵时, 需把多端线网等效成适当连接权的

以线网的最大权值, 使得线网的权值小于等于 1. 在许多场合, 关键路径是由用户指定的, 这 时可以直接用用户指定的关键路径上的线网作为特征分量. 芯片中的热来自各晶体管. 对于 CM O S 电路, 门在 “开” 状态和 “关” 状态下产生的热量 是不一样的, 需确定在任一时刻 “开” 状态门的数目和 “关” 状态门的数目的比例 对于 ECL .

系统, 典型的门功耗为 0125mW 每门, 而与门的状态和运行频率无关. 输入样本矢量的热分 量需要除以单元的最大散热量, 使得每个样本的热分量小于等于 1. 图 1 是一个简化的单元连接图, 设线网 n 1、 2、 3 和 n 4 都为关键线网, 单元 b 和 d 为热 n n 源单元, 关键线网 n 4 为三端线网, 则该单元连接图的输入样本如表 1 所示.

两端线网. 这种等效方法具有一定的失真性, 不能完全真实反映多端线网的连接特征. 312 面向线网和功耗的样本矢量 面向线网和功耗的样本矢量将时延信息和热信息描述在样本矢量的特征分量中, 由关 键线网特征分量和热特征分量组成: 以关键线网的加权值作为关键线网特征分量; 用单元的 散热量作为热特征分量 ( 时延和热的处理思想与文献 [ 4 ] 类似). 具有相同特征值的相似单元 经自组织学习以后能够移到一起或因为都是热源单元而移得较远. 显然处理的每一步用的 都是关于电路的完整的、 真实的连接信息, 而不是分解的、 变形的信息, 从而能够直接处理多 端线网. 获取线网权值的一个方法是: 先对电路进行时延分析, 通过时延方程、 组合电路单元的 内部时延和系统周期时间确定线网的权值. 为了网络训练的方便, 还要将关键线网的权值除

311 面向单元的样本矢量

9期

胡卫明等:  用神经网络求解时延、 功耗和连线三重驱动的布局问题

799

表 1 图 1 的样本数据
单 元
a b c d

特 征 量 关键线网 n 1
0. 95 0 0. 95 0

关键线网 n 2
0 1 1 0

关键线网 n 3
0 0 0. 8 0. 8

关键线网 n 4
0. 85 0. 85 0 0. 85

热特征
0 0. 8 0 1

图 1 单元连接图

4 自组织学习算法
对应于一个有 K 个关键单元、 - 1 个关键线网和布局平面上有 N 个单元放置位置 M ( 即输出节点) 的门阵列布局实例, 网络需要 K 个训练样本点、 个输入矢量特征分量 (M M 1 个关键线网分量和一个热分量) 和 N 个输出神经元 其中, 一个关键单元对应一个样本; . 一个单元放置位置对应一个输出神经元. 网络的自组织学习过程为: 步骤 1: 随机给定网络初始权: 0< w ij < 1, i= 1, 2, …, M , j = 1, 2, …, N 步骤 2: 从输入样本数据中随机选取一样本点 X , 计算所有输出节点的输出值:
M

yj =

∑x w
i i= 1 j

ij

, j = 1, 2, …, N

  步骤 3: 选择输出值最大的输出节点 c 为竞争获胜神经元: y c = m ax ( y j ) , j = 1, 2, …, N   步骤 4: 确定神经元 c 的领域 N c. 步骤 5: 更新 N c 内所有输出神经元 j 的权值: w ij = w ij + Α( t) Γcj ( x i - w ij ) , i = 1, 2, …, M - 1, j ∈ N c w M j = w M j + Α( t) Γcj ( x M - w M j ) , i = M , j = c [4] w M j = w M j + Α( t) ( 1 - Γcj ) ( x M - w M j ) , i = M , j ∈ N c , j ≠ c 其中 Α( t) = A e- t Σ ( Σ为常数) 或 Α( t) = 0. 9 ( 1- t 1000)
i = M 为热特征分量

数后, 学习结束; 否则进入下一轮学习. 进一步说明如下: ( 1) 输入矢量与输出神经元的权矢量的相似性用它们的点积值 ( 而非 Euclidean 距离) 表示. ( 2) 热特征分量 ( i= M ) 的学习规则必须特殊考虑, 它的学习方式与其它特征不同 . ( 3) 输出神经元 c 在不同时间 t 时的邻域 N c ( t) 由与神经元 c 间的距离小于等于 k ( t) 的 神经元组成. k ( t) 反映了领域的大小, 是一个时间递减函数. 初始时邻域可以取很大, 随着学 习步数 t 的增大再线性缩小, 直到只剩下一个神经元.

步骤 6: 转步骤 2. , 当所有样本输入一遍后, 满足m ax { w ij ( t + 1) - w ij ( t) }< Ε 或达到预先取定的迭代次 i, j

< Γcj = Χ ( 1< Χ 2) , ( d 为输出神经元 c 和 j 的M anha t tan 距离)
- d

800

半 导 体 学 报

20 卷

长 .

由于样本训练次数一般为 O (K ) 数量级, 每输入一个样本平均有 logN 个输出神经元的 2 权 值 需 要 调 节 , 且 每 个 输 出 神 经 元 有 M 个 权 分 量, 所 以 该 算 法 的 时 间 复 杂 性 为 O ( KM logN ). 另外, 实际样本训练次数还与初始状态有关, 不同的初始状态, 迭代到满足收敛 2 条件, 所需的迭代步数是不完全一样的.

5 分配算法

对于上述的自组织学习过程, 如果学习时间不够长 ( 在电路规模较大的情况下, 要使网 络收到最优解需要很长的学习时间) , 那么多个关键单元会映射到同一个输出点节上, 即有 多个样本在同一输出神经元上有最大输出值, 称之为单元重叠. 单元重叠出现的可能性主要 取决于关键单元在单元集合中所占的比例, 关键单元越多, 越容易出现重叠. 但一般情况下, 关键单元占的比例并不大, 所以重叠现象并不严重, 而且由于关键单元比输出节点要少很 多, 即使在出现重叠的情况下, 也很容易为重叠单元找到一个次优匹配的输出节点, 因此一 般情况下分配后对布局结果的影响并不大. 我们设计了一个基于贪心思想的分配算法来处 理这种情况. 算法描述如下: 第一步: 初始化关键单元集合 A 和输出节点集合 B , 即 A = {1, 2, …, K }, B = {1, 2, …, N }. 第二步: 相对于样本 i, 输出节点 j 的输出值用 y ij 表示. 如果 y a , b = m ax ( y ij ) , a ∈ A , b ∈ B ,
i∈A , j ∈B

则将输出节点 b 分配给关键单元 a , 并且 A = A - {a }, B = B - {b}. 第三步: 如果集合 A 非空, 则转到第二步, 否则结束.

6 非关键单元的定位

自组织学习算法和分配算法可以确定关键单元在布局平面上的位置. 对于门阵列版图 模式, 可以用 Steinberg 法、 对交换法、 邻域交换法、 力向量成对交换法、 力向量松弛法、 广义 力向量松弛法等迭代改善方法来减少单元的总连线长度, 以确定非关键单元在布局平面上 的位置. 由于此时已与关键线网、 热源单元无关, 所以也可以用传统的提高布通率的算法来 确定非关键单元的位置.

7 实验结果

本算法已用 Bo rland C + + 编程, 在 486 66 计算机上实现. 两类布局实例被用来验证算 法的有效性: 第一类为规则的筛网结构电路, 并在电路上指定一条或多条关键路径 这类例 . 子的最佳布局构型是已知的, 比较容易判断一个布局结果与最佳布局有多大偏差. 另一类例 子由计算机随机产生, 它更具一般性. 表 2 给了测试用的 4 个电路的有关信息, 其中例 1 和

( 5) 收敛条件中的 Ε越小或选取的迭代次数越多, 解的质量越好, 但所需的计算时间越

( 4) 参数 Σ和 Χ越大, 网络收敛得越快, 但解的质量会受影响 .

9期

胡卫明等:  用神经网络求解时延、 功耗和连线三重驱动的布局问题

801

例 2 为第一类电路, 例 3 和例 4 为第二类例子.
表 2 实验电路的有关信息
例号
1 2 3 4

单元数
25 25 100 200

线网数
40 40 210 454

关键单元数
5 9 39 93

关键线网数
4 7 71 141

2 端线网数 40 40 136 241

3 端线网数 0 0 52 116

4 端线网数 0 0 22 97

  表 3 给出了例 2 的样本数据, 图 2 和表 4 是例 2 在不同时刻的执行情况和运行结果. 从 结果可以看出, 关键线网的长度达到最短, 热源单元 1、、 和 9 分得较开. 4 7
表 3 例 2 的样本数据
单元 号
1 2 3 4 5 6 7 8 9
n1 n2 n3

特 征 量
n4 n5 n6 n7

散热
1 0 0 0. 9 0 0 0. 8 0 0. 85

0. 9 0. 9 0 0 0 0 0 6 0

0 0. 95 0. 95 0 0 0 0 0 0

0 0 0. 85 0. 85 0 0 0 0 0

0 0 0. 87 0 0. 87 0 0 0 0

0 0 0 0 0 0. 92 0 0. 92 0

0 0 0 0 0 0 1 1 0

0 0 0 0 0 0 0 0. 96 0. 96

图 2 例 2 在不同时刻 t 的执行情况 表 4 例 2 在不同时刻的运行结果
测试量 ( 关键线网总长)
Euclidean 平方和 M anhattan 距离
t= 0 t= 6 t= 12 t= 25 t= 50 t= 100

51 29

36 20

29 16

20 12

11 9

7 7

  表 5 比较了本算法与 HNN 算法的实验结果. 其中 HNN 算法是由文献 [ 1 ] 中的算法改 进得来的: 文献 [ 1 ] 优化的是连线总长, HNN 算法改进为优化关键线网的长度. 本算法的运

802

半 导 体 学 报

20 卷

行结果依赖于随机产生的网络初始权值, 表 5 的例 3、 4 是 5 次运行的最佳结果 ( 例 1、 2 例 例 的规模较小, 每次运行均能达到最优解). 从表中可以看出, 本算法不仅运行速度快于 HNN 算法, 而且布局的质量也优于 HNN 算法.
表 5 实验结果
例 号
1 2 3 4

关键线网 Euclidean 总长 本算法
4 7 112 236 HNN 算法 4 9 125 248

关键线网 M anhattan 总长 本算法
4 7 139 274 HNN 算法 4 10 164 297

运行时间 s 本算法
0. 05 0. 12 8. 40 90. 3 HNN 算法 0. 07 0. 53 23. 9 264. 0

8 结束语
本文应用 Kohonen 自组织神经网络求解以关键线网时延最小、 散热大的单元相距尽可 能远并且单元间连线总长度尽可能短为优化目标的门阵列布局问题. 与文献 [ 4 ] 相比, 本算 法的特点是: 是门阵列布局, 而后者是任意单元布局; 建立了面向线网的样本矢量能够直接 处理多端线网的思想; 用分配算法处理关键单元重叠现象; 能优化单元间的连线. 参 考 文 献

[ 1 ]  Sriram M. , Kang S. M. , P roc. of ISCA S, 1990: 1664 1667. ~ [ 2 ]  H em an i A. , Po stu la A. , N eu ral N etw o rk s, 1990, 3 (1) : 377 383. ~ [ 3 ]  沈涛, 等, 电子学报, 1992, 20 (10) : 100 105. ~ [ 4 ]  Zhang C. X. , P roc. of ISCA S, 1993: 2067 2070. ~ [ 5 ]  焦李成, 神经网络计算, 西安: 西安电子科技大学出版社, 1995, 第 2 章. [ 6 ]  U naltuna M. K. , P itchum an i V. , P roc. of ISCA S, 1993: 2047 2050. ~ [ 7 ]  Glo ria A. D. , Farabo sch i P. , O livieriM. , IEEE T ran s. CAD , 1994, 13 (6) : 694 701. ~

9期

胡卫明等:  用神经网络求解时延、 功耗和连线三重驱动的布局问题

803

Neura l Network Approach for T i ing, Power D iss ipa tion m and W ire Connection D r iven P lacem en t
H u W eim ing
( Institu te of Com p u ter S cience and T echnology , P ek ing U n iversity , B eij ing  100871)

L i Cu ichao , Zhu Yu song, Yan X iao lang
(CA D Cen ter, H ang z hou Institu te of E lectron ics E ng ineering , H ang z hou  310037) R eceived 3 M arch 1998, revised m anu scrip t received 25 June 1998

pow er d issip a t ion, and w ire connect ion d riven p lacem en t of ga te a rray. In the a lgo rithm , the crit ica l net s a re m in im ized, the d istance betw een hea t sou rce cells is m ax im ized, and the to 2 a lgo rithm a re u sed to fit the crit ica l cells, and t rad it iona l itera t ive im p rovem en t m ethod is sim ila rity vecto r is in t roduced. Com p a red w ith the cell o rien ted sim ila rity vecto r, net and ta l leng th of net s is m in im ized. T he self 2 rgan izing lea rn ing app roach and the a ssignm en t o show s tha t it is an effect ive m ethod.

pow er d issip a t ion o rien ted sim ila rity vecto r can no t on ly dea l w ith the m u lt i2term ina l net s d irect ly, bu t a lso describe the info rm a t ion abou t t im ing and hea t. T he exp erim en ta l resu lt CCACC: 7410D , 5120

Abstract T he Kohonen self 2 rgan izing neu ra l netw o rk app roach is app lied to the t im ing, o

. u sed to fit the o ther cells In add it ion, the concep t of net and pow er d issip a t ion o rien ted


相关文章:
用神经网络求解时延、功耗和连线三重驱动的布局问题.pdf
用神经网络求解时延功耗和连线三重驱动的布局问题_专业资料。本文应用Kohone
用神经网络求解时间驱动的宏单元布局问题.pdf
用神经网络求解时间驱动的宏单元布局问题 - 文中提出了一个宏单元布局的均场退火网络求解方法.算法用一个三维二值换位矩阵将问题映射为神经网络,建立包含时延约束...
功耗和时延双重驱动的VLSI布局算法.pdf
功耗和时延双重驱动的VLSI布局算法.以往发表的布局...可以大致分为基于线网和基于路径[ 1~ 3 ] 的两...用神经网络求解时延、功... 暂无评价 7页 免费 ...
基于神经网络的时延驱动版图规划算法.pdf
基于神经网络的时延驱动版图规划算法 - 本文用离散的网格代替连续的版图规划平面,把长宽比可变的软模块对应成多个长度和宽度均确定的硬模块,给出了相应的时延驱动...
一种基于敏感度的时延驱动快速布局算法-电子学报_图文.pdf
的思想提出一种基于敏感度的线网权重模型, 进而提 出一种基于敏感度的时延驱动快速布局算法 . 该模型 在布局算法的解方程阶段不仅考虑了关键线网的关键 度和松弛...
基于神经网络的时延预测算法研究_图文.pdf
文章编号 基于神经网络的时延预测算法研究孙立宁 谢...解决延迟模型误差问题 通过在线辨识和参数调节 在时延...来生成和计算线 误差 出下一个时延值 其输入输出...
基于神经网络预测的网络控制系统故障检测_图文.pdf
时延 图2基于神经网 络预 测的 网络 控制系 统...制器节 点均 为时间驱动,控 且时钟完 全 同步 ...非线 性的, 以使 用工 具 难 软件 直接求解 ...
第三章 神经网络控制及应用(基础)_图文.ppt
知识库 平行推理 输入数据 变量变换 求解的问题 神经网络专家系统的构成 由神络...T j } (3-1) τij 输入输出间的突触时延; 输入输出间的突触时延; ...
具时延的细胞神经网络的全局渐近稳定性分析.pdf
[)91) 』一 摘要 本文通过Ly8puz-ov泛函方法和新的不等式n 26曼(2n3+矿)/3,(n,b三0)分析技巧, 讨论了一类具时延的细胞神经网络DcNN全局渐近稳定性问题...
Elman改进型神经网络在X射线探测器中的应用-论文_图文.pdf
3 5卷第 5期201 5年 5月 核 电子 学探 ...控制器产生 CMOS 传感器的驱动信号来控 制探测 器 ...由于 Elma n神经网络具有局部 递归、 反馈时延的特性...
基于相空间重构理论的时延神经网络应用于降雨径流预报_....pdf
基于相空间重构理论的时延神经网络应用于降雨径流预报_能源/化工_工程科技_专业资料。本文运用时延神经网络模型来模拟降雨径流过程,根据Takens相空间重构理论对前期影响...
更多相关文章: