New multimedia embedded applications are increasingly dynamic, and rely on dynamically-allocated data types (DDTs) to store their data. The optimization of DDTs for each target embedded system is a time-consuming process due to the large searching space of possible DDTs implementations. That implies the minimization of embedded design variables (memory accesses, power consumption and memory usage). Up to know, some very effective heuristic algorithms have been developed in order to solve this problem, but it is unknown how good the selected DDTs are since the problem is NP-complete and cannot be fully explored. In these cases the use of parallel processing can be very useful because it allows not only to explore more solutions spending the same time, but also to implement new algorithms. This paper describes several parallel evolutionary algorithms for DDTs optimization in Embedded Systems, where parallelism improves the solutions found by the corresponding sequential algorithm, which indeed is quite effective compared with other previously proposed procedures. Experimental results show how a novel parallel multi-objective genetic algorithm, which combines NSGA-II and SPEA2, allows designers to reach a larger number of solutions than previous approximations.