US-12619432-B1 - Method and apparatus for obtaining a physical address from a logical address using recursive division

Abstract

A recursive divide operation is performed on a logical address for a predetermined number of iterations. On each iteration of the recursive divide operation, a respective component of a physical address represented by the logical address is derived. The physical address corresponding to the logical address is the constructed from the derived components.

Inventors

• Sean Lee

Assignees

• MARVELL ASIA PTE LTD

Dates

Publication Date

20260505

Application Date

20240422

Claims (20)

1. 1 . An apparatus comprising: memory; and a processor configured to: perform, for a predetermined number of iterations, a recursive divide operation on a logical storage address; derive, on each iteration of the recursive divide operation, a respective component of a physical address represented by the logical storage address; and construct, from the derived respective components, the physical address corresponding to the logical storage address.
2. 2 . The apparatus of claim 1 , wherein to derive, on each iteration, a respective component of the physical address represented by the logical storage address, the processor is further configured to: retrieve, from the memory, a divisor associated with the respective component; and divide at least a portion of the logical storage address by the divisor to obtain a quotient and a remainder, wherein the remainder represents the respective component of the physical address and the quotient represents a portion of the logical storage address to be divided in a next iteration.
3. 3 . The apparatus of claim 2 , wherein the processor is further configured to: store the quotient from a first iteration; and retrieve the stored quotient in a second iteration, wherein the stored quotient is the at least a portion of the logical storage address to be divided in the second iteration.
4. 4 . The apparatus of claim 1 , wherein the processor is further configured to store each derived respective component at a respective location in the memory.
5. 5 . The apparatus of claim 1 , wherein the processor is further configured to receive a recursive divide instruction.
6. 6 . The apparatus of claim 5 , wherein the processor is further configured to extract, from the recursive divide instruction, a number of iterations for which to perform the recursive divide operation, a first pointer identifying a location in a lookup table at which a list of divisors relevant to the recursive divide instruction begins, a second pointer identifying a location in the memory at which a first dividend is stored, and a third pointer identifying a location in the memory at which to begin storing dividends obtained from the recursive divide operation.
7. 7 . The apparatus of claim 1 , wherein the physical address is based on characteristics of a storage device, and wherein the processor is further configured to: determine the characteristics of the storage device; and store, in a lookup table, a plurality of values corresponding to the characteristics of the storage device.
8. 8 . The apparatus of claim 1 , wherein the derived respective component of the physical address represents one of a channel, a die, a page, or a block to which the physical address points.
9. 9 . A method comprising: performing, for a predetermined number of iterations, a recursive divide operation on a logical storage address; deriving, on each iteration of the recursive divide operation, a respective component of a physical address represented by the logical storage address; and constructing, from the derived respective components, the physical address corresponding to the logical storage address.
10. 10 . The method of claim 9 , wherein deriving, on each iteration, a respective component of the physical address represented by the logical storage address further comprises: retrieving, from a memory, a divisor associated with the respective component; and dividing at least a portion of the logical storage address by the divisor to obtain a quotient and a remainder, wherein the remainder represents the respective component of the physical address and the quotient represents a portion of the logical storage address to be divided in a next iteration.
11. 11 . The method of claim 10 , further comprising: storing the quotient from a first iteration; and retrieving the stored quotient in a second iteration, wherein the stored quotient is the at least a portion of the logical storage address to be divided in the second iteration.
12. 12 . The method of claim 9 , further comprising storing each derived respective component at a respective location in a memory.
13. 13 . The method of claim 9 , further comprising receiving a recursive divide instruction.
14. 14 . The method of claim 13 , further comprising extracting, from the recursive divide instruction, a number of iterations for which to perform the recursive divide operation, a first pointer identifying a location in a lookup table at which a list of divisors relevant to the recursive divide instruction begins, a second pointer identifying a location in a memory at which a first dividend is stored, and a third pointer identifying a location in the memory at which to begin storing dividends obtained from the recursive divide operation.
15. 15 . The method of claim 9 , wherein the physical address is based on characteristics of a storage device, the method further comprising: determining the characteristics of the storage device; and storing, in a lookup table, a plurality of values corresponding to the characteristics of the storage device.
16. 16 . The method of claim 9 , wherein deriving the respective component of the physical address comprises deriving one of a channel, a die, a page, or a block to which the physical address points.
17. 17 . A non-transitory computer-readable medium having non-transitory computer-readable instructions encoded thereon for execution by a processor, the non-transitory computer-readable instructions comprising: an instruction to perform, for a predetermined number of iterations, a recursive divide operation on a logical storage address; an instruction to derive, on each iteration of the recursive divide operation, a respective component of a physical address represented by the logical storage address; and an instruction to construct, from the derived respective components, the physical address corresponding to the logical storage address.
18. 18 . The non-transitory computer-readable medium of claim 17 , wherein the instruction to derive, on each iteration, a respective component of the physical address represented by the logical storage address further comprises: an instruction to retrieve, from a memory, a divisor associated with the respective component; and an instruction to divide at least a portion of the logical storage address by the divisor to obtain a quotient and a remainder, wherein the remainder represents the respective component of the physical address and the quotient represents a portion of the logical storage address to be divided in a next iteration.
19. 19 . The non-transitory computer-readable medium of claim 18 , wherein the non-transitory computer-readable instructions that are encoded further comprise: an instruction to store the quotient from a first iteration; and an instruction to retrieve the stored quotient in a second iteration, wherein the stored quotient is the at least a portion of the logical storage address to be divided in the second iteration.
20. 20 . The non-transitory computer-readable medium of claim 17 , wherein the non-transitory computer-readable instructions that are encoded further comprise an instruction to store each derived respective component at a respective location in a memory.

Description

CROSS REFERENCE TO RELATED APPLICATION This disclosure claims the benefit of commonly-assigned U.S. Provisional Patent Application No. 63/462,811, filed Apr. 28, 2023, which is hereby incorporated by reference herein in its entirety. FIELD OF USE This disclosure relates to architectures for a Fast Path Programmable Accelerator (FPA) and obtaining a physical memory address from a logical memory address. BACKGROUND The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the inventors hereof, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted to be prior art against the subject matter of the present disclosure. Many computing and electronic devices include non-volatile memory for storing software, applications, or data of the device. Additionally, most users stream data or access services with their devices, such as multimedia content or social media applications, over data networks from various locations or on the move. With users' ever-increasing demand for data and services, storage providers have scaled up capacity and performance of storage drives to support the data access associated with these activities of users and other data storage clients. Typically, a storage drive of a device includes storage media to which data of the device is written and read from. To do so, the device may issue data access requests to the storage drive, which in turn writes the data to or reads the data from the storage media as specified by each request. Thus, storage drive performance generally depends on a rate at which the storage drive is able to complete the data access requests of the device or the storage client. Generally, hardware of a storage drive is designed to process an average flow of data access requests as quickly as possible. Access patterns of the storage media, however, can vary over a wide array of usage patterns. As such, the hardware of conventional storage drives may not be optimized for access request traffic patterns or flows associated with different applications, user types, multitasking, storage network topologies, and so forth. For example, a large volume of one type of access request may overload the storage drive hardware and create a bottleneck in request processing that slows processing of all other access requests received by the storage drive. Accordingly, when storage drives are deployed with a static hardware configuration, overall storage drive performance is often less than optimal because the storage drive is unable to efficiently handle different types of access request traffic patterns. In various aspects, processing units of the FPA architecture may manipulate or process any suitable data. In some cases, the FPA architecture enables the access, manipulation, or processing of data in fewer clock or instructions cycles, which may enable more efficient data processing. SUMMARY Methods and apparatus are described herein for obtaining a physical address from a logical address using recursive division. A recursive divide operation is performed on a logical address for a predetermined number of iterations. On each iteration of the recursive divide operation, a respective component of a physical address represented by the logical address is derived. The physical address corresponding to the logical address is the constructed from the derived components. In some implementations, to derive a respective component of the physical address, a divisor associated with the respective component may be retrieved from memory. At least a portion of the logical address is then divided by the divisor to obtain a quotient and a remainder. The remainder represents the respective component of the physical address and the quotient represents a portion of the logical address to be divided in the next iteration of the recursive division operation. In some implementations, the quotient from a first iteration is stored. During a second iteration, the stored quotient may be retrieved as the at least a portion of the logical address to be divided in the second iteration. In some implementations, each derived component is stored at a respective location in a memory. In some implementations, a recursive divide instruction may be received. The instruction may include information to be used in executing the instructions. This information may include a number of iterations for which to perform the recursive division, a first pointer identifying a location in a lookup table at which a list of divisors relevant to the instruction begins, a second pointer identifying a location in memory at which a first dividend is stored, and/or third pointer identifying a location in memory at which to begin storing dividends (i.e., quotients to be used in later iterations) obtained from the recursive divisi