Optimizing BreadthFirst Search at Scale Using HardwareAccelerated Space Consistency Graph traversal is a critical building block in many algorithms. Traversing a large graph using breadthfirst search, although conceptually simple, is timeconsuming in distributedmemory environments due to the amount of exchanged data. In this work, we present both an efficient algorithmic approach to carry out the traversal and a lowoverhead runtime that provides efficient primitives to implement the algorithm. Our algorithm relies on constructing a traversal composed of partially consistent trees until all vertices are discovered. We resolve such inconsistency through election and exchange steps. The election phase relies on communicating compressed vertices through collectives that do not stress the bisection bandwidth of the interconnect. We leverage the space consistency programming abstraction to allow an efficient overlap of computation with communication. We extend the model to leverage hardware accelerated collectives and provide primitives for onesided broadcast and sparse reduction. We present the algorithm and runtime designs and show the results of applying our techniques on the BluegeneQ architectures. We achieve 1040 GTEPS on a single rack (1K nodes), which is better than the bestknown algorithms on the same architecture. We also achieve superior scalability compared with other implementations up to 32K nodes.

Parallel Finger Search Structures In this paper we present two versions of a parallel finger structure FS on p processors that supports searches, insertions and deletions, and has a finger at each end. This is to our knowledge the first implementation of a parallel search structure that is workoptimal with respect to the finger bound and yet has very good parallelism (within a factor of O( (log p)2 ) of optimal). We utilize an extended implicit batching framework that transparently facilitates the use of FS by any parallel program P that is modelled by a dynamically generated DAG D where each node is either a unittime instruction or a call to FS.  :108,290,total work done by either version of FS is bounded by the finger bound FL (for some linearization L of D ), i.e. each operation on an item with finger distance r takes O( log r  1 ) amortized work; it is cheaper for items closer to a finger. Running P using the simpler version takes O( ( T1  FL )  p  Tinf  d * ( (log p)2  log n ) ) time on a greedy scheduler, where T1,Tinf are the size and span of D respectively, and n is the maximum number of items in FS, and d is the maximum number of calls to FS along any path in D. Using the faster version, this is reduced to O( ( T1  FL )  p  Tinf  d * (log p)2  sL ) time, where sL is the weighted span of D where each call to FS is weighted by its cost according to FL. We also sketch how to extend FS to support a fixed number of movable fingers.  data structures in our paper fit into the dynamic multithreading paradigm, and their performance bounds are directly composable with other data structures given in the same paradigm. Also, the results can be translated to practical implementations using workstealing schedulers.