CN109522428B - An external memory access method for graph computing system based on index positioning - Google Patents

Abstract

The invention discloses an external memory access method for a graph computing system based on index positioning, comprising: dividing complete graph data into multiple subgraphs; sorting the edges of each subgraph according to source vertex numbers and target vertex numbers respectively; Write the sorted subgraphs into the external memory file, and establish indexes for the source vertex number and the target vertex number respectively; select the optimal loading method from the loading method of index positioning and the loading method of accessing complete data; Load each sub-image in external memory into memory in an optimal loading method. The invention redesigns the external memory data structure, improves the data loading method, enables the system to analyze the valid data in the external memory before loading, significantly reduces the amount of I/O data and the number of random accesses; analyzes and accesses the complete data method and index positioning method It can dynamically determine the optimal data loading method of the system and reduce the time overhead of data loading.

Description

An external memory access method for graph computing system based on index positioning

technical field

The invention belongs to the field of graph computing based on external memory, and more particularly, relates to an external memory access method of a graph computing system based on index positioning.

Background technique

Graph computations are performed by iteratively executing the update function. A common approach used by out-of-memory-based graph computing systems is to organize graph data into multiple subgraph data files on disk, so that each subgraph file can fit into memory. Each subgraph contains vertex information used to compute updates, and one full iteration process will process all subgraph data. The key point is how to manage the calculation state of all subgraphs to ensure the correctness of the processing results, including loading graph data from external memory to memory, and writing intermediate results back to external memory, so that subsequent calculations can get updated results . Therefore, each iteration needs to access a large amount of data, which creates a lot of IO overhead and becomes a bottleneck for out-of-memory-based methods.

The GraphChi system divides the vertices in the graph data into disjoint intervals during preprocessing, and divides the edges into multiple data shards. The data shards correspond to the vertex intervals one-to-one. The target of the edge in each data shard is Vertices correspond to vertices in their respective vertex intervals, and it uses a vertex-centric processing model to collect data from neighboring vertices, execute an update function on each vertex, and compute and update vertex values. A parallel sliding window technique is used to reduce random external memory I/O; Keval Vora et al. proposed a general optimized access method ADS for external memory graph computing systems, which only reads active data. The idea is that at the end of each iteration, the active data in the next round of iterations will be regenerated into new sub-partitions, and only the newly generated sub-partitions will be read in the next round of iterations. At the same time, DELAY_BUFFER is set up in memory to store the vertices that need to be updated but not executed, and the original subgraph is read uniformly every few iterations to update the subgraph located in DELAY_BUFFER.

To sum up, most of the current external memory data access methods in graph computing systems are to load complete subgraph partitions. Whether it is GraphChi using a parallel sliding window or ADS that creates dynamic subgraph partitions, because the external memory data is not divided more carefully, it is impossible to accurately locate and access the data required for computing. At the same time, if you simply use the positioning method to load external memory data, although the amount of loaded data can be reduced and resource utilization can be improved, the original sequential access will be divided into multiple random accesses, which will bring additional time overhead. .

SUMMARY OF THE INVENTION

In view of the defects of the prior art, the purpose of the present invention is to solve the technical problems of large I/O data volume, random access times and time overhead in the external memory access method in the prior art.

In order to achieve the above object, in a first aspect, an embodiment of the present invention provides an external memory access method for a graph computing system based on index positioning, the method includes the following steps:

S0. Divide the complete graph data into multiple subgraphs that the memory can accommodate;

S1. Sort the edges of each subgraph according to the source vertex number and the target vertex number respectively;

S2. Write the sorted subgraphs into the external memory file, and establish indexes for the source vertex number and the target vertex number respectively;

S3. Select the optimal loading method from the loading method of index positioning and the loading method of accessing complete data;

S4. Load each subgraph in the external memory into the memory in an optimal loading manner.

Specifically, the writing of the sorted subgraphs into the external memory file is as follows:

When writing each subgraph after edge sorting into the external memory file, the edges with the same source vertex and target vertex are stored in a continuous external memory data block; the data of the edge includes the edge and the edge value, which are respectively saved in the external memory as Two files: an edge file and an edge value file; the edge file saves the topology of the graph, and the storage format is the adjacency list format; the edge value order in the edge value file corresponds to the edge order in the edge file.

Specifically, the edge file includes: an outgoing edge file according to the number of the source vertex and an incoming edge file according to the number of the target vertex; wherein, the outgoing edge file is organized according to the number of the source vertex, and sequentially and continuously stores the number of the source vertex, the out-degree And the target vertex number of the outgoing edge; the incoming edge file is composed according to the destination vertex number, and sequentially and continuously stores the destination vertex number, the in-degree, and the source vertex number of the incoming edge.

Specifically, the index records the offset address of the edge corresponding to the vertex in the external storage file.

Specifically, the loading method of the index positioning is as follows:

(1) Find the data block that needs to be loaded into the memory in the outbound file according to the index positioning;

(2) According to the offset address of the outgoing edge of the data block that needs to be loaded in the outgoing edge file, find the outgoing edge value data in the edge value file, and load the edge value data into the memory;

(3) Constructing the out-edge topology of vertices in memory;

(4) When the application needs to enter the edge, locate the edge-in data block that needs to be loaded into the memory in the edge-in file according to the index;

(5) According to the input edge offset address of the data block that needs to be loaded in the input edge file, find the edge value offset address of the input edge in the edge value index file, and load the edge value data offset address to the memory;

(6) Construct the incoming edge topology of vertices in memory.

Specifically, step S3 is as follows:

S30. Determine the active vertices of each subgraph, determine whether the active vertex ratio exceeds the threshold, if so, go to step S31, otherwise, the loading mode of accessing the complete data is the optimal loading mode, and end step S3;

S31. Record the data block number corresponding to the active vertex data;

S32. Based on the data block number corresponding to the active vertex data, calculate the cost of the loading mode of index positioning (Index) and the cost of the loading mode of accessing complete data Cost (All);

S33. Determine whether Cost(All) is greater than Cost(Index). If so, the loading method for index positioning is the optimal loading method; otherwise, the loading method for accessing complete data is the optimal loading method.

Specifically, the threshold value ranges from 20% to 30%.

索引定位的载入方式的开销

其中，E为图中所有边的集合；D为单条边所占的存储空间；B为一次I/O的数据块大小；b为每个索引项指向的数据块大小；k为当前系统中所有活跃顶点对应的索引数据块的数量；r为随机访问开销。Specifically, the overhead of the loading method to access the complete data

The cost of loading the index positioning

Among them, E is the set of all edges in the graph; D is the storage space occupied by a single edge; B is the size of the data block of one I/O; b is the size of the data block pointed to by each index entry; k is the size of the data block in the current system The number of index data blocks corresponding to active vertices; r is the random access cost.

In a second aspect, an embodiment of the present invention provides a computer-readable storage medium, where a computer program is stored on the computer-readable storage medium, and when the computer program is executed by a processor, the external memory access method described in the first aspect above is implemented .

In general, compared with the prior art, the above technical method conceived by the present invention has the following beneficial effects:

1. The present invention redesigns the organizational structure of the external memory data in combination with the operating characteristics of the graph application, so that the data of the same vertex is stored in the continuous space of the external memory for easy reading, and is the offset of the data block corresponding to the vertex in the file. The address establishes an index, so as to quickly access the corresponding data block, which improves the data loading method of the system, so that the system can calculate and analyze the valid data in the external memory before the data loading stage, so as to realize the selection of the vertex data required for the loading calculation. , thereby significantly reducing the amount of I/O data and the number of random accesses;

2. The present invention analyzes the time overhead of the original access complete data method and index positioning method, and designs a decision-making and judgment function, which is used to dynamically determine the optimal data loading method of the system in each round of iteration, effectively reducing the time and cost of data loading. time cost.

Description of drawings

1 is a schematic diagram of the correspondence between a boundary value file provided by the present invention and a boundary value offset address file;

FIG. 2 is a schematic diagram of an outbound index file and an outbound file provided by an embodiment of the present invention;

FIG. 3 is a flowchart of step S3 provided by an embodiment of the present invention.

Detailed ways

In order to make the objectives, technical methods and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

A method for accessing external memory of a graph computing system based on index positioning provided by the present invention includes the following steps:

S0. Divide the complete graph data into multiple subgraphs that the memory can accommodate;

S1. Sort the edges of each subgraph according to the source vertex number and the target vertex number respectively;

S2. Write the sorted subgraphs into the external memory file, and establish indexes for the source vertex number and the target vertex number respectively;

S3. Select the optimal loading method from the loading method of index positioning and the loading method of accessing complete data;

S4. Load each subgraph in the external memory into the memory in an optimal loading manner.

The graph computing system mainly consists of a preprocessing stage and a computation execution stage. The preprocessing stage includes reading the original graph data into the memory, processing the data into the format required for system calculation execution, and writing it to the external memory file; the calculation execution stage includes loading the external memory data into the memory, constructing subgraphs in the memory, and performing calculation updates. And the calculation results are written back to external memory. In order to realize the selective loading of external memory data based on the index, subgraph data sorting and indexing are added in the preprocessing stage; decision judgment is added in the calculation execution stage, and the way of loading edge data and edge value data is modified. .

The preprocessing stage of the present invention includes steps S0-S2.

Step S0. Divide the complete graph data into multiple subgraphs that the memory can accommodate.

According to the size of the available memory in the computing resources, the graph data is divided into multiple subgraphs from the complete original data. The amount of subgraph data usually does not exceed the available memory capacity to ensure that the memory can store all the data of a single subgraph.

Step S1. Sort the edges of each subgraph according to the number of the source vertex and the number of the target vertex respectively.

Consider the vertices to be consecutively numbered from 0 to |V|-1, and sort the subgraph data according to the number of the source vertex and the number of the destination vertex, respectively. The vertex set V is the set of all vertices in the graph, and the vertex consists of the vertex number and the value of the vertex itself.

Step S2. Write the sorted subgraphs into the external storage file, and establish indexes for the source vertex number and the target vertex number respectively, and the index records the offset address of the edge corresponding to the vertex in the external storage file.

When writing each subgraph after edge sorting into an external memory file, the edges with the same source vertex and target vertex are stored in a continuous external memory data block. The edge data includes edge and edge value, which are saved as two files in external memory: edge file and edge value file. The edge file saves the topology of the graph, and the storage format is the adjacency list format. The edge files include: outgoing edge files numbered by source vertices and incoming edge files numbered by destination vertices. Among them, the out-edge file is organized according to the source vertex number, and the source vertex number, out-degree and the destination vertex number of the out-edge are stored sequentially and continuously; the in-edge file is composed according to the destination vertex number, and the destination vertex number, The in-degree and the source vertex number of the in-edge. The order of edge values in the edge file corresponds to the order of edges in the edge file. Since the stored information in the two files is in the same order, the data in the edge value file can be easily located through the information in the edge file.

Considering that if you want to save two copies of edge value data, it is inevitable to synchronize and write back twice the data, so consider optimizing the data write back process. Since there is only the difference in the storage order between the two copies of the edge value, an improved edge value file structure is designed to save only one copy of the edge value data and the offset address of the edge value data in the file. FIG. 1 is a schematic diagram of the correspondence between a boundary value file and a boundary value offset address file provided by the present invention. As shown in Figure 1, the data file of the outgoing edge saves the original edge value data, and the order of the edge values corresponds to the order of the edges in the data file, which is compatible with the original data loading method of the system; the data file of the incoming edge constructs a A copy of the "boundary value" data in the same format, the content saved in the file is not the real boundary value, but a file offset address, pointing to the position of the real boundary value data in the file.

The index records the offset address of the edge corresponding to the vertex in the external memory file. The invention adopts the method of sparse index to establish indexes for the source vertex number and the target vertex number respectively, and uses the method of redundant storage to store each edge as an incoming edge and an outgoing edge respectively, and double the external memory storage overhead in exchange for it. Time performance improvement. details as follows:

When creating an index, an index file is created based on the vertex number of the edge file, and the index points to the offset address of the outgoing edge/incoming edge of the vertex in the file. Each line of the index file corresponds to a two-tuple: vertex number + the offset address of its corresponding out-edge information/in-edge information in the file. Divide the edge file into multiple blocks according to a given interval, and each index item points to the first piece of data of the corresponding block, including the vertex number and its file offset address. A lot of vertex data can be skipped in this way. At the same time, when loading data, although one data block is loaded at a time, some useless data will inevitably be read, but since the data block read each time may contain the data of multiple required vertices, the I/O can be reduced. times to improve efficiency.

FIG. 2 is a schematic diagram of an outgoing index file and an outgoing file provided by an embodiment of the present invention. As shown in Figure 2, each line in the out-edge file represents the out-edge information of a source vertex, which consists of: source vertex number + out-degree + destination vertex number. The given interval interval is 3. When creating an index, the outgoing edge file is divided into multiple blocks at an interval of 3, then vertices 1-3 are a block, vertices 4-6 are a block, and the established indexes point to the first vertex of the block, for example, the first A vertex V1 points to the first address 0 of the first block, and then vertex 4 points to the first address 32 of the second block (assuming that 4 bits are required to store each value).

The topology of the graph directly affects the organizational structure of the external memory data, thereby affecting the positioning of the external memory data. On the premise of not changing the topological structure of the graph, the present invention establishes an index for the external memory data and finds the positioning data, which reduces the complexity of implementation and also reduces the overhead of additional external memory access.

The calculation execution phase of the present invention includes steps S3-S4.

Step S3. Select the optimal loading mode from the loading mode of index positioning and the loading mode of accessing complete data. FIG. 3 is a flowchart of step S3 provided by an embodiment of the present invention. As shown in Figure 3, step S3 is as follows:

S30. Determine the active vertices of each subgraph, and determine whether the proportion of active vertices exceeds the threshold. If so, go to step S31. Otherwise, the loading mode for accessing complete data is the optimal loading mode, and step S3 ends.

The vertices that participate in the calculation update are called active vertices; the vertices that do not participate in the calculation are called inactive nodes.

The rounds with a low proportion of active vertices use the index-based loading method to improve performance, and the rounds with a high proportion of active vertices use the original method of accessing complete data for better performance. Combining the two data loading methods can achieve overall performance. The optimal solution, that is, the selection of the data loading method through the decision and judgment module can obtain the maximum performance improvement effect. The threshold value ranges from 20% to 30%, preferably 30%.

S31. Record the data block number corresponding to the active vertex data.

A data block usually contains data of multiple vertices, and the data blocks corresponding to all active vertex data are counted. Consider the distribution of active vertices in data blocks, that is, find out which data blocks have active vertices, and count the data blocks with active vertices.

S32. Based on the data block number corresponding to the active vertex data, calculate the cost Cost (Index) of the loading mode of index positioning and the cost Cost (All) of the loading mode of accessing complete data.

There are two ways to load data from external memory into memory, and the content of the data loaded in these two ways is not the same. When accessing the complete data, the complete subgraph data is loaded, which corresponds to the data file with the ordered vertices of the source, and the ordered data file of the target vertices is not loaded; when using index positioning to load valid data, it is Loads the outgoing edges of vertices from the source vertex ordered outgoing edge file, and loads the vertex incoming edges from the destination vertex ordered incoming edge file.

For the data loading method of accessing the complete subgraph, it is usually used when the amount of data required by the application is large. At this time, there is less invalid data that can be skipped, and the optimization benefit is relatively low. The high performance of sequential access using external memory can be used. Get higher access efficiency. Note that after the original image data is preprocessed, two copies of external memory data are obtained, and both data files contain complete sub-image information, so the system only needs to access one of the data files when loading data. When constructing a subgraph, process each edge in the data file in turn, and determine whether the source vertex and target vertex of the edge are the data required by the application. If the source vertex needs to participate in the calculation, add the current edge to the vertex's out-edge sequence; if the target vertex needs to participate in the calculation, add the current edge to the vertex's in-edge sequence.

The data loading method for accessing the complete subgraph is as follows:

(1) Sequentially load the ordered data files of the source vertices;

(2) Process each edge in the data file in turn, and determine whether the source vertex and target vertex of the edge are the data required by the application. If the source vertex needs to participate in the calculation, add the current edge to the out-edge sequence of the vertex; if The target vertex needs to participate in the calculation, adding the current edge to the incoming edge sequence of this vertex.

For the data loading method of index positioning, it is usually used when the amount of data required by the application is small. At this time, there is a lot of invalid data that can be skipped, and the optimization effect is obvious. Use index positioning to access the data required by the application to reduce I// O data volume to obtain higher access efficiency. Before accessing the external memory data, first obtain the vertex state information in the system, and record the data block number corresponding to the active vertex data. A data block usually contains the data of multiple vertices, and count the data corresponding to all active vertex data. Block, locate the corresponding file location according to the index to access the data block. Ideally, only the data corresponding to the active vertex needs to be loaded, but in actual reading, considering that each vertex needs to access the external memory once, it will lead to a lot of I/O times, which is inefficient, and the data corresponding to the access vertex is used. The block method can read the data of multiple vertices at a time. Although the data block will inevitably contain some useless data, it can greatly reduce the number of I/O and improve the efficiency of I/O. Note that the loaded data is obtained from two data files, the outgoing edges of the vertices are loaded from the source vertex-ordered file, and the incoming edges of the vertices are loaded from the target vertex-ordered file. Therefore, when constructing a subgraph, adding the outgoing edge to the outgoing edge sequence of the corresponding source vertex, and adding the incoming edge to the incoming edge sequence of the corresponding target vertex, reduces the amount of data that needs to be processed compared to the way of accessing the complete data.

The data loading method of index positioning is as follows:

(1) Find the data block that needs to be loaded into the memory in the outbound file according to the index positioning;

(2) According to the offset address of the outgoing edge of the data block that needs to be loaded in the outgoing edge file, find the outgoing edge value data in the edge value file, and load the edge value data into the memory;

(3) Constructing the out-edge topology of vertices in memory;

(4) When the application needs to enter the edge, locate the edge-in data block that needs to be loaded into the memory in the edge-in file according to the index;

(5) According to the input edge offset address of the data block that needs to be loaded in the input edge file, find the edge value offset address of the input edge in the edge value index file, and load the offset address of the edge value data to the memory;

(6) Construct the incoming edge topology of vertices in memory.

When data is loaded, the position of the data in the file can be quickly located according to the vertex number, thereby improving the efficiency of data search and access at runtime.

索引定位的载入方式的开销

其中，E为图中所有边的集合；D为单条边所占的存储空间；B为一次I/O的数据块大小；b为每个索引项指向的数据块大小；k为当前系统中所有活跃顶点对应的索引数据块的数量；r为随机访问开销。The overhead of the loading method to access the complete data

The cost of loading the index positioning

Among them, E is the set of all edges in the graph; D is the storage space occupied by a single edge; B is the size of the data block of one I/O; b is the size of the data block pointed to by each index entry; k is the size of the data block in the current system The number of index data blocks corresponding to active vertices; r is the random access cost.

The constants D, |E|B, b, and r are acquired and assigned before the calculation runs, where D*|E| is the space occupied by the data file.

S33. Determine whether Cost(All) is greater than Cost(Index). If so, the loading method for index positioning is the optimal loading method; otherwise, the loading method for accessing complete data is the optimal loading method.

By comparing the two data loading methods, it can be seen that the data loading method of index positioning is suitable for the case where the number of active vertices is small. At this time, the amount of data required for calculation is small. If the complete data is accessed, there will be a lot of Invalid data, and the amount of data that needs to be processed when building the subgraph is also huge, wasting CPU resources. The data loading method of accessing the complete subgraph can make full use of the sequential access performance of the external memory disk, and when the proportion of active vertices is large, loading all the data at one time can obtain better performance. The comprehensive use of these two data loading methods enables the system to always obtain optimal performance when loading data, which greatly improves the overall efficiency of the system.

Step S4. Load each sub-picture in the external memory into the internal memory in an optimal loading manner.

The above are only the preferred embodiments of the present application, but the protection scope of the present application is not limited to this. Any person skilled in the art can easily think of changes or replacements within the technical scope disclosed in the present application, All should be covered within the scope of protection of this application. Therefore, the protection scope of the present application should be subject to the protection scope of the claims.

Claims (7)

1. An external memory access method for a graph computing system based on index positioning, the method comprising the steps of:

s0. dividing the complete graph data into multiple sub-graphs that the memory can hold;

s1, sequencing edges of each subgraph according to a source vertex number and a target vertex number;

s2, writing the sequenced subgraphs into an external storage file, and respectively establishing indexes for a source vertex number and a target vertex number;

s3, selecting an optimal loading mode from the loading modes of index positioning and the data loading modes of accessing the complete subgraph, wherein the step S3 is as follows:

s30, determining active vertexes of all sub-graphs, judging whether the proportion of the active vertexes exceeds a threshold value, if so, entering a step S31, otherwise, accessing the data loading mode of the complete sub-graph to be an optimal loading mode, and ending the step S3;

s31, recording a data block number corresponding to the active vertex data;

s32, calculating the overhead cost (index) of a loading mode for index positioning and the overhead cost (all) of a data loading mode for accessing a complete subgraph based on the number of a data block corresponding to the active vertex data;

s33, judging whether cost (all) is greater than cost (index), if so, determining the loading mode of index positioning as the optimal loading mode, otherwise, determining the data loading mode of accessing the complete subgraph as the optimal loading mode;

the loading mode of the index positioning is as follows: (1) finding out data blocks needing to be loaded into the memory in the edge file according to the index positioning; (2) according to the offset address of the data block output edge which needs to be loaded in the output edge file, finding out the edge value data of the output edge in the edge value file, and loading the edge value data into the memory; (3) constructing an edge-out topological structure of a vertex in a memory; (4) when the application needs to enter the edge, locating an edge entering data block which needs to be loaded into the memory in the edge entering file according to the index; (5) according to the edge entering offset address of the data block to be loaded in the edge entering file, finding the edge value offset address of the edge entering in the edge value index file, and loading the edge value data offset address to the memory; (6) constructing an edge-entering topological structure of a vertex in a memory;

the data loading mode for accessing the complete subgraph is as follows: (1) sequentially loading data files with ordered source vertexes; (2) sequentially processing each edge in the data file, respectively judging whether a source vertex and a target vertex of the edge are data required by application, and adding a current edge into an edge outlet sequence of the vertex if the source vertex needs to participate in calculation; if the target vertex needs to participate in calculation, adding the current edge into the edge entering sequence of the vertex;

and S4, loading each sub-graph in the external memory into the internal memory in an optimal loading mode.

2. The method according to claim 1, wherein the writing of the sorted subgraphs into the external memory file is as follows:

when each sub-graph after edge sequencing is written into an external memory file, edges with the same source vertex and target vertex are stored in continuous external memory data blocks; the data of the edge comprises an edge and an edge value, and the edge are respectively stored as two files in an external memory: an edge file and an edge value file; the edge file stores the topological structure of the graph, the storage format is the adjacency list format; the order of the edge values in the edge file corresponds to the order of the edges in the edge file.

3. The external memory access method of claim 2, wherein the edge file comprises: an edge-out file according to the source vertex number and an edge-in file according to the target vertex number; the edge-out file is organized according to the source vertex number, and the source vertex number, the out-degree and the target vertex number of the edge-out are sequentially and continuously stored; the edge entering file is composed according to the target vertex number, and the target vertex number, the degree of entry and the source vertex number of the edge entering are sequentially and continuously stored.

4. The method as claimed in claim 2, wherein, when creating the index, the edge-value index file is created by using the vertex number of the edge file, and each row of the edge-value index file corresponds to one tuple: the vertex number of the edge file and the offset address of the corresponding outgoing edge or incoming edge in the external file.

5. The method according to claim 1, wherein the threshold value ranges from 20% to 30%.

6. The method of claim 1, wherein the overhead of accessing the data load of a complete subgraph

Overhead of index-oriented load-wise

Wherein E is the set of all edges in the graph; d is a storage space occupied by a single edge; b is the data block size of primary I/O; b is the size of the data block pointed to by each index entry; k is the number of index data blocks corresponding to all active vertexes in the current system; r is the random access overhead.

7. A computer-readable storage medium, having stored thereon a computer program which, when executed by a processor, implements a method of external memory access according to any one of claims 1 to 6.

Images