An investigation into the parallel implementation of JPEG for image compression

This research develops a parallel algorithm to implement the JPEG standard for continuous tone still picture compression to be run on a group of transputers. The processor-farm paradigm is adopted. This research shows this to be the best paradigm for use with the JPEG baseline algorithm on the measured component times within the algorithm. The speedup of the parallel algorithm is investigated and measured against a single processor version. A n optimal distribution of J P E G components on the processors within the processor farm is established. The research focuses on the investigation of the optimal number of processors, which can be used effectively for a JPEG implementation adopting the processor-farm paradigm. This optimal number is termed the saturation point. Once the saturation point has been reached, it is shown that the parallel algorithm's speedup cannot be improved without the redistribution of tasks in the farm, regardless of h o w many extra processors are used. Further distributions of processing tasks are investigated with the aim of extending the saturation point. It is shown that the saturation point can be extended, and the distributions of tasks to achieve this are demonstrated. It is also shown that while the saturation point can be increased, the gains are minimal and m a y not be worth the cost of the extra processor. In fact, the algorithm speedup diminishes after the addition of the third processor, up to saturation point. A simulation algorithm is devised using Java, which takes advantage of the multithreaded nature of the language. A technique is developed for simulating the processorfarm paradigm. This technique uses the concept of the Java threadgroup as a basis for a simulated processor, and a Java thread allocated to that group, as a process belonging to this processor. A process scheduling scheme is refined which allows the simulated parallel system to be monitored over simulated scheduling rounds. A scheme is also shown that simulates the message passing of the transputer. This simulated system allows the investigation of the saturation point regardless of the number of processors physically available. Further data on the saturation point supports the hypothesis that the saturation point is around seven processors. The hypothesis is based on the extrapolation of the results obtained using a limited number of processors. Using the simulation, the behaviour of a parallel system can be observed with an arbitrary number of processors. Since this simulation is written in Java, it is also platform independent, and defines an algorithm suitable for a distributed system