A Survey of Parallel Algorithms for Fractal Image Compression <s> DISCUSSION <s> Abstract In this paper we study diffusion schemes for dynamic load balancing on message passing multiprocessor networks. One of the main results concerns conditions under which these dynamic schemes converge and their rates of convergence for arbitrary topologies. These results use the eigenstructure of the iteration matrices that arise in dynamic load balancing. We completely analyze the hypercube network by explicitly computing the eigenstructure of its node adjacency matrix. Using a realistic model of inter-processor communications, we show that a diffusion approach to load balancing on a hypercube multiprocessor is inferior to another approach which we call the dimension exchange method. For a d-dimensional hypercube, we compute the rate of convergence to a uniform work distribution and show that after d + 1 iterations of a diffusion type approach, we can guarantee that the work distribution is approximately within e−2 of the uniform distribution independent of the hypercube dimension d. Both static and dynamic random models of work distribution are studied. <s> BIB001 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> DISCUSSION <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> BIB002 </s> A Survey of Parallel Algorithms for Fractal Image Compression <s> DISCUSSION <s> In this paper we contrast the performance of a number of different parallel dynamic load-balancing algorithms when used in conjunction with a particular parallel, adaptive, time-dependent, 3D flow solver. An overview of this solver is given along with a description of the dynamic load-balancing problem that results from its use. Two recently published parallel dynamic load-balancing software tools are then briefly described and a number of recursive parallel dynamic load-balancing techniques are also outlined. The effectiveness of each of these algorithms is then assessed when they are coupled with the parallel adaptive solver and used to tackle a model 3D flow problem. <s> BIB003
In this short communication we have attempted to review a number of the key ideas and algorithms that have been developed for parallel fractal image compression over the past decade or more. The motivation behind the use of parallel computer architectures in this context comes from the extremely high computational cost of the standard sequential encoding algorithms. A number of available techniques have been discussed from the viewpoints of granularity, load balancing, data partitioning and complexity reduction. In discussing these issues it becomes apparent that a significant amount of care and thought has gone into developing and implementing algorithms suitable for a variety of hardware platforms. It is worth observing however that many of the properties of today's parallel hardware are not consistent with assumptions made in some of the past work. In particular, it is inconceivable today that a parallel processor would not have sufficient of its own primary memory to store its own copy of the entire uncompressed image (or even a sequence of uncompressed images in the case of video compression). For this reason, any future focus on improving parallel performance must surely assume that each process has access to the entire domain pool, as discussed in  BIB002 for example. An important issue that arises in undertaking this work is that of load balancing. As discussed in the previous section, dynamic load balancing is likely to yield the best performances and so it may be that there is benefit to be gained from focusing on this issue more deeply. Typically, for the fractal image compression algorithms considered here, dynamic load balancing has been achieved through the master-slave paradigm. Whilst this is certainly a reliable and straightforward approach it does suffer from the overhead of requiring the master process to execute in addition to the slaves: which are doing all of the "useful" work. There may therefore be some benefits in considering alternative dynamic load balancing strategies, such as those based upon asynchronous diffusion  BIB001 for example. A possible approach could be to allow each processor to have a copy of the entire image and then allocate itself (based upon its process number for example) an equal share of the range pool. As each processor works through its range blocks, successfully matching them with images of domain blocks, it communicates its remaining number of range blocks to process to its neighboring processors asynchronously. If the remaining load on any processors gets out of balance with its neighbors then the ownership of some of the remaining range blocks can be passed between processors to balance the remaining work dynamically. BIB003 provides a review of parallel dynamic load balancing algorithms, including this diffusion approach. It is clear that fractal image compression is unlikely to be as widely used as JPEG is for the general representation of photographic images in the near future. However it certainly plays an important role for specific problems where compression ratio is more important than real-time compression, or where it is desirable to reproduce an image of realistic quality regardless of the resolution to which it is viewed. In these cases parallel FIC algorithms have a valuable role to play and efficient, portable implementations should be possible on modern computer architectures.