Suppose that a given architecture does not have hardware support for multiplicat

Question

Suppose that a given architecture does not have hardware support for multiplication, so multiplications have to be done through repeated addition, as was the case on some early microprocessors. Assume it takes 200 cycles to perform a multiplication in software, and 4 cycles to perform a multiplication in hardware. What is the overall speedup of the program when multiplications are done in hardware if: a. 10 percent of the program execution is spent in doing multiplications? b. 40 percent of the program execution is spent in doing multiplications?

Explanation / Answer

Hi,

This can be solved using Amdahl's Law. Amdahl's Law states that the performance improvement to be gained from using some faster mode of execution is limited by the fraction of time the faster mode can be used.

In other words, the impact of a given improvement on overall performance is dependent on both:

- when an improvment is in use, how much it improves the performance.

- how often the improvement is in use.

This can be expressed by Amdahl's Law as:

NewExecTime = OldExecTime * [UnusedTimeFraction + UsedTimeFraction/SpeedUpByUsing], where

OldExecTime is the older time of execution when improvement was not in use, UnusedTimeFraction is the fraction of time when the improvement was not in use, UsedTimeFraction is the fraction of time when improvement is in use, and SpeedUpByUsing is the speedup that occurs when improvement is used.

Now, Speedup = OldExecTime/NewExecTime

Applying above formula, Speedup = OldExecTime/ OldExecTime * [UnusedTimeFraction + UsedTimeFraction/SpeedUpByUsing]

which implies Speedup = 1/ [UnusedTimeFraction + UsedTimeFraction/SpeedUpByUsing] ----> Eq1

Now for the given question,

Given OldExecTime = 200 (Multiplications done in software)

NewExecTime = 4 (Multiplication done in hardware)

So, Speedup by using improvement, SpeedupByUsing = OldExecTime/NewExecTime = 200/4 = 50

(a.) 10 percent of the program execution is spent in doing multiplications,

UnusedTimeFraction = 1-10% = 1-0.1 = 0.9

UsedTimeFraction = 10% = 0.1

So putting these values in above formula (Eq1), Speedup = 1/(.9+.1/50) = 1.108647 = 1.11

(b.) 40 percent of the program execution is spent in doing multiplications,

UnusedTimeFraction = 1-40% = 1-0.4 = 0.6

UsedTimeFraction = 40% = 0.4

So putting these values in above formula (Eq1), Speedup = 1/(.6+.4/50) = 1.644737= 1.64

Thanks

If you have any queries regarding this, feel free to ask. :)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.