Task mapping exploration plays an important role in the high performance achieved by heterogeneous multi-processor system-on-chip (MPSoC) platforms. The dynamic of application workloads in modern MPSoC-based embedded systems are consistently growing. Nowadays, the execution of different applications is done concurrently and these applications compete for resources in such systems. This paper presents a novel run-time mapping algorithm for multimedia applications. The objective of application mapping is to minimize execution time in a predefined budget of energy consumption. This algorithm is divided to two phases: design-time and run-time. During design-time, application clustering is combined with design space exploration, then a set of rules for mapping is extracted by using Association Rule Mining techniques, and after that, during run-time, feature extraction and application classification is performed based on the rule sets. The evaluation of the proposed algorithm is done by using a heterogeneous MPSoC system with several applications that have different communication and computation behaviors. The experimental results revealed that during run-time, applications were correctly classified by the proposed algorithm and the best resources selected for mapping accurately. The results clearly showcase the proposed algorithm’s effectiveness.