发明名称 |
CACHE AND/OR SOCKET SENSITIVE MULTI-PROCESSOR CORES BREADTH-FIRST TRAVERSAL |
摘要 |
Methods, apparatuses and storage device associated with cache and/or socket sensitive breadth-first iterative traversal of a graph by parallel threads, are disclosed. In embodiments, 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. In embodiments, 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. In various embodiments, 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. Other embodiments may be disclosed or claimed. |
申请公布号 |
WO2013048413(A1) |
申请公布日期 |
2013.04.04 |
申请号 |
WO2011US54016 |
申请日期 |
2011.09.29 |
申请人 |
INTEL CORPORATION;SATISH, NADATHUR RAJAGOPALAN;KIM, CHANGKYU;CHHUGANI, JATIN;SEWALL, JASON D. |
发明人 |
SATISH, NADATHUR RAJAGOPALAN;KIM, CHANGKYU;CHHUGANI, JATIN;SEWALL, JASON D. |
分类号 |
G06F9/38;G06F9/06;G06F13/14;G06F15/80 |
主分类号 |
G06F9/38 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|