Title :
Scalable Triadic Analysis of Large-Scale Graphs: Multi-core vs. Multi-processor vs. Multi-threaded Shared Memory Architectures
Author :
Chin, George, Jr. ; Marquez, Andres ; Choudhury, Sutanay ; Feo, John
Author_Institution :
Pacific Northwest Nat. Lab., CA, USA
Abstract :
Triadic analysis encompasses a useful set of graph mining methods that are centered on the concept of a triad, which is a sub graph of three nodes. Such methods are often applied in the social sciences as well as many other diverse fields. Triadic methods commonly operate on a triad census that counts the number of triads of every possible edge configuration in a graph. Like other graph algorithms, triadic census algorithms do not scale well when graphs reach tens of millions to billions of nodes. To enable the triadic analysis of large-scale graphs, we developed and optimized a triad census algorithm to efficiently execute on shared memory architectures. We then conducted performance evaluations of the parallel triad census algorithm on three specific systems: CrayXMT, HP Superdome, and AMD multi-core NUMA machine. These three systems have shared memory architectures but with markedly different hardware capabilities to manage parallelism.
Keywords :
graph theory; multi-threading; parallel algorithms; parallel architectures; shared memory systems; AMD multicore NUMA machine; CrayXMT; HP Superdome; graph algorithm; graph edge configuration; graph mining method; hardware capability; large-scale graph; multicore shared memory architecture; multiprocessor shared memory architecture; multithreaded shared memory architecture; parallel triad census algorithm; parallelism management; performance evaluation; scalable triadic analysis; triadic census algorithm; triadic method; Algorithm design and analysis; Arrays; Instruction sets; Patents; Social network services; Vectors;
Conference_Titel :
Computer Architecture and High Performance Computing (SBAC-PAD), 2012 IEEE 24th International Symposium on
Conference_Location :
New York, NY
Print_ISBN :
978-1-4673-4790-7
DOI :
10.1109/SBAC-PAD.2012.39