This paper describes the implementation of the W-CDMA cell search algorithm on a homogeneous general purpose Multi-Processor System-on-Chip architecture. The architecture is composed of nine nodes based on COFFEE RISC cores communicating using hierarchical Network-on-Chip. The work focuses on the parallelization of the cell search algorithm, enabling execution on different processing nodes, and exploiting the capabilities of the network-on-chip. We achieved a total speed-up of 7.3X when compared with a single processing core system, taking into account the overhead related with the communication between different nodes. The result is significant since very close to the theoretical maximum of 9X. Considering the hardware implementation, the target cell search is performed in 104ms on an FPGA with 75MHz maximum frequency, and in 40ms on an ASIC circuit with 200MHz maximum frequency.