Spatial and temporal data parallelization of the H.261 video coding algorithm

In this paper, the parallelization of the H.261 video coding algorithm on t he IBM SP2(R) multiprocessor system is described. The effect of parallelizi ng computations and communications in the spatial, temporal, and both spati al-temporal domains are considered through the study of frame rate, speedup , and implementation efficiency, which are modeled and measured with respec t to the number of nodes (n) and parallel methods used. Four parallel algor ithms were developed, of which the first two exploited the spatial parallel ism in each frame, and the last two exploited both the temporal and spatial parallelism over a sequence of frames, The two spatial algorithms differ i n that one utilizes a single communication master, while the other attempts to distribute communications across three masters. On the other hand, the spatial-temporal algorithms use a pipeline structure for exploiting the tem poral parallelism together with either a single master or multiple masters. The best median speedup (frame rate) achieved was close to 15 [15 frames p er second (fps)] for 552 x 240 video on 24 nodes, and 13 (37 fps) for QCIF video, by the spatial algorithm with distributed communications. For n < 10 , the single-master spatial algorithm performs better with efficiency up to 90%, while the multiple-master spatial algorithm is superior for n > 10, w ith efficiency up to 70%. The spatial-temporal algorithms achieved average speedup performance, but are most scalable for large n.