Timing-driven placement is critical to achieve high performance SoC designs. Existing algorithms cannot guarantee timing feasibility: wirelength weights which reflect timing criticalities cannot give predictable placement solutions; bounds on half perimeter of bounding box cannot imply bounds on wirelength for nets with more than three terminals; wirelength estimates from wireload models are known to have large deviations and cannot provide wirelength bounds. We propose more accurate mapping of timing constraints into physical locations. Our algorithm computes timing feasible locations by geometric computation, which guarantees timing feasibility and introduces less pessimism.

Interconnects dominate VLSI system performance in DSM (deep sub-micron) domain (i.e., up to 70% of a path delay are interconnect delays and interconnect-related gate delays). Traditional interconnect synthesis schemes minimize wirelength by solving the Steiner minimum tree problem. However in DSM domain minimum wirelength may not imply timing optimum, and timing optimum depends on geometric, electrical, and timing criticality parameters. Existing timing-driven interconnect synthesis algorithms are either purely geometric, heuristic, or suffer from scalability problem and cannot handle instances of practical sizes.

Our contributions include: (1) We observe an ``chicken-egg'' dilemma between VLSI interconnect timing optimization and delay calculation, and suggest an iterative timing-driven interconnect synthesis approach. (2) We separate interconnect timing transformation as Hanan grafting and non-Hanan sliding, and reveal generally negligible contribution of non-Hanan sliding. (3) Our greedy iterative timing optimization algorithm ``Q-Tree'' achieves ``dominant''solutions (with shorter wires, less buffers, and better timing performance) over existing algorithms (e.g., PER-Steiner, C-Tree, BA-Tree and P-Tree). In general, Q-Tree can be applied to any interconnect tree for further timing performance improvement, with practical instance sizes and easily-extended functionality (e.g., including buffer station and routing obstacle avoidance considerations).

Upper-bounding the capacitive load of a driver is a typical industry practice of today, which effectively bounds signal slew rate, coupling noise, and delay uncertainty; such a design methodology also reduces hot-carrier oxide breakdown and interconnect AC self-heating, and helps design technology migration. We have proposed six distinct algorithms for either buffer/inverter insertion, with/without the freedom of changing the routing tree, and with/without an approximation ratio/error bound. We also show the suboptimality of a previously published (and claimed optimal) greedy algorithm (for minimum buffering of a clock tree with prescribed buffer skew bound), and propose a dynamic programming algorithm for this minimum buffer skew problem.

Early planning of buffer and wiring resources is a critical aspect of every modern high-performance VLSI implementation methodology. Today, such planning is needed to evaluate the quality of RT-level partitioning and soft (pre-synthesis) block placement/shaping, system-level timing constraints, and pin definition and buffered routing of global interconnects. In our recent ASPDAC'02 Best Paper, we have proposed a new algorithm for floorplan evaluation using timing-driven buffered routing according to a prescribed buffer site map. Specifically, we have proposed a provably good multi-commodity flow based algorithm that finds a global routing minimizing routing area (wirelength and number of buffers) subject to given constraints on buffer/wire congestion and sink delays. This permits detailed floorplan evaluation, i.e., computing the tradeoff curve between routing area and wire/buffer congestion under any combination of delay and capacity constraints. Our algorithm (1) enforces maximum source/buffer wireloads; (2) enforces wire and buffer congestion constraints by taking into account routing channel capacities and buffer site locations; (3) enforces individual sink delay constraints; (4) performs buffer/wire sizing and layer assignment; and (5) integrates pin assignment with virtually no increase in runtime. Preliminary experiments show that near-optimal results are obtained with a practical runtime. Future work aims to incorporate in our implementation practical improvements such as the use of uneven sized tiles, window constraints on buffer usage (as opposed to tile constraints), and faster-converging dual-update rules.

Continuous VLSI process technology advancement has been enabled by low defect density. However, continuous reduction in defect density cannot be expected by development of process technology in the near future. Design-for-manufacturability (DFM) techniques must be applied to improve manufacturing yield of large-area chips, and decrease sensitivity of parametric (performance) yield to variability of high-performance designs.

Back-end-of-line(BEOL) defects (e.g., high-resistance via or interconnect defects) have increasing occurrence probability than front-end-of-line (FEOL) defects in nanometer technologies. Interconnects are increasing defect-prone. We propose introduction of redundant interconnect as a post-routing optimization for manufacturing yield and reliability improvements. We formulate the problem as a variant of the classic NP-hard 2-edge connectivity augmentation problem, which minimizes defect-prone ``critical area'' with a minimal amount of extra wireing, and propose both linear programming and a greedy algorithm which comes within 1-2% of the optimum on the average. Our experiments reveal improved manufacturing yield, timing performance, and performance reliability to process variation.

We have explored the theoretical foundations of scaling models for large-scale systems. One such scaling model is given by Rent's Rule, a simple empirical model first documented in the 1970s; today, Rent's Rule forms the foundation of numerous interconnect prediction research efforts. We have studied several random graph models from which other interconnect scaling phenomena can be inferred, and which appear equally well-supported (in comparison with Rent's Rule) by empirical data. We suggest that Rent's Rule may not be the only underlying scaling law for VLSI interconnects. Other interconnect scaling phenomena may independently apply, and Rent's Rule itself may be an implication of some more fundamental observations.

Wireload models are typical wirelength estimates in industry. However, wirelength estimates from wireload models suffer from large deviations and cannot provide guaranteed accuracy. We propose to improve accuracy of wireload models and Rent's Rule based interconnect prediction techniques by taking routing obstacles into account. Such obstacles are more common in SoC (System-on-Chip) designs, e.g., formed by large IP blocks, memory, analog, RF, etc. modules.