Browse Prior Art Database

Highly Parallelized Task Execution in Graph Processing Systems

IP.com Disclosure Number: IPCOM000248721D
Publication Date: 2016-Dec-29
Document File: 2 page(s) / 40K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a system for parallel execution in graph processing systems, which holds overlapping tasks on the same central processing unit (CPU) queue to avoid cross CPU synchronization issues.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 62% of the total text.

1

Highly Parallelized Task Execution in Graph Processing Systems

Existing parallelization mechanisms in graph processing systems can result in too many synchronization latencies and locked operations due to intersected parallel sub-graph assignments. This causes inefficient central processing unit (CPU) utilization, inefficient parallelism, and increased execution times.

To achieve complete parallelism, similar tasks (i.e., tasks that contain same partitions) should be scheduled into the same queue and dissimilar tasks (i.e., tasks that contain few of the same partitions) should be held in different queues.

The novel solution is to implement a locality sensitive task to the CPU assignment method. The system provides parallel execution in graph processing systems, which holds overlapping tasks on the same central processing unit (CPU) queue to avoid cross CPU synchronization issues. In addition to highly parallelized task executions, the system provides almost maximal CPU and memory and decreased input/output (I/O) utilization in graph processing systems.

The core idea is to use a locality sensitive technique to put similar tasks into similar queues and dissimilar tasks to different queues. Similarity detection mechanisms, such as locality sensitive hashing (LSH), genetic algorithms, etc., are used to find overlapping tasks. In a multicore system having k cores, the new approach assigns n tasks into k cores where each core has nearly n/k tasks. This minimizes the intersection...