CN115658327B

CN115658327B - Device and method for managing storage space, computing device and chip

Info

Publication number: CN115658327B
Application number: CN202211561698.5A
Authority: CN
Inventors: 请求不公布姓名
Original assignee: Moore Threads Technology Co Ltd
Current assignee: Moore Threads Technology Co Ltd
Priority date: 2022-12-07
Filing date: 2022-12-07
Publication date: 2023-10-31
Anticipated expiration: 2042-12-07
Also published as: CN115658327A

Abstract

The present disclosure discloses an apparatus, method, computing device, and chip for managing storage space. The device comprises: a request source interface connected to the external request source and configured to receive a space management request from the external request source; an index memory configured to store one or more memory cell indices, wherein each memory cell index is used to characterize one memory cell of a preset size in the memory space; and the space management module is configured to manage the storage unit indexes in the index storage according to the space management request. By the scheme, the read-write path of the storage unit index is shortened, and space management efficiency is improved.

Description

Device and method for managing storage space, computing device and chip

Technical Field

The present disclosure relates to the field of computer technology, and in particular, to an apparatus for managing storage space, a computing device, a method for managing storage space, and a chip.

Background

With the development of computer technology, more and more various computing devices are presented in life, work and study of people. Generally, in these computing devices, there are various forms of processors, controllers, or microcontrollers that, when they run an application to perform a function, need to request a certain amount of space from memory, and when the application is running, the corresponding space can be freed. This involves the management of memory space.

At present, the management of the memory space is generally realized in a software mode, that is, a CPU (central processing unit ) or an MCU (Microcontroller Unit, micro control unit) runs a memory management policy, and issues an instruction, so that a hardware system processes the instruction, and then the read-write operation of the memory is realized through a bus. In the memory management scheme implemented by the software, the problems of long path, high delay, complex structure and the like generally exist.

Disclosure of Invention

In view of the above, the present disclosure provides an apparatus for managing storage space, a method for managing storage space, a computing device, and a chip, which may alleviate, mitigate, or even eliminate the above-mentioned problems.

According to an aspect of the present disclosure, there is provided an apparatus for managing storage space, including: a request source interface connected to the external request source and configured to receive a space management request from the external request source; an index memory configured to store one or more memory cell indices, wherein each memory cell index is used to characterize one memory cell of a preset size in the memory space; and the space management module is configured to manage the storage unit indexes in the index storage according to the space management request.

In some embodiments, the index memory includes an index store queue.

In some embodiments, the space management request includes a space allocation request and a space reclamation request, and the space management module includes: a space allocation module configured to: allocating at least one storage unit index to an external request source according to the size of the space requested to be allocated by the space allocation request; a space reclamation module configured to: one or more storage unit indexes are written to the index memory according to the space requested to be reclaimed by the space reclamation request.

In some embodiments, the space allocation module comprises: a readout counting circuit configured to: in response to the index read number not being equal to the number to be allocated, adding 1 to the index read number, wherein the number to be allocated is determined based on the amount of space requested to be allocated by the space allocation request; a readout circuit configured to: in response to the index read number not being equal to the number to be allocated, at least one memory cell index is read from the index memory and the read at least one memory cell index is output.

In some embodiments, the space management module further comprises: and the index generation module is configured to generate one or more storage unit indexes according to a preset rule.

In some embodiments, the space allocation module is further configured to: in response to the allocated number of storage unit indexes being less than the threshold number, causing the index generation module to generate at least one storage unit index, wherein the allocated number of storage unit indexes is a cumulative number of storage unit indexes allocated to the external request source; reading at least one storage unit index from an index memory in response to a sum of an allocated number of storage unit indexes and a number to be allocated being greater than a threshold number, wherein the number to be allocated is determined based on an amount of space requested to be allocated by a space allocation request; the generated at least one storage unit index and/or the read at least one storage unit index is assigned to an external request source.

In some embodiments, the space allocation module comprises: a readout counting circuit configured to: in response to the index read number not being equal to the number to be allocated, adding 1 to the index read number; a selection circuit configured to: in response to the allocated number of storage unit indexes being less than the threshold number, causing the index generation module to generate at least one storage unit index, and in response to the sum of the allocated number of storage unit indexes and the number to be allocated being greater than the threshold number, reading the at least one storage unit index from the index memory; a readout circuit configured to: at least one memory cell index provided by the selection circuit is output in response to the index read number not being equal to the number to be allocated.

In some embodiments, the index generation module is further configured to: after the device is powered on, generating a plurality of storage unit indexes according to a preset rule, and writing the storage unit indexes into an index memory.

In some embodiments, the space reclamation module includes: write counting circuitry configured to: in response to the index writing number not being equal to the to-be-written number, adding 1 to the index writing number, wherein the to-be-written number is determined based on the space requested to be reclaimed by the space reclamation request; write enable circuitry configured to: in response to the index write number not being equal to the number to be written and the index to be written being valid data, a write enable signal is generated such that the index to be written is written to the index memory.

In some embodiments, the index memory includes at least two sub-index memories, each configured to store at least one storage unit index, and the storage unit characterized by the at least one storage unit index has one of a set of preset sizes.

In some embodiments, the space management module includes at least two sub-management modules, each sub-management module corresponding to one of the set of preset sizes and configured to manage the storage unit index in the corresponding sub-index storage according to the space management request.

According to another aspect of the present disclosure, there is provided a computing device comprising an apparatus for managing storage space as described according to the previous aspect.

According to yet another aspect of the present disclosure, there is provided a method for managing storage space, comprising: receiving a space management request from an external request source; the method comprises managing storage unit indexes in an index memory according to a space management request, wherein the index memory is configured to store one or more storage unit indexes, and each storage unit index is used for representing one storage unit with a preset size in a storage space.

According to yet another aspect of the present disclosure, there is provided a chip comprising the apparatus for managing storage space described according to the various embodiments of the preceding aspects.

The apparatus for managing storage space provided by the present disclosure may locally store a storage unit index and manage the locally stored storage unit index based on a space management request of an external request source. Since each storage unit index characterizes a storage unit in the storage space of the memory, management of the storage units in the memory can be achieved by managing the storage unit index. Therefore, the allocation and recovery of the storage space in the memory can be efficiently managed by the hardware device based on the request of the request source such as the CPU, the MCU and the like, and the problems of long path, high delay and the like caused by a software mode can be reduced, so that the management efficiency of the storage space can be improved, and the running speed of the whole computing system can be improved. Meanwhile, the resources of the processor, the controller or the microcontroller can be released by means of the independent hardware device for memory management, so that the optimal configuration of the resources is realized, and the overall performance of the computing system is improved. In addition, the device for managing storage space provided by the present disclosure stores the storage unit index in the local index storage completely, and compared with the method of reading and writing the storage unit index on the external storage, the method of the present disclosure can effectively shorten the read-write path of the storage unit index and reduce frequent interaction with the external storage, thereby improving the read-write efficiency, further improving the space management efficiency, and improving the efficiency of the overall computing system.

These and other aspects of the disclosure will be apparent from and elucidated with reference to the embodiments described hereinafter.

Drawings

Further details, features and advantages of the present disclosure are disclosed in the following description of exemplary embodiments, with reference to the following drawings, wherein:

FIG. 1 is a schematic diagram illustrating a memory management architecture in the related art;

FIGS. 2A, 2B, and 2C schematically illustrate example block diagrams of storage space management systems according to some embodiments of the present disclosure;

FIGS. 3A and 3B schematically illustrate a partitioning scheme of storage space according to some embodiments of the present disclosure;

FIG. 4 schematically illustrates an example read-write architecture of an index memory according to some embodiments of the present disclosure;

fig. 5A and 5B schematically illustrate example block diagrams of circuitry in a space allocation module according to some embodiments of the present disclosure;

FIG. 6 schematically illustrates an example block diagram of circuitry in a space reclamation module according to some embodiments of the present disclosure;

FIG. 7 schematically illustrates an example block diagram of a request classification module according to some embodiments of the disclosure;

FIG. 8 schematically illustrates an example block diagram of a computing device according to some embodiments of the disclosure;

Fig. 9 schematically illustrates an example flowchart of a method for managing storage space, according to some embodiments of the disclosure.

Detailed Description

The technical solutions in the embodiments of the present disclosure will be clearly and completely described below with reference to the drawings in the embodiments of the present disclosure. It should be understood that the described embodiments are merely some, but not all embodiments of the present disclosure. Based on the embodiments in this disclosure, all other embodiments that a person of ordinary skill in the art would obtain without making any inventive effort are within the scope of protection of this disclosure.

Fig. 1 schematically illustrates a memory management architecture 100 in the related art. As shown in fig. 1, in the related art, the memory 110 may be directly managed by the processor 120 or the like via the bus 130. For example, when the processor 120 needs to write data into the memory space, the usable space may be determined according to the internal memory space management policy, and then an instruction for writing data into the corresponding memory space is issued, and the instruction may be processed by hardware and sent to the memory 110 via the bus 130, so as to implement data writing. The process of data reading, deleting, etc. may be similarly implemented. However, the applicant has found that performing memory management in this manner has the following drawbacks: firstly, the resources of a processor (or a controller, a microcontroller and the like) are required to be occupied to execute operations such as space allocation, recovery and the like, which is not beneficial to the efficient utilization of the resources; secondly, the allocation and recovery of the memory space are implemented through software, the instruction is required to be processed through hardware, and then the read-write operation is performed in the memory space through a bus, so that the characteristics of long path, high delay, complex structure and the like are achieved; thirdly, the parallel operation of space recovery and space allocation is difficult to realize by managing the memory in a software mode, so that the improvement of the operation efficiency is limited; etc.

Based on the above considerations, the applicant has proposed a new solution for implementing memory management by means of hardware circuits, which helps to solve or alleviate the various problems described above. According to the embodiment of the disclosure, the memory space is not required to be occupied for storing the memory unit index, and the management of the memory unit index in the memory space is not required to be realized by performing read-write operation on the memory space, so that the read-write time is saved, and the occupation of the read-write bandwidth of the memory is reduced.

FIG. 2A schematically illustrates an example block diagram of a storage space management system 200A, according to some embodiments of the disclosure. The storage space management system 200A includes means 210 for managing storage space that may receive a space management request from an external request source 220 and process the received space management request to manage storage space in a memory (not shown). The above memory may be various memories used as a memory, such as a Double Data Rate (DDR) synchronous dynamic random access memory, or the like, or may be other types of memories, for example. By way of example, external request source 220 may be any device that may initiate a space management request, such as a CPU, MCU, etc. Further, although only one external request source is shown in the drawings of the present disclosure, the apparatus 210 provided by embodiments of the present disclosure may be used to receive and process space management requests from a plurality of external request sources according to specific application requirements.

As shown in fig. 2A, the means 210 for managing storage space may include a request source interface 211, an index memory 212, and a space management module 213. Request source interface 211 may be coupled to external request source 220, e.g., via a dedicated line or a common line (e.g., bus), and may be used to enable communication between external request source 220 and device 210, e.g., via a handshake. The request source interface 211 may be configured to receive a space management request from the external request source 220, and may be configured to feed back a management result from the space management module to the external request source 220. The space management request may be a space allocation request or a space reclamation request, and the management result may be, for example, information indicating a storage unit index of the allocated space, a space allocation failure, a space reclamation success, or the like. In this disclosure, a space allocation request may refer to a request to allocate a size of space in memory for use, and a space reclamation request (or space release request) may refer to a request to reclaim (or request release) used space in memory.

Index store 212 may be configured to store one or more storage unit indices, where each storage unit index is used to characterize one of the storage spaces as a storage unit having a preset size. Illustratively, the index memory 212 may include one or more index store queues, which may take the form of, for example, FIFOs (First in first out, first-in-first-out) or other forms of storage structures.

Illustratively, FIG. 3A shows a schematic diagram of a storage space 300. As shown in fig. 3A, the storage space 300 may include a storage area 310. The storage area 310 may be divided into a plurality of storage units having a preset size, and the apparatus 210 may manage storage unit indexes for characterizing the storage units of the preset size, and the preset size may be set according to specific requirements, for example, set to 4 KB, or set to 2 KB, 8 KB, 16 KB, 32 KB, or the like. Illustratively, when request source 220 requests allocation of a portion of space, device 210 may feed back thereto one or more storage unit indices from which request source 220 may then address corresponding storage units in storage space 300; when request source 220 requests reclamation of certain spaces, device 210 may reclaim the corresponding storage unit index for subsequent allocation, i.e., the storage units characterized by the reclaimed storage unit index recover available status and may be reassigned. Optionally, the storage space 300 may also include other storage areas 320 reserved for other uses. For ease of understanding, assuming that the size of the storage area 310 is 8 GB, if it is divided into a plurality of storage units with a granularity of 4 KB, it can be divided into 2097152 storage units in total, thereby requiring 2097152 storage unit indexes in total. If each storage unit index is stored in 4 bytes (bytes), the index memory 212 may be 8 MB in size in the example described above.

In some embodiments, the storage area 310 may be divided into a plurality of storage units, wherein each storage unit has one of a set of preset sizes. The set of preset sizes may be set according to specific needs, for example may be set to include one or more of 8 MB, 2 MB, 512 KB, 256 KB, 128 KB, 64 KB, 16 KB, 4 KB, or may include other preset sizes as well. Illustratively, as shown in fig. 3B, the memory area 310 may be divided into sub-areas 311, 312, etc., each sub-area may be divided into memory cells of different preset sizes, and each sub-area may have different sizes and may be divided into different numbers of memory cells. For ease of understanding, for example, assuming that the total size of storage area 310 is 8 GB, if 4 Gb storage is divided at 8 MB granularity, 2 GB storage is divided at 2 MB granularity, 1 GB storage is divided at 512 KB granularity, 512 MB storage is divided at 256 KB granularity, 256 MB storage is divided at 64 KB granularity, and 256 MB storage is divided at 16 KB granularity, then a total of 512 8 MB storage units, 1024 2 MB storage units, 2048 512 KB storage units, 2048 256 KB storage units, 4096 64 KB storage units, 16384 16 KB storage units may be divided. If a 4 byte (byte) storage unit index is allocated to each storage unit, the storage unit index corresponding to 8 MB storage units is 2 KB, the storage unit index corresponding to 2 MB storage units is 4 KB, the storage unit index corresponding to 512 KB storage units is 8 KB, the storage unit index corresponding to 256 KB storage units is 8 KB, the storage unit index corresponding to 64 KB storage units is 16 KB, and the storage unit index corresponding to 16 KB storage units is 64 KB. Thus, in the example above, the index memory 212 may be 102 KB in size. Further illustratively, in such embodiments, the index memory 212 may further comprise a plurality of sub-index memories, each of which may be used to store only memory cell indices corresponding to a predetermined size. Taking the example described above as an example, there may be 6 sub-index memories storing the storage unit indexes corresponding to the storage units of 8 MB, 2 MB, 512 KB, 256 KB, 64 KB, 16 KB, respectively. Further, in such an embodiment, in order to identify the storage unit indexes corresponding to different preset sizes, an identifier indicating the preset size may be included in each storage unit index. For example, the storage unit index may be divided into an identifier portion, which may be used to store an identifier indicating a preset size, and a unit index portion, which may be used to store an index value of a storage unit having a corresponding preset size. Illustratively, in the example described above having 6 preset sizes of 8 MB, 2 MB, 512 KB, 256 KB, 64 KB, 16 KB and representing the storage unit index in 4 bytes, the preset size may be represented in the upper 3 bits for each storage unit index, for example, 16 KB may be represented in 000, 64 KB in 001, 256 KB in 010, 542 KB in 011, 2 MB in 100, 8 MB in 101, and the remaining 29 bits may represent a specific index value.

The space management module 213 may be configured to manage the storage unit index in the index memory according to the space management request. Illustratively, the space management module 213 may read or write the storage unit index from or to the index memory 212 based on the space management request to complete allocation and reclamation of the corresponding storage units in the memory.

By way of example, the memory space management device 210 may be implemented as various types of hardware circuits, such as formed as an integrated circuit, packaged as a chip structure, etc., so as to be used as desired, such as soldered at respective pins of a circuit board or plugged into respective sockets of a circuit board, etc.

Through the device 210, the storage space of the memory (for example, the internal memory such as the DDR) can be managed in a hardware manner, so that the defect of a software management manner can be reduced, a more convenient management manner can be provided, the space management efficiency is improved, the processing resources of the main control unit such as the CPU or the MCU are saved, the operation efficiency of the whole computing system is further improved, and the resource allocation of the whole computing system is optimized. Meanwhile, by the storage space management device 210, the storage unit index can be stored locally, compared with the storage unit index read-write on the external memory, the read-write path of the storage unit index can be effectively shortened, frequent interaction with the external memory is reduced, so that the read-write efficiency is improved, the occupation of the read-write bandwidth of the memory is reduced or reduced, the space management efficiency is improved, and the overall efficiency of the storage space management system is improved.

For further ease of understanding, taking the spatial partitioning scheme described above with reference to fig. 3A, 3B as an example, it is assumed that there is no local index store 212, and all storage unit indices are stored on external memory. Taking the request relating to management of 2 MB storage space as an example, in the example described above where 8 GB space is all divided into 4 KB storage units, then a total of 512 storage unit indexes need to be read/written in memory; in the example described above where the 8 GB space is divided into six sizes of 8 MB, 2 MB, 512 KB, 256 KB, 64 KB, 16 KB memory cells, then 1 memory cell index corresponding to 2 MB memory cells may be required to be read/written altogether. Such a read/write process occupies on the one hand the read/write bandwidth of the memory and on the other hand requires more time. Although dividing the memory space into a plurality of memory cells of a predetermined size may help to reduce the number of times and time of reading and writing, the problem cannot be completely solved, and the number of times and time of reading and writing may still be high when the number of index of the memory cells involved is large. In contrast, using the apparatus for managing storage space described in the embodiments of the present disclosure, such as the apparatus 210 shown in fig. 2A, the local index memory 212 may store the storage unit index for allocation/reclamation operation, so that frequent access to the memory can be effectively reduced, and the read-write path in the storage unit index management process can be shortened, thereby improving the space management efficiency and the overall performance of the system.

In the present disclosure, space management may include both space allocation, which may be implemented by allocation of storage unit indexes, and space reclamation, which may be implemented by reclamation of storage unit indexes. Further, allocation of the storage unit index may be understood as a process of acquiring the storage unit index from the local index generation module or the memory by the space allocation module and feeding back to the external request source, and reclamation of the storage unit index may be understood as a process of writing the storage unit index corresponding to the space requested to be reclaimed by the space reclamation request from the external request source into the memory by the space reclamation module.

Illustratively, FIG. 2B shows a schematic block diagram of a storage space management system 200B, according to some embodiments of the present disclosure.

As shown in fig. 2B, in some embodiments, the space management request may include a space allocation request and a space reclamation request, and the space management module 213 may include a space allocation module 2131 and a space reclamation module 2132. More specifically, the space allocation module 2131 may be configured to: allocating at least one storage unit index to an external request source according to the size of the space requested to be allocated by the space allocation request; the space reclamation module 2132 may be configured to: one or more storage unit indexes are written to the index memory according to the space requested to be reclaimed by the space reclamation request. Illustratively, the space allocation module 2131 may receive a space allocation request, and based on the size of the space requested by the space allocation request and the preset size of the storage units into which the memory is partitioned, the space allocation module 2131 may determine whether there are currently enough storage unit indices available for allocation and the number of storage unit indices that need to be allocated. Subsequently, the space allocation module 2131 may read a corresponding number of storage unit indexes from the index memory 212 and feed back to the external request source 220. Illustratively, the read process may proceed as shown in FIG. 4, for example, space allocation module 2131 may initiate a request to read a number of storage unit indexes, and upon receipt of the request, index store 212 may pass a corresponding number of storage unit indexes to space allocation module 2131. Similarly, for example, the space reclamation module 2132 may receive a space reclamation request, and based on the space that the space reclamation request requested to reclaim, the space reclamation module 2132 may determine a storage unit index that needs to be reclaimed. Subsequently, space reclamation module 2132 may write these storage unit indices to index store 212 and optionally feed back the information of the successful reclamation to external request source 220. Illustratively, the writing process may proceed as shown in FIG. 4, for example, space reclamation module 2132 may initiate a request to write a storage unit index, and upon receipt of the request, index store 212 may respond to the request to allow the storage unit index from space reclamation module 2132 to be written. By arranging the space allocation module and the space recycling module, the space allocation request and the space recycling request can be allowed to be processed in parallel, so that the space management efficiency is improved.

Fig. 5A schematically illustrates an example block diagram of a circuit 500A in a space allocation module according to some embodiments of this disclosure. As shown in fig. 5A, circuit 500A may include a readout counting circuit 510 and a readout circuit 520. More specifically, the readout counting circuit 510 may be configured to: in response to the index read number not being equal to the number to be allocated, the index read number is increased by 1, wherein the number to be allocated is determined based on the amount of space requested to be allocated by the space allocation request. The readout circuitry 520 may be configured to: in response to the index read number not being equal to the number to be allocated, at least one memory cell index is read from the index memory and the read at least one memory cell index is output. By the circuit 500A, a function of counting the index of the memory cell read out and stopping the reading out when the count reaches the number of indexes requested to be allocated can be realized.

Illustratively, as shown in FIG. 5A, the readout counting circuit 510 may include an adder, a data selector (mux), a register, and a comparator. Specifically, the adder is identified by "+" symbol, one input end of the adder can be connected with the signal 1, and the other input end of the adder can be connected with the output end of the register, so that the adding operation of 1 on the data in the register is realized. The data selector is identified by a "mux" symbol and is shown as a two-out data selector, one input of which is connected to the output of the adder and the other input of which is connected to signal 0, the selection control may be connected to the output of the comparator, whereby the data selector may output the output value of the adder when the two inputs of the comparator are unequal. The register is shown as a D-type flip-flop identified by a "D" symbol, the input of which is connected to the output of the data selector, whereby the register can receive the output value from the adder through the data selector when the two inputs of the comparator are unequal, thereby achieving the effect of recording the accumulated value. The comparator is identified by "=" symbol, and one input terminal thereof receives the number master_req_index_num of the memory cell indexes requested to be allocated (i.e., the aforementioned number to be allocated), and illustratively, the number may be received from the space allocation module 2131, and the other input terminal may be connected to the output terminal of the register, thereby realizing a function of judging whether the value recorded by the register is equal to the number of the memory cell indexes requested to be allocated, i.e., a function of judging whether the accumulated value is equal to the number of the memory cell indexes requested to be allocated. Also by way of example, the readout circuit 520 may include a data selector mux, one input of which may be connected to an index memory, such as the index memory 212 shown in fig. 2A and 2B, the other input of which may be connected to a signal 0, and a selection space terminal of which may be connected to an output of a comparator, i.e., an allocate_done signal shown in the drawing, whereby a function of reading out a memory cell index from the index memory when the accumulated value is not equal to the number of memory cell indexes requested to be allocated may be implemented, and the read out memory cell index may be outputted as output data (i.e., output_data shown in the drawing) and fed back to an external request source.

It should be understood that the circuit diagram shown in fig. 5A is merely illustrative and exemplary, that other circuit structures may be present in an actual circuit, and that the same or similar functions may be implemented by other circuit structures.

Fig. 6 schematically illustrates an example block diagram of a circuit 600 in a space reclamation module according to some embodiments of the disclosure. As shown in fig. 6, the circuit 600 may include a write count circuit 610 and a write enable circuit 620. More specifically, the write count circuit 610 may be configured to: in response to the index writing number not being equal to the to-be-written number, adding 1 to the index writing number, wherein the to-be-written number is determined based on the space requested to be reclaimed by the space reclamation request; the write enable circuit 620 may be configured to: in response to the index write number not being equal to the number to be written and the index to be written being valid data, a write enable signal is generated such that the index to be written is written to the index memory. Counting of written memory cell indices may be accomplished by circuit 600 and stopping writing when the count reaches the number of indices requested to be reclaimed.

Illustratively, as shown in FIG. 6, the readout counting circuit 610 may include an adder, a data selector (mux), a register, and a comparator. Specifically, the adder is identified by "+" symbol, one input end of the adder can be connected with the signal 1, and the other input end of the adder can be connected with the output end of the register, so that the adding operation of 1 on the data in the register is realized. The data selector is identified by a "mux" symbol and is shown as a two-out data selector, one input of which is connected to the output of the adder and the other input of which is connected to signal 0, the selection control may be connected to the output of the comparator, whereby the data selector may output the output value of the adder when the two inputs of the comparator are unequal. The register is shown as a D-type flip-flop identified by a "D" symbol, the input of which is connected to the output of the data selector, whereby the register can receive the output value from the adder through the data selector when the two inputs of the comparator are unequal, thereby achieving the effect of recording the accumulated value. The comparator is identified by "=" symbol, and one input terminal thereof receives the number master_req_index_num of the storage unit indexes requested to be reclaimed (i.e., the aforementioned number to be written), and illustratively, the number may be received from the space reclamation module 2132, and the other input terminal may be connected to the output terminal of the register, thereby realizing a function of judging whether the value recorded by the register is equal to the number of the storage unit indexes requested to be reclaimed, i.e., a function of judging whether the accumulated value is equal to the number of the storage unit indexes requested to be reclaimed. Also illustratively, the write enable circuit 620 may include an inverter and an AND gate. The input of the inverter may be connected to the output of the comparator, i.e. the deallocated done signal shown in the figure, to effect a reverse operation of the signal. One input of the AND gate may be connected to the output of the inverter, and the other input may be connected to a data valid signal, which may be used to indicate that the index to be written is valid data, and may be from an external request source. Thereby, a function of generating the write enable signal wr_en when the accumulated value is not equal to the number of the requested reclaimed memory cell indexes and the index to be written is valid data can be realized. The write enable signal may be passed to an index store, such as index store 212 described previously, so that the index to be written may be written to the index store, such as write_index shown in FIG. 6.

It should be understood that the circuit diagram shown in fig. 6 is merely illustrative and exemplary, that other circuit structures may be present in an actual circuit, and that the same or similar functions may be implemented by other circuit structures.

Returning to fig. 2B, in some embodiments, the space management module 213 may also include an index generation module 2133. The index generation module 2133 may be configured to generate one or more storage unit indexes according to preset rules. Alternatively, the index generation module 2133 may generate all the storage unit indexes at once, or may generate the storage unit indexes in batches. By way of example, the preset rule may include one or more of a start index value, a stop index value, a total number, etc. of the storage unit index, wherein the start index value, the stop index value, the total number, etc. of the storage unit index may be configurable, such as by an associated configuration register, for example. The index generation module 2133 may generate individual storage unit indices by means of an accumulation operation based on the starting index value, or may generate storage unit indices by other means, for example.

In some embodiments, the index generation module 2133 may be configured to: after the device 210 is powered on, a plurality of storage unit indexes are generated according to a preset rule, and the generated plurality of storage unit indexes are written into the index memory 212. Alternatively, after all storage unit index writes are completed, the index generation module 2133 may issue a message indicating that index writes are completed, and subsequently, the device 210 may begin receiving and processing space management requests from the external request source 220. In such an embodiment, the index generation module 2133 may only operate for a short period of time after the device 210 is powered up, such as during an initialization period of the device 210, and then may not be started until the device 210 is powered up next time, and the space allocation module 2131 and the space reclamation module 2132 may interact directly with the index memory 212 to complete the management operations of the storage unit indexes. Illustratively, the space allocation module 2131 may implement the function of reading the storage unit index from the index memory 212 via the circuitry shown in fig. 5A or the like, and the space reclamation module 2132 may implement the function of writing the storage unit index to the index memory 212 via the circuitry shown in fig. 6 or the like.

In some embodiments, the index generation module 2133 may be configured to gradually generate all or part of the storage unit index based on the instructions of the space allocation module 2131. In particular, the space allocation module 2131 may be configured to: in response to the allocated number of storage unit indexes being less than the threshold number, cause the index generation module 2133 to generate at least one storage unit index, wherein the allocated number of storage unit indexes is a cumulative number of storage unit indexes allocated to the external request source 220; reading at least one storage unit index from an index memory in response to a sum of an allocated number of storage unit indexes and a number to be allocated being greater than a threshold number, wherein the number to be allocated is determined based on an amount of space requested to be allocated by a space allocation request; the generated at least one storage unit index and/or the read at least one storage unit index is assigned to an external request source. Alternatively, the threshold number may be a default value or a configurable value, which may be less than or equal to the total number of storage unit indexes, where the total number of storage unit indexes corresponds to the number of storage units having a preset size in the storage space. The allocated number of storage unit indexes may be understood as an accumulated number of storage unit indexes (including the number of storage unit indexes allocated by the respective space allocation modules) allocated to the external request source 220. For example, assuming that m space allocation requests are cumulatively received after the device is powered up and n space allocation requests are successfully allocated, the sum of the numbers of the allocated unit indexes for the n space allocation requests may be regarded as the allocated number of the unit indexes. Compared with the embodiment described in the previous paragraph, the embodiment described in this paragraph helps to increase the initialization speed after the device is powered on, and reduces the time consumed for writing the index set of storage units, thereby helping to increase the overall efficiency of the storage space management system. Illustratively, in such an embodiment, the space allocation module 2131 may implement the function of reading the storage unit index from the index memory 212 via the circuitry shown in fig. 5B or the like, and the space reclamation module 2132 may implement the function of writing the storage unit index to the index memory 212 via the circuitry shown in fig. 6 or the like.

As shown in fig. 5B, the circuit 500B may include a readout counting circuit 510, a readout circuit 520, and a selection circuit 530. The readout counting circuit 510 may be configured to: in response to the index read number not being equal to the number to be allocated, the index read number is incremented by 1. The readout circuitry 520 may be configured to: at least one memory cell index provided by the selection circuit is output in response to the index read number not being equal to the number to be allocated. The selection circuit 530 may be configured to: the index generation module 2133 is caused to generate at least one storage unit index in response to the allocated number of storage unit indexes being less than a threshold number, and to read the at least one storage unit index from the index memory 212 in response to the sum of the allocated number of storage unit indexes and the number to be allocated being greater than the threshold number. By the circuit 500B, a function of counting the read out memory cell indexes, stopping reading out when the count reaches the index number requested to be allocated, and determining whether to read the memory cell indexes from the index memory 212 or from the index generation module 2133 according to the allocated number and the number to be allocated of the memory cell indexes can be realized.

Illustratively, as shown in fig. 5B, the structure of the readout counting circuit 510 is the same as that shown in fig. 5A, and will not be described again here; the structure of the readout circuit 520 is also substantially the same as that shown in fig. 5A, except that: one input of the data selector mux may be connected to the selection circuit 530 instead of the index memory shown in fig. 5A, whereby a function of outputting the selection circuit 530 when the accumulated value is not equal to the number of memory cell indexes requested to be allocated can be realized, and the read memory cell indexes can be outputted as output data (i.e., output_data shown in the drawing) and fed back to an external request source. The selection circuit 530 may include a data selector mux, one input of which may be connected to an index generation module, such as the index generation module 2133, and the other input of which may be connected to an index memory, such as the index memory 212, the selection control of which may have access to a signal from the index generation module, such as the create_index_done signal shown in the figure, which may be used to indicate whether the index generation module has completed generation of a threshold number of memory cell indexes, and, illustratively, if not completed, may be set to 0, such that the data selector outputs data from the index generation module; if so, the signal may be set to 1, causing the data selector to output the data from the index memory. Thus, it is possible to realize a function of determining whether to acquire the storage unit index from the index generating module or to read the storage unit index from the index memory according to whether or not the number of storage unit indexes accumulatively generated by the index generating module reaches the threshold value.

It should be understood that the circuit diagram shown in fig. 5B is merely illustrative and exemplary, other circuit structures may be present in an actual circuit, and that the same or similar functions may be implemented by other circuit structures.

Returning again to fig. 2B, as shown, in some embodiments, the apparatus 210 may further include a request classification module 214. Fig. 7 schematically illustrates an example block diagram of the request classification module 214, according to some embodiments of the disclosure. As shown in fig. 7, the request classification module 214 may be configured to: the space management request is received, stored to the first queue 2141 when the space management request is a space allocation request, and stored to the second queue 2142 when the space management request is a space reclamation request. Thus, the space management requests from the external request source can be classified and stored, so that the space allocation requests and the space reclamation requests can be simultaneously transferred to the later modules, for example, the space allocation module and the space reclamation module, thereby facilitating the parallel processing of the space allocation requests and the space reclamation requests. In addition, the first queue and the second queue can store the received space allocation requests and space reclamation requests, so that when an external request source initiates multiple requests, the back pressure of the external request source can be reduced, and the system efficiency is improved. Alternatively, the first and second queues 2141, 2142 may take the form of a storage structure such as a FIFO. Due to the limited FIFO memory space, a pre-fill threshold may be set for first queue 2141 and second queue 2142. When the number of space allocation requests stored in first queue 2141 reaches a corresponding pre-full threshold (otherwise referred to as a first threshold), first queue 2141 may perform a pre-full back pressure and may no longer receive space allocation requests from external request sources; when the number of space reclamation requests stored in the second queue 2142 reaches a corresponding pre-full threshold (otherwise referred to as a second threshold), the second queue 2142 may perform a pre-full back pressure and may no longer receive space reclamation requests from external request sources. By the backpressure mechanism, the request classification module 214 may be prevented from receiving space allocation requests and/or space reclamation requests that exceed its storage capacity, thereby reducing the probability of processing errors.

As mentioned above, in some embodiments, the storage space of the memory may be divided into storage units having different preset sizes. In such an embodiment, index memory 212 may include at least two sub-index memories, each of which may be configured to store at least one storage unit index, and the storage units characterized by the at least one storage unit index have one of a set of preset sizes. Illustratively, as described in the previous examples, the set of preset sizes may include six preset sizes of 8 MB, 2 MB, 512 KB, 256 KB, 64 KB, 16 KB, and accordingly, in such examples, the index memory 212 may include six sub-index memories for storing the storage unit indices of 8 MB, 2 MB, 512 KB, 256 KB, 64 KB, 16 KB, respectively, alternatively, each sub-index memory may take the form of a FIFO or other form of storage structure. By storing the storage unit indexes with different preset sizes in different sub-index memories, the multi-granularity storage space division scene can be supported, and the storage unit indexes with various preset sizes can be orderly stored in the scene so that the space management module can execute corresponding read-write operation.

Further, in such an embodiment, in order to more conveniently manage the storage unit indexes corresponding to the respective preset sizes, respectively, the space management module may include at least two sub-management modules, each corresponding to one of the preset sizes in the preset size set, and configured to manage the storage unit indexes in the corresponding sub-index memories according to the space management request. The interaction between each sub-management module and the corresponding sub-index store may be similar to the interaction between the space management module and the index store described above, and will not be described again.

For ease of understanding, FIG. 2C schematically illustrates an example block diagram of a storage space management system 200C according to the above-described embodiments of the present disclosure. As shown in fig. 2C, the index memory 212 may include sub-index memories 212-1 to 212-N, which may be integers greater than or equal to 2 and may be equal to the number of preset sizes in the preset size set. Accordingly, the space allocation module 2131 may include sub-allocation modules 2131-1 through 2131-N, the space reclamation module 2132 may include sub-reclamation modules 2132-1 through 2132-N, and operations of and interactions between each sub-allocation module and sub-reclamation module and sub-index memory may be similar to the space allocation module, space reclamation module and index memory described in the various embodiments above and will not be described again herein.

Optionally, the apparatus 210 may further include a spatial counting module 215. The space counting module 215 may be configured to receive the space allocation request and the space reclamation request and record the allocation of the storage unit index according to the amount of space it requests to allocate or reclaim. For example, the space count module 215 may include an index counter that may be configured to: when the space count module 215 receives a space allocation request, it changes in a first direction based on the number of storage unit indexes to which the space allocation request relates; when the space count module 215 receives the space reclamation request, it changes in the second direction based on the number of storage unit indexes to which the space reclamation request relates, wherein the amount of change in the first direction or the second direction corresponds to the number of storage unit indexes allocated or reclaimed. Thus, the allocation of the storage unit indices may be recorded, for example, the number of storage unit indices available for allocation. Illustratively, as shown, to record the number of each preset size storage unit index, the index counters in the space count module 215 may include sub-index counters 2151-1 through 2151-N, each of which may be used to record a change in the number of storage unit indexes of one preset size.

Further exemplary, the space counting module 215 may be configured to: splitting the space management request into one or more sub-allocation requests or one or more sub-reclamation requests, wherein each sub-allocation request or sub-reclamation request corresponds to one of a set of preset sizes. The split one or more sub-allocation requests may be passed to the space allocation module 2131 and processed by the corresponding sub-allocation module; the split one or more sub-reclamation requests may be passed to the space reclamation module 2132 and processed by the corresponding sub-reclamation module. Illustratively, the space counting module 215 may receive a space allocation request and split a space requested to be allocated by the space allocation request based on a preset size in a set of preset sizes, such that the requested allocated space may be split into one or more storage units having the same or different preset sizes, thereby splitting the space allocation request into one or more sub-allocation requests, each of which may be used to request allocation of a storage unit index of one preset size. For example, taking the foregoing example of dividing the storage space with granularity of 8MB, 2MB, 512KB, 256KB, 64KB, and 16KB as an example, it may be determined whether the space requested to be allocated by the space allocation request satisfies the rule of a×8mb+b×2mb+c×512 kb+d×256 kb+e×64kb+f×16kb, where A, B, C, D, E, F is an integer greater than or equal to zero. If satisfied, the space allocation request may be considered to be completely split, and if not, the space allocation request may be considered to be incompletely split. In the case of incomplete splitting, information indicating an error may be reported. In the case of complete splitting, A, B, C, D, E, F represents the required number of storage units for each preset size. Optionally, in splitting the space allocation request, in order to further reduce the number of storage unit indexes to be read and improve the reading efficiency, the number of storage units after splitting may be minimized as much as possible. For example, in the above example, the value of a+b+c+d+e+f may be minimized.

In some embodiments of the present disclosure, a computing device is also provided that may include the apparatus for managing storage space described previously, such as apparatus 210, and the like. Schematically, fig. 8 illustrates an example block diagram of a computing device 800. As shown, computing device 800 may include means 810 for managing storage space, which may perform storage space management functions as described in the various embodiments above. Computing device 800 may also include a processor or controller 820, which may be implemented as a CPU, MCU or similar structure, and may be used to perform various processing or control operations. Computing device 800 may also include memory 830 that may be used to store data such as various program data required by processor or controller 820 in executing an application or data used or generated during execution of an application, and the like. The memory 830 is implemented as a single memory, for example, or may be implemented as a combination of two or more memories. For example, memory 830 may include one or more internal memories, such as DDR memory or SDRAM memory or the like, used as memory. The means 810 for managing storage space, the processor/controller 820 and the memory 830 may be coupled together by a communication line 840 and enable data transfer between each other. Illustratively, communication line 840 may be a bus (such as an AXI bus, etc.) or other type of communication line, or may be a combination thereof.

In some embodiments of the present disclosure, a method for managing storage space is also provided. Illustratively, FIG. 9 shows an example flow chart of a method 900 for managing storage space. As shown in fig. 9, at step 910, a space management request from the external request source may be received; at step 920, a storage unit index in an index memory may be managed according to the space management request, wherein the index memory is configured to store one or more storage unit indexes, each storage unit index being used to characterize one storage unit in the storage space having a preset size.

The method 900 may have the same or similar embodiments as the previously described means for managing storage space and may have the same or similar technical effects. For brevity, the description is omitted here.

In some embodiments of the present disclosure, a chip is also provided, which may include the apparatus for managing storage space described in the various embodiments above. The chip may be connected to a request source such as CPU, GPU, MCU, for example, by a bus or other means, and may manage the storage unit index stored on-chip according to the space management request of the request source based on the various embodiments described above, thereby achieving management of the storage space in the memory. Alternatively, the chip may also be connected to a memory such as a DDR or the like via a bus or other means. And optionally the chip may comprise, in addition to the means for managing memory space described above, circuit modules or means for implementing other functions.

In the description of the present disclosure, the azimuth or positional relationship indicated by the terms "upper", "lower", "left", "right", etc., are based on the azimuth or positional relationship shown in the drawings, and are merely for convenience of describing the present disclosure, not to require that the present disclosure must be constructed and operated in a specific azimuth, and thus should not be construed as limiting the present disclosure.

In the description of the present specification, reference to the term "one embodiment," "another embodiment," etc., means that a particular feature, structure, material, or characteristic described in connection with the embodiment is included in at least one embodiment of the present disclosure. In this specification, schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, the different embodiments or examples described in this specification and the features of the different embodiments or examples may be combined and combined by those skilled in the art without contradiction. In addition, it should be noted that, in this specification, the terms "first" and "second" are used for descriptive purposes only and are not to be construed as indicating or implying relative importance or implicitly indicating the number of technical features indicated.

Furthermore, the terms "first," "second," and the like, are used for descriptive purposes only and are not to be construed as indicating or implying a relative importance or implicitly indicating the number of technical features indicated. Thus, a feature defining "a first" or "a second" may explicitly or implicitly include one or more such feature. In the description of the present disclosure, the meaning of "a plurality" is two or more, unless explicitly defined otherwise.

In the present disclosure, unless explicitly specified and limited otherwise, the terms "mounted," "connected," "secured," and the like are to be construed broadly, and may be, for example, fixedly connected, detachably connected, or integrally formed; the device can be mechanically connected, electrically connected and communicated; can be directly connected or indirectly connected through an intermediate medium, and can be communicated with the inside of two elements or the interaction relationship of the two elements. The specific meaning of the terms in this disclosure will be understood by those of ordinary skill in the art as the case may be.

The foregoing is merely a specific embodiment of the disclosure, but the scope of the disclosure is not limited thereto. Any changes or substitutions that would be readily apparent to one of ordinary skill in the art within the scope of the present disclosure are intended to be encompassed within the scope of the present disclosure. Therefore, the protection scope of the present disclosure shall be subject to the protection scope of the claims.

Claims

1. An apparatus for managing storage space, comprising:

a request source interface connected to an external request source and configured to receive a space management request from the external request source;

an index memory configured to store one or more storage unit indices, wherein each storage unit index is used to characterize a storage unit in the storage space having one of a set of preset sizes;

a space counting module configured to: splitting the space management request into one or more sub-allocation requests or one or more sub-reclamation requests, wherein each sub-allocation request or sub-reclamation request corresponds to one of the preset sizes in the preset size set;

a space management module comprising a space allocation module and a space reclamation module, wherein the space allocation module is configured to: allocating at least one storage unit index to the external request source according to the size of the space requested to be allocated by the one or more sub-allocation requests, the space reclamation module being configured to: and writing one or more storage unit indexes into the index memory according to the space requested to be reclaimed by the one or more sub reclamation requests.

2. The apparatus of claim 1, wherein the index memory comprises an index store queue.

3. The apparatus of claim 1, wherein the space allocation module comprises:

a readout counting circuit configured to: in response to the index read number not being equal to the number to be allocated, adding 1 to the index read number, wherein the number to be allocated is determined based on the amount of space requested to be allocated by the one or more sub-allocation requests; a readout circuit configured to: and in response to the index read number not being equal to the number to be allocated, reading at least one memory cell index from the index memory and outputting the read at least one memory cell index.

4. The apparatus of claim 1, wherein the spatial management module further comprises:

and the index generation module is configured to generate one or more storage unit indexes according to a preset rule.

5. The apparatus of claim 4, wherein the space allocation module is further configured to:

in response to the allocated number of storage unit indexes being less than a threshold number, causing the index generation module to generate at least one storage unit index, wherein the allocated number of storage unit indexes is a cumulative number of storage unit indexes allocated to the external request source;

Reading at least one storage unit index from the index memory in response to a sum of an allocated number of storage unit indexes and a number to be allocated being greater than a threshold number, wherein the number to be allocated is determined based on an amount of space requested to be allocated by the one or more sub-allocation requests;

the generated at least one storage unit index and/or the read at least one storage unit index is allocated to the external request source.

6. The apparatus of claim 5, wherein the space allocation module comprises:

a readout counting circuit configured to: in response to the index read number not being equal to the number to be allocated, adding 1 to the index read number;

a selection circuit configured to: causing the index generation module to generate at least one storage unit index in response to the allocated number of storage unit indexes being less than a threshold number, and reading at least one storage unit index from the index memory in response to the sum of the allocated number of storage unit indexes and the number to be allocated being greater than the threshold number;

a readout circuit configured to: at least one memory cell index provided by the selection circuit is output in response to the index read number not being equal to the number to be allocated.

7. The apparatus of claim 4, wherein the index generation module is further configured to: and after the device is powered on, generating the storage unit indexes according to the preset rule, and writing the storage unit indexes into the index memory.

8. The apparatus of claim 1, wherein the spatial reclamation module comprises:

write counting circuitry configured to: in response to the index write number not being equal to the number to be written, adding 1 to the index write number, wherein the number to be written is determined based on the space requested to be reclaimed by the one or more child reclamation requests;

write enable circuitry configured to: and generating a write enabling signal in response to the index writing quantity being not equal to the quantity to be written and the index to be written being valid data, so that the index to be written is written into the index memory.

9. The apparatus of claim 1, wherein the index memory comprises at least two sub-index memories, each sub-index memory configured to store at least one storage unit index, and the storage unit characterized by the at least one storage unit index has one of the set of preset sizes.

10. The apparatus of claim 9, wherein the space management module comprises at least two sub-management modules, each sub-management module corresponding to one of the set of preset sizes and configured to manage the storage unit index in the respective sub-index memory according to the respective sub-allocation request or sub-reclamation request.

11. A computing device comprising the apparatus for managing storage space of any of claims 1-10.

12. A method for managing storage space, comprising:

receiving a space management request from an external request source;

splitting the space management request into one or more sub-allocation requests or one or more sub-reclamation requests, wherein each sub-allocation request or sub-reclamation request corresponds to one of a set of preset sizes;

allocating at least one storage unit index to the external request source according to the size of the space requested to be allocated by the one or more sub-allocation requests, or writing one or more storage unit indexes to an index memory according to the space requested to be reclaimed by the one or more sub-reclamation requests, wherein the index memory is configured to store one or more storage unit indexes, each storage unit index being used for representing one storage unit with one preset size in the preset size set in the storage space.

13. A chip comprising the apparatus for managing storage space of any one of claims 1 to 10.