How parallelizable are PAQ algorithms ?

[boxerab]

As a way of learning how PAQ works, I was thinking of implementing on massively parallel
GPU. Also, to see what sort of speedup is possible. But, if the algorithm is very serial, this may not
be worthwhile. I have found that even fairly serial coders such as MQ coder can be significantly
sped up on GPU, with the right amount of cunning.

[Minimum]

4x4:b256m:paq :D

[Lucas]

Since paq uses many models you can easily parallelize the update cycles, so once you know the current bit each model can update on it's own thread, but it'd still need to use some amount of thread scheduling. Mixing can sometimes be done out-of-order given how many weights you're using and how you mix it. Something like p * (W0 + W1 + ... Wn-1) / n is able to add all the weights in any order since it all sums to the same value, though this would be a bad mixer it still would be able to utilize out-of-order execution. I haven't done any parallel CM at all yet but I have been thinking about it, I don't know of any that currently exist so it'd be nice to see what can be made.

[Shelwien]

Actually the best way to parallelize CM encoding is BWT-like - ie sort counters by context, compute all probability values, then do the same with mixing/SSE layers.

The main problem is that this method is not applicable to decoding - it fact, decoder for a parallel encoder could become even slower than it is now.

Some tricks could be applied to optimize decoding speed too, I guess - like replacing some of mixing with switching + parsing optimization,
speculative decoding, etc. But its much harder to parallelize decoding for CM, overall, because normally each decoded bit would change next predictions,
so we have to know all previous bits to decode the next one. While during encoding, all bits are simply already available.

[JamesB]

Since paq uses many models you can easily parallelize the update cycles, so once you know the current bit each model can update on it's own thread, but it'd still need to use some amount of thread scheduling.

I think threading is challenging as it would need very fine scheduling, however I like the idea of updating multiple models simultaneously. Perhaps for related models some of this can be done in a SIMD fashion, which is still a form of parallelism (in-core). I don't know enough about the different models though to know how much shared maths there is.

[Lucas]

Now that I think about it, you can properly multi-thread sparse context models if you just load the n'th thread's probability into i%nth position in a probability buffer. Because each model only looks at context with gaps of a certain size if you were to use a context with a gap of 1, we would have room to fit a second sparse model running along side and just slotting in the probabilities into the buffer but at a fixed offset (one model would only look at even positions and the other would model odd positions).

To take this idea even further you could perform a fixed reorder of the input data and feed it through parallel models, feeding their output into a buffer at certain offsets for each thread and topping it off with periodic range coding of the buffer. It would sacrifice some compression and increase memory usage (1N blocksize + 32kb buffer + models*threads) but it would allow for proper multi-threading without scheduling on every bit, it's pretty much a fancy way to do blockwise CM with a contiguous output.

To increase compression you could (in theory) periodically mix the content of each thread's models. This would allow for the models to inherit the data seen in other threads and should help keep compression high.

[boxerab]

Thanks, everyone. So, it doesn't sound that promising for running on GPU. GPU memory has very high bandwidth,
but also high latency - the way to hid latency is to run multiple threads on the same task.
Still worth looking into, though.