THE PARALLEL-PIPELINED IMPLEMENTATION OF THE FRACTAL IMAGE COMPRESSION AND DECOMPRESSION FOR RECONFIGURABLE COMPUTING SYSTEMS

Abstract

Fractal algorithms find an increasing number of areas of application - from computer graphics to modeling complex physical processes, but their software implementation requires significant computing power. Fractal image compression is characterized by a high degree of data compression with good quality of the reconstructed image. The aim of this work is to improve the performance of reconfigurable computing systems (RCS) when implementing fractal compression and decompression of images. The paper describes the developed methods of fractal compression and subsequent decompression of images, implemented in a parallel-pipeline method for RCS. Themain idea of parallel implementation of fractal image compression is reduced to parallel execution of pairwise comparison of domain and rank blocks. For best performance, the maximum number of pairs must be compared simultaneously. In the practical implementation of fractal image compression on the DCS, such critical resources as the number of input channels and the number of FPGA logical cells are taken into account. For the problem of fractal image compression, data channels are a critical resource; therefore, the parallel organization of computations is replaced by parallel-pipeline, after the performance reduction of the parallel computational structure is performed. Each operand goes into the computational structure sequentially (bit by bit) to save computational resources and reduce equipment downtime. To store the coefficients of the iterated functions system encoding the image, a data structure has been introduced that specifies the relation between the numbers of rank and domain blocks and the corresponding parameters. For the convenience of subsequent decompression, the elements of the array encoding the compressed image are ordered by the numbers of the rank blocks, which avoids double indirect addressing in the computational structure. Applying this approach for parallel-pipeline programs allows scaling computing structure to plurality programmable logic arrays (FPGAs). A practical implementation performed on a reconfigurable computer Tertius-2 containing eight FPGAs provides an acceleration of 15000 times compared to a universal multi-core processor and 18–25 times compared to existing solutions for FPGAs. The implementation of image decompression on a reconfigurable computer shows an acceleration of 380 times in comparison with the similar implementation for a multi-core general-purpose processor.