CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority under 35 U.S.C. § 119 to Korean Patent Application No. 10-2019-0104278, filed on Aug. 26, 2019, which is incorporated herein by reference in its entirety.

BACKGROUND

1. Field

Various embodiments of the invention relate to a graph processing system, and particularly, to a graph processing system including different kinds of memory devices and a method for operating the graph processing system.

2. Discussion of the Related Art

With the advent of the big data era, a graph-based data structure for efficiently expressing and analyzing the relationships between data plays an important role in machine learning and various data analyses. Accordingly, various graph algorithms are actually being used as main applications in corporate data centers.

For example, Google's PageRank (Reference 1: Ian Rogers, “The Google PageRank Algorithm and How It Works”, 2002) and Twitter's connected component algorithm (Reference 2: David Ediger, Karl Jiang, Jason Riedy, David A. Bader, and Courtney Corley, “Massive Social Network Analysis: Mining Twitter for Social Good” in ICPP, 2010) discuss representative graph-based data analysis applications.

Systems which apply a general purpose graphics processing unit (GPGPU) are used in many computation domains to satisfy high numbers of computations demanded by graph applications. However, because it is the norm that only a volatile memory device having relatively small capacity is included in a GPGPU system, frequent page swapping with respect to the volatile memory device and frequent data copying between a host and a device occur as illustrated inFIG. 1, which may cause degradation in the performance of the applications.FIG. 1shows a case in which the volatile memory device has 16 GB capacity and the size of the graph data is 16 TB.

Furthermore, since a main ending condition of a graph algorithm is saturation, after a number of iterative computations are performed, a checkpoint operation of storing a computation result in a separate storage device connected with the GPGPU system is required for efficient failure recovery. However, since it is the norm that the separate storage device connected with the GPGPU system uses a disk/flash-based storage device, a problem may be encountered in that, in the GPGPU system, a time required for the checkpoint operation of storing a computation result in the storage device is longer than a time required to perform computations.

For example, in the case of the Google's PageRank algorithm described above, the computation time required is 30 seconds, but 60 the checkpoint time required is 60 seconds (Reference 3: Yanyan Shen, Gang Chen, H. V. Jagadish, Wei Lu, Beng Chin Ooi, and Bogdan Marious Tudor, “Fast Failure Recovery in Distributed Graph Processing Systems” in VLDB, 2014).

SUMMARY

Various embodiments are directed to a graph processing system including two kinds of memory devices having different characteristics and thereby effectively checkpointing a graph computation result while quickly performing iterative graph computations on graph data, and a method for operating the graph processing system.

In accordance with an embodiment of the present invention, a method for operating a graph processing system including a first memory device and a second memory device, the method may include: storing, as a first storage operation, in the first memory device, a start vertex index, a terminal vertex index and an edge value between a start vertex and a terminal vertex, of graph data inputted from a host; storing, as a second storage operation, in the second memory device, a start vertex value of the graph data; rearranging the start vertex value as an intermediate vertex value by using to the start vertex index; performing a graph computation on the intermediate vertex value by using to the terminal vertex index and the edge value; storing, as a third storage operation, in the second memory device, a terminal vertex value as a result of the graph computation; determining whether a graph processing operation is completed by comparing the terminal vertex value and the start vertex value; setting the terminal vertex value as the start vertex value when the graph processing operation is determined as not completed; and iterating the rearranging, the performing, the third storage operation, the determining and the setting until it is determined that the graph processing operation is completed.

The method further may include: storing, as a fourth storage operation, the terminal vertex value in the first memory device, as the result of the graph processing operation, when it is determined that the graph processing operation is completed.

The method further may include: storing, as an intermediate storage operation, when it is determined that the graph processing operation is not completed, and storing the terminal vertex value in the first memory device as an intermediate result of the graph processing operation, depending on a number of times the determining operation is performed.

A period in which the intermediate storage operation may be performed overlaps with a period in which the setting, the rearranging, the performing, the third storage and the determining operations are performed through the iterating.

When the intermediate storage operation is performed at least twice, a storage area of the first memory device which is used in a preceding intermediate storage operation and a storage area of the first memory device which is used in a following intermediate storage operation may be different from each other, and the storage area which is used in the preceding intermediate storage operation may be released when the following intermediate storage operation is completed.

A storage area of the first memory device which is used in the intermediate storage operation and a storage area of the first memory device which is used in the fourth storage operation may be different from each other, and the storage area which is used in the intermediate storage operation may be released when the fourth storage operation is completed.

The performing of the graph computation may include generating a message, the method may further include: storing, as a fifth storage operation, in the second memory device, the message to correspond to the terminal vertex value.

The first memory device may be a nonvolatile memory device which inputs/outputs data in the unit of a page, and the second memory device may be a volatile memory device which inputs/outputs data in the unit of a bit.

The graph data may include a plurality of pieces of data that include a plurality of start vertex indexes, a plurality of terminal vertex indexes, a plurality of edge values and a plurality of start vertex values, respectively. The first storage operation may include: grouping the plurality of start vertex indexes, the plurality of terminal vertex indexes, and the plurality of edge values in units of pages; and storing, as sixth storage operation, the pages in the first memory device, and the second storage operation may include storing the start vertex values in the second memory device.

In accordance with an embodiment of the present invention, a graph processing system may include: a first memory device; a second memory device; and a graph processing device configured to: may store, as a first storage operation, in the first memory device, a start vertex index, a terminal vertex index and an edge value between a start vertex and a terminal vertex of graph data inputted from a host; may store, as a second storage operation, in the second memory device, a start vertex value in the graph data; rearrange the start vertex value as an intermediate vertex value based on the start vertex index; may perform a graph computation on the intermediate vertex value based on the terminal vertex index and the edge value; may store, as a third storage operation, in the second memory device, a terminal vertex value as a result of the graph computation; may determine whether a graph processing operation is completed by comparing the terminal vertex value and the start vertex value; may set the terminal vertex value as the start vertex value when it is determined that the graph processing operation is not completed; and may iterate the rearrange, perform, third storage, determine and set operations until it is determined that the graph processing operation is completed.

The graph processing device is further configured to: may store, as an intermediate storage operation, when it is determined that the graph processing operation is not completed, the terminal vertex value in the first memory device as an intermediate result of the graph processing operation, depending on a number of times the determination act is performed; and may store, as a fourth storage operation, the terminal vertex value in the first memory device, as the result of the graph processing operation, when it is determined that the graph processing operation is completed.

The graph processing device may further control a period in which the intermediate storage operation is performed, to overlap with a period in which the set, rearrange, perform, third storage and determine operations are performed through the iterate operation.

The graph processing device is further configured to: may set, when the intermediate storage operation is performed at least twice, a storage area used in the first memory device in a preceding intermediate storage operation and a storage area used in the first memory device in a following intermediate storage operation to be different from each other, and may release the storage area used in the preceding intermediate storage operation when the following intermediate storage operation is completed.

The graph processing device is further configured to: may set a storage area used in the first memory device in the intermediate storage operation and a storage area used in the first memory device in the fourth storage operation to be different from each other, and may release the storage area used in the intermediate storage operation when the fourth storage operation is completed.

The perform the graph computation operation may include generating a message, and the graph processing device is further configured to may store, as a fifth storage operation, in the second memory device, the message to correspond to the terminal vertex value.

The first memory device may be a nonvolatile memory device which inputs/outputs data in the unit of a page, and the second memory device may be a volatile memory device which inputs/outputs data in the unit of a bit.

The graph data may include a plurality of pieces of data that include a plurality of start vertex indexes, a plurality of terminal vertex indexes, a plurality of edge values and a plurality of start vertex values, respectively. The first storage operation may include: grouping the plurality of start vertex indexes, the plurality of terminal vertex indexes, the plurality of edge values in units of pages; and storing, as a sixth storage operation, the pages in the first memory device, and the second storage operation may include storing the start vertex values in the second memory device.

In accordance with an embodiment of the present invention, a graph processing system may include: a first memory device configured to store a read-only portion of graph data inputted from a host; a second memory device configured to store a read-and-write portion of the graph data; and a graph processor configured to: may perform a super step operation iteratively based on the graph data distributed in the first and second memory devices; and may perform, each time after a set number of the iterations are performed, a checkpointing operation of storing a result of a last of the set number of the iterations, the first memory device may have a greater storage capacity than the second memory device, and the second memory device may have a higher operation speed than the first memory device.

The read-only portion may include a start vertex index, a terminal vertex index and an edge value between a start vertex and a terminal vertex in each piece of the graph data, and the read-and-write portion may include a start vertex value of a row.

The first memory device respectively may store, on a group basis, the start vertex indexes, the terminal vertex indexes and the edge values in plural pieces of the graph data, and each of the groups may have a size corresponding to a storage element of the first memory device.

In embodiments of the present invention, by distributedly storing graph data inputted from a host, in two kinds of memory devices having different characteristics, it is possible to quickly perform iterative graph computations on the graph data while effectively storing the graph data.

