Dynamic memory management apparatus and method for HLS

Patent metadata

Field	Value
Publication number	US-12189950-B2
Application number	US-202218145552-A
Country	US
Kind code	B2
Filing date	Dec 22, 2022
Priority date	Aug 11, 2022
Publication date	Jan 7, 2025
Grant date	Jan 7, 2025

Abstract

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.

First claim

What is claimed is:

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 wri

Assignees

• Univ Huazhong Science Tech
• Zhejiang Lab

Inventors

• Zheng Long
• Wang Qinggang
• Liao Xiaofei
• An Zhaozeng
• Jin Hai

Classifications

• G06F3/0673

  Single storage device · CPC title

• G06F3/0656

  Data buffering arrangements · CPC title

• G06F16/90335

  Query processing · CPC title

• G06F12/0893

  Caches characterised by their organisation or structure · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title