Question

Suppose a program segment consists of a purely sequential part which takes 100 cycles to execute, and an iterated loop which takes 400 cycles per iteration. Assume that the loop is dependent on the sequential part, i.e., both parts cannot run in parallel. Also assume that the loop iterations are independent, and cannot be further parallelized. If the loop is to be executed 100 times, what is the maximum speedup possible using an infinite number of processors (as many processors as you could possibly need) compared to a single processor?

Answer 1

The maximum speedup possible with an infinite number of processors compared to a single processor is 80.2, by parallelizing the loop iterations and keeping the sequential part unchanged.

Step-by-step explanation:

In the scenario described, we're asked to determine the maximum speedup possible using an infinite number of processors compared to a single processor. The program segment includes a sequential part requiring 100 cycles and an iterated loop that is independent and takes 400 cycles per iteration, with the loop running 100 times.

Firstly, the sequential part of the program cannot be parallelized and must run on its own, taking 100 cycles. However, the loop iterations can be run concurrently.

With an infinite number of processors, all iterations of the loop could theoretically run at the same time, meaning the total time for the loop would be the time for one iteration (400 cycles), irrespective of the number of iterations.

To calculate speedup, we use the formula S = Tserial / Tparallel. Here, Tserial would be the time taken by the sequential part plus the time for all iterations of the loop when running on a single processor (100 + 400 * 100 = 40,100 cycles), and Tparallel would be the time taken by the sequential part plus the time for a single iteration of the loop (100 + 400 = 500 cycles).

Therefore, the maximum speedup is 40,100 cycles divided by 500 cycles, which gives us a speedup of 80.2.