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

ABSTRACT

The emergence of inexpensive parallel computers powered by multicore chips combined with stagnating clock rates raises new challenges for software engineering. As future performance improvements will not come "for free" from increased clock rates, performance critical applications will need to be parallelized. However, little is known about the engineering principles for parallel general-purpose applications.

This paper presents an experience report with four diverse case studies on multicore software development for general-purpose applications. They were programmed in different languages and benchmarked on several multicore computers. Empirical findings include: 1) Multicore computers deliver: Real speedups are achievable, albeit with significant programming effort and speedups that are typically lower than the number of cores employed; 2) Massive refactoring of sequential programs is required, sometimes at several levels. Special tools for parallelization refactorings appear to be an important area of research; 3) Autotuning is indispensable, as manually tuning thread assignment, number of pipeline stages, size of data partitions and other parameters is difficult and error prone; 4) Architectures that encompass several parallel components are poorly understood. Tuneable architectural patterns with parallelism at several levels need to be discovered.

REFERENCES

• 1: Challenge benchmarks of the 9th DIMACS implementation challenge - shortest paths, 2006.
• 2: Agilent Technologies. MassHunter Metabolite ID software. http://www.chem.agilent.com/Scripts/PDS.asp?lPage=57806, 2008. last accessed January 17, 2008.
• 3: S. Akhter and J. Roberts. Multi-Core Programming. Intel Press, 2006.
• 4: Stuart L. Anderson, Random number generations generators on Vector supercomputers and other advanced architectures, SIAM Review, v.32 n.2, p.221-251, June 1990 [doi>10.1137/1032044]
• 5: K. Asanovic et al. The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley, December 18 2006.
• 6: Robit Chandra , Leonardo Dagum , Dave Kohr , Dror Maydan , Jeff McDonald , Ramesh Menon, Parallel programming in OpenMP, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 7: W. Eatherton. The push of network processing to the top of the pyramid. Keynote address at Symposium on Architectures for Networking and Communications Systems, Oct. 26--28 2005.
• 8: C. Frommeyer. Parallelisierung von Kürzeste-Wege-Algorithmen für die Anwendung auf Straßengraphen. Master's thesis, IPD Institute, University of Karlsruhe, Germany, 2007.
• 9: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA [doi>10.1145/1168857.1168877]
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 12: E. L. Lawler et al., editors. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley and Sons, 1985.
• 13: K. Madduri, D. A. Bader, J. W. Berry, and J. R. Crobak. Parallel shortest path algorithms for solving large-scale instances. In 9th DIMACS Implementation Challenge - Shortest Paths, November 2006.
• 14: T. G. Mattson, B. A. Sanders, and B. L. Massingill. Patterns for Parallel Programming. Addison-Wesley Professional, 2004.
• 15: U. Meyer , P. Sanders, Δ-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, v.49 n.1, p.114-152, 1 October 2003 [doi>10.1016/S0196-6774(03)00076-2]
• 16: David A. Patterson, Computer science education in the 21^st century, Communications of the ACM, v.49 n.3, March 2006 [doi>10.1145/1118178.1118212]
• 17: J. R. Rattner. Tera-scale computing - a parallel path to the future. http://softwarecommunity.intel.com/articles/eng/1275.htm, May 15 2007.
• 18: J. Reinders. Intel Threading Building Blocks. O'Reilly, 2007.
• 19: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977
• 20: N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, V10(2):99--116, February 1997.
• 21: B. Smith. Reinventing computing. In Keynote at the Manycore Computing Workshop, Seattle, WA, June 20-21 2007.
• 22: The R Development Core Team. R: A language and environment for statistical computing. http://www.r-project.org, June 27 2007.
• 23: Thomas M. Warschko , Joachim M. Blum , Walter F. Tichy, The ParaStation project: using workstations as building blocks for parallel computing, Information Sciences: an International Journal, v.106 n.3-4, p.277-292, May 1, 1998 [doi>10.1016/S0020-0255(97)10015-9]
• 24: Otilia Werner-Kytölä , Walter F. Tichy, Self-Tuning Parallelism, Proceedings of the 8th International Conference on High-Performance Computing and Networking, p.300-312, May 08-10, 2000
• 25: R. K. Yin. Case Study Research: Design and Methods. Sage Publications, 3rd edition, 2002.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
autotuning, design patterns, multicore systems, openMP