Congratulations that Mr. Gengjie Chen, Ms. Peishan Tu, and Prof. Evangeline F.Y. Young won the prestigious William J. McCalla Best Paper Award at the
IEEE/ACM International Conference on Computer Aided Design (ICCAD) 2017.
Co-sponsored by the Council on Electronic Design Automation (CEDA) of the Institute of Electrical and Electronics Engineers (IEEE), and the Special
Interest Group on Design Automation (SIGDA) of the Association for Computing Machinery (ACM), ICCAD is one of the most prestigious conferences
in design automation. The Best Paper Award recognizes two highest-quality research papers at the conference, one covering the front-end of the design
process and one covering the back-end.
Title: “SALT: Provably good routing topology by a novel steiner shallow-light tree algorithm”
Link: https://ieeexplore.ieee.org/document/8203828/
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. 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.
