[Moving this reply from duplicate thread.]
tbb::pipeline is unlikely to have the flexibility to do what you wish. Using either the new tbb::flow::graph framework or using raw tbb::task objects seems appropriate. Chapters 9 and 10 of the TBB Design Patterns manual have examples of building special-purpose schedulers on top of tbb::task .
Another approach that I have heard other people use is to turn the problem into embarrassing parallelism by giving up a little compression. Break the input into separate chunks and compress each separately. That means the beginning of each chunk cannot use frames in the previous chunk as reference frames, hence some compression is lost. Of course this is not practical for streaming applications.
Once piece of advice if you build your own scheduler on top of tbb::task: Write it as a template so that you can instantiate it with dummy types that do heavy-duty checking. Being able to solidly test it without the complications of real video encoding logic will save you grief.
How would graph offer useful additional flexibility over pipeline in this situation, and does that assume subtiling?
Maybe I missed something, but the dependencies seem too ad hoc and continuously changing for any existing algorithm. A coder can isolate itself between substantial scene changes (unpredictable in both occurrence and content), but what is the cost (computational, compressionwise and visually) of subtiling? I suppose that tying division of work to the motion prediction logic could be too ambitious for an initial attempt, and I don't know enough to be able to even guess how beneficial it would be, but it's something I would be tempted to explore.