M.Sc Thesis

M.Sc StudentMoiseev Konstantin
SubjectPerformance Optimization by Reordering of Interconnect Wires
DepartmentDepartment of Electrical and Computer Engineering
Supervisors ASSOCIATE PROF. Shmuel Wimer


Interconnect delays have become dominant in CMOS VLSI digital systems as a result of technology scaling. This thesis addresses the problem of ordering and sizing parallel wires in a single metal layer within an interconnect bus of a given width, such that cross-capacitances are optimally shared for circuit delay minimization.

Three different objective functions are defined for minimization: total sum of wire delays in a bus, worst wire delay and worst wire slack. Using an Elmore delay model including cross capacitances for a bundle of variable-width wires, an optimal wire ordering is uniquely determined for the first objective function, such that best timing can be obtained by proper allocation of inter-wire spaces. The optimal ordering, called BMI (Balanced Monotonic Interleaved) depends on the size of drivers, and is independent of size of receivers. For the second and third objective functions (worst wire delay and worst wire slack) the BMI order is shown empirically to be optimal. Influence of non-homogenous crosstalk and edge effects on nominal delays are examined. Methods for optimization impact estimation are proposed.

The thesis also discusses minimization of crosstalk by wire ordering. Two corresponding objective functions are defined: total sum of wire delay uncertainties and worst wire delay uncertainty. It is shown that both delay uncertainty objectives are optimized by the orders delay objectives are. Monotonic ordering according to driver strength is shown to be advantageous for several objective functions. Efficient exact and heuristic algorithms are proposed for all kinds of optimizations described.

Examples for 90-nanometer technology are analyzed and discussed.