MPSoCs (multi-processor system-on-chips) are comprehensively applied in the embedded multimedia processing field. Multimedia MPSoCs often adopt the “host processor+multiple heterogeneous synergistic processor” architecture, which makes the trade-off between universality and flexibility. MPSoCs also take into consideration both performance and power-consumption, but challenges the method of performance optimization of System-on-Chip applications. This paper proposes an approach that improves the performance of application algorithms running on heterogeneous MPSoCs. The approach includes three stages: Application feature analysis, affine partitioning of kernel loops, and “application-architecture” mapping. It optimizes the multi-level parallelism and data locality of application algorithms to improve MPSoC performance. Experimental results show that the proposed approach can greatly improve the multimedia processing performance on heterogeneous MPSoCs.