With K processor cores, how to optimally split N jobs into groups, with each group to be processed sequentially by one processor core, when the time to process each job is unknown ahead of time and there is overhead associated with processing each group of jobs?
It is possible to kill a job group before it completes, but then no useful processing progress will be extracted from that job group.
If I just make each group size 1, add them to a queue, and process K of them at once, then the overhead can dominate the total time. If I split them into K equal sized groups, then the overhead can still dominate the total time and I could get unlucky and have all the slowest jobs in one group further slowing things down.
Is this an example of a general well studied problem with an understood algorithm to optimally process?
For example, suppose I have 326400 jobs, 32 cores, and about 5 seconds overhead associated with processing a group.
- 3,200 big jobs take 2 minutes each to process if done in four separate groups
- 3,200 medium jobs take 1 minute each to process if done in four separate groups
- the remaining 320,000 small jobs take about 5.001 seconds each to process if done in 320,000 separate groups.
- for the 5.001 seconds for the small jobs, 1 millisecond is due to the processing and 5 seconds is due to the overhead of processing any group. if all the small jobs are done in one group, it takes 325 seconds to process total due to sharing the overhead (320,000 * 1 millisecond + 5 seconds = 325 seconds)
If I just made each group size 1, put the groups in a queue, and ran 32 at a time concurrently on 32 cores, and happened to pick the 3,200 biggest jobs from the queue first, then the 3,200 medium jobs from the queue, it would take 200 minutes for the big jobs to finish, 100 minutes for the medium jobs to finish, and 833.5 minutes for the small jobs to finish: 18 hours total.
Optimally I would process the biggest jobs first (1 job per group), then the medium jobs (1 job per group), then split the remaining small jobs into 32 groups for a total of about 5 hours total to finish.
I am hoping that there is some well studied algorithm that I am ignorant of that handles this situation well.