Previous | Next --- Slide 16 of 64
Back to Lecture Thumbnails

Load imbalance occurs because the most computationally intensive task is scheduled at the end, causing a decrease in efficiency as all the other cores will complete their tasks before the core with the difficult task. Ideally this task can be subdivided into smaller tasks or it can be scheduled at the beginning to reduce the load imbalance issue.


One thing to note here is that the scheduler reached a state of an imbalance of work due to the fact that it was making an optimal decision at each step independent of the other steps. If the scheduler had some prior knowledge of the upcoming tasks, then it could have avoided this situation.


This online algorithmic task of distributing work as evenly as possible among a set of workers is known as the makespan (or job shop scheduling) problem. Though often difficult to compute the optimal solution, the sorted greedy algorithm proposed on the next slide can be shown to be a 1.5-approximation of this optimal scheduling order.