Research and ACM SRC Posters Archive

Algebraic Breadth-First Search on the Cerebras Wafer-Scale Engine


Poster Type: ACM SRC Posters

Author: Elia Belli (Sapienza University of Rome), Daniele De Sensi (Sapienza University of Rome)

Abstract: Graph traversal is memory bound on conventional hardware: irregular access defeats the cache hierarchy. The Cerebras WSE-3 gives each of its 900,000 cores its own 48 KB of SRAM, turning irregular access into local access, but leaves them coordinating over a 2D mesh and a slow host-device link. We present an algebraic BFS that runs entirely on device, avoiding the link that host-callable SpMV kernels would cross every iteration. Sweeping Graph500-specification R-MAT graphs from scale 10 to 20 across PE grids up to 750x750, we find adding cores helps only up to a point, past which larger collectives outweigh the smaller share of work per PE. At that turning point up to 89% of device time goes into collectives, while exporting results costs two orders of magnitude more than the search itself. Within the kernel, distributed on-chip memory removes the memory wall and leaves collective communication as the next target.

Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing