Sequential processing

Comment 3:

What exactly is “sequential processing”?

Follow-up:

Sequential processing refers to those computations that can only be handled by one single processor. Putting in more processors does not help. For example, in a typical parallel or multi-task program, there are some “managerial” tasks to be carried out. One most commonly encountered task is the division of the whole job into pieces. Specifically, if we consider an image processing task, dividing up the image into pieces is one such managerial task. Obviously, this action is not parallelizable.

Can you think about some daily life examples of sequential processing task?

Sequential mode or parallel mode?

Problem:

A uniprocessor computer can operate in either sequential mode or parallel mode. In parallel mode, computations can be performed nine times faster than in sequential mode. A certain benchmark program took time T to run on this computer. Furthermore, suppose that 25% of T was spent in parallel mode whereas the remaining portion was in sequential mode.

(a) What is the effective speedup of the above execution as compared with the condition when parallel mode is not used at all?
 
(b) What is the fraction α of parallelized code of the benchmark program?

(c) Suppose we double the speed ratio between parallel mode and the sequential mode by hardware improvements. What is the new effective speedup?

(d) Suppose the speedup you calculated in (c) is to be obtained by software improvement alone in terms of parallelization fraction, instead of by any hardware improvement. What is the new parallelization fraction required?

Follow-up:

(a) If parallel mode is not used at all, the execution time will be 0.75T + 9 × 0.25T = 3T .
Therefore, the speedup of the program is 3T ⁄ T = 3 .

(b) The fraction of parallelized code is given by:

(c) The new execution time now becomes:

And the new speedup is:

(d) Parallelization in general is done by the compiler (an important piece of software for translating your program into machine language). Since the new speedup is to be obtained by software instead of hardware, the speed of parallelized code is still 9 times faster than sequential mode. Let β be the new parallelization fraction. Then, we have:

 

Thus, we have

That is, the compiler has to parallelize 5% more of the benchmark program.