CS 545 Parallel Computing System

                      

                                                                                      11:00 - 11:50  MWF

                                                                                                EPS 350

 

Instructor:     Year-Back Yoo

                        EPS 359, x3541, yoo@cs.montana.edu

 

Office Hour:   9-11 MW

                                     

Text:               Lecture notes.  (No textbook)

 

 References:    Introduction to Parallel Computing, 2^nd Ed

                                  Grama, Gupta, Karypis, and Kumar, Addison Wesley, 2003

                            Parallel Computing: Theory and Practice, 2^nd Ed

                                  Quinn, McGraw Hill, 1994

                            The Design and Analysis of Parallel Algorithms

                                  Akl, Prentice-Hall, 1989

                        Algorithms: Sequential, Parallel, and Distributed

                                  Berman and Paul, Thomson, 2005

            

       

Requirements

 

·       Assignments                40

o   Seminar (Tutorial)        30

·        Project                        80'   

·        Tests                         100                                  

 

                                   

 

Project  (80' pts)

 

         Implementation of a parallel algorithm for the problem you choose.

         Follow the following guideline.

            1.  Journal Survey

            2.  Design of parallel algorithm for the problem.

            3.  Implementation of the algorithm on a parallel computing system

            4.  Experiments with various input sizes (Use benchmark, if available)

            5.  Report from he the experiment (Include discussion and conclusion).

         Submit the report by November 30, and give a presentation in December.

 

         The evaluation criteria:

            1.  Extent of the journal survey

            2.  Efficiency of the parallel algorithm designed.

            3.  Effectiveness of the experimental design

            4.  Computational results

            5.  Report quality

            6.  Presentation

 

 

Part I.    Foundation

 

 1.   Introduction

            Motivation

            History

            Performance metric – speedup, efficiency                          

            Model of parallel computation

                    RAM (Shared memory)

                    Distributed Memory (Message passing)    

            Design of Parallel Algorithm

           

  2.   Parallel Computer Architecture

  o  Taxonomy 

  o  Processor Interconnection - Goodness measures 

  o  Benchmarking - Top500                                                                                             

 

 3.   Mapping and Scheduling                                                                                                         

o   Mapping                                                                               

o   Scheduling

                                                                          

 4.   Parallel Programming Languages

       o   Parallel Program Constructs

       o   Parallel Programming Languages 

     

 Part II.   Parallel Algorithms 

 

  5.   Elementary Parallel Algorithms:  sum, prefix sum, surfix sum, broadcast                                                     

 

  6.   Sorting  and Merging

                                                                                                   

  7.   Matrix Algorithms

                                                                               

  8.   Graph and Network Algorithms                                                                                                                                                     

 

Part III.    Special Topics  (Seminar)

 

       o  Team A:    Ant Colony Optimization

       o  Team B:    Tabu Search

       o  Team C:   Systolic Array

       o  Team D:   Dataflow Machine

       o  Team E:   Optical Computer/DNA Computer/Quantum Computer