Problem - Running parallel applications using cloud resources.

Consider the figure below that shows a parallel application that consists of 3 processing phases:

1. n identical tasks execute in parallel, each requiring Ta units of computation.

2. a sequential task that executes after all tasks in Phase 1 complete and requires Ts units of computation

3. m identical tasks execute in parallel requiring Tb units of computation each; these tasks can only start after the sequential task completes. Consider that the tasks run on virtual machines leased from a cloud provider (ex. Amazon EC2).

The table shows 4 VM types available from the cloud provider, the price/sec for each, and their relative speed.

For example, VM type 1 is the slowest and VM type 4 is 8 times faster than VM type 1. The times Ta, Ts, and Tb are relative to VMs of type 1. Let S (i) be the relative speed of VM of type i and let P(i) be the price/sec for VMs of type i.

Ex. S(3) = 4 and P(3) = $0.000110556/sec.

Sequence:

Answer the following:

I. Give an expression for the total time T to execute the parallel application described above assuming that VMs of type s are used for phase 1, a VM of type t is used for the sequential task, and VMs of type u are used for Phase 3. The expression should be a function of Ta, Ts, Tb, S(s), S(t), and S(u).

II. Give an expression for the total cost C to execute the parallel application described above assuming that VMs of type s are used for Phase 1, a VM of type t is used for the sequential task, and VMs of type u are used for Phase 3. The expression should be a function of Ta, Ts, Tb, S(s), S(t), S(u), m, and n.

III. Assume that n = 200, m = 150, Ta = 25,000 computations, Ts = 100,000 computations, and Tb = 50,000 computations Use the numbers in the table above to compute the execution time and corresponding cost of the application using the fastest VMs. Provide your explanation and show calculations.

IV. Using the same numbers as above, compute the execution time and corresponding cost of the application using the slowest VMs. Provide your explanation and show calculations.

V. Compare your answers to items III. and IV. above and explain your conclusions.

Tb Ta VI IX. Relative speed (computations/sec) Ta price/sec ( 0.000027778 0.000055278 0.000110556 0.000221111 VM type Ts Ta XI. 4 Tb Tb Ta VI IX. Relative speed (computations/sec) Ta price/sec ( 0.000027778 0.000055278 0.000110556 0.000221111 VM type Ts Ta XI. 4 Tb