AMS 530:
Principles of Parallel Computing
References
--- Grades
|
Instructor |
Yuefan Deng |
|
Room Number |
A-135
Physics Tower for all office hours |
|
Phone Number |
631-632-8614 |
|
Email Address |
|
|
Web URL |
|
|
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 |
|
|
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 |
|
|
|
01/30 |
|||
|
02/06 |
IBM:
Programming BlueGene; Julich:
BG Doc; IBM
Redbook: BG/P; |
|
|
|
02/13 |
|||
|
02/20 |
6A: Guest lecture by Josh Shapiro on
PAT and measuring performance (parallel program profiling) |
|
|
|
02/27 |
9: MPI
(Part5-Process-Mapping) OpenMP
(Wiki) OpenMP
Tutorial (LLNL) |
|
|
|
03/05 |
10: Linear Algebra
(Part1-Intro) |
|
|
|
03/12 |
|||
|
03/19 |
|
Updated (3/19/2012): 19: Task
Mapping (Deng) |
|
|
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 |
|
|
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.2, Proj3.2, |
|
04/16 |
Traveling
Salesman Problem (Wiki) |
(cf: 3D
FFT on 6D Torus by Fang, Deng, Martyna), Cooley-Tukey FFT (The original Article), Cooley-Tukey FFT(Wiki), |
|
|
04/23 |
|
||
|
04/30 |
21: Network design issues |
||
|
05/07 |
|
|
|
|
05/14 |
|
|
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.