DocumentCode :
3279020
Title :
Slack matching asynchronous designs
Author :
Beerel, Peter A. ; Lines, Andrew ; Davies, Mike ; Kim, Nam-Hoon
Author_Institution :
Southern California Univ., Los Angeles, CA
fYear :
2006
fDate :
13-15 March 2006
Lastpage :
194
Abstract :
Slack matching is the problem of adding pipeline buffers to an asynchronous pipelined design in order to prevent stalls and improve performance. This paper addresses the problem of minimizing the cost of additional pipeline buffers needed to achieve a given performance target. An intuitive analysis is given that is then formalized using marked graph theory. This leads to a mixed integer linear programming (MILP) solution of the problem. Theory is then presented that identifies under what circumstances the MILP solution admits a polynomial time solution. For other circumstances, a polynomial-time approximate algorithm using linear programming is proposed. Experimental results on a large set of benchmark circuits demonstrate the computational feasibility and effectiveness of both approaches
Keywords :
asynchronous circuits; buffer circuits; circuit optimisation; graph theory; integer programming; linear programming; logic design; asynchronous pipelined design; marked graph theory; mixed integer linear programming; pipeline buffers; slack matching; Asynchronous circuits; Clustering algorithms; Costs; Graph theory; Linear approximation; Linear programming; Mixed integer linear programming; Optimization methods; Pipeline processing; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Asynchronous Circuits and Systems, 2006. 12th IEEE International Symposium on
Conference_Location :
Grenoble
ISSN :
1522-8681
Print_ISBN :
0-7695-2498-2
Type :
conf
DOI :
10.1109/ASYNC.2006.26
Filename :
1595702
Link To Document :
بازگشت