Write buffer design for high-latency memories

A memory system includes a write buffer, a main memory having a higher latency than the write buffer, and a memory controller. In response to a write request indicating first data for storing at a write address in the main memory, the memory controller adds a new write entry in the write buffer, where the new write entry includes the write address and the first data, and updates a pointer of a previous write entry in the write buffer to point to the new write entry. In response to a write-back instruction, the memory controller traverses a plurality of write entries stored in the write buffer, and writes into the main memory second data of the previous write entry and the first data of the new write entry.

TECHNICAL FIELD

This disclosure relates to the field of memory and, in particular, to buffering of high-latency memory in a computing system.

BACKGROUND

Many modern computer systems utilize non-volatile memory (NVM) for data storage. NVM retains its contents even when power is not being supplied to the NVM, and can thus retain its contents through a power-cycle of the computer system. One common type of NVM technology is flash memory.

Some newer computing systems utilize NVM as random-access memory (RAM); however, frequent writes to NVM can cause wear-out and eventual failure of the NVM. In addition, read or write accesses to NVM typically have higher latency than accesses to volatile memory types.

DETAILED DESCRIPTION

The following description sets forth numerous specific details such as examples of specific systems, components, methods, and so forth, in order to provide a good understanding of the embodiments. It will be apparent to one skilled in the art, however, that at least some embodiments may be practiced without these specific details. In other instances, well-known components or methods are not described in detail or are presented in a simple block diagram format in order to avoid unnecessarily obscuring the embodiments. Thus, the specific details set forth are merely exemplary. Particular implementations may vary from these exemplary details and still be contemplated to be within the scope of the embodiments.

Non-volatile memories are likely to scale further and provide higher capacity than existing dynamic random access memory (DRAM) technologies, but have higher read and significantly higher write latency. To reduce performance impact and wear-out effects due to writes, a write buffering scheme that relies on a hash table and a linked list may be implemented for buffering write accesses to NVM memories. In one embodiment, such a write buffer can also provide cache-like behavior. In contrast with a cache, however, the write buffer is simpler and does not need a separate cache tag array. The write buffer could be implemented in hardware, software or firmware.

FIG. 1illustrates an embodiment of a computing system100which may implement a write buffer for buffering writes to a NVM, as described above. In general, the computing system100may be embodied as any of a number of different types of devices, including but not limited to a laptop or desktop computer, mobile phone, server, etc. The computing system100includes a number of components102-108that can communicate with each other through a bus101or other form of interconnect. In computing system100, each of the components102-108is capable of communicating with any of the other components102-108either directly through the bus101, or via one or more of the other components102-108. The components101-108in computing system100are contained within a single physical casing, such as a laptop or desktop chassis, or a mobile phone casing. In alternative embodiments, some of the components of computing system100may be embodied as peripheral devices such that the entire computing system100does not reside within a single physical casing.

The computing system100also includes user interface devices for receiving information from or providing information to a user. Specifically, the computing system100includes an input device102, such as a keyboard, mouse, touch-screen, or other device for receiving information from the user. The computing system100displays information to the user via a display105, such as a monitor, light-emitting diode (LED) display, liquid crystal display, or other output device.

Computing system100additionally includes a network adapter107for transmitting and receiving data over a wired or wireless network. Computing system100also includes one or more peripheral devices108. The peripheral devices108may include mass storage devices, location detection devices, sensors, input devices, or other types of devices that can be used by the computing system100.

Computing system100includes a processor104that is configured to receive and execute instructions106athat are stored in the memory subsystem106. In alternative embodiments, the processor104can be any processing element, including but not limited to a central processing unit (CPU), a graphics processing unit (GPU), an accelerated processing unit (APU), a field programmable gate array (FPGA), a digital signal processor (DSP), or any other application-specific integrated circuit (ASIC).

Memory subsystem106includes memory devices used by the computing system100, such as random-access memory (RAM) modules, read-only memory (ROM) modules, hard disks, and other non-transitory computer-readable media. The memory included in memory subsystem106is used as main memory in the computing system100and may be implemented using a variety of memory technologies, including NVM. Additional types of memory can be included in memory subsystem106or elsewhere in computing system100. For example, cache memory and registers may also be present in the processor104or on other components of the computing system100.

FIG. 2illustrates a memory system200within the computing system100. The memory system200includes components of the computing system100that are involved in the operation of the main memory220. The processor104of the computing system100corresponds to the host processor201, which includes memory controller202. Memory controller202manages read and write requests to and from the main memory220, and also controls the storage of entries in the write buffer210. The memory system200includes write buffer210and the main memory220, which are part of the memory subsystem106of the computing system100.

In one embodiment, the write buffer210is implemented using a fast and low-latency memory (relative to the main memory220) such as DRAM, and may be implemented on a different physical integrated circuit chip than the main memory220and the host processor201. The write buffer210utilizes a combination of a hash table and a linked list to store write entries for write requests directed at the main memory220.

The main memory220is implemented using NVM or, alternatively, may be implemented using some other memory technology that has a higher latency or experiences a higher wear rate than the write buffer. The main memory220also has a higher capacity than the write buffer210.

The memory controller202is communicatively coupled with both the write buffer210and the main memory220(e.g., through bus101). In one embodiment, the memory controller202is implemented in a field-programmable gate array (FPGA); alternatively, the memory controller202can be implemented using logic on the same die as the host processor201.

During operation of the computing system100, the host processor201issues write requests indicating data to be written to one or more addresses at the main memory220. The memory controller202includes logic that responds to such a write request from the host processor201by writing the data to the main memory220at the requested address. If the main memory is contended, the memory controller202detects the contention and instead stores a new write entry for the request in the write buffer210. The write entry includes the write address of the request, as well as the address in the main memory at which the data was requested to be written.

When adding the new write entry, the memory controller202also identifies a previous write entry that is the most recently added write entry prior to the new write entry, and updates a ‘next write’ pointer (NWP) of the previous write entry to refer to the new write entry. Thus, the memory controller202can create a chronological (i.e., oldest to newest) linked list of multiple write entries in the write buffer210, with a write entry corresponding to each of multiple write requests issued by the host processor.

In one embodiment, the memory controller202may further optimize performance by leaving a memory row open in the write buffer in response to determining that other write requests will be buffered within a threshold amount of time. Thus, after adding the new write entry, the memory controller202adds a subsequent new write entry in response to a subsequent write request prior to closing the memory row that was opened for writing the new write entry. This behavior reduces the time for updating the NWP.

Thus, in the case of memory contention at the main memory220, the memory controller202creates in the write buffer210a new write entry for the write request. In one embodiment, the memory controller202performs a write-back of the buffered writes in response to detecting at least a threshold amount of available bandwidth for the main memory. In other words, the memory controller202detects when the main memory220is no longer contended and has sufficient spare bandwidth for performing the write-back operation. In alternative embodiments, the host processor201or some other logic may determine whether the main memory has at least the threshold amount of available bandwidth for performing the write-back. To avoid the possibility of the write buffer becoming full, a maximum age can be specified for write buffer entries before they are forced to be written back to main memory.

Upon detecting that the main memory220has sufficient bandwidth or the age threshold has been reached, the host processor201or the memory controller202initiates the write-back operation (e.g., by issuing a write-back instruction). The memory controller202performs the write-back operation by traversing the linked list of write entries, starting from the first chronological write entry (i.e., the ‘head’ entry) and following the NWPs to subsequent write entries. For each of the write entries in the linked list, the data of the write entry is copied to the main memory220as the entry is traversed, the write entry is invalidated, and the linked list is updated by manipulating the head pointer. By this process, some or all of the buffered write data is written to the main memory220in the original chronological order of the write requests, and at the appropriate addresses as indicated in the write requests.

In one embodiment, the memory controller202maintains a Bloom filter203. For example, the Bloom filter203may be implemented as a bit array stored in memory in the memory controller, along with hash logic for determining bit positions corresponding to memory addresses to be added to the Bloom filter203. In alternative embodiments, the bit array and/or logic of the Bloom filter203may be implemented within parts of the memory system200other than the memory controller202.

The memory controller202maintains the Bloom filter203by, for each write entry that is added to the write buffer, adding an address of the write entry to the Bloom filter203. The hash logic of the Bloom filter203is used to determine bit positions corresponding to the address of the write entry, and the bit positions are set in the Bloom filter. The Bloom filter203can thus be used to determine if the address of a particular write request is “probably in the write buffer210” or “definitely not in the write buffer210”.

In response to an incoming write request, the memory controller202checks the Bloom filter203to determine whether the write buffer210should be updated instead of the main memory220. Thus, if the Bloom filter203indicates that the address of the write request is “probably in the write buffer210”, then the memory controller202attempts to locate the write entry or entries in the write buffer210and updates the data in the write entry for the write request, or the memory controller202writes-back the entries to the main memory220before executing the write request.

However, if the Bloom filter203indicates that the address of the write request is “definitely not in the write buffer210”, then the data is written to the main memory without a look-up of the address in the write buffer210, or a new entry is allocated in the write buffer without searching it for an older value to update. The Bloom filter203thus reduces the number of look-ups directed to the write buffer210.

The memory controller202also uses the Bloom filter203to check the write buffer210in response to incoming read requests. If the Bloom filter203indicates that the requested data could be in the write buffer210(i.e., the Bloom filter203returns a match for the read address), the memory controller202issues contemporaneous reads to both the write buffer210and the main memory220. If the data is present in the write buffer210, the memory controller202returns the data from the write buffer210and ignores the stale data from the main memory220. If the data is not in the write buffer210, it returns a ‘miss’ and the memory controller202returns the data from the main memory220. By serializing the operations and checking the write buffer first, energy can be saved by not having to access main memory on a write buffer hit. However, if the write buffer did not contain the address, latency is increased by waiting to access main memory.

However, if the Bloom filter203indicates that the requested data is not in the write buffer210(i.e., the Bloom filter does not return a match for the read address), then the memory controller202issues the read to the main memory220and returns the data read from the main memory220.

FIG. 3illustrates write entries301and302that can be stored in the write buffer210, according to an embodiment. InFIG. 3, the ‘write order’ indicates the chronological order of the write entries301and302; specifically, entry301having write order ‘0’ is written prior to entry302having write order ‘1’. The ‘address in buffer’ for each write entry indicates the hash address of the write entry in the write buffer210; write entry301is located at address ‘0’ in the write buffer210, while write entry302is located at address ‘128’. The ‘head pointer’ indicates the ‘head’ of the linked list of write entries, which is the oldest write entry in the linked list. The head write entry is not referenced by any other write entry in the linked list, and every other write entry is directly or indirectly referenced from the head write entry. The head pointer could be included in each write entry or, as illustrated inFIG. 3, may not be included in the write entries. For example, the head pointer could be stored in memory controller202, at a static location in the write buffer210, etc.

Each of the write pointers301and302includes the following fields: a valid bit (‘VALID’), a dirty bit (‘DIRTY’), an address field (‘TAG’), a data field (‘DATA’), a hash pointer (‘HASH_PTR’), and a next write pointer (‘NWP’). The address field TAG and the data field DATA store the address and data, respectively, of the original write request. Thus, when the memory controller202creates a write entry, it copies the address and data of the originating write request into the TAG and DATA fields, respectively, of the write entry. Note that if some bits of the address can be determined from the row index (as in a cache memory) then the tag only needs to store the remaining address bits.

Each write entry also includes a next write pointer (NWP) that points to the next subsequent write entry (i.e., the next newer write entry). For example, the NWP of entry301points to the address128, which is the hash address of the entry302. Write entry302is chronologically the next subsequent write entry after write entry301. In other words, the write entry302is generated from a write request that is the next subsequent write request following the write request from which write entry301was generated. If there is no newer write entry, the NWP is null. The memory controller202traverses the linked list of write entries (e.g., in response to a read or write-back operation) by following the head pointer to the first write entry, then following the NWP of each write entry to traverse the list until a null NWP is reached.

As an example, the write entries301and302inFIG. 3each represent a write request issued from the host processor201. A first write request to write DATA1at address A is received by the memory controller202, which creates write entry301at hashed address 0 of the write buffer210. Since write entry301is the first write entry in the buffer210, the head pointer is set to address 0. The next write request to write DATA2at address B is received by the memory controller202and is hashed to address128in the write buffer210, in write entry302. The NWP of the previous write entry301is concurrently updated to point to the hash address of write entry302, which is 128. In addition to the head pointer, a tail pointer can be maintained so that the current tail can be quickly located and updated in the event of a new write being inserted.

In one embodiment, each write entry also includes a previous write pointer (PWP) that points the previous write entry (i.e., the most recent prior write entry). For example, the PWP of write entry302stores the hash address ‘0’, referring to the previous write entry301. Since write entry301is at the head of the linked list, there is no previous write entry and the PWP of write entry301is NULL. The implementation of a doubly linked list including a NWP and PWP for each entry enables traversal of the linked list in either direction, and further enables fast insertion and deletion of entries.

For example, in a singly linked list, if a write request is received that is directed to an existing buffered address (e.g., corresponding to the nth write entry), the value can be updated in-place; however, moving the nth entry to the tail of the list would entail searching from the head of the list to find the (n−1)th entry (i.e., the previous entry) so that the NWP of the previous entry can be updated. In a doubly linked list, the memory controller202could 1) locate the (n−1)th entry via the PWP of the nth entry, 2) update the NWP of the (n−1)th entry to refer to the (n+1)th entry, 3) locate the (n+1)th entry via the NWP of the nth entry, 4) update the PWP of the (n+1)th entry to refer to the (n−1)th entry, and 5) move the nth entry to the tail of the linked list by updating the NWP of the last entry to refer to the nth entry and the NWP and PWP of the nth entry to refer to NULL and to the last entry, respectively.

The VALID bit of a write entry records whether the write entry is still valid. For example, when a write-back including the write entry has already been performed, the VALID bit is deasserted. The DIRTY bit can be used in embodiments where the write buffer210has cache-like functionality, and is asserted to indicate that changes to the data in the write entry have not been reflected in the main memory.

The hash pointer HASH_PTR for each write entry can be used to store hash addresses for referencing other write entries in the write buffer210for hash table chaining in the event of collisions that occur when write entries are being created. For example, if the memory controller202attempts to add an entry at a hash address that already contains an existing entry, a hash collision occurs. In the case of such a hash collision, the memory controller202chains the new write entry by creating the new write entry and updating the hash pointer of the existing write entry to point to the new write entry.

FIG. 4is a flow diagram illustrating a write buffering process400, according to an embodiment. The operations of process400are performed by the components of memory system200, including the host processor201, memory controller202, Bloom filter203, write buffer210, and main memory220. In alternative embodiments, some or all of the operations of process400may be performed by other components in the computing system100.

The process400begins by looping between blocks401and413; here, the memory controller202waits for memory requests (i.e., write requests or read requests) to be issued from the host processor201. If, at block401, the memory controller202receives a write request directed to the main memory220, then the process400continues from block401to block403. Blocks403-411represent a process for handling the write request.

At block403, the memory controller202determines whether the main memory220, to which the write request is directed, is contended. In one embodiment, the main memory220is contended if a concurrent access or other conflict prevents write access to the main memory220.

If the memory controller202receives a write request when the main memory is not contended (as determined at block403) the process400continues to block411. At block411, the memory controller202writes the data of the write request to the address in main memory as specified in the write request without buffering the write. From block411, the process400continues back to block401to continue handling additional write requests.

At block403, if the main memory is contended, then the process400continues at block405. At block405, the memory controller202adds a new write entry for the write request in the write buffer210. The new write entry includes the address and data of the original write request (as illustrated, for example, inFIG. 3). For an embodiment where each write entry includes a PWP, the memory controller202also updates the PWP of the new write entry to refer to the previous write entry (i.e., the most recently added write entry before the new write entry). For example, the PWP field of the new write entry may be updated to store the hash address of the previous write entry. From block405, the process400continues at block407.

At block407, the memory controller202updates the NWP of the previous write entry to reference the new write entry. For example, the memory controller202may change the NWP of the previous write entry from a NULL value to the hash address of the new write entry. From block407, the process400continues at block409.

At block409, the memory controller202adds the write address of the write request to the Bloom filter203. Hash logic for the Bloom filter generates bit positions corresponding to the write address, and the bit positions are set in the Bloom filter. From block409, the process400continues back to block401to continue handling additional write requests.

Thus, after adding the new write entry, the memory controller202may receive subsequent a write request (at block401) and, if the main memory220is still contended (block403), the memory controller202adds a subsequent new write entry for the subsequent write request at block405. The process400thus loops through blocks401-411when buffering multiple write requests that are received during a time when the main memory220is contended, creating a write entry in write buffer210for each write request that is received during this time. In one embodiment, the memory controller202may hold open a memory row of the write buffer210when creating multiple write entries. In other words, the memory controller202may open the memory row for a first write entry, then create one or more subsequent write entries prior to closing the memory row that was opened for creating the first write entry.

In one embodiment, the host processor201also issues read requests indicating an address of the main memory220from which data is to be retrieved. At block413, if the memory controller202receives a read request from the host processor201, the process400continues at block415.

At block415, the memory controller202determines whether the Bloom filter203returns a match for the read address specified in the read request. Specifically, the hash logic of the Bloom filter is used to determine bit positions corresponding to the read address, which are matched against the bit positions in the Bloom filter's bit array. If all of the bit positions are asserted, then a match is returned. Otherwise, if at least one of the bit positions is not asserted, then there is no match. If no match is returned by the Bloom filter, then no write entry exists in the write buffer210for the requested read address. The memory controller202thus issues the read request to the main memory, at block423, and returns the data retrieved from the main memory, at block425. From block425, the process400continues back to block413.

At block415, if the Bloom filter returns a match for the read address, then a write address could possibly exist in the write buffer for the requested read address, and the process400continues at block417. At block417, since the requested data could be in either the write buffer210or the main memory220, the memory controller contemporaneously issues the read request to both the write buffer210and to the main memory220in parallel. From block417, the process400continues at block419.

At block419, if the requested read address corresponds to a write entry in the write buffer210, then the write buffer210returns the requested data and the process400continues at block421. At block421, the memory controller202returns the data from the write buffer210, ignoring the data (presumed to be stale) that is returned by the main memory220in response to the read request. At block419, if the requested read address does not correspond to a write entry in the buffer210, then the buffer210returns a ‘miss’ and the memory controller202returns the data from the main memory220, as provided at block425. From block421or425, the process400continues back to block413.

By the operation of process400, write entries can be added to the write buffer210in response to write requests received when the main memory220is contended. In one embodiment, these write requests may be removed from the write buffer by a write flushing process500, as illustrated inFIG. 5. The operations of process500may be performed concurrently with the operations of process400; that is, process500may be performed in parallel with process400.

At block501, the memory controller202determines whether the main memory220has sufficient spare bandwidth to perform a write-back operation of the write entries in the write buffer210. In one embodiment, the main memory220may be determined to have sufficient bandwidth if the main memory220has an amount of available bandwidth that exceeds at least a predetermined threshold. In alternative embodiments, the spare bandwidth determination may be performed by other components in the memory system200or the computing system100. At block501, if the main memory does not have sufficient spare bandwidth to perform the write-back, the process500loops back to block501to continue checking for spare bandwidth.

At block501, if the main memory220has sufficient spare bandwidth to perform a write-back of the buffered writes in the write buffer210, the process500continues at block503. At block503, a write-back instruction is issued, which may be any signal or message that causes the memory controller202to initiate a write-back of the buffered writes to the main memory220. In one embodiment, the write-back instruction may be issued by the host processor201in response to detecting that the main memory220has sufficient spare bandwidth. In an alternative embodiment, the memory controller202may itself initiate the write-back operation in response to detecting sufficient spare bandwidth. From block503, the process500continues at block505.

At block505, the memory controller202begins traversing the linked list of write entries in the write buffer210by locating the head pointer, which references the first write entry in the linked list. If the head pointer is NULL, then there are no write entries to write-back, and the process500continues back to block501. Otherwise, the process500continues to block507, where the first write entry is located by following the address of the head pointer. From block507, the process500continues to block509.

At block509, the memory controller202copies the data from the DATA field of the write entry to the appropriate address (indicated in the TAG field of the write entry) of the main memory220. From block509, the process500continues at block511. At block511, the memory controller202invalidates the write entry by deasserting the VALID bit of the write entry. From block511, the process500continues at block513.

At block513, the memory controller202updates the Bloom filter203to reflect the removal of the write entry from the write buffer210. In one embodiment, the Bloom filter203is a counting filter, such that the insertion of a write entry address increments, rather than merely asserting, the bit positions in the Bloom filter203. The write entry is then removed from the Bloom filter203by using the Bloom filter's hash logic to again determine the bit positions corresponding to the address of the write entry, then decrementing the bit positions in the Bloom filter. From block513, the process500continues back to block505.

The process500thus repeats the operations of blocks505,507,509,511, and513in a loop to perform a write-back operation including all of the write entries in the linked list. Blocks505-513repeat until a write entry having a NWP set to NULL is reached, indicating the end of the linked list. At block505, when the last write entry (having a NWP set to NULL) is reached, the process500continues back to block501. The write flushing process500thus repeats the operations of blocks501-513to monitor the available bandwidth of the main memory220and flush the write entries from the write buffer210when sufficient bandwidth is available.

As used herein, the term “coupled to” may mean coupled directly or indirectly through one or more intervening components. Any of the signals provided over various buses described herein may be time multiplexed with other signals and provided over one or more common buses. Additionally, the interconnection between circuit components or blocks may be shown as buses or as single signal lines. Each of the buses may alternatively be one or more single signal lines and each of the single signal lines may alternatively be buses.

Certain embodiments may be implemented as a computer program product that may include instructions stored on a non-transitory computer-readable medium. These instructions may be used to program a general-purpose or special-purpose processor to perform the described operations. A computer-readable medium includes any mechanism for storing or transmitting information in a form (e.g., software, processing application) readable by a machine (e.g., a computer). The non-transitory computer-readable storage medium may include, but is not limited to, magnetic storage medium (e.g., floppy diskette); optical storage medium (e.g., CD-ROM); magneto-optical storage medium; read-only memory (ROM); random-access memory (RAM); erasable programmable memory (e.g., EPROM and EEPROM); flash memory, or another type of medium suitable for storing electronic instructions.

Additionally, some embodiments may be practiced in distributed computing environments where the computer-readable medium is stored on and/or executed by more than one computer system. In addition, the information transferred between computer systems may either be pulled or pushed across the transmission medium connecting the computer systems.

Generally, a data structure representing the memory system200and/or portions thereof carried on the computer-readable storage medium may be a database or other data structure which can be read by a program and used, directly or indirectly, to fabricate the hardware comprising the memory system200. For example, the data structure may be a behavioral-level description or register-transfer level (RTL) description of the hardware functionality in a high level design language (HDL) such as Verilog or VHDL. The description may be read by a synthesis tool which may synthesize the description to produce a netlist comprising a list of gates from a synthesis library. The netlist includes a set of gates which also represent the functionality of the hardware comprising the memory system200. The netlist may then be placed and routed to produce a data set describing geometric shapes to be applied to masks. The masks may then be used in various semiconductor fabrication steps to produce a semiconductor circuit or circuits corresponding to the memory system200. Alternatively, the database on the computer-readable storage medium may be the netlist (with or without the synthesis library) or the data set, as desired, or Graphic Data System (GDS) II data.

In the foregoing specification, the embodiments have been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the scope of the embodiments as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative sense rather than a restrictive sense.