Does a scheduling algorithm like work scheduling work better for cases where we know the tasks up front, or only in cases where tasks are dynamically created by recursive calls for example?
crow
If you know the tasks up front, it may be possible to prefetch instructions and data, which speeds up computation.
kayvonf
@crow. That is true. Another implication of knowing the tasks up front is that the assignment of tasks to threads can be done efficiently so the system does not suffer from work imbalance. More on that next week.
firebb
Actually we could start with statically assigning the tasks to each worker (equal in number). It is possible that each task may take different time. Thus even each worker is assigned the same number of works, it is possible some of the workers may finish their jobs faster than the others. We could solve this problem by the smart idea of Work Stealing. The basic idea is to let the workers already done their jobs steal some tasks from the busy ones.
bazinga
When an enormous number of pthreads are spawned (number of pthreads >> number of available CPU cores), OS-level context switching overhead shoots up considerably and starts limiting the achievable speedup.
mumen_rider
It seems dynamic assignment has much better work balance than static assignment. By creating tasks of reasonable size, threads that finish a task can continue working and never be idle. However, in static assignment, the "tasks" are set in stone and thus often will lead to work imbalances and idle time.
Penguin
Finding a "reasonable" size is not always easy, however, because although smaller tasks lets you distribute the work more evenly, they also make the overhead for switching between them a greater portion of the overall program.
rav
As observed in Assignment 3 and the OpenMP, it is quite interesting to play with the chunk size with the dynamic schedule option in the #pragma openmp for. Making the chunk size too small, makes the scheduling/switching overhead dominate, whereas making it too big gives you less control over the workload balancing.
nishadg
Does dynamic assignment just use a greedy assignment algorithm? Or does it take into account the size/work associated with the tasks?
Does a scheduling algorithm like work scheduling work better for cases where we know the tasks up front, or only in cases where tasks are dynamically created by recursive calls for example?
If you know the tasks up front, it may be possible to prefetch instructions and data, which speeds up computation.
@crow. That is true. Another implication of knowing the tasks up front is that the assignment of tasks to threads can be done efficiently so the system does not suffer from work imbalance. More on that next week.
Actually we could start with statically assigning the tasks to each worker (equal in number). It is possible that each task may take different time. Thus even each worker is assigned the same number of works, it is possible some of the workers may finish their jobs faster than the others. We could solve this problem by the smart idea of Work Stealing. The basic idea is to let the workers already done their jobs steal some tasks from the busy ones.
When an enormous number of pthreads are spawned (number of pthreads >> number of available CPU cores), OS-level context switching overhead shoots up considerably and starts limiting the achievable speedup.
It seems dynamic assignment has much better work balance than static assignment. By creating tasks of reasonable size, threads that finish a task can continue working and never be idle. However, in static assignment, the "tasks" are set in stone and thus often will lead to work imbalances and idle time.
Finding a "reasonable" size is not always easy, however, because although smaller tasks lets you distribute the work more evenly, they also make the overhead for switching between them a greater portion of the overall program.
As observed in Assignment 3 and the OpenMP, it is quite interesting to play with the chunk size with the dynamic schedule option in the #pragma openmp for. Making the chunk size too small, makes the scheduling/switching overhead dominate, whereas making it too big gives you less control over the workload balancing.
Does dynamic assignment just use a greedy assignment algorithm? Or does it take into account the size/work associated with the tasks?