Basic Information

Dates

Description

This seminar introduces students to fundamental results in parallel programming and design. Students will study and present research papers that span topics in both theory and practice, ranging from foundations of parallel computing to applications. The focus will be on fundamental lower and upper bounds, thus, many papers will be dated. Students need a solid mathematical background.

Educational Objective

At the end of the course, the students should be familiar with a broad range of key research results in the area of parallel computing, know how to read and assess papers in the area, and be able to highlight practical examples/applications, limitations of existing work, and outline potential improvements.

Content

A selection of research papers with a focus on foundations of parallel computing/programming.

Presentation details

Talk assignments

Date Paper Student Assistent
10.03.15 - 1:0027Severin MüngerTobias Gysi
10.03.15 - 2:0030Seraiah WalterMaciej Besta
17.03.15 - 1:0012Benjamin FischerSalvatore Di Girolamo
17.03.15 - 2:001Otto BibartiuTimo Schneider
24.03.15 - 1:0022Fabian MeierTobias Grosser
24.03.15 - 2:0021Nadja MüllerArnamoy Bhattacharyya
31.03.15 - 1:0015Cedric BaumannTobias Gysi
31.03.15 - 2:0016Fredrik RothenbergTobias Grosser
28.04.15 - 1:0018Stefan MüllerEdgar Solominik
28.04.15 - 2:007Lukas BurkhalterEdgar Solominik
05.05.15 - 1:0017Theodoros TheodoridisArnamoy Bhattacharyya
05.05.15 - 2:0019Tijana ZivicMaciej Besta
12.05.15 - 1:0028Cyril SteimerSalvatore Di Girolamo
12.05.15 - 2:0020Florian HahnTimo Schneider
19.05.15 - 1:0008Benjamin WeberEdgar Solominik

We invite the speakers to approach the reseach assistent assigned in case of questions on the paper, the presentation or any other questions where help is requireed. Contact details can be found at: http://spcl.inf.ethz.ch/People/

Publications

Each student is invited to choose one publication to prepare and present.

Number Title/Author URL
Communication (I/O) complexity
1 H. Jia-Wei and H. T. Kung. "I/O Complexity: The Red-Blue Pebble Game." Proc. 13th Ann. ACM Symp on Theory of Computing, May 11-13, (1981), 326-333 ACM
2 Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz. "Graph expansion and communication costs of fast matrix multiplication." J. ACM 59, 6, Article 32 (December 2012), 23 pages. ACM
3 A. Aggarwal and J. S. Vitter. "The Input/Output Complexity of Sorting and Related Problems." Communications of the ACM 31 (September 1988),1116-1127. ACM
4 Alok Aggarwal, Ashok K. Chandra, Marc Snir. "Communication complexity of PRAMs." Theoretical Computer Science 71.1 (1990): 3-28. Science Direct
5 Dror Irony, Sivan Toledo, and Alexander Tiskin. "Communication lower bounds for distributed-memory matrix multiplication." Journal of Parallel and Distributed Computing 64.9 (2004): 1017-1026. Science Direct
6 David E. Shaw. "A fast, scalable method for the parallel evaluation of distance‐limited pairwise particle interaction." Journal of computational chemistry 26.13 (2005): 1318-1328. Wiley
7 Alexander Tiskin. "Communication-efficient parallel generic pairwise elimination." Future Generation Computer Systems 23.2 (2007): 179-188. Science Direct
Parallel algorithms, models, and bounds
8 Soumen Chakrabarti, James Demmel, and Katherine Yelick. "Modeling the benefits of mixed data and task parallelism", In Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures (SPAA '95). ACM
9 Tom Leighton. "Tight bounds on the complexity of parallel sorting." IEEE Trans. Comput. 34, 4 (April 1985), 344-354. IEEE
10 John M. Mellor-Crummey and Michael L. Scott. "Synchronization without contention." SIGARCH Comput. Archit. News 19, 2 (April 1991), 269-278 ACM
11 Marc Snir. "Size-depth tradeoffs for monotone arithmetic circuits." Theoretical Computer Science 82, 1, May 1991, 85-93. Science Direct
12 R. Ladner and M. Fischer. "Parallel prefix computation", J. Assoc. Comput. Mach., 27, pp. 831–838, 1980. ACM
13 Uzi Vishkin. "Randomized Speed-ups in Parallel Computation." ACM Symposium on Theory of Computing, 230-238, 1984. ACM
14 Richard Cole and Ofer Zajicek. "The APRAM: Incorporating Asynchrony in the PRAM model." 1st ACM Symp on Parallel Algorithms and Architectures (SPAA), 169-178, 1989. ACM
Scheduling and work stealing
15 N. S. Arora, R. D. Blumofe, and C. G. Plaxton. "Thread Scheduling for Multiprogrammed Multiprocessors." Theory of Computing Systems 34, 115-144 (2001) Springer
16 Umut A. Acar, Guy E. Blelloch, and Robert D. Blumofe. "The Data Locality of Work Stealing." Theory of Computing Systems 35, 321-347 (2002) Springer
17 Richard Cole and Uzi Vishkin. "Approximate Parallel Scheduling." Part I, SIAM J. of Computing (17)1, 128-142, 1988. SIAM
18 Rezaul Alam Chowdhury, Vijaya Ramachandran, Francesco Silvestri, and Brandon Blakeley. “Oblivious algorithms for multicores and networks of processors.” Journal of Parallel and Distributed Computing 73, no. 7 (2013): 911-925. Science Direct
Parallel Graph algorithms
19 U. Meyer and P. Sanders. "Δ-stepping: a parallelizable shortest path algorithm." J. Algorithms 49, 1 (October 2003) Science Direct
20 Yossi Shiloah and Uzi Vishkin. "An O(logn) Parallel Connectivity Algorithm." Journal of Algorithms (3), 57-67, 1982. Science Direct
21 Michael J. Quinn and Narsingh Deo. "Parallel Graph Algorithms." Computing Surveys (16)2, 319-348, 1984. ACM
22 Julian Shun, Laxman Dhulipala, and Guy Blelloch. "A simple and practical linear-work parallel algorithm for connectivity." SPAA '14. ACM, New York, NY, USA, 143-153. ACM
23 Alexandre Tiskin. "All-pairs shortest paths computation in the BSP model." Automata, Languages and Programming. Springer Berlin Heidelberg, 2001. 178-189. Springer
Networks, communication, and routing
24 A. Borodin and J. E. Hopcroft. "Routing, merging and sorting on parallel models of computation." In Proceedings of the fourteenth annual ACM symposium on Theory of computing (STOC '82). ACM, New York, NY, USA, 338-344 ACM
25 Mikkel Thorup, Uri Zwick. "Compact routing schemes", SPAA '01 Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures Pages 1-10 ACM
26 Richard M. Karp, Abhijit Sahay, Eunice E. Santos, Klaus Erik Schauser. "Optimal broadcast and summation in the LogP model." SPAA '93 Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures Pages 142 - 153 ACM
27 Charles E. Leiserson. "Fat-Trees: Universal Networks for Hadware-Efficient Supercomputing." IEEE Transactions on Computers archive, Volume 34 Issue 10, Oct. 1985, Pages 892 - 901 IEEE
28 Jehoshua Bruck, Ching-Tien Ho, Eli Upfal, Shlomo Kipnis, and Derrick Weathers. "Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems." IEEE Trans. Parallel Distrib. Syst. 8, 11, 1997. Springer
29 Jesper Larsson Träff and Andreas Ripke. "Optimal broadcast for fully connected networks." High Performance Computing and Communications. Springer Berlin Heidelberg, 2005. 45-56.
+ Peter Sanders, Jochen Speck, and Jesper Larsson Träff. "Two-tree algorithms for full bandwidth broadcast, reduction and scan." Parallel Comput. 35, 12 (December 2009) 		ACM
Springer
30 Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy. "Memory consistency and event ordering in scalable shared-memory multiprocessors".
ISCA '90 Proceedings of the 17th annual international symposium on Computer Architecture, Pages 15-26 		ACM