A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> In this paper, we present a parallel fractal image compression using the programmable graphics hardware. The main problem of fractal compression is the very high computing time needed to encode images. Our implementation exploits SIMD architecture and inherent parallelism of recently graphic boards to speed-up baseline approach of fractal encoding. The results we present are achieved on cheap and widely available graphics boards. <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> Data compression has become an important issue in relation to storage and transmission. This issue is especially true for databases consisting of a large number of detailed computer images. Many methods have been proposed in recent years for achieving high compression ratios for compressed image storage. A very promising compression technique, in terms of compression ratios, is fractal image compression. Fractal image compression exploits natural affine redundancy present in typical images to achieve a high compression ratio in a lossy compression format. Fractal based compression algorithms, however, have high computational demands. To obtain faster compression, a sequential fractal image compression algorithm may be translated into a parallel algorithm. This translation takes advantage of the inherently parallel nature, from a data domain viewpoint, of the fractal transform process. > <s> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> In this paper parallel algorithms for fractal image compression on MIMD architectures are introduced, classified, and discussed. The crucial point for the choice of a suitable parallelization strategy is the memory capacity of a processor element of the target architecture, therefore the classification follows the memory demand of the algorithms. We present experimental results of all main-representatives of the different algorithm classes. The results show a decreasing speedup for increasing memory demand for most of the proposed algorithms. <s> BIB003 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> Fractal image compression is known to be very demanding with respect to CPU-power, and demands are higher again for fractal video compression. Methods to speed up the encoding process can be divided into two groups: one contains sequential speedup-methods like classification, transformation into other search spaces, . . .The other possibility is the use of parallel systems. Here we like to show the possibilities and experiences with shared memory MIMD machines. <s> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> In this work we introduce and analyse algorithms for fractal image compression on massively parallel SIMD arrays. The different algorithms discussed differ significantly in terms of their communication and computation structure. Therefore, the most suited algorithm for a given architecture may be selected according to our investigations. Experimental results compare the performance of the algorithms on the 2-D mesh array of the MasPar MP-2. <s> BIB005 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by data partition <s> Since fractal image compression is computationally very expensive, speed-up techniques are required in addition to parallel processing in order to compress large images in reasonable time. In this paper we discuss parallel fractal image compression algorithms suited for MIMD architectures which employ block classification as speed-up method. <s> BIB006
This appears to be the most widely used mechanism in the literature for classifying different coarse grained parallel algorithms, as in BIB004  BIB006 BIB001 BIB005  BIB003  for example. Essentially, there are two main classes that may be considered: either each processor has sufficient memory to store a copy of the entire image, and therefore can access the entire domain pool without communication, or it does not. The former case either occurs when a shared memory parallel architecture is used, e.g. BIB004 , or when a distributed memory architecture has a significant amount of memory available on each processor. In practice, in recent years memory technology has scaled sufficiently well to ensure that today's distributed memory architectures will always have sufficient memory on each processor to store even a very high resolution image. This has not always been the case however, and so numerous publications in this field have focused upon algorithms for which the domain pool is partitioned across some or all of the processing elements. Examples include BIB005 BIB002  . These are not discussed in any detail here however since we believe them to be of limited value when sufficient memory is available on each processor. This view is consistent with that expressed in BIB005 , where the replication of the entire image on each processor is found to give the best scalability. The approach of allowing each processor to have access to the entire domain pool is also used in BIB003 , for example, where it is again found to be beneficial. In fact, BIB003 describes a number of algorithms that use this approach successfully. Parallelism is achieved by partitioning the range pool across the processing elements (either statically or dynamically, as described above) and so only a very limited amount of inter-processor communication is required.