Leveraging protocol knowledge in slack matching

ABSTRACT

Stalls, due to mis-matches in communication rates, are a major performance obstacle in pipelined circuits. If the rate of data production is faster than the rate of consumption, the resulting design performs slower than when the communication rate is matched. This can be remedied by inserting pipeline buffers (to temporarily hold data), allowing the producer to proceed if the consumer is not ready to accept data. The problem of deciding which channels need these buffers (and how many) for an arbitrary communication profile is called the slack matching problem; the optimal solution to this problem has been shown to be NP-complete.

In this paper, we present a heuristic that uses knowledge of the communication protocol to explicitly model these bottlenecks, and an iterative algorithm to progressively remove these bottlenecks by inserting buffers. We apply this algorithm to asynchronous circuits, and show that it naturally handles large designs with arbitrarily cyclic and acyclic topologies, which exhibit various types of control choice. The heuristic is efficient, achieving linear time complexity in practice, and produces solutions that (a) achieve up to 60% performance speedup on large media processing kernels, and (b) can either be verified to be optimal, or the approximation margin can be bounded.

REFERENCES

• 1: Peter A. Beerel , Nam-Hoon Kim , Andrew Lines , Mike Davies, Slack Matching Asynchronous Designs, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.184, March 13-15, 2006 [doi>10.1109/ASYNC.2006.26]
• 2: E. Bozorgzadeh , S. Ghiasi , A. Takahashi , M. Sarrafzadeh, Optimal integer delay budgeting on directed acyclic graphs, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776064]
• 3: Steven Morgan Burns, Performance analysis and optimization of asynchronous circuits, California Institute of Technology, Pasadena, CA, 1992
• 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: 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
• 6: Ruibing Lu , Cheng-Kok Koh, Performance Optimization of Latency Insensitive Systems Through Buffer Queue Sizing of Communication Channels, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.227, November 09-13, 2003 [doi>10.1109/ICCAD.2003.113]
• 7: 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]
• 8: Piyush Prakash , Alain J. Martin, Slack Matching Quasi Delay-Insensitive Circuits, Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems, p.195, March 13-15, 2006 [doi>10.1109/ASYNC.2006.27]
• 9: I. E. Sutherland, Micropipelines, Communications of the ACM, v.32 n.6, p.720-738, June 1989 [doi>10.1145/63526.63532]
• 10: B. Taskin and I. Kourtev. Delay insertion method in clock skew scheduling. IEEE TCAD, 25--4:651--663, 2006.
• 11: G. Venkataramani, M. Budiu, et al. C to asynchronous dataflow circuits: An end-to-end toolflow. In IWLS, June 2004.
• 12: G. Venkataramani, T. Chelcea, et al. Modeling the global critical path in concurrent systems. Technical Report CMU-CS-06-144, Carnegie Mellon University, August 2006.
• 13: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance