Optimize machines for distributed merging cost
Optimize Machines for Distributed Merging Cost
Problem Description
You are tasked with optimizing the runtime of a distributed computation. A dataset of size n is to be processed by splitting it across k identical machines.
The total runtime T(k) is determined by two primary factors:
- Per-machine compute: When the dataset is evenly partitioned, the compute cost per machine is
O(n/k). - Merge cost: The cost to merge the
kpartial results back together isO(k^2). - Other overheads are considered negligible.
The total runtime is given by the formula: T(k) = O(n/k + k^2).
Question
Determine the value of k that approximately minimizes the total runtime T(k).
Choose the best option from the following:
- A) around 10
- B) around log₂ n
- C) around square root of n
- D) around n/2
AI interview prep
Core dilemma
Balancing the benefits of increased parallelism (reduced per-machine work) against the escalating overheads of coordination and merging in a distributed system, specifically finding the optimal number of machines (k) that minimizes total runtime.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Optimize machines for distributed merging cost
Optimize Machines for Distributed Merging Cost
Problem Description
You are tasked with optimizing the runtime of a distributed computation. A dataset of size n is to be processed by splitting it across k identical machines.
The total runtime T(k) is determined by two primary factors:
- Per-machine compute: When the dataset is evenly partitioned, the compute cost per machine is
O(n/k). - Merge cost: The cost to merge the
kpartial results back together isO(k^2). - Other overheads are considered negligible.
The total runtime is given by the formula: T(k) = O(n/k + k^2).
Question
Determine the value of k that approximately minimizes the total runtime T(k).
Choose the best option from the following:
- A) around 10
- B) around log₂ n
- C) around square root of n
- D) around n/2