1999 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Multimedia
Volume 1 Number 2, June 1999

Real-Time Interactive MPEG-4 System Encoder Using a Cluster of Workstations

Page 217.

Abstract:

MPEG-4 currently being finalized by the Moving Pictures Experts Group of the ISO is a multimedia standard. MPEG-4 aims to support content-based coding of audio, text, image, and video (synthetic and natural) data, multiplexing of coded data, as well as composition and representation of audio-visual scenes. One of the most critical components of an MPEG-4 environment is the system encoder. An MPEG-4 scene may contain several audio and video objects, images, and text, each of which must be encoded individually and then multiplexed to form the system bitstream. Due to its flexible features, object-based nature, and provision for user interaction, MPEG-4 encoder is highly suitable for a software-based implementation. A full-scale software-based MPEG-4 system encoder with real-time encoding speed is a nontrivial task and requires massive computation. We have built such an encoder using a cluster of workstations collectively working as a virtual parallel machine. Parallel processing of MPEG-4 encoder needs to be carried out carefully as objects may appear or disappear dynamically in a scene. In addition, objects may be synchronized with each other. User interactions may also prohibit a straightforward parallelization. We propose a modeling methodology that captures the spatio-temporal relationship between various objects and user interaction. We then propose a number of scheduling algorithms that periodically allocate MPEG-4 objects to multiple workstations ensuring load balancing and synchronization requirements among multiple objects. Each scheduling algorithm has its own performance and complexity characteristics. The experimental results, while showing real-time encoding rates, exhibit tradeoffs between load balancing, scheduling overhead cost, and global performance.

References

1. L. Chiariglione, "MPEG and multimedia communications," IEEE Trans. Cicuits Syst. Video Techol., vol. 7, pp. 5-18, Feb. 1997.
2. ISO/IEC, "MPEG-4 overview," JTC1/SC29/WG11 N2564, Dec. 1998.
3. B. G. Haskell et al., "Image and video coding--Emerging standards and beyond," IEEE Trans. Cicuits Syst. Video Techol., vol. 8, pp. 814-837, Nov. 1998.
4. M. L. Liou, "Overview of the p × 64 kbps video coding standard," Commun. ACM, vol. 34, no. 4, pp. 59-63, Apr. 1991.
5. Draft ITU-T Recommendation H.263, "Video coding for narrow telecommunication channel at <64 kbit/s," Apr. 1995.
6. D. Le Gall, "MPEG: A video compression standard for multimedia applications," Commun. ACM, vol. 34, no. 4, pp. 46-58, Apr. 1991.
7. ISO Committee Draft 13818-2, "Generic coding of moving pictures and associated audio: Recommendation H.262," ISO/IEC JTC1/SC29/WG11, Nov. 1993.
8. ISO/IEC, "MPEG-4 applications document," JTC1/SC29/WG11 N2563, Dec. 1998.
9. T. Sikora, "The MPEG-4 video standard verification model," IEEE Trans. Cicuits Syst. Video Techol., vol. 7, pp. 19-31, Feb. 1997.
10. ISO/IEC, "MPEG-4 video verification model 8.0," JTC1/SC29/WG11 N1796, July 1997.
11. B. Furht, "Multimedia systems: An overview," IEEE Multimedia, vol. 1, pp. 47-59, Spring 1994.
12. F. Tompa, "A data model for flexible hypertext database system," Inform. Services Use, vol. 7, pp. 85-100, Jan. 1989.
13. T. Murata, "Petri nets: Properties, analysis and applications," Proc. IEEE, vol. 77, pp. 5-35, Apr. 1989.
14. Y. Masunaga, "An object-oriented multimedia database management system," J. Inform. Process., vol. 14, pp. 60-74, 1991.
15. R. Steinmeta, "Synchronization properties in multimedia systems," IEEE J. Select. Areas Commun., vol. 8, pp. 401-412, Apr. 1990.
16. D. Anderson et al., "Support for continuous media in the dash system," in Proc. 10th Int. Conf. Distrib. Comput. Syst., May 1990, pp. 54-61.
17. M. Woo, N. U. Qazi, and A. Ghafoor, "A synchronization framework for communication of pre-orchestrated multimedia information," IEEE Network, vol. 8, pp. 52-61, Jan. 1994.
18. Y. K. Kwok and I. Ahmad, "Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors," IEEE Trans. Parallel Distrib. Syst., vol. 7, pp. 506-521, May 1996.
19. G. C. Buttazzo, Hard Real-Time Computing Systems.Boston, MA: Kluwer, 1997.
20. P. Brucker, Scheduling Algorithms.New York: Springer, 1998.
21. Y. He, I. Ahmad, and M. L. Liou, "A shape-adaptive partitioning method for MPEG-4 video encoding," in Proc. Int. Conf. Electron., Circuits, Syst., 1998, pp. 239-242.
22. J. C. Liou and M. A. Palis, "A comparison of general approaches to multiprocessor scheduling," in Proc. 11th Int. Parallel Process. Symp., 1997, pp. 152-156.
23. D. W. Walker and J. J. Dongarra, "MPI: A standard message passing interface," Supercomput., vol. 12, no. 1, pp. 56-68, Jan. 1996.
24. Z. L. He and M. L. Liou, "A high-performance fast search algorithm for block matching motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 826-828, Oct. 1997.