ABSTRACT

Large, real-world graphs are famously difficult to process efficiently. Not only do 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 talk will present the advantages of graph processing on hybrid systems: that is, systems that host both traditional CPUs and discrete GPUs systems.

To this end, this talk will: (i) present a performance model that highlights the achievable performance on gains enabled by hybrid systems; (ii) introduce TOTEM - a processing engine based on the Bulk Synchronous Parallel (BSP) model that offers a convenient environment to implement of graph algorithms on these systems; (iii) present strategies for graph partitioning that lead to non-linear performance gains by matching the resulting workload to the processing element that best matches its characteristics; and, finally, (iv) highlight TOTEM'S efficiency by presenting performance numbers for a set of graph algorithms that present a diverse set of challenges.

More information about the TOTEM project: http://netsyslab.ece.ubc.ca/wiki/index.php/Totem

BIOGRAPHY

Matei Ripeanu received his Ph.D. degree in Computer Science from The University of Chicago in 2005. After a brief visiting period with Argonne National Laboratory, Matei joined the Electrical and Computer Engineering Department of the University of British Columbia. Matei is broadly interested in distributed systems with a focus on self-organization and decentralized control in large-scale Grid and peer-to-peer systems.

http://www.ece.ubc.ca/~matei/