CN-121996429-A - Pointer distribution device, linked list structure and chip of linked list

CN121996429ACN 121996429 ACN121996429 ACN 121996429ACN-121996429-A

Abstract

The application relates to a pointer distribution device, a linked list structure and a chip of a linked list, which comprise a first-stage FIFO module, a second-stage buffer memory module, a pointer control logic module and a third-stage memory module, wherein the first-stage FIFO module is used for storing null pointers, the second-stage buffer memory module is used for storing first use state information of pointers corresponding to partial memory units of a memory entity, the third-stage memory module is used for storing second use state information of pointers corresponding to all memory units of the memory entity, the pointer control logic module is used for acquiring the null pointers from the first-stage FIFO module according to a write request, and when the number of the null pointers in the first-stage FIFO module is insufficient, the second-stage buffer memory module is used for supplementing the null pointers to the first-stage FIFO module, and when resources in the second-stage buffer memory module are insufficient, the third-stage memory module is used for supplementing resources to the second-stage FIFO module. According to the application, the hardware resources of the linked list can be reduced and the hardware logic of the linked list can be simplified.

Inventors

ZHANG XUELI
SUN JINGYU
ZHAI XIN

Assignees

深圳云豹智能股份有限公司

Dates

Publication Date: 20260508
Application Date: 20260408

Claims (12)

1. The pointer distribution device of the linked list is characterized by comprising a first-stage FIFO module, a second-stage cache module, a third-stage storage module and a pointer control logic module; The first-stage FIFO module is used for storing a null pointer, wherein the null pointer is the address of a free storage unit in a storage entity for storing linked list data, and the storage entity comprises a plurality of storage units; The second-level buffer module is used for storing first use state information of pointers corresponding to part of storage units of the storage entity, wherein the first use state information comprises unused and used; The third-level storage module is used for storing second use state information of pointers corresponding to all storage units of the storage entity, wherein the second use state information comprises unused and used storage capacity of the third-level storage module is larger than that of the second-level cache module, and the storage capacity of the second-level cache module is larger than that of the first-level FIFO module; The pointer control logic module is configured to obtain a target null pointer according to the first usage state information stored in the second-level buffer module when the number of null pointers in the first-level FIFO module is detected to be smaller than a preset threshold, write the target null pointer into the first-level FIFO module, and update corresponding first usage state information in the second-level buffer module; The pointer control logic module is further configured to obtain a set of second usage state information according to the second usage state information stored in the third-level storage module when it is detected that the first usage state information in the second-level cache module meets a preset condition, and write the set of second usage state information into the second-level cache module as a new set of first usage state information, where the preset condition indicates that the second-level cache module needs to be supplemented with the set of first usage state information.
2. The pointer allocation apparatus according to claim 1, wherein in the second level buffer module, when a storage unit corresponding to any pointer is free and the any pointer is written into the first level FIFO module, or a storage unit corresponding to any pointer is not free, the first usage status information of any pointer is set to be used, otherwise the first usage status information of any pointer is set to be unused; The pointer control logic module is specifically configured to obtain a target null pointer according to first usage state information of a pointer in the second level buffer module when the number of null pointers in the first level FIFO module is detected to be smaller than a preset threshold, write the target null pointer into the first level FIFO module, and update the first usage state information of the target null pointer in the second level buffer module to be used.
3. The pointer allocation apparatus of claim 2 wherein said second level cache module comprises a plurality of cache lines, each cache line comprising a plurality of first usage status information, said third level storage module comprising a plurality of groups, each group comprising a plurality of second usage status information; In the third-level storage module, when a storage unit corresponding to any pointer is idle and a group to which the any pointer belongs is not prefetched to the second-level cache module, or the any pointer is released and status is finished for back flushing, the second use status information of the any pointer is set to be unused; The pointer control logic module is specifically configured to obtain a set of second usage state information according to the second usage state information in the third-level storage module when it is detected that the first usage state information of any cache line in the second-level storage module is used, and write the set of second usage state information as a new set of first usage state information into the any cache line, where at least one second usage state information exists in the set of second usage state information as unused.
4. The pointer allocation apparatus of claim 3 wherein said second level buffer module comprises a plurality of first status bits, each first status bit for storing a first usage status information; The pointer control logic module is specifically configured to update a first mapping relationship between each first status bit in the arbitrary cache line and the pointer after the set of second usage status information is written as a set of new first usage status information to the arbitrary cache line; The pointer control logic module is specifically configured to obtain the target null pointer according to the first usage state information of the pointer in the second level buffer module and the first mapping relationship.
5. The pointer allocation apparatus of claim 4, wherein the pointer control logic module is further specifically configured to update a second mapping relationship between a line number of the any cache line and a group number corresponding to the set of second usage state information after the set of second usage state information is written as a new set of first usage state information to the any cache line; And the pointer control logic module is specifically further configured to obtain a corresponding target group number according to the line number of any cache line and the second mapping relationship when all the first use state information of any cache line in the second-level cache module is detected to be used, and update a group of second use state information corresponding to the target group number in the third-level storage module to be used.
6. The pointer allocation apparatus of claim 5 wherein said first stage FIFO module comprises a plurality of queue elements, each queue element for storing a null pointer, each group of said third stage storage modules comprising a plurality of second status bits, each second status bit for storing a second usage status information; The number of second status bits in each group of the third-level memory module is the same as the number of queue elements in the first-level FIFO module and the number of first status bits in each cache line of the second-level cache module.
7. The pointer allocation apparatus according to claim 3, wherein the pointer control logic is specifically configured to determine, when data of a storage unit corresponding to a head pointer of a linked list is read out, whether a number of null pointers in the first stage FIFO module is smaller than the preset threshold, if yes, write the head pointer into the first stage FIFO module, and if not, update a second usage status information corresponding to the head pointer in the third stage storage module to be unused.
8. The pointer allocation apparatus according to claim 7, wherein the pointer control logic is specifically configured to, when the number of null pointers in the first stage FIFO module is smaller than a preset threshold, preferentially write the head pointer currently released by the linked list into the first stage FIFO module as a target null pointer, and if the number of null pointers in the first stage FIFO module is still smaller than the preset threshold after writing the head pointer currently released by the linked list into the first stage FIFO module, further obtain a target null pointer according to the pointer usage status information stored by the second stage buffer module, and write the target null pointer into the first stage FIFO module until the number of null pointers in the first stage FIFO module is equal to the preset threshold.
9. The pointer allocation apparatus according to claim 1, wherein the pointer control logic module is specifically configured to, when a write request is received, suspend responding to the write request if the first FIFO module is empty and all the first usage status information in the second FIFO module is used, and otherwise, obtain a null pointer from the first FIFO module and output in response to the write request.
10. A linked list structure, comprising a head pointer entity, a tail pointer entity, a storage entity, a pointer entity, a read control logic module, a pointer allocation device according to any one of claims 1 to 9; The head pointer entity is used for storing the head pointer of the linked list; the tail pointer entity is used for storing tail pointers of the linked list; the storage entity is used for storing the data of the linked list; the pointer entity is used for storing the pointing relation between pointers; The read control logic module is used for receiving a write request, writing data carried by the write request into a storage unit corresponding to the null pointer according to the null pointer output by the pointer distribution device in response to the write request, and updating the pointing relation between corresponding pointers in the pointer entity and the tail pointer of the linked list.
11. The linked list structure of claim 10, wherein the read control logic is further configured to receive a read request, search the head pointer entity for a head pointer based on the read request, read data of a corresponding storage unit from the storage entity based on the head pointer, and update the head pointer of the linked list.
12. A chip comprising the pointer allocation device according to any one of claims 1 to 9, or the linked list structure according to claim 10 or 11.

Description

Pointer distribution device, linked list structure and chip of linked list Technical Field The application relates to the technical field of linked lists, in particular to a pointer distribution device, a linked list structure and a chip of a linked list. Background The linked list uses pointers to connect scattered memory nodes in series, and realizes ordered storage and discontinuous access of data through head-tail pointers and subsequent pointers between nodes, wherein the pointers are used for allocating null pointers for hanging new nodes when writing data, and removing head node pointers and releasing resources when reading data. The linked list used in the current hardware design mainly has the following two types: the FIFO (FIRST IN FIRST Out) is usually composed of registers or RAMs based on a large-capacity FIFO, and particularly, the FIFO (FIRST IN FIRST Out) is used for storing all available pointers based on the large-capacity FIFO linked list by using a FIFO queue, all sub-linked lists share the FIFO queue, the depth of the FIFO is in direct proportion to the number of pointers (or nodes) supported by the linked list, for example, 4k nodes are supported, a FIFO with the depth of 4k is needed, the scheme based on the large-capacity FIFO has the advantages of simple logic and easy convergence of time sequence, but the depth of the FIFO queue occupies a large amount of registers or RAM resources (therefore, the FIFO with the large capacity) so as to cause large chip area cost and be unfavorable for chip design. The bitmap-based linked list is realized and consists of a plurality of bits, specifically, the bitmap-based linked list records the service condition of each pointer by using one bitmap, each bit corresponds to one pointer, 0 indicates that the pointer is available, and 1 indicates that the pointer is occupied, the bitmap-based scheme has the advantages of relatively less occupied resources, complex searching and releasing logic of the pointer, the need of traversing the bitmap to search for a null pointer, long comprehensive time sequence path, difficult convergence of time sequence, poor performance and incapability of realizing high-throughput beat processing (namely, processing one request every clock cycle), and inapplicability to high-concurrency scenes. Therefore, how to solve the technical problems that the hardware resource occupation of the traditional high-capacity FIFO-based linked list is too high and the time sequence is difficult to converge due to the logic complexity of the bitmap-based linked list is urgent need in the current hardware design field. Disclosure of Invention The application aims to provide a pointer distribution device, a linked list structure and a chip of a linked list, so as to reduce hardware resources of the linked list and simplify hardware logic of the linked list, and solve the technical problems that the occupation of hardware resources of the linked list is too high based on a large-capacity FIFO and the time sequence is difficult to converge due to the logic complexity of the linked list based on a bitmap. In order to achieve the above object, according to a first aspect of the present application, a pointer allocation device for a linked list is provided, including a first-stage FIFO module, a second-stage buffer module, a third-stage storage module, and a pointer control logic module; The first-stage FIFO module is used for storing a null pointer, wherein the null pointer is the address of a free storage unit in a storage entity for storing linked list data, and the storage entity comprises a plurality of storage units; The second-level buffer module is used for storing first use state information of pointers corresponding to part of storage units of the storage entity, wherein the first use state information comprises unused and used; The third-level storage module is used for storing second use state information of pointers corresponding to all storage units of the storage entity, wherein the second use state information comprises unused and used storage capacity of the third-level storage module is larger than that of the second-level cache module, and the storage capacity of the second-level cache module is larger than that of the first-level FIFO module; The pointer control logic module is configured to obtain a target null pointer according to the first usage state information stored in the second-level buffer module when the number of null pointers in the first-level FIFO module is detected to be smaller than a preset threshold, write the target null pointer into the first-level FIFO module, and update corresponding first usage state information in the second-level buffer module; The pointer control logic module is further configured to obtain a set of second usage state information according to the second usage state information stored in the third-level storage module when it is detected that the first usage state information in the