Back to Homepage

MST

CS

CS 228

CS 253

CS 284

CS 355

CS 387

CS 487

CSc 387 - Introduction to Parallel Programming and Algorithms

Instructor: Fikret Ercal
Office Hours: 1-3pm. Monday and 2-3pm Wed. or by appointment (in CS 314)

---

Grader: Brian Goldman (in Room CS 339) (brian.goldman@mst.edu)
office hours: Tue & Th; 2-3:30pm or by appointment

---

Assignments and Announcements

• Programming Project 4: Gaussian Elimination, due April 14 (11:59pm) ........ matrices ........ expected results ........ Grading Rubric
  RELATED MATERIALS FOR THE ASSIGNMENT
  • Matrix Multiplication (From Quinn - PPT slides)
  • Gaussian Elimination (From Quinn - PPT slides)
• Presentation Schedule ..... Read guidelines for presentations here
• TEST II, April 21 ....... CS-387 Question Pool (pdf)
• How to submit projects?
  
• Directory containing all of the slides used in the CS-387 class

Syllabus, Term Project, Q/A Pool

• syllabus
• Guidelines for Term Projects
• Question Pool for TEST I and TEST II
• Lecture venue - 202 Computer Science Building Egress map (emergency exit route)

MPI - The Message Passing Interface & MST Cluster

• MPI Quick Start
• MPI Routines
• Other MPI Links
• MST Cluster & MPICH Quick Tutorial (PPT slides)
• MST Cluster Start Page
• MST Cluster Report

Programming GPUs using CUDA

• MST/CUDA Lecture slides
• MST/CUDA Quick Start
• Simple Vector Addition with CUDA
• CUDA Programming Guide
  
• CUDA Routines
  
• Other CUDA resources at nvidia.com
  
• CUDA U
  

SLIDES

• Lecture 1 - Introduction: Parallel Computers
• Lecture 2.a - MPI
• Lecture 2.b - MST Cluster Quick Tutorial
• Lecture 3 - Embarrassingly Parallel Computations
• Lecture 4 - Partitioning and Divide-and-Conquer Strategies
• Lecture 5.a - Pipelining
• Lecture 5.b - Prime Number Sieve
• Lecture 6 - Synchronous Computations (Prefix, Jacobi etc.)
• Lecture 7 - Parallel Sorting Algorithms (Bitonic sort etc.)
• Lecture 8 - Parallel Numerical Algorithms (Matrix Multiplication and Solution of Linear System of Equations) If time permits:
• Lecture 9 - Parallel Graph Algorithms
• Directory containing all of the slides used in the CS-387 class
• Homepage for the Textbook and the original slides

Projects and Homeworks

• Programming Project 1: Image Compression, due Monday, Feb.8 (midnight) ........ images ........ Grading Rubric
  
• Programming Project 2: Prime Number Sieve, due Feb 10 (11:59pm) ........ Grading Rubric ........ Results file
• Programming Project 3: Bitonic Sort, due ........ input.400K ........ Results ........ Grading Rubric
• Programming Project 4: Gaussian Elimination, due ........ matrices ........ expected results ........ Grading Rubric
  RELATED MATERIALS FOR THE ASSIGNMENT
  • Matrix Multiplication (From Quinn - PPT slides)
  • Gaussian Elimination (From Quinn - PPT slides)
  
  
• Homework 1, due April 5 (in class or e-mail) ........ Grading Rubric ......... Solution to Hw1
  

Exams

• TEST I ....... CS-387 Question Pool (pdf)
• TEST II ....... CS-387 Question Pool (pdf)

Class Notes (supplementary)

• 1. Parallel Computers, Topologies, Hypercube, Embeddings
• 1.1 Fundamental Hypercube Algorithms
• 2. Message Passing Computing
  
  • 2.2.3 MPI - Message Passing Interface
    
  • 2.3 Evaluating Parallel Programs
    
  • Compile/Run MPI Programs on MST Cluster (Slides)
• 3. Embarrassingly Parallel Computations
  
  • 3.2.2 Introduction to Mandelbrot Set
• 4. Partitioning and Divide-and-Conquer Strategies
• 5. Pipelined Computations
  • Pipelining (ppt slides)
  • 5-Supplement: The Sum of the Reciprocal of the Primes Diverges (Proof)
• 6. Synchronous Computations
• 7. Load Balancing and Termination Detection
  
• 8. Programming with Shared Memory
  • Mutual Exclusion (ppt slides)
  • Multithreading - sample programs
• 9. Sorting Algorithms
  • Proof: Bitonic Sort Algorithm is CORRECT!
  • Sort Example (For N >> P)
  • Optimizing Parallel Bitonic Sort (Paper from IPDPS'97 in PDF
• 10. Numerical Algorithms
  • Matrix Multiplication (From Quinn - PPT slides)
  • Gaussian Elimination (From Quinn - PPT slides)
• 11. Image Processing Algorithms
• 12. Searching and Optimization

Back to Homepage

MST

CS

CS 228

CS 253

CS 284

CS 355

CS 387

CS 487