Paper

SALT: Provably good routing topology by a novel steiner shallow-light tree algorithm

Publication Date:
Publication Date
16 November 2017

paper Menu

Abstract

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates (i) shortest distances from a root to the other vertices, and (ii) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one [1], [2]. In this paper, we propose a novel Steiner SLT construction method called SALT (Steiner shAllow-Light Tree), which is efficient and has the tightest bound over all the state-of-the-art SLT algorithms. Applying SALT to Manhattan space offers a smooth trade-off between rectilinear Steiner minimum tree (RSMT) and rectilinear Steiner minimum arborescence (RSMA) for VLSI routing. In addition, the adaption further reduces the time complexity from O(n 2 ) to O(n log n). The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods.

Country
USA
Affiliation
Duke University
IEEE Region
Region 03 (Southeastern U.S.)
Email
Country
HKG
Affiliation
Chinese University of Hong Kong
IEEE Region
Region 10 (Asia and Pacific)
Email