WebP Parallel Analysis and Implementation
Pablo Enfedaque
Hello everyone,
I am working in a project to explore (and develop, if possible) a massive parallel implementation of a lossy WebP encoder. I am not an expert with the coding system, so I would like to share here my initial ideas respect the WebP lossy encoder parallelism. I would greatly appreciate if anyone could double check my statements and point to any mistake, or alternatively, share any comment or suggestion.
WebP lossy encoder parallelism analysis
------------------------------------------------------------------
1.- Y, U and V planes can be coded each one of them independently from the others, and in parallel.
2.- The coding of different Macroblocks (MB) presents dependencies following this pattern:
1 2 3 4 5
3 4 5 6 7
5 6 7 8 9
7 8 9 10 11
Where each number corresponds to a different MB, and the number itself means the “dependency step” in which that MB can be process. This is:
step 1: only the corner top-left MB (1,1) can be processed.
step 2: only the right next MB (1,2) can be processed.
step 3: 2 MBs, (1,3) and (2,1), can be processed independently and in parallel.
etc.
So we have kind of an increasing-max-decreasing parallelism pattern, as the coding of the MB advances, where:
max parallelism = min(image_rows,(image_columns+1)/2)
3.- If I have understood it correctly, the MB dependencies to compute 16x16 and 8x8 prediction modes are like this:
x x
x o
(“o” is the MB to process and “x” are its dependent MBs)
But when using the 4x4 luma block prediction mode, the MB present a L-shape dependency like this:
x x x
x o
This is because, when predicting a MB using the 4x4 mode, the dependencies of each 4x4 subblock (SB) respect the previous SBs follow this same L-shape pattern. This means that SBs in the right border of the MB require the coefficients from the bottom-left corner SB from the top-right MB.
Because 4x4 block mode is not used in U or V, when coding these planes, the dependencies between MB are less constrained, and look like this:
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
Now with steeper (faster) increasing/decreasing parallelism transitions and:
max parallelism = min(image_rows, image_columns)
4.- The different 4 16x16 or 8x8 prediction modes inside a given MB can be computed independently and in parallel.
5.- The different 10 prediction modes inside a given SB can be computed independently and in parallel. Dependencies between different SBs inside the same MB follow the L-shape pattern described previously, and have to be respected, although they present exactly the same parallelism described in the point 1 of this discussion (now with a 4x4 matrix of SBs, instead of MBs, and max parallelism of 2).
6.- Inside a given luma MB, the 4 different 16x16 prediction modes along with the 10 prediction modes for the first SB can be computed independently and in parallel (i.e. points 4 and 5 of this discussion can be done in parallel).
------------------------------------------------------------------
I think that is all, thank you very much for your comments!
Pablo
If you are interested in any detail of the project or wanna share any further comment, feel free to contact me at:
Pascal Massimino
Hello everyone,
I am working in a project to explore (and develop, if possible) a massive parallel implementation of a lossy WebP encoder. I am not an expert with the coding system, so I would like to share here my initial ideas respect the WebP lossy encoder parallelism. I would greatly appreciate if anyone could double check my statements and point to any mistake, or alternatively, share any comment or suggestion.
WebP lossy encoder parallelism analysis
------------------------------------------------------------------
I list here all the main relevant points (performance wise) where I think the WepP encoder expose parallelism, from coarse- to fine-grained:
1.- Y, U and V planes can be coded each one of them independently from the others, and in parallel.
2.- The coding of different Macroblocks (MB) presents dependencies following this pattern:
1 2 3 4 5
3 4 5 6 7
5 6 7 8 9
7 8 9 10 11
Where each number corresponds to a different MB, and the number itself means the “dependency step” in which that MB can be process. This is:
step 1: only the corner top-left MB (1,1) can be processed.
step 2: only the right next MB (1,2) can be processed.
step 3: 2 MBs, (1,3) and (2,1), can be processed independently and in parallel.
etc.
So we have kind of an increasing-max-decreasing parallelism pattern, as the coding of the MB advances, where:
max parallelism = min(image_rows,(image_columns+1)/2)
3.- If I have understood it correctly, the MB dependencies to compute 16x16 and 8x8 prediction modes are like this:
x x
x o
(“o” is the MB to process and “x” are its dependent MBs)
But when using the 4x4 luma block prediction mode, the MB present a L-shape dependency like this:
x x x
x o
This is because, when predicting a MB using the 4x4 mode, the dependencies of each 4x4 subblock (SB) respect the previous SBs follow this same L-shape pattern. This means that SBs in the right border of the MB require the coefficients from the bottom-left corner SB from the top-right MB.
Because 4x4 block mode is not used in U or V, when coding these planes, the dependencies between MB are less constrained, and look like this:
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
Now with steeper (faster) increasing/decreasing parallelism transitions and:
max parallelism = min(image_rows, image_columns)
4.- The different 4 16x16 or 8x8 prediction modes inside a given MB can be computed independently and in parallel.
5.- The different 10 prediction modes inside a given SB can be computed independently and in parallel. Dependencies between different SBs inside the same MB follow the L-shape pattern described previously, and have to be respected, although they present exactly the same parallelism described in the point 1 of this discussion (now with a 4x4 matrix of SBs, instead of MBs, and max parallelism of 2).
6.- Inside a given luma MB, the 4 different 16x16 prediction modes along with the 10 prediction modes for the first SB can be computed independently and in parallel (i.e. points 4 and 5 of this discussion can be done in parallel).
------------------------------------------------------------------
I think that is all, thank you very much for your comments!
Pablo
If you are interested in any detail of the project or wanna share any further comment, feel free to contact me at:
--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss...@webmproject.org.
To post to this group, send email to webp-d...@webmproject.org.
Visit this group at https://groups.google.com/a/webmproject.org/group/webp-discuss/.
For more options, visit https://groups.google.com/a/webmproject.org/d/optout.
Pablo Enfedaque
Hi skal,
Thank you very much for you response! It is really useful to have your opinion and comments regarding those aspects of the encoder. A couple of comments about your response:
1.- It is true that U and V share prediction modes. Checking out the code, I am a bit confused about how does it work though. So, if I want to asses the prediction+reconstruction+distortion of a MB in U and V, I understand that I could reconstruct both planes independently. The thing is that when measuring dist,rate, etc. for a given prediction mode in a MB I have to kind of measure them together? (add them up, do an average or something?).
2.- I am planning on developing a CPU-GPU implementation, so an increase in main memory B/W should not be a major problem, even more considering the near arrival of the 2.5D and 3D memories. Latencies could be an issue though if I could not expose enough parallelism at all times.
3.- IMO there is enough coarse-grained parallelism to exploit. You have not developed a true multi-parallel CPU implementation due to other priorities, or your analysis really showed that it won't be efficient performance-wise?
4.- Last and most important question: For what I understand, in the encoder I could run a good enough amount of GPU threads (those 32-wide-vector “threads” called warps in CUDA). They key question now is:
- There is pixel-level (or similar level) parallelism when computing TTransform, ITransform, QuantizeBlock, Disto4/16 and (I think) more importantly, GetResidualCost??
My initial guess was that there is (at least in the DCT, WHT, Quant.). After the first looks at the code I still think so, but I may easily be missing something.
I will keep you posted about my progress!
Cheers and thanks,
Pablo
Pascal Massimino
Hi skal,
Thank you very much for you response! It is really useful to have your opinion and comments regarding those aspects of the encoder. A couple of comments about your response:
1.- It is true that U and V share prediction modes. Checking out the code, I am a bit confused about how does it work though. So, if I want to asses the prediction+reconstruction+distortion of a MB in U and V, I understand that I could reconstruct both planes independently. The thing is that when measuring dist,rate, etc. for a given prediction mode in a MB I have to kind of measure them together? (add them up, do an average or something?).
2.- I am planning on developing a CPU-GPU implementation, so an increase in main memory B/W should not be a major problem, even more considering the near arrival of the 2.5D and 3D memories. Latencies could be an issue though if I could not expose enough parallelism at all times.
3.- IMO there is enough coarse-grained parallelism to exploit. You have not developed a true multi-parallel CPU implementation due to other priorities, or your analysis really showed that it won't be efficient performance-wise?
4.- Last and most important question: For what I understand, in the encoder I could run a good enough amount of GPU threads (those 32-wide-vector “threads” called warps in CUDA). They key question now is:
- There is pixel-level (or similar level) parallelism when computing TTransform, ITransform, QuantizeBlock, Disto4/16 and (I think) more importantly, GetResidualCost??
My initial guess was that there is (at least in the DCT, WHT, Quant.). After the first looks at the code I still think so, but I may easily be missing something.
I will keep you posted about my progress!
Cheers and thanks,
Pablo
Pablo Enfedaque
Hi skal,
Thanks for the answer! Everything clear now :D
Respect the VP8PutBit (aka the boolean arithmetic coder), I was thinking about computing first the prediction/reconstruction/metrics for all MBs in a first pass, and afterwards do the arithmetic coding for all MBs in a second pass. Does that make sense??
The VP8 spec says that it runs a separate arithmetic decoder (AC) per partition, so I was being positive about arithmetic coding different MBs independently (i.e. run parallel instances of ACs equal to the number of MBs). I don't exactly know if that is possible though, because there may be (for instance) propagation of context probabilities between the coding of different MBs. Do you think multiple parallel ACs over different MBs is possible (after they have been all measured and reconstructed)?
Thank you very much!!
Pablo