Traversing Trillions of Edges in Real-time: Graph Exploration on Large-scale Parallel Machines

被引：38

作者：

Checconi, Fabio ^{[1
]}

Petrini, Fabrizio ^{[1
]}

机构：

[1] IBM TJ Watson, High Performance Analyt Dept, Yorktown Hts, NY 10598 USA

来源：

2014 IEEE 28TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM | 2014年

关键词：

ALGORITHMS;

D O I：

10.1109/IPDPS.2014.52

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The world of Big Data is changing dramatically right before our eyes-from the amount of data being produced to the way in which it is structured and used. The trend of "big data growth" presents enormous challenges, but it also presents incredible scientific and business opportunities. Together with the data explosion, we are also witnessing a dramatic increase in data processing capabilities, thanks to new powerful parallel computer architectures and more sophisticated algorithms. In this paper we describe the algorithmic design and the optimization techniques that led to the unprecedented processing rate of 15.3 trillion edges per second on 64 thousand BlueGene/Q nodes, that allowed the in-memory exploration of a petabyte-scale graph in just a few seconds. This paper provides insight into our parallelization and optimization techniques. We believe that these techniques can be successfully applied to a broader class of graph algorithms.

引用

页数：10

共 28 条

[21]

Pearce R., 2013, P 24 INT S PAR DISTR

[22] SKIP LISTS - A PROBABILISTIC ALTERNATIVE TO BALANCED TREES [J].

PUGH, W .

COMMUNICATIONS OF THE ACM, 1990, 33 (06) :668-676

[23] An Early Evaluation of the Scalability of Graph Algorithms on the Intel MIC Architecture [J].

Saule, Erik ;

Catalyuerek, Uemit V. .

2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW), 2012, :1629-1639

[24]

Seshadhri C., 2011, Proceedings of the 2011 IEEE 11th International Conference on Data Mining (ICDM 2011), P587, DOI 10.1109/ICDM.2011.23

[25]

Sud A, 2007, IEEE VIRTUAL REALITY 2007, PROCEEDINGS, P91

[26]

Sungpack Hong, 2011, Proceedings 2011 International Conference on Parallel Architectures and Compilation Techniques (PACT), P78, DOI 10.1109/PACT.2011.14

[27]

Yoo Andy., 2005, Supercomputing, P25, DOI DOI 10.1109/SC.2005.4

[28]

Zhang L., 2006, P INT WORKSH ALG FDN

← 1 2 3 →