Patent ID: 11875426
Assignee: SHANGHAI JIAO TONG UNIVERSITY
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 6:
7. The graph sampling and random walk acceleration method based on a GPU according to claim 1, wherein said generating an alias table for a full graph specifically includes:
step 1: the thread block of each GPU core function requests a task from the global task queue; when the number of vertices to be sampled in the task is obtained and d<T1, the threads in one sub-warp perform collaborative processing on the vertices, that is, multiple threads at the same time, calculate the alias table for a vertex together; when T1<d<T2, the vertex is temporarily added to the local task queue for subsequent processing; when T2<d, the vertex is added to the global height vertex task Queue, where T1 and T2 are two adjustable thresholds, which are 32 and 256 in practice; d is the out-degree of the vertex, that is, the number of edges emitted by the vertex;
step 2: when the global task queue corresponding to this iteration is empty, the completed thread in a warp waits for other threads in the same warp to participate in the processing of the local task queue;
step 3: when the local task queue corresponding to the current iteration is empty, the completed thread in one thread block waits for other threads in the same thread block to participate in the processing of the global high-degree vertex task queue; and
step 4: each thread checks whether the current sampling depth is equal to the target sampling depth; when the sampling does not reach the target depth, repeat steps 1-4 for iteration, otherwise the processing ends.