Paper describes a method of distributing workloads, designed to improve the efficiency of parallel breadth-first search algorithm. A detailed description of the algorithm which based on this method and its implementation for massively parallel architecture of GPU-accelerators is presented. It is shown that using this method allows to achieve high graph traversal rates.