CN110647663B - Graph node attribute memory implementation method and device for shortest path problem - Google Patents
Graph node attribute memory implementation method and device for shortest path problem Download PDFInfo
- Publication number
- CN110647663B CN110647663B CN201910849008.8A CN201910849008A CN110647663B CN 110647663 B CN110647663 B CN 110647663B CN 201910849008 A CN201910849008 A CN 201910849008A CN 110647663 B CN110647663 B CN 110647663B
- Authority
- CN
- China
- Prior art keywords
- node attribute
- graph node
- graph
- memory cell
- memory
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a graph node attribute memory implementation method and device for the problem of the shortest path, wherein the graph node attribute memory comprises a plurality of graph node attribute memory units; each memory unit comprises a graph node attribute initialization mechanism, a node attribute write success mechanism and a read success mechanism; initializing graph node attributes, initializing a source node attribute value to be 0, and initializing a non-source node attribute value to be infinite (initializing all binary bits of a storage data area to be all 1); the node attribute is successfully written, if and only if the attribute value of the node to be written is less than or equal to the node attribute value in the memory, the node can be successfully written, otherwise, the writing operation is ignored; and (4) reading the attribute of the graph node, and immediately returning the node attribute data for the read operation of the node attribute storage unit. The invention realizes a graph node attribute memory realization method for the shortest path problem, and reduces the influence of random read operation on performance.
Description
Technical Field
The invention relates to a storage technology of graph calculation problems, in particular to a method and a device for realizing a graph node attribute storage facing to a shortest path problem.
Background
The graph calculation problem is a typical access intensive problem and has the characteristics of unbalanced load, irregular access, low calculation access ratio and poor locality. A typical graph computation problem involves setting an attribute for each graph node, and the goal of the problem solution is to compute the attribute value for each node. For example, for the single-source shortest path problem, i.e., given an origin node S, the shortest distance from the origin node S to all graph nodes is calculated, where the attribute value is the distance from the node to the origin node; for the width-first search problem, a root node R is given, a width-first search tree with the node R as the root is obtained through calculation, and the attribute value is the number of layers of each node or the father node of each node. Typical graph computation algorithms define an array of attributes based on the number of graph nodes, placed in processor chips or memory based on size. After the attribute array is initialized, the array is updated through algorithm iteration. The updating process involves repeatedly reading and writing the attribute array, and the access to the attribute array usually has large randomness and irregularity, thereby causing poor graph calculation performance.
In order to improve the performance of graph computation, storage optimization is an important approach. A typical storage optimization method includes: customizing an optimized graph data storage structure, designing a multi-channel parallel memory access and improving memory access bandwidth and the like. The graph data storage structure generally adopts a CSR (compressed spare row) mode to store graph data, so that the data locality is enhanced; the access bandwidth is improved by the multi-channel parallel access. Besides, reducing the random access times is also an important way for improving the performance. In order to reduce the influence of random read access of the attribute array on the graph computation performance, an optimized graph node attribute memory is needed.
Disclosure of Invention
The technical problems to be solved by the invention are as follows: the invention can avoid the display read operation of the destination node attribute when updating the destination node attribute, reduces the influence of the random read operation on the performance, and has the advantages of simple logic realization and flexible and convenient use.
In order to solve the technical problems, the invention adopts the technical scheme that:
a graph node attribute memory implementation method facing the shortest path problem comprises the following implementation steps:
1) obtaining an access operation aiming at a graph node attribute memory, wherein the graph node attribute memory comprises a plurality of graph node attribute memory cells, skipping to execute the step 2) when the access operation is a graph node attribute initialization operation, skipping to execute the step 3) when the access operation is a graph node attribute write operation, and skipping to execute the step 4) when the access operation is a graph node attribute read operation;
2) executing graph node attribute initialization operation aiming at the designated graph node attribute memory cell, initializing the source node attribute value to 0, initializing the non-source node attribute value to a maximum value, ending and exiting;
3) executing graph node attribute write operation aiming at the designated graph node attribute memory cell, if and only if the attribute value of the node to be written is less than or equal to the node attribute value in the memory, the write operation is successful, otherwise, the write operation is ignored, and the operation is finished and quitted;
4) and executing graph node attribute reading operation aiming at the specified graph node attribute memory cell, immediately returning node attribute data for the reading operation of the node attribute memory cell, ending and exiting.
Optionally, the maximum in step 2) specifically means that all bins in the data storage area are initialized to all 1 s.
Optionally, the detailed steps of step 2) include:
2.1) the designated graph node attribute memory cell receives the initialization signal and acquires a source node index;
2.2) comparing the source node index with the memory cell address of the node attribute memory cell of the graph;
2.3) if the source node index and the memory unit address are equal, initializing the binary bit of the memory unit data to be all 0; otherwise, initializing the binary bit of the data of the memory unit to be all 1; and ending and exiting.
Optionally, the detailed steps of step 3) include:
3.1) the designated graph node attribute memory cell receives the node attribute write signal and acquires a node attribute value D to be written;
and 3.2) comparing the node attribute value D to be written with the node attribute value E in the node attribute memory cell of the graph, if the node attribute value D and the node attribute value E meet the condition that D < > is equal to E, updating the data in the node attribute memory cell of the graph into the node attribute value D to be written, and otherwise, keeping the data in the node attribute memory cell of the graph unchanged.
Optionally, the detailed steps of step 4) include:
4.1) the designated graph node attribute memory cell receives the node attribute reading signal to obtain a reading node index;
4.2) comparing the read node index with the memory cell address of the node attribute memory cell of the graph;
4.3) if the reading node index is equal to the memory cell address of the node attribute memory cell of the graph, returning the data in the memory cell, otherwise, returning all 0 s.
In addition, the invention also provides a device for realizing the graph node attribute storage facing the shortest path problem, which comprises a graph node attribute storage and an access control unit, wherein the graph node attribute storage comprises a plurality of graph node attribute storage units cells, and the access control unit is programmed or configured to execute the steps of the method for realizing the graph node attribute storage facing the shortest path problem. In addition, the invention also provides a device for implementing the graph node attribute storage facing the shortest path problem, which comprises a graph node attribute storage, an access control unit and a storage device, wherein the graph node attribute storage comprises a plurality of graph node attribute storage units cells, and the storage device is stored with a computer program which is programmed or configured to execute the method for implementing the graph node attribute storage facing the shortest path problem.
Compared with the prior art, the invention has the following beneficial effects:
1. the invention realizes the graph node attribute memory facing the shortest path problem by customization, can directly realize the update of the destination node attribute without displaying and reading the destination node attribute value, and reduces the random reading times.
2. The invention adds part of processing logic on the graph node attribute memory cell of the graph node attribute memory, and has the advantage of simple hardware logic realization.
3. The invention can be applied to the design of the graph calculation memory in the shortest path graph calculation processing, and meanwhile, the design concept can also provide reference for the design of a general graph attribute memory.
Drawings
FIG. 1 is a schematic diagram of a basic flow of a method according to an embodiment of the present invention.
FIG. 2 is a block diagram illustrating the principles of a graph node memory cell in an embodiment of the present invention.
FIG. 3 is a diagram illustrating the initialization of a graph node memory unit according to an embodiment of the present invention.
FIG. 4 is a diagram illustrating a graph node memory unit write attribute data according to an embodiment of the present invention.
FIG. 5 is a diagram illustrating a graph node memory unit write attribute data according to an embodiment of the present invention.
Detailed Description
As shown in fig. 1, the implementation steps of the graph node attribute storage implementation method for the shortest path problem in this embodiment include:
1) obtaining an access operation aiming at a graph node attribute memory, wherein the graph node attribute memory comprises a plurality of graph node attribute memory cells, skipping to execute the step 2) when the access operation is a graph node attribute initialization operation, skipping to execute the step 3) when the access operation is a graph node attribute write operation, and skipping to execute the step 4) when the access operation is a graph node attribute read operation;
2) executing graph node attribute initialization operation aiming at the designated graph node attribute memory cell, initializing the source node attribute value to 0, initializing the non-source node attribute value to a maximum value, ending and exiting;
3) executing graph node attribute write operation aiming at the designated graph node attribute memory cell, if and only if the attribute value of the node to be written is less than or equal to the node attribute value in the memory, the write operation is successful, otherwise, the write operation is ignored, and the operation is finished and quitted;
4) and executing graph node attribute reading operation aiming at the specified graph node attribute memory cell, immediately returning node attribute data for the reading operation of the node attribute memory cell, ending and exiting.
Referring to fig. 2, in the graph node attribute storage implementation method for the shortest path problem according to the present embodiment, initialization (step 2), a write success mechanism (step 3), and a read success mechanism (step 4) are implemented around node attribute storage unit data. In the embodiment, the graph node attribute storage facing the shortest path problem is realized by customization, the target node attribute can be directly updated without displaying and reading the target node attribute value, and the random reading times are reduced. In this embodiment, a part of processing logic is added to the cell of the graph node attribute memory unit of the graph node attribute memory, and the method has the advantage of simple hardware logic implementation. The embodiment can be applied to the design of the graph calculation memory in the shortest path graph calculation processing, and meanwhile, the design concept can also provide reference for the design of a general graph attribute memory.
In this embodiment, the maximum value in step 2) specifically means that all the bins in the data storage area are initialized to all 1 s.
As shown in fig. 3, the detailed steps of step 2) include:
2.1) the designated graph node attribute memory cell receives the initialization signal and acquires a source node index;
2.2) comparing the source node index with the memory cell address of the node attribute memory cell of the graph;
2.3) if the source node index and the memory unit address are equal, initializing the binary bit of the memory unit data to be all 0; otherwise, initializing the binary bit of the data of the memory unit to be all 1; and ending and exiting.
As shown in fig. 4, the detailed steps of step 3) include:
3.1) the designated graph node attribute memory cell receives the node attribute write signal and acquires a node attribute value D to be written;
and 3.2) comparing the node attribute value D to be written with the node attribute value E in the node attribute memory cell of the graph, if the node attribute value D and the node attribute value E meet the condition that D < > is equal to E, updating the data in the node attribute memory cell of the graph into the node attribute value D to be written, and otherwise, keeping the data in the node attribute memory cell of the graph unchanged.
As shown in fig. 5, the detailed steps of step 4) include:
4.1) the designated graph node attribute memory cell receives the node attribute reading signal to obtain a reading node index;
4.2) comparing the read node index with the memory cell address of the node attribute memory cell of the graph;
4.3) if the reading node index is equal to the memory cell address of the node attribute memory cell of the graph, returning the data in the memory cell, otherwise, returning all 0 s.
In addition, the present embodiment further provides an apparatus for implementing a graph node attribute storage facing a shortest path problem, including a graph node attribute storage and an access control unit (omitted from the drawing), where the graph node attribute storage includes a plurality of graph node attribute storage cells, and the access control unit is programmed or configured to execute the steps of the method for implementing the graph node attribute storage facing the shortest path problem according to the present embodiment. In addition, the present embodiment further provides an apparatus for implementing a graph node attribute storage for a shortest path problem, including a graph node attribute storage, an access control unit (omitted from the figure), and a storage device (omitted from the figure), where the graph node attribute storage includes a plurality of graph node attribute storage cells, and the storage device stores thereon a computer program that is programmed or configured to execute the method for implementing the graph node attribute storage for a shortest path problem according to the present embodiment.
The above description is only a preferred embodiment of the present invention, and the protection scope of the present invention is not limited to the above embodiments, and all technical solutions belonging to the idea of the present invention belong to the protection scope of the present invention. It should be noted that modifications and embellishments within the scope of the invention may occur to those skilled in the art without departing from the principle of the invention, and are considered to be within the scope of the invention.
Claims (4)
1. A graph node attribute memory implementation method facing the shortest path problem is characterized in that the implementation steps comprise:
1) obtaining an access operation aiming at a graph node attribute memory, wherein the graph node attribute memory comprises a plurality of graph node attribute memory cells, skipping to execute the step 2) when the access operation is a graph node attribute initialization operation, skipping to execute the step 3) when the access operation is a graph node attribute write operation, and skipping to execute the step 4) when the access operation is a graph node attribute read operation;
2) executing graph node attribute initialization operation aiming at the designated graph node attribute memory cell, initializing the source node attribute value to 0, initializing the non-source node attribute value to a maximum value, ending and exiting;
3) executing graph node attribute write operation aiming at the designated graph node attribute memory cell, if and only if the attribute value of the node to be written is less than or equal to the node attribute value in the memory, the write operation is successful, otherwise, the write operation is ignored, and the operation is finished and quitted;
4) executing graph node attribute reading operation aiming at the appointed graph node attribute memory cell, immediately returning node attribute data to the reading operation of the node attribute memory cell, ending and exiting;
the detailed steps of the step 2) comprise:
2.1) the designated graph node attribute memory cell receives the initialization signal and acquires a source node index;
2.2) comparing the source node index with the memory cell address of the graph node attribute memory cell;
2.3) if the source node index and the memory unit address are equal, initializing the binary bit of the memory unit data to be all 0; otherwise, initializing the binary bit of the data of the memory unit to be all 1; ending and exiting;
the detailed steps of the step 3) comprise:
3.1) the designated graph node attribute memory cell receives the node attribute write signal and acquires a node attribute value D to be written;
3.2) comparing the node attribute value D to be written with the node attribute value E in the graph node attribute memory cell, if the two meet the condition D < > E, updating the data in the graph node attribute memory cell to the node attribute value D to be written, otherwise, keeping the data in the graph node attribute memory cell unchanged;
the detailed steps of the step 4) comprise:
4.1) the designated graph node attribute memory cell receives the node attribute reading signal to obtain a reading node index;
4.2) comparing the reading node index with the memory cell address of the graph node attribute memory cell;
4.3) if the reading node index is equal to the memory cell address of the graph node attribute memory cell, returning the data in the memory cell, otherwise, returning all 0 s.
2. The shortest path problem-oriented graph node attribute memory implementation method of claim 1, wherein the maximum value in step 2) specifically means that all bins in the data storage area are initialized to all 1 s.
3. An apparatus for implementing a graph node attribute storage facing shortest path problem, comprising a graph node attribute storage and an access control unit, wherein the graph node attribute storage comprises a plurality of graph node attribute storage cells, and the access control unit is programmed or configured to execute the steps of the method for implementing a graph node attribute storage facing shortest path problem in claim 1 or 2.
4. An apparatus for implementing a graph node attribute storage for a shortest path problem, comprising a graph node attribute storage, an access control unit and a storage device, wherein the graph node attribute storage comprises a plurality of graph node attribute storage cells, and the storage device has stored thereon a computer program programmed or configured to execute the method for implementing a graph node attribute storage for a shortest path problem according to claim 1 or 2.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910849008.8A CN110647663B (en) | 2019-09-09 | 2019-09-09 | Graph node attribute memory implementation method and device for shortest path problem |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910849008.8A CN110647663B (en) | 2019-09-09 | 2019-09-09 | Graph node attribute memory implementation method and device for shortest path problem |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110647663A CN110647663A (en) | 2020-01-03 |
| CN110647663B true CN110647663B (en) | 2021-12-17 |
Family
ID=68991693
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910849008.8A Active CN110647663B (en) | 2019-09-09 | 2019-09-09 | Graph node attribute memory implementation method and device for shortest path problem |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110647663B (en) |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2010077884A2 (en) * | 2008-12-30 | 2010-07-08 | Intel Corporation | Memory model for hardware attributes within a transactional memory system |
| CN103064635A (en) * | 2012-12-19 | 2013-04-24 | 华为技术有限公司 | Distributed storage method and device |
| JP2016103154A (en) * | 2014-11-28 | 2016-06-02 | ルネサスエレクトロニクス株式会社 | Data processing method, program, and data processing apparatus |
| EP3159810A1 (en) * | 2015-10-20 | 2017-04-26 | Sap Se | Improved secondary data structures for storage class memory (scm) enabled main-memory databases |
| CN106600062A (en) * | 2016-12-15 | 2017-04-26 | 湖南第师范学院 | Method for calculating the shortest path of single source in multi-region-cross complex network diagram |
-
2019
- 2019-09-09 CN CN201910849008.8A patent/CN110647663B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2010077884A2 (en) * | 2008-12-30 | 2010-07-08 | Intel Corporation | Memory model for hardware attributes within a transactional memory system |
| CN103064635A (en) * | 2012-12-19 | 2013-04-24 | 华为技术有限公司 | Distributed storage method and device |
| JP2016103154A (en) * | 2014-11-28 | 2016-06-02 | ルネサスエレクトロニクス株式会社 | Data processing method, program, and data processing apparatus |
| EP3159810A1 (en) * | 2015-10-20 | 2017-04-26 | Sap Se | Improved secondary data structures for storage class memory (scm) enabled main-memory databases |
| CN106600062A (en) * | 2016-12-15 | 2017-04-26 | 湖南第师范学院 | Method for calculating the shortest path of single source in multi-region-cross complex network diagram |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110647663A (en) | 2020-01-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105242871B (en) | A kind of method for writing data and device | |
| US8793554B2 (en) | Switchable on-die memory error correcting engine | |
| US20120054468A1 (en) | Processor, apparatus, and method for memory management | |
| US8180965B2 (en) | System and method for cache access prediction | |
| US9513992B2 (en) | Method and apparatus to perform concurrent read and write memory operations | |
| US20050055493A1 (en) | [method for accessing large block flash memory] | |
| US20210366562A1 (en) | Memory system processing request based on inference and operating method of the same | |
| JP5622155B2 (en) | Cache memory and control method thereof | |
| US9773534B2 (en) | Non-volatile memory accelerator and method for speeding up data access | |
| KR20170124995A (en) | Autonomous memory architecture | |
| CN108446764A (en) | A kind of new type nerve form chip architecture | |
| CN101840383A (en) | Configurable storage structure supporting continuous/discrete address multidata parallel access | |
| WO2015152922A1 (en) | Memory device with speculated bit flip threshold | |
| CN114527953B (en) | Memory data processing system, method, apparatus, computer device and medium | |
| US11705207B2 (en) | Processor in non-volatile storage memory | |
| CN106708749A (en) | Data search method | |
| US11526285B2 (en) | Memory device for neural networks | |
| CN110647663B (en) | Graph node attribute memory implementation method and device for shortest path problem | |
| KR20200126155A (en) | Semiconductor memory device performing command merging and operating method thereof | |
| CN110490312B (en) | Pooling calculation method and circuit | |
| CN117234720A (en) | Dynamically configurable memory computing fusion data caching structure, processor and electronic equipment | |
| KR20210060022A (en) | Storage device with artificial intelligence and storage system including the same | |
| CN109800867B (en) | Data calling method based on FPGA off-chip memory | |
| US9460782B2 (en) | Method of operating memory controller and devices including memory controller | |
| CN110766133B (en) | Data processing method, device, equipment and storage medium in embedded equipment |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |