Performance Analysis in CoDe-X Partitioning for Structural Programmable Accelerators

ABSTRACT

The paper presents the performance analysis process within the parallelizing compilation environment CoDe-X for simultaneous programming of Xputer-based accelerators and their host. The paper introduces briefly its hardware/software co-design strategies at two levels of partitioning. CoDe-X performs both, at first level a profiling-driven host/accelerator partitioning for performance optimization, and at second level a resource-driven sequential/structural partitioning of the accelerator source code to optimize the utilization of its reconfigurable resources. The analysis of candidate (task) performances in CoDe-X has to be done for both, a procedural (sequential) programmable host processor, and the structural programmable data-driven accelerator processor. In complete application time estimation data-dependencies for parallel task execution (host/accelerators) are considered. To stress the significance of this application development methodology, the paper first gives an introduction to the target hardware platform.

REFERENCES

• 1: [1] R. Hartenstein, (key note): Custom Computing Machines- An Overview; Workshop on Design Methodologies for Microelectronics, Smolenice Castle, Slovakia, Sept. 1995.
• 2: Reiner W. Hartenstein , Jürgen Becker , Rainer Kress, Custom Computing Machines vs. Hardware/Software Codesign: From a globalized point of view, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.65-76, September 23-25, 1996
• 3: [3] D. Monjau: Proc. GI/ITG Workshop Custom Computing, Dagstuhl, Germany, June 1996.
• 4: [4] D. Buell, K. Pocek: Proc. IEEE Workshop on FPGAs for Custom Computing Machines, FCCM'94, Napa, CA, April 1993.
• 5: [5] see [4], but 1994, 1995, and 1996.
• 6: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 7: Rajesh K. Gupta , Claudionor N. Coelho, Jr. , Giovanni De Micheli, Program Implementation Schemes for Hardware-Software Systems, Computer, v.27 n.1, p.48-55, January 1994 [doi>10.1109/2.248880]
• 8: [8] R. Hartenstein, A. Hirschbiel, M. Weber: A Novel Paradigm of Parallel Computation and its Use to Implement Simple High Performance Hardware; InfoJapan'90 Int'l. Conf. memorizing the 30th Anniv. of Computer Society Japan, Tokyo, Japan, 1990.
• 9: Reiner W. Hartenstein , Rainer Kress, A datapath synthesis system for the reconfigurable datapath architecture, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.77-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224959]
• 10: [10] R. Kress: A fast reconfigurable ALU for Xputers; Ph.D. dissertation, Kaiserslautem University 1996.
• 11: [11] R. Hartenstein: FAQ and FQA about Xputers; see http:// xputers.informatik.uni-kl.de/
• 12: B. K. Fawcett , J. Watson, Reconfigurable Processing With Field Programmable Gate Arrays, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.293, August 19-23, 1996
• 13: R. W. Hartenstein , A. Hirschbiel , M. Weber, A flexible architecture for image processing, Microprocessing and Microprogramming, v.21 n.1-5, p.65-71, Aug. 1987 [doi>10.1016/0165-6074(87)90019-6]
• 14: Reiner W. Hartenstein , Jürgen Becker, A Two-level Co-Design Framework for Xputer-based data-driven reconfigurable Accelerators, Proceedings of the 30th Hawaii International Conference on System Sciences: Advanced Technology Track, p.125, January 03-06, 1997
• 15: [15] R. Hartenstein, J. Becker et al.: A Reconfigurable Machine for Applications in Image and Video Commpression; Conf. on Compression Techniques & Standards for Image & Video Compression, Amsterdam, Netherlands, 1995.
• 16: Reiner W. Hartenstein , Jürgen Becker , Michael Herz , Rainer Kress , Ulrich Nageldinger, A Partitioning Programming Environment for a Novel Parallel Architecture, Proceedings of the 10th International Parallel Processing Symposium, p.544-548, April 15-19, 1996
• 17: [17] K. Schmidt: A Program Partitioning, Restructuring, and Mapping Method for Xputers; Ph.D. Thesis, Kaiserslautern 1994.
• 18: Andreas Ast , Jürgen Becker , Reiner W. Hartenstein , Rainer Kress , Helmut Reinig , Karin Schmidt, Data-Procedural Languages for FPL-based Machines, Proceedings of the 4th International Workshop on Field-Programmable Logic and Applications: Field-Programmable Logic, Architectures, Synthesis and Applications, p.183-195, September 07-09, 1994
• 19: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 20: [20] R. Hartenstein, J. Becker et al.: A Parallelizing Programming Environment for Embedded Xputer-based Accelerators; High Performance Computing Symp.'96, Ottawa, Canada, June 1996.
• 21: Reiner W. Hartenstein , Juergen Becker , Rainer Kress, Two-level Partitioning of Image Processing Algorithms for the Parallel Map-oriented Machine, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.77, March 18-20, 1996
• 22: [22] U. Nageldinger: Design and Implementation of a menu-driven Run Time System for the MoM-3; Master Thesis, University of Kaiserslautern, 1995.
• 23: [23] J. Stumpe: Comparison and Reorganizing the storage schemes of variable arrays in the Xputer Multi Tasking Mode; Project Thesis, University of Kaiserslautern, 1996.
• 24: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 25: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.456-461, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217570]
• 26: [26] S. Malik, W. Wolf, A. Wolfe, Y.-T. Li, T-Y. Yen: Performance Analysis of Embedded Systems: NATO/ASI, Tremezzo, Italy, 1995, Kluwer Acad. Publishers, 1995.
• 27: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
• 28: Computer Staff, Efficient program tracing, Computer, v.26 n.5, p.52-61, May 1993 [doi>10.1109/2.211900]
• 29: [29] KUKLFLAP program execution time estimator; Gesellschaft f. Mathematik u. Datenverarbeitung, Sankt Augustin, Germany 1995: http://alcatraz.gmd.de:9422/castle/doc/kukflap.html.
• 30: [30] P. G. Plöger, H. T. Vierhaus: Retargierbare Laufzeitabschaetzugen; to be publ. in Proc. of Workshop Entwurf Integrierter Systeme (E.I.S.), Univ. Hamburg, 8.-9, April, 1997.
• 31: Raul Camposano , Jörg Wilberg, Embedded system design, Design Automation for Embedded Systems, v.1 n.1-2, p.5-50, Jan. 1996 [doi>10.1007/BF00134682]
• 32: [32] J. Wilberg, R. Camposano, P. G. Plöger, M. Langevin, T. Vierhaus: Cosynthesis in CASTLE: in G. Saucier, A. Mignotte: Novel approaches in Logic and Architecture Synthesis, pp. 355-366, Chapman & Hall, London, 1995.
• 33: M. Wolfe , C. W. Tseng, The Power Test for Data Dependence, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.591-601, September 1992 [doi>10.1109/71.159042]
• 34: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001

INDEX TERMS

Keywords:
design space exploration, performance estimation, structural programmable co-processors