PNNL

Abstract

Numerous applications require the exploration of large graphs. The problem has been tackled in the past through a variety of solutions, either based on commodity processors or dedicated hardware. Processors based on multiple cores, like the Cell Broadband Engine (CBE), are gaining popularity as basic building blocks for high performance clusters. Nevertheless, no studies have still investigated how effectively the CBE architecture can explore large graphs, and how its performance compares with other architectural solutions. In this paper, we describe the challenges and design choices involved in mapping a breadth-first search (BFS) algorithm on the CBE. Our implementation has been driven by an accurate performance model, that has allowed seamless coordination between onchip communication, off-chip memory access, and computation. Preliminary results obtained on a pre-production prototype running at 2.4 GHz show almost linear speedups when using multiple synergistic processing units and impressive levels of performance when compared to other processors.