ZERO SKEW CLOCK ROUTING WITH MINIMUM WIRELENGTH

In the design of high performance VLSI systems, minimization of clock skew is an increasingly important objective. Additionally, wirelength of clock routing trees should be minimized in order to reduce system power requirements and deformation of the clock pulse at the synchronizing elements of the system. In this paper, we first present the deferred-merge embedding (DME) algorithm, which embeds any given connection topology to create a clock tree with zero skew while minimizing total wirelength. The algorithm always yields exact zero skew trees with respect to the appropriate delay model. Experimental results show an 8% to 15% wirelength reduction over previous constructions in [17] and [18]. The DME algorithm may be applied to either the Elmore or linear delay model, and yields optimal total wirelength for linear delay. DME is a very fast algorithm, running in time linear in the number of synchronizing elements. We also present a unified BB + DME algorithm, which constructs a clock tree topology using a top-down balanced bipartition (BB) approach, and then applies DME to that topology. Our experimental results indicate that both the topology generation and embedding components of our methodology are necessary for effective clock tree construction. The BB + DME method averages 15% wirelength savings over the previous method of [17], and also gives 10% average wirelength savings when compared to the method of [25]. The paper concludes with a number of extensions and directions for future research.