CN107957962A - It is a kind of to calculate efficient figure division methods and system towards big figure - Google Patents

Abstract

The present invention proposes a high-efficiency graph partitioning method and system for large graph computing. The method divides the graph data into multiple vertices, and converts the random sorting of the vertices into a queue; the first vertex is partitioned and allocated according to the sequence of the queue, that is, Assigned to the processing unit, after the allocation, the partition information of the vertex is used as the value, and the neighbors of the vertex are used as the key, and stored in DRAM or NVM in the form of dictionary entries; for subsequent vertices, first determine whether there is such a vertex in DRAM or NVM If the entry whose vertex is the key exists, the partition information of this vertex is directly appended to the corresponding entry in DRAM or NVM; if it does not exist, the point is allocated to the processing unit with the least load. The partition information of each allocated vertex is used as the value, and the neighbors of this vertex are used as keys, and stored in the corresponding cache in the form of dictionary entries. This method can directly search for the corresponding entry with the point as the key according to the current fixed point each time, and the efficiency is improved.

Description

A high-efficiency graph partitioning method and system for large graph computing

technical field

The invention relates to the field of computers, in particular to a method and system for large-scale computing and high-efficiency graph division.

Background technique

At present, the scale of graphs is huge and growing. For example, a graph composed of brain nerves can reach hundreds of terabytes. The most typical is the World Wide Web. Search engines can capture about 1 trillion link graphs. According to It is estimated that the future scale will exceed ten trillion. The world's largest social network Facebook currently has about 1 billion users, corresponding to tens of billions of relationship links. Ordinary computers cannot process these graphs (large graphs) normally due to memory limitations, which poses severe challenges to common graph calculations (such as finding connected components, calculating triangles and Pagerank). A standard solution is to divide graph data into multiple subgraphs and load them into different processing units for distributed computing. To this end, distributed system frameworks such as Spark, Pregel, Giraph, and Trinity have been successively developed. These systems mainly use pseudo-random hash functions to distribute tasks to each processing unit according to the node ID. Although load balancing can be achieved, due to The high amount of communication between partitions results in slower computational runtimes than algorithms with good partition quality. Fortunately, these systems support custom partitioning methods, and users can replace the existing hash algorithm with a more complex partitioning method.

Graph partition management is the premise of distributed computing, which is directly related to the communication volume or running time between sub-regions in the graph computing process. Due to the need for repeated iterative calculations and frequent access to vertices and edges, offline partitioning will lead to high time complexity and memory capacity requirements, making it difficult to apply to large-scale graph partitioning. Since then, it has been continuously developed. The latest Fennel algorithm is close to or even surpasses the Metis division in terms of division quality, and the stream algorithm can also effectively process dynamic large-scale data.

In the existing streaming method, for a new vertex loaded into the memory, the required neighbor partition information has been stored in the memory, and each time the neighbor is searched first, and then the corresponding partition is searched according to the neighbor. The complexity of the search is directly related to the number of neighbor points, and the search efficiency is low. In reality, the scale of many large graphs exceeds the memory capacity of ordinary computers, and some graphs even reach the terabyte level. Therefore, it is not feasible to store all point and point partition information in the cache. If some intermediate data is stored on the hard disk, performance will inevitably be reduced.

The emergence of a new type of non-volatile memory (Non-Volatile Memory, NVM) is beneficial to alleviate the problems in the traditional storage architecture. NVM is a brand-new storage medium, which has the advantages of byte addressability, non-volatility, low static power consumption, and high density. on flash and disk. NVM is a general term for non-volatile storage media with these characteristics. NVM can often be used as main memory or external memory to alleviate the problems of traditional storage architectures. On the one hand, because NVM is byte-addressable, it can be directly mounted on the memory bus for access, and the processor can access and store data on the NVM through load/store instructions instead of time-consuming I/O O operation to access and store data. At the same time, NVM is similar to DRAM in terms of access delay and read and write performance, and its static power consumption is lower than that of DRAM. The graph division is a read and write intensive calculation. Due to the poor write performance of NVM, high write power consumption and limited number of write operations, If NVM is directly used as memory, the service life of NVM will be directly affected due to high-frequency write operations.

Contents of the invention

In order to overcome the above-mentioned defects in the prior art, the object of the present invention is to provide a method and system for large-scale computing and efficient graph partitioning.

In order to achieve the above-mentioned purpose of the present invention, the present invention provides a kind of high-efficiency graph division method for large graph calculation, comprising the following steps:

S1, divide the graph data into multiple vertices, and randomly sort the vertices into a queue;

S2, partition the first vertex according to the order of the queue, that is, after the allocation to the processing unit, the partition information of the vertex is used as the value, and the neighbors of the vertex are used as keys, which are stored in the DRAM in the form of dictionary entries. If The data capacity of DRAM exceeds the set threshold and is stored in NVM;

S3, for the subsequent vertex in the queue, first judge whether there is an entry with this vertex as the key in DRAM or NVM, if it exists, directly append the partition information of this vertex to the corresponding entry in DRAM or NVM, that is, according to the entry in the entry Value, assign the point to the corresponding processing unit, each time a vertex is assigned, the partition information of the assigned vertex is used as the value, and the neighbors of this vertex are used as keys, which are stored in the corresponding cache in the form of dictionary entries;

If there is no entry with this vertex as the key in DRAM or NVM, then assign this point to the processing unit with the least load, and then use the partition information of each allocated vertex as the value, and the neighbors of this vertex as the key, and use The form of the dictionary entry is stored in the DRAM, and if the data capacity of the DRAM exceeds the set threshold, it is stored in the NVM until all points in the queue are allocated, wherein the processing unit with the least load is the partition with the least number of vertices.

This method can directly search for the corresponding entry with the point as the key according to the current fixed point each time, and the cache efficiency is high.

Further, when assigning partitions, the vertex to be assigned is assigned to the partition containing the largest number of neighbors of the vertex.

Further, the following formula is used for partitioning: Among them, S _ind is the partition assigned to vertex v, N(v) represents the neighbor point of vertex v, S _i ^t represents the state of the vertex partition that has been divided at time t, n is the number of vertices in the graph, k is the number of partitions, f ₁ refers to the number of neighbor points containing vertex v in each partition at time t, f ₂ is the penalty function, and n/k is the average load.

Further, during the division of graph data, when each entry is generated or updated, the timestamp of the entry is updated synchronously;

When the data capacity in DRAM exceeds the set threshold, the entry data with the earliest time is migrated to NVM according to the time stamp of the entry in the cache;

When the cache data in the DRAM is reduced to a set threshold and the data in the NVM is not empty, the entry in the cache with the last timestamp in the NVM is migrated to the DRAM.

This solution reduces the number of writes to the NVM and improves the life of the NVM.

Further, when allocating subsequent vertices in the queue, if there is an entry with this vertex as the key in DRAM or NVM, after assigning the point to the corresponding processing unit according to the value in the entry, remove this entry from the cache Delete, which improves the utilization of memory space.

The present invention also proposes a high-efficiency graph division system for large graph computing, including a CPU, DRAM, NVM, and a processing unit. The processing unit is a computing unit in a cluster, and the CPU communicates with the DRAM, NVM, and processing unit. The DRAM is connected to the NVM in communication, and the CPU, the DRAM, the NVM, and the processing unit cache the large image according to the large-image calculation and efficient image division method described in any one of claims 1-3.

Beneficial effects of the present invention:

1. This application does not need to consider whether the memory capacity meets the requirements. Compared with disk or solid-state hard disk, the division efficiency has been improved, and the processing speed is close to that of memory;

2. By adopting the present invention, the corresponding entry with this point as the key can be searched directly according to the current fixed point, and the efficiency is obviously improved;

3. The number of writes to NVM has been significantly reduced, increasing the average life of NVM.

Additional aspects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention.

Description of drawings

The above and/or additional aspects and advantages of the present invention will become apparent and comprehensible from the description of the embodiments in conjunction with the following drawings, wherein:

Fig. 1 is a hybrid storage architecture diagram of the present invention;

Figure 2 is an example diagram of graph division;

Figure 3 is a schematic diagram of a vertex queue of a large graph;

Fig. 4-Fig. 6 are the comparison diagrams of the content capacity occupied by the present invention and the processing process of the other two caching methods;

Figure 7-9 is a comparison of write times for different replacement strategies.

Detailed ways

Embodiments of the present invention are described in detail below, examples of which are shown in the drawings, wherein the same or similar reference numerals designate the same or similar elements or elements having the same or similar functions throughout. The embodiments described below by referring to the figures are exemplary only for explaining the present invention and should not be construed as limiting the present invention.

In the description of the present invention, unless otherwise specified and limited, it should be noted that the terms "installation", "connection" and "connection" should be understood in a broad sense, for example, it can be mechanical connection or electrical connection, or two The internal communication of each element may be directly connected or indirectly connected through an intermediary. Those skilled in the art can understand the specific meanings of the above terms according to specific situations.

A hybrid storage structure as shown in Figure 1, DRAM is used as a first-level cache, and NVM is used as a second-level disk of a disk. Based on this structure, the present invention provides a method for partitioning large-scale computing and efficient graphs, including the following steps:

S1, the graph data is divided into multiple vertices, and the vertices are randomly sorted into queues.

S2, according to the order of the queue, the first vertex is partitioned and allocated, that is, allocated to the processing unit, where the processing unit is the computing unit in the cluster. After allocation, the partition information of the vertex is used as the value, and the neighbors of the vertex are used as keys, which are stored in DRAM in the form of dictionary entries. If the data capacity of DRAM exceeds the set threshold, it is stored in NVM or in NVM.

S3, for the subsequent vertex in the queue, first judge whether there is an entry with this vertex as the key in DRAM or NVM, if it exists, directly append the partition information of this vertex to the corresponding entry in DRAM or NVM, that is, according to the entry in the entry Value, assign the point to the corresponding processing unit. Every time a vertex is allocated, the partition information of the allocated vertex is used as the value, and the neighbors of this vertex are used as keys, which are stored in the corresponding cache in the form of dictionary entries.

When allocating subsequent vertices in the queue, if there is an entry with this vertex as the key in DRAM or NVM, the entry is deleted from the cache after the point is assigned to the corresponding processing unit according to the value in the entry.

If it does not exist, allocate the point to the processing unit with the least load, and then use the partition information of each allocated vertex as the value, and the neighbors of this vertex as keys, and store them in DRAM in the form of dictionary entries. If DRAM If the data capacity exceeds the set threshold, it will be stored in the NVM until all points in the queue are allocated, wherein the processing unit with the least load is the partition with the least number of vertices.

When assigning partitions, the vertex to be assigned is assigned to the partition containing the largest number of neighbors of the vertex.

Specifically, the following formula can be used for partitioning:

Among them, N(v) represents the neighbor point of vertex v, Indicates the vertex partition status that has been divided at time t, n is the number of vertices in the graph, and k is the number of partitions. It can be seen from the above equation that each vertex is only checked once. The function f ₁ in the first half of the equation means the number of neighbors of vertex v in each partition at time t. In order to balance the partition load, multiply the penalty after the equation function f ₂ . Select the sub-area with the largest function value, assign the vertex v to this sub-area, and n/k is the average load.

As shown in Table 1, the leftmost column in the table is a data set. The hybrid storage structure of the present invention is compared with other storage structures in terms of division time. In non-volatile storage devices, magnetic disks, and solid-state hard disks, DRAMs are respectively set The cache capacity in is respectively 5%, 9%, 13% and 17% of the corresponding figure. The cache content storage structure is the storage structure introduced in the present invention. It can be seen that the hybrid storage structure of the present invention is much shorter in time than other storage structures.

The DRAM storage capacity is set to be unlimited, compared with the original division time, the superiority of the cache content structure introduced in the present invention can be seen directly from the table data.

Table 1 Comparison of division time under different media

The following figure illustrates the division process. The left figure in Figure 2 is divided into three sub-areas using the above algorithm. Among them, the left figure in Figure 2 is the basic expression of the figure, which is stored in the computer disk in the form of a file and loaded into the memory. That is, the calculation process is shown in Figure 3 and Table 2. First, the large graph data is divided into multiple vertices, and the random ordering of the vertices is converted into a queue, as shown in Figure 3; Table 2 is from time T to time T+ 6. During the division of the large graph G, dynamically cache the data content (adjacent edge structure), and process the vertex (v ₁ ) with the ID number 1 at time T. After the allocation is completed, use the partition information of this point as the value, and the neighbor Stored in the cache as the key (v ₂ →S ₁ , v ₃ →S ₁ ). At time T+1, calculate vertex v ₃ , since the neighbor partition of point v ₃ has been saved in the cache (v ₃ → S ₁ ), so the partition to which this point belongs is directly calculated according to this entry, and point v ₃ After the allocation is completed, the entry (v ₃ →S ₁ ) at this point has become redundant data, so it is directly deleted. Until all vertices are allocated, the algorithm ends.

A point can only be assigned to one partition, and a key in the cache can correspond to multiple values. This algorithm is calculated based on the number of allocated neighbor points. For example, (v2→S1) does not mean assigning point v2 to s1. Just know Only one neighbor of v2 is in s1. Among them (V4:S2, S3) indicates that there is one adjacent point of point v4 in the sub-region s2 and one in the sub-region s3. Knowing this information, it can be substituted into the above formula for calculation. In the computer field, the value can be understood as the data that needs to be stored, and the key is the number of the value that needs to be stored.

Table 2 Contents of dynamic cache data in the process of partitioning graph G from time T to time T+6

The three cache content storage structures shown in Figure 4-6 follow the process of division, and the capacity of the cache data accounts for the percentage of the corresponding graph scale. Among them, OCS means adopting the cache content storage structure of the present invention, OCSnodel means adopting the cache content storage structure of the present invention without introducing deletion operation, NPS means the storage structure of the original algorithm, and the partition information of points and corresponding points is used as the basic entry. It can be seen from the figure that with the process of point processing, the scale of using the NPS structure and the OCSnodel structure is constantly increasing, and the OCSnodel structure finally reaches 100% of the original scale. Adopting the storage structure OCS of the present invention follows the process of vertex processing, but the capacity is constantly decreasing after reaching the peak value. The maximum storage capacity required by NPS is smaller than that of OCS and OCSnodel, but the required maximum capacity also accounts for nearly 30%. For As far as the big picture of TB is concerned, it is obvious that ordinary stand-alone machines are powerless at present.

In order to reduce the number of writes to NVM, the circular least recent data migration strategy is used. During the division of graph data, when each entry is generated or updated, the timestamp of the entry is updated synchronously;

When the data capacity in DRAM exceeds the set threshold, the entry data with the earliest time is migrated to NVM according to the time stamp of the entry in the cache;

When the cache data in the DRAM is reduced to a set threshold and the data in the NVM is not empty, the entry in the cache with the last timestamp in the NVM is migrated to the DRAM.

As shown in Figure 7-9, set the DRAM cache capacity as a percentage (5%, 10%, 15%) corresponding to the figure. When the cache data in DRAM exceeds the specified size, the data will be written into NVM. In order to verify the superiority of this strategy, other strategies are also tested to compare the results.

Random is a random strategy. When the memory cache data is full, the data in it is randomly selected and written to NVM. LFU is the least frequently used strategy. A count variable is added to the entry, and the number of updated entries is used as the basic unit to migrate the entry with the least number of times to NVM. LRU is the least-recently-used policy, adding timestamps to entries, and migrating the oldest entries to NVM. LRU _loop is the least-recently-used strategy. The strategy of migrating cached data in DRAM to NVM is the same as LRU. The difference is that, as shown in Figure 3, when processing to about 0.05%-0.2% of the vertex queue , the required cache capacity is constantly decreasing, and there will be redundant space in the DRAM. The present invention uses this space to introduce a write-back strategy. When the remaining space increases to a certain scale, the entries in the NVM are selected according to the timestamp. Entry data is migrated to DRAM, again reducing write cycles. The results in Figure 3 reflect the superiority of this strategy, and the number of writes is significantly less than other strategies.

The present invention also proposes a high-efficiency graph division system for large graph computing, including a CPU, DRAM, NVM, and a processing unit. The processing unit is a computing unit in a cluster, and the CPU communicates with the DRAM, NVM, and processing unit. The DRAM is connected to the NVM in communication, and the CPU, DRAM, NVM, and processing unit cache the large image according to the above-mentioned high-efficiency graph division method for large-scale computing.

In the description of this specification, descriptions referring to the terms "one embodiment", "some embodiments", "example", "specific examples", or "some examples" mean that specific features described in connection with the embodiment or example , structure, material or characteristic is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms do not necessarily refer to the same embodiment or example. Furthermore, the specific features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.

Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications, substitutions and modifications can be made to these embodiments without departing from the principle and spirit of the present invention. The scope of the invention is defined by the claims and their equivalents.

Claims (6)

1. a kind of calculate efficient figure division methods towards big figure, it is characterised in that comprises the following steps：

S1, multiple vertex are divided into by diagram data, and switch to queue by vertex is randomly ordered；

S2, carries out subregion distribution to first vertex according to queue sequence, that is, processing unit is assigned to, with the vertex after distributing Partition information as value, the adjoint point on this vertex is stored in DRAM, if the number of DRAM as key in the form of dictionary entry Then it is stored according to capacity more than given threshold in NVM；

S3, for follow-up vertex in queue, first judges the entry for whether having using this vertex as key in DRAM or NVM, if it does, The partition information on this vertex is directly appended to corresponding entry in DRAM or NVM, i.e., according to the value in the entry, by the point Corresponding processing unit is assigned to, often distributes a vertex, the partition information to be assigned vertex is used as value, this vertex Adjoint point as key, be stored in the form of dictionary entry in corresponding caching；

If the point is assigned to the minimum processing unit of load there is no the entry using this vertex as key in DRAM or NVM, Stored again using the partition information on each vertex distributed as value, the adjoint point on this vertex as key in the form of dictionary entry In DRAM, it is stored in if the data capacity of DRAM exceedes given threshold in NVM, until all the points all distribute in queue Finish, wherein, the minimum processing unit of the load is the subregion for possessing vertex minimum number.

2. according to claim 1 calculate efficient figure division methods towards big figure, it is characterised in that, will when subregion distributes Vertex to be allocated is distributed to the most subregion of the adjoint point quantity containing the vertex.

3. according to claim 1 calculate efficient figure division methods towards big figure, it is characterised in that using the following formula into Row subregion：Wherein, S_indThe subregion being assigned to for vertex v, N (v) Neighbours' point of vertex v is represented,Represent the vertex subregion state divided in t moment, n is the number of vertex of figure, and k is subregion Number, f₁Refer in t moment, neighbours' point quantity containing vertex v, f in each subregion₂For penalty, n/k is average load.

4. according to claim 1 calculate efficient figure division methods towards big figure, it is characterised in that in the division of diagram data During, when the generation or renewal of each entry, the timestamp of the synchronized update entry；

It is before and after entry time stamp in caching, the time is most forward when the data capacity in DRAM exceedes given threshold Entry data move in NVM；

When the data cached data being reduced in given threshold and NVM in DRAM are not empty, by timestamp in NVM most rearward Caching in entry move in DRAM.

5. according to claim 1 calculate efficient figure division methods towards big figure, it is characterised in that follow-up in queue When vertex is allocated, if existed in DRAM or NVM using entry of this vertex as key, the value according to entry will be put minute After being fitted on corresponding processing unit, this entry is removed from the cache.

6. a kind of calculate efficient figure dividing system towards big figure, it is characterised in that including CPU, DRAM, NVM and processing unit, The processing unit is the computing unit in cluster, and the CPU and DRAM, NVM, processing unit communicate to connect, the DRAM with NVM is communicated to connect, and described CPU, DRAM, NVM and processing unit are calculated high by claim 1-5 any one of them towards big figure Effect figure division methods cache big figure.