Scalable Triadic Analysis of Large-Scale Graphs: Multi-core vs. Multi-processor vs. Multi-threaded Shared Memory Architectures

• George Chin Jr. Pacific Northwest National Laboratory
• Andres Marquez Pacific Northwest National Laboratory
• Sutanay Choudhury Pacific Northwest National Laboratory
• John Feo Pacific Northwest National Laboratory

Resumo

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.

Palavras-chave: Algorithm design and analysis, Arrays, Instruction sets, Social network services, Patents, Vectors