When parallelizing complex multimedia processing on multiple processors, the stochastic timing behavior should be carefully studied. Although there are already many papers on the performance analysis of stochastic parallel system, they are not targeted on multimedia processing. In this paper, first we study H.264/AVC encoder (running on x86) and QSDPCM encoder (running on TI TMS32C62 instruction simulator) to characterize important aspects of the stochastic timing behavior in complicated multimedia processing applications. It is shown that the variation and correlation are indeed very significant. In order to make systematic analysis feasible, we apply Stochastic Timed Marked Graph (STMG) as a formal model to capture essential timing related behaviors of parallel multimedia processing systems. Then, we show how the local timing variations and correlations interact and propagate to the global timing behavior; from this we conclude general parallelization guidelines. Furthermore, we develop an analytical performance estimation technique to derive the probability distribution of timing behavior for parallel multimedia processing systems that have correlated stochastic timing behaviors inside. The estimation technique is based on principal component analysis and approximations.