Graph cache reconfiguration
View Patent ↗A graph cache may be dynamically reconfigured to adapt to changes in a graph or access requirements. In an implementation, the graph cache includes a content addressable memory (CAM) array comprising CAM rows and match lines, configured to receive an identifier of a target node of a graph structure and a key associated with a user credential, search for a combination of the identifier and key, and activate match lines corresponding to matching CAM rows. A random-access memory (RAM) array comprises RAM rows and word lines. A multiple match resolver serially activates word lines of the RAM array corresponding to activated match lines. A management processor receives an encrypted input, decrypts it to obtain the identifier and key, and provides the combination to the CAM array.
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 a combination of an identifier of a target node of a graph structure and a key associated with a user credential, to search for the combination of the identifier and the key in the CAM rows, and to activate ones of the match lines corresponding to the CAM rows that store the combination of the identifier and the key;
a random-access memory (RAM) array comprising RAM rows and word lines corresponding to the RAM rows;
a multiple match resolver connected to the CAM array and to the RAM array, the multiple match resolver configured to;
serially generate a plurality of output vectors corresponding to the match lines of the CAM array that are activated; and
serially provide the output vectors to the word lines of the RAM array, wherein each of the output vectors activates a respective one of the word lines while remaining ones of the word lines remain deactivated; and
a management processor configured to:
receive an encrypted input;
decrypt the encrypted input to obtain the identifier and the key; and
provide the combination of the identifier and the key to the CAM array.
2 . The graph cache of claim 1 , wherein the management processor is further configured to partition the graph structure into partitions, and the key is associated with one of the partitions.
3 . The graph cache of claim 2 , wherein the partitioning of the graph structure is physical, with each of the partitions corresponding to a separate physical section of the CAM array.
4 . The graph cache of claim 2 , wherein the partitioning of the graph structure is logical, with each of the partitions corresponding to a separate logical section of the CAM array.
5 . The graph cache of claim 2 , wherein the management processor is further configured to swap data corresponding to different ones of the partitions in and out of the CAM array.
6 . The graph cache of claim 1 , wherein the encrypted input comprises an encrypted identifier and an encrypted key, and wherein the management processor is configured to decrypt the encrypted identifier and the encrypted key.
7 . The graph cache of claim 1 , wherein the management processor is configured to decrypt the encrypted input using a public-private key pair.
8 . The graph cache of claim 1 , wherein the CAM array further comprises search lines, the management processor is connected to the search lines, and the CAM array receives the combination of the identifier and the key on the search lines.
9 . The graph cache of claim 1 , wherein the RAM array further comprises bit lines, the management processor is connected to the 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.
10 . The graph cache of claim 9 , wherein the management processor is further configured to encrypt the memory addresses for the neighbor nodes.
11 . 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, the register being configured to store a match vector comprising high values, the high values corresponding to the match lines of the CAM array that are activated, wherein the output vectors generated by the multiple match resolver correspond to the high values of the match vector.
12 . The graph cache of claim 1 , wherein the CAM array is configured to simultaneously activate the match lines corresponding to the CAM rows that store the combination of the identifier and the key.
13 . The graph cache of claim 1 , wherein each of the output vectors comprises a plurality of values, each of the values being a low value except for one of the values being a high value.
14 . The graph cache of claim 1 , wherein the multiple match resolver is a match token multiple match resolver.
15 . The graph cache of claim 1 , wherein each of the CAM rows comprises a plurality of CAM cells, wherein a first subset of the CAM cells stores a key, wherein a second subset of the CAM cells stores an identifier.
16 . The graph cache of claim 1 , wherein the management processor is further configured to:
receive an embedding address from the RAM array;
encrypt the embedding address; and
output the encrypted embedding address.
17 . The graph cache of claim 1 , further comprising:
a register connected to the match lines of the CAM array, wherein the register is configured to store a match vector corresponding to the match lines of the CAM array, the match vector includes high values corresponding to the match lines of the CAM array that are activated, and the match vector includes low values corresponding to the match lines of the CAM array that are deactivated.
18 . The graph cache of claim 1 , wherein each of the CAM rows that stores the identifier of the target node corresponds to an edge connecting the target node to a neighbor node of the target node in the graph structure.
19 . The graph cache of claim 1 , wherein the CAM array is programmed with values corresponding to edges of the graph structure, and the RAM array is programmed with memory addresses pointing to embeddings of neighbor nodes of the target node stored in a memory external to the graph cache.
20 . The graph cache of claim 1 , wherein an input port and an output port of the graph cache are connected to the management processor, and the management processor is an intermediary for data input and output within the graph cache.