Name
Abstract | ||
|---|---|---|
Abstract Search-based graph queries, such as nding short paths and isomorphic subgraphs, are dominated by memory,latency. If input graphs can be partitioned appropriately, large cluster-based computing platforms can run these queries. However, the lack of compute-bound processing at each vertex of the input graph and the constant need to retrieve neighbors implies low processor utilization. Furthermore, graph classes such as scale-free social networks lack the locality to make partitioning clearly eectiv e. Massive multithreading is an alternative architectural paradigm, in which a large shared memory,is combined with processors that have extra hardware to support many thread contexts. The processor speed is typically slower than normal, and there is no data cache. Rather than mitigating memory latency, multithreaded machines tolerate it. This paradigm is well aligned with the problem of graph search, as the high ratio of memory,requests to computation can be tolerated via multithreading. In this paper, we introduce the MultiThreaded Graph Library (MTGL), generic graph query software for processing semantic graphs on multithreaded computers. This library currently runs on serial machines and the Cray MTA-2, but Sandia is developing a run-time system that will make it possible to run MTGL-based code on Symmetric MultiProcessors. We also introduce a multithreaded algorithm for connected |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1109/IPDPS.2007.370685 | IPDPS |
Keywords | Field | DocType |
graph theory,multi-threading,parallel algorithms,shared memory systems,tree searching,Blue Gene-Light,Cray MTA-2,multithreaded architecture,multithreaded graph library,s-t connectivity,search-based graph query,semantic graph,shared memory,symmetric multiprocessor | Computer science,Theoretical computer science,Implicit graph,Subgraph isomorphism problem,Distributed computing,Graph theory,Graph database,Shared memory,Parallel computing,Algorithm,Connected component,Graph rewriting,Graph (abstract data type) | Conference |
Citations | PageRank | References |
32 | 2.15 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jonathan W. Berry | 1 | 445 | 46.01 |
| Bruce Hendrickson | 2 | 1669 | 214.08 |
| Simon Kahan | 3 | 279 | 209.26 |
| Petr Konecny | 4 | 42 | 2.93 |