Previous | Next --- Slide 63 of 64
Back to Lecture Thumbnails
haofeng

The bookkeeping and stealing overheads would dominate if there are too much tasks with fine granularity. Therefore, it is a good idea to use recursion when dividing the tasks. Each thread divides the task until certain granularity is reached, and when dividing the tasks, the largest chunk of the tasks could be stolen by other threads to process. This helps better load balancing and reduces the overheads for stealing fine-grained tasks.

ishangaur

This allows each thread to expose the biggest chunk of available work, and start from its smallest granularity. This gets it out of the way of all the other threads while allowing the discovery of work itself to be recursively parallelized through stealing.

Please log in to leave a comment.