Data communication estimation and reduction for reconfigurable systems

ABSTRACT

Widespread adoption of reconfigurable devices requires system level synthesis techniques to take an application written in a high level language and map it to the reconfigurable device. This paper describes methods for synthesizing the internal representation of a compiler into a hardware description language in order to program reconfigurable hardware devices. We demonstrate the usefulness of static single assignment (SSA) in reducing the amount of data communication in the hardware. However, the placement of Φ-nodes by current SSA algorithms is not optimal in terms of minimizing data communication. We propose a new algorithm which optimally places Φ-nodes, further decreasing area and communication latency. Our algorithm reduces the data communication (measured as total edge weight in a control data flow graph) by as much as 20% for some applications as compared to the best-known SSA algorithm - the pruned algorithm. We also describe future modifications to our model that should increase the effectiveness of our methods.

REFERENCES

• 1: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 2: Preston Briggs , Keith D. Cooper , Timothy J. Harvey , L. Taylor Simpson, Practical improvements to the construction and destruction of static single assignment form, Software—Practice & Experience, v.28 n.8, p.859-881, July 10, 1998 [doi>10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8]
• 3: 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]
• 4: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 5: M. Hall et al., "DEFACTO: A Design Environment for Adaptive Computing Technology", Proceedings of the 6th Reconfigurable Architectures Workshop, Springer-Verlag, 1999.
• 6: Ryan Charles Kastner , Majid Sarrafzadeh, Synthesis techniques and optimizations for reconfigurable systems, 2002
• 7: R. Cytron et al., "Efficiently Computing Φ-nodes On-the-Fly", ACM Transactions on Programming Languages and Systems, October 1991.
• 8: K. Kennedy. "A Survey of Data Flow Analysis Techniques", Program Flow Analysis: Theory and Applications, Prentice-Hall, 1981.
• 9: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 10: 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
• 11: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 12: M. D. Smith and G. Holloway, An Introduction to Machine SUIF and its Portable Libraries for Analysis and Optimization, Division of Engineering and Applied Sciences, Harvard University,
• 13: P. Briggs, T. Harvey and L. Simpson, Static Single Assignment Construction, Implementation documentation, 1996.
• 14: A. Smith et al., "PRISM II Compiler and Architecture", Proceedings of IEEE Workshop on FPGA-based Custom Computing Machines, April, 1993.
• 15: Jonathan Babb , Martin Rinard , Csaba Andras Moritz , Walter Lee , Matthew Frank , Rajeev Barua , Saman Amarasinghe, Parallelizing Applications into Silicon, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.70, April 21-23, 1999
• 16: Justin L. Tripp , Preston A. Jackson , Brad Hutchings, Sea Cucumber: A Synthesizing Compiler for FPGAs, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.875-885, September 02-04, 2002
• 17: Mihai Budiu , Seth Copen Goldstein, Compiling Application-Specific Hardware, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.853-863, September 02-04, 2002
• 18: Robert Rinker , Margaret Carter , Amitkumar Patel , Monica Chawathe , Charlie Ross , Jeffrey Hammes , Walid A. Najjar , Wim Böhm, An automated process for compiling dataflow graphs into reconfigurable hardware, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.130-139, Feb. 2001 [doi>10.1109/92.920828]