A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by load-balancing algorithms <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> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by load-balancing algorithms <s> Abstract In this paper, a load balancing extension for the PVM software system is described. This extension includes slave processes, for obtaining host CPU load information, and a master process for gathering the load information. A programming interface is included to provide the PVM user with CPU load information and a load balancing process spawn. For tested applications, the load balancing extension exhibits considerable improvement in parallel runtime performance. Results presented include parallel runtime comparisons for basic matrix oriented algorithms, a parallel fractal image compression algorithm, and selected NAS parallel benchmarks. <s> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by load-balancing algorithms <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 load-balancing algorithms <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> BIB004 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> Classification by load-balancing algorithms <s> This paper proposes a parallel architecture for quadtree-based fractal image coding. This architecture is capable of performing the fractal image coding based on quadtree partitioning without the external memory for the fixed domain pool. Since a large domain block consists of small domain blocks, the calculations of distortion for all kinds of domain blocks are performed by the summation of the distortions for the maximum-depth domain pool which is extracted from the smallest range blocks of the neighbor processors. Fast comparison module is proposed for this architecture. This module can compute the distortions between range blocks and their eight isometric transformations by one full rotation around the center. <s> BIB005
In this section of the paper we describe the available parallel algorithms in terms of the techniques that they use to ensure that the parallel load is evenly distributed across the available processing elements. These are described in terms of three general classes of algorithms however, as we will explain, these classes are not disjoint. We begin with a discussion of pipeline algorithms, in which static load balancing based upon a partition of the range pool, and finish with a discussion of dynamically partitioning the range pool. The systolic architecture approach of BIB005 has already been introduced above. In this approach each range block is compared with a different domain block at any given step. Once the comparison step is completed the domain blocks are shifted to the next processor in the pipeline, for another comparison step. When all domain blocks have passed through the pipeline (which is actually a ring, so as to save any start-up overhead) the comparison step is complete for all range blocks. A similar technique is also adopted in  . Another pipeline approach is described in  , which focuses on the design of a parallel image processing architecture. In this case the pipeline is used to enhance the performance of the arithmetic in calculating the terms in the expressions (6) and (7) using finegrained parallelism. Perhaps the simplest possible load-balancing approach that can be used is to equally partition the range pool across the available processors when using a coarse grained parallel algorithm, this is described in BIB002  BIB004 for example. If the time required to find the matching element of the domain pool is the same for each element of the range pool then each processor will automatically have an equal amount of computational work in the crucial matching stage. This is the case when the range and domain pools are fixed and we always seek the best possible match from the domain pool to each element of the range pool. In practice however, the most efficient fractal compression algorithms do not work like this since they either involve use of an adaptive quad-tree (for when no suitable matching domain block is found) or a matching tolerance (such that the search through the domain blocks stops once a suitably close match has been found), or both. This means that the time required to match a domain block to a given range block is not known in advance, and so static partitioning is likely to be unreliable. As a consequence of this, the majority of coarse-grained parallel algorithms that have been developed tend to use some form of dynamic load-balancing, e.g. BIB004 BIB001 BIB003  . Typically this approach involves a master process and a large number of slave processes. For example, in BIB001 a master process divides the image equally amongst the slaves. Each slave is therefore responsible for its own subset of the overall domain pool. The master then transmits range blocks to any idle slaves and waits for them to return the best match from their subset of the domain pool. Depending upon whether this is a satisfactory match or not this range block may or may not be sent to another processor. Once all of the range blocks have been processed the master can then move onto the next level of the quad-tree if this is necessary. The master process ensures that all of the slaves are kept busy until the task is completed. This is typical of the masterslave approach to dynamic load balancing. In more general terms, the master keeps a queue of computational tasks and a queue of idle slave processes. Whenever the process queue is not empty the master seeks to give the next job on the task queue to the next process on the idle slave queue. Interestingly, some dynamic load balancing algorithms have successfully combined the master-slave paradigm with the use of pipelines. For example, in  the domain blocks are initially distributed amongst the slaves. Each slave is then assigned a range block by the master. Once the quality of the match between the range block and the subset of the domain blocks has been found on each slave one of two things happens. If the match on a slave is below the desired threshold, or if the range block has already been considered by all of the other slaves, the range block is returned to the master along with a note of the best matching domain block. Otherwise the slave passes the range block on to the next slave in the pipeline of slaves. Before the next matching step begins the master sends a new range block from its task queue to any slave processors who did not receive a range block from their predecessor in the pipeline.