Name
Abstract | ||
|---|---|---|
Large, real-world graphs are famously difficult to process efficiently. Not only they have a large memory footprint but most graph processing algorithms entail memory access patterns with poor locality, data-dependent parallelism, and a low compute-to- memory access ratio. Additionally, most real-world graphs have a low diameter and a highly heterogeneous node degree distribution. Partitioning these graphs and simultaneously achieve access locality and load-balancing is difficult if not impossible. This paper demonstrates the feasibility of graph processing on heterogeneous (i.e., including both CPUs and GPUs) platforms as a cost-effective approach towards addressing the graph processing challenges above. To this end, this work (i) presents and evaluates a performance model that estimates the achievable performance on heterogeneous platforms; (ii) introduces TOTEM -- a processing engine based on the Bulk Synchronous Parallel (BSP) model that offers a convenient environment to simplify the implementation of graph algorithms on heterogeneous platforms; and, (iii) demonstrates TOTEM'S efficiency by implementing and evaluating two graph algorithms (PageRank and breadth-first search). TOTEM achieves speedups close to the model's prediction, and applies a number of optimizations that enable linear speedups with respect to the share of the graph offloaded for processing to accelerators. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2370816.2370866 | PACT |
Keywords | Field | DocType |
large memory footprint,graph processing challenge,heterogeneous node degree distribution,heavy lifting graph processing,graph processing algorithm,heterogeneous platform,graph processing,thousand chicken,real-world graph,access locality,graph algorithm,processing engine,load balance,bulk synchronous parallel,degree distribution,breadth first search,process engineering,cost effectiveness | Graph theory,PageRank,Locality,Computer science,CUDA,Breadth-first search,Parallel computing,Degree distribution,Memory footprint,Bulk synchronous parallel | Conference |
ISSN | ISBN | Citations |
1089-795X | 978-1-5090-6609-4 | 46 |
PageRank | References | Authors |
1.47 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abdullah Gharaibeh | 1 | 246 | 16.75 |
| Lauro Beltrao Costa | 2 | 194 | 12.23 |
| Elizeu Santos-Neto | 3 | 418 | 26.42 |
| Matei Ripeanu | 4 | 2461 | 233.84 |