Future integrated systems will contain billion of transistors, composing tens to hundreds of IP cores. These IP cores, implementing emerging complex multimedia and network ap- plications, should be able to deliver rich multimedia and networking services. An efficient cooperation among these IP cores (e.g., efficient data transfers) can be achieved through utilization of the available resources. The design of such complex systems includes several challenges to be addressed. Among others one challenge is to design an on-chip interconnection network that should be able to efficiently connect the IP cores. Another challenge is to derive such an application mapping that will make efficient usage of the available hardware resources . An architecture that is able to accommodate such a high number of cores, satisfying the need for commu- nication and data transfers, is the Network-on-Chip (NoC) architecture. For these reasons Networks-on-Chip become a popular choice for designing the on-chip interconnect for Systems-on-Chip (MPSoCs), and are supported from the industry (such as the Ethereal NoC from Philips, the STNoC from STMicroelectronics and an 80-core NoC from Intel). As it is presented in , the key design challenges of emerging NoC design are a) the communication infrastructure, b) the communication paradigm selection and c) the application mapping optimization.