Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Kahn Process Networks is an appealing model of computation for programming and mapping applications onto multi-processor platforms. Autonomous processes communicate through unbounded FIFO channels in absence of a global scheduler. We derive Kahn process networks from sequential applications using the pn compiler, but the derived networks do not necessarily meet the performance requirements. Process partitioning transformations can achieve a more balanced network improving the performance results significantly. There are a number of process partitioning transformations that can be used, but no hints are given to the designer which transformation should be applied to minimize, for example, the execution time. Therefore, we investigate a compile-time approach for selecting the best transformation candidate and show results on a Xilinx Virtex 2 FPGA and the Cell BE processor.

REFERENCES

• 1: 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 Annual Design Automation Conference, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 2: P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20, 1991.
• 3: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 4: E. Lee et al. PtolemyII: Heterogeneous Concurrent Modeling and Design in Java. Technical report, University of California at Berkeley, 1999. UCB/ERL M99/40.
• 5: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 6: Dmitry Nadezhkin , Sjoerd Meijer , Todor Stefanov , Ed Deprettere, Realizing FIFO Communication When Mapping Kahn Process Networks onto the Cell, Proceedings of the 9th International Workshop on Embedded Computer Systems: Architectures, Modeling, and Simulation, July 20-23, 2009, Samos, Greece [doi>10.1007/978-3-642-03138-0_34]
• 7: Hristo Nikolov , Todor Stefanov , Ed Deprettere, Multi-processor system design with ESPAM, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176306]
• 8: H. Nikolov, T. Stefanov, and E. Deprettere. Systematic and automated multiprocessor system design, programming, and implementation. IEEE Transactions on Computer--Aided Design of Integrated Circuits and Systems, 27(3):542--555, 2008.
• 9: H. Nikolov , M. Thompson , T. Stefanov , A. Pimentel , S. Polstra , R. Bose , C. Zissulescu , E. Deprettere, Daedalus: toward composable multimedia MP-SoC design, Proceedings of the 45th annual Design Automation Conference, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391615]
• 10: Keshab K. Parhi , David G. Messerschmitt, Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding, IEEE Transactions on Computers, v.40 n.2, p.178-195, February 1991 [doi>10.1109/12.73588]
• 11: Sundararajan Sriram , Shuvra S. Bhattacharyya, Embedded Multiprocessors: Scheduling and Synchronization, Marcel Dekker, Inc., New York, NY, 2000
• 12: 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]
• 13: Jürgen Teich , Lothar Thiele, Exact Partitioning of Affine Dependence Algorithms, Embedded Processor Design Challenges: Systems, Architectures, Modeling, and Simulation - SAMOS, p.135-153, January 2002
• 14: A. Turjan. Compiling nested loop programs to process networks, 2007. PhD thesis, Leiden University, The Netherlands.
• 15: Sven Verdoolaege , Hristo Nikolov , Todor Stefanov, pn: a tool for improved derivation of process networks, EURASIP Journal on Embedded Systems, v.2007 n.1, p.19-19, January 2007 [doi>10.1155/2007/75947]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design, Performance

Keywords:
Kahn process networks, programming of MPSoC, transformations