US 2026/0073468 A1 · LARGE GRAPH PARTITIONING METHOD USING STREAMING CLUSTERING IN GPU ENVIRONMENT

Abstract

Provided is a large graph partitioning method using streaming clustering in a GPU environment. A CPU gradually compresses graph data by considering a structural environment of a GPU and then transfers the compressed graph data to a GPU memory to perform graph partitioning, thereby utilizing the memory of the GPU most efficiently and performing fast graph processing. As a result, the large graph partitioning method using streaming clustering in a GPU environment relates to a technology that can effectively process connection information for all clusters in parallel by utilizing the high computational amount of the GPU and overcome the memory limitations of the GPU by processing computations that require a large memory space in the CPU.

Claims9

Dependent claims

A large graph partitioning method using streaming clustering in a GPU environment, the large graph partitioning method comprising:

an input operation of receiving, by a CPU, which is a host, original graph data;
a clustering operation of generating, by the CPU, a cluster map array for the received original graph data using a streaming clustering algorithm and generating cluster graph data using the cluster map array generated for the original graph data;
a transmission operation of receiving, by a GPU, the generated cluster graph data;
an initial partitioning operation of performing, by the GPU, initial partitioning on the received cluster graph data by applying a pre-stored algorithm;
and
an optimization operation of receiving, by the CPU, assigned partition label data, which is an initial partitioning result, and performing optimization on the assigned partition label data using the generated cluster map array.

3 more elements

Dependencies are inferred from the claim text.

Large graph partitioning method using streaming clustering in gpu environment

Life of this patent

Large graph partitioning method using streaming clustering in gpu environment

Life of this patent

Abstract

Claims9