Compiler Design Lab

Speculative Parallelization Seminar

People

Clemens Hammacher, Kevin Streit, Andreas Zeller, Sebastian Hack

Organization

Language English
Participants 12
Preparatory Meeting 2014-04-16, 2:00 pm - 4:00 pm (sine tempore), E1 1, room 1.06
Weekly Meeting Wednesday, 4:15 pm - 6:00 pm, E1 1, room 1.06
Final talks Tuesday, August 5th and Wednesday, August 6th, 10-12am and 13-15pm, E1 1, room 1.06
Availability Seminar fully booked
Prerequisites basic knowledge about compiler construction or program analysis is sufficient
Topics runtime systems for speculative parallelization, (dynamic) parallelization detection, tuning parallel execution

Modus Operandi

Each paper will be assigned to one participant. We will have weekly meetings during the semester in which we will discuss one of the papers. The discussion will be managed by the student to whom the paper was assigned. She/He is responsible for giving a short summary on the paper and for structuring the following discussion.

Every week each student has to write a summary (300 - 500 words, about 1/2 to 1 page) on the week's paper. This summary should include open questions and is to be submitted to Clemens Hammacher two days before the corresponding meeting (Monday before 11:59 pm). The summaries of all participants will be made available and can be used by the moderator to structure the discussion in the following meeting.

At the end of the semester each participant will give a presentation (30 minutes) about her/his paper.

Each participant is allowed to drop two summaries without any particular reason. In case you drop a summary, please send a short mail telling so.

Dates & Papers

× Info: All the papers can be downloaded from within the university network.

Introduction

[I1] 2014-04-23 Thomas Karos M. Burke, R. Cytron, J. Ferrante, and W. Hsieh, “Automatic generation of nested, fork-join parallelism,” J. Supercomput., vol. 3, no. 2, pp. 71–88, Jul. 1989. [summaries]
[I2] 2014-04-30 Alex Schlosser R. Rugina and M. Rinard, “Automatic parallelization of divide and conquer algorithms,” in Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP ’99, 1999, pp. 72–83. [summaries]
([I3]) L. Rauchwerger and D. Padua, “The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization,” IEEE Trans. Parallel Distrib. Syst., vol. 10, no. 2, pp. 160–180, 1999.

Software Transactional Memory

[S1] 2014-05-07 M. Mehrara, J. Hao, P.-C. Hsu, and S. Mahlke, “Parallelizing sequential applications on commodity hardware using a low-cost software transactional memory,” in Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI ’09, 2009, vol. 44, no. 6, pp. 166–176. [summaries]
[S2] 2014-05-14 D. Dice, O. Shalev, and N. Shavit, “Transactional Locking II,” in Proceedings of the 20th International Conference on Distributed Computing (DISC), 2006, pp. 194–208. [summaries]

Thread-Level Speculation (TLS) & Runtime Parallelization

[T1] 2014-05-21 Immanuel Haffner M. DeVuyst, D. M. Tullsen, and S. W. Kim, “Runtime parallelization of legacy code on a transactional memory system,” in Proceedings of the 6th International Conference on High Performance and Embedded Architectures and Compilers - HiPEAC ’11, 2011, pp. 127–136. [summaries]
[T2] 2014-05-28 Fabian Kosmale C. Ding, X. Shen, K. Kelsey, C. Tice, R. Huang, and C. Zhang, “Software behavior oriented parallelization,” in Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation - PLDI ’07, 2007, pp. 223–234. [summaries]
[T3] 2014-06-04 Daniel Birtel K. Kelsey, C. Zhang, and C. Ding, “Fast Track: Supporting Unsafe Optimizations with Software Speculation,” in 16th International Conference on Parallel Architecture and Compilation Techniques (PACT 2007), 2007, pp. 414–414. [summaries]
[T4] 2014-06-11 R. Rangan, N. Vachharajani, M. Vachharajani, and D. I. August, “Decoupled software pipelining with the synchronization array,” in 13th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2004, pp. 177–188. [summaries]
[T5] 2014-06-18 N. Vachharajani, R. Rangan, E. Raman, M. J. Bridges, G. Ottoni, and D. I. August, “Speculative decoupled software pipelining,” in 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), 2007, pp. 49–59. [summaries]

Adaptation

[A1] 2014-06-25 E. A. Brewer, “High-level optimization via automated statistical modeling,” in Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPOPP ’95, 1995, pp. 80–91. [summaries]
[A2] 2014-07-02 Curd Becker A. Raman, A. Zaks, J. W. Lee, and D. I. August, “Parcae: A System for Flexible Parallel Execution,” in Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation - PLDI ’12, 2012, pp. 133–144. [summaries]
[A3] 2014-07-09 Dominik Montada Q. Wang, S. Kulkarni, J. Cavazos, and M. Spear, “Towards Applying Machine Learning to Adaptive Transactional Memory,” Science (80-. )., pp. 1–9, 2011. [summaries]
[A4] 2014-07-16 Vasant Karasulli J. Ansel, C. Chan, Y. L. Wong, M. Olszewski, Q. Zhao, A. Edelman, and S. Amarasinghe, “PetaBricks: A Language and Compiler for Algorithmic Choice,” in Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation - PLDI ’09, 2009, pp. 38–49. [summaries]