Selective replication of data structures
View Patent ↗Methods and apparatus are provided for selectively replicating a data structure in a low-latency memory. The memory includes multiple individual memory banks configured to store replicated copies of the same data structure. Upon receiving a request to access the stored data structure, a low-latency memory access controller selects one of the memory banks, then accesses the stored data from the selected memory bank. Selection of a memory bank can be accomplished using a thermometer technique comparing the relative availability of the different memory banks. Exemplary data structures that benefit from the resulting efficiencies include deterministic finite automata (DFA) graphs and other data structures that are loaded (i.e., read) more often than they are stored (i.e., written).
1. A method for managing a low-latency memory including a plurality of memory banks, the method comprising:
receiving a request to store a determined number of replications of a data structure in the plurality of memory banks, the request including a replication factor indicative of the number of replications selected, the replication factor being any number between one and the plurality of memory banks; and
storing, responsive to the store request, each of the determined number of replications in a respective one of the plurality of memory banks.
2. The method of claim 1 , wherein the replication factor is a power of two.
3. The method of claim 1 , wherein the data structure is a deterministic finite automata.
4. The method of claim 1 , wherein each of the plurality of memory banks is accessible using one of a plurality of low-latency memory interfaces, at least some of the replications of a data structure being accessible using different low-latency interfaces.
5. The method of claim 1 , further comprising:
receiving a request to access the stored data structure;
selecting, responsive to the access request, one of the memory banks of the plurality of memory banks, the selected memory bank storing a replication of the requested data structure; and
accessing the selected memory bank.
6. The method of claim 5 , wherein selecting one of the memory banks comprises:
determining usage of each memory bank of the plurality of memory banks storing a replication of the data structure; and
selecting one of the plurality of memory banks responsive to the determined usage.
7. The method of claim 6 , wherein the step of determining usage comprises comparing a plurality of queues, each queue associated with a respective one of the plurality of memory banks.
8. The method of claim 1 , wherein the low-latency memory is selected from the group consisting of: dynamic random access memory (DRAM); Reduced Latency Dynamic Random Access Memory (RLDRAM); Synchronous Random Access Memory (SRAM); Fast Cycle Random Access Memory (FCRAM); and combinations thereof
9. The method of claim 1 , further comprising determining the replication factor based on frequency of access to the data structure.
10. A low-latency memory management controller comprising:
a first memory interface configured to access a low-latency memory, the low-latency memory including a plurality of memory banks;
a main memory interface adapted to access a main memory;
instruction unit coupled to the main memory interface receiving a request to store a selectable number of replications of a data structure in more than one memory bank of the plurality of memory banks, the request to store a selectable number of replications including a replication factor indicative of the number of replications selected, the replication factor being any number between one and the plurality of memory banks;
plurality of thread engines coupled to the instruction unit, each thread engine adapted for association with a selectable respective one of the plurality of memory banks; and
a low-latency memory controller coupled to the instruction unit, and coupled between the first memory interface and the plurality of thread engines, the low-latency memory controller storing each of the selected number of replications of the data structure on a respective one of the plurality of memory banks.
11. The apparatus of claim 10 , wherein the processor comprises a multi-core processor.
12. The apparatus of claim 10 , wherein the replication factor is a power of two.
13. The apparatus of claim 10 , wherein the low-latency memory controller comprises a plurality of input queues, one input queue for each of the plurality of memory banks, the low-latency memory controller selecting one of the plurality of memory banks responsive to a determined value.
14. The apparatus of claim 13 , wherein the determined value relates to usage of the stored data structure.
15. The apparatus of claim 13 , wherein the low-latency memory controller includes a thermometer unit determining the relative availability among different queues of the plurality of input queues, each input queue associated with a respective one of the plurality of memory banks.
16. The apparatus of claim 10 , wherein the data structure comprises deterministic finite automata.
17. The apparatus of claim 10 , wherein the low-latency memory is selected from the group consisting of: dynamic random access memory (DRAM); Reduced Latency Dynamic Random Access Memory (RLDRAM); Synchronous Random Access Memory (SRAM); Fast Cycle Random Access Memory (FCRAM); and combinations thereof.
18. The apparatus of claim 10 , wherein some of the plurality of memory banks are accessible using a first low-latency memory interfaces and others of the plurality of memory banks are accessible using a second low-latency memory interface, at least some of the replications of a data structure being accessible using either of the first and second low-latency memory interfaces.
19. The apparatus of claim 10 , further comprising a processor interface through which the low-latency memory management controller communicates with a processor.
20. The apparatus of claim 10 , wherein the replication factor is based on frequency of access to the data structure.
21. A low-latency memory access system comprising:
a plurality of memory banks;
means for receiving a request to store a determined number of replications of a data structure in the plurality of memory banks, the request including a replication factor indicative of the number of replications selected, the replication factor being any number between one and the plurality of memory banks; and
means for storing, responsive to the store request, each of the determined number of replications in a respective one of the plurality of memory banks.