PAQ multi thread

[frede_sch]

Hi guys,

I'm new with PAQ and data compression. I've tested the some PAQ versions founded at Matt Mahoney page: http://cs.fit.edu/~mmahoney/compression at my linux x86_64, the results are great, but why no one of them is multi thread?

Maybe those examples are outdated and the new examples here at the forum are multi thread, but if not, can someone say me why? It is "impossible" or just not done yet?

[m^2]

People don't make multithreaded versions of PAQ8 nowadays.

Old experiments with it:
http://encode.su/threads/1017-PAQ8o8...=multithreaded

ZPAQ is multithreaded though.
http://encode.su/threads/456-zpaq-updates

[frede_sch]

There is any experiment on parallel programming? Something like use ZPAQ at NVidia through CUDA technology?

[m^2]

There is any experiment on parallel programming? Something like use ZPAQ at NVidia through CUDA technology?

There are many experiments with parallelism, but few with PAQ.
It's not so simple.
I think the strongest GPGPU codec right now is BSC. And IIRC parts of it run on CPU.

[frede_sch]

There are many experiments with parallelism, but few with PAQ.
It's not so simple.
I think the strongest GPGPU codec right now is BSC. And IIRC parts of it run on CPU.

BSC? A simple google search give me nothing.

I'm thinking about trying to implement some PAQ at CUDA, the fact that there are a multi thread PAQ is a great step, so I will take a look at that for the beginning. There is some paper/documentation or anything that fully explains ZPAQ code?

[Shelwien]

http://libbsc.com/default.aspx
http://mattmahoney.net/dc/zpaq.html

[frede_sch]

Thanks Shelwien.

BSC is a very nice project, and have very nice benchmarks. But does not implements any version of PAQ for parallelism. Has someone done that?

[Matt Mahoney]

ZPAQ is my replacement for PAQ. I no longer support PAQ. ZPAQ is based on PAQ-like algorithms but it embeds a description of the decompression algorithm in the archive so that new versions of the compressor don't break compatibility with older versions of the decompresser. This was a problem with PAQ. There are over 160 versions that are incompatible with each other. All versions of ZPAQ compliant programs can read each other's output. The format is described by a specification and a reference decoder.

ZPAQ uses multi-threaded compression and decompression. The data can be divided into blocks that are compressed or decompressed in parallel and reassembled. Obviously there is a tradeoff between compressed size and speed. Larger blocks will compress better, but fewer threads are possible. In addition, zpaq -m1 and -m2 use BWT with a context mixing back end. The BWT is implemented with divsufsort which is multi-threaded with openmp. However, the back end modeling is single threaded, as is the inverse BWT.

To make a context mixing algorithm parallel, you would implement each model on a separate processor and combine the predictions in a mixing tree that could also be parallel at each level. However, there is a serial bottleneck at the root of the tree and the arithmetic coder. You can pipeline the compressor by starting the update and next bit prediction before the previous bit is coded, but you cannot do this for decompression. You have to decode each bit before updating the model. This is why PAQ and ZPAQ decompression is already a little slower than compression. Modern processors will execute instructions in parallel or out of order when possible, but it is less possible for decompression.

[frede_sch]

I'm trying to simple ZPAC some file with: ./zpaq -m4 c a.zpaq file in my i7 linux 64, shouldn't it use 8 threads? It's only using one CPU and 3.8% of my 6GB of RAM.

top:
4710 frederic 20 0 260m 224m 1224 S 100 3.8 0:37.71 zpaq

[schnaader]

I'm trying to simple ZPAC some file with: ./zpaq -m4 c a.zpaq file in my i7 linux 64, shouldn't it use 8 threads? It's only using one CPU and 3.8% of my 6GB of RAM.

Depending on the file size, you have to adjust the block size. For example, for a 32 MB file, a block size of 32 MB / 8 = 4 MB will result in work for 8 threads:

./zpaq -m4 -b4 c a.zpaq file

Default is 16 MB blocks for -m1 and -m2, whole file 1 block for -m3 and -m4. Also note that smaller blocks will result in slightly worse compression, so it's a tradeoff between speed and compression ratio.

[Matt Mahoney]

Also, memory usage is multiplied by number of threads, so "zpaq -m4 -bX c archive file" where X is filesize/8 in MB will use about 2 GB memory (246 MB per thread). -m1 and -m2 use 80 MB per thread, -m3 uses 111 MB per thread. You can also change the maximum number of threads with -t, but not more than the number of blocks. If you compress multiple files, then each is a separate block (except in solid mode, -bs).

[frede_sch]

Also, memory usage is multiplied by number of threads, so "zpaq -m4 -bX c archive file" where X is filesize/8 in MB will use about 2 GB memory (246 MB per thread). -m1 and -m2 use 80 MB per thread, -m3 uses 111 MB per thread. You can also change the maximum number of threads with -t, but not more than the number of blocks. If you compress multiple files, then each is a separate block (except in solid mode, -bs).

What's the difference of solid mode?

[Matt Mahoney]

In solid mode, all files are stored in a single block. Since blocks are independent but segments within blocks are not, you only get 1 thread to compress or decompress the segments (files) in order. By default, each file gets its own block. In -m1 and -m2 or if you use -b, then large files are further divided into blocks. Thus, solid mode gets the best compression but is slowest. Using small blocks is fastest but gets the worst compression.