Dynamic memory management apparatus and method for HLS
The present invention relates to a dynamic memory management apparatus and method for HLS, the apparatus has several searching and caching modules and several modifying and writing-back modules, the searching and caching modules are in connection with a DRAM storing module and a BRAM buffer, respectively, and the modifying and writing-back modules are in connection with the DRAM storing module and the BRAM buffer, respectively, the BRAM buffer is for caching information about nodes on a search path and registering information about modification made to the nodes. To remedy the defect that the traditional operating system is directly transplanted to the FPGA and has low execution efficiency, the present invention utilizes the advantage of the large capacity of the DRAM on the FPGA to realize efficient dynamic memory allocation and deallocation, and improve the usability and code reusability of HLS.
1. A dynamic memory management apparatus for HLS, at least comprising: several searching and caching modules and several modifying and writing-back modules,
wherein the searching and caching modules are in connection with a DRAM storing module and a block random access memory (BRAM) buffer respectively, and the modifying and writing-back modules are in connection with the DRAM storing module and the BRAM buffer respectively, wherein the BRAM buffer is for caching information about nodes on a search path and registering information about modification made to the nodes;
the searching and caching module is for reading node data from the DRAM storing module according to received operator and address of node, and writing the node data into the BRAM buffer; and
the modifying and writing-back module reads the node data from the BRAM buffer and writes the node data back into the DRAM storing module, wherein the DRAM storing module is at least divided into a static storage area, a dynamic storage area, and a multi-way search tree storage area,
the static storage area is for storing information that will not be released once written;
the dynamic storage area is a dynamically managed memory area; and
the multi-way search tree storage area is for storing search tree structure information so that the search tree structure information is managed based on a free node linked list at a node-based granularity,
for node extraction, the multi-way search tree storage area extracts the next node from a head of the free node linked list, and for node release, a free node is inserted back into the head of the free node linked list.
2. The dynamic memory management apparatus for HLS of claim 1 ,
wherein the plural searching and caching modules are arranged into a multi-layer structure that has as many layers as the search tree does, wherein
after one of the searching and caching modules analyzes the operators and the node data, the searching and caching module transmits the corresponding operators and the addresses of the nodes to be read to the next adjacent searching and caching module.
3. The dynamic memory management apparatus for HLS of claim 2 , wherein the plural modifying and writing-back modules are arranged into a multi-layer structure that has as many layers as the search tree does, and
the modifying and writing-back modules modify the nodes in the BRAM buffer according to the received operators, and write the node data back into the multi-way search tree storage area in the DRAM storing module, wherein
after one of the modifying and writing-back modules analyzes the operators and the read nodes, the modifying and writing-back module transmits the corresponding operators to the adjacent modifying and writing-back module.
4. The dynamic memory management apparatus for HLS of claim 3 , wherein a data transmission order among the searching and caching modules is reverse to the plural modifying and writing-back modules.
5. The dynamic memory management apparatus for HLS of claim 4 , wherein the multi-way search tree storage area is configured to manage a memory in such a manner that:
it manages free memory blocks in the memory based on the structure of the search tree; wherein
a free memory block is a minimum unit of the memory and is represented by its head address and length.
6. The dynamic memory management apparatus for HLS of claim 5 , further comprising a switching module, which is in connection with the searching and caching module at the bottom layer and the modifying and writing-back module at the bottom layer, respectively, wherein
after the searching and caching module at the bottom layer transmits the operators for releasing the memory blocks to the switching module, the switching module reverses the transmission order and transmits those to the modifying and writing-back module connected thereto.
7. The dynamic memory management apparatus for HLS of claim 6 , further comprising a request queuing module, which is in connection with the top searching and caching modules, wherein
the request queuing module is for caching memory allocating requests and memory release requests issued by a computing unit, wherein
the allocating requests that are failed due to out of memory are cached in a queue, and
the dequeued allocating requests are added into the pipeline to participate in computing.
8. The dynamic memory management apparatus for HLS of claim 7 , wherein
the request queuing module is in connection with the individual searching and caching modules, respectively,
plural searching and caching modules are arranged into a multi-layer structure that has as many layers as the search tree does,
after one of the searching and caching modules analyzes the operators and the node data, the searching and caching module transmits the corresponding operators and the addresses of the nodes to be read to the next adjacent searching and caching module according to a predetermined order.
9. The dynamic memory management apparatus for HLS of claim 8 , wherein the searching and caching module at the bottom layer and the modifying and writing-back module at the bottom layer are in connection with the switching module,
after the searching and caching module at the bottom layer transmits the operators for releasing memory blocks to the switching module, the switching module transmits the operators to the modifying and writing-back module connected thereto and the order of the operators is reversed.
10. A dynamic memory management method for HLS, at least comprising:
arranging several searching and caching modules into a multi-layer structure that has as many layers as a search tree does,
arranging several modifying and writing-back modules into a multi-layer structure that has as many layers as the search tree does,
at the searching and caching modules, reading node data from a DRAM storing module according to operators and node address transmitted by the upper layer and writing the node data into a block random access memory (BRAM) buffer that caches information about nodes on the search path and caches modification made to the nodes; and at the modifying and writing-back modules, reading the node data from the BRAM buffer and writing the node data back into the DRAM storing module.
11. The dynamic memory management method for HLS of claim 10 , the method further comprising:
dividing the DRAM storing module into at least a static storage area, a dynamic storage area, and a multi-way search tree storage area; wherein
the static storage area is for storing information that will not be released once written,
the dynamic storage area is a dynamically managed memory area; and
the multi-way search tree storage area is for storing search tree structure information and is configured to manage memory in such a manner that:
it manages free memory blocks in the memory based on the search tree data structure; wherein a free memory block is a minimum unit of the memory.
12. The dynamic memory management method for HLS of claim 11 , wherein the searching and caching modules are arranged into a multi-layer structure that has as many layers as the search tree does, wherein
after one of the searching and caching modules analyzes the operators and the node data, the searching and caching module transmits the corresponding operators and the addresses of the nodes to be read to the next adjacent searching and caching module.
13. The dynamic memory management method for HLS of claim 12 , wherein the modifying and writing-back modules are arranged into a multi-layer structure that has as many layers as the search tree does, and
the modifying and writing-back modules modify the nodes in the BRAM buffer according to the received operators, and write the node data back into the multi-way search tree storage area in the DRAM storing module, wherein
after one of the modifying and writing-back modules analyzes the operators and the read nodes, the modifying and writing-back module transmits the corresponding operators to the modifying and writing-back module at the next layer.
14. The dynamic memory management method for HLS of claim 13 , wherein a data transmission order among the layers of the searching and caching modules is reverse to a data transmission order among the layers of the plural modifying and writing-back modules.
15. The dynamic memory management method for HLS of claim 14 , wherein the multi-way search tree storage area is for storing search tree structure information so that the search tree structure information is managed based on a free node linked list at node based granularity, wherein
for node extraction, the multi-way search tree storage area extracts the next node from a head of the free node linked list, and for node release, a free node is inserted back into the head of the free node linked list.
16. The dynamic memory management method for HLS of claim 15 , wherein a switching module is in connection with the searching and caching module at the bottom layer and the modifying and writing-back module at the bottom layer, respectively, wherein
after the searching and caching module at the bottom layer transmits the operators for releasing the memory blocks to the switching module, the switching module reverses a transmission order of the operators and transmits the operators to the modifying and writing-back module connected thereto.
17. The dynamic memory management method for HLS of claim 16 , wherein a request queuing module is in connection with the plural searching and caching modules, wherein
the request queuing module is for caching memory allocating requests and memory release requests issued by a computing unit, wherein
the allocating requests that are failed due to out of memory are cached in a queue, and
the dequeued allocating requests are added into a pipeline to compute.
18. The dynamic memory management method for HLS of claim 17 , wherein
the request queuing module is in connection with the individual searching and caching modules, respectively,
plural searching and caching modules are arranged into a multi-layer structure that has as many layers as the search tree,
after one of the searching and caching modules analyzes the operators and the node data, the searching and caching module transmits the corresponding operator and the address of the node to be read to the next searching and caching module according to a predetermined order,
the operator and the node data are transmitted from the searching and caching module at the upper layer to the searching and caching module at the lower layer.
19. The dynamic memory management method for HLS of claim 18 , wherein the searching and caching module and the modifying and writing-back module at the bottom layer are in connection with the switching module respectively,
after the searching and caching module at the bottom layer transmits the operators for releasing memory blocks to the switching module, the switching module reverses the transmission order and transmits to the modifying and writing-back module connected thereto.