Video transcoding is a popular technique for delivering video content of varying quality and size to diverse audiences. In this paper we present a taxonomy of the different ways movie trans/en-coding can be performed by a multicomputer platform. We differentiate these techniques based on (a) the party that performs the decoding of the input media stream, (b) whether the input data can be randomly accessed without the need for sequential decoding and (c) the communication capabilities of the computing nodes. We then proceed to derive analytical closed-form solutions to the problem of optimizing the input data distribution to the nodes of the parallel machine in order to minimize the total execution time. This analysis is based on a systematic study of the costs associated with decoding and encoding movie frames by the FFMPEG OSS library. The paper is concluded by a simulation study based on a set of benchmarks performed on Linux workstations.