Page MenuHome

Cycles: TileManager rewrite using priority queues
Closed, ArchivedPublic


While the current TaskManager does its job, I somehow feel that a more elegant solution would be to use Priority Queues.

My idea for that would be:

  • 3 Lists: Current pass, Next pass, Done
  • All three are Priority Queues, the priority of a tile is calculated based on the tile ordering (e.g. the distance from the center)
  • When rendering starts, all tiles are pushed into the "Current pass" queue
  • acquire_tile pops the highest-priority tile from the "Current pass" queue
  • Once a tile is finished, it gets returned to the TileManager
    • For final renders, these tiles just are pushed into the "Done" queue
    • For preview/progressive renders, the tiles are pushed to "Next pass" if they've not received the desired sample count, and "Done" otherwise
  • Once the "Current pass" is empty, the "Next pass" is moved to "Current pass" if non-empty, otherwise rendering stops

The biggest advantage is that it makes more advanced tile strategies easier: D808 already uses a priority queue, another example is rendering a quick preview pass before each tile is fully rendered.

Are there any obvious problems with this approach? If not, would a patch that implements it have a chance?



Event Timeline

Priority queue is better than iterating all the tiles when you're trying to acquire the non-rendered one yet, but the suggested approach is not totally good either:

  • Storing tiles in the queue is not a good idea, better to store indices IMO
  • Moving tiles from one queue to another is not really cheap. You'll either end up with per-queue push allocation or you'll be having some sloppy memory which is just used by STL classes.
  • It would need to be per-device queue for previews/progressive
  • It does not allow dynamic scheduling based on the spacial locality of rendering. Meaning, you don't want tiles to follow the curve, you either want "spot" of tiles to follow the curve (basically, minimizing momentum of tiles ) This i'm not sure how you can achieve with static scheduling.

Yes, having a tile array and storing index/priority pairs inside the queues sounds reasonable. That also solves problem #2, these 8 bytes per tile should not be noticable (even with 8x8 tiles for a 4K frame, you only end up with 1MB of data).
Regarding per-device: I'm not totally sure here, but the approach I use in D808 (popping from the queue until a tile from the correct device appears, pushing back the others) seems to work with a single queue.
As for locality: Tile ordering is another topic, D1166 might help here as it obeys locality, another option might be a kind of extending spiral starting in the center.

With D1684 this is probably not relevant anymore, so I'm just closing it.