Scalability and Communication in Parallel Low-Complexity Lossless Compression |
| |
Authors: | Luigi Cinque Sergio De Agostino Luca Lombardi |
| |
Institution: | 1.Computer Science Department,Sapienza University,Rome,Italy;2.Computer Science Department,University of Pavia,Pavia,Italy |
| |
Abstract: | Approximation schemes for optimal compression with static and sliding dictionaries which can run on a simple array of processors
with distributed memory and no interconnections are presented. These approximation algorithms can be implemented on both small
and large scale parallel systems. The sliding dictionary method requires large size files on large scale systems. As far as
lossless image compression is concerned, arithmetic encoders enable the best lossless compressors but they are often ruled
out because they are too complex. Storer extended dictionary text compression to bi-level images to avoid arithmetic encoders
(BLOCK MATCHING). We were able to partition an image into up to a hundred areas and to apply the BLOCK MATCHING heuristic
independently to each area with no loss of compression effectiveness. Therefore, the approach is suitable for a small scale
parallel system at no communication cost. On the other hand, bi-level image compression seems to require communication on
large scale systems. With regard to grey scale and color images, parallelizable lossless image compression (PALIC) is a highly
parallelizable and scalable lossless compressor since it is applied independently to blocks of 8 × 8 pixels. We experimented
the BLOCK MATCHING and PALIC heuristics with up to 32 processors of a 256 Intel Xeon 3.06 GHz processors machine () on a test set of large topographic bi-level images and color images in RGB format. We obtained the expected speed-up of
the compression and decompression times, achieving parallel running times about 25 times faster than the sequential ones.
Finally, scalable algorithms computing static and sliding dictionary optimal text compression on an exclusive read, exclusive
write shared memory parallel machine are presented. On the same model, compression by block matching of bi-level images is
shown which can be implemented on a full binary tree architecture under some realistic assumptions with no scalability issues. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|