New idea.
Each queue has a semaphore dedicated to preventing jobs submitted to the same queue from overlapping. Each job submitted to a queue both waits and signals the semaphore of that queue.
In addition to this, each job submission would signal one individual semaphore for each possible other queue.
When a new job is submitted, the resources involved are queried to determine which previous jobs must be finished before starting the new one (each resource keeps in memory the last job that wrote or read it). For each dependency, there are two possibilities: either the inter-queue semaphore it signaled is still available, and we wait on it, or the semaphore has already been waited upon. In that second case, we know for sure that it has already been waited upon by a previous job of the queue we are currently submitting to, which means that we don't need to wait upon it.
In the example above, when the second "Read buffer" job is submitted we find out that it depends on the "Write buffer" job. But since the inter-queues semaphore has already been waited upon, we know for sure that the "Write buffer" was already a dependency of an earlier job of queue 1. Which means that we don't need to wait for anything else than the per-queue semaphore.
I think that's probably the best approach.
The drawback is that there are a lot of semaphore destructions, but:
- There should be only a few dozen jobs per frame and a typical program doesn't use more than 4-5 queues, so that would be a few hundred semaphores. It's not that much.
- A pool of semaphores could be maintained to avoid creating and destroying them. I'm not exactly sure how to handle that yet, but it looks definitely possible.
- I think a good idea would be to let the user provide a hint of how many queue transitions there is going to be. This means that we only need to create the appropriate number of semaphores (one + the hint). If the hint happens to be too low, we can submit a dummy command buffer to the source queue to signal the semaphore. That is obviously an overhead, but that's what you get for not providing the right hint.