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

When discussing how to assign tasks to threads and how to choose a task size (granularity measure), Professor Kayvon mentioned that we could run into the above problem where the longer tasks are scheduled last in which case we would have to wait for a long time (some of it will be serially run). We could fix this by breaking the tasks into smaller ones to avoid having longer tasks or by scheduling the longer ones first - though we need to watch out for dependencies amongst tasks -.


If the system assigns these left to right, then it will distribute each of the small blocks of work fairly evenly across the N threads until the last one. Then, the large block will need to be placed on one of these threads that are all about evenly balanced before. The time it takes to execute this will increase by about the time it takes for a thread to process the large block.


I guess the takeaway for this slide is that we'd rather deal with the large tasks first, because even if imbalance happens, the remaining tasks can still occupy the other threads; on the other hand, if we schedule the smaller tasks first, then eventually the huge task would be the only one running in the system, seriously hurting parallelism.


Note that the x axis indicates the order in which the tasks are assigned to different threads. Originally, I was a bit confused by the depiction of the tasks by the graph because I thought this graph is showing how all workers are being ran at the same time by 16 different threads. And after understanding what the graph actually meant, what others said before made sense.