Challenges in exploitation of loop parallelism in embedded applications

ABSTRACT

Embedded processors have been increasingly exploiting hardware parallelism. Vector units, multiple processors or cores, hyper-threading, special-purpose accelerators such as DSPs or cryptographic engines, or a combination of the above have appeared in a number of processors. They serve to address the increasing performance requirements of modern embedded applications. How this hardware parallelism can be exploited by applications is directly related to the amount of parallelism inherent in a target application. In this paper we evaluate the performance potential of different types of parallelism, viz., true thread-level parallelism, speculative thread-level parallelism and vector parallelism, when executing loops. Applications from the industry-standard EEMBC 1.1, EEMBC 2.0 and the MiBench embedded benchmark suites are analyzed using the Intel C compiler. The results show what can be achieved today, provide upper bounds on the performance potential of different types of thread parallelism, and point out a number of issues that need to be addressed to improve performance. The latter include parallelization of libraries such as libc and design of parallel algorithms to allow maximal exploitation of parallelism. The results also point to the need for developing new benchmark suites more suitable to parallel compilation and execution.

REFERENCES

• 1: S. Prakash and A. C. Parker. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. Journal of Parallel and Distributed Computing, 16:338--351, 1992.
• 2: Allan Rae , Sri Parameswaran, Application-specific heterogeneous multiprocessor synthesis using differential-evolution, Proceedings of the 11th international symposium on System synthesis, p.83-88, December 02-04, 1998, Hsinchu, Taiwan, China
• 3: Damien Lyonnard , Sungjoo Yoo , Amer Baghdadi , Ahmed A. Jerraya, Automatic generation of application-specific architectures for heterogeneous multiprocessor system-on-chip, Proceedings of the 38th conference on Design automation, p.518-523, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379015]
• 4: Wayne Wolf, The future of multiprocessor systems-on-chips, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996753]
• 5: Fei Sun , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Synthesis of Application-Specific Heterogeneous Multiprocessor Architectures Using Extensible Processors, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.551-556, January 03-07, 2005 [doi>10.1109/ICVD.2005.155]
• 6: J. T. J. Van Eijndhoven , E. J. D. Pol, TriMedia CPU64 Architecture, Proceedings of the 1999 IEEE International Conference on Computer Design, p.586, October 10-13, 1999
• 7: ARM11 Family. http://www.arm.com/products/CPUs/families/ARM11Family.html.
• 8: Intel® IXP2850 Network Processor. http://www.intel.com/design/network/products/npfamily/ixp2850.htm.
• 9: OMAP2420. http://focus.ti.com/general/docs/wtbu/wtbuproductcontent.tsp?templateId=6123&navigationId=11990&contentId=4671.
• 10: Intel® Multi-Core Processor Architecture Development. http://www.intel.com/cd/ids/developer/asmo-na/eng/201969.htm?page=6.
• 11: Dual-Core Intel® Xeon® Processor 7000 sequence Platform Brief. ftp://download.intel.com/products/processor/xeon/dc7kplatbrief.pdf.
• 12: The Cell Processor. http://arstechnica.com/articles/paedia/cpu/cell-1.ars.
• 13: RAMP: Research Accelerator for Multiple Processors. http://ramp.eecs.berkeley.edu/.
• 14: Manoj Franklin , Gurindar S. Sohi, The expandable split window paradigm for exploiting fine-grain parallelsim, Proceedings of the 19th annual international symposium on Computer architecture, p.58-67, May 19-21, 1992, Queensland, Australia
• 15: M. Flynn. Very high-speed computing systems. Proceedings of the IEEE, 54(12):1901--1909, December 1966.
• 16: S. Lundstrom and G. Barnes. A controllable MIMD architectures. In Proceedings of the 1980 International Conference on Parallel Processing, St. Charles, IL, August 1980.
• 17: U. Banerjee, R. Eigenmann, A. Nicolau, and D. Padua. Automatic program parallelization. Proceedings of the IEEE, 81(2):211--243, February 1993.
• 18: EEMBC. http://www.eembc.org/.
• 19: MiBench Version 1.0. http://www.eecs.umich.edu/mibench/.
• 20: OpenMP Specification, version 2.5. http://www.openmp.org/drupal/mp-documents/spec25.pdf.
• 21: C. Polychronopoulos. Loop coalescing: A compiler transformation for parallel machines In Proceedings of the 1987 International Conference on Parallel Processing, pages 235--242, August 1987.
• 22: R. S. Bird, Notes on recursion elimination, Communications of the ACM, v.20 n.6, p.434-439, June 1977 [doi>10.1145/359605.359630]
• 23: Yanhong A. Liu , Scott D. Stoller, From recursion to iteration: what are the optimizations?, Proceedings of the 2000 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, p.73-82, January 22-23, 2000, Boston, Massachusetts, United States
• 24: GNU C library. http://www.gnu.org/software/libc/.
• 25: Richard Gerber, The Software Optimization Cookbook, Intel Press, 2002
• 26: A. Kejariwal and A. Nicolau. Reading list of performance analysis, speculative execution. http://www.ics.uci.edu/~akejariw/SpeculativeExecutionReadingList.pdf.
• 27: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 28: Gang Ren , Peng Wu , David Padua, An Empirical Study On the Vectorization of Multimedia Applications for Multimedia Extensions, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.89.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.94]
• 29: Franz Franchetti , Markus Püschel, Short Vector Code Generation for the Discrete Fourier Transform, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.58.2, April 22-26, 2003
• 30: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 31: Sriram Vajapeyam , P. J. Joseph , Tulika Mitra, Dynamic vectorization: a mechanism for exploiting far-flung ILP in ordinary programs, Proceedings of the 26th annual international symposium on Computer architecture, p.16-27, May 01-04, 1999, Atlanta, Georgia, United States
• 32: SPEC: Standard Performance Evaluation Corporation. http://www.spec.org/.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages; Methodologies (e.g., object-oriented, structured)
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Measurement, Performance

Keywords:
libraries, multi-cores, multithreading, parallel loops, programming models, thread-level speculation, vectorization