Monday, February 23, 2015

ParallelSpeedup

Problem:

TopCoder Problem Statement - ParallelSpeedup
Single Round Match 165 Round 1 - Division I, Level One
Single Round Match 165 Round 1 - Division II, Level Two

Overview:

Determine the number of processors that will finish a job in the shortest amount of time. Additional processors will help divide the load, but incur an exponential communication cost.

Java Source:
01: public class ParallelSpeedup {
02: 
03:     private static final int MAX_PROCESSORS = 1_000_000;
04: 
05:  public int numProcessors(int k, int overhead) {
06: 
07:         // Time it takes for 1 processor.
08:         long fastest = k;
09: 
10:         for (int processors = 2; processors <= MAX_PROCESSORS; processors++)  {
11: 
12:             // Calculate the communications overhead
13:             long o = ((processors * (processors - 1)) / 2) * overhead;
14: 
15:             /*
16:              * Total time is the overhead, plus the number of tasks divided
17:              * by the number of processors.
18:              */
19:             long time = o + (k / processors);
20: 
21:             /*
22:             * If the number of tasks does not divide evenly by the number
23:             * of processors, then we'll need 1 extra ms to finish the remaining
24:             * tasks.
25:             */
26:             if (k % processors != 0) time += 1;
27: 
28:             /*
29:             * As soon as time levels out or begins increasing, stop
30:             * and return the previous number of processors.  From here
31:             * on, time will keep increasing.
32:             */
33:             if (time >= fastest) return processors - 1;
34: 
35:             // record our new fastest time.
36:             fastest = time;
37: 
38:         }
39: 
40:         // Should never reach here.
41:         return -1;
42: 
43:  }
44: }
Notes:

The approach taken here is to calculate the time it takes to solve the problem using one processor, and then add additional processors until the time stops decreasing. There are two forces at work here. Each additional processor helps us by spreading the load. Whenever the number of processors doubles, the amount of time it takes to process the job is cut in half. As the number of processors grows, the gains diminish.

On the other hand, with additional processors, the communication overhead increases at an exponential rate. ((p * (p-1) / 2) * overhead Eventually, the cost of the communication overhead must overcome the benefit of additional processors. From that point on, additional processors will only slow the task down. Therefore, we can quit as soon as the time levels out or starts to become larger.

The time it takes to process the job is the communication overhead, plus the number of tasks divided by the number of processors. If the number of tasks does not divide evenly by the number of processors, then one extra round will be needed to complete those remainders.

Note that if the number of processors gets very large, it is likely that the values of o and time will overflow. By returning as soon as time begins increasing, this problem is avoided. Also note, that we can set the initial upper limit for the fastest time to k - that is the amount of time it would take 1 processor to handle k tasks.

No comments:

Post a Comment