Title

Path enumeration & redundancy removal for timing optimization

Date of Award

2009

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

C. Y. Roger Chen

Second Advisor

Chilukuri Mohan

Keywords

Redundancy, Timing optimization, Path extraction, False paths, Circuit delay

Subject Categories

Computer Engineering | Engineering

Abstract

As circuits are getting denser, the number of paths in a circuit is drastically increasing. Therefore, to consider all possible paths in a circuit to perform timing analysis would be very time consuming and sometimes impossible. However, path extraction is a very crucial step for timing verification and timing analysis of circuits. Therefore, having an efficient path selection algorithm leads to faster timing verification, analysis and optimization tools. In this dissertation, a path enumeration algorithm is proposed that enumerates all the paths whose delay exceeds a given threshold in linear-time with respect to the number of paths in the circuit. A parallel version of this algorithm is also proposed which can enumerate the paths of any circuit, regardless of how large it is, given an adequate number of machines on which the application can run on. This parallel version of the algorithm is adaptive and dynamic; that is, it analyzes the available machines and decides how many are needed to perform the enumeration and how to distribute the load among the different machines based on their available physical memory. The enumerated paths returned by both algorithms are in no particular order. Since sorting the paths in descending order of their delay is crucial for many timing optimization and verification algorithms it is important to sort the enumerated paths before they are sent to the user. To maintain linearity of the algorithm, we propose a hash-table based linear-time sorting algorithm that would sort the returned paths in descending order of their severity. Having enumerated the paths of a circuit, we explore the different methods appearing in the literature that identify the true critical delay of a circuit. Finding the longest true critical delay of a given circuit is of extreme importance as it determines the frequency of the clock with which the circuit can operate. However, due to the existence of false paths, it has been proven that the longest topological path does not always determine the true critical delay of a circuit. These false paths do not contribute to the delay of the circuit since there is no input vector that can exercise them. Once the true critical delay has been identified and the long false paths have been removed, redundancies in a circuit can be removed in any arbitrary order without penalizing the performance of the circuit. In order to make the redundancy identification more efficient, a new notion of acceleration and partial acceleration lines is proposed to allow the significant pruning of search space. Finally, we propose a new redundancy removal technique whose goal is to reduce the true delay of a circuit. Unlike redundancy addition and removal methods, this procedure is performed during the initial redundancy removal phase, and uses the notion of backward redundancy prediction to perform the required analysis and removal.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=1904937051&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS