An Early Evaluation of the Scalability of Graph Algorithms on the Intel MIC Architecture
Authors:
- Erik SauleESErik Saule
- Umit V. CatalyurekUCUmit V. Catalyurek
- 1 May 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1629-1639
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 micro benchmark 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 in irregular applications to achieve almost perfect speedup.Keywords
This publication has 15 references indexed in Scilit:
- A Tighter Analysis of Work StealingLecture Notes in Computer Science, 2010
- A framework for scalable greedy coloring on distributed-memory parallel computersJournal of Parallel and Distributed Computing, 2008
- CHALLENGES IN PARALLEL GRAPH PROCESSINGParallel Processing Letters, 2007
- A General Performance Model of Structured and Unstructured Mesh Particle Transport ComputationsThe Journal of Supercomputing, 2005
- What Color Is Your Jacobian? Graph Coloring for Computing DerivativesSIAM Review, 2005
- Metrics and models for reordering transformations2004
- Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to CilkTheory of Computing Systems, 2002
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Cilk: An Efficient Multithreaded Runtime SystemJournal of Parallel and Distributed Computing, 1996
- Estimation of Sparse Jacobian Matrices and Graph Coloring BlemsSIAM Journal on Numerical Analysis, 1983