  For parallel breadth first search (BFS) algorithm on large-scale distributed
memory systems, communication often costs significantly more than arithmetic
and limits the scalability of the algorithm. In this paper we sufficiently
reduce the communication cost in distributed BFS by compressing and sieving the
messages. First, we leverage a bitmap compression algorithm to reduce the size
of messages before communication. Second, we propose a novel distributed
directory algorithm, cross directory, to sieve the redundant data in messages.
Experiments on a 6,144-core SMP cluster show our algorithm outperforms the
baseline implementation in Graph500 by 2.2 times, reduces its communication
time by 79.0%, and achieves a performance rate of 12.1 GTEPS (billion edge
visits per second)
