Diastolic arrays: throughput-driven reconfigurable computing

ABSTRACT

Diastolic arrays are arrays of processing elements that communicate exclusively through First-In First-Out (FIFO) queues. FIFO virtualization units enable relaxed timing of data transfers, and include hardware support to guarantee bandwidth and buffer space for all data transfers, which may follow composite paths through the network. We show that the architecture of diastolic arrays enables efficient synthesis from high-level specifications of communicating finite state machines so average throughput is maximized. Preliminary results are presented on an H.264 decoding benchmark.

REFERENCES

• 1: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 2: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 3: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 4: B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Technical Journal, vol. 49, pp. 291--307, February 1970.
• 5: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 6: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 7: K. Fleming, C.-C. Lin, N. Dave, Arvind, G. Raghavan, and J. Hicks, "H.264 Decoding: A Case Study in Late Design-Cycle Changes," in Proceedings of the Sixth MEMOCODE Conference, 2008.
• 8: M. Pellauer, M. Vijayaraghavan, M. Adler, J. Emer, and Arvind, "Quick Performance Models Quickly: Timing-Directed Simulation on FPGAs," in International Symposium on Performance Analysis of Systems and Software (ISPASS 2008), April 2008.
• 9: M. H. Cho, "Diastolic Arrays: Throughput-Driven Reconfigurable Computing," Master's thesis, Massachusetts Institute of Technology, May 2008. {Online}. Available: http://csg.csail.mit.edu/pubs/memos/Memo-504/memo504.pdf
• 10: H. T. Kung, Why Systolic Architectures?, Computer, v.15 n.1, p.37-46, January 1982 [doi>10.1109/MC.1982.1653825]
• 11: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 12: Thomas Gross , David R. O'Hallaron, iWarp: anatomy of a parallel computing system, MIT Press, Cambridge, MA, 1998
• 13: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 14: David Wentzlaff , Patrick Griffin , Henry Hoffmann , Liewei Bao , Bruce Edwards , Carl Ramey , Matthew Mattina , Chyi-Chang Miao , John F. Brown III , Anant Agarwal, On-Chip Interconnection Architecture of the Tile Processor, IEEE Micro, v.27 n.5, p.15-31, September 2007 [doi>10.1109/MM.2007.89]
• 15: Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Doug Burger , Stephen W. Keckler , Charles R. Moore, Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 16: Z. Yu, "High performance and energy efficient multi-core systems for DSP applications," Ph.D. dissertation, U. C. Davis, 2007.
• 17: Mike Butts, Synchronization through Communication in a Massively Parallel Processor Array, IEEE Micro, v.27 n.5, p.32-40, September 2007 [doi>10.1109/MM.2007.92]
• 18: Michael Butts , Anthony Mark Jones , Paul Wasson, A Structural Object Programming Model, Architecture, Chip and Tools for Reconfigurable Computing, Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.55-64, April 23-25, 2007 [doi>10.1109/FCCM.2007.14]
• 19: S. Murali, D. Atienz, L. Benini, and G. D. Micheli, "A Method for Routing Packets Across Multiple Paths in NoCs with In-Order Delivery and Fault-Tolerance Gaurantees," VLSI Design, vol. 2007, 2007.