Abstract

Our research focuses on routing the Clock Distribution Network (CDN). The CDN consumes an increasing portion of all resources in terms of wiring area, power, and design time. Different approaches that have been proposed, such as Deferred-Merge Embedding algorithm (DME) and Greedy-DME (GDME), require the re-calculation of the whole solution when there is a change in the skew constraint or the location or the load capacitance of the clock pins. Redesigning the CDN would be an extremely computation intensive process for a complex system, and very painful with the increase in demand for shorter time to market. For this reason, we have used an incremental routing scheme. The incremental routing or ECO (Engineering Change Order) routing is a new field that has been introduced to meet the demand of high performance and complex designs. We propose a new method, called Adaptive Wire Adjustment (AWA), to minimize the skew of a given CDN to any given bound by tuning its wire lengths in order to cope with minor modifications in System on Chip (SoC) during the design process. The proposed algorithm outperforms DME and GDME for implementing ECO for large CDNs. Moreover, to speed up AWA's convergence, we propose the use of a Local Topology Modification (LTM) technique. Additionally, LTM helps to enhance the CDN's quality in terms of total wire length and wire elongations. We show that GDME relies heavily on wire elongations and offers a solution that suffers from large Standard Deviation of the Path Lengths (SDPL) between clock pins and the CDN's root. To our knowledge, this thesis is one of the first of its kind that deals with minor CDN's modifications and local topology modification. In addition to satisfying the timing requirements, the CDN has to be routed with minimum wire length. Moreover, it is often the case that the interconnects of a net must not intersect with some obstacles in the routing plane. We propose a simple model called Shortest Paths Polygon (SPP) to describe the routing area of shortest paths between two points among obstacles. A methodology is proposed to determine the SPP of two points using a gridless graph. The SPP model facilitates a better routing of any multi-terminal net since it determines all shortest paths. Consequently, using the SPP would provide a good correlation between detailed routing and other design phases. This is important because it satisfies the system requirements and supports ECO routing effectively. The SPP model is applied to three problems related to the CDN routing: tuning the CDN under obstacle constraints, designing a ZSCDN under obstacle constraints, and routing the CDN in two layers.