CS546 Parallel and Distributed Processing

Instructor: Xian-He Sun

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