# Presentation: 423440

## When Don’t I Use MPI?

**Jonathan Berry  **
**Scalable Algorithms Department**
**Sandia National Laboratories**
**June 3, 2008**

## Informatics Datasets Are Different

**Informatics Datasets Are Different**

**Informatics**: The analysis of datasets arising from “information” sources such as the WWW (not physical simulation)
**Motivating Applications:**
-  Homeland security
-  Computer security (DOE emphasis)
-  Biological networks, etc.

**Primary HPC Implication:** Any partitioning is “bad”

**“***One of the interesting ramifications of the fact that the PageRank calculation converges rapidly is that the web is an expander-like graph***”**
- Page, Brin, Motwani,Winograd  1999

- From UCSD ‘08

- Broder, et al. ‘00

## Informatics Usage Models Can Be Quite Different

## PageRank performs a sequence of matrix-vector multiplications

 “NICE” data are “R-MAT” graphs with maximum degree ~1000

“NASTY” data are R-MAT graphs with maximum degree ~200k 

The MTA-2 runs are nearly data agnostic and have ideal speedup through 20p

The end of MTA-2 scaling indicates that algorithmic work is needed (we’ve seen and overcome behavior like this before)

**PageRank performs a sequence of matrix-vector multiplications**
** “****NICE” data are “R-MAT” graphs with maximum degree ~1000**
**“****NASTY” data are R-MAT graphs with maximum degree ~200k **
**The MTA-2 runs are nearly data agnostic and have ideal speedup through 20p**
**The end of MTA-2 scaling indicates that algorithmic work is needed **(we’ve seen and overcome behavior like this before)

**Multithreaded Architectures Can Boost Performance**

- [K. Devine, S. Plimpton, Berry]

- 33M vertices, 268M directed edges

- Number of Processors

- PageRank time

## MTA/XMT Programming: Use the Compiler

**Here, we sum a quantity over the neighbors of one vertex**
**The removal of the reduction of “sum” prevents a hot spot**
**This output is from “canal,” an MTA/XMT compiler analysis tool**

## We Are Developing The MultiThreaded Graph Library

**We Are Developing The MultiThreaded Graph Library**

- Enables multithreaded graph algorithms (XMT, SMP, Niagara)
- Builds upon community standard (Boost Graph Library)
- Abstracts data structures and other application specifics
- Hide some shared memory issues
- Preserves good multithreaded performance

- MTGL

- MTGL

- C

- C

- S-T connectivity scaling (MTA-2)

- SSSP scaling (MTA-2)

- MTA-2 Processors

- MTA-2 Processors

- Solve time (sec)

- Solve time (sec)

## Current MTGL Algorithms

**Connected components (****psearch, visit_edges, visit_adj****)**
**Strongly-connected components (****psearch****)**
**Maximal independent set (****visit_edges****)**
**Typed subgraph isomorphism (****psearch, visit_edges****)**
**S-t connectivity (****bfs****)**
**Single-source shortest paths (****psearch****)**
**Betweenness centrality (bfs-like)**
**Community detection (****all kernels****)**
**Connection subgraphs (****bfs, sparse matrix, mt-quicksort****)**
**Find triangles (****psearch****)**
**Find assortativity (****psearch****)**
**Find modularity (****psearch****)**
**PageRank (****matvec****)**
**Network Simplex for MaxFlow**
***Under development:***
**Motif detection**
**more**

- Berkeley Open-Source Licence pending

## Acknowledgements

**MultiThreading Background**
- Simon Kahan (formerly Cray)
- Petr Konecny (Google (formerly Cray))
**MultiThreading/Distributed Memory Comparisons**
- Karen Devine (Sandia)
- Steve Plimpton (Sandia)
**MTGL Algorithm Design and Development**
- Vitus Leung (Sandia)
- Kamesh Madduri (Georgia Tech.)
- William McLendon (Sandia)
- Cynthia Phillips (Sandia)
**Generic Programming Background**
- Andrew Lumsdaine (Indiana U.)
- Doug Gregor (Indiana U.)