Operation chaining asynchronous pipelined circuits

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.

REFERENCES

• 1: Mihai Budiu , Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein, Spatial computation, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 2: En-Shou Chang , Daniel D. Gajski , Sanjiv Narayan, An optimal clock period selection method based on slack minimization criteria, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.3, p.352-370, July 1996 [doi>10.1145/234860.234864]
• 3: Tiberiu Chelcea , Steven M. Nowick, Resynthesis and peephole transformations for the optimization of large-scale asynchronous systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514023]
• 4: Stephen B. Furber , Paul Day, Four-phase micropipeline latch control circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.2, p.247-253, June 1996 [doi>10.1109/92.502196]
• 5: Girish Venkataramani , Seth C. Goldstein, Leveraging protocol knowledge in slack matching, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233650]
• 6: Sangyun Kim , Peter A. Beerel, Pipeline optimization for asynchronous circuits: complexity analysis and an efficient optimal algorithm, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 7: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: Naresh Maheshwari , Sachin S. Sapatnekar, Minimum area retiming with equivalent initial states, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.216-219, November 09-13, 1997, San Jose, California, United States
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: Christian D. Nielsen , Michael Kishinevsky, Performance analysis based on timing simulation, Proceedings of the 31st annual conference on Design automation, p.70-76, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196281]
• 11: Rajeev K. Ranjan , Vigyan Singhal , Fabio Somenzi , Robert K. Brayton, On the optimization power of retiming and resynthesis transformations, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.402-407, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289061]
• 12: G. Venkataramani, M. Budiu, et al. C to asynchronous dataflow circuits: An end-to-end toolflow. In IWLS, June 2004.
• 13: Girish Venkataramani , Mihai Budiu , Tiberiu Chelcea , Seth C. Goldstein, Global critical path: a tool for system-level timing analysis, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278675]
• 14: Ted Eugene Williams, Self-timed rings and their application to division, Stanford University, Stanford, CA, 1992
• 15: Aiguo Xie , Sangyun Kim , Peter A. Beerel, Bounding Average Time Separations of Events in Stochastic Timed Petri Nets with Choice, Proceedings of the 5th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.94, April 19-21, 1999
• 16: Ying Yi , Ioannis Nousias , Mark Milward , Sami Khawam , Tughrul Arslan , Iain Lindsay, System-level scheduling on instruction cell based reconfigurable systems, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany