Contents (hide)

Course Subject and Overview

Motivation. Multicore architectures have become popular in recent years. Additionally, the need to efficiently implement graph algorithms has increased due to the rise of social networks (e.g., Facebook and Twitter), recommending systems (e.g., those of Netflix and Amazon), and scientific applications (e.g., in biology).

Goals. To expose the students to concepts and techniques for parallelizing graph algorithms and to enable them to experience with their implementation via an advanced system called Galois.

Instruction Method. In the introductory lecture(s), the students will learn the principles of implementing parallel graph algorithms via the Galois system. During the semester, we will have 2-3 full meetings and schedule personal meetings on demand.

Course Requirements

The students will divide into groups of 1-2 students. Each group will propose an algorithm it would like to implement. Then, the students will divide into groups, propose a graph algorithm, implement it, and experience running it on a multi-core server. Finally, the students will prepare a summary report and a short presentation of their project.

Grading

  • 10%: quality of the final report.
  • 10%: quality of the project presentation.
  • 5%: coding quality and code documentation quality.
  • 5%: thoroughness of experimental evaluation.
  • 70%: algorithm implementation quality.

Lectures

01-Introduction (PPTX)

02-Paralleling Graph Algorithms (PPTX)

03-Technical introduction to Galois (PPTX)

Useful Links

  1. Galois web-page
  2. Galois API documentation
  3. Graph conversion graph-convert.cpp
  4. C++11