Citation
Prakash, Piyush (2008) Throughput Optimization of Quasi Delay Insensitive Circuits via Slack Matching. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/9HMY-RR92. https://resolver.caltech.edu/CaltechETD:etd-05262008-234258
Abstract
Though the logical correctness of an asynchronous circuit is independent of implementation delays, the cycle time of an asynchronous circuit is of great importance to the designer. Oftentimes, the insertion of buffers to such circuits reduces the cycle time of the circuit without affecting the logical correctness of the circuit. This optimization is called slack matching. In this thesis the slack matching problem is formulated. I show that this problem is NP-complete via a reduction from subset sum. I describe two methods for expressing slack matching as a mixed integer linear program(MILP). The first method is applicable to any QDI circuit, while the second method produces a smaller MILP for circuits comprised solely of half buffers. These two formulations of slack matching were applied to the design of a fetch loop in an asynchronous micro-controller. Slack matching reduced the cycle time of the circuit by a factor of 3. For a circuit composed of 14 byte wide processes and a 8k instruction memory, 30s were required to generate the first MILP. It was solved in 2s. When the memory is modeled as a pipeline of half buffers, the second MILP could be formulated in 0.1s and solved in 0.6s. This MILP had half the number of integer variables as the first formulation.
Item Type: | Thesis (Dissertation (Ph.D.)) |
---|---|
Subject Keywords: | asynchronous; cycle time; NP-complete; quasi delay insensitive; slack matching; subset sum; VLSI |
Degree Grantor: | California Institute of Technology |
Division: | Engineering and Applied Science |
Major Option: | Computer Science |
Thesis Availability: | Public (worldwide access) |
Research Advisor(s): |
|
Thesis Committee: |
|
Defense Date: | 5 December 2007 |
Record Number: | CaltechETD:etd-05262008-234258 |
Persistent URL: | https://resolver.caltech.edu/CaltechETD:etd-05262008-234258 |
DOI: | 10.7907/9HMY-RR92 |
Default Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. |
ID Code: | 2118 |
Collection: | CaltechTHESIS |
Deposited By: | Imported from ETD-db |
Deposited On: | 02 Jun 2008 |
Last Modified: | 29 Jan 2020 19:59 |
Thesis Files
|
PDF
- Final Version
See Usage Policy. 917kB |
Repository Staff Only: item control page