CS546 Homework Assignment 2
CS546 Parallel and Distributed Processing
Department of Computer Science
Homework 2 (Due Date: 2/9/2012, Thursday)
- What are the four steps to creat a parallel program?
- Give an anti-dependency example and give a corresponding solution
to remove the dependence.
- For the problem of adding n numbers on a p-processor hypercube (example 5.1 of text),
assume that the base problem for p=1 is adding 512 numbers,
it takes ten time units to communicate a number between two
directly-connected processors, and takes one unit of time to add two numbers,
assuming p increases in power of 2,
- Find the fixed-size (fixed-workload) speedup and comment on the results
- Find the fixed-time speedup and comment on the results
- Find the memory-bound speedup and comment on the results.
- Three algorithms are proposed in
IEEE TC 92
for solving tridiagonal systems.
- Show that the parallel run time of the
PPT algorithm on a p-processor hypercube is the same for both store-and-forward
and cut-through routing schemes
- Give the communication cost of PPT algorithm on a p-processor hypercube
and 2D mesh, respectively.
- Prove, by iso-speed scalability, the PDD algorithm is perfectly scalable
when the number of right side scales with the number of processors.
- Assume a pipeline has p stages with p processors, each stage takes one
unit of time for computing and one unit time to pass the task to the next
stage (communication is one unit of time). There are n tasks to be solved.
Derive the total computing time and communication time for the pipeline
and show the steps of your derivation.
- Exercise 3.2 (Text: Grama, et al, Addison Wesley)
- Exercise 3.16 (Text: Grama, et al, Addison Wesley)
- Exercise 5.1 (Text: Grama, et al, Addison Wesley)
- Read Chapter 3 and 5 of the text book.
Contact Information
- Email: sun at iit dot edu
- Telephone: (312) 567-5260
- FAX: (312) 567-5067
- USMail:
Xian-He Sun
Department of Computer Science
Illinois Institute of Technology
10 West 31st Street
Chicago, IL 60616-3793