Support of Brotli for data-parallel decompression processing - a proof-of-concept
Paul Blinzer
AMD’s research into data-parallel compression and
decompression algorithms that allow efficient GPU and multithreaded CPU
implementations in common use scenarios has investigated Brotli as a basis of a modern general-use, lossless, open, and widely
used compression format. The goal was to identify what it would take to accelerate such a format with data-parallel accelerators like GPUs and in multi-threaded CPU
or CPU SIMD implementations.
It was found that with some minor modifications to how the bitstream
is built, the decompression can then be made to efficiently scale on GPU and multi-threaded CPU
for decompression, while preserving (most of) the compression ratio benefits, with improved overall decompression performance and staying generally
compatible with the Brotli format definitions.
The result of this proof-of-concept work has been temporarily named "Brotli-G"; a description on how the bitstream may be generated to get the data parallel execution benefits and reference source code for CPU based compression and GPU-shader & CPU based decompression implementations has been released as the Brotli-G
SDK on github as-is, under an open-source MIT license, compatible to the license and attribution of the original Brotli reference code released by the IETF.
The performance scaling may depend on the input data and system configuration, but is comparable to other data-parallel decompression formats while typically providing the notably better compression ratio of the Brotli format; exact performance is depending on the number of GPU SIMD or multi-core threads available on the system; a command line test application is part of the SDK. The code has been successfully tested on a variety of hardware configurations from various vendors but no assertions of suitability for a particular platform are made.
The goal of the release is to encourage further
research and more easily engage with the larger Brotli-interested open source community to
further the work by additional contributions and have some of these concepts maybe become part of a future iteration of the format. The GPU compute shader source code is currently based on DX12 but should be relatively easy to convert to other modern GPU shader languages.
The majority of the modifications are in the compressor source code to build a bitstream that
then allows data-parallel decompression; changes to the original Brotli reference source base are easily identifiable.
Collaboration, feedback, research and code contribution for ports to other GPU APIs or SIMD execution, and optimizations are
encouraged and welcome, under the same MIT compatible license and attribution requirements as described in the github repository and the original Brotli reference source code
Anyone interested in further engaging to extend Brotli into such direction?
Best Regards
Paul Blinzer