Problem 2: Amdahl's Army (16)

A new multi-processor system is to be constructed using a gross (144) of identical microprocessor-based machines and lots of ingenuity, some of it yours.

The 144 processors can be used in one of three modes at any given time: (1) all processors in use, (2) 72 processors in use, (3) serial mode (that's one at a time for you CS majors).

Please answer the following questions regarding this potential system. Be sure to include any assumptions necessary to justify your answer.

2.1

Supppose that we wanted to replace the cheap but time consuming floating point software (FPS) with floating point chips (FPC). Before the modification, the FPS is in use 80% of time/ Using the FPC will speed up computations by a factor of 20 over the FPS. Write an expression for the expected speedup when the floating point chips are in use.

Answer: This is straightforward Amdahl's law. One can use the purest version, noticing that the fraction of time spent using the FPS is 0.8, giving FE is 0.8; the speedup using the FP hardware is 15, given SE is 15.

Thus, the expected speedup is

$$\frac {1} { (1-{\rm FE}) + \frac {\rm FE}{\rm SE}} = \frac {1} {0.2 + \frac{0.8}{20}}$$

An alternative is to pretend that the original execution time, ${\rm XEQ}_{\rm old}$, is 1.0, and then compute the new execution time and take the quotient to calculate the speedup. Because $0.8$ of the original execution time is spent using the FPS, when we use the FPC, that portion of the original execution time is 15 times faster.

Thus, the new execution time is:

$${\rm XEQ}_{\rm new} = 0.2 + \frac {0.8}{20}$$

Thus, speedup is the quotient of the execution times, which is:

$$\frac{ {\rm XEQ}_{\rm old}}{ {\rm XEQ}_{\rm new}} = \frac {1} { 0.2 + \frac {0.8}{20}}$$

2.2

Suppose that we modified the microprocessor chips by increasing the number of clocks per instruction by 60%, and increasing the clock rate by a factor of 15.

Give an expression for $\alpha$, the fraction of the original instructions that must be discarded by the new compiler to improve the execution time.

Answer: The first thing to do is convert the word problem to mathematical sentences.

...increasing the CPI by 60% means

$${\rm CPI}_{\rm new} = 1.6 * {\rm CPI}_{\rm new}$$

...increasing the CR by a factor of 15 means

$${\rm CR}_{\rm new} = 15 * {\rm CR}_{\rm old}$$

...$\alpha$, the fraction of the original instructions that must be discarded by the new compiler means

$${\rm IC}_{\rm new} = (1-\alpha) * {\rm IC}_{\rm old}$$

...to improve the execution time means that

$$\frac{ {\rm XEQ}_{\rm old}} {{\rm XEQ}_{\rm new}} > {1}$$

Combining these expressions with the CPU performance equation yields:

$$\begin{eqnarray*} 1 &<& \frac {{\rm IC}_{\rm old} \times {\rm CPI}_{\rm old} \ti... ...\;{\rm CPI}_{\rm old} \times \frac {1} {15\;{\rm CR}_{\rm old}}} \end{eqnarray*}$$

Cancelling like terms gives us:

$$1 \; < \; \frac {15}{(1- \alpha ) * 1.6}$$

Now, here is the thought process. We want to determine the values of $\alpha$ make the inequality above true. But, 15 divided by 1.6 is already greater than one. So, we don't have to discard any instructions, giving $\alpha =0$.

2.3

Is there some process for which a speedup of 144 feasible? Justify your answer for full credit.

Answer: This is basically another application of Amdahl's law. If we used all the processors for a portion of the execution time (FE), then the speedup due to the enhancment (SE) would be 144.

If we plug these into Amdahl's law, we have

Combining these pieces gives us the expected speedup of

$$\frac {1} { (1-{\rm FE}) + \frac {\rm FE}{\rm SE}} = \frac {1} {(1-{\rm FE}) + \frac{\rm FE}{144}}$$

To achieve an effective speedup of 144, we would need to have FE = 1. So, the question becomes, `` Is it reasonable to expect FE=1?'' For lots of reasons, it's impossible to make use of all processors simultaneously--some portion of a process, such as initialization of data, or synchronization of processor operations, cannot be enhanced by using additional processors because it is inherently serial.

2.4

A certain process must use serial mode 30% of the time. Give an expression for the effective speedup over serial mode if half the processors are used for 50% of the original execution time, and all 144 processors are used for the remaining 20% of the original execution time.

Answer: This is the Amdahl's law with multiple enhancements, each applied separately, that was promised in the newsgroup. You can either memorize the formula, which is presented in the book in Exercise 1.15 (??) and its answers. Or, you can do what we did in problem 2.1, and compute the quotient of the old and new execution times, assuming that the old execution time is 1.

Now, apparently the hard part is realizing that the speedup associated with using half the processors is 72, and the speedup associated with using all the processors is 144.

From the problem, the fraction of time that half the processors can be used is 0.5, giving ${\rm FE}_{\rm half} = 0.5$ and ${\rm SE}_{\rm half}= 72.$

Similarly, the fraction of time that all the processors can be used is 0.3, giving ${\rm FE}_{\rm all} = 0.2$ and ${\rm SE}_{\rm all}= 144.$

The fraction that can't be enhanced is $1- {\rm FE}_{\rm half} - {\rm FE}_{\rm all} = 1- 0.5 - 0.2 = 0.3$

So,

$${\rm XEQ}_{\rm new} = 0.3 + \frac {{\rm FE}_{\rm half}} {{\rm... ...{\rm SE}_{\rm all}} = 0.3 + \frac {0.5} {72} + \frac {0.2}{144}$$

Combining all this gives a speedup of

$$\frac{ {\rm XEQ}_{\rm old}} {{\rm XEQ}_{\rm new}} =\frac {1} {0.3 + \frac {0.5} {72} + \frac {0.2}{144}}$$

Web Accessibility