A Caltech Library Service

Throughput Optimization of Quasi Delay Insensitive Circuits via Slack Matching


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.


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):
  • Martin, Alain J.
Thesis Committee:
  • Martin, Alain J. (chair)
  • DeHon, Andre
  • Umans, Christopher M.
  • Chandy, K. Mani
Defense Date:5 December 2007
Record Number:CaltechETD:etd-05262008-234258
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2118
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.


Repository Staff Only: item control page