3 ms·

Is there anything in the algorithm which would preclude an efficient CUDA implementation?

krasin 5y ago
Good question. I've taken a look at the final revision of the spec ([1]) and it seems that parallelizing a QOI decoder may be non-trivial, because of back references. More over, it's possible to come up with QOI-encoded images which would see no speedup from any concurrent decoding (for example, if every single pixel refers to the previous). On the other hand, a parallel QOI encoder is relatively straightforward and will only have about 4*N bytes of compression penalty per image, where N is the number of threads, which is a trivial cost, if we talk about megapixel-scale images (as opposed to tiny icons). 1. https://qoiformat.org/qoi-specification.pdf https://qoiformat.org/qoi-specification.pdf
astrange 5y ago
Compression is fundamentally not suitable for GPGPU, because if it can be parallelized then it's not compressed well enough. That's why codec acceleration all uses ASICs. Of course in some situations you don't care about compression efficiency that much.
- riedel 5y ago
  That is a strange statement, most machine learning boils down to compression in essence (OK it is lossy, but any image quantisation is also lossy). E.g. autoencoders are compression algorithms: take the model as a dictionary and the latent space weights as compressed representation. For most algorithms you are right though. Particularly it is worth the effort to put things in to Asics as the "wiring" normally stays stable and you do not need the flexibility of gpgpus . Still also there is nothing that keeps you from using them e.g. for efficient parallel decoding.
  - astrange 5y ago
    I think it's axiomatically true and ML models get a pass on being inefficient because people are so busy being impressed by their magic tricks. In particular, using ML models for compression would get a free advantage because they're often several GBs where a traditional codec is KBs, so they can hide data in there, but most people wouldn't think of that as being part of the compressed message size. But they could have very differently shaped dependency trees, especially if you somehow managed to not run an entropy coder as the last step of compression.
    - riedel 5y ago
      Totally agree, tgeneral compression that requires the dictionary to be transmitted on every message is not the best use case (if there even is any). Minimal description length is actually a nice information theoretical measure to describe power of ML models to compress. However I have also seen tons of theoretical proof that probably there is no optimal compression method ( I looked at grammar vs entropy coding some time ago) hence there is probably no optimal hardware in general. In the end it depends on your assumption about the the data (quality, structure, size, chunking,...) you want to compress.
- mort96 5y ago
  This doesn't seem correct? All the compression algorithms I have some amount of understanding of (that being JPEG and H.264; not a ton, but fairly widespread) have some concept of mostly-independently-compressed blocks. You also see in practice that many compression tools can use multiple threads. From a theoretical perspective, compressing something is largely a search problem; you're searching through a space of possible representations in order to find the smallest one. Search problems can often be parallelized.
  - astrange 5y ago
    I wrote the multithreaded H.264 decoder in ffmpeg. Any concept of "independently compressed blocks" is a compromise because you could've made them depend on each other and made the entropy coder more efficient. But I was talking about GPGPU, which is completely unsuitable for it either way.
mkcg 5y ago
I don't know about CUDA, however I've made an AVX2 based encoder a few months ago : https://github.com/phoboslab/qoi/pull/143 https://github.com/phoboslab/qoi/pull/143 I intend to create an AVX2 based decoder but I had absolutely no time to work on side projects in the past three months. You might also want to take a look at this streaming encoder if you want to encode large files with a tiny memory footprint : https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c

Good question. I've taken a look at the final revision of the spec ([1]) and it seems that parallelizing a QOI decoder may be non-trivial, because of back references. More over, it's possible to come up with QOI-encoded images which would see no speedup from any concurrent decoding (for example, if every single pixel refers to the previous). On the other hand, a parallel QOI encoder is relatively straightforward and will only have about 4*N bytes of compression penalty per image, where N is the number of threads, which is a trivial cost, if we talk about megapixel-scale images (as opposed to tiny icons). 1. https://qoiformat.org/qoi-specification.pdf https://qoiformat.org/qoi-specification.pdf

astrange 5y ago

Compression is fundamentally not suitable for GPGPU, because if it can be parallelized then it's not compressed well enough. That's why codec acceleration all uses ASICs. Of course in some situations you don't care about compression efficiency that much.

riedel 5y ago
That is a strange statement, most machine learning boils down to compression in essence (OK it is lossy, but any image quantisation is also lossy). E.g. autoencoders are compression algorithms: take the model as a dictionary and the latent space weights as compressed representation. For most algorithms you are right though. Particularly it is worth the effort to put things in to Asics as the "wiring" normally stays stable and you do not need the flexibility of gpgpus . Still also there is nothing that keeps you from using them e.g. for efficient parallel decoding.
- astrange 5y ago
  I think it's axiomatically true and ML models get a pass on being inefficient because people are so busy being impressed by their magic tricks. In particular, using ML models for compression would get a free advantage because they're often several GBs where a traditional codec is KBs, so they can hide data in there, but most people wouldn't think of that as being part of the compressed message size. But they could have very differently shaped dependency trees, especially if you somehow managed to not run an entropy coder as the last step of compression.
  - riedel 5y ago
    Totally agree, tgeneral compression that requires the dictionary to be transmitted on every message is not the best use case (if there even is any). Minimal description length is actually a nice information theoretical measure to describe power of ML models to compress. However I have also seen tons of theoretical proof that probably there is no optimal compression method ( I looked at grammar vs entropy coding some time ago) hence there is probably no optimal hardware in general. In the end it depends on your assumption about the the data (quality, structure, size, chunking,...) you want to compress.
mort96 5y ago
This doesn't seem correct? All the compression algorithms I have some amount of understanding of (that being JPEG and H.264; not a ton, but fairly widespread) have some concept of mostly-independently-compressed blocks. You also see in practice that many compression tools can use multiple threads. From a theoretical perspective, compressing something is largely a search problem; you're searching through a space of possible representations in order to find the smallest one. Search problems can often be parallelized.
- astrange 5y ago
  I wrote the multithreaded H.264 decoder in ffmpeg. Any concept of "independently compressed blocks" is a compromise because you could've made them depend on each other and made the entropy coder more efficient. But I was talking about GPGPU, which is completely unsuitable for it either way.

mkcg 5y ago

I don't know about CUDA, however I've made an AVX2 based encoder a few months ago : https://github.com/phoboslab/qoi/pull/143 https://github.com/phoboslab/qoi/pull/143 I intend to create an AVX2 based decoder but I had absolutely no time to work on side projects in the past three months. You might also want to take a look at this streaming encoder if you want to encode large files with a tiny memory footprint : https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c