How Much Faster Can You Get?

Computer Science Level 2

Running a process on a computer with $n$ -processors does not necessarily reduce the runtime by $n$ folds. Let's try to see how bad this can be at times.

Chris bought a house with 10 rooms: 9 of them are of the same size and the $10^\text{th}$ one is double that size.

Let's say that the time Chris takes to complete painting the entire house all by himself is $a$ units.

Chris realises that $a$ units is pretty long and invites 9 friends over, who work at the same rate as him. (To clarify, we have 10 people working now).

Let's further say that the time all these people take to complete painting the entire house if they are working together simultaneously is $b$ units.

Find the ratio $\dfrac ab$ .

Clarification : The walls are being painted with complex patterns. Not more than one person can work on painting the same room at a time since it is hard for them to coordinate.

This problem was inspired by The Art of Multiprocessor Programing .

The answer is 5.5.

1 solution

Seth Christman
Sep 23, 2016

Assume it takes $x$ units of time to complete one room. Also, let $y$ represent the time it takes to paint the "double" room. We can see that, at the same painting pace, $y = 2x$ . Then $a = 9x + y = 9x + 2x = 11x$ .

Now with 10 people over, lets let each person reside in their own room and not be able to help the other rooms. If they all work at the same pace, then after $x$ units of time, all of the single rooms are finished, and half the double room is finished. One more $x$ units of time later and the 10th man will have finished the double room. This means that $b = 2x$ .

$\dfrac{a}{b} = \dfrac{11x}{2x} = \dfrac {11}{2} = 5.5$

But, nowhere in the problem does it say each person is assigned a room. In fact, it says everyone works simultaneously. So after x time when everyone has finished a room except for the tenth person who has finished half, if everyone works now on that half it will take a tenth of x time to complete. 11x/1.1x=10

Emily Namm - 4 years, 8 months ago

I completely agree with you. Thats how I solved the problem at first. Since this was related to a question involving processors I thought maybe it was meant to imply exclusivity to the rooms. But you bring up a reasonable, and very valid point that I hope gets addressed.

Seth Christman - 4 years, 8 months ago

exactly.......

Anom Ahmed - 4 years, 8 months ago

I agree. I have edited the problem to clarify this point.

The intentened point of this problem was to introduce Amdahl's Law in the context that not all algorithms can be readily parallelized and the non-parallelizable part often poses a challenge to be dealt with.

Agnishom Chattopadhyay - 4 years, 8 months ago

If rooms are cubes then wouldn't the "double room" require eight times the amount of painting?

Jim Jackman - 4 years, 8 months ago

How Much Faster Can You Get?

This problem was inspired by The Art of Multiprocessor Programing .

The answer is 5.5.

1 solution

0 pending reports