In this work, we propose a combined multi-core architecture with the capability for instruction set extension (ISE). We show that while both multi-core and ISE exploit parallelism, they do so differently. For this reason multiple cores and ISE could be combined to obtain greater performance improvement than the sum of the two alone. To evaluate this, we implement a dual core microprocessor on a FPGA using an extensible soft-core, eMIPS and mapped the Floyd-Warshall all points shortest path algorithm to this system. Overall, the combined technique yielded performance 3.25x faster and 1.73x faster than parallel or ISE techniques alone.