Is there any good way to determine an upper-bound for the number of tasks to create. Eventually the overhead of creating tasks will likely reduce the benefit of having them but is there a way to find this upper-bound besides trial and error?
Calloc
As we saw in assignment 1, if the work is distributed fairly evenly among the tasks then creating more tasks than the number of cores available on the machine won't be helpful. However, if work distribution isn't even even then I don't know what else can be done apart from trial and error, you can be smart about how you try, for instance use 2 tasks, 4 tasks, 8 tasks, etc. trying to find the optimal number of tasks that give the most speedup using binary search.
cmusam
How high is the cost really to create tasks? If we have 10,000 computations to do, should we generate 10,000 tasks? I'd imagine doing so gives the balanced work assignment.
(In assignment 1, my observation was that the more tasks the higher the speedup.)
anon
@cmusam, I don't know the exact cost for creating tasks, but from what I remember in the demo timing code presented in lecture, the speedup was significantly higher when assigning a task per execution context and using them very efficiently by dynamically allocating computations, compared to spawning a new task for every computation.
418_touhenying
@xyz I think that the overhead of these things pretty much have time complexity in constant family. On the other side, creating more tasks and letting tasks have "finer granularity" speeds up the program much much more, like in an incomparable degree.
Updog
As you increase the number of tasks, there is a tradeoff between task overhead and good load balancing. ISPC recommends launching "many more tasks than there are processors in the system" (source). That's a bit vague, but the exact best number of tasks probably depends on the specific problem you are trying to solve.
ote
@cmusam When you say that the more tasks the higher the speedup, that is not true across the board, right? Depending on the complexity and requirements for the sorts of computations that we are performing, and the limitations on memory bandwidth involved, can't creating more tasks can actually slow down the speedup?
althalus
I agree with @ote. I think that there is always some factor which will limit you. As seen in the last problem of assignment 1, bandwidth is one of the things which does not make having a lot of threads better.
Also, there is a difference in breaking it up into many tasks and threads and how the program handles them.
teamG
I think another factor that should come into play when determining the tasks that you want to create is that one might want to think about caching and locality. When I was working on assignment 1 I suspected that we sometimes might want to do run a program with fewer tasks so that we can exploit cache locality. However, based on the trial and error on the previous error I didn't see any advantages of using fewer tasks.
Is there any good way to determine an upper-bound for the number of tasks to create. Eventually the overhead of creating tasks will likely reduce the benefit of having them but is there a way to find this upper-bound besides trial and error?
As we saw in assignment 1, if the work is distributed fairly evenly among the tasks then creating more tasks than the number of cores available on the machine won't be helpful. However, if work distribution isn't even even then I don't know what else can be done apart from trial and error, you can be smart about how you try, for instance use 2 tasks, 4 tasks, 8 tasks, etc. trying to find the optimal number of tasks that give the most speedup using binary search.
How high is the cost really to create tasks? If we have 10,000 computations to do, should we generate 10,000 tasks? I'd imagine doing so gives the balanced work assignment. (In assignment 1, my observation was that the more tasks the higher the speedup.)
@cmusam, I don't know the exact cost for creating tasks, but from what I remember in the demo timing code presented in lecture, the speedup was significantly higher when assigning a task per execution context and using them very efficiently by dynamically allocating computations, compared to spawning a new task for every computation.
@xyz I think that the overhead of these things pretty much have time complexity in constant family. On the other side, creating more tasks and letting tasks have "finer granularity" speeds up the program much much more, like in an incomparable degree.
As you increase the number of tasks, there is a tradeoff between task overhead and good load balancing. ISPC recommends launching "many more tasks than there are processors in the system" (source). That's a bit vague, but the exact best number of tasks probably depends on the specific problem you are trying to solve.
@cmusam When you say that the more tasks the higher the speedup, that is not true across the board, right? Depending on the complexity and requirements for the sorts of computations that we are performing, and the limitations on memory bandwidth involved, can't creating more tasks can actually slow down the speedup?
I agree with @ote. I think that there is always some factor which will limit you. As seen in the last problem of assignment 1, bandwidth is one of the things which does not make having a lot of threads better. Also, there is a difference in breaking it up into many tasks and threads and how the program handles them.
I think another factor that should come into play when determining the tasks that you want to create is that one might want to think about caching and locality. When I was working on assignment 1 I suspected that we sometimes might want to do run a program with fewer tasks so that we can exploit cache locality. However, based on the trial and error on the previous error I didn't see any advantages of using fewer tasks.