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

Date

2006

Authors

Peter A Beerel, Andrew Lines, Mike Davies, Nam-Hoon Kim

Conference

12th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC'06)

Pages

11 pp.-194

Publisher

IEEE