Adjustable Delay Buffer Allocation under Useful Clock Skew Scheduling

Abstract

This paper proposes a graph-based algorithm for solving the adjustable delay buffer (ADB) allocation problem optimally under useful clock skew scheduling. Our algorithm supports additional features: extending the optimality to the allocation of ADBs with quantized delay values, extending the optimality to the allocation of ADBs with delay upper bound, and extending to the consideration of the delay variability of clock buffers. In addition, we propose two acceleration techniques for speeding up the computation. The first one is speeding up the graph traversal of our optimal solver without sacrificing the optimality while the second one, supplementing our algorithm, is to deal with the extremely large designs at the expense of the allocation quality. The experiments with benchmark circuits show that our algorithm reduces the number of ADBs by 23.3% on average over the results produced by the conventional ADB allocation under useful clock skew scheduling and reduces the number of ADBs by 86.3% on average over that produced by the previous optimal ADB allocation under bounded clock skew constraint. In addition, our optimal algorithm runs 30-460 times faster than the prior work.