@inproceedings{venkataramani-iccad07,
author = {Venkataramani, Girish and Goldstein, Seth Copen},
title = {Operation Chaining Asynchronous Pipelined Circuits},
booktitle = {ICCAD},
abstract = {We define operation chaining (op-chaining) as an
optimization problem to determine the optimal pipeline depth for
balancing performance against energy demands in pipelined
asynchronous designs. Since there are no clock period
requirements, asynchronous pipeline stages can have non-uniform
latencies. We exploit this fact to coalesce several stages
together thereby saving power and area due to the elimination of
control-path resources from the pipeline. The trade-off is
potentially reduced pipeline parallelism. In this paper, we
formally define this optimization as a graph covering problem,
which finds sub-graphs that will be synthesized as an opchained
pipeline stage. We then define the solution space for provably
correct solutions and present an algorithm to efficiently search
this space. The search technique partitions the graph based on
post-dominator relationships to find sub-graphs that are
potential op-chain candidates. We use knowledge of the Global
Critical Path (GCP) [13] to evaluate the performance impact of
accepting a candidate sub-graph and formulate a heuristic cost
function to model this trade-off. The algorithm has a
quadratic-time complexity in the size of the dataflow graph. We
have implemented this algorithm within an automated asynchronous
synthesis toolchain [12]. Experimental evidence from applying the
algorithm on several media processing kernels reveals that the
average energy-delay and energy-delay-area products improve by
about 1.4x and 1.8x respectively, with a maximum improvement of
5x and 18x.},
month = {Nov},
year = {2007},
url = {http://www.cs.cmu.edu/~seth/papers/venkataramani-iccad07.pdf},
keywords = {Asychronous Circuits, CAD, Global Critical Path},
}