CSC 744: Parallel Computing

Contents:

Required textbook: An Introduction to Parallel Computing: Design and Analysis of Algorithms, Second Edition by A. Grama, V. Kumar et al. Pearson Addison Wesley. ISBN: 0201648652. 

Reference: Using MPI - 2nd Edition: Portable Parallel Programming with the Message Passing Interface (Scientic and Engineering Computation) by William Gropp, Ewing Lusk, Anthony Skjellum. MIT Press; 2nd edition (November 26, 1999), ISBN: 0262571323.

There are four homework. Homeworks will focus on understanding and designing parallel programs.

• Homework assignments will be assigned during class and also posted on the course Web-page: http://www.cs.csi.cuny.edu/~yumei/csc744/csc744Fall07.html
• Homeworks MUST be turned in before the beginning of the class on the due date.



• Homework1 is available here.
• Homework2 is available here.

There will be two programming assignments. Your tasks will be designing and implementing parallel algorithms, compiling and running your programs in the environment of cluster, evaluating a solution, and submitting your program and report.

You will use CSI’s Linux cluster to do your programming assignments. Basic Information about CSI’s Cluster can be found at http://montecarlo.csi.cuny.edu/, and then click the link of Research Linux Cluster. You will need to use SSH to access CSI’s cluster from CSI’s PC or your home computer. You can download SSH from the link: http://unixace.csi.cuny.edu/csiunix/index.php4. You will also need an account to access CSI’s cluster. You will get your account within two weeks.

You are strongly encouraged to set up the programming environment and try to be familiar with CSI’s cluster before your first programming assignment.

The solution to each programming assignment may include the source code and a report showing the result:

• The source code MUST be turned in by email to huo@mail.csi.cuny.edu before midnight the date they are due.

• The report MUST be submitted either per email or be handed in a hard-copy at the beginning of the class on the due date.
• Handwritten or typed report will be accepted.
• Solutions must be readable(especially handwriting!!!), clear, concise and complete.

• The exams may test on material covered only in class and on material covered only in the reading assignments.
  
  Your grade will be based approximately, as follows. These percentages are tentative and subject to change.

     25% - Homeworks
     25% - Programming Assignments
     25% - Midterm Exam
     25% - Final
  

• Class participation is essential to succeed in this course.
• DO NOT USE pencils to write down your solutions for the homework, programming assignments or exams; if you decide, however, to use a pencil do not complain about grading.
• Check the marks in a homework, programming assignments or an exam and report errors promptly. Make sure you report such problems to the instructor within four weeks from receipt but no later than Dec.17, 2007 . If you believe a grade you received is not representative of your effort talk to the instructor.
• Homework assignments are due at the start of class on their due date. If you think you won't be present in class on that Wednesday, turn the homework in earlier at instructor's office or by email.
• No later solutions will be taken into consideration!
• The work you turn in MUST BE your own personal work, composed and written by you. No plagiarism. Otherwise, you will get the grade of zero for the homework or project.
• DO NOT OBTAIN YOUR SOLUTION THROUGH THE INTERNET. Or you will get the grade of zero for the homework or project.
• Collaboration of any kind is NOT allowed in the in-class exams (midterms, and final).

Specific contents (subject to change):

1. (8/29/07) First Class !!!
   • Discussion of the syllabus, requirements, topics to be covered, etc.
   • Introduction to Parallel Computing
   • courseinfo, note1
   • Suggested Reading: Chapter 1 of the textbook
    
2. (9/5/07)
   • Parallel Programming Platforms: taxonomy of parallel computing architecture
   • PRAM algorithm: Parallel Sum
   • Suggested Reading: Chapter 2 of the textbook

    

3. (9/12/07) NO class.
4. (9/19/07)
   • PRAM algorithms: Logic AND operation, Broadcasting, Matrix Multiplication
   • Parallel Programming Platforms: Innerconnection Networks for Parallel Computers
   • note2, note3
   • Suggested Reading: Chapter 2, chapter 8(8.2.3) of the textbook
    
5. (9/26/07)
   • Parallel Programming Platforms: Evaluation of fixed connection networks
   • Analytical Modeling of Parallel Programs
   • note4
   • Suggested Reading: Chapter 2, Chapter 5 of the textbook
    
6. (10/3/07)
   • Analytical Modeling of Parallel Programs (cont.)
   • PRAM algorithms: Parallel Prefix
   • note5
   • Suggested Reading: Chapter 5 of the textbook
    
7. (10/10/07)
   • PRAM algorithms:
     • Parallel Prefix(cont.)
     • Application of Parallel Prefix: binary number addition
     • Maximum finding
   • note6
    
8. (10/17/07)
   • Midterm Exam
    
9. (10/24/07)
   • Review midterm exam

    

10. (10/31/07)
    • MPI
    • Suggested Reading: Chapter 6 of the textbook
    • Handout: example of MPI program
     
11. (11/7/07)
    • MPI(cont.)
    • Suggested Reading: Chapter 6 of the textbook
     
12. (11/14/07)
    • Review homework 2
    • MPI(cont.)
    • Suggested Reading: Chapter 6 of the textbook
    • note7
    • Discussion about Part B of programming assignment 1

13. (11/21/07) No class.
    •  

14. (11/28/07)
    • Architecture Independent Algorithm Design and Time analysis
    • Suggested Reading: Chapter 4(Page 147-165) and Chapter 8 of the textbook
    • note8

15. (12/5/07)
    •  

16. (12/12/07) last class
    •  
17. (12/19/07) Final Exam

To be announced

• Tentative date/time of FINAL exam

References:

References to some classical books on parallel computing and c++ programming language will be posted here - these titles will be for your information only - they're not required for the course nor they will be used in any way by the instructor.

1. Using MPI - 2nd Edition: Portable Parallel Programming with the Message Passing Interface (Scientic and Engineering Computation) by William Gropp, Ewing Lusk, Anthony Skjellum. MIT Press; 2nd edition (November 26, 1999), ISBN: 0262571323.

2. The C++ Programming Language , by Bjarne Stroustrup

3. Algorithm Design, by Jon Kleinberg and Eva Tardos, ISBN: 0-321-29535-8

4. Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, ISBN-10: 0262032937

Links relevant to the course:

1.