MPEG-4 which is currently being developed by MPEG (Moving Pictures Experts Group), is poised to become a standard for supporting current and emerging interactive multimedia applications. The objective of MPEG-4 is to support content-based compression, communication, access and manipulation of digital objects which can be natural or synthetic. Since MPEG-4 based video consists of objects and provides full interactivity between the client and the server, a software-based implementation seems to be the only viable approach for building an MPEG-4 encoder. Parallel processing solves the problem of large computational requirements for building a real-time encoder. In this paper, we describe a parallel implementation of MPEG-4 video encoder using a cluster of workstations collectively working as a virtual machine. Parallelization of the MPEG-4 encoder poses an interesting problem since not only can objects be added or deleted from a video scene but their sizes and shapes may vary with time. Moreover, some of the computationally intensive parts of the encoder are non-uniform algorithms, which means their execution times are data dependent and cannot be predicted in advance. In order to guarantee the spatio-temporal relationship between various objects in a video, we propose a real-time scheduling algorithm for exploiting parallelism in the temporal domain. The algorithm divides the workstations into a number of groups and assigns one video object to one group of workstations for encoding. A dynamic shape-adaptive data partitioning strategy is proposed to exploit parallelism in the spatial domain. The partitioning strategy divides the data of an object among the workstations within a group. The scheduling scheme ensures the synchronization requirements among multiple objects while the dynamic data parallel approach adapts to the object shape variations to balance the load for all the workstations. The performance of the encoder can scale according to the number of workstations used. With 20 workstations, the encoder yields an encoding rate higher than real-time, allowing to encode multiple sequences simultaneously.