Efficient Buffer Allocation for Asynchronous Linear Pipelines by Design Space Localization

Abstract

Asynchronous circuit design is very attractive as a high performance design method since it can achieve average-case delay. However, it is hard to make use of such an advantage in a pipelined architecture due to the blocking/starvation effects between stages. In most of current solutions, buffers are allocated to reduce the blocking/starvation effects but it is difficult to find a distribution of buffers over an asynchronous linear pipeline(ALP) that is optimal in terms of ‘time*area’ cost.

In this paper, we show that the design space of the buffer allocation on an ALP is non-convex by introducing a term, called additional cycle time reduction (ACTR) that can separate the effect of a simultaneous buffer insertion from an individual buffer insertion. Furthermore, we propose a hybrid algorithm such that hill-climbing search is first performed during the early stage of buffer allocation while more sophisticated simulated annealing is applied for the later stage. Such a hybrid approach makes use of the characteristics of buffer allocation design space. Experiments and comparison with conventional methods based on simulated annealing are presented to show the efficiency of the proposed algorithm.