论文部分内容阅读
提出了一种基于CBL布图表示的新的增量式布图规划算法.该算法能很好地解决包括不可二划分结构在内的布图规划问题.针对现有增量式的一些需求,算法给出了相应的高速解决方案.在已有的初始布局的基础上,基于CBL表示方法建立水平约束和垂直约束图,利用图中关键路径和各模块之间的累加的距离松弛量进行增量式操作.对于新模块的插入,在力求面积最小,线长最短和移动模块数目最少的目标指引下能快速地找到最佳位置作为插入点,高效地完成相关操作,算法的时间复杂性仅为O(n).通过对一组来自工业界的设计实例的测试结果表明,该算法在保证芯片的面积、线长等性能不降低甚至有所改善的情况下,运行速度相当快,仅在μs量级,满足了工业界对增量式布图规划算法在速度上的首要要求,同时保证了基本性能的稳定.
This paper proposes a new incremental layout plan algorithm based on CBL layout representation, which can well solve the layout planning problem including the non-divisible partition structure.Aiming at some existing incremental requirements, The corresponding high-speed solution is given.On the basis of the existing initial layout, a horizontal constraint and a vertical constraint map are established based on the CBL representation method, and the critical path and the accumulated amount of slack between the modules are used to increase For the insertion of a new module, the optimal position can be quickly found as an insertion point under the guidance of the goal of minimizing area, shortest line length and minimizing the number of moving modules, and the related operations are completed efficiently. The time complexity of the algorithm is only as high as Is O (n) .Through a series of industrial design examples from the test results show that the algorithm to ensure that the chip area, length and other performance does not reduce or even improve the circumstances, the operation speed is very fast, only in μs order of magnitude to meet the industry’s primary requirements for incremental layout algorithm in the speed, while ensuring the stability of the basic performance.