CaltechTHESIS
  A Caltech Library Service

Throughput optimization of quasi delay insensitive circuits via slack matching

Citation

Prakash, Piyush (2008) Throughput optimization of quasi delay insensitive circuits via slack matching. Dissertation (Ph.D.), California Institute of Technology. http://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:Restricted to Caltech community only
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:http://resolver.caltech.edu/CaltechETD:etd-05262008-234258
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:26 Dec 2012 02:47

Thesis Files

[img] PDF (thesis.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

895Kb

Repository Staff Only: item control page