The work assignment by cost zone technique is great because it pretty much avoids communication between processors to assign the work. Think about dynamic assignment approach we discussed previously, where there's a worker pool and queue of tasks, and task is assigned to a worker when it's available. Dynamic assignment requires lots of communication between processors.
In this case, however, every processor independently computes its own portion of work based on the cost tree. Each processor is responsible for a zone where stars are close to each other, thus providing good temporal locality.
With this approach, notice that each processor has to traverse the tree to compute its portion of the work, which may be the reason why in slide 21 the processors spent more time in "busy" mode.
@haibinl That's reasonable. But how to efficiently estimate the workload?
Do they precompute the mapping of the indices of the cost zone?
The indices of the cost zone look like they are computed from the tree. By updating the tree a new mapping of indices can be computed. This allows the distribution of work to remain approximately even.