Implementing breadth-first search on a compact supercomputer suiren

Cost and energy efficient supercomputers have received attention not only for scientific computation but for big data processing. In the fields of social networks and biology, the relationship between data is often represented by large target graphs that require huge computation costs to analyze. A new parallel BFS method called degree-chain traversal (DC) is proposed and implemented on the energy efficient compact supercomputer Suiren. In DC, by treating vertices that have the same parents as a form of 'chain', both the communication amount and the number of memory accesses are reduced. Evaluation results show that the total amount of computation was reduced by 30%, and the execution time was shortened by 14%, when tasks are executed with four processes. We also tried to accelerate the execution with PEZY-SC, an MIMD accelerator attached to Suiren. However, the average execution time was not improved because of the large variation in the execution time depending on the root node. Through the analysis, an unbalanced task assignment and a bottleneck of the memory were pointed out. However, this bottleneck is eased by using new PEZY-SC2 which has wider memory bandwidth.