Patent ID: 8533432

Claim:
At least one non-transitory computer-readable storage device having a plurality of instructions configured to enable a plurality of threads of an apparatus, in response to execution of a plurality of instances of the instructions by a plurality of processor cores of the apparatus, to: partition a vertices visited array (VIS) into a plurality of VIS sub-arrays, wherein the VIS is to be employed by the threads to track visited vertices of a graph to be breadth-first traversed by the threads, wherein the processor cores are associated with one or more last level caches (LLC) having respective cache size(s) employed to cache the VIS sub-arrays during traversal of the graph; and wherein the VIS sub-arrays have sub-array sizes that are smaller than the cache sizes of the LLC the VIS sub-arrays are cached by respective amount(s) to reduce likelihood of eviction of any of the sub-arrays from the LLC during traversal of the graph; and breadth-first traverse the graph, after the partition, with the threads successively traversing different breadth spans of the graph in a plurality of iterations, one breadth span during each iteration, wherein the threads traverse different portions of a breadth span of the graph in parallel, respectively using different ones of the VIS sub-arrays, and lock-and-atomic free operations to update depth and parent values of the vertices of the different portions visited.