IIUC all current encoders that support parallelism work by multiple threads working on the same frame at the same time. Often times the frame is split into regions and each thread focuses on a specific region of the frame. This approach can have a (usually small) quality/efficiency cost and requires per-encoder logic to assemble those regions into a single frame.
What if instead/additionally different keyframe segments are processed independently? So if keyframes are every 60 frames ffmpeg will read 60 frames pass that to the first thread, the next 60 to the next thread, ... then assemble the results basically by concatenating them. It seems like this could be used to parallelize any codec in a fairly generic way and it should be more efficient as there is no thread-communication overhead or splitting of the frame into regions which harms cross-region compression.
Off the top of my head I can only think of two issues:
1. Requires loading N*keyframe period frames into memory as well as the overhead memory for encoding N frames.
2. Variable keyframe support would require special support as the keyframe splits will need to be identified before passing the video to the encoding threads. This may require extra work to be performed upfront.
But both of these seem like they won't be an issue in many cases. Lots of the time I'd be happy to use tons of RAM and output with a fixed keyframe interval.
Probably I would combine this with intra-frame parallelization such as process every frame with 4 threads and then run 8 keyframe segments in parallel. This way I can get really good parallelism but only minor quality loss from 4 regions rather than splitting the video into 32 regions which would harm quality more.