Existing routing problems for delay minimization consider the connection of a single source node to a number of sink nodes, with the objective of minimizing the delay from the source to all sinks, or a set of critical sinks. In this paper, we study the problem of routing nets with multiple sources, such as those found in signal busses. This new model assumes that each node in a net may be a source, a sink, or both. The objective is to optimize the routing topology to minimize the total weighted delay between all node pairs (of a subset of critical node pairs). We present a heuristic algorithm for the multiple-source performance driven routing tree problem based on efficient construction of minimum diameter minimum-cost Steiner trees. Experimental results on random nets with submicrometer CMOS IC and MCM technologies show an average of 12.6% and 21% reduction in the maximum interconnect delay, when compared with conventional minimum Steiner tree based topologies. Experimental results on multisource nets extracted from an Intel processor show as much as a 16.1% reduction in the maximum interconnect delay, when compared with conventional minimum Steiner tree based topologies.
展开▼
