Results 1 to 13 of 13

Thread: PAQ multi thread

  1. #1
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    PAQ multi thread

    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?

  2. #2
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    People don't make multithreaded versions of PAQ8 nowadays.

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

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

  3. #3
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts
    There is any experiment on parallel programming? Something like use ZPAQ at NVidia through CUDA technology?

  4. #4
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by frede_sch View Post
    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.

  5. #5
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by m^2 View Post
    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?

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts

  7. #7
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  8. #8
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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.

  9. #9
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  10. #10
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    539
    Thanks
    192
    Thanked 174 Times in 81 Posts
    Quote Originally Posted by frede_sch View Post
    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:

    Code:
    ./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.
    Last edited by schnaader; 30th October 2011 at 21:09.
    http://schnaader.info
    Damn kids. They're all alike.

  11. #11
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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).

  12. #12
    Member
    Join Date
    Oct 2011
    Location
    Porto Alegre, Brazil
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Matt Mahoney View Post
    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?

  13. #13
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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.

Similar Threads

  1. Thread title changeable? - No Problem!
    By Simon Berger in forum The Off-Topic Lounge
    Replies: 13
    Last Post: 7th January 2016, 11:53
  2. Multiline PAQ
    By kampaster in forum Data Compression
    Replies: 2
    Last Post: 5th August 2011, 17:25
  3. Multi-way QuickSort
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 7
    Last Post: 9th May 2011, 18:59
  4. Forum does not let me to post in some thread
    By Piotr Tarsa in forum The Off-Topic Lounge
    Replies: 3
    Last Post: 9th April 2011, 14:14
  5. Asymmetric PAQ
    By kampaster in forum Data Compression
    Replies: 11
    Last Post: 27th August 2010, 04:16

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •