Minimize Max GPU Workload
At Nvidia, optimizing resource utilization is crucial for maximizing throughput in parallel computing. Imagine you have a set of computational tasks, each with a specific complexity (representing the time it takes to complete). You need to distribute these tasks across a limited number of GPUs. The goal is to minimize the maximum workload any single GPU has to handle, ensuring efficient and balanced utilization of your hardware.
This problem challenges you to find the most efficient way to assign tasks to GPUs such that the heaviest loaded GPU has its workload minimized. This is a common optimization pattern in distributed systems and resource scheduling.
Implement the function minimizeMaxWorkload that takes an array of task complexities and the number of available GPUs, and returns the minimum possible value for the maximum workload on any single GPU.
Constraints for task assignment:
taskComplexities = [t1, t2, t3, t4] and you assign t1 and t2 to GPU1, then t3 must be assigned to GPU2 (or subsequent GPUs), not GPU1. You cannot reorder tasks.Function Signature:
function minimizeMaxWorkload(taskComplexities: number[], numGPUs: number): number;
Parameters:
taskComplexities: An array of numbers, where taskComplexities[i] represents the complexity (time) of the i-th task.numGPUs: A number representing the total number of GPUs available.Return Value:
number representing the minimum possible value for the maximum workload on any single GPU across all valid task distributions.taskComplexities is empty, the maximum workload is 0.numGPUs will always be at least 1.Examples
Example 1
Input:
taskComplexities = [10, 20, 30, 40], numGPUs = 2
Output:
60
Note:
If GPU1 takes tasks [10, 20, 30] (total 60) and GPU2 takes [40] (total 40), the maximum workload is 60. It's not possible to achieve a maximum workload less than 60 with 2 GPUs while maintaining task order. For example, a max workload of 50 would require GPU1 to take [10, 20] (30), then GPU2 would need to take [30, 40] (70), which exceeds 50.
Example 2
Input:
taskComplexities = [1, 2, 3, 4, 5], numGPUs = 5
Output:
5
Note:
With 5 GPUs, each task can be assigned to its own GPU. The maximum workload will be the largest single task, which is 5.
Example 3
Input:
taskComplexities = [1000000000, 1000000000, 1000000000], numGPUs = 1
Output:
3000000000
Note:
All tasks must be assigned to the single GPU. The total workload will be the sum of all task complexities.
Example 4
Input:
taskComplexities = [1, 1, 1, 1, 100], numGPUs = 2
Output:
100
Note:
One optimal distribution is: GPU1 takes [1, 1, 1, 1] (total 4), and GPU2 takes [100] (total 100). The maximum workload is 100.
Constraints
1 <= taskComplexities.length <= 10^51 <= taskComplexities[i] <= 10^91 <= numGPUs <= taskComplexities.lengthtaskComplexities can exceed the standard 32-bit integer limit, so use 64-bit integers or JavaScript's number type which handles large integers up to 2^53 - 1 safely for sums, and 10^9 for individual tasks. The maximum possible sum is 10^5 * 10^9 = 10^{14}, which fits within JavaScript's safe integer range.Loading editor...