AMS 530: Principles of Parallel Computing

 

References --- Grades

 

For Spring 2012 (Updated 4/30/2012)

 

Instructor

Yuefan Deng

Room Number

A-135 Physics Tower for all office hours

Phone Number

631-632-8614

Email Address

Yuefan.Deng@StonyBrook.edu

Web URL

http://www.ams.sunysb.edu/~deng

Class Time

Mondays & Wednesdays 3:50pm-5:10pm

Office Hours

Mondays & Wednesdays 1-3pm (other times possible by email)

Classroom

Room S235 SINC Site

 

TA

Hongren Wei (for 2012)

Office

B148-8 Math Tower

Email

howei@ams.sunysb.edu

Website

 

Office Hours

Friday 2:15pm-4:15pm

 

 

 

Lecture Plan:

Ø  The following lecture plan will be followed as closely as possible;

Ø  Perfect synchronization between the plan and actual lecture is unlikely;

Ø  Lectures will be paced according to class responses;

Ø  Lecture PPT password is given 24 hours before each lecture.

 

 

Week

of

Monday

3:50p-5:10p

Wednesday

3:50p-5:10p

Projects

01/23

1A: Course Overview: This website or PDF

1B: PP Introduction (PDF, PPT)

 

01/30

1C: Hardware Introduction

2: Software Introduction

02/06

IBM: Programming BlueGene; Julich: BG Doc; IBM Redbook: BG/P;

 

3: Algorithms Introduction

4: Performance Measurement

 

02/13

5: MPI (Part1-Intro)

6: MPI (Part2-Examples)

Project-1

02/20

6A: Guest lecture by Josh Shapiro on PAT and measuring performance (parallel program profiling)

7: MPI (Part3-Collective-Operations)

 

02/27

8: MPI (Part4-Collective-Operations-List)

9: MPI (Part5-Process-Mapping)

 

OpenMP (Wiki)

OpenMP Tutorial (LLNL)

 

03/05

10: Linear Algebra (Part1-Intro) 

 

Parallel LA by Koerfgen

 

Parallel Dense LA

 

ScaLAPACK

11: Matrix Multiply (Part 2)

 

Project-2

03/12

12: Calculus-and-PDEs

13: More-PDEs

03/19

14: Simple MD

 

 

Updated (3/19/2012):

 

19: Task Mapping (Deng)

 

 

19A: Task Mapping by P. Zhang

 

03/26

Class changed to 4/10 Presentations

17: Parallel Monte Carlo Methods (Deng)

Chu-Deng-Reinitz: Parallel SA (PDF)

Book: Random Numbers and MC

Cambridge: MacKay: Intro to Monte Carlo

CS-Edu: Monte Carlo

Wiki: Monte Carlo

 

Project-3 

04/02

Spring Break

Spring Break

04/09

Class changed to 4/12 Presentations

Simulated Annealing (Wiki)

SA Method (Numerical Recipes)

Genetic Algorithm (Wiki)

History of MC (LANL)

Optimization (Wiki)

Global Optimization (Wiki)

 

Optimization Software (Web)

With permission, I post the following presentations for your references (same password)

Proj3.1,

Proj3.1,

Proj3.2,

Proj3.2,

Proj3.3,

Proj3.3,

Proj3.4,

Proj3.4.

04/16

Traveling Salesman Problem (Wiki)

 

The Traveling Salesman Problem (Book)

15: Basic FFT,

(cf: 3D FFT on 6D Torus by Fang, Deng, Martyna),

Cooley-Tukey FFT (The original Article),

Cooley-Tukey FFT(Wiki),

Parallel FFTW,

FFT Algorithms,

MS Thesis for PP FFT

Project-4

04/23

16: Linear Equations

18: Basic Load Balance

 

04/30

 21: Network design issues

 20: Concluding Remarks

Project-5

05/07

 

 

 

05/14

 

 

Project-6

 

 

Announcements:

1. I have encouraged people to do self-composed projects. The only requirement is that the projects have to be well composed and are emailed to me for approval at least one week before the due date. After I approve the project, I would post it on my web and alert our TA. No projects outside my assignment are allowed unless the above single condition is met. Please cooperate.

2. Lectures 18 (load balance, optional), 17 (FFT), 16 (iterative), 15, 14, 13, 12, 11 10, 9, 8, 7, 6, 5, 4, 3, 2, 1C, 1B, 1A are all ready. Lectures 16 and 18 are added on Monday April 30.

3. Projects 6, 5, 4, 3, 2 and 1 are ready. Remember, Project 6’s due date is Monday May 14. I will post ABCs on May 16 (assuming receiving grades from TA on May 15).

4. I have sent an announcement on BB to congratulate those who have earned more than 60% and warned others who have made below 31%. Two more projects (5&6) are still here to allow you to make up to 30% more. I would follow the grading policy posted at the start of the semester for ABCs and give them immediately after I receive grades of Project 6. Please work with our TA to ensure the accuracy of your scores before my posting.

5. With permissions from individuals, I have posted a few presentations that I consider good. Please feel free to view and comment.

6. For Project 3, you need to submit a PPT for the presentation and a usual project report. The due date is the same: 8AM April 10 Tuesday. The first presentation will start at 9AM that day and run through 11AM. The second group will present on April 12 (same time window).

7. To accommodate people who have access problems to Seawulf etc, I would allow everyone to submit up to one late project late for 24 hours. All other cases of late submission are considered late.

8. Please view the latest release IBM BlueGene/Q datasheet.

9. Lecture PPT will be released to class 24 hours before each lecture. Project assignments will be released to class at least 10 school days before due date.

10.    Most Reference links are fully functional. Please email me if you find any broken links.

11.    My book will be used for the class as a reference in addition to links I provide.

12.    Students asked about prerequisites. Knowing one sequential computer language and Linux basics is necessary (and sufficient to start). In the past, we have a significant number of undergraduates taking this class and did well. For people whose computing (or programming) skills are not sharp but are willing to learn, talk to me more during my office hours. Also, I advise you to work on a few ams326 projects.

13.    Please view old contents of this site to know more about this course. A great deal of legacies will be kept and, of course, the latest and greatest progresses in supercomputing will be presented.

 

 

Course Description:

This course is designed for students majoring in applied mathematics, physics, chemistry, biology, all engineering areas needing large-scale computing, and computer science. Its key purpose is to teach parallel computing algorithm design; students, after taking this course, should be able to construct efficient parallel algorithms for reasonably complicated problems on distributed-memory systems. The course is focused on developing parallel computing methodologies for large-scale computing applications in scientific and engineering. More specifically, it covers three main issues: (1) Analysis of parallel hardware and software systems (Architecture); (2) Design and implementation of parallel algorithms (Algorithms);(3) Applications of parallel computing to selected problems in physical science and engineering (Applications).

 

Goals:

 

To gain extensive experience in design and analysis of parallel algorithms for scientific and engineering problems. We study AAA (architecture, algorithms, and applications) with 60% of efforts devoted to the middle “A” while each of the other “A”s gets 15% attention.

 

 

Prerequisites:

 

AMS326 (Numerical Analysis) or AMS 528 (Numerical solutions to partial differential equations) or Prior computing experience with networked workstations and in using languages such as Fortran or C or C++ or Java is essential. In addition, a major in mathematics or in any of the physical sciences or engineering is desirable.

 

 

Main Lecture Content:

Introduction, Hardware issues, Past/present/future, Taxonomy, Software issues, Message passing/tools, Speedup/scalability, Programming models, Algorithmic issues, Master-slave Decomposition, SPMD/Virtual share, Basic algorithms, Communication patterns, One-to-one, one-to-all, all-to-one, all-to-all, Integration/Diff, ODEs, Hyperbolic Equations, Parabolic Equations: Heat Equations, Wave Equations, Maxwell Equations and Schroedinger Equations, Linear Algebra, Matrix-Vector, M-M, Dense AX=B, Sparse AX=B, Jacobi, Gaussian elimination, Precondition/Multi-grid, Conjugate gradient, Elliptic Equations, Gauss-Seidel, SOR etc, Molecular dynamics, Monte Carlo methods, Simulated annealing, Genetic algorithms.

 

 

Grading Policy:

Ø  Five regular projects

o   Equal 15 point for each project

o   Take-home (totally open)

o   Each project is posted with more than 10 working before the due day

o   Each project requires about 3-5 quality hours to complete

Ø  One presentation project that requires a written report and a 10-minute presentation

o   This project will be offered around the mid-term

o   This project will earn you 25 points (10 points for the essay and 15 for the presentation)

o   Fellow students grade your presentation; average all scores after removing the highest and the lowest.

o   Details about this project will be announced two weeks before its due

Ø  Total Grade: 15+15+15+(10+15)+15+15=100

 

 

 

Textbook References:

 

There is no single book that’s suitable for the course. You will depend on lecture notes and periodical handouts for the course. This will ensure we learn the most up-to-date material in the wildly fast developing field. I would follow the Deng Book although you are encouraged to read widely (See References).

 

Course Work Requirements:

Ø  All projects must be sent to TA and me by email although Web reporting is encouraged (but not required.)

Ø  No paper submission is accepted.

Ø  Every project report must contain at least:

1. Problem description;

2. Source code with comments;

3. Required numerical results;

4. Comments on the results;

5. Parallel performance analysis.

Ø  Full report for each project with programs, comments, and results in email is acceptable.

Ø  Grades are given to each problem evenly unless stated otherwise.

Ø  All projects arrived after 5pm of the due date will not be graded.

 

 

Standards of Best Programs:

Ø  Scalable;

Ø  Accurate;

Ø  Portable;

Ø  Maintainable;

Ø  Stable.