The shift to multi-core processors presents a number of opportunities and challenges to different research fields, including the field of FPGA applications. Unlike the previous research efforts that implements multi-core systems based on FPGAs for the purpose of emulation and system development, this paper investigates the performance advantages of combining multi-core processors and reconfigurable instruction set extensions. Our analysis and the experimental results show that these two approaches exploit different levels of parallelism. Thus, combining them together allows the acceleration benefits to add up. Using a case study on the Floyd-Warshall algorithm, we find that the multi-core architecture and the reconfigurable instruction set extensions complement each other. On the one hand, instruction set extensions allow engineers to optimize the execution of critical blocks in the software and control fine-grain optimization. This provides more options and control to achieve balanced task partitioning, and therefore, to increase the efficiency of the multi-core system. On the other hand, parallel programming on multi-core processors provides a global view of the application. This perspective enables engineers to better optimize instruction set extensions globally in terms of speed and area cost. By combining these two methods together we find a win-win solution, which gives us a more efficient implementation with higher performance.