Using the Intel Many Integrated Core to accelerate graph traversal

Abstract

Data-intensive applications have drawn more and more attention in the last few years. The basic graph traversal algorithm, the breadth-first search (BFS), a typical data-intensive application, is widely used and the Graph 500 benchmark uses it to rank the performance of supercomputers. The Intel Many Integrated Core (MIC) architecture, which is designed for highly parallel computing, has not been fully evaluated for graph traversal. In this paper, we discuss how to use the MIC to accelerate the BFS. We present some optimizations for native BFS algorithms and develop a heterogeneous BFS algorithm. For the native BFS algorithm, we mainly discuss how to exploit many cores and wide-vector processing units. The performance of our optimized native BFS implementation is 5.3 times that of the highest published performance for graphics processing units (GPU). For the heterogeneous BFS algorithm, the performance of the general processing unit (CPU) and MIC cooperative computing can gain an increase in speed of approximately 1.4 times than that of a CPU for graphs with 2M vertices. This work is valuable for using a MIC to accelerate the BFS. It is also a general guidance for a MIC used for data-intensive applications.

Keywords

Many Integrated Core MIC breadth first search BFS graph traversal heterogeneous computing Graph 500

Get full access to this article

View all access options for this article.

References

Agarwal

Petrini

Pasetto

. (2010) Scalable graph exploration on multicore processors. In: 2010 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC10), New Orleans, LA, US, 13–19 November 2010, pp.1–11.

Albert

Jeong

Barabási

(1999) Internet: diameter of the world-wide web. Nature 401(6749): 130–131.

Bader

Madduri

(2006) Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In: International conference on parallel processin, Columbus, OH, US, 14–18 August 2006, pp. 523–530.

Barabási

Albert

(1999) Emergence of scaling in random networks. Science 286(5439): 509.

Beamer

Asanovic

Patterson

(2012) Direction-optimizing breadth-first search. In: 2012 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC12), Salt Lake City, UT, US, 10–16 November 2012, pp 1–10.

Brette

Rudolph

Carnevale

. (2007) Simulation of networks of spiking neurons: a review of tools and strategies. Journal of Computational Neuroscience 23(3): 349–398.

Buluç

Madduri

(2011) Parallel breadth-first search on distributed memory systems. In: 2011 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC11), Seattle, WA, US, 12–18 November 2011, pp. 65–76.

Chakrabarti

Zhan

Faloutsos

(2004) R-MAT: a recursive model for graph mining. In: 4th international conference on data mining, Lake Buena Vista, FL, US, 22–24 April 2004, pp 442–446.

Checconi

Petrini

Willcock

. (2012) Breaking the speed and scalability barriers for graph exploration on distributed-memory machines. In: 2012 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC12). Salt Lake City, UT, US, 10–16 November 2012, pp. 1–12.

10.

Chhugani

Satish

Kim

. (2012) Fast and efficient graph traversal algorithm for CPUs: maximizing single-node efficiency. In: 2012 IEEE 26th international parallel and distributed processing symposium (IPDPS12). Shanghai, China, 21–25 May 2012, pp. 378–389.

11.

Dodds

Muhamad

Watts

(2003) An experimental study of search in global social networks. Science 301(5634): 827–829.

12.

Duran

Klemm

(2011) The Intel Many Integrated Core architecture, Intel Corporation.

13.

Hong

Oguntebi

Olukotun

(2011) Efficient parallel graph exploration on multi-core CPU and GPU. In: Parallel architectures and compilation techniques (PACT). Galveston Island, TX, US, 10–14 October 2011, pp. 78–88.

14.

Leskovec

Chakrabarti

Kleinberg

. (2010) Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research 11: 985–1042.

15.

Lumsdaine

Gregor

Hendrickson

. (2007) Challenges in parallel graph processing. Parallel Processing Letters 17(1): 5–20.

16.

Manyika

Chui

Brown

. (2011) Big data: the next frontier for innovation, competition, and productivity, McKinsey Global Institute.

17.

Merrill

Garland

Grimshaw

(2012) Scalable GPU graph traversal. In: 17th ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP12). New Orleans, LA, US, 25–29 February 2012, pp. 117–128.

18.

Murphy

Wheeler

Barrett

. (2010) Introducing the Graph 500, Cray User’s Group (CUG).

19.

Satish

Kim

Chhugani

. (2012) Large-scale energy-effcient graph traversal: a path to efficient data-intensive supercomputing. In: 2012 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC12), Salt Lake City, UT, US, 10–16 November 2012, pp. 14.

20.

Saule

Catalyurek

(2012) An early evaluation of the scalability of graph algorithms on the intel mic architecture. In: 2012 IEEE 26th international parallel and distributed processing symposium workshop (IPDPSW), Shanghai, China, 21–25 May 2012, pp. 1629–1639.

21.

Tao

Yutong

Guang

(2013) Using MIC to accelerate a typical data-intensive application: the breadth-first search. In: 2013 IEEE 27th international parallel and distributed processing symposium workshop and PhD forum (IPDPSW), Boston, MA, US, 20–24 May 2013, pp. 1117–1125.

22.

Watts

Strogatz

(1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684): 440–442.

23.

Yang

Liao

. (2010) Th-1: China’s first petaﬂop supercomputer. Frontiers of Computer Science in China 4(4): 445–455.

24.

Yang

Chen

. (2013) Accelerating PQMRCGSTAB Algorithm on Xeon Phi. Advanced Materials Research 709: 555–562.

25.

Yoo

Chow

Henderson

. (2005) A scalable distributed parallel breadth-first search algorithm on BlueGene/L. In: 2005 ACM/IEEE international conference for high performance computing, networking, storage and analysis (SC05), Seatle, WA, US, 12–18 November 2005, pp. 25–34.