Patent ID: 12242387

DETAILED DESCRIPTION

Hereinafter, example embodiments will be described in more detail with reference to the accompanying drawings, in which like reference numbers refer to like elements throughout. The present disclosure, however, may be embodied in various different forms, and should not be construed as being limited to only the illustrated embodiments herein. Rather, these embodiments are provided as examples so that this disclosure will be thorough and complete, and will fully convey the aspects and features of the present disclosure to those skilled in the art. Accordingly, processes, elements, and techniques that are not necessary to those having ordinary skill in the art for a complete understanding of the aspects and features of the present disclosure may not be described. Unless otherwise noted, like reference numerals denote like elements throughout the attached drawings and the written description, and thus, descriptions thereof may not be repeated. Further, in the drawings, the relative sizes of elements, layers, and regions may be exaggerated and/or simplified for clarity.

A computational storage device (for example, a solid state drive (SSD) with an embedded processor or Field Programmable Gate Array (FPGA)), may perform computations locally and send results of the computations to a host device. Computations performed by the storage device may include, for example, Sparse Length Sum (SLS) operations of a Deep Learning Recommendation Model (DLRM) using multiple vectors. Other computations may include identifying records in a table stored in the storage device, performing aggregation operations using the records, and transmitting results of the aggregation operations to the host.

The host may receive the computation results through a device driver, which may in turn pass the results to an application running on the host. Typically, in order for the application to utilize the results, the results are placed in cache memory. Direct cache access mechanisms that allow direct access to the cache memory may be used to store computation results output by the storage device, directly in cache memory instead of a main memory such as a dynamic random access memory (DRAM). For example, CDMA may allow data to be stored directly into a level 2 (L2) cache, while DDIO may allow data to be stored directly in a last level cache (LLC). Storing data directly in the cache memory may help reduce data access latency that is typical with DRAM accesses, and may help increase throughput for the storage device.

A drawback of using a direct cache access mechanism to store data directly into the cache memory is the lack of control of use of the cache memory to store data. Such control may be desirable, for example, as cache memory space is limited, and there may be other processing cores competing for the same memory space. If the cache memory is filled with data used by one of the cores, the remaining cores may be forced to access the DRAM, negatively affecting performance of the cores.

In general terms, the various embodiments of the present disclosure are directed to systems and methods for managing utilization of the cache memory via a circular or ring data structure referred to as a ring buffer. The ring buffer is a circular in structure because when a pointer accesses a last virtual address of the buffer, the pointer wraps back to the beginning of the buffer to access a first virtual address.

The ring buffer may control and limit the use of cache memory space. In this regard, each entry in the ring buffer may identify a virtual address of a page in a virtual address space. The virtual address is translated into a physical address that identifies a cache line of the cache memory that is used to store data associated with the virtual address. The larger the ring buffer, the bigger the amount of cache memory used.

In one embodiment, a buffer manager is aware of the cache memory structure, including cache memory size, placement policy used by the cache memory, number of processors that use the cache memory, and/or the like. The buffer manager may use this knowledge to set the buffer size. In one embodiment, the buffer manager monitors a number of items in the buffer, and periodically adjusts the buffer size accordingly, optimizing use of the cache memory.

In one embodiment, the ring buffer follows a producer-consumer model where the storage device is the producer and the host is the consumer. In this regard, the storage device/producer generates data after local computation, and the host/consumer consumes the data generated by the storage device. A tail pointer of the ring buffer determines a location/entry/address of the ring buffer where the data is to be written into/produced. A head pointer of the ring buffer determines a location of the ring buffer where the data is to be retrieved/consumed. The tail pointer advances as new data is produced by the storage device, and points to a next available location in the buffer for writing data. The head pointer advances as the stored data is consumed by the host, and points to next data in the buffer to be consumed. The producing and consuming of data may be in response to requests from an application in the host.

Updates to the head and tail pointers may or may not be immediately available to the host and storage devices depending on whether cache coherency is supported. In an embodiment where the ring buffer resides in a shared memory space of the host and the storage device, cache coherency may be supported. In this case, both the storage device and the host device have access to the same ring buffer in the shared memory space. Updates to the tail and head pointers, as data is input and removed from the ring buffer, may be available to both the host and the storage device at substantially the same time.

In an embodiment where the ring buffer in the host is not shared with the storage device, cache coherency may not be supported. In case, the storage device maintains a copy of the host ring buffer in its own memory space. As the host consumes data from the host ring buffer and updates the head pointer, a message is sent to the storage device to update the copy of the head pointer in the shadow ring buffer. Similarly, as the storage device produces data for the shadow ring buffer and updates the tail pointer, a message is sent to the host to update the copy of the tail pointer of the host ring buffer.

In one embodiment, regardless of whether a cache coherent or cache non-coherent protocol is used, the ring buffer(s) adhere to an eventual consistency model. In this regard, although the update to the head pointer may not be immediately available to the storage device, or the update to the tail pointer may not be immediately available to the host, the updates eventually become available. Until then, the host relies on a prior value of the head pointer to decide whether there are any entries in the buffer to consume, and the storage device relies on a prior value of the tail pointer to decide whether there is room in the buffer to produce more data. Relying on prior pointer values may help avoid buffer overruns.

FIG.1is a block diagram of a computer system configured for memory utilization management according to one embodiment. The system may include a host computing device (“host”)100coupled to a computational storage device (“storage device”)102over a wired or wireless storage interface104including Ethernet, fiber channel, and/or other storage interface. The host100may transfer and receive data to and from the storage device102over the storage interface104, using a storage interface protocol. The storage interface protocol may be, for example, a non-volatile memory express (NVMe) protocol or any other like protocol.

The storage device102may be a solid state drive (SSD) with an embedded processor120such as a field programmable gate array (FPGA), an SSD controller, and/or a discrete co-processor. In some embodiments, the embedded processor may be a graphics processing unit (GPU), tensor processing unit (TPU), and/or another application-specific integrated circuit ASIC. The embedded processor may be configured to perform various types of computations such as, for example, a Sparse Length Sum (SLS) operation of a Deep Learning Recommendation Model (DLRM) using multiple vectors. Other computations may include identifying records in a table stored in the storage device102, performing aggregation operations using the records, and transmitting results of the aggregation operations to the host100.

The storage device102may further include a non-volatile memory (NVM) media122for storing data provided by the host100. The NVM media122may include one or more types of non-volatile memory such as, for example, flash memory.

In one embodiment, the host100includes one or more central processing unit (CPU) cores106(also simply referred to as “processors”) configured to execute computer program instructions and process data stored in a cache memory108(also simply referred to as “memory” or “cache”). The cache memory108may be dedicated to one of the CPU cores106, or shared by various ones of the CPU cores.

The cache memory108may include, for example, a level one cache (L1) coupled to level two cache (L2) coupled to a last level cache (LLC). The LLC cache may in turn be coupled to a memory controller109which in turn is coupled to a main memory110. The main memory110may include, for example, a dynamic random access memory (DRAM) storing computer program instructions and/or data (collectively referenced as data) generated by the storage device102. In order for an application of the host100to use data generated by the storage device102, the data may be loaded into the cache memory108, and the application may consume the data directly from the cache memory. If the data to be consumed is not already in the cache, the application may need to query other memory devices in the memory hierarchy to find the data. For example, if the data that is sought is not in the L1 cache, the application may query the L2 cache, and if not in the L2 cache, query the LLC cache, and if not in the LLC cache, query the DRAM.

In one embodiment, the data produced by the storage device102is stored directly in the cache memory108(e.g. L2 cache or LLC cache), bypassing the main memory110. A direct cache access mechanism such as DDIO or CDMA may be used to write data directly into the cache. Use of a direct cache access mechanism may help avoid data access latency that is typical with DRAM accesses.

Because the cache memory108is a valuable resource, it may be desirable to manage use of the cache to avoid the storage device102from monopolizing the cache or polluting the cache with too much data. In one embodiment, a circular/ring data structure (hereinafter referred to as a ring buffer)112astored in buffer memory is used to manage and/or limit use of the cache space. In one embodiment, a buffer management system114generates the ring buffer112awith a default size. The buffer management system114may create a separate ring buffer112aper storage device102, per CPU core106, and/or the like.

In one embodiment, the ring buffer112acomprises an array of contiguous virtual memory addresses of a given size. The virtual memory addresses may be translated to a physical memory address of the cache via a translation lookaside buffer (TLB)116. In one example, if an address of a page in the virtual address space is accessed by an application in the host100, the virtual address is translated into a physical address, and a cache line of the cache memory108that contains that address is allocated in the cache memory with a memory identifier (also referred to as a tag).

In one embodiment, the size of the ring buffer112ais set so as to optimize use of the cache memory108. In this regard, the size of the ring buffer is set based on the structure of the cache memory108, including the cache size, associativity/placement policy of the cache, number of ring buffers available for the cache, cache line size, and/or the like.

In one embodiment, the buffer management system114monitors use of the ring buffer112aand adjusts the size of the buffer to optimize use of the cache memory108. A trigger event may invoke the buffer management system114to reevaluate the size of the ring buffer112a. The trigger event may be, for example, passage of an amount of time, a certain number of traversals around the ring buffer, and/or the like. In response to the trigger event, the buffer management system114may apply one or more rules for shrinking, expanding, or leaving the buffer size intact. The rule may be, for example, that if the buffer consistently uses only a portion of its total size to hold data before the data is consumed, the size of the buffer may be shrunk based on the amount of the buffer that is unused. This may allow more, for example, a more efficient use of the cache memory110by allowing, for example, other CPU cores to use the unused portions.

In one embodiment, the ring buffer112ais designed for a producer-consumer model where the storage device102is the producer, and the host100is the consumer. In this regard, the ring buffer112amay include a head pointer that indicates the location in the buffer of the oldest data item that is to be consumed next, and a tail pointer of a next available location in the buffer to be written into. The host may100update the head pointer as it consumes data from the buffer, and the storage device102may update the tail pointer as it produces and writes data into the buffer.

In one embodiment, the ring buffer112aadheres to a cache coherency protocol that allows coherent sharing of the buffer by the host100and the storage device102. An example cache coherency protocol is a Compute Express Link (CXL).cache protocol. When the ring buffer112aadheres to a cache coherency protocol, a single copy of the ring buffer112ais maintained in a shared memory space. As updates are made to the ring buffer112aby either the host100or the storage device102, the updates are substantially immediately available to both parties.

In one embodiment, the ring buffer112aadheres to a non-cache-coherency protocol. When the ring buffer112ais not cache coherent, the storage device102may have no access to the ring buffer112ain the host100. According to this embodiment, the storage device102maintains a separate copy of the ring buffer112areferred to as a shadow ring buffer112bin an internal memory of the storage device. In one embodiment, the storage device102updates the tail pointer of the shadow ring buffer112bas data is produced, and transmits metadata and the produced data to the host100. The metadata may include, for example, the new position of the tail pointer. The tail pointer of the ring buffer112ais eventually updated based on the received metadata. Similarly, the host100updates the head pointer of the ring buffer112aas data is consumed, and transmits metadata to the storage device102to update the shadow ring buffer112b. The metadata may include, for example, the new position of the head pointer. The head pointer of the shadow ring buffer112bis eventually updated based on the received metadata.

In one embodiment, an eventual consistency model is employed for synchronizing the ring buffer112aand shadow ring buffer112b. Use of eventual consistency may help avoid express locking mechanisms to update the buffers. With eventual consistency, updates from a transmitting party to a receiving party (e.g. from the host100to the storage device102) may not be immediately available given that there may be a delay as updates are received and processed. In this regard, the storage device102may think that the shadow ring buffer112bis more full than it actually is because the head value of the shadow ring buffer112bis not immediately updated when the host100consumes and updates the head pointer in the ring buffer112a. The host100may think that there is less data in the ring buffer112athan there actually is because the tail value of the ring buffer112ais not immediately updated when the storage device102produces data and updates the tail pointer of the shadow ring buffer112b. The updates, however, become eventually visible to the receiving party. Until then, prior pointer values are relied upon, helping avoid buffer overruns.

FIG.2is a more detailed block diagram of the ring buffer112aand the cache memory108according to one embodiment. In one embodiment, the ring buffer112aincludes a range of contiguous virtual memory addresses200, a tail pointer202, and a head pointer204. As the storage device102writes data into the ring buffer112a, the tail pointer202is incremented to indicate the production of the entry. As the host100reads the data from the ring buffer112a, the head pointer204is incremented to indicate the consumption of the entry. By evaluating the distance between the head pointer204and the tail pointer202, the storage device102and the host100can determine fullness of the buffer.

In one embodiment, the virtual memory addresses200are mapped to physical addresses206of the cache memory108. The virtual memory addresses200may be in a contiguous virtual address space, while the physical pages may or may not be in a contiguous physical address space. For example, the physical addresses may be contiguous for addresses of a page207a,207bin the virtual address space.

In one embodiment, the cache memory108is configured as a set-associative cache, where the cache is divided into N sets208a, and each set can fit M blocks of data (referred to as a cache line)210a. For example, a 16-way associative cache can fit 16 cache lines210aper set208a. The blocks of a page in the virtual address space are stored in contiguous sets208ain one of the various cache lines. For example, in a 16-way associative cache, if a cache line is 64 bytes, and a page in the virtual address space is 4 KB, the page addresses 64 64-byte blocks of data that may be stored in 64 contiguous sets, with the blocks being stored in one of the 16 cache lines of the set.

In one embodiment, the physical address that is mapped to a virtual address includes a set value and a tag value. The set value identifies one of the sets208aof the cache memory associated with the physical address, and the tag value identifies one of the cache lines within the set (e.g. cache line212).

In one embodiment, the ring buffer112ais assigned a default buffer size with a default number of slots corresponding to the virtual addresses200. The default buffer size may be selected, for example, by a system administrator. Once the ring buffer112ais created with the buffer size, the buffer management system114may monitor (e.g. periodically) the maximum number of items in the buffer, and adjust the buffer size if the maximum number of items is less than the allocated buffer size. In one embodiment, a minimum unit of adjustment is the cache line size (e.g. 64 bytes).

In one embodiment, the size of the ring buffer112ais calculated as follows:
Floor(cache size/set size/cache line size/number of buffers)*cache line size

For example, assuming a 1 MB, 16 set associative cache (e.g. cache size is 1 MB, and the set size is 16), where the cache line size is 64 B and four ring buffers are contemplated, a possible size of one of the ring buffers may be: (1024*1024/16/64/4)*64=16 KB (256 slots*64 B).

FIG.3is a logic diagram for addressing the cache memory108according to one embodiment. Data300is stored to and retrieved from locations of the cache memory108using a physical memory address302. In one embodiment, the physical memory address302is determined based on the virtual address of a slot of the ring buffer112athat is mapped to the physical memory address302. The physical memory address302includes “set” bits304that identify one of the sets208bof the cache memory108, and “tag” bits306athat identify one of the cache lines210bin the identified set. In one embodiment, the tag bits306aare stored in the cache line210bas stored tag bits306b, along with the data302.

When an application makes a request for a particular memory location, the set bits304of the requested memory location are used to identify the set208bin the cache108. The tag bits306aof the requested memory location may then be compared against the stored tag bits306bin the identified set, for determining whether the requested memory location is in the cache. If so, the data302stored in the identified cache line may be retrieved.

FIG.4is layout diagram of a ring buffer400a(similar to ring buffer112a) and a shadow ring buffer400b(similar to shadow ring buffer112b) that are managed using eventual consistency according to one embodiment. The host100creates the ring buffer400ain a virtual address space with a head pointer402, tail pointer copy404, buffer size406, and buffer entries408. The storage device102creates the shadow ring buffer400bbased on the ring buffer400a. The shadow ring buffer400bincludes a tail pointer410, head pointer copy412, buffer size414, and buffer entries416.

The host100consumes the buffer entries408and updates the head pointer402from a first head pointer location422to a second head pointer location424. In one embodiment, the buffer management system114transmits metadata of the updated head pointer402to the storage device102for updating the head pointer copy412. The updated head pointer402may be sent to the storage device using a coherent or non-coherent mechanism.

The storage device102produces buffer entries416and updates the tail pointer410from a first tail pointer location418to a second tail pointer location420. In one embodiment, the buffer management system114transmits the produced data to the host100along with metadata of the updated tail pointer410using a coherent or non-coherent mechanism. In one embodiment, there is a gap from the time the tail pointer410is updated to when the tail pointer copy404is updated. Until the host100updates the tail pointer copy404, the host relies a previous tail location426instead of the updated tail location428. Thus, the host100may think that the ring buffer400ahas fewer entries than it actually has. In one embodiment, if the head pointer402equals the tail pointer copy404, the host100determines that the ring buffer400ais empty.

In regards to updating the head pointer, there is a gap from the time the head pointer402is updated to when the head pointer copy412is updated. Until the storage device102updates the head pointer copy412, the storage device relies on a previous head location430instead of an updated head location432. Thus, the storage device may think that the shadow ring buffer400bis fuller than it actually is. In one embodiment, in order to distinguish between empty and full situations, if a next value of the tail pointer410equals the head pointer copy412, the storage device102determines that the shadow ring buffer400bis full.

FIG.5is a flow diagram of a process for managing utilization of the cache memory108according to one embodiment. The process starts, and in act500, the ring buffer112a(e.g. a first data structure) is generated, for example, by the buffer management system114. The ring buffer112amay be generated using a preset default size.

In act502, data is produced, for example, by the storage device102. For example, the data may be results of computations performed by the storage device for use by the CPU core106for further processing.

In one embodiment, the storage device102identifies a first virtual address associated with an available slot in the ring buffer112afor storing the data. The data may be stored in chunks/blocks that correspond to the size of a cache line (e.g. 64B). In this regard, the storage device102identifies, in act504, from the ring buffer112a(in the event of a coherent cache memory108) or shadow ring buffer112b(in the event of a non-coherent cache memory108), a value of the tail pointer202that identifies a next available slot in the buffer where the data is to be written into. The ring buffer112amay be deemed full with no available slots, if a next value of the tail pointer202(e.g. current tail pointer+1) equals the head pointer204.

Assuming that the ring buffer112ais not full, the host100invokes the TLB116to map the virtual address200identified by the tail pointer202to a physical address in act506. The physical address includes a set value identifying one of the sets208ain the cache108, and a tag value identifying a cache line210within the identified set.

In act508, the data is stored in the identified cache line210along with the tag value. For example, the storage device102may store the data in the cache line210using a direct cache access mechanism.

In act510, the ring buffer is updated (e.g. by the storage device102) by advancing a location of the tail pointer202to point to a next slot of the ring buffer. When a last slot of the ring buffer is reached, the tail pointer wraps around to a beginning slot.

FIG.6is a flow diagram of a process for consuming entries from the ring buffer112aaccording to one embodiment. The process starts, and in act600, the CPU core106identifies a virtual address of a slot in the ring buffer112athat is pointed by the head pointer204.

In act602, the virtual address is mapped to a physical address via the TLB116. The physical address identifies the set208a, and cache line210within the set, that is to be accessed.

In act604, the requested cache line is identified based on a comparison of the tag bits306ain the requested physical address, and the stored tag bits306bin the various cache lines210bwithin the set.

In act606, the data stored in association with the matched tag bits is retrieved from the cache memory108.

In act608, the ring buffer112ais updated by advancing a location of the head pointer204to point to a next slot of the ring buffer.

FIG.7is a flow diagram of a process for dynamically adjusting a size of the ring buffer112aaccording to one embodiment. In act700, the use of the ring buffer112ais monitored, for example, by the buffer management system114. For example, the buffer management system114may periodically monitor the distance between the head pointer204and the tail pointer202for determining maximum fullness/utilization of the buffer at a given time.

In act702, a determination is made as to whether a trigger condition is detected for recomputing the size of the ring buffer. The trigger condition may be, for example, passage of a certain amount of time, a certain number of traversals around the ringer buffer112a, and/or the like.

If a trigger condition is detected, the buffer management system114re-calculates, in act704, the size of the ring buffer112a. For example, if maximum usage of the ring buffer at a given time is only 50% of the allotted size, the buffer management system114may shrink the size of the ring buffer112aby half (e.g. reduce the number of slots of the ring buffer112a, and associated virtual addresses, by half).

In act706, the size of the ring buffer112ais dynamically adjusted based on the recalculated size.

In some embodiments, the systems and methods for managing memory utilization discussed above, are implemented in one or more processors. The term processor may refer to one or more processors and/or one or more processing cores. The one or more processors may be hosted in a single device or distributed over multiple devices (e.g. over a cloud system). A processor may include, for example, application specific integrated circuits (ASICs), general purpose or special purpose central processing units (CPUs), digital signal processors (DSPs), graphics processing units (GPUs), and programmable logic devices such as field programmable gate arrays (FPGAs). In a processor, as used herein, each function is performed either by hardware configured, i.e., hard-wired, to perform that function, or by more general-purpose hardware, such as a CPU, configured to execute instructions stored in a non-transitory storage medium (e.g. memory). A processor may be fabricated on a single printed circuit board (PCB) or distributed over several interconnected PCBs. A processor may contain other processing circuits; for example, a processing circuit may include two processing circuits, an FPGA and a CPU, interconnected on a PCB.

It will be understood that, although the terms “first”, “second”, “third”, etc., may be used herein to describe various elements, components, regions, layers and/or sections, these elements, components, regions, layers and/or sections should not be limited by these terms. These terms are only used to distinguish one element, component, region, layer or section from another element, component, region, layer or section. Thus, a first element, component, region, layer or section discussed herein could be termed a second element, component, region, layer or section, without departing from the spirit and scope of the inventive concept.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the inventive concept. Also, unless explicitly stated, the embodiments described herein are not mutually exclusive. Aspects of the embodiments described herein may be combined in some implementations.

With respect to the processes described with respect to the flow diagrams ofFIGS.5-7, the sequence of steps of these processes are not fixed, but can be modified, changed in order, performed differently, performed sequentially, concurrently, or simultaneously, or altered into any desired sequence, as recognized by a person of skill in the art. The steps may be executed based on computer instructions stored in the non-transitory storage medium (e.g. random access memory) (also referred to as second memory).

As used herein, the terms “substantially,” “about,” and similar terms are used as terms of approximation and not as terms of degree, and are intended to account for the inherent deviations in measured or calculated values that would be recognized by those of ordinary skill in the art.

As used herein, the singular forms “a” and “an” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises” and/or “comprising”, when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items. Expressions such as “at least one of,” when preceding a list of elements, modify the entire list of elements and do not modify the individual elements of the list. Further, the use of “may” when describing embodiments of the inventive concept refers to “one or more embodiments of the present disclosure”. Also, the term “exemplary” is intended to refer to an example or illustration. As used herein, the terms “use,” “using,” and “used” may be considered synonymous with the terms “utilize,” “utilizing,” and “utilized,” respectively.

It will be understood that when an element or layer is referred to as being “on”, “connected to”, “coupled to”, or “adjacent to” another element or layer, it may be directly on, connected to, coupled to, or adjacent to the other element or layer, or one or more intervening elements or layers may be present. In contrast, when an element or layer is referred to as being “directly on”, “directly connected to”, “directly coupled to”, or “immediately adjacent to” another element or layer, there are no intervening elements or layers present.

Although exemplary embodiments of systems and methods for managing memory utilization have been specifically described and illustrated herein, many modifications and variations will be apparent to those skilled in the art. Accordingly, it is to be understood that systems and methods for managing memory utilization constructed according to principles of this disclosure may be embodied other than as specifically described herein. The disclosure is also defined in the following claims, and equivalents thereof.