- Course Number: 263-2100-OOL, 2 Credits
- Spring 2015, Tue 13-15 CHN D 44
- Instructors: T. Hoefler (htor at inf, CAB E 64.1)
- Teaching language: English
- Maximal participants: 22

- 2/17 : Introduction - Slides: 1 per page/6 per page
**2/20 - 5pm: Deadline for paper and slot selection**- 2/24 : skip (final deadline for schedule announcement)
- 3/3 : No talk scheduled
- 3/10, 3/17, 3/24, 3/31, 4/14, 4/21, 4/28, 5/5, 5/12, 5/19: seminar talks

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.

- Speakers are asked to arrive with sufficient time before the presentation to prepare and test their setup
- The actual presentations will start at 13:15, the second presentation right after the first one (do not assume time to prepare/test the setup)
- Each presentation should take 30 minutes (stay within limit)
- The presentation is followed by 15 minutes questions/answers
- The speaker is invited to freely choose the tools for his presentation (no tools/beamer slides/overhead projector/blackboard/...)

Date | Paper | Student | Assistent |
---|---|---|---|

10.03.15 - 1:00 | 27 | Severin Münger | Tobias Gysi |

10.03.15 - 2:00 | 30 | Seraiah Walter | Maciej Besta |

17.03.15 - 1:00 | 12 | Benjamin Fischer | Salvatore Di Girolamo |

17.03.15 - 2:00 | 1 | Otto Bibartiu | Timo Schneider |

24.03.15 - 1:00 | 22 | Fabian Meier | Tobias Grosser |

24.03.15 - 2:00 | 21 | Nadja Müller | Arnamoy Bhattacharyya |

31.03.15 - 1:00 | 15 | Cedric Baumann | Tobias Gysi |

31.03.15 - 2:00 | 16 | Fredrik Rothenberg | Tobias Grosser |

28.04.15 - 1:00 | 18 | Stefan Müller | Edgar Solominik |

28.04.15 - 2:00 | 7 | Lukas Burkhalter | Edgar Solominik |

05.05.15 - 1:00 | 17 | Theodoros Theodoridis | Arnamoy Bhattacharyya |

05.05.15 - 2:00 | 19 | Tijana Zivic | Maciej Besta |

12.05.15 - 1:00 | 28 | Cyril Steimer | Salvatore Di Girolamo |

12.05.15 - 2:00 | 20 | Florian Hahn | Timo Schneider |

19.05.15 - 1:00 | 08 | Benjamin Weber | Edgar 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/

Number | Title/Author | URL |
---|---|---|

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 |

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 |

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 |

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 |

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 |