Extreme scale breadth-first search on supercomputers

Koji Ueno, Toyotaro Suzumura, Naoya Maruyama, Katsuki Fujisawa, Satoshi Matsuoka

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    16 Citations (Scopus)


    Breadth-First Search(BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid-BFS algorithm by Beamer[3], we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and optimization techniques such as vertex reordering and load balancing. Performance evaluation on the K shows our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously-known best techniques.

    Original languageEnglish
    Title of host publicationProceedings - 2016 IEEE International Conference on Big Data, Big Data 2016
    EditorsRonay Ak, George Karypis, Yinglong Xia, Xiaohua Tony Hu, Philip S. Yu, James Joshi, Lyle Ungar, Ling Liu, Aki-Hiro Sato, Toyotaro Suzumura, Sudarsan Rachuri, Rama Govindaraju, Weijia Xu
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Number of pages8
    ISBN (Electronic)9781467390040
    Publication statusPublished - 2016
    Event4th IEEE International Conference on Big Data, Big Data 2016 - Washington, United States
    Duration: Dec 5 2016Dec 8 2016

    Publication series

    NameProceedings - 2016 IEEE International Conference on Big Data, Big Data 2016


    Other4th IEEE International Conference on Big Data, Big Data 2016
    Country/TerritoryUnited States

    All Science Journal Classification (ASJC) codes

    • Computer Networks and Communications
    • Information Systems
    • Hardware and Architecture


    Dive into the research topics of 'Extreme scale breadth-first search on supercomputers'. Together they form a unique fingerprint.

    Cite this