Design of Multiprocessor System-on-a-Chips (MPSoC) currently suffers from poor tool support. MPSoC is considered to be the next general design platform for embedded system designs. As complex designs such as multimedia and gaming processing become more common in handheld devices and traditional ASIC solutions are too slow and too expensive, MPSoC allows a fast software solution by running multiple low-cost, low-speed, low-power embedded processors in parallel and combining their processing power to solve more complex computation problems. However, current design methodologies for MPSoC generally restrict the specification of the software for the convenience that it can be analyzed statically. Such restrictions prevent MPSoC designs to reach their full potentials.

In this thesis, I propose an MPSoC design methodology that does not impose unnecessary restrictions on the software. Specifically, \emph{Kahn Process Network} (KPN) is used to model the applications such that each process in the KPN process networks can be expressed by the full power of high-level programming languages. Unfortunately, allowing the full power of high-level programming languages prevents the software to be analyzed statically. Therefore, similar to optimizing software for single-processor systems, a profile-based methodology is proposed to explore the vast design space of MPSoC for applications written in KPN.

There are two main ingredients in the methodology. 1. The MPSoC simulation must be made both fast and accurate. The speed of the simulation must allow designers to modify and experiment different design options in the limited design time allocated for system-level design exploration. At the same time the simulation must be accurate enough for the exploration results to be meaningful. A new MPSoC simulation framework that simulates in the speed close to behavioral simulation and generates performance results with less than 5\% error is shown. 2. An analysis from the simulation must provide accurate MPSoC-specific profiling information about the implementation for guiding the designers to make design decisions. Execution characteristics of MPSoC make such profiling information very different from single-processor systems. A new profiling technique specifically to determine performance-critical information for MPSoC is described.

Three optimization techniques at various implementation levels that use the proposed methodology are shown and applied to an MPEG-2 Decoder design. The experiments show that the optimization techniques using the methodology can efficiently optimize the implementations in term of performance, power and area. The results show that the methodology allows designers to explore the MPSoC design space more efficiently with the accurate MPSoC profiling information.