Answers are grounded in this paper and cite their sources.
Routing is a key stage for VLSI physical design. Steiner tree construction is a well studied topic in design automation. There have been a number of significant theoretical advances in the past few years. The focus of this paper is on combining the speed and solution quality of a high quality Steiner heuristic with the reality of modern routing. Practical designs contain routing congestion and blockages; routing is implemented across multiple layers. Each routing layer has preferred directions, and connecting vias have significant cost. In a modern design, many trees are in competition with each other for scarce routing resources. The objective is not to simply build trees with the lowest length; they must also be low cost. We present an approach that is as fast as spanning tree construction, while accurately modeling routing costs. Our work extends an earlier Steiner tree heuristic algorithm by adding the ability to minimize the routing congestion without altering the computational complexity of the underlying algorithm. We compare our CAST algorithm with the capacitated minimum spanning tree (CMST) and the ER algorithm finding that our approach offers impressive reduction in congestion cost in average about 23.1% and 63.4%, respectively.
No takes yet. Share an insight, caveat, or question.
Terapasirdsin et al. (2008) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: