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: 2-3:30pm. Mondays and Wednesdays or when I am in the office (in CS 314)

---

Grader: Shashank Kumar (in Room 343 Comp.Sci.Bldg.) ( sk2z6@mst.edu )
office hours: 1-2:30pm Tuesday & Thursdays or by appointment

---

Assignments and Announcements

• Programming Project 3: Bitonic Sort, due April 15 (midnight) ........ input.400K ........ Results ........ Grading Rubric
• TEST II, April 25 ....... CS-387 Question Pool (pdf)
• Presentations start on April 30th. ..... Presentation Schedule ..... General Guidelines ..... Evaluation questions
• Directory containing all of the slides used in the CS-387 class

Syllabus, Term Project, Q/A Pool

• syllabus
• How to submit projects?
  
• Guidelines for Term Projects ..... Guidelines for presentations
• Question Pool for TEST I and TEST II
• Lecture venue - 207 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 ..... ........ images ........ Grading Rubric
  
• Programming Project 2: Prime Number Sieve, due .... ........ 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