Using NP-Complete Problems to Compare a CPU, GPU, and the Intel® Xeon Phi™ Coprocessor

David M. Toth, Zachary Goodwyn, and Jerome Mueller


Performance evaluation, Analysis and modleing, GPU, Intel Phi, Coprocessor


As accelerators are integrated into many of the newest workstations and supercomputers to provide large amounts of additional processing power, selecting the appropriate one is critical for achieving the best performance. The new Intel® Xeon® Phi™ coprocessor provides more processing cores than a CPU but less than a graphics processing unit (GPU). However, the Phi's cores do not have the limitations of a GPU's cores and can also run code written for traditional CPUs instead of requiring code written specifically for GPUs. We used the traveling salesman problem, the knapsack problem, and the party problem, three NP-complete problems, as benchmark applications to compare the relative performance of the Phi with a contemporary GPU and CPU. Programs were written to solve the problems on the CPU and on the coprocessor that could be easily ported to run on the GPU with only minor modifications. The length of time the programs took to complete on the coprocessor, the GPU, and the CPU was measured. While the GPU attained speedups of almost 14 to 80 over a single CPU core for the problems, the coprocessor only attained speedups between 4 and 7 for the problems.

Important Links:

Go Back