Parallel Programming Concepts

Winter term 2013/14

Dr. Peter Tröger, Frank Feinbube

Oral exams will take place on the following days: 18.2., 20.2., 25.2., 27.2., 27.3., 28.3., 31.3., 1.4., 2.4., 3.4., 4.4.
Please register yourselve at the office C-1.6.

Since the very beginning of computers, processors were build with ever-increasing clock frequencies and instruction-level optimizations for faster serial code execution, such as ILP, caches, or speculative engines. Software developers and industry got used to the fact that applications get faster by just exchanging the underlying hardware. For several years now, these rules are proven to be no longer valid. Moore's law about the ever-increasing number of transistors per die is still valid, but decreased structural sizes and increased power consumption demand stalling, or even reduced, clock frequencies. Due to this development, serial execution performance no longer improves automatically with the next processor generation.

In the 'many-core era' that happens now, additional transistors are used not to speed up serial code paths, but to offer multiple execution engines ('cores') per processor. This changes every desktop-, server-, or even mobile system into a parallel computer. The exploitation of additional transistors is therefore now the responsibility of software, which makes parallel programming a mandatory approach for all software with scalability demands.

In this course, we want to discuss the relevant theoretical and practical solutions available for parallel software development.

Slides will be made available shortly after the lecture.

Lectures

Mo, 9:15 - 10:45, HS 3
Thu, 9:15 - 10:45, HS 3

Assignments

Rules

Assignments have to be solved alone or as a team of two persons. The oral exam admittance is achieved if 50% of the assignments are solved correctly.

Recommended Readings

Book

  • R. H. Perrott, Parallel Programming. Addison-Wesley Publishing Company, 1987.
  • J. Jaja, An introduction to parallel algorithms. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc., 1992.
  • I. Foster, Designing and Building Parallel Programs. Addison-Wesley, 1995.
  • N. Lynch, Distributed Algorithms. Morgan Kaufmann Series in Data Management Systems, 1997.
  • S. Schneider, Concurrent and Real Time Systems: The CSP Approach. New York, NY, USA: John Wiley Sons, Inc., 1999.
  • P. B. Hansen, Ed., The origin of concurrent programming: From semaphores to remote procedure calls. New York, NY, USA: Springer-Verlag New York, Inc., 2002.
  • T. G. Mattson, B. A. S, ers, and B. L. Massingill, Patterns for Parallel Programming (Software Patterns Series), 1st ed. Addison-Wesley Professional, 2004.
  • M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. Morgan Kaufmann, 2008.
  • C. Breshears, The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications. O'Reilly Media, Inc., 2009.
  • D. B. Kirk and W. W. Hwu, Programming Massively Parallel Processors: A Hands-on Approach, 1st ed. Morgan Kaufmann, 2010.
  • K. Mani Chandy and J. Misra, Parallel Programming Design. .

Book Section

  • G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities," San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2000, pp. 79-81.
  • P. J. Courtois, F. Heymans, and D. L. Parnas, "Concurrent control with 'readers' and 'writers'," D. M. Hoffman and D. M. Weiss, Eds. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2001, pp. 389-392.
  • C. A. R. Hoare, "Towards a theory of parallel programming," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 231-244.
  • E. W. Dijkstra, "Cooperating sequential processes," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 65-138.
  • E. W. Dijkstra, "Hierarchical ordering of sequential processes," in The origin of concurrent programming: From semaphores to remote procedure calls, New York, NY, USA: Springer-Verlag New York, Inc., 2002, pp. 198-227.
  • Journal Article

  • M. E. Conway, "Design of a separable transition-diagram compiler," Commun. ACM, vol. 6, no. 7, pp. 396-408, Jul. 1963.
  • P. Brinch Hansen, "Structured multiprogramming," Commun. ACM, vol. 15, no. 7, pp. 574-578, 1972.
  • C. A. R. Hoare, "Monitors: an operating system structuring concept," Commun. ACM, vol. 17, no. 10, pp. 549-557, 1974.
  • C. Antony Richard Hoare, "Communicating Sequential Processes," Commun. ACM, vol. 21, no. 8, pp. 666-677, 1978.
  • P. Brinch Hansen, "Distributed processes: a concurrent programming concept," Commun. ACM, vol. 21, no. 11, pp. 934-941, 1978.
  • D. Gelernter, "Generative communication in Linda," ACM Trans. Program. Lang. Syst., vol. 7, no. 1, pp. 80-112, Jan. 1985.
  • J. L. Gustafson, "Reevaluating Amdahl's law," Commun. ACM, vol. 31, no. 5, pp. 532-533, 1988.
  • L. G. Valiant, "A bridging model for parallel computation," Commun. ACM, vol. 33, no. 8, pp. 103-111, 1990.
  • H. Sutter, "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software," Dr. Dobb's Journal, vol. 30, no. 3, Mar. 2005.
  • M. D. Hill and M. R. Marty, "Amdahl's Law in the Multicore Era," IEEE Computer, vol. 41, no. 7, pp. 33-38, Jul. 2008.
  • F. Feinbube, P. Tröger, and A. Polze, "Joint Forces: From Multithreaded Programming to GPU Computing," IEEE Software (Software), vol. 28, no. 1, pp. 51-57, Oct. 2010.
  • H. González-Vélez and M. Leyton, "A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers," Software: Practice and Experience, vol. 40, no. 12, pp. 1135-1160, Nov. 2010.

Conference Paper

  • E. W. Dijkstra, "The structure of the 'THE'-multiprogramming system," in SOSP '67: Proceedings of the first ACM symposium on Operating System Principles, 1967.
  • D. E. Culler, R. M. Karp, D. A. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken, "LogP: Towards a Realistic Model of Parallel Computation," 1993, pp. 1-12.
  • R. D. Blumofe and C. E. Leiserson, "Scheduling Multithreaded Computations by Work Stealing," in In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS, 1994, pp. 356-368.
  • K. Kennedy, C. Koelbel, and H. Zima, "The rise and fall of High Performance Fortran: an historical object lesson," in third ACM SIGPLAN conference on History of programming languages, 2007, pp. 7-1.
  • G. Bronevetsky, I. Laguna, S. Bagchi, B. R. de Supinski, D. H. Ahn, and M. Schulz, "AutomaDeD: Automata-based debugging for dissimilar parallel tasks," in International Conference on Dependable Systems and Networks (DSN), 2010, pp. 231-240.
  • W. Gellerich and M. . Gutzmann, "Massively Parallel Programming Languages - A Classification," in ISCA International Conference on Parallel and Distributed Computing Systems, vol. 1, pp. 110-118.
  • A. P. Chandrakasan, M. Potkonjak, R. Mehra, J. Rabaey, and R. W. Brodersen, "Optimizing Power Using Transformations."
  • D. M. Tullsen, S. J. Eggers, and H. M. Levy, "Simultaneous Multithreading: Maximizing On-Chip Parallelism," in 22nd Annual International Symposium on Computer Architecture.

Web Page

  • "Classification of the principal programming paradigms." [Online]. Available: http://www.info.ucl.ac.be/~pvr/paradigms.html. [Accessed: 29-Mar-2011].
  • G. V. Wilson, "The History of the Development of Parallel Computing." .
  • B. Barney, "Introduction to Parallel Computing." .
  • C. Breshears, "Intro to Parallel Programming - Video Course." [Online]. Available: http://www.dailymotion.com/playlist/x1pc0m_Intel_Academic_EMEA_intro-to-parallel-programming/1

Slide

  • A. Bechtolsheim, The Road To Exascale. 2009.