Breadth-First Search on a MapReduce One-Chip System

Abstract

An implementation of a newly developed parallel graph traversal algorithm on a new one-chip many-core structure with a MapReduce architecture is presented. The generic structure's main features and performances are described. The developed algorithm uses the representation of the graph as a matrix and the new MapReduce structure performs best on matrix-vector operations so, the algorithm considers both, dense and sparse matrix cases. A Verilog based simulator is used for evaluation. The main outcome of the presented research is that our MapReduce architecture (with P execution units and the size in O(P)) has the same theoretical time performance: O(NlogN) for P = N = |V | = number of vertices in the graph, as the hypercube architecture (having P processors and the size in O(PlogP)). Also, the actual energy performance of our architecture is 7 pJ for 32-bit integer operation, compared with the ~150pJ per operation of the current many-cores.