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

• 作 者: 李康[1]虞厥邦[2]廖勇[3]
• 机 构: 电子科技大学电子工程学院570教研室,成都 610054
• 出 处: 全国第19届计算机技术与应用学术会议(CACIS·2008)
• 发表日期: 2008年期

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