Study On Parallel Algorithms Of Image Encoding

Due to the restriction of the integrated circuit technology, the processing speed of single-core computer becomes difficult to have fast improvement. Hence, the parallel computer with multiple cores becomes an important development direction of computer industry. The development of the multimedia technology greatly increases the size of image document, and the requirement for the real-time image processing asks for the image processing speed to increase accordingly.This thesis studies the parallel image compression on the multi-core computer and specially focuses on Huffman Coding and Run-length Coding. First, we introduce the serial algorithms of these two encoding methods, and analyze the feasibility of transforming the serial algorithms into parallel algorithms. Second, we design parallel algorithms for the two coding methods, respectively. The parallel design steps are as follows:1. According to the number of processors participating in operation, data are evenly divided into blocks on the principle of "Divide and Conquer". We process the blocked data in parallel. The parallel processing time is approximately equivalent to the serial time divided by the number of processors involved in computing.2. Applying the approach of parallel reading documents, each processor reads file data independently according to their numbers and encodes the data. The time of reading documents decreases with the increase of the number of processors.3. The output documents are written in the pipeline design method. The processors involved in computing write documents individually, which reduces the communication time between processors.Here we adopt SPMD parallel model, where each computing node processes different data based on its own number. We compose parallel programs on the MPI parallel environment according to the parallel algorithms. We put all the parallel programs into execution on the IBM X3500 quad-core server. The results show that the running time of parallel programs is less than that of serial programs and the parallel speedup grows with the increase of the number of nodes, which proves that the two parallel coding algorithms are effective.