CS 4328 Parallel Computing
Fall 2009 (CRN: 10169, 3 credit hours)
Prerequisites: CS 3402 and CS 3304. You must have a good working knowledge of C.
Instructor: Dr. Hong Lin, Office: S-717
email:
web
page: http://cms.dt.uh.edu/faculty/linh/courses/cs4328
office phone: (713) 221 2781
office hours: Monday - Thursday 2:00PM - 4:30PM
Textbook: Parallel Programming - Techniques and Applications Using Networked Workstations and Parallel Computers, 2nd Edition, by Barry Wilkinson and Michael Allen, Pearson Prentice Hall, 2005.
Catalog Description:
Consideration of the issues involved in various forms of parallel computing including pipelines, vector processors, multiprocessor systems, related algorithms and parallel distributed processing.
Course Topics:
|
Chapters |
Topics |
|
Chapter 1. Parallel Computers |
Demand for computational speed, types of parallel computers, cluster computing. |
|
Chapter 2. Message-passing Computing |
Basics of message-passing programming, software tools, MPI, evaluating parallel programs, compiling MPI programs. |
|
Chapter 3. Embarrassingly Parallel Computations |
Embarrassingly Parallel examples, Mandelbrot Set, Monte Carlo methods. |
|
Chapter 4. Partitioning and Divide and Conquer Strategies |
Partitioning and divide and conquer examples, bucket sort, numerical integration, N-body problem. |
|
Chapter 5. Pipelined Computations |
Pipeline technique and types, examples, adding numbers, sorting, prime number generation, solving system of linear equations. |
|
Chapter 6. Synchronous Computations |
Synchronization, barrier implementation, synchronous computation examples, data parallel, synchronous iteration, solving system of linear equations by iteration, heat distributed problem, cellular automata, partially synchronous methods. |
|
Chapter 7. Load Balancing and Termination Detection |
Dynamic load balancing, distributed termination detection algorithms, program example (shortest path problem) |
|
Chapter 8. Programming with Shared Memory |
Shared memory multiprocessors, constructs for specifying parallelism, processes, threads, language constructs, dependency analysis, OpenMP, performance issues, program examples |
|
Chapter 10. Sorting Algorithms |
Potential speedup of sorting in parallel, compare and exchange, bubble sort, odd-even transposition sort, mergesort, quicksort, odd-even mergesort, bitonic mergesort, sorting on meshes and hypercube, rank sort, counting sort, radix sort, sample sort, sorting on clusters. |
Course Goal:
Upon completion of this course, students should be able to:
· DESCRIBE the major functions and approaches to parallelism used in a large parallel program, through program inspection and research on an application domain,
· IDENTIFY the regions of a large time-consuming program that are most conducive to increased performance through parallelization,
· SELECT and apply appropriate parallelization constructs to a large program to create a correct parallel version to exploit a state-of-the-art parallel computing environment,
· ASSESS the correctness of a parallel program,
· APPLY available debugging methods to detect and correct errors in an erroneous parallel program,
· ASSESS the performance of parallel programs run with different parameters of input sizes and numbers of processors,
· VERBALLY AND ORALLY CRITIQUE a parallelization effort and its resulting performance results to non-experts,
· Work on a realistic program parallelization problem
This course is a writing course. Students who want to take this course as a
writing course must get approval from the department. A writing project will be
assigned to those students who take this course as a writing course, and must
be completed at the end of the semester in addition to the completion of other
course work. A student must get at least a "C" to have his/her
writing project evaluated, in which situation his/her writing project will be
given a grade either "Pass" or "
Grading Breakdown:
2 Tests 40% (20% each)
Final Exam 25%
3 Programming Assignments 20%
Short oral presentation 5%
Quizzes, Labs, and participation 10%
Grading Scale:
90-100 A, 80-89 B, 70-79 C, 60-69 D, Below 60 F
Programs:
We will write parallel programs using MPI (Message Passing Interface). Programs should be written using C and the MPI library. All submitted work must be compilable in Visual C++ and be tested on MPICH Windows version. Due dates are listed in the course schedule. You should check the course schedule regularly for updates about the assignments and due dates.
Complete, documented copies of your program source code, and test files should be submitted in a disk together with a print-out of your source code and test results at the beginning of the class on the due date.
The last project includes a short oral presentation on a real-life application of parallelism. You will be given a problem and be asked to search the web for a demonstration of an application that depends on parallelism to achieve its goal, and present a short (length will be determined according to class size) presentation describing the application and how it utilizes parallelism, how parallelism is achieved, and why parallelism is so crucial to its success. Depending on class size, assignments will be given individually or based on groups.
Policies:
Students are responsible for the materials assigned from the book and the lecture notes. To pass this course a passing grade on both programming assignments and exams is required. No make up tests will be given. You are expected to turn in your own work on time. Assignments submitted at any later time without an approved excuse will not be accepted. In any circumstances, late submission will cause a loss of 10 points per day (including weekends), and no submission late more than 1 week will be accepted. All missed grades will be recorded as zero. It is up to you to determine the version of your assignment to be graded. You must weigh the late penalty against the completeness of your assignment.
Academic Dishonesty
For this class, all work must be
done individually -- no group work is allowed. You are encouraged to generally
discuss assignments with fellow students, but may not copy their solution or
code. Significant identicalness constitutes duplication. This includes but not
be limited to: the main body of the programs are the same; only variable names
are different; e
General University Policies and Procedures: All students
are subject to UH-Downtown's Academic Honesty Policy and to all other
university-wide policies and procedures as they are set forth in the
UH-Downtown University Catalog and Student Handbook. The Academic Honesty Code
is embraced by all members of the
Statement on reasonable accommodations
UHD adheres to all applicable federal, state, and local laws, regulations, and guidelines with respect to providing reasonable accommodations for students with disabilities. Students with disabilities should be notified to register with Disabled Student Services and contact the instructor in a timely manner to arrange for appropriate accommodations.
CS4328 - Course Schedule
(This schedule is subject to update. You should check the schedule regularly for assignments and due dates)
|
Week |
Monday |
Wednesday |
|
1 |
8/24 |
8/26 |
|
2 |
8/31
|
|
|
3 |
9/7 |
|
|
4 |
9/14 |
9/16 Lab: Monte Carlo Method |
|
5 |
9/21 |
9/23 |
|
6 |
9/28 |
9/30 |
|
7 |
10/5 Lab
Chapter 4 - Integration Project 1 Due |
10/7 |
|
8 |
10/12 Lab
exercise 2 - Pipeling: Insertion Sort |
10/14 |
|
9 |
10/19 |
10/21 |
|
10 |
10/26 Review for 2nd Test |
10/28 |
|
11 |
11/2 Project 2 Due |
11/4 |
|
12 |
11/9 |
11/11 |
|
13 |
11/16 |
11/18 |
|
14 |
11/23 |
11/25 |
|
15 |
11/30 Presentation of writing projects Writing Projects Due Project 3 Due |
12/2 |
|
16 |
12/7 Reading Day |
12/9 Final Exam 10:00am – 12:30pm |