The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. The BSMA can handle asymmetric link characteristics and variable delay bounds on destinations, specified as real values, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The BSMA's expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution.

To achieve path delay balance, instead of making faster paths slower by elongating wires used in most zero skew clock routing methods, we make slower paths faster by the wire sizing. The wire sizing technique is frequently used by IC designers to minimize the clock skew caused by the unbalanced RC delays and transmission line noises. However, manual sizing takes a long time and lacks accurate relationship between the timing and wire widths. This paper formulates the optimal clock sizing problem and proposes a sizing optimization algorithm based on Gauss-Marquardt's least square minimization method. The minimum skew is achieved by this method due to its uphill mechanism of searching the global minimum by selecting a proper Lagrange multiplier dynamically at each iteration. The optimization is guided by the delay calculation based on a distributed RLC interconnect model which takes into the account the nonnegligible inductance in high-speed long interconnects (such as on the substrate of a multichip module). The algorithm and delay model can handle a general clock network including loops such as a clock mesh. For testing examples of equal path length clock trees, this algorithm can further achieve 10/spl times/ skew reduction and 14% path delay reduction after the sizing.

A new concept of chip and package co-design for the clock network is presented in this paper. We propose a two level clock distribution scheme which partitions the clock network into two levels. First, the clock terminals are partitioned into a set of clusters. For each cluster, a local on-chip clock tree is used to distribute the clock signal from a locally inserted buffer to terminals inside this cluster. The clock signal is then distributed from the main clock driver to each of local buffers by means of a global clock tree, which is a planar tree with equal path lengths. With the flip chip area I/O attachment, the planar global clock tree can be put on a dedicated package layer. The interconnect on the package layer has two to four order smaller resistance than that on the chip layer. The main contribution of this paper is a novel algorithm to construct a planar clock tree with equal path lengths-the length of the path from the clock source to each destination is exactly the same. In addition, the path length from the source to destinations is minimized.

A new heuristic algorithm is presented for constructing minimum-cost multicast trees with delay constraints. The new algorithm can set variable delay bounds on destinations and handles two variants of the network cost optimization goal: one minimizing the total cost (total bandwidth utilization) of the tree, and another minimizing the maximal link cost (the most congested link). Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible search optimization method which starts with the minimum-delay tree and monotonically decreases the cost by iterative improvement of the delay-bounded tree. The optimality of the costs of the delay-bounded trees obtained with the new algorithm is analyzed by simulation. Depending on how tight the delay bounds are, the costs of the multicast trees obtained with the new algorithm are shown to be very close to the costs of the trees obtained by the Kou, Markowsky and Berman's algorithm (1981).

To achieve delay balance, instead of making the faster path slower by elongating branches, we make slower paths faster by sizing. Given a general clock network, which may includes loops, together with a set of feasible widths for each branch, we formulate the optimal sizing of the clock network as a constrained optimization problem. By turning the skew minimization problem into a least-squares estimation problem, a modified Gauss-Marquardt's method is used to determine the optimal widths. An efficient initial sizing algorithm is proposed to speed up the sizing process. Instead of using zero-order delay model (path length) or one-order delay model (Elmore delay), we employ a generalized delay model which can handle general RLC and transmission line networks. Experimental results show that this method significantly reduces both the clock skew and path delays from source to terminals.

In the design of high speed digital VLSI circuits, it is preferable that the clock net be routed on the metal layer with the smallest RC delay. This strategy not only avoids the difficulties of having different electrical parameters on different layers, but also eliminates the delay and attenuation of the clock signal through vias. The clock phase-delay is also decreased. An algorithm, based on max-min optimization, to construct a planar clock tree which can be embedded on a single metal layer is presented. The clock tree achieves equal path lengths, i.e., the lengths of the paths from the clock source to each clock terminal are exactly the same. In addition, the path length from the source to clock terminals is minimized. Some examples including industrial benchmarks have been tested, and the results are promising.>