Title :
Slack matching asynchronous designs
Author :
Beerel, Peter A. ; Lines, Andrew ; Davies, Mike ; Kim, Nam-Hoon
Author_Institution :
Southern California Univ., Los Angeles, CA
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;
Conference_Titel :
Asynchronous Circuits and Systems, 2006. 12th IEEE International Symposium on
Conference_Location :
Grenoble
Print_ISBN :
0-7695-2498-2
DOI :
10.1109/ASYNC.2006.26