Statistics

Problem Statement for "MultiprocessorProgramming"

Problem Statement

As multiprocessor computers become more widespread in our lives, it becomes more and more important to write parallel programs that can solve tasks using several processors.

However, designing parallel programs is difficult for many reasons. Let us consider two of them. First, some amount of work cannot be parallelized and must therefore be executed on a single processor. Besides that, when increasing the number of processors, the amount of work needed for synchronization increases. We will assume that there is one special processor that controls the execution and executes the unparallelizable part, and that the increase in time due to synchronization is linear in the number of processors.

You are given ints t0, tp, and ts. t0 is the number of seconds needed for the execution of the unparallelizable part. tp is the number of seconds needed for execution of the parallelizable part on a single processor. ts is the number of seconds added to the synchronization time for each additional processor.

The time needed to execute the whole task on one processor is t0+tp. The time needed to execute the whole task on n > 1 processors is max(t0, tp/(n-1) + ts*(n-1)). Here tp/(n-1) is a floating point number. Return the number of processors needed to execute the task in minimal time. If there are multiple solutions, return the smallest among them.

Definition

Class:
MultiprocessorProgramming
Method:
optimalNumberOfProcessors
Parameters:
int, int, int
Returns:
long
Method signature:
long optimalNumberOfProcessors(int t0, int tp, int ts)
(be sure your method is public)

Constraints

  • t0 will be between 1 and 109, inclusive.
  • tp will be between 1 and 109, inclusive.
  • ts will be between 1 and 109, inclusive.

Examples

  1. 1

    10

    1

    Returns: 4

    In this case the optimal number of processors is 4. The time needed to complete the task is max(1,10/3+1*3)=19/3.

  2. 8

    10

    1

    Returns: 3

    In this case the unparallelizable part is too large, so the optimal number of processors is 3. The time needed to complete the task is max(8,10/2+1*2)=8.

  3. 1

    10

    5

    Returns: 1

    In this case synchronization is too difficult, so parallelization is unreasonable.

  4. 1

    1000000000

    1

    Returns: 31624

  5. 1000

    999

    1

    Returns: 2

  6. 1000

    1000

    999

    Returns: 2

  7. 81

    58

    8

    Returns: 2

  8. 612

    2

    8

    Returns: 2

  9. 247

    76

    70

    Returns: 2

  10. 8056

    4788

    10

    Returns: 2

  11. 7090

    5099

    60

    Returns: 2

  12. 7403

    5370

    640

    Returns: 2

  13. 57974

    68011

    6

    Returns: 3

  14. 64128

    11161

    94

    Returns: 2

  15. 43686

    49526

    882

    Returns: 3

  16. 88656

    64260

    5275

    Returns: 2

  17. 607883

    369740

    3

    Returns: 2

  18. 416520

    831568

    3

    Returns: 3

  19. 321329

    655719

    405

    Returns: 4

  20. 963804

    929852

    8751

    Returns: 2

  21. 667946

    990363

    10426

    Returns: 3

  22. 4511786

    5711700

    9

    Returns: 3

  23. 4314183

    2907204

    25

    Returns: 2

  24. 9506894

    7914971

    98

    Returns: 2

  25. 2975459

    2772130

    9388

    Returns: 2

  26. 7639165

    1657374

    34988

    Returns: 2

  27. 2642001

    1222618

    250963

    Returns: 2

  28. 10029649

    44482369

    7

    Returns: 6

  29. 63348534

    15864854

    5

    Returns: 2

  30. 87340276

    95080908

    634

    Returns: 3

  31. 30611580

    57017451

    734

    Returns: 3

  32. 15459890

    93521237

    57837

    Returns: 8

  33. 41747210

    45715858

    770616

    Returns: 3

  34. 7969643

    71218675

    1733237

    Returns: 7

  35. 352974246

    164429534

    6

    Returns: 2

  36. 201814298

    899959279

    47

    Returns: 6

  37. 795506370

    172884987

    282

    Returns: 2

  38. 531993718

    794543610

    5760

    Returns: 3

  39. 6404522

    427863884

    94347

    Returns: 68

  40. 55317727

    594560067

    402872

    Returns: 13

  41. 129280568

    600000746

    7882576

    Returns: 10

  42. 79802243

    402598517

    7120470

    Returns: 9

  43. 906216104

    927811713

    871

    Returns: 3

  44. 123910816

    451871627

    213

    Returns: 5

  45. 183361388

    778040178

    53

    Returns: 6

  46. 483848882

    643713062

    17

    Returns: 3

  47. 41796044

    397391667

    24

    Returns: 11

  48. 17628628

    759013518

    28

    Returns: 45

  49. 85679555

    893834648

    1

    Returns: 12

  50. 447186548

    887686544

    3

    Returns: 3

  51. 722215221

    834312405

    4

    Returns: 3

  52. 333511935

    978922496

    7

    Returns: 4

  53. 627080187

    776429229

    4

    Returns: 3

  54. 542659399

    806221805

    1

    Returns: 3

  55. 407439524

    698316020

    3

    Returns: 3

  56. 491964889

    903776156

    3

    Returns: 3

  57. 203307414

    588935199

    3

    Returns: 4

  58. 288181302

    405131831

    1

    Returns: 3

  59. 268150757

    625732579

    2

    Returns: 4

  60. 870482749

    895757080

    3

    Returns: 3

  61. 13617080

    901883228

    1

    Returns: 68

  62. 226946144

    822039352

    2

    Returns: 5

  63. 617412000

    732662830

    1

    Returns: 3

  64. 92612640

    588405357

    1

    Returns: 8

  65. 827068480

    879592708

    1

    Returns: 3

  66. 268356415

    557715043

    1

    Returns: 4

  67. 568940146

    863127854

    1

    Returns: 3

  68. 164057265

    721737293

    1

    Returns: 6

  69. 639926378

    715111455

    1

    Returns: 3

  70. 676591057

    937519782

    1

    Returns: 3

  71. 665133317

    809692458

    1

    Returns: 3

  72. 737658304

    874418307

    1

    Returns: 3

  73. 257378767

    909354792

    1

    Returns: 5

  74. 300

    5000

    2

    Returns: 21

  75. 1000000000

    1000000000

    1000000000

    Returns: 1

  76. 1000000000

    1000000000

    54545555

    Returns: 3

  77. 454

    455555555

    2222

    Returns: 454

  78. 105455511

    10045445

    2222

    Returns: 2

  79. 25

    100

    1

    Returns: 6

  80. 1

    12347628

    23884854

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: