用角轮廓结构实现基于单序列表示法的快速模块放置算法

摘要：

在VLSI的物理设计中，单序列表示法(Single-sequence，简称SS)利用自然数1，2，3，...n的全排列来表示平面上n个不重叠物体间的上下左右位置关系。物体间的拓扑位置由代表它们的自然数在单序列中的位置和大小关系决定。原始基于单序列的模块放置算法并不完善，其算法时间复杂度为O(n2)。本文提出利用角轮廓结构实现基于单序列表示法的模块快速放置算法。在模块放置过程中只保持一个角轮廓，并且利用角轮廓的阶梯下降性，结合单序列表示法编码给出的模块间的位置关系，使每个模块的放置时间下降为O(logn)，算法整体时间复杂度下降为O(nlogn)。在MCNC标准实验例子上的实验结果验证了算法的有效性。

关键词： 物理设计 布图规划 单序列表示法 模块放置 放置算法

作者: 李康 虞厥邦 廖勇

作者单位: 电子科技大学电子工程学院570教研室,成都 610054;四川交通职业技术学院,成都 611130 电子科技大学电子工程学院570教研室,成都　610054 电子科技大学计算机科学与工程学院实时系统实验室,成都 610054

会议类型: 国内会议

会议名称: 全国第19届计算机技术与应用学术会议(CACIS·2008)

会议地点: 合肥

会议语种:中文

页码: 185-190

在线出版日期: 2008-07-15（万方平台首次上网日期，不代表论文的发表时间）