Login | Register

Tuning and topology optimization of the clock distribution network under obstacle contraints


Tuning and topology optimization of the clock distribution network under obstacle contraints

Saaied, Haydar (2004) Tuning and topology optimization of the clock distribution network under obstacle contraints. PhD thesis, Concordia University.

[thumbnail of NR04058.pdf]
Text (application/pdf)
NR04058.pdf - Accepted Version


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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Electrical and Computer Engineering
Item Type:Thesis (PhD)
Authors:Saaied, Haydar
Pagination:xiv, 166 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Electrical and Computer Engineering
Thesis Supervisor(s):Al-Khalili, Dhamin and Al-Khalili, Asim J
Identification Number:QA 611.17 S23 2004
ID Code:8268
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:20
Last Modified:13 Jul 2020 20:03
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top