Understanding Concurrency for Graph Workloads in Large Scale Multicores

Algorithms operating on a graph setting are known to be highly irregular and un- structured. This leads to workload imbalance and data locality challenge when these algorithms are parallelized and executed on the evolving multicore processors. Previous parallel benchmark suites for shared memory multicores have focused on various workload domains, such as scientific, graphics, and vision. However, these suites lack graph applications that must be evaluated in the context of architectural design space for futuristic multicores. This paper presents CRONO, a benchmark suite composed of multi-threaded graph algorithms for shared memory multicore processors. We analyze and characterize these benchmarks using a multicore simulator, as well as a real multicore machine setup. CRONO uses both synthetic and real world graphs. Our characterization shows that graph benchmarks are diverse and challenging in the context of scaling efficiency. They exhibit low locality due to unstructured memory access patterns, and incur fine-grain communication between threads. Our characterization also reveals that these challenges remain in state-of-the-art graph algorithms, and in this context CRONO can be used to identify develop novel architectural methods to mitigate efficiency bottlenecks in futuristic multicore processors