Crunching Large Graphs With Commodity Processors

Date Added: Apr 2011
Format: PDF

Crunching large graphs is the basis of many emerging applications, such as social network analysis and bio-informatics. Graph analytics algorithms exhibit little locality and therefore present significant performance challenges. Hardware multi-threading systems (e.g., Cray XMT) show that with enough concurrency, the authors can tolerate long latencies. Unfortunately, this solution is not available with commodity parts. Their goal is to develop a latency-tolerant system built out of commodity parts and mostly in software. The proposed system includes a run-time that supports a large number of lightweight contexts, full-bit synchronization and a memory manager that provides a high-latency but high-bandwidth global shared memory.