Classifying interprocess communication in process network representation of nested-loop programs

ABSTRACT

New embedded signal-processing architectures are emerging that are composed of loosely coupled heterogeneous components like CPUs or DSPs, specialized IP cores, reconfigurable units, or memories. We believe that these architectures should be programmed using the process network model of computation. To ease the mapping of applications, we are developing the Compaan compiler that automatically derives a process network (PN) description from an application written in Matlab or C. In this paper, we investigate a particular problem in nested loop programs, which is about classifying the interprocess communication in the PN representation of the nested loop program. The global memory arrays present in the code have to be replaced by a distributed communication structure used for communicating data between the network processes. We show that four types of communication exist, each exhibiting different requirements when realizing them in hardware or software. We first present two compile time tests that are based on integer linear programming to decide the type of the communication. In the second part of this paper, we present alternative classification techniques that have polynomial complexity. However, in some cases, those techniques do not give a definitive answer and the ILP tests have to be applied. All present tests are combined in a hybrid classification scheme that correctly classifies the interprocess communication. In only 5% of the cases to classify, we have to rely on integer linear programming while, in the remaining 95%, the alternative techniques presented in this paper are able to correctly classify each case. The hybrid classification scheme has become an important part of our Compaan compiler.

REFERENCES

• 1: Basten, T. and Hoogerbrugge, J. 2001. Efficient execution of process networks. In Communicating Process Architectures---2001, Proceedings. Bristol. 1--14.
• 2: Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
• 3: Davis, Jr, II, J., Hylands, C., Kienhuis, B., Lee, E. A., Liu, J., Liu, X., Muliadi, L., Neuendorffer, S., Tsay, J., Vogel, B., and Xiong, Y. 2001. Heterogeneous concurrent modeling and design in java. Tech. Rep. Memorandum UCB/ERL M01/12 (Mar.), University of California, Dept EECS, Berkeley, CA 94720.
• 4: De Greef, E., Catthoor, F., and De Man, H. 1977. Memory size reduction through storage order optimization for embedded parallel multimedia applications. In Parallel Processing and Multimedia. Geneva.
• 5: 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]
• 6: Feautrier, P. 1988. Parametric Integer Programming. In RAIRO Recherche Op?rationnelle, 22, 3, 243--268.
• 7: Kahn, G. 1974. The semantics of a simple language for parallel programming. In Proc. of the IFIP Congress 74. North-Holland, Amsterdam.
• 8: 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]
• 9: Bart Kienhuis , Ed F. Deprettere , Pieter van der Wolf , Kees A. Vissers, A Methodology to Design Programmable Embedded Systems - The Y-Chart Approach, Embedded Processor Design Challenges: Systems, Architectures, Modeling, and Simulation - SAMOS, p.18-37, January 2002
• 10: Vincent Lefebvre , Paul Feautrier, Automatic storage management for parallel programs, Parallel Computing, v.24 n.3-4, p.649-671, May, 1998 [doi>10.1016/S0167-8191(98)00029-5]
• 11: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 12: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996
• 13: PicoChip. 2000. http://www.picochip.com.
• 14: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 15: Fabien Quilleré , Sanjay Rajopadhye, Optimizing memory usage in the polyhedral model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.773-815, Sept. 2000 [doi>10.1145/365151.365152]
• 16: Rijpkema, E. 2002. Modeling task level parallelism in piece-wise regular programs. PhD thesis, Leiden Institute of Advanced Computer Science, Leiden Univerity, The Netherlands.
• 17: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 18: Todor Stefanov , Ed Deprettere, Deriving process networks from weakly dynamic applications in system-level design, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944673]
• 19: Todor Stefanov , Claudiu Zissulescu , Alexandru Turjan , Bart Kienhuis , Ed Deprettere, System Design Using Kahn Process Networks: The Compaan/Laura Approach, Proceedings of the conference on Design, automation and test in Europe, p.10340, February 16-20, 2004
• 20: Stravers, P. and Hoogerbrugge, J. 2001. Homogeneous multiprocessoring and the future of silicon design paradigms. In Proceedings of the Int. Symposium on VLSI Technology, Systems, and Applications.
• 21: Jürgen Teich , Lothar Thiele, Partitioning of processor arrays: a piecewise regular approach, Integration, the VLSI Journal, v.14 n.3, p.297-332, Feb. 1993 [doi>10.1016/0167-9260(93)90013-3]
• 22: Turjan, A. and Kienhuis, B. 2003. Storage management in process networks using the lexicographically maximal preimage. In Proceedings of the IEEE 14th Int. Conf. on Application-specific Systems, Architectures and Processors (ASAP'03). The Hague.
• 23: Alexandru Turjan , Bart Kienhuis , Ed Deprettere, A Compile Time Based Approach for Solving Out-of-Order Communication in Kahn Process Networks, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.17, July 17-19, 2002
• 24: 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]
• 25: Doran Wilde , Sanjay V. Rajopadhye, Memory Reuse Analysis in the Polyhedral Model, Proceedings of the Second International Euro-Par Conference on Parallel Processing, p.389-397, August 26-29, 1996
• 26: Xilinx. 2000. http://www.xilinx.com.
• 27: Zissulescu, C., Stefanov, T., Kienhuis, B., and Deprettere, E. 2003. LAURA: Leiden architecture research and exploration tool. In Proc. 13th Int. Conference on Field Programmable Logic and Applications (FPL'03).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Keywords:
Static analysis, hybrid classification approach, integer linear programming, matrix manipulations