Cache and/or socket sensitive multi-processor cores breadth-first traversal

A computer-implemented method comprising:

• partitioning, by one or more of a plurality of threads, a vertices visited array (VIS) into a plurality VIS sub-arrays, wherein the VIS sub-arrays are to be employed by the threads to track visited vertices of a graph to be cooperatively breadth-first traversed by the threads, wherein the threads are operated by a plurality of processor cores associated with one or more last level caches (LLC) having respective cache size(s) employed to selectively 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 VIS sub-arrays from the LLC during traversal of the graph;
• and
• after the partitioning, breadth-first traversing the graph, by the plurality of threads, with the plurality of threads successively traversing different breadth spans of the graph in a plurality of iterations, one breadth span during each iteration, and the plurality of threads traversing 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.

An apparatus comprising:

• a shared memory;
• a number (NS) of sockets coupled tot he shared memory;
• and
• a plurality of processor cores distributed in the sockets, with each socket having multiple processor cores;
• wherein each processor core includes one or more hardware context configured to execute one or more threads to cooperatively breadth-first traverse a graph having a plurality of vertices;
• wherein the breadth-first traversal includes prior to the breadth-first traversal of the graph, determine a number (npbv) of potential boundary vertices arrays (PBVt,j) to be initialized, for each thread, and to initialize in the shared memory, on determination, the PBVt,j;
• wherein the PBVt,j are to be used to store and bin potential boundary vertices during an iteration of the breadth-first traversal, j is an integer between 1 and npbv;
• wherein determination of npbv is based at least in part on NS and partition of a vertices visited array (VIS) used to track visited vertices during the breadth-first traversal.

A system comprising:

• an image device;
• a shared memory;
• a number (NS) of sockets having correspondingly associated last level caches (LLC), coupled to the image device and the shared memory;
• a plurality of processor cores distributed in the plurality of sockets;
• with each socket having multiple processor cores;
• wherein each processor core includes one or more hardware context configured to execute one or more threads to cooperatively breadth-first traverse associated with an application associated with operation of the image device or operation on image data of the image device, wherein the breadth-first traversal includes prior to the breadth-first traversal of the graph,
• partition of 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 the graph during the breadth-first traversal, wherein the LLC have respective cache size(s) and 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 VIS sub-arrays from the LLC during traversal of the graph;
• and
• determine a number (npbv) of potential boundary vertices arrays (PBVt,j) to be initialized, for each thread, and to initialize in the shared memory, on determination, the PBVt,j, wherein the PBVt,j are to be used to store and bin potential boundary vertices during an iteration of the breadth-first traversal, j is an integer between 1 and npbv, and determination of npbv is based at least in part on NS and the partition of VIS.