公开(公告)号：EP2761435A4

公开(公告)日：2015-10-14

申请号：EP11873205

申请日：2011-09-29

Applicant: INTEL CORP

Inventor： SATISH NADATHUR RAJAGOPALAN ,  KIM CHANGKYU ,  CHHUGANI JATIN ,  SEWALL JASON D

IPC: G06F9/38 ,  G06F9/06 ,  G06F9/52 ,  G06F13/14 ,  G06F15/80 ,  G06F17/10

CPC classification number: G06F9/52

Abstract: Methods, apparatuses and storage device associated with cache and/or socket sensitive breadth-first iterative traversal of a graph by parallel threads, are described. A vertices visited array (VIS) may be employed to track graph vertices visited. VIS may be partitioned into VIS sub-arrays, taking into consideration cache sizes of LLC, to reduce likelihood of evictions. Potential boundary vertices arrays (PBV) may be employed to store potential boundary vertices for a next iteration, for vertices being visited in a current iteration. The number of PBV generated for each thread may take into consideration a number of sockets, over which the processor cores employed are distributed. The threads may be load balanced; further data locality awareness to reduce inter-socket communication may be considered, and/or lock-and-atomic free update operations may be employed.

Abstract translation: 描述了通过并行线程与缓存和/或套接字敏感的宽度优先迭代图相关联的方法，装置和存储装置。 可以使用顶点访问阵列（VIS）来跟踪所访问的图形顶点。 VIS可以分为VIS子阵列，考虑到LLC的缓存大小，以减少驱逐的可能性。 可以使用潜在边界顶点阵列（PBV）来存储用于下一次迭代的潜在边界顶点，用于在当前迭代中被访问的顶点。 为每个线程生成的PBV的数量可以考虑多个套接字，所采用的处理器核在其上分布。 螺纹可以是负载平衡的; 可以考虑减少套接字间通信的进一步的数据局部性意识，和/或可以采用锁定和无原子的更新操作。

公开(公告)号：EP2751667A4

公开(公告)日：2015-07-15

申请号：EP11871468

申请日：2011-08-29

Applicant: INTEL CORP

Inventor： SEWALL JASON D ,  KIM CHANGKYA ,  CHHUGANI JATIN ,  SATISH NADATHUR RAJAGOPALAN

IPC: G06F9/38 ,  G06F9/06

CPC classification number: G06F17/30327 ,  G06F9/5005 ,  G06F2209/5018

Abstract: Embodiments of techniques and systems for parallel processing of B+ trees are described. A parallel B+ tree processing module with partitioning and redistribution may include a set of threads executing a batch of B+ tree operations on a B+ tree in parallel. The batch of operations may be partitioned amongst the threads. Next, a search may be performed to determine which leaf nodes in the B+ tree are to be affected by which operations. Then, the threads may redistribute operations between each other such that multiple threads will not operate on the same leaf node. The threads may then perform B+ tree operations on the leaf nodes of the B+ tree in parallel. Subsequent modifications to nodes in the B+ may similarly be redistributed and performed in parallel as the threads work up the tree.

Abstract translation: 描述了B +树的并行处理技术和系统的实施例。 具有分区和再分配的并行B +树处理模块可以包括一组在B +树上并行执行一批B +树操作的线程。 该批操作可以在线程之间进行分区。 接下来，可以执行搜索以确定B +树中的哪些叶节点将受哪个操作的影响。 然后，线程可以在彼此之间重新分配操作，使得多个线程将不在同一叶节点上操作。 然后，线程可以并行地在B +树的叶节点上执行B +树操作。 当线程处理树时，对B +中的节点的后续修改可以类似地重新分布并且并行执行。