New Paper: An Early Evaluation of the Scalability of Graph Algorithms on the Intel MIC Architecture

Erik Saule and Umit V. Catalytirek from Ohio State University have published a new paper examining the scalability of the upcoming Intel MIC architecture on Graph algorithms.

Abstract
Graph algorithms are notorious for not getting good speedup on parallel architectures. These algorithms tend to suffer from irregular dependencies and a high synchronization cost that prevent an efficient execution on distributed memory machines. Hence such algorithms are mostly parallelized on shared memory machines. However, current commodity shared memory machines do not typically offer enough parallelism to process these problems. In this paper, we are presenting an early investigation of the scalability of such algorithms on Intel’s upcoming Many Integrated Core (Intel MIC) architecture which, when it will be released in 2012, is expected to provide more than 50 physical cores with SMT capability. The Intel MIC architecture can be programmed through many programming models, here we investigate the three most popular of these models namely OpenMP, Cilk Plus and Intel’s TBB. We present scalability results of a parallel graph coloring algorithm, three variations of a breadth-first search algorithm and a microbenchmark for irregular computations using these three programming models. Our results on a prototype board show that the multi-threaded architecture of Intel MIC can be effectively used for hiding latencies

Download the paper (PDF).