A cache is used for efficiently storing a graph structure. The graph cache may be used in a computing system to accelerate processing of a graph by a graph neural network, and is different than a general-purpose memory of the computing system. Embeddings for the nodes of a graph are stored in the memory of the computing system, while the structure of the graph is stored in the graph cache. The graph cache may include a content addressable memory array, which may be suitable for efficiently representing a graph structure.
1. A graph cache comprising:
a content addressable memory (CAM) array comprising CAM rows and match lines corresponding to the CAM rows, the CAM array configured to receive an identifier of a target node of a graph structure, to search for the identifier in the CAM rows, and to activate ones of the match lines corresponding to the CAM rows that store the identifier;
a random-access memory (RAM) array comprising RAM rows and word lines corresponding to the RAM rows; and
a multiple match resolver connected to the CAM array and to the RAM array, the multiple match resolver configured to serially activate the word lines of the RAM array corresponding to the match lines of the CAM array that are activated.
2. The graph cache of claim 1 , wherein the CAM array further comprises search lines, and the CAM array receives the identifier on the search lines.
3. The graph cache of claim 2 , further comprising:
an input port connected to the search lines.
4. The graph cache of claim 1 , wherein the RAM array further comprises bit lines, and the RAM array is configured to output memory addresses for neighbor nodes of the target node on the bit lines when the word lines are activated.
5. The graph cache of claim 4 , further comprising:
an output port connected to the bit lines.
6. The graph cache of claim 1 , further comprising:
a register connected to the match lines of the CAM array, an output of the register connected to an input of the multiple match resolver.
7. The graph cache of claim 6 , wherein the register is configured to store a match vector comprising high values, the high values corresponding to the match lines of the CAM array that are activated.
8. The graph cache of claim 7 , wherein the multiple match resolver is configured to serially generate output vectors corresponding to the high values of the match vector, and to provide the output vectors to the RAM array.
9. The graph cache of claim 1 , wherein the multiple match resolver comprises a match token multiple match resolver.
10. The graph cache of claim 1 , wherein the CAM rows comprise ternary content-addressable memory cells, and the RAM rows comprise static random-access memory cells.
11. A method, implemented by a computing system, the method comprising:
obtaining memory addresses for neighbor nodes of a target node from a graph cache of the computing system, the graph cache storing a graph structure comprising the target node and the neighbor nodes, the neighbor nodes being connected to the target node in the graph structure, the memory addresses being locations of a memory of the computing system, the memory being different than the graph cache;
accessing neighbor embeddings of the neighbor nodes at the memory addresses of the memory;
updating a target embedding of the target node by aggregating the neighbor embeddings of the neighbor nodes; and
storing the target embedding of the target node in the memory.
12. The method of claim 11 , further comprising:
storing the graph structure in the graph cache.
13. The method of claim 12 , wherein storing the graph structure in the graph cache comprises:
programming a content addressable memory array of the graph cache with an identifier of the target node; and
programming a random-access memory array of the graph cache with the memory addresses.
14. The method of claim 11 , wherein obtaining the memory addresses comprises:
searching for an identifier of the target node in a content addressable memory (CAM) array of the graph cache, match lines of CAM rows of the CAM array being activated in response to the CAM rows storing the identifier; and
activating word lines of a random-access memory (RAM) rows of a RAM array, the word lines of the RAM rows corresponding to the match lines of the CAM rows, the RAM rows storing the memory addresses.
15. The method of claim 14 , wherein the word lines of the RAM rows are activated serially.
16. The method of claim 11 , wherein obtaining the memory addresses comprises:
providing an identifier of the target node to the graph cache; and
receiving the memory addresses from the graph cache.
17. A computing system comprising:
a processor;
a graph cache; and
a memory, the memory being different than the graph cache, the memory comprising a non-transitory computer readable medium storing instructions which, when executed by the processor, cause the processor to:
store a graph structure in the graph cache;
provide an identifier of a target node of the graph structure to the graph cache;
receive memory addresses for neighbor nodes of the target node from the graph cache, the neighbor nodes being connected to the target node in the graph structure, the memory addresses being locations of the memory;
access neighbor embeddings of the neighbor nodes at the memory addresses of the memory;
update a target embedding of the target node by aggregating the neighbor embeddings of the neighbor nodes; and
store the target embedding of the target node in the memory.
18. The computing system of claim 17 , wherein the graph cache has a different architecture than the memory.
19. The computing system of claim 17 , wherein the graph cache comprises:
a content addressable memory (CAM) array comprising match lines;
a register connected to the match lines of the CAM array;
a random-access memory (RAM) array comprising word lines; and
a multiple match resolver connected to the word lines of the RAM array, the register connected to the multiple match resolver.
20. The computing system of claim 19 , wherein the instructions to store the graph structure in the graph cache comprise instructions to:
program the CAM array with the identifier of the target node; and
program the RAM array with the memory addresses for the neighbor nodes.