Systems, methods, and devices for data propagation in graph processing

US12020079B2 · kind B2 · utility

Assignee

• SAMSUNG ELECTRONICS CO., LTD. · KR

Inventors

• Soheil Khadirsharbiyani · State College, US
• Nima Elyasi · State College, US
• Armin Haj Aboutalebi · San Jose, US
• Changho Choi · San Jose, US

Key dates

• Filing date: Feb 8, 2021
• Grant date: Jun 25, 2024
• Expiry date: Nov 4, 2042

Classification

• Technology area (CPC —): General

Abstract

A method of partitioning a graph for processing may include sorting two or more vertices of the graph based on incoming edges and outgoing edges, placing a first one of the vertices with fewer incoming edges in a first partition, and placing a second one of the vertices with fewer outgoing edges in a second partition. The first one of the vertices may have a lowest number of incoming edges, and the first one of the vertices may be placed in a first available partition. The second one of the vertices may have a lowest number of outgoing edges, and the second one of the vertices may be placed in a second available partition. A method for updating vertices of a graph may include storing a first update in a first buffer, storing a second update in a second buffer, and transferring the first and second updates to a memory using different threads.