Problem Statement
Your boss thinks you can speed up an application you are writing by running it on multiple processors in parallel. Your application performs k independent tasks that each take 1 millisecond to run on a single processor. Distributing a task across several processors does not make it run faster, but running different tasks on different processors may indeed make your application faster.
Unfortunately, when your application runs on more than one processor, communication overheads between processors become a significant factor. In particular, every pair of processors spends overhead milliseconds communicating with each other before work on the tasks can begin. Worse, because the processors share a single bus for communications, different pairs of processors cannot communicate in parallel. For example, if overhead is 2 milliseconds and you run your application on 3 processors, there will be a 6 millisecond delay before the actual computations begin: 2 milliseconds for processors 1 and 2 to communicate, 2 milliseconds for processors 1 and 3 to communicate, and 2 milliseconds for processors 2 and 3 to communicate. Note that, once the initial communications phase has completed, no further communications are required, even if each processor is executing multiple tasks.
Your task is to determine the number of processors that will run the k tasks in the minimum amount of time, assuming overhead milliseconds of communication overhead per pair of processors. If several configurations of processors will achieve the minimum amount of time, prefer the configuration with the smallest number of processors.
Definition
- Class:
- ParallelSpeedup
- Method:
- numProcessors
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int numProcessors(int k, int overhead)
- (be sure your method is public)
Constraints
- k is between 1 and 1000000, inclusive.
- overhead is between 1 and 10, inclusive.
Examples
12
1
Returns: 2
The application runs in 7 milliseconds on 2 processors (1 millisecond of communication and 6 milliseconds for the actual tasks). It also runs in 7 milliseconds on 3 processors (3 milliseconds of communication and 4 milliseconds for the actual tasks). However, we prefer the smaller number of processors.
50
3
Returns: 3
The application runs in 26 milliseconds on 3 processors (9 milliseconds of communication and 17 milliseconds for the tasks). One of the processors actually finishes one millisecond early, after a total of 25 milliseconds, but the application is not considered complete until the last task is finished.
9
10
Returns: 1
3333
2
Returns: 12
1000000
4
Returns: 63
3017
2
Returns: 12
18440
10
Returns: 12
21486
8
Returns: 14
49976
8
Returns: 19
50159
8
Returns: 19
50338
5
Returns: 22
50569
3
Returns: 26
91279
5
Returns: 26
234356
5
Returns: 36
269264
10
Returns: 30
280734
7
Returns: 34
295280
1
Returns: 66
298153
5
Returns: 39
349256
4
Returns: 44
421991
10
Returns: 35
484349
10
Returns: 37
487455
5
Returns: 46
507298
10
Returns: 37
542370
7
Returns: 43
552740
8
Returns: 41
553796
8
Returns: 41
554192
6
Returns: 45
566392
1
Returns: 83
620825
4
Returns: 54
684574
1
Returns: 88
723183
1
Returns: 90
762438
9
Returns: 44
763775
2
Returns: 73
804578
2
Returns: 74
818309
9
Returns: 45
842467
8
Returns: 47
872357
2
Returns: 76
906329
4
Returns: 61
907363
1
Returns: 97
915025
1
Returns: 97
922091
2
Returns: 77
955089
8
Returns: 49
965882
1
Returns: 99
988704
8
Returns: 50
993865
2
Returns: 79
1000000
1
Returns: 100
500
5
Returns: 5
8
8
Returns: 1
8
7
Returns: 1
1000000
1
Returns: 100
1000000
2
Returns: 80
1000000
3
Returns: 69
1000000
4
Returns: 63
1000000
5
Returns: 59
1000000
6
Returns: 55
1000000
7
Returns: 52
1000000
8
Returns: 50
1000000
9
Returns: 48
1000000
10
Returns: 47
21
10
Returns: 1
22
10
Returns: 2
3333
2
Returns: 12
1000000
1
Returns: 100
9746
1
Returns: 22
984571
6
Returns: 55
899999
1
Returns: 96
1000000
4
Returns: 63
1000000
9
Returns: 48
5
2
Returns: 1
40
3
Returns: 2
4
1
Returns: 2
3
1
Returns: 1
1
2
Returns: 1
1000000
7
Returns: 52
2
4
Returns: 1
31602
8
Returns: 16
2
1
Returns: 1