Interactive presentation: A process splitting transformation for Kahn process networks

ABSTRACT

In this paper we present a process splitting transformation for Kahn process networks. Running applications written in this parallel program specification on a multiprocessor architecture does not guarantee that the runtime requirements are met. Therefore, it may be necessary to further analyze and optimize Kahn process networks. In this paper, we will present a four-step transformation that results in a functionally equivalent process network, but with a changed and optimized network structure. The class of networks that can be handled is not restricted to static networks. The novelty of this approach is that it can also handle processes with dynamic program statements. We will illustrate the transformation prototyped in GCC for a JPEG decoder, showing a 21% performance improvements.

REFERENCES

• 1: Martin Alt , Uwe Aßmann , Hans van Someren, Cosy Compiler Phase Embedding with the CoSy Compiler Model, Proceedings of the 5th International Conference on Compiler Construction, p.278-293, April 07-09, 1994
• 2: E. A. de Kock, Multiprocessor mapping of process networks: a JPEG decoding case study, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581216]
• 3: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 4: P. Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22(3):243--268, 1988.
• 5: G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information processing, pages 471--475, Stockholm, Sweden, Aug 1974. North Holland, Amsterdam.
• 6: Bart Kienhuis , Edwin Rijpkema , Ed Deprettere, Compaan: deriving process networks from Matlab for embedded signal processing architectures, Proceedings of the eighth international workshop on Hardware/software codesign, p.13-17, May 2000, San Diego, California, United States [doi>10.1145/334012.334015]
• 7: D. Pham et al. The design and implementation of a first-generation cell processor. In In ISSCC Digest of Technical Papers, pages p. 184--5, 2005.
• 8: http://y-api.sourceforge.net/.
• 9: Edwin Rijpkema. Modeling Task Level Parallelism in Piece-wise Regular Programs, 2002. PhD thesis, Leiden University, The Netherlands.
• 10: Todor Stefanov , Bart Kienhuis , Ed Deprettere, Algorithmic transformation techniques for efficient exploration of alternative application instances, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774792]
• 11: Paul Stravers and Jan Hoogerbrugge. Homogeneous multiprocessing and the future of silicon design paradigms. In In Prce. International Symposium on VLSI Technology, Systems, and Applications (VLSI-TSA 2001), April 2001.
• 12: Alexandru Turjan , Bart Kienhuis , Ed Deprettere, Translating affine nested-loop programs to process networks, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023864]
• 13: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: Claudiu Zissulescu, Bart Kienhuis, and Ed F. Deprettere. Increasing pipelined ip core utilization in process networks using exploration. In FPL, pages 690--699, 2004.