CS 330, Fall 2004

CS 545 Parallel Computing System

Fall 2005

Instructor

Text

Tutorial Schedule

Lecture Schedule

Team Project

Grades

Instructor

Y.B.Yoo , Associate Professor

E-mail: yoo@cs.montana.edu
Office EPS 359
Office Hours: 9-10 and 11-12 MW
Phone: (406) 994-3541

------------------------------------------------------------------------------------------------------------------------------------------------------

 Text       None

Tutorial Schedule

9/30 Simulated Annealing Wan

10/3 Tabu Search Alok

10/3 Artificail Neural Network William + Block

10/5 Genetic Algorithm Ramaraj + Arun

10/5 Simulated Evolution Trotter

10/7 Stochastic Evolution Hay

10/7 Ants Colony Crewdson

                      Note. Submit a report and give a presentation in class.

Lecture Schedule (subject to change)

[1] Foundation of Parallel Computing (Yoo)

Why parallel computing?

Demand for supercomputing power - weather forecasting

Performance measure - MFLOPS, GFLOPS, TFLOPS

Issues in parallel computing

Model of parallel computation - PRAM: CREW, CRCW

Arguments against parallel computing - Minsky's, Amdahl's, Gustafson's

Sources that prevent linear speedup

[2] Parallel Computer Architecture

Taxonomy (Yoo)

Flynn's - SISD, MISD, SIMD, MIMD

Duncan's - handout

Processor Interconnections: goodness measures (Trotter) 9/16

Multistage interconnection network: Omega, Butterfly, ,,

Mesh - 2D, 3D, Torus, ...

Tree - Double tree, Fat tree

Hypercube

Goodness measure - node degree, diameter, bisection width

Performance metric (Ramaraj) 9/21

speedup, efficiency, cost (work)

Benchmarking: Top500

Linpack

Livermore Loop

PERFECT

NAS Kernel

SLALOM

SPEC 95 - CINT95, CFP95

Mapping and Scheduling (Alok) 9/23,26

embedding - dilation

Mapping

2D <-- ring, tree, binomial tree

Hypercube <-- tree, ring, 2D

Scheduling

Static: Graham's, Coffman-Graham's

[3] Parallel Program Constructs (Yoo) 9/26,28

fork/join

parbegin/parend

forall (doall,pardo,doaccross)

parallel subprogram

synchronization

cooperation

competition - critical section

dining philosophers

test-and-set (busy waiting)

P,V semaphore

barriers

monitor

fetch-and-add

message passing

Parallel Programming Languages (Williams) 10/12

[4] Parallel Algorithm Design

Fundamentals (Yoo) 10/14

Things to consider when you design parallel algorithms

Parallelization techniques

Parallel algorithm design process

Elementary parallel algorithms (Yoo) 10/14

Sum: 1-D mesh, hypercube

Prefix sum: 1-D array, tree, hypercube 10/17

Sum: shuffle-exchange, 2-D mesh

Broadcast: hypercube

Suffix sum

Merge: PRAM, CREW, EREW

Sorting (Block) (10/21)

Odd-even transport

Mergesort

Sheersort

Radix sort

Rank sort

Bitonic mergesort (Batcher's)

Matrix operations (Arun) (10/26)

(10/28)

[5] Special topics

Recurrence Relation (Yoo) (10/31, 11/2)

Dataflow machines (Hay) (11/4)

Systolic array - linear system (Wan) (11/7)

Merge network (Yoo) (11/9)

(Project Week) - No class due to SC '05 (11/14 - 11/18)

Fuzzy logic architectures (Crewdson) (11/21)

Graph algorithms (Yoo) (11/23 - 12/5)

Sollin's parallel MST

Parallel label-correcting algorithm

 -------------------------------------------------------------------------------------------------------------

                                     Team Project

---------------------------------------------------------------------------------

Team Members Problem Algorithm

------------------------------------------------------------------------------------------------------------

A (Ramaraj, Alok Arun) VLSI Placement Genetic Algorithm

B (Hay, Block, Crewdson) VLSI Placement Stochastic Evolution

C (Trotter, Williams, Wan) VLSI Placement Simulated Evolution

------------------------------------------------------------------------------------------------------------

Abstract Due: October 3 (Mon)

Progress Report: October 28 (Fri)

Presentation-1 December 9 (Fri)

Presentation-2 December 12 (Mon)

Draft due: December 14 (W)

The quality of your project is the most important factor of your final grade.

Please follow the following guideline for your project.

       1.  Select a combinatorial optimization problem to solve.

              Suggestion: VLSI cell placement problem.

       2.  Select a modern heuristic to solve the problem.

       3.  Present your problem and the algorithm to use.               9/28

       4.  Prepare a grant proposal(Abstract) for supercomputing time.  10/3

           (Discuss with me before submission

           Progress Report: 10/28(F)

       5.  Design and run your parallel program on a parallel computer. November

       6.  Present the experimental results.                            12/9-12

                Alpha:(Ramaraj, Alik, Arun)

                Bravo:(Hay, Block, Crewdson)

                Charlie: (Trotter, Williams, Wan)

       7.  Write a draft of the paper to send to a journal/conference.  12/14

             Submit a paper to a parallel computing journal/conference.

------------------------------------------------------------------------------------------------------

         
                   Grading Policy

        Tutorial            10%

          Peer teaching       10%

          Group project       55%

          Paper (Draft)       10%

          Exam (take-home)    15%

         The exam will be given on December 2 (Fri).

          The due is 10 AM on December 7 (Wed)