MAPS: an integrated framework for MPSoC application parallelization

ABSTRACT

In the past few years, MPSoC has become the most popular solution for embedded computing. However, the challenge of programming MPSoCs also comes as the biggest side-effect of the solution. Especially, when designers have to face the legacy C code accumulated through the years, the tool support is mostly unsatisfactory. In this paper, we propose an integrated framework, MAPS, which aims at parallelizing C applications for MPSoC platforms. It extracts coarsegrained parallelism on a novel granularity level. A set of tools have been developed for the framework. We will introduce the major components and their functionalities. Two case studies will be given, which demonstrate the use of MAPS on two different kinds of applications. In both cases the proposed framework helps the programmer to extract parallelism efficiently.

REFERENCES

• 1: The OpenMP Specification for Parallel Programming. http://www.openmp.org.
• 2: Standard for Information Technology - Portable Operating System Interface (POSIX). Shell and utilities. IEEE Std 1003.1--2004, The Open Group Base Specifications Issue 6, section 2.9. IEEE and The Open Group.
• 3: Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, ACM SIGPLAN Notices, v.42 n.6, June 2007
• 4: Lothar Thiele , Iuliana Bacivarov , Wolfgang Haid , Kai Huang, Mapping Applications to Tiled Multiprocessor Embedded Systems, Proceedings of the Seventh International Conference on Application of Concurrency to System Design, p.29-40, July 10-13, 2007 [doi>10.1109/ACSD.2007.53]
• 5: T. Wiangtong, P. Cheung, and W. Luk. Hardware/Software Codesign: a Systematic Approach Targeting Data-intensive Applications. IEEE Signal Processing Magazine, 22(3):14--22, 2005.
• 6: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 7: Embedded Software Stuck at C. http://www.eetimes.com/news/design/showArticle.jhtml?articleID=202102427.
• 8: M. Z. Urfianto, T. Isshiki, A. U. Khan, D. Li, and H. Kunieda. A Multiprocessor System-on-Chip Architecture with Enhanced Compiler Support and Efficient Interconnect. In IP-SOC 2006, Design and Reuse, S.A., 2006.
• 9: M. Z. Urfianto, T. Isshiki, A. U. Khan, D. Li, and H. Kunieda. A Multiprocessor SoC Architecture with Efficient Communication Infrastructure and Advanced Compiler Support for Easy Application Development. IEICE Trans. Fundamentals, Vol. E91-A, No.4, Apr. 2008.
• 10: T. Isshiki, M. Z. Urfianto, A. U. Khan, D. Li, and H. Kunieda. Tightly-Coupled-Thread Model: A New Design Framework for Multiprocessor System-on-Chips. In Design Automation Symposium (Japan), 2006.
• 11: U. Banerjee, R. Eigenmann, A. Nicolau, and D. A. Padua. Automatic Program Parallelization. Proceedings of the IEEE, 81(2):211--243, 1993.
• 12: Rainer Leupers, Code selection for media processors with SIMD instructions, Proceedings of the conference on Design, automation and test in Europe, p.4-8, March 27-30, 2000, Paris, France [doi>10.1145/343647.343679]
• 13: Mary H. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Detecting coarse-grain parallelism using an interprocedural parallelizing compiler, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224337]
• 14: S. Verdoolaege, H. Nikolov, and T. Stefanov. Improved Derivation of Process Networks. In ODES-4, 2006.
• 15: T. Harriss, R. Walke, B. Kienhuis, and E. Deprettere. Compilation from Matlab to Process Networks Realized in FPGA. In Design Automation of Embedded Systems, volume 7, 2002.
• 16: I. Karkowski , H. Corporaal, Design of heterogenous multi-processor embedded systems: applying functional pipelining, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.156, November 11-15, 1997
• 17: R. N. Weng and T. Wolf. Application Analysis and Resource Mapping for Heterogeneous Network Processor Architectures. In in Proc. of Third Workshop on Network Processors and Applications (NP-3), pages 103--119, Feb. 2004.
• 18: Guilherme Ottoni , Ram Rangan , Adam Stoler , David I. August, Automatic Thread Extraction with Decoupled Software Pipelining, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.105-118, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.13]
• 19: William Thies , Vikram Chandrasekhar , Saman Amarasinghe, A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.356-369, December 01-05, 2007 [doi>10.1109/MICRO.2007.7]
• 20: Matthew Bridges , Neil Vachharajani , Yun Zhang , Thomas Jablin , David August, Revisiting the Sequential Programming Model for Multi-Core, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.69-84, December 01-05, 2007 [doi>10.1109/MICRO.2007.35]
• 21: Eclipse C/C++ Development Tooling. http://www.eclipse,org/cdt.
• 22: R. Leupers, O. Wahlen, M. Hohenauer, T. Kogel, and P. Marwedel. An Executable Intermediate Representation for Retargetable Compilation and High-Level Code Optimization. In SAMOS, 2003.
• 23: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 24: Torsten Kempf , Kingshuk Karuri , Stefan Wallentowitz , Gerd Ascheid , Rainer Leupers , Heinrich Meyr, A SW performance estimation framework for early system-level-design using fine-grained instrumentation, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 25: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 26: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD 96, pages 468--473, Aug. 1996.
• 27: Independent JPEG Group, http://www.ijg.org/.
• 28: DSPStone. http://www.ert.rwthaachen.de/Projekte/Tools/DSPSTONE/dspstone.html.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design

Keywords:
MPSoC programming, embedded, parallelization, software