COP2500 Assignment 15

Deliverables: To complete this assignment you must perfom three tasks --

  1. Perform two experiments that simulate parallel processes.
  2. Answer the questions below by editing this file.
  3. Turn in your HTML document to your instructor.

Introduction: We don't have to have access to parallel computers to investigate how parallel processing works. We can simulate parallel processing. We will assume the processors are connected together in a tree structure like the examples in class (Figure 1). Remember there are five stages to a parallel process:

  1. (Cost) Divide problem and distribute to remote processors.
  2. (Cost) Initiate remote processes.
  3. (Benefit) Perform the parallel computation.
  4. (Cost) Transmit local results to a single processor.
  5. (Cost) Combine local results into a complete single result

Figure 1: Five stages of parallel processing flowing through a tree architecture.
In this lab you will investigate the trade offs between communication costs and speed up obtained when more than one processor is used to solve a problem. Use the form on the left to specify how many processors you want to use to solve a problem, the cost of communication between two processors, and the overall cost of the problem. You will do two experiements, listed below in the Questions section.
Number of Processors Used to solve the Problem
Transmission Cost Between Layers
Total Computation Cost
Cost to Distribute the Problem
Cost to Start up Remote Processes (we'll assume zero.)
Cost to Comput Local Solutions
Cost to Send Local Solutions to Central Processor
Cost to Consolidate Answer (we'll assume zero)
Total Cost:

Questions:


Part 1: Use a communication cost of 5 and overall computation cost of 1000.
1.) What is the overall cost computed when one processor is used?
2.) What is the overall cost computed when 2 processors are used to solve the problem?
3.) Keep doubling the number of processors used. What number gives the best total cost?
4.) Keep doubling the number of processors used. At what point is the total cost worse than when 1 processor was used? Why would adding more processors cost more?

Part 2: Use a communication cost of 250 and overall computation cost of 1000.
1.) What is the overall cost computed when one processor is used?
2.) What is the overall cost computed when 2 processors are used to solve the problem?
3.) Keep doubling the number of processors used. What number gives the best total cost?
4.) Keep doubling the number of processors used. At what point is the total cost worse than when 1 processor was used? What does this tell you about parallel processing in situations where communication costs are high?