DS221: Introduction to Scalable Systems

Department of Computational and Data Sciences

Introduction to Scalable Systems

  • Instructor: Sathish Vadhiyar (www | email), Chirag Jain (www | email) and Matthew Jacob (www | email)
  • Teaching Assistant: Chandrashekar M A (email)
  • Course number: DS221
  • Credits: 3:1
  • Semester: Aug, 2021
  • Lecture: Tue/Thu 10-11:30 AM (First class: Aug 5, 2021 10AM on Teams)
  • Lab: As announced
  • Microsoft Teams Link: Teams (Use IISc Office 365 account to login)
  • Mailing list: TBD

[DS221 2020 Website] [DS221 2019 Website] [DS221 2018 Website][DS221 2017 Website]


Overview

This course covers computer systems topics that are essential for students engaging in computational and data sciences. It introduces topics on architecture, OS and data structures that may be new to students without a degree in Computer Science. Then it moves to more advanced topics on tree/graph data structures, HPC/GPGPU programming and Big Data platforms.

Some of the topics covered are: Architecture: computer organization, single-core optimizations including exploiting cache hierarchy and vectorization, parallel architectures including multi-core, shared memory, distributed memory and GPU architectures; Algorithms and Data Structures: algorithmic analysis, overview of trees and graphs, algorithmic strategies, concurrent data structures; Parallelization Principles: motivation, challenges, metrics, parallelization steps, data distribution, PRAM model; Parallel Programming Models and Languages: OpenMP, MPI, CUDA; Distributed Computing: Commodity cluster and cloud computing; Distributed Programming: MapReduce/Hadoop model.

This course is a precursor to more advanced courses like DS 295: Parallel Programming, and DS 256: Scalable Systems for Data Science, and includes topics from the earlier DS 286: Data Structures and Programming and DS 292: High Performance Computing courses.


Pre-requisites

This is an introductory crash-course on computer systems, algorithms, HPC and Big Data platforms. So the pre-requisites are minimal: Basic knowledge of computer systems, data structures and programming, and algorithms. However, the course will have a rapid pace and students are expected to pick up the skills rapidly through self-learning.


Grading Scheme

  • MJT
    • 1 Assignment (10 points)
    • 1 Quiz (10 points)
  • CJ
    • 1 Programming Assignments (15 points)
    • 1 Written Assignment (15 points)
  • VSS
    • Continuous assessments (10 points)
    • Assignment (10 points)
  • Final Exam (30 points)
    • 5 (MJT) + 5 (CJ) + 20 (VSS)
  • First 50 points (MJT+CJ) are for Sessionals, and Second 50 points (VSS+Finals) are for Terminal

Resources

  • Data Structures, Algorithms, and Applications in C++, 2nd Edition, Sartaj Sahni
  • Parallel Computing Architecture. A Hardware/Software Approach. David Culler, Jaswant Singh. Publisher: Morgan Kauffman. ISBN: 981-4033-103. 1999.
  • Parallel Computing. Theory and Practice. Michael J. Quinn. Publisher: Tata: McGraw-Hill. ISBN: 0-07-049546-7. 2002.
  • Computer Systems – A Programmer’s Perspective. Bryant and O’Hallaron. Publisher: Pearson Education. ISBN: 81-297-0026-3. 2003.
  • Introduction to Parallel Computing. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar. Publisher: Addison Wesley. ISBN: 0-201-64865-2. 2003.
  • An Introduction to Parallel Programming. Peter S Pacheco. Publisher: Morgan Kauffman. ISBN: 978-93-80931-75-3. 2011.
  • Online references for OpenMP, MPI, CUDA
  • Lecture slides

Tentative Schedule

  • Architecture, MJT (6 lectures, Aug 5-26)
    • Computer organization including cache hierarchy, locality
    • Assignment 1 (10 points)
    • Quiz (10 points, Oct 29)
  • Algorithms and Data Structures, CJ (8 lectures, Aug 31- Sept 23)
    • Algorithmic analysis and Lists
    • Basic Data Structures: Stacks, Queues, Trees
    • Searching: Hashmap, Search trees
    • Fundamentals of graphs
    • Algorithmic Strategies
    • Programming Assignment 2 (15 points)
  • Introduction to Big Data, CJ (3 lectures, Sept 28 – Oct 5)
    • Big Data programming models: Apache Spark
    • Assignment 3 (15 points)
  • Parallel Computing, VSS (10 lectures, Oct 7 – Nov 16)
    • Continuous Assessments (10 points)
    • Parallel architectures
      • Shared and Distributed memory architectures
      • Many-core architectures
    • Parallelization Principles
    • Parallel Programming Models and Languages
      • Shared memory: OpenMP
      • Distributed Memory: MPI – pt2pt, collectives
      • GPUs: CUDA
    • Sample Parallel Algorithms
      • Sorting, Searching
    • Assignment 4 (10 points)
  • Final Exam (TBD Dec 1-10, 2021; 30 points)

NOTE: Besides these lectures, there will be several tutorials as well. The schedule for these will be announced in class.


Reading

  • Parallel architecture – Grama et al. – 2.4, Many-core – Google for NVIDIA Kepler white paper
  • Parallelization principles – Grama et al. – 3.1, 3.5, 5.1-5.6; Culler and Singh – 2.2, 2.3
  • OpenMP tutorial: http://www.llnl.gov/computing/tutorials/openMP
  • MPI online tutorial: “MPI complete reference”. Google for it.
  • CUDA: Google for NVIDIA CUDA programming guide.
  • Parallel algorithms
    • Parallel Quick sort – the corresponding portion in the text book by Grama et al.
    • BFS
      • Paper: A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L. Yoo et al. SC 2005. (Pages 1-7)
      • Paper: Accelerating large graph algorithms on the GPU using CUDA. Harish and Narayanan. HiPC 2007. (Page 5-8)

Assignments