In this paper, we study the interconnect layout optimization problem under
a higher order resistance-inductance-capacitance model to optimize not only
delay, but also waveform. for interconnects with nonmonotone signal respon
se in the context of multipchip-module global routing. We propose a unified
approach that considers topology optimization and waveform optimization si
multaneously. Using a new incremental moment-computation algorithm, we inte
rleave topology construction with moment computation to facilitate accurate
delay calculation and evaluation of waveform quality. Our algorithm consid
ers a large class of routing topologies, ranging from shortest path Steiner
trees to bounded-radius Steiner trees and Steiner routings. We construct a
set of required arrival-time Steiner (RATS) trees, providing smooth tradeo
ffs among signal delay, waveform, and routing area. When combined with the
MINOTAUR MCM global router (Cong and Madden, 1998), (Madden, 1998) that we
have developed, the RATS-tree solutions prove to be effective in reducing o
verall routing congestion.