Question: Can someone describe how the system got itself into a situation of poor work balance here?
paluri
@kayvonf Assuming that the algorithm was attempting to maintain a balance at all times, it fell victim to one of the downfalls of greedy algorithms. As evidenced by this example, when dividing tasks among processors and tasks can be of variable length, it is certainly not necessarily guaranteed that maintaining as perfectly balanced a load as possible will result in the overall lowest latency from start to finish of all tasks. If the scheduler had some knowledge about upcoming tasks, it could have avoided such an unfortunate result.
kayvonf
And specifically, the "unfortunate" result is that that last task processed by the system was a very long one. Since there is no other work to do, while that long task is running, the other cores are idle. Contrast this to the next slide where there are other tasks for the other cores to work on while the long task is running.
Question: Can someone describe how the system got itself into a situation of poor work balance here?
@kayvonf Assuming that the algorithm was attempting to maintain a balance at all times, it fell victim to one of the downfalls of greedy algorithms. As evidenced by this example, when dividing tasks among processors and tasks can be of variable length, it is certainly not necessarily guaranteed that maintaining as perfectly balanced a load as possible will result in the overall lowest latency from start to finish of all tasks. If the scheduler had some knowledge about upcoming tasks, it could have avoided such an unfortunate result.
And specifically, the "unfortunate" result is that that last task processed by the system was a very long one. Since there is no other work to do, while that long task is running, the other cores are idle. Contrast this to the next slide where there are other tasks for the other cores to work on while the long task is running.