Patent ID: 12189532

DETAILED DESCRIPTION

In the following detailed description, numerous specific details are set forth to provide a full understanding of the present disclosure. It will be apparent, however, to one of ordinary skill in the art that the various embodiments disclosed may be practiced without some of these specific details. In other instances, well-known structures and techniques have not been shown in detail to avoid unnecessarily obscuring the various embodiments.

Example Systems

FIG.1is a block diagram of an example system for implementing memory coherence and memory fault tolerance according to one or more embodiments. System100inFIG.1may function as, for example, a multi-core computer, a System on a Chip (SoC), or a supercomputer that processes data stored in shared memory112. As shown inFIG.1, system100includes processors102, caches104, interconnect110, and shared memory112.

Each of processors1021to102Ncan include, for example, circuitry such as one or more RISC-V cores or other type of Central Processing Unit (CPU), a Graphics Processing Unit (GPU), a microcontroller, a Digital Signal Processor (DSP), an Application-Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA), hard-wired logic, analog circuitry and/or a combination thereof. In this regard, each processor102may comprise a multi-core processor or each processor102can represent a single processing core. In some implementations, a processor102can include an SoC or other type of integrated processing system that includes a cache104to form a processing unit101. In addition, each processor102can include one or more levels of cache memory not shown inFIG.1, such as L1, L2, and/or L3 caches.

Processors1021to102Nuse respective caches1041to104Nas a Last Level Cache (LLC) (e.g., an L2, L3, or L4 cache depending on the levels of cache included in the processor102) that caches data blocks or cache lines that are requested by the processor102or expected to be accessed by the processor102. Cache controllers106control the operation of their respective cache memories108to retrieve cache lines from shared memory112via interconnect110and store the retrieved cache lines in cache memory108for access by processor102. In this regard, cache controllers106can retrieve cache lines from shared memory112based on commands received from its respective processor102, and in some implementations, may also retrieve or prefetch additional cache lines that are expected to be used by processor102.

Processors102and caches104can communicate with shared memory112via interconnect110, which can include, for example, a Peripheral Component Interconnect express (PCIe) bus, a Network on a Chip (NoC), or another type of bus or network. In this regard, each cache104and shared memory112can include respective interfaces for communicating on interconnect110.

Cache controllers106can follow a coherence protocol that is managed by memory controller114of shared memory112. In addition, cache controllers106can perform certain fault tolerance operations disclosed herein, such as erasure encoding cache lines for storage in shared memory112and erasure decoding cache lines retrieved from shared memory112. In some implementations, cache controllers106can include circuitry such as a hardware controller or other processing circuitry including hard-wired logic, analog circuitry and/or a combination thereof. Cache memories108can include, for example, Static Random Access Memory (SRAM), Magnetoresistive RAM (MRAM), or other high-speed RAM or Storage Class Memory (SCM). Cache controllers106can execute instructions, such as a firmware for managing cache memory108and for performing fault tolerance and coherency operations disclosed herein.

Memory controller114can include, for example, circuitry such as a hardware controller or other processing circuitry including hard-wired logic, analog circuitry and/or a combination thereof. Memory116can include, for example, Dynamic RAM (DRAM), or other solid-state memory, such as SCM, used as a main memory for system100that can be accessed by processors102via caches104for loading cache lines from memory116and storing cache lines in memory116. The cache lines can have a fixed size for use by processors102, such as a fixed number of bytes in the range of 16 bytes to 256 bytes.

While the description herein refers to solid-state memory generally, it is understood that solid-state memory may comprise one or more of various types of memory devices such as flash integrated circuits, NAND memory (e.g., Single-Level Cell (SLC) memory, Multi-Level Cell (MLC) memory (i.e., two or more levels), or any combination thereof), NOR memory, EEPROM, other discrete Non-Volatile Memory (NVM) chips, or any combination thereof. In other implementations, memory116and/or cache memories108(or memories216and/or cache memories208inFIG.2) may include an SCM, such as, Chalcogenide RAM (C-RAM), Phase Change Memory (PCM), Programmable Metallization Cell RAM (PMC-RAM or PMCm), Ovonic Unified Memory (OUM), Resistive RAM (RRAM), Ferroelectric Memory (FeRAM), MRAM, 3D-XPoint memory, and/or other types of solid-state memory, for example.

Memory controller114can execute instructions, such as a firmware for managing shared memory112and for performing certain fault tolerance and coherency operations disclosed herein. As discussed in more detail below, memory controller114can implement fault tolerance operations and coherency operations for data stored in regions of memory116, referred to herein as “blast zones” and described in more detail below with reference toFIG.3. Memory controller114can ensure the consistency or coherence of the copies of cache lines that are stored in memory116and in one or more cache memories108of caches104on a blast zone basis by serializing the performance of memory requests in the blast zone and tracking the state of the cache lines stored in the blast zone. In addition, memory controller114can ensure the fault tolerance of the cache lines on a blast zone basis by configuring each blast zone to include nodes that store respective data portions or parity portions of erasure encoded cache lines. Memory controller114may then replace nodes from the blast zones as needed from a rebuild pool of spare nodes in memory116.

Those of ordinary skill in the art will appreciate with reference to the present disclosure that other implementations of system100can include different components or a different arrangement of components. For example, other implementations of system100can include multiple shared memories112or a different number of caches104with respect to the number of processors102, such that there are more processors102than caches104. In addition, those of ordinary skill in the art will recognize that system100ofFIG.1is for the purposes of illustration, and that system100can include many more processors102, shared memories112, and/or cache memories108than shown inFIG.1.

FIG.2is a block diagram of an example distributed system for implementing memory fault tolerance and memory coherence according to one or more embodiments. As shown inFIG.2, system200includes processing units2011to2013and memory units2121to2123. Unlike system100inFIG.1, distributed system200inFIG.2includes separate memory units212that each include a memory216that is shared among the processing units201via network210as a main memory of system200.

In some implementations, system200inFIG.2may be used as at least part of a data center or supercomputer for distributed processing, such as for distributed machine learning or big data analysis. As will be appreciated by those of ordinary skill in the art, processing units201and memory units212are shown for the purposes of illustration, and distributed system200can include many more processing units201and/or memory units212than those shown inFIG.1. In addition, those of ordinary skill the art will appreciate that system200can include more components than shown inFIG.1, such as aggregated switches, Top of Rack (ToR) switches, and network controllers, for example.

Network210can include, for example, a Storage Area Network (SAN), a Local Area Network (LAN), and/or a Wide Area Network (WAN), such as the Internet. In this regard, processing units201and/or memory units212may not be in the same geographic location. Processing units201and memory units212may communicate using one or more standards such as, for example, Ethernet.

Each processing unit201in the example ofFIG.1includes one or more processors202and a cache204. These components of processing units201may communicate with each other via a bus, which can include, for example, a PCIe bus, or other type of interconnect, such as an NoC. In addition, each of processing units201can include a network interface for communicating on network210, such as a Network Interface Card (NIC), network interface controller, or network adapter.

Processors202can include, for example, circuitry such as one or more RISC-V cores or other type of CPU, a GPU, a microcontroller, a DSP, an ASIC, an FPGA, hard-wired logic, analog circuitry and/or a combination thereof. In this regard, each processor202may comprise a multi-core processor or each processor202can represent a single processing core. In some implementations, a processor202can include an SoC or other type of integrated processing system, which may be combined with a cache204. In addition, each of processors202can include one or more levels of cache memory not shown inFIG.2, such as L1, L2, and/or L3 caches.

Processors2021to2023use respective caches2041to2043as an LLC (e.g., an L2, L3, or L4 cache depending on the levels of cache included in the processor(s)202) that caches data blocks or cache lines that are requested by the processor(s)202or expected to be accessed by the processor(s)202. Cache controllers206control the operation of their respective cache memories208to retrieve cache lines from memory units212via network210and store the retrieved cache lines in cache memory208for access by processor(s)202. In this regard, cache controllers206can retrieve cache lines from memory units212based on commands received from its respective processor or processors202, and in some implementations, may also retrieve or prefetch additional cache lines that are expected to be used by the processor(s)202.

Cache controllers206can follow a coherence protocol that is managed by memory controllers214of memory units212. In addition, cache controllers206can also perform certain fault tolerance operations disclosed herein, such as erasure encoding cache lines for storage in memories216of memory units212and erasure decoding cache lines retrieved from memories216. In some implementations, cache controllers206can include circuitry such as a hardware controller or other processing circuitry including hard-wired logic, analog circuitry and/or a combination thereof. Cache memories208can include, for example, SRAM, MRAM, or other high-speed RAM or SCM. Cache controllers206can execute instructions, such as a firmware for managing cache memory208and for performing certain fault tolerance and coherency operations disclosed herein.

As shown in the example ofFIG.2, each memory unit212includes a memory controller214and a memory216. In addition, each memory unit212can include a network interface for communicating on network210, such as a NIC, network interface controller, or network adapter.

Memory controllers214of memory units212can include, for example, circuitry such as a hardware controller or other processing circuitry including hard-wired logic, analog circuitry and/or a combination thereof. Memories216of memory units212can include, for example, DRAM or other solid-state memory, such as SCM, used as a shared memory for distributed system200that can be accessed by processors202of processing units201via caches204for loading cache lines from memories216and storing cache lines in memories216. In this regard, memories216may collectively serve as a main memory for distributed system200. The cache lines can have a fixed size for use by processors202, such as a fixed number of bytes in the range of 16 bytes to 256 bytes.

As discussed in more detail below, memory controllers214can implement fault tolerance operations and coherence operations for data stored in regions of their respective memories216, referred to herein as blast zones. Memory controllers214can ensure the consistency or coherence of the copies of cache lines that are stored in its respective memory216and in one or more cache memories208of caches204on a blast zone basis by serializing the performance of memory requests in the blast zone and tracking the state of the cache lines stored in the blast zone. In addition, memory controllers214can ensure the fault tolerance of the cache lines on a blast zone basis by configuring each blast zone to include nodes that store a respective data portion or parity portion of erasure encoded cache lines. Memory controllers214may then replace nodes from the blast zones as needed from a rebuild pool of spare nodes in its associated memory216.

Those of ordinary skill in the art will appreciate with reference to the present disclosure that other implementations may include a different number or arrangement of processing units201and memory units212than shown in the example ofFIG.2. In this regard, distributed system200shown inFIG.1is for the purposes of illustration and those of ordinary skill in the art will appreciate that system200may include many more processing units201and/or memory units212, and additional components, such as routers and switches.

FIG.3provides an example configuration of memory116fromFIG.1or of a memory216from a memory unit212inFIG.2according to one or more embodiments. As shown inFIG.3, the memory has been partitioned into physical sub-regions of the memory (i.e., “nodes”), including active nodes12and spare nodes in a rebuild pool14. Blast zones101to10N are formed to include a predetermined number of active nodes12that are mapped to the blast zone in a logical to physical mapping of the memory116or216. The mapping can include, for example, routing tables or other data structures that indicate physical locations for the nodes in each blast zone.

The mapping of the nodes is logical in the sense that the nodes12of a particular blast zone10need not be physically adjacent to each other. Although the blast zones in some implementations may include physically adjacent nodes, other implementations may benefit from having nodes that are physically dispersed throughout the memory for better fault tolerance. In the example ofFIG.3, each blast zone10includes three nodes, but other implementations may include more nodes depending on the desired level of redundancy or error correction of the cache lines stored in the blast zones.

In the example ofFIG.3, each blast zone10includes two data portion nodes C1and C2and one parity portion node P. Each active node12in the blast zone10stores erasure encoded portions of cache lines. For example, a cache line can be split into two data portions that are stored in nodes121Aand121B, respectively, of blast zone101. A parity portion of the cache line can be stored in node121C. The parity portion of the cache line can include, for example, an XOR operation performed on the two data portions of the cache line stored in nodes121Aand121B. If one of the portions of the cache line cannot be recovered, such as due to the failure of a node, the missing portion of the cache line can be reconstructed by erasure decoding the missing portion using the other two portions of the cache line.

The size of each blast zone10can be based at least in part on the time it takes to read data from an entire storage capacity of the blast zone or a time it takes to write data to the entire storage capacity of the blast zone. This may be referred to as an “access density” of the blast zone. For example, 16 gigabytes (GB) of DRAM may have an access density of 1.6 seconds to fully write its 16 GB of storage capacity, while a 1 terabyte (TB) HDD may have an access density of approximately an hour to fully write its 1 TB of storage capacity. In some implementations, the blast zones may be sized to have an access density of approximately 1 millisecond (ms). The size of the blast zones can be set so that the access density, which can correspond to the time it takes to reconstruct data stored in one or more failed nodes12of the blast zone, is short enough to facilitate pausing or deferring new memory requests in the blast zone while the data is reconstructed. This independent handling of relatively smaller sized blast zones, as compared to the total size of the memory, can greatly simplify the preservation of consistency or coherence of the cache lines stored in the blast zone while one or more nodes in the blast zone are being rebuilt.

The rebuild operation for the blast zone can be triggered in response to a timeout value being reached in attempting to access data by a cache controller106of a cache104inFIG.1or a cache controller206of a memory unit201inFIG.1. In some implementations, the cache104or204may send a message to the shared memory112or memory unit212if it is not able to repair the missing data within a timeout value (e.g., 1 ms). The repair attempts by the cache104or204can include, for example, requesting the missing or corrupted data again or using Error Correcting Code (ECC) that may be included with a packet received from the shared memory112or memory unit212to correct flipped bits in the message.

In other cases, a rebuild operation for a blast zone can be triggered in response to a failure in reading or writing the data in one or more nodes12of the blast zone10, such as after performing a predetermined number of write or read retries that may correspond to a timeout value. Memory controller114inFIG.1or a memory controller214inFIG.2may also initiate the rebuild operation in response to one or more nodes reaching a usable life expectancy indicated by, for example, a number of read or write operations performed in the node, a latency in accessing data in the node, an error rate for data retrieved from or stored in the node, and/or a change in threshold voltages used to read or write data in the node.

If the memory controller determines that the data stored in one or more nodes12needs to be reconstructed, the memory controller can pause or defer new requests to access data in the blast zone, which may be tracked in some implementations in a buffer of shared memory112or memory unit212.

The memory controller designates one or more corresponding spare nodes (i.e., nodes R1to RN inFIG.3) from rebuild pool14in the memory116or216to replace the one or more nodes from the blast zone to be rebuilt. The selection of the spare nodes can be serialized from a head of rebuild pool14so that a first spare node R1is designated to replace a first failed node12, and subsequent requests to replace the same first failed node12are ignored. The designation may be accomplished, for example, by changing the mapping for the blast zone from the node being replaced to the new spare node.

As discussed below in more detail with reference to the rebuild sequence ofFIGS.6A and6B, the memory controller can recruit caches104or204that have requested cache lines from the blast zone to reconstruct the data to be stored in the newly designated node for the blast zone. This can include, for example, the memory controller sending the remaining portions of a cache line to the cache104or204to erasure decode the missing data and return the missing data portion or parity portion to the shared memory112or memory unit212. As used herein, erasure decoding can include calculating a missing data portion or parity portion, such as by performing an XOR operation on the other portions or a subset of the other portions of the cache line.

As shown inFIG.3, one node of each blast zone10serves as a Lowest Point of Coherence (LPC) for the cache lines stored in the blast zone by tracking a state of each cache line stored in the blast zone. The LPC node, such as nodes121B,122B, and12NB inFIG.3can store the states for the cache lines in the blast zone, such as by including an additional entry or field in its cache line portion for the state of the cache line. In other implementations, the LPC node may include a separate data structure for storing the states of the cache lines.

The states can indicate a status or permission level for different copies of the cache line being accessed by one or more caches104or204. Example states of cache lines can include, for example, a shared state for cache lines that are being accessed by one or more caches104or204that have a read-only access for the cache line, an exclusive state for cache lines that are being accessed by a cache104or204that has permission to modify the cache line, a modified state for cache lines that have been modified by a cache104or204and not yet returned to the memory116or216(i.e., “dirty” data), a valid state indicating that the cache line stored in the memory116or216is not being accessed by a cache104or204, and/or an invalid state indicating that the cache line stored in the memory116or216may not be the most current version of the cache line if it is being accessed by a cache104or204in an exclusive or modified state. The LPC node in some implementations may also track which cache104or204currently has access to the cache line and its associated status for the cache line.

As will be appreciated by those of ordinary skill in the art with reference to the present disclosure, other implementations may use different states for maintaining the coherence of the cache lines stored in memory116or216. For example, the state of the cache line at one or more caches104or204and/or in the blast zone may be inferred by a single state indicated in the LPC node. The state of the cache line in the blast zone may be inferred as shared when other copies of the cache line are shared at one or more caches104or204or if there are no caches104or204with access to a copy of the cache line. Similarly, the state of the cache line in the memory may be invalid when there is another copy of the cache line at a cache104or204in a modified or exclusive state.

Those of ordinary skill in the art will also appreciate with reference to the present disclosure that other implementations of memory116or216may differ. For example, each blast zone10may include more data portion nodes and/or more parity portion nodes to provide higher levels of fault tolerance.

Example Processes

FIG.4is a sequence diagram for a read/write operation in a blast zone according to one or more embodiments. In the example sequence ofFIG.4, a read request is sent for cache line x from a processor102or202to its LLC104or204. In response, the cache104or204sends a request to read a parity portion of cache line x (i.e., “Get Shared xp” inFIG.4) to shared memory112or memory unit212, which is directed to a parity node of the blast zone storing the cache line (i.e., “P” inFIG.4). The cache104or204also sends a get shared request for a data portion of cache line x (i.e., “Get Shared xc1” inFIG.4) to shared memory112or memory unit212, which is directed to the data portion node of the blast zone that serves as the LPC (i.e., C1/LPC inFIG.4). In some implementations, the cache104or204may also optionally send a get shared request that is directed to a second data portion node that is not the LPC in attempt to receive the two data portions needed to decode the cache line sooner if the data portion from the other node arrives quicker. This is indicated by the first dashed arrow inFIG.4from cache104or204to node C2. In other implementations, the sending of the additional get shared request may be omitted in favor of conserving packet processing resources and bandwidth on the interconnect or network.

As noted above with reference toFIG.3, other implementations may include a different number of data portions and/or parity portions in the blast zone. In such implementations, at least one request is directed to the LPC node, which may be a parity node or a data node, and at least as many additional requests are sent as are needed for reconstructing the full cache line, which will depend on the level of redundancy used by the erasure code. In addition, other implementations may not require the cache104or204to send separate requests to the shared memory112or memory unit212for each data and/or parity portion. In such implementations, the memory controller or other circuitry of the shared memory112or memory unit212may be responsible for directing the performance of the access requests to the relevant nodes for the cache line.

Shared memory112or memory unit212sends the parity portion from the parity node and a first data portion from the LPC node. Shared memory112or memory unit212may also optionally send extra data or parity portions that may have been additionally requested for speeding up the receipt of the portions in some implementations, as indicated by the dashed arrow from node C2to cache104or204inFIG.4. The data portion(s) and/or parity portion(s) may be sent as separate packets as shown in the sequence ofFIG.4or may be sent together as a single packet in some implementations.

A version or sequence number is included with each portion of the cache line sent to the cache104or204. The cache controller can compare the version numbers from the different portions for the same cache line to ensure that all the received portions are for the same version of the cache line. For example, a higher version number for the portion received from the LPC node than for a portion received from another node can indicate that the other node may not have committed or stored its portion of the latest version of the cache line. In such an example, the cache104or204may then request that the portion is resent until reaching a timeout value, which may trigger a rebuild process for the other node, as discussed in more detail below with reference toFIGS.6A and6B.

A cache controller of the cache104or204may then perform erasure decoding to reconstruct the cache line x before sending it to the processor102or202to complete the read request received from the processor by the cache controller at the beginning of the sequence. At this point in the example ofFIG.4, the processor102or202decides to modify cache line x so it now requests the cache104or204to obtain an exclusive permission or state to modify cache line x. In response, the cache controller for the cache104or204sends a “Get Exclusive x” request to the shared memory112or memory unit212. The memory controller directs the request to the LPC node of the blast zone that stores cache line x to determine if any other copies of cache line x need to be invalidated and to update the state for cache line x to indicate that it is in an exclusive state for the processor102or202. In this regard, the coherence protocol of the present disclosure may be considered a permissive protocol in that memory requests are generally granted in the order in which they are received.

After updating the state of cache line x in the LPC node, the shared memory112or memory unit212returns an acknowledgement to the cache104or204granting exclusive access to modify cache line x (i.e., “Exclusive x Ack.” inFIG.4). The cache104or204then notifies the processor102or202of the change in status for cache line x. After modifying cache line x, the processor102or202sends a write command to the cache104or204to store the modified cache line x′ in memory.

In response, a cache controller of cache104or204can erasure encode the modified cache line x′ and sends the data portions and parity portion to shared memory112or memory unit212with an incremented version number indicating that the cache line has been modified, which can be updated in the LPC node. As used herein, erasure encoding can include splitting a cache line into data portions and calculating one or more parity portions from the data portions, such as by performing an XOR operation on the data portions.

FIG.5is a sequence diagram for a contention resolution sequence in a blast zone according to one or more embodiments. As shown in the example ofFIG.5, a cache1042or2042sends requests to obtain exclusive permission to modify cache line x and requests two data portions of the cache line from the LPC node (i.e., C1/LPC inFIG.5) and a second data portion node (i.e., C2inFIG.5). Shared memory112or memory unit212responds with the data portions with indications of the versions of the data portions for cache line x (i.e., “xc1, v1” and “xc2, v1” inFIG.5). The cache controller of cache1042or2042erasure decodes the data portions, such as by appending the data portions, to form cache line x for processing.

A different cache1041or2041then sends requests to obtain a shared access to cache line x by requesting the parity portion from the parity node of the blast zone and a data portion from the LPC node of the blast zone (i.e., “Get Shared xp” and “Get Shared xc1” inFIG.5). The parity portion xp is returned to the cache1041or2041, but no response is sent from the LPC node since the state in the LPC node indicates that cache1042or2042already has exclusive access to cache line x. Instead, an invalidate message is sent from the LPC node (i.e., “Invalidate x”) to return the copy of cache line x to the blast zone so that cache line x can be shared with cache1041or2041. In other implementations, the LPC node may alternatively send a “probe” request to have cache line x returned to the blast zone.

In response, the cache controller for cache1042or2042erasure encodes its copy of cache line x, which has been modified (i.e., “Encode x′” inFIG.5). The cache controller for cache1042or2042then stores the data portions and parity portion resulting from the erasure encoding in the different nodes of the blast zones with an incremented version number indicating that the cache line has been modified. The LPC node for the blast zone updates the version number and provides its data portion for the new version of cache line x to cache1041or2041.

In some implementations, the memory controller may then send the parity portion for the new version of cache line x to the cache1041or2041to replace the outdated version previously sent from the parity node of the blast zone without an additional request from cache1041or2041for the updated version. In other implementations, the receipt of the new version of the data portion from the LPC node with the higher version number can trigger the cache controller for cache1041or2041to send a new get shared request for the parity portion, as indicated by the dashed arrow inFIG.5. The cache controller then performs erasure decoding on the new portions of the cache line to reconstruct the cache line for processing.

FIGS.6A and6Bprovide a sequence diagram for a rebuild sequence in a blast zone according to one or more embodiments. In the example sequence ofFIGS.6A and6B, a cache1042or2042requests exclusive access to a cache line x by sending a get exclusive request for a first data portion xc1 from the LPC node of the blast zone and sending a get exclusive request for a second data portion xc2 from another data node, C2, of the blast zone. However, the data node C2has recently been replaced by a spare node C2′ from a rebuild pool of shared memory112or memory unit212and is in the process of being rebuilt.

As discussed in more detail below with reference toFIG.8, the rebuild process may begin in some implementations with the memory controller for the shared memory112or memory unit212broadcasting invalidate messages for the data portions stored in the node being rebuilt. In cases like the example ofFIG.6Awhere the node being rebuilt is not the LPC node for the blast zone, the version numbers of any copies of the portions received from caches that were accessing the cache line can be compared to the state for the cache line in the LPC node. If the cache sending the cache line portion matches the cache indicated as having access to the cache line in the state stored in the LPC node, the memory controller may use the received cache line portion by storing the received portion in the replacement node and the reconstruction of that data portion can be skipped.

On the other hand, if the LPC node needs to be rebuilt, each cache line portion stored in the LPC node can be first reconstructed using erasure coding before proceeding with using any received data portions that were being accessed by caches. In other implementations, the storing of dirty data for a cache line in the blast zone may instead proceed after a portion for the cache line has been stored in the new node without having to wait for all the remaining cache line portions to be reconstructed and stored in the new node.

In the example ofFIG.6, the memory controller of shared memory112or memory unit212defers performance of the request for cache line x and recruits the requesting cache1042or2042to help reconstruct data to be stored in the new data node C2′ by sending a message to cache1042or2042to reconstruct a data portion for a different cache line a (i.e., “Reconstruct a, ac1, v1” inFIG.6A). The reconstruct message can include the data portion from the LPC (i.e., “ac1”) and a version number for the cache line portion.

In response, cache1042or2042sends a get exclusive request for the parity portion of the cache line a from the parity node in the blast zone. In implementations that may require a greater number of portions to reconstruct the data portion, the cache1042or2042would send additional get exclusive requests to obtain enough portions to reconstruct the data portion. After receiving the parity portion for cache line a, the cache controller erasure decodes the data portion for cache line a to be stored in node C2′ (i.e., “ac2”). The cache1042or2042then sends the reconstructed data portion for storage in the new node C2′ of the blast zone.

By recruiting caches attempting to access data from the blast zone being rebuilt, the performance impact of rebuilding is reduced since the requesting cache would otherwise need to wait for the blast zone to finish being rebuilt before proceeding with the requested cache line. In addition, and as noted above, the size of the blast zone can be small enough so as not to impose an unacceptable delay for the system (e.g., in terms of Quality of Service (QoS)) in reconstructing the data stored in or one or more nodes of the blast zone.

Cache1042or2042attempts again to request exclusive access to cache line x by sending a get exclusive request for the first data portion xc1 from the LPC node and sending a get exclusive request for the second data portion xc2 from node C2′. However, a reconstructed copy of the second data portion xc2 has not been stored in node C2′ yet.

The memory controller of shared memory112or memory unit212can ignore the resent request for cache line x and recruits the requesting cache1042or2042to help reconstruct a data portion for another cache line b to be stored in data node C2′ by sending a reconstruct message to cache1042or2042to reconstruct the data portion with the data portion from the LPC node (i.e., “bc1”) and a version number for the cache line portion.

In response, cache1042or2042sends a get exclusive request for the parity portion of cache line b from the parity node in the blast zone. After receiving the parity portion for cache line b, the cache controller erasure decodes the portion of cache line b to be stored in node C2′ (i.e., “bc2”). The cache1042or2042then sends the reconstructed data portion for storage in the new node C2′ of the blast zone.

A different cache1041or2041then requests shared access to cache line x by sending get shared requests for a parity portion and a data portion of cache line x to nodes P and C1of the blast zone. The parity node in the example ofFIG.6Areturns the parity portion of cache line x (i.e., “xp”), but the LPC node returns a reconstruct message for the data portion of node C2′ since this data portion has not yet been reconstructed and stored in node C2′.

The memory controller of shared memory112or memory unit212defers the new get shared request for cache line x and recruits the requesting cache1041or2041to help reconstruct a data portion for another cache line c to be stored in data node C2′ by sending a reconstruct message to cache1041or2041to reconstruct the data portion with the data portion from the LPC node (i.e., “cc1”) and a version number for the cache line portion.

In response, cache1041or2041sends a get exclusive request for the parity portion of cache line c from the parity node in the blast zone. After receiving the parity portion for cache line c, the cache controller of cache1041or2041reconstructs the portion of cache line c to be stored in node C2′ (i.e., “cc2”). The cache1041or2041then sends the reconstructed data portion for storage in the new node C2′ of the blast zone.

The new node C2′ continues to be rebuilt inFIG.6Awith reconstructed data portions from requesting caches and the rebuilding of node C2′ reaches the data portion for cache line x. Cache1042or2042again requests exclusive access to cache line x by sending a get exclusive request for the first data portion xc1 from the LPC node and sending a get exclusive request for the second data portion xc2 from node C2′. The shared memory112or memory unit212sends a reconstruct message for cache line x including the data portion from the LPC node, xc1, and a version number for cache line x.

In response, cache1042or2042sends a get exclusive request for the parity portion of cache line x from the parity node in the blast zone. After receiving the parity portion for cache line x, the cache controller reconstructs the portion of cache line x to be stored in node C2′ (i.e., “xc2”). The cache1042or2042then sends the reconstructed data portion for storage in the new node C2′ of the blast zone.

After cache line x has been reconstructed, the memory controller in some implementations may then resume performance of the deferred get exclusive memory request from cache1042or2042by sending an acknowledgment to grant the exclusive state of the cache line x stored by cache1042or2042(i.e., “Exclusive x Ack.” inFIG.6A), even though all of the portions may not have been stored yet in C2′. A cache controller of cache1042or2042may then decode the locally stored erasure encoded portions of cache line x, such as by appending the data portions for xc1 and xc2, for processing by a processor associated with cache1042or2042.

In the example ofFIG.6A, the next deferred memory request for cache line x is then resumed after granting the exclusive access to cache line x. As a result, shared memory112or memory unit212sends an invalidate message to cache1042or2042to return its copy of cache line x (which may or may not have been modified) to perform the deferred get shared request from cache1041or2041for cache line x.

Following the rebuild sequence ofFIG.6AtoFIG.6B, cache1042or2042erasure encodes a modified copy of cache line x′ and sends the data portions and the parity portion for cache line x′ for storage in the corresponding nodes of the blast zone with an incremented version number (i.e., v2). After storing the portions for cache line x and updating the version number in the state for the cache line, the shared memory112or memory unit212sends the first data portion requested for cache line x from the LPC node to the cache1041or2041and sends the parity portion for cache line x from the parity node to the cache1041or2041. In some implementations, the cache1041or2041may send an additional get shared request for the parity portion, as indicated by the dashed arrow inFIG.6B. Cache1041or2041then decodes the updated cache line x for read-only processing by an associated processor.

Those of ordinary skill in the art will appreciate with reference to the present disclosure that the example rebuild sequence ofFIGS.6A and6Bis for the purposes of illustration and that other implementations may differ. For example, other rebuild sequences may include a different number of nodes than shown inFIGS.6A and6Bor may involve rebuilding the LPC node, which may further delay the performance of deferred requests until after the completion of reconstructing all of the data for the LPC node.

FIG.7is a flowchart for a memory configuration process according to one or more embodiments. The memory configuration process ofFIG.7can be performed by, for example, memory controller114inFIG.1or at least one memory controller214inFIG.2.

In block702, the memory controller partitions at least one memory into a plurality of nodes of a predetermined size. The partitioning may be accomplished, for example, by logically dividing a portion of the at least one memory allocated for shared use by the system into equally sized physical memory regions.

In block704, the memory controller forms a plurality of blast zones that each include a predetermined number of nodes from the partitioning in block702. The predetermined number of nodes in each blast zone corresponds to the total number of data portions and parity portions that will be used to erasure encode the cache lines to be stored in each blast zone. The cache lines can have a fixed size for use by processors in the system, such as a fixed number of bytes in the range of 16 bytes to 256 bytes, and the blast zones can be sized to store up to a predetermined number of erasure encoded cache lines. The partitioning of the at least one memory in block702can take this blast zone sizing and the number of portions for erasure encoding into account when determining the predetermined size of each node.

The nodes assigned to the blast zone may be located in different areas of the at least one memory, such as to provide a more robust fault tolerance since different physical areas of memory may be more prone to failure or wearing out prematurely. As discussed above, the blast zones may be sized based on an access density of the blast zone to facilitate rebuilding one or more nodes of the blast zone within a threshold time, which may be based on a QoS for the system. The formation of the blast zones in block704can include, for example, mapping physical addresses for the nodes to logical identifiers or logical addresses for the blast zones and/or nodes.

In block708, the memory controller stores erasure encoded cache lines in one or more blast zones such that at least two nodes in a blast zone store respective portions of a cache line and at least one node in the blast zone stores a parity portion of the cache line. In addition, and as discussed above, one of the nodes in each blast zone can serve as an LPC for tracking the states of any copies of cache lines throughout the system. The independent data recovery of each blast zone enables a faster recovery due to the smaller size of the blast zones as compared to checkpointing an entire memory and restoring data from a storage device for a larger memory region.

In addition, the independent coherence tracking of each blast zone facilitates a temporary pause in performing new memory requests while the blast zone is rebuilt without incurring a significant penalty since the size of the blast zone can be set based on a time to rebuild one or more nodes (e.g., a 1 ms rebuild time). This use of coherence tracking and data recovery at a smaller blast zone level can improve the scalability of memory coherence and fault tolerance because the time to track coherence and recover data is generally limited to a fixed blast zone size regardless of the overall size of the system. Advantageously, the down time to reconstruct data in large scale systems, such as in supercomputers and data centers is significantly decreased as compared to recovering checkpointed data for much larger regions of memory.

Those of ordinary skill in the art will appreciate with reference to the present disclosure that the memory configuration process ofFIG.7may be performed in a different order. For example, more blast zones may be added in block704after storing erasure encoded cache lines in block706to increase the available memory capacity for the system. In addition, more portions of memory may be partitioned into nodes in block702for the formation of additional blast zones in block704.

FIG.8is a flowchart for a rebuild process according to one or more embodiments. The rebuild process ofFIG.8can be performed by, for example, memory controller114inFIG.1or at least one memory controller214inFIG.2in conjunction with at least one cache controller106inFIG.1or at least one cache controller206inFIG.2.

In block802, the memory controller determines that data stored in one or more nodes in a blast zone needs to be reconstructed and stored in one or more nodes from a rebuild pool in at least one memory. The determination can be based on, for example, at least one of a useable life expectancy for the one or more nodes and a failure indication from attempting to access data stored in the one or more nodes.

In this regard, a cache requesting access to the data can initiate the rebuild process by sending a message to the shared memory or memory unit indicating that a request for the one or more nodes has timed out for requested data or for an acknowledgment that data has been stored in the one or more nodes. In some implementations, this may occur after the requesting cache has attempted at least one retry by resending its request.

In addition, the memory controller may initiate the rebuild process, such as when not being able to read or write data from the one or more nodes, which may follow attempts to error correct the data using ECC or attempts to retry the read or write operation. In such cases, the memory controller may use at least one of a predetermined number of retry attempts and a timeout value for accessing the data. The memory controller may also initiate a rebuild of one or more nodes based on life expectancy information, such as at least one of number of read or write operations performed in the one or more nodes, a change in a threshold voltage needed to read or write data in the one or more nodes, a latency in accessing data in the one or more nodes, and/or an error rate in data stored or retrieved from the one or more nodes.

In block804, the memory controller defers the performance of any new memory requests from caches to access data in the blast zone. As discussed above with reference to the rebuild sequence ofFIGS.6A and6B, the blast zone is sized so that the deferring of new memory requests does not significantly delay operation of the system. Any new memory requests received from the caches may be buffered in the shared memory or memory unit to be performed after the entire node or nodes have been rebuilt in the case where an LPC node is being rebuilt or after the particular cache line or cache lines of the deferred request has been reconstructed in the rebuilt node(s) in the case where the LPC node is not being rebuilt. In addition, the memory controller may discard repeated memory requests for the same cache line(s) from the same cache so that the deferred requests can be performed in the order in which they were received after the data has been reconstructed and to conserve space in any buffers that may be used to defer the new requests.

In some cases, the performance of at least one memory request is deferred since an initial memory request from a cache may initiate the rebuild process. The first memory request that triggers the determination that data stored in the one or more nodes needs to be reconstructed is then considered the first deferred memory request. In other implementations, such as where the memory controller initiates the rebuild process on its own without receiving a memory request from a cache, there may not be any deferred memory requests in block804.

In block806, the memory controller designates one or more spare nodes from a rebuild pool of the at least one memory to replace the one or more nodes of the blast zone being rebuilt. The designation can be made by changing a mapping, such as a routing table, to replace a physical address or addresses for the one or more nodes being rebuilt with a physical address or addresses for the one or more spare nodes. Since multiple caches and/or the memory controller may initiate the rebuild process as discussed above for block802, the memory controller serializes the designation of each spare node by selecting a first spare node in the rebuild pool and disregards additional messages to rebuild the same node.

In block808, erasure decoding is performed using data stored in one or more other nodes in the blast zone to reconstruct the data stored in the one or more nodes being rebuilt. As discussed above with reference to the rebuild sequence ofFIGS.6A and6B, the memory controller can recruit caches that request access to data in the blast zone to reconstruct the data for the node or nodes being rebuilt. This improves the efficiency of the rebuild process since the processors instructing the requesting caches would otherwise stall or encounter delays by not having access to data in the blast zone while the node(s) are being rebuilt.

The memory controller can send a reconstruct message for a cache line to the requesting cache in response to receiving a request from the cache during the rebuild process. A cache controller of the cache can then erasure decode the portions or portions of the cache line to be reconstructed using data from the remaining nodes in the blast zone. In some cases, only one cache may end up reconstructing all the data for the rebuilt node(s) if no other caches are sending memory requests during the rebuild process. In other implementations, the memory controller or other hardware of the shared memory or memory unit (e.g., a hardware accelerator such as a GPU) may reconstruct data if no other caches request data or to otherwise speed up the rebuild process.

In block810, the reconstructed data is stored in the one or more spare nodes. As discussed above with reference to the rebuild sequence ofFIGS.6A and6B, the cache or caches that have been recruited to reconstruct the data may send the cache line portions as they are reconstructed. The memory controller may then update a count or other indicator, such as an indication in the state of the cache line in the LPC node to indicate that reconstruction of the cache line has been completed.

In block812, the memory controller resumes performance of any deferred memory requests in the blast zone. In cases where the LPC node was not rebuilt, the resumption of deferred memory requests may occur after the requested cache line has been reconstructed. In such cases, the performance of certain memory requests may occur while other cache lines are still being reconstructed. In cases where the LPC node was rebuilt, the resumption of the deferred memory requests may occur after all the cache lines for the blast zone have been reconstructed. After all the cache lines have been reconstructed and all the unique deferred memory requests (i.e., not including repeated memory requests from the same cache) have been performed in the order the requests were initially received, the operation of the blast zone returns to normal without deferring performance of any further new memory requests.

Those of ordinary skill in the art will appreciate with reference to the present disclosure that other implementations of the rebuild process ofFIG.8may differ. For example, other implementations may omit the deferral of new memory requests in block804where the rebuild process is initiated without receiving a memory request from a cache and no new memory requests are received throughout the rebuild process. In such implementations, the memory controller may reconstruct the data on its own or may recruit caches for reconstructing data on a basis other than the origination of memory requests, such as based on a past history of access of the blast zone by the recruited caches.

The foregoing fault tolerance and memory coherence arrangements and operations can reduce the latency and storage footprint otherwise needed to maintain fault tolerant and coherent data in large-scale systems. In one aspect, the independent blast zones storing erasure coded cache lines can provide a lower storage overhead as compared to checkpointing an entire redundant copy of the cache lines. In another aspect, the performance penalty for reconstructing data in each independent blast zone is compartmentalized or limited to the blast zone, which can be sized based on an acceptable performance penalty for rebuilding one or more nodes. Similarly, the performance cost in maintaining coherence of the cache lines in large scale systems is also compartmentalized, which generally improves scalability of the system. In addition, the foregoing fault tolerance and memory coherence operations can significantly reduce downtime in large-scale systems, such as supercomputers and data centers, since the independent blast zones are relatively small and scalable as compared to conventional coherence and fault tolerance methods used for system memory.

Other Embodiments

Those of ordinary skill in the art will appreciate that the various illustrative logical blocks, modules, and processes described in connection with the examples disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. Furthermore, the foregoing processes can be embodied on a computer readable medium which causes processor or controller circuitry to perform or execute certain functions.

To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, and modules have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Those of ordinary skill in the art may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present disclosure.

The various illustrative logical blocks, units, modules, processor circuitry, and controller circuitry described in connection with the examples disclosed herein may be implemented or performed with a general purpose processor, a GPU, a DSP, an ASIC, an FPGA or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. Processor or controller circuitry may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, an SoC, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The activities of a method or process described in connection with the examples disclosed herein may be embodied directly in hardware, in a software module executed by processor or controller circuitry, or in a combination of the two. The steps of the method or algorithm may also be performed in an alternate order from those provided in the examples. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable media, an optical media, or any other form of storage medium known in the art. An exemplary storage medium is coupled to processor or controller circuitry such that the processor or controller circuitry can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to processor or controller circuitry. The processor or controller circuitry and the storage medium may reside in an ASIC or an SoC.

The foregoing description of the disclosed example embodiments is provided to enable any person of ordinary skill in the art to make or use the embodiments in the present disclosure. Various modifications to these examples will be readily apparent to those of ordinary skill in the art, and the principles disclosed herein may be applied to other examples without departing from the spirit or scope of the present disclosure. The described embodiments are to be considered in all respects only as illustrative and not restrictive. In addition, the use of language in the form of “at least one of A and B” in the following claims should be understood to mean “only A, only B, or both A and B.”