考虑总线时序匹配的多策略层分配算法

Multi-Strategy Layer Assignment Algorithm Considering Bus Timing Matching

在总体布线的过程中,层分配阶段通过控制总线线网的层次影响总线的时序匹配效果.为此,提出考虑总线时序匹配的多策略层分配算法.首先基于线网属性的线网优先级策略,针对线网不同属性的特点得到一个兼顾线长和总线偏差的布线顺序;然后基于贪心策略的初始布线策略,每次布线都对正在布线的线网选择当前最短路径,使相同总线内的线网都尽可能等长;最后基于总线线长的局部调整策略对初始的布线结果进行拆线重绕,延长部分线网以缩短其与最长的总线线网之间的线长差距.算法在2.60GHzCPU和64 GB内存的Linux环境下运行,使用ISPD竞赛中提供的测试数据进行算法的有效性验证.实验结果表明,所提算法产生的总线偏差降低了23.5%,能够显著优化总线时序匹配效果.

Layer assignment stage affects the timing matching of the bus by controlling the level of bus net in the global routing stage.Therefore,a multi-strategy layer assignment algorithm considering bus timing matching is proposed.First,a network prioritization strategy based on wired network attributes is adopted to acquire a routing sequence that satisfies not only the wire lengths but also the bus deviation according to the different attribute characteristics of the network.Second,using the initial routing strategy based on the greedy strategy,every shortest route in the network being configured is selected from each routing process,which keeps networks inside similar buses to be of equal lengths whenever possible.Finally,a local adjustment strategy formulated based on the bus wire length is employed to rip and reroute the completed initial routing,so as to lengthen parts of the network to minimize the length discrepancy between the bus longest wired network.The algorithms run in a Linux environment with a 2.60 GHz CPU and 64 GB of RAM.The algorithm validation experiments use the test data from the ISPD competition,and the experimental results show the bus deviation generated by this algorithm is reduced by 23.5%,and it is possible to significantly optimize the bus timing matching effect.