This dissertation, "Fast and Efficient Video Coding Based on Communication and Computation Scheduling on Multiprocessors" by Kwong-Keung, Leung, 梁光強, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled Fast and Efficient Video Coding based on Communication and Computation Scheduling on Multiprocessors submitted by Kwong-Keung LEUNG for the degree of Doctor of Philosophy at the University of Hong Kong in April 2001 The goal of this research is to investigate possible parallelization methods for video coding under the criteria of efficiency, coding frame rate, coding delay and applicability. To achieve this goal, a philosophy based on the scheduling of communication and computation on multiprocessors has been adopted and a number of methods and algorithms have been proposed. Firstly, data parallelization has been investigated by a systematic approach considering the data dependency and communication issues. Comparisons have shown that an algorithm with a distributed communication scheme is more scalable than one with centralized communication. In addition, a mixed spatial and temporal parallelization approach is more general and effective than a purely spatial one, especially for reduced frame size. From our simulation on the IBM SP2, a speedup of 14.8 [40.4 frames/second (fps)] was achieved for 352240 video using 24 processors with 61.6% efficiency, which is over 14% better than any other methods reported with comparable frame rate. Secondly, based on the idea of communication hiding using communication co- processor, a new method for parallel video coding has been developed aiming at good efficiency. To verify this, an H.261 video encoder has been implemented on a TMS320C80 system. The measured speedup were 3.67 (34.2 fps) and 3.75 (10.3 fps) using four parallel processors for QCIF and 352240 video, respectively, which correspond to 91.6% and 93.8% efficiencies, respectively. This is some 10% better than any parallel implementation reported so far. As this method is reasonably independent from the target video coding standard, it is fair to assume that it is equally applicable to other similar coding algorithms such as H.263, MPEG-1 and MPEG-2. Thirdly, for generalization of the task scheduling problem, a neighborhood search algorithm has been developed based on a realistic model with consideration of inter- processor communication and resource contention. The schedule representation scheme allows the exploitation of communication locality for communication overhead reduction and temporal parallelism. Through simulation, significant improvement has been obtained over several existing methods. When applied to parallel video coding, an implementation on the IBM SP2 has achieved a speedup of 13.8 (39.3 fps) using 24 processors at 352240 resolution. The result of the schedule obtained automatically is comparable with the manually optimized parallel algorithms presented in this thesis. Fourthly, speedup variation in parallel video coding was observed due to encoding time variation. This issue was tackled with an adaptive parallel scheme based on run-time schedule selection in which the run-time overhead is scheduled together with the coding algorithm. This has the advantage of being near-optimal using compile-time schedules and simultaneously, involving small and controlled run-time overhead. This scheme has been evaluated with a parallel H.261 video encoder on the IBM SP2 . Compared with the single static schedule scheme, average improvements of 16.9% and 13.2% have been achieved for the c