计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2014年
10期
1909-1914
,共6页
马坤%齐子阳%周强%蔡懿慈
馬坤%齊子暘%週彊%蔡懿慈
마곤%제자양%주강%채의자
总体布线%矩形Steiner最小树%布线灵活度
總體佈線%矩形Steiner最小樹%佈線靈活度
총체포선%구형Steiner최소수%포선령활도
global routing%rectilinear Steiner minimal tree%flexibility
矩形Steiner最小树(RSMT)的布线灵活度影响其结构变形能力,直接影响芯片布线的收敛性.文中从树边形态、结构固有变形和拓扑变形3方面对线网的RSMT的布线灵活度进行刻画,给出了更能反映RSMT结构变形能力的计算模型.针对布线灵活度的“瓶颈”问题,提出了拥挤驱动的RSMT布线灵活度挖掘算法:根据树形的最短布线路径布线可能情况,定义了树边的布线灵活度;进而考虑RSMT结构中所有树边布线灵活度的组合情况和RSMT拓扑的变形性,得到RSMT布线灵活度.实验结果表明:将计算模型应用到拥挤驱动的RSMT布线灵活度挖掘算法,良好地改善了布线拥挤;将该挖掘算法应用到FastRoute4.1总体布线算法中,能够缩短14％的运行时间.
矩形Steiner最小樹(RSMT)的佈線靈活度影響其結構變形能力,直接影響芯片佈線的收斂性.文中從樹邊形態、結構固有變形和拓撲變形3方麵對線網的RSMT的佈線靈活度進行刻畫,給齣瞭更能反映RSMT結構變形能力的計算模型.針對佈線靈活度的“瓶頸”問題,提齣瞭擁擠驅動的RSMT佈線靈活度挖掘算法:根據樹形的最短佈線路徑佈線可能情況,定義瞭樹邊的佈線靈活度;進而攷慮RSMT結構中所有樹邊佈線靈活度的組閤情況和RSMT拓撲的變形性,得到RSMT佈線靈活度.實驗結果錶明:將計算模型應用到擁擠驅動的RSMT佈線靈活度挖掘算法,良好地改善瞭佈線擁擠;將該挖掘算法應用到FastRoute4.1總體佈線算法中,能夠縮短14％的運行時間.
구형Steiner최소수(RSMT)적포선령활도영향기결구변형능력,직접영향심편포선적수렴성.문중종수변형태、결구고유변형화탁복변형3방면대선망적RSMT적포선령활도진행각화,급출료경능반영RSMT결구변형능력적계산모형.침대포선령활도적“병경”문제,제출료옹제구동적RSMT포선령활도알굴산법:근거수형적최단포선로경포선가능정황,정의료수변적포선령활도;진이고필RSMT결구중소유수변포선령활도적조합정황화RSMT탁복적변형성,득도RSMT포선령활도.실험결과표명:장계산모형응용도옹제구동적RSMT포선령활도알굴산법,량호지개선료포선옹제;장해알굴산법응용도FastRoute4.1총체포선산법중,능구축단14％적운행시간.
