MARCH: MAze Routing Under a Concurrent and Hierarchical Scheme for Buses

论文信息

作者： Jingsong Chen, Jinwei Liu, Gengjie Chen, Dan Zheng, Evangeline F. Y. Young

单位： 香港中文大学（CUHK）计算机科学与工程系

发表会议： DAC 2019

摘要

现代VLSI技术的持续发展为片上互连带来了新的挑战。与经典的逐网路由不同，总线路由要求同一总线中的所有网络（位）共享相似甚至相同的拓扑结构，除了考虑线长、过孔数量和其他设计规则外。本文提出了MARCH，一种在并发和分层方案下进行总线路由的高效迷宫路由方法。在MARCH中，为了实现相同的拓扑，总线中的所有位像在路径中行进一样并发路由。为了提高效率，我们的方法是分层的，包括粗粒度的拓扑感知路径规划和细粒度的位轨迹分配。此外，应用了有效的撕裂和重新布线方案以进一步提高解决方案质量。在实验结果中，MARCH在质量和运行时间方面都显著优于2018年IC/CAD竞赛的第一名。

引言

MARCH: MAze Routing Under a Concurrent and Hierarchical

The continuous development of modern VLSI technology has brought

new challenges for on-chip interconnections. Different from classic

net-by-net routing, bus routing requires all the nets (bits) in the same

bus to share similar or even the same topology, besides considering

wire length, via count, and other design rules. In this paper, we present

MARCH, an efficient maze routing method under a concurrent and hi-

erarchical scheme for buses. In MARCH, to achieve the same topology,

all the bits in a bus are routed concurrently like marching in a path. For

efficiency, our method is hierarchical, consisting of a coarse-grained

topology-aware path planning and a fine-grained track assignment for

bits. Additionally, an effective rip-up and reroute scheme is applied to

further improve the solution quality. In experimental results, MARCH

significantly outperforms the first place at 2018 IC/CAD Contest in

The continuous development of modern VLSI technology has brought

new challenges for on-chip interconnections. In modern designs, there

are buses with long wires that can introduce long wire delay. To main-

tain signal integrity, some post-routing optimizations such as buffer

insertions are needed. However, if the bits in the same bus are routed

in different topologies, it is very difficult to find places to insert buffers

for different bits of the same bus in a regular manner. To resolve this

problem, it is preferred to have the same routing topology among all

the bits of a bus, which is different from classic net-by-net routing. In

spite of reducing the size of the solution space of the routing problem

to some extent, this topology constraint also makes it more difficult

to efficiently allocate appropriate routing resources to each bus on

multiple metal layers. Meanwhile, similar to classic net-by-net routing,

solution qualities such as wire length and via count are also important

metrics to optimize for bus routing. An effective bus router should

provide a solution with high routing quality while maintaining the

The work described in this paper was partially supported by a grant from the Research

Grants Council of the Hong Kong Special Administrative Region, China (Project No.

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed for

profit or commercial advantage and that copies bear this notice and the full citation on the

first page. Copyrights for components of this work owned by others than ACM must be

honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on

servers or to redistribute to lists, requires prior specific permission and/or a fee. Request

Figure 1: (a) A bus with two pins and three bits to be routed;

(b) The bits routed one by one; (c) The Topology-Aware Path

planning (TAP) result; (d) The Track Assignment for Bits (TAB)

topology consistency among different bits of the bus for the benefits

Routing has been well studied by many previous works, including

both global routing (e.g. ARCHER [ 1], NCTU-GR [ 2], and NTHU-

Route [3]) and detailed routing (e.g. TritonRoute [ 4] and Dr. CU [ 5]).

However, the techniques of these works can hardly be straightfor-

wardly applied in bus routing due to the difficulty of maintaining

topology consistency. If the buses are processed bit by bit (e.g. route

bit 1, 2 and 3 sequentially as in Figure 1 (b)), the latter bits may lack

available track segments to be routed on especially when the routing

track configuration is non-uniform and complex. In the worst case,

关键词： 总线路由、迷宫路由、并发布线、分层方案、VLSI、EDA

PDF下载： 从作者主页下载