Executing parallel operations to increase data access performance

Techniques are described for increasing data access performance for a memory device. In various embodiments, a scheduler/controller is configured to manage data as it read to or written from a memory. Read or write access is increased by partitioning a memory into a group of sub-blocks, associating a parity block with the sub-blocks, and accessing the sub-blocks to read data as needed. Write access is increased by including a latency cache that stores data associated with a read command. Once a read-modify write command is received, the data stored in the data cache is used to update the parity block. In a memory without a parity block, write access is increased by adding one or more spare memory blocks to provide additional memory locations for performing write operations to the same memory block in parallel.

TECHNICAL FIELD

Embodiments presented in this disclosure generally relate to memory management techniques, and more particularly, to increasing data access performance by creating additional ports or channels used to read to and write from a memory storage device.

BACKGROUND

Demand for memory bandwidth on network and switching devices continues to increase. For example, memory bandwidth needs to keep pace with both increases in port density (i.e., with rapidly increasing system port counts) as well as with increases in port speeds (e.g., as port speeds migrate upwards from 1 Gb to 10 Gb to 40 Gb to 100 Gb). Higher density ports and higher speeds translate to larger and faster tables with correspondingly larger aggregate memory and I/O bandwidth requirements. For example, a network-switching device may use memory lookup tables for routing and forwarding network traffic. These tables may include hundreds-of-thousands of entries used for routing millions of network packets.

In these systems, a central processing unit (CPU) or other specialized circuitry (e.g., a field programmable gate array) is configured to route network data received on one port of the device to another port. Firmware running on the network device reads addresses from the lookup table to determine what port a given packet should be forwarded over (based on reading a destination address listed in the packet). As both port density and port speeds increase, the rate at which data can be read from the forwarding table (and from the packet in a buffer) is becoming a limiting factor in the throughput of some network and switching devices.

Further, increases in port density and link speeds also present heavy demands on the memory write capabilities of a networking device. For example, the network device may include buffers used to store a network packet received on one port prior to forwarding the packet out on another port. If the write speeds are insufficient to keep pace with the port speed (and increased port density), packet drops may occur. Similarly, the network device may be configured to write counters values (or other data) to memory for use in traffic monitoring, traffic shaping and for variety of other purposes. Thus, much like the speed at which memory reads occur, the speed at which memory writes occur is becoming a limiting factor for the performance of some network and switching devices.

DESCRIPTION

Overview

One embodiment of the present disclosure includes a method for performing a plurality of read operations and a write operation in parallel. The method includes performing a first read operation by reading data at a first memory address in a first block of addresses and, in parallel to the first read operation, performing a second read operation for a second memory address in the first block of addresses by reading data at an address from a second block of memory addresses and a first parity block. Moreover, performing the second read operation includes performing a first exclusive-or (XOR) operation using the data read from the second block of memory addresses and read from the first parity block. The method includes, in parallel to the first and second read operations, performing the write operation by writing data to a third memory address in the first block of addresses. The method includes updating a value in the first parity block in response to the write operation by performing a second XOR operation using at least the data read from at least two other parity blocks.

Another embodiment of the present disclosure includes an apparatus including a memory and memory controller configured to perform multiple read operations and a write operation in parallel. The memory controller performs a first read operation by reading data at a first memory address in a first block of addresses in the memory and, in parallel to the first read operation, performs a second read operation for a second memory address in the first block of addresses by reading data at an associated address from a second block of memory addresses in the memory and a first parity block in the memory. Moreover, performing the second read operation comprises performing a first exclusive-or (XOR) operation using the data read from the second block of memory addresses and read from the first parity block. The memory controller, in parallel to the first and second read operations, performs the write operation by writing data to a third memory address in the first block of addresses. The memory controller updates a value in the first parity block in response to the write operation by performing a second XOR operation using the data read from at least two other parity blocks in the memory.

Another embodiment of the present disclosure includes a method for performing a read-modify write operation. The method includes performing a read operation by reading data at a first memory address in a first block of addresses and, in response to the read operation, storing data from a second block of addresses corresponding to the first memory address into a cache. The method includes, after performing the read operation, performing the read-modify write operation by writing data at the first memory address. While performing the read-modify write operation, the method includes updating a value of a parity block by performing an XOR operation using the data written to the first memory address and the data stored in the cache in response to the read operation.

Another embodiment of the present disclosure includes a method for performing at least three simultaneous write operations. The method includes receiving three write commands associated with a first memory address, second memory address, and third memory address, respectively and determining, by querying both a first and a second memory translation table, that the first, second, and third addresses are each assigned to a first memory block of a plurality of memory blocks. The method includes performing a first write operation to the first memory address in the first memory block. In parallel to the first write operation, the method includes identifying second and third memory blocks from the plurality of memory blocks that each have at least one available memory location, assigning the second memory address to the second memory block and the third memory address to the third memory block, and updating the first memory translation table to indicate that the second memory address is assigned to the second memory block and the second memory translation table to indicate that the third memory address is assigned to the third memory block.

Description of Example Embodiments

Embodiments described herein provide techniques for increasing data access performance for a memory device. In various embodiments, a scheduler/controller is configured to manage data written to and read from a memory. In one embodiment, read access is increased by partitioning a memory into a group of sub-blocks, associating a parity block with the sub-blocks, and accessing the sub-blocks to read data as needed. Data access is increased by allowing simultaneous reads to addresses within the same block to occur—data for one address being read from a sub-block in which the address is located, and data for a second address being read using the combination of the other sub-blocks and the parity block. Further, the memory may be partitioned (and parity blocks added) across n-dimensions. Doing so provides an n+1-fold read performance for completely random access (necessary for general-purpose applications) without introducing a throughput penalty due to access collisions. This topic is also discussed in co-pending U.S. patent application Ser. No. 12/870,566 filed Aug. 27, 2010 entitled “Increasing Data Access Performance”, which is incorporated herein by reference in its entirety.

Further, a memory partitioned to include at least two dimensions may also provide a write access advantage. In this case, the memory may perform both a read operation and a write operation in parallel, even if the sub-blocks are capable of performing only one read and one write per memory access cycle. Because each time a sub-block is written to the corresponding parity block (or blocks) are updated, the memory may use the other parity blocks (e.g., row and column parity blocks) to update the parity block. Doing so enables the memory to perform a conflict-free read operation in parallel to the write operation. As used herein, a “memory access cycle” is typically one clock cycle of the memory's clock. However, in some embodiments, a memory access cycle may extend over several clock cycles. For example, a read-modify write operation is pipelined to avoid wasting bandwidth. That is, if read-modify write operations are received at time0, time1, and time2, they may complete at time2, time3, and time4. Thus, to the user it appears as if an operation is completed every clock cycle even though the memory access requires two clock cycles.

In another embodiment, a memory partitioned to include at least one parity block may be associated with a latency cache that stores data in response to previous read operations performed by the memory. Subsequently, the memory may receive a read-modify write command which instructs the memory to perform a write operation that updates value of the data that was previously read from the memory. For example, the read-modify write command may store in the memory an updated value of a counter that was incremented. The data stored in the latency cache during the previous read command may be accessed once the read-modify write command is received in order to update a value stored in the parity block. Doing so, permits the memory to perform other operations during the read-modify write, such as a separate read operation, without having to add duplicative hardware or memory blocks with additional read or write ports.

In still another embodiment, write speeds are improved through a set-associative organization of memory blocks. Write access is increased by partitioning memory into blocks, and associating an additional block of equal size with the primary data blocks in a set-associative manner. For example, if the set includes four blocks to which data for an address may be written, then a fifth, additional block is added. These five blocks form an associative set. Providing an additional memory block ensures that a free block is always available when two conflicting write operations are performed. For example, if each memory block can perform only one write operation per cycle but the two write operations provide addresses that both map to the same block, one write operation is performed in the originally addressed block while the other write operation is performed in the additional memory block. In this manner, the memory can perform two writes in the same cycle, regardless of whether the received write addresses are assigned to the same memory block. Moreover, applications of this embodiment are not limited to ones that are set-associative. For example, embodiments may be adapted for use with a First-in-First-Out (FIFO) data structure. Further still, in one embodiment, the increased write performance due to the set-associative mechanism is expanded to include two additional memory blocks. Accordingly, the memory may perform three write operations in the same cycle even if all three received addresses are assigned to the same memory block. That is, because the two additional memory blocks guarantee that there are at least two available storage locations per associative set, the memory performs two of the three write operations in the available memory locations.

Description of Example Embodiments

The following description is presented to enable one of ordinary skill in the art to make and use the proposed techniques. Descriptions of specific embodiments and applications are provided only as examples and various modifications will be readily apparent to those skilled in the art. The general principles described herein may be applied to other embodiments and applications without departing from the scope of the disclosure. Thus, the present disclosure is not to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features described herein. For purpose of clarity, features relating to technical material that is known in the technical fields related to the proposed ideas have not been described in detail.

Further, a particular embodiment is described using a memory management unit on a network routing device configured to read from and/or write to a memory on the routing device. However, it should be understood that embodiments described herein may be adapted for a broad variety of memory or storage devices, including, e.g., DRAM, SRAM, or SDRAM memory modules (or other memory modules), disk drives, flash memory devices, or networked storage devices, etc. More generally, any memory or storage space that can be partitioned, logically or physically, into a group of blocks can be adapted to use the techniques described herein to increase read/write performance. Accordingly, references to the particular example of a memory management device on a network routing device are included to be illustrative and not limiting.

FIG. 1illustrates an example computing infrastructure100, configured according to certain embodiments of the present disclosure. As shown, a routing device110includes an uplink to a network120. Note, the routing device may include multiple uplinks to the network120(e.g., multiple 10 Gb Ethernet ports). Additionally, the routing device110includes links to multiple clients1051-N. The routing device110is generally configured to route network traffic to/from the network120for the connected client devices1051-N. As described in greater detail below, the routing device100may include one or more memories and a scheduler configured to read/write data to the memories. For example,FIG. 2is a block diagram further illustrating the routing device110ofFIG. 1, according to certain embodiments of the present disclosure.

As shown inFIG. 2, the routing device110includes a memory205, and a forwarding table210, a central processing unit (CPU)/forwarding logic215, a controller/scheduler220and ports255. Of course, one of ordinary skill in the art will recognize that the depiction of a network routing device shown inFIG. 2is simplified to highlight aspects of the disclosure and further, that, in practice, network devices may be configured with a variety of additional functions, features and components.

In this example, ports225include both upstream ports, such as one or more high-speed uplinks (e.g., 10 Gb) to another network and also includes ports used to connect a collection of clients to the routing device110. The clients may be computing systems (e.g., servers in a data center) as well as other networking devices. CPU215provides a processing unit configured to forward traffic received over one of the ports225. The scheduler/controller220is configured to control the follow of data being written to or read from the memory205and/or the forwarding table210. For example, the controller220may write network data is received over one of the ports225to a buffer in the memory205. In response, the CPU215may request that the controller220read a memory address from the forwarding table210in order to determine a port over which to forward the traffic. That is, the forwarding table210generally provides a lookup table mapping ports on the device to the address of a device connected to a given port (e.g., mapping a port ID to a MAC address of a network interface card).

In one embodiment, the forwarding table210may be implemented as a ternary content addressable memory (TCAM) and the memory205may be any combination of fixed or removable memory chips or modules (e.g., DRAM, SDRAM, SRAM). Further, as described in greater detail below, embodiments of the disclosure provide a variety of techniques for configuring the controller220, memory205and/or forwarding table210in order in order to increase memory read performance and memory write performance.

For example,FIG. 3illustrates an example of a memory305configured to use a memory parity320block to increase read performance, according to certain embodiments of the present disclosure. As shown, the memory305is partitioned into four equal-sized blocks315, labeled A0, A1, A2and A3. Each memory block315may include a read port which allows the scheduler/controller310to read an address in that block. A variety of approaches may be used to partition memory305into blocks315, including, e.g., using a modulus or hash value and using uniform physical block splits. In one embodiment, a “memory block” is a unit of physical memory storage that includes at least one port or interface for receiving data for performing a read or write operation. For example, the memory block may include only one interface that may be used to either write data to the block or read data from the block during each cycle (i.e., a 1 R/W memory). Alternatively, the memory block may include a plurality of ports such as one read port and one read port that permit the block to perform a write operation and read operation in parallel during the same memory access cycle (i.e., a 1R1W memory). Nonetheless, in other embodiments, a memory block may be logical partition of a larger memory storage element.

In addition to the four blocks315, the memory305also includes a parity memory block320. The parity block320is sized to be same depth as each of the memory blocks315(whether partitioned logically or physically). The parity block320stores a parity result generated from the contents of a given address across all the blocks. As shown, the parity values run vertically, and a parity value may be obtained by performing a logical exclusive or (XOR) using the contents of an address in each of the blocks315. The resulting parity value is stored in parity block320. The parity value may be used to recover data for an address in the event of a failure in one of the blocks315. The parity value P stored in block320may be represented mathematically as follows:
P=A0⊕A1⊕A2⊕A3  (1)
where “⊕” corresponds an XOR operation. The value for an address in a given block320can be recovered by XORing the contents of the other blocks with the parity value. For example, a value stored in A0at a particular address can be recovered as follows:
A0=P⊕A1⊕A2⊕A3  (2)

In one embodiment, the parity block320is used to provide an additional user read port or channel, allowing the scheduler/controller310to perform two simultaneous reads from the same block to occur. That is, controller310has two available choices for reading a given memory address. First, the exact memory block in which an address is stored, and second, the remaining data and parity blocks.

In order to read two addresses simultaneously, the controller310first determines whether the addresses being read are present in different blocks315. If yes, i.e., if no read collision occurs, than the controller310reads the contents of two different blocks. Otherwise, if a collision occurs (i.e., the reads are for different addresses in the same block315) then one address is read from the target block and the other is read using the non-target memory blocks and the parity block. Accordingly, although not shown, the memory305may include two separate read ports for receiving two read addresses from the scheduler/controller310during each command cycle.

FIG. 4illustrates a method400for performing multiple read operations from a memory, according to certain embodiments of the present disclosure. As shown, the method400begins at step405, where the controller receives read requests. The requests may be stored in a read buffer associated with the controller. At step410, the controller selects the next two read operations to perform. At step415, the controller identifies a target block (logical or physical) associated with each of the two the read operations.

At step420, the controller determines whether the two read operations target the same block. If not (i.e., if the read operations target different blocks), then at step435, the controller reads a first address from a first target block and at step440reads a second address from a second target block. Otherwise, if the controller determines that the two read operations target the same block, then at step425, the controller reads a first address from the target block common to both addresses. And at step430, reads a second address from the target block by XORing the value from the identified address in each non-target block and the parity block. Thus, regardless of the whether two addresses target the same or different blocks, the memory controller can read two addresses during each read cycle.

Performing at Least Three Simultaneous Reads

Further, the approach of using a parity block to increase read access performance may be extended to higher dimensions. For example,FIG. 5illustrates an example of a memory505configured to use memory parity blocks520to increase read performance across multiple dimensions, according to certain embodiments of the present disclosure. As shown inFIG. 5, a memory505is partitioned into four blocks515, labeled A0, A1, A2and A3. Additionally, four parity blocks5201-4are used to determine a parity value from vertical or horizontal pairs of the blocks515. For example, parity block5201(P01) provides a parity value computed from blocks A0and A1. Similarly, parity block5202(P02) provides a parity value computed from blocks A0and A2. More generally, each block515is a member of two parity combinations, one running vertically and one running horizontally. This arrangement allows memory controller510to read three separate addresses from a memory block515simultaneously. For example, to read three separate addressees from block A0, the controller510reads a first address in A0directly, with the other two reads using the vertical and horizontal parity groups. That is, the controller510reads a second address as A0=P01⊕A1and reads a third address as A0=P02⊕A2.

One of skill in the art will recognize that the parity block approach to increasing read performance discussed above has many possible arrangements and is not limited to an arrangement of memory blocks in square or rectangular arrays. Consider, e.g., an array of seven memory blocks, in such a case, five parity blocks could be used to achieve a tripling of read performance by ensuring that each of the seven memory blocks is associated with two distinct parity groups. That is, to allow each of seven memory blocks to participate in two distinct parity groups requires five parity blocks. Similarly, using eleven parity blocks would allow each of the seven memory blocks to participate in three distinct parity groups, resulting in a quadrupling of read performance. More generally, each one of n-fold increases in read performance requires an additional parity group for each memory block.

Performing at Least Two Reads and One Write Simultaneously

The memory505may be used to perform at least two reads and one write simultaneously (2R1W), even if these three operations all map to the same memory block. Further, the read and write operations may have uncorrelated or random addresses—i.e., the reads and write are not dependent on each other. For this embodiment it is assumed that each of the physical memory blocks515,520in memory505have a dedicated read port (or interface) and a dedicated write port. That is, each memory block515,520is capable of performing one read and one write simultaneously (1R1W). Furthermore the blocks515,520may read an old value from, as well as write a new value to, the same address simultaneously. Table 1 illustrates one possible example of reading the values stored in Address X and Address Y and writing a new value to Address Z from memory block A0in parallel. Note that this example is not intended to be limiting but rather to illustrate the worst case scenario, i.e., performing two read and one write operations the map to the same memory block.

TABLE 1Reading from/Writing to Block A0Read Address XRead using read port of A0Read Address YRead using read ports of A2 and P02Perform the operation A2 ⊕ P02Write to Address ZWrite using write port of A0

To complete the 2R1W operations in one cycle, the parity blocks P02and P01must also be updated to reflect the new data value stored at Address Z. Focusing on P02, there are at least two ways of updating this parity block. One, the old values in blocks A0, A2, and P02corresponding to Address Z are retrieved and XORed, or two, the new value in A0and the corresponding value for Address Z in A2are retrieved and XORed. In either case, as shown in Table 1, the read ports of A2and P02are already occupied performing the reads for the values corresponding to Address Y and cannot be used in the same cycle to read the values corresponding to Address Z.

Instead, the two dimensional structure of memory505permits 2R1W operations, as well as updating both of the parity blocks, to occur simultaneously by using the other parity blocks to update P01and P02. Stated in general terms, these two parity blocks may be updated using the following logic:
New P02=Old P02⊕Old A0⊕New A0  (3)
New P01=Old P01⊕Old A0⊕New A0  (4)

New P02and New P01represent the updated values that are stored in these blocks in response to the new data being written into Address Z in A0. Old P02and Old P01represent the old values written in P02and P01that correspond to the old data in Address Z before the memory505received the write command. Old A0represents the old value stored at Address Z in A0while New A0represents the new value that is currently being written into Address Z in A0.

New A0is known since it was received by the scheduler/controller510when 2R1W operations began. Old A0, however, is derived since the read port of A0is busy retrieving the value stored in Address X as shown in Table 1. One possible example of deriving Old A0is as follows:
Old A0=A1⊕Old P01  (5)

When performing the logic illustrated in equation 5, the controller510uses the read ports of A1and P01to retrieve the values corresponding to Address Z to derive the old value stored at Address Z in A0. This derivation avoids having to retrieve the old value of Address Z directly from A0.

Moreover, in the embodiment shown in Table 1, the controller501is unable to retrieve the value of Old P02directly from that memory block, since the read port of P02is being used to fetch the value corresponding to Address Y. Thus, the controller501may derive Old P02as follows:
Old P02=Old P13⊕Old P23⊕Old P01  (6)

As shown, Old P02is derived by reading the corresponding values stored in P13, P23, and P01. Thus, XORing the different parity memory blocks520permits controller510to derive the value corresponding to Address Z in P02. Note that in this embodiment, the value read from P01is being used at least twice: once to derive Old A0and once to derive Old P02. However, because the same value is being retrieved from P01, only one read port is needed. That is, the controller510simply copies and routes the data retrieved via the read port of P01to logic necessary to derive both Old A0and Old P02, and thus, memory block P01needs only one read port.

Once Old A0and Old P02are derived using equations 5 and 6, respectively, the controller501may use these values to perform equation 3 and find the updated or new value of P02. For example, the controller510may use the following logic to derive New P02by substituting equations 5 and 6 into equation 3:
New P02=(P13⊕P23⊕P01)⊕(A1⊕P01)⊕New A0  (7)

Moreover, equation 7 can be further reduced since the two occurrences of P01nullify each other:
New P02=P13⊕P23⊕A1⊕New A0  (8)

A similar process may be followed to derive the new value of P01using equation 4. However, Old P01does need to be derived from the values stored in the other parity memory blocks as done to derive Old P02in equation 6 since Old P01is currently being read from P01's read port as shown in equation 5. Accordingly, equation 4 may be rewritten as:
New P01=Old P01⊕(A1⊕Old P01)⊕New A0  (9)

In equation 9, equation 5 is substituted into equation 4 to yield New P01. In this manner, the controller510may perform the logic detailed in equation 8 and 9 to yield the new, updated values associated with Address Z in each of the parity blocks5201and5202. The controller510then writes these values into the respective parity blocks5201and5202using their respective write ports while simultaneously performing the 2R1W operations.

Equations 3-9 and the example shown in Table 1 are for illustration purposes only. One of ordinary skill will recognize the different manner in which a multi-dimensional memory may be used to perform two reads and one write whose addresses are associated with the same memory block. Moreover, different logic may be employed to find the various data required to update the parity blocks. For example, instead of using equation 9 to find New P01, this value may be derived as follows:
New P01=A1⊕New A0  (10)
Performing at Least One Read and One Read-Modify Write Simultaneously

Many memory systems write data that was modified based on a previous read. For example, a counter retrieves data from a memory, increments the data, and stores the incremented data in the same address. Other computational functions, such as statistical data or a MAC learn for updating routing data, also perform a similar operation where retrieved data is updated and written back into memory in a later operation. In this manner, the later in time write operation is based on a read operation that occurred in a previous memory access cycle. As used herein, this type of write is referred to as a “read-modify write”. The previous read is an indicator that a subsequent write will occur. Stated differently, the read-modify write is dependent on the previous read.

FIG. 6Aillustrates a memory system600for performing a read-modify write. In one embodiment, the scheduler/controller610is configured to perform a read-modify write and at least one read operation in parallel. Moreover, the read-modify write and the read operation may be independent. That is, the read-modify write and the read operation may be random accesses that are unrelated. However, the read-modify write may be related to a read operation that was performed in a previous cycle.

The latency cache620stores some of the data associated with previous read operations in the memory605. For example, if the controller610used the memory blocks A1and P to derive a value stored in A0, the value retrieved from A1, P, the derived value of A0, or combinations thereof may be stored in the latency cache620. Furthermore, the latency cache620may index the stored data based on the address associated with the read operation. For example, if the read operation requested the value stored at Address X on A0, the cache620may use Address X to provide an index for the data stored in the cache620. Thus, a later read-modify write that writes a modified value to Address X can access the cache620to retrieve the previously stored data. However, in other embodiments, different identifiers may be used to index data in the latency cache620such as a cycle number or a time stamp. In general, the identifiers permit a subsequent read-modify write operation to locate related data stored in the latency cache620.

As shown, each memory block615,617in memory605is a 1R1W memory with separate read and write ports or interfaces that permit the memory605to read data from and write data to the blocks615,617in parallel. Moreover, the system600includes the parity block P617for enabling two read accesses to be performed in parallel. Although not shown, the system600may include a multi-dimensional structure like, for example, the memory505shown inFIG. 5. By extending the dimension of the structure and adding other parity blocks—e.g., column parity blocks, the system600may be expanded to support more complex parallel operations such as three reads and one read-modify write.

In one embodiment, the scheduler/controller610indentifies when it performs a read operation that retrieves data from an address that will later be used for a read-modify write. For example, the scheduler610may include a separate port that receives read commands that will be followed by a read-modify write operation to the same address. Each time the scheduler610receives a read command at that port, a portion of the data retrieved is stored in the latency cache620. Alternatively, when decoding a read command, the controller610may identify a type of the command. If the read type indicates that the command will be followed by the read-modify write, the control610stores some portion of the data in memory605into the cache620.

Table 2 illustrates an example of using the latency cache620to perform a read-modify write operation.

TABLE 2TimeOperation(s)Latency Cache ActionTime 1Read Address X of A0Store corresponding valueof A1Time 2Read-modify write newRetrieve value of A1 tovalue to Address X of A0update parity block P

At time1, the controller610receives a command to perform a read operation on Address X of A0. While performing this operation, the controller610determines that the read data is related to a future read-modify write and stores a least a portion of data associated with Address X into the latency cache620. In the example illustrated in Table 2, the controller610stores the value of A1that corresponds to Address X of A0into the latency cache620. The cache620may also a store an identifier into the latency cache620to enable the controller610to locate the data when the related read-modify write operation is performed.

After the read operation is performed, the controller610transmits the retrieved data to the computing element that requested the data. For example, the computing element may be a counter, statistical application, MAC learn application, and the like. Once the retrieved data has been modified, at time2, the computing element instructs the controller610to perform a read-modify write operation to store the modified data back into Address X. Although time2may be the next sequential cycle to follow the read operation performed at time1, this is not a requirement. Between time1and time2, the memory system600may have performed a plurality of different operations and stored data to the latency cache620that is related to different read-modify write operations.

When performing the read-write operation, the controller610writes the modified data to Address X of A0. Additionally, the controller610updates the corresponding location in the parity block P based on the value stored at Address X. One technique of updating the parity block P is XORing the corresponding values in A0and A1as shown in equation 1. The value of A0was received at the controller610along with the read-modify write command and the value of A1may be retrieved using A1's read port. Using A1's read port, however, means the controller610is unable to use the read port of A1for a different read. For example, to perform one read and one read-modify write operations in parallel, if the read operation requests data stored in A1, either this data cannot be retrieved or the parity block P cannot be updated. Accordingly, if the one read and one read-modify write operations are unrelated (i.e., random) then, in certain situations, the memory605in unable to perform the two operations in parallel.

Alternatively, the controller610may rely on data stored in the latency cache620to perform a read operation and read-modify write operation simultaneously, regardless of which memory blocks615map to the received addresses. Specifically, instead of using the read port of A1to retrieve the necessary data to update parity block P, the controller610may use an identifier to index into the latency cache620and retrieve the value of A1that was stored during time1. Accordingly, if the read operation instructs the controller610to retrieve data stored in A1, the controller610is free to do so. For example, controller610may use the address of the read-modify write operation (e.g., Address X) to hash into latency cache620and retrieve the value of A1stored previously. The controller610XORs this value with the modified value and writes the result in P using the parity block's write port. In this manner, the read operation may access any of the read ports of the memory605, even including the read port of parity block P.

Table 3 illustrates another example of using the latency cache620to perform a read-modify write operation for any number of memory blocks.

TABLE 3TimeOperation(s)Latency Cache ActionTime 1Read Address X of A0Store value of Address Xin A0 and correspondingvalue in PTime 2Read-modify write newRetrieve values stored atvalue to Address X of A0Time 1 to update parityblock P

As shown inFIG. 6B, the memory system601includes components similar to the components shown inFIG. 6A, however, instead of having only two memory blocks615with the parity block P617, any number of memory blocks615(A0through AN) may be associated with a single parity block in the memory606.

At time1, the controller610performs a read operation to retrieve the value stored at Address X in A0. In response to this operation, the controller610also stores the retrieved value of Address X and the corresponding value of P into the latency cache620and transmits the retrieved value to the requesting computing element.

After modifying the retrieved value, the controller610receives a read-modify command at time2to store the modified data into Address X. In addition to writing this information into A0, the controller610updates the parity block P to reflect the modified data. However, if the controller610simply XORs the modified data with the corresponding values stored in A1through AN, this prevents those read ports from being used to perform one or more simultaneous read operations. Accordingly, the controller610may retrieve the stored values in the latency cache620to update the corresponding value in P using the following logic:
New P=Old P⊕Old A0⊕New A0  (11)

Old P and Old A0represent the values that the controller610stored in the latency cache620during time1. New A0is the modified data received by the controller610and the New P is the updated value corresponding to Address X that is then stored in parity block P. In this manner, the read ports for all the memory blocks615in memory606remain available to perform at least one read operation in parallel to the read-modify write operation.

In one embodiment, instead of storing Old P and Old A0in the cache620, at time1, the controller610may save the values of A1-AN corresponding to Address X into the latency cache. Thus, when updating the parity block P, the modified value of A0and the stored values of A1-AN may be XORed. Further still, in another embodiment, the controller610determines which values are stored in the cache620based on read port availability. For example, in addition to retrieving data from A0, assume at time1the controller610also performed a read operation that fetches data from parity block P corresponding to a different address. Because the read port of P is busy, the controller610instead stores into the latency cache620the values of A1-AN which are then used to update P as shown by equation 1.

Similarly, the method shown in Table 2 may be modified such that the value corresponding to Address X of A0and the correspond value in P are saved rather than only the value in A1if, for example, the read port of A1was busy at time1. Thus, the parity block in the example shown in Table 2 may also be updated using logic similar to that shown in equation 11.

Performing at Least Two Simultaneous Write Operations

The write performance may be increased by dividing the memory into blocks and then adding an extra memory block. For example,FIG. 7illustrates an example architecture700used to increase write performance according to certain embodiments of the present disclosure. As shown, a memory705is partitioned into four equal-sized blocks715, labeled A0, A1, A2and A3. In this example, each block715provides an address space of 64 values—resulting in a total address space of 256 useable addresses in memory705. Corresponding addresses in each block forms a 4-way set. For example, the memory addresses at locations59,123,187and251together form a set. In this case, a set may be identified using six lower-order bits of an address in the 0-255 range. For example, the six-lower order bits of 59, 123, 187 and 251 are the same in binary—111011. Because the two most significant bits in the full 8 bit address are not used as physical address of memory705, the full 8 bit address may be referred to as virtual address.

Additionally, memory705includes a spare block725, also 64 addresses deep. The useable size of memory705remains 256, but using five blocks to store a 4-way set, as depicted for memory705, guarantees that at least one location in any set is always unoccupied. In other words, the spare block725creates an additional write port for the memory705. The spare block725ensures that scheduler/controller710can always perform two write operations during a given read/write cycle.

More generally, to gain a write port (i.e., write port WB), a memory of useable depth of D may be partitioned into X blocks each with a depth of D/X. In the example ofFIG. 7, X=4, D=256, and thus D/X=64. Accordingly, blocks715are each 64 addresses deep. Note, each block may also have the same bit-width W. Once partitioned into X blocks, a spare memory block725of D/X depth and width W is added to the memory. Moreover, in one embodiment, each of the memory blocks715are one read or one write physical memories (1R/W). In this case, the architecture700permits at least one read and one write or two writes in the same cycle. In another embodiment, each of the memory blocks715are one read and one write memories (1R1W). Here, the architecture700permits at least one read and two writes to occur simultaneously. The following discussion is based on using 1R1W memory blocks715that enable 1R2W per cycle, although the present disclosure is not limited to such.

The controller710uses the one read and two write ports to transmit up to three unique addresses to the memory705. If the two write addresses are stored on different memory blocks715than there is no conflict and the three operations may be performed in parallel. However, if the write addresses map to the same block715, then there is a conflict. Specifically, the memory705uses the memory ID table720to identify write conflicts. The memory ID table720includes a table that correlates each address in the addressable memory space (D=256) to a particular memory block715which stores the value corresponding to that address. For example, the address of WAand the address of WBare compared to determine whether the addresses are assigned to the same block715. If so, a conflict exists and the memory705can write only one of the values corresponding to WAand WBto the identified memory block715. The spare block725ensures, however, that there exists at least one alternative location where the other value can be written. Moreover, the memory ID table720may include two identical copies of the memory mapping (e.g., two separate physical memory blocks) to permit the addresses received on ports WAand WBto be evaluated in parallel.

After detecting a conflict, the memory705uses the freelist array730to identify the memory block715with the available memory location. The freelist array730is guaranteed to identify at least one memory location where the conflicting write may be performed. As shown, the freelist array730includes one memory block735that corresponds to each of the blocks715—i.e., block7351corresponds to A0, block7352corresponds to block A1, and so forth. Accordingly, the memory blocks735may have the same depth as the memories715(i.e., D/X=64). Assuming WBis chose to be written to a different memory block715, the memory705may use the 6 least significant bits (LSB) of the address sent to the memory705on write port WBto index into each of the freelist memories7351-5. One of the five memories735is guaranteed to have a memory location that is available or free. For example, the freelist memories735may store a one if the location is free (invalid) or a zero if the location is taken (valid). In one embodiment, once the memory705is initialized, all of the memory locations in the spare block725are free while the memory locations in the other memory blocks715(i.e., A0-A3) are taken. Thus, once the first conflict occurs, one of the write operations is performed into the spare block725. However, after continued operation, two simultaneous write may both map to the spare block725which would require at least one of these write operations to be performed in a different memory block715.

FIG. 8illustrates a method of performing two simultaneous writes, according to certain embodiments of the present disclosure. For clarity, method800will be described with reference the memory architecture700discussed inFIG. 7. Method800begins at block805where the memory705receives two write commands on two separate write ports—e.g., WAand WB. At block810, the memory determines whether the two write commands map to the same memory block715. For the discussion here, assume that port WAreceives Address X and WBreceives Address Y which both map to A0. That is, the memory705uses the memory ID table720to determine which memory block or blocks715store the data associated with Addresses X and Y. If the addresses map to different memory blocks715, at block815the method800uses the individual write ports of the identified memory blocks715to perform the write commands. If the addresses map to the same memory block715, however, there is a conflict.

At block820, the memory705uses the LSBs of Address X and Y to identify at least one memory block715with a free memory location. The number of LSBs needed is dependent on the depth of the memory blocks715in the memory705. As shown inFIG. 7, only the six LSBs are needed to address each row in the memory blocks715(i.e., identify a 4-way set), and thus, each memory735in the freelist array730is 64 rows deep. However, this architecture may vary depending on the particular memory architecture.

At least one of the received write addresses—e.g., Address Y—is compared to the memories7351-5in the freelist array730to determine a free memory location. That is, one of the five memories7351-5includes an invalid or free bit corresponding to each set in the memory705—i.e., there are at least 64 invalid memory locations in the memory blocks715. In this manner, the six LSBs of Address Y may be used to identify which memory block715has the free memory location for that particular set.

At block825, the memory705writes one of the commands to the original memory block715and the other command to the memory block715with the free memory location. For example, the memory705may write the value received on port WAto the memory block715identified in the memory ID table720but use the freelist array730to determine a free location for the value received on port WB. State differently, the memory705moves, or assigns, Address Y that was received on port WBto a different memory block715.

At block830, the memory705updates the memory ID table720and the freelist array730to reflect that Address Y has moved to a different memory block715—e.g., from A0to A3. Specifically, the memory ID table720now indicates that Address Y is located in A3while the freelist memory7355corresponding to A3now has a valid or taken bit corresponding to the six LSBs of Address Y. Moreover, the freelist memory7351corresponding to the previous location of Address Y—A0—is updated to contain the invalid or free bit. Thus, if Address Y needs to be moved again because of a conflict, the memory ID table720and freelist array730reflect that Address Y is now stored in A3and that A0contains a free memory location for the set. In this manner, the memory ID table720and freelist array730work in tandem to translate logical addresses—i.e., addresses received at the write ports—to physical addresses—i.e., the particular memory blocks715where the values corresponding to the addresses are stored. Thus, any application reading data from or writing data to memory705does not know which memory block715actually stores the value corresponding to the read or write address.

Performing at Least Three Simultaneous Write Operations

FIG. 9illustrates memory architecture for performing three simultaneous writes, according to certain embodiments of the present disclosure. Specifically, the architecture900expands the architecture700shown inFIG. 7to include at least two additional spare blocks9251,2. Moreover, the memory translation unit—i.e., the memory ID tables9201,2and the freelist array930—are reconfigured to handle a cycle where three write operations map to the same memory block915. That is, the memory905receives three different addresses on write ports WA, WB, and WCthat each map to the same memory block915. Although the following discussion focuses on the worst case scenario—receiving three write operations that map the same memory block915—the memory905is able to perform three simultaneous write operations if there is a conflict between only two of the write port addresses or if there are no conflicts.

Like inFIG. 7, the memory905includes a total addressable space of 256 addresses but use two spare blocks9251,2to expand the memory905to include 384 memory locations to enable simultaneous writes for conflicting write operations. Memory905includes two different memory ID tables9201,2for detecting and managing conflicts. Each memory ID table9201,2includes a memory ID array922and memory validity array924. The memory ID arrays9221,2include at least four memory blocks9231-4that correspond to the number of read and write ports of the memory905. As shown here, the memory ID arrays9221,2have respective memory blocks9231-4for the read port (R) and the three write ports (WA, WB, and WC). In general, the addresses received on read and write ports are sent to the respective memory blocks9231-4to determine a corresponding memory block915tasked with storing the value of that address.

The memory validity arrays9241,2includes four memory blocks9251-4that each correspond to a memory block9231-4in the memory ID arrays9221,2—e.g., memory block9251corresponds to memory block9231, memory block9252corresponds to memory block9232, and so forth. The addresses for each of the read and write ports (or some other identifier) are used to index into the memory units9251-4and determine if the memory block915identified in the memory block923of the memory ID array922is valid. For example, if Address X is received on write port WA, memory unit9232may reflect that Address X is assigned to A2, but if the memory block9252in the memory validity array924stores an invalid bit corresponding to Address X, then the memory905disregards the information retrieved from the memory block9232in the memory ID array922. For each address received on the memory's905ports, only one of the two storage locations produced by the two memory ID arrays9221,2will be valid. That is, for any given address, only one of the memory ID tables9201,2stores in the memory ID array922the correct memory block915while the other memory ID array922stores an invalid memory location. In this manner, the depth of the memory blocks9231-4and9251-4are at least as deep as the total addressable memory of the memory905—e.g., 256. However, memory blocks9251-4may be narrower in width than memory blocks9231-4since the blocks9251-4may only store a validity bit while memory blocks9231-4may store a three-bit code for uniquely representing each of the memory blocks915. The reason for maintaining two memory ID tables9201,2will be discussed later.

If comparing the valid memory locations retrieved from the memory ID tables920indicate at least one conflict, the memory905uses the freelist array930to determine a suitable substitute memory block915for the conflicting addresses. In the case of three write addresses mapping to the same memory block915, the freelist array930uses one or more of the write addresses—e.g., the write addresses received at ports WBor WC—to index into the memory units9321-6. These units9321-6include one or more memory blocks that are indexed using the addresses received on the memory's905write ports. Providing at least two memory blocks in each unit932ensures that two received address can be indexed in the same cycle. That is, the memory blocks may have only one read port, and thus, to determine whether the corresponding memory block915has an available memory location the memory units9321-6include at least two identical memory blocks.

However, if only two of the write addresses conflict, then only one of the conflicting addresses is used to index into the freelist array930. For example, if the addresses received on ports WBand WCconflict, then value received at the data port (not shown) of WBmay be written to the memory location provided by the memory ID tables920while the address of port WCmay be used to index into the memory units9321-6to identify an available memory location to store the value received on the data port (not shown) of WC.

As discussed, each of the memory units9321-6in the freelist array930corresponds to a memory block915. That is, memory unit9321corresponds to A0, memory unit9322corresponds to A1, and so forth. Based on the memory configuration shown inFIG. 9, the six LSBs (64 unique memory locations) of the received address are used to index into the memory blocks of the memory units9321-6. The memory blocks store a free/taken bit corresponding to the LSBs (i.e., a free/taken bit per row of the memory blocks) that represents whether that particular memory location in the corresponding memory block915is available. Because the memory905includes two spare blocks925, at least two memory locations for each 4-way set in the memory blocks915are guaranteed to be available. By searching each memory unit9321-6of the freelist array930, the memory905identifies at least two free memory locations for each the addresses received on write port WBand write port WC. The freelist array930may have further logic to ensure that the same substitute memory block915is not selected for the received addresses.

Moreover, the addresses may map to the same memory blocks915even if the addresses are not part of the same set. For example, the freelist array930may identify that A0and A2have available memory locations for the address received on write port WBand A2and Spare Block1include available memory locations for the address received on write port WC. Because in one embodiment each memory block915can perform only one write per cycle, the memory905may write the data value corresponding to port WBto A2but write the data value corresponding to port WCto Spare Block1.

As discussed relative toFIG. 9, memory unit932stores data to enable simultaneous indexing using two different addresses. Thus, the memory blocks in memory unit932should be updated when memory address are moved or assigned to different memory blocks915. For example, if all three write addresses map to A0but the memory905decides to move two of those addresses (e.g., Address Y and Z) to A1and A2, then the memory blocks in memory unit9321, memory unit9322, and memory unit9323are updated. In regards to the memory blocks in memory unit9321, the availability bits corresponding to Address Y and Z need to reflect that these memory locations are now available. However, this requires two writes to be performed in memory unit9321. If the memory blocks in memory unit9321are implemented using 1R/W or 1R1W memories, these memories are incapable of performing the two writes necessary to change two validity bits in the same cycle.

FIG. 10illustrates a memory architecture for updating the memory units in a freelist array, according to certain embodiments of the present disclosure. Specifically,FIG. 10illustrates a single memory unit932of the freelist array that uses four memory blocks1015to ensure each memory unit932can update two availability bits in the same cycle—i.e., in parallel. As shown, the memory unit932includes four physical memory blocks1015—X0, X1, Y0, and Y1—that are 1R1W memories, although the present disclosure is not limited to such.

Memory unit932includes two read interfaces for receiving the addresses associated with ports WBand WC. Each read interface couples to two of the memory blocks1015. As shown, the LSB portion of a received address is used to index into two of the memory blocks—X0and X1or Y0and Y1—using their respective read ports. The resulting availability bit is then transferred to the OR gates1050and used to determine whether the memory block915inFIG. 9corresponding to the memory unit932has an available memory location at that address. For example, if either memory block X0or X1returns a “1”, the memory unit932indicates that the memory location is available or free. However, if both memory blocks X0or X1return a “0”, the memory unit932indicates that the memory location is taken and is not a suitable memory block915for storing the value received at the write port.

Assume that all three addresses received on ports WA, WB, and Wc conflict and map to memory block A0shown inFIG. 9. If the memory unit shown inFIG. 10is the memory unit9321that corresponds to block A0, Status WBand Status WCsignals both yield a “0”—i.e., the memory locations are taken. Further assume that the addresses associated with WBand WC—Address X and Address Y, respectively—are moved to memory block A1and A2, respectively. This means that the memory locations corresponding to the LSBs of Address X and Y in A0are now invalid. To update the memory unit932associated with A0, Address X and Y are transmitted on the Free WBand Free WCsignals, respectively. The Free WBsignal writes a “1” into the rows of X0and Y0that correspond to the LSB portion of Address X, while Free WCsignal writes a “1” into the rows of X1and Y1that correspond to the LSB portion of Address Y. The next time these address are received on either of the WBor WCports, at least one of the memory blocks1015will return a “1” to indicate the memory location is now available. For example, if Address Y is subsequently received on port WB(instead of port WC), once this address reaches the read interface of memory unit932, X1returns a “1” since this block1015was changed by Free WCin a previous cycle, but X0may return a “0” since this block1015was not changed by Free WBor Free WC. Nonetheless, the OR gate1050reports that the memory location is available in the corresponding memory block915. Accordingly, when Address X or Y are received on either of the write ports, the Status WBand Status WCsignals return a “1” indicating the memory locations for both of these addresses is available.

Continuing the example above, assume that the memory unit932shown inFIG. 10is the memory unit9322corresponding to the memory block A1. Because the address of port WBwas moved to memory block A1, the memory unit932is updated to reflect that the once unavailable memory location corresponding to Address X is now taken. Accordingly, while the received value is stored into A1, the memory unit932transmits the LSBs of Address X on the Taken signal. This writes into all the memory blocks1015the taken bit (e.g., “0”) to indicate the memory location is unavailable. The same update may be performed on the memory unit932corresponding to the memory block A2—i.e., the new location of Address Y received on port WB. In this manner, the circuit schematic shown inFIG. 10may be repeated for each memory unit9321-6inFIG. 9to enable at least two reads and two writes during one cycle to track and update the availability of the memory locations in the memory blocks915.

InFIG. 10, the taken signal is mutually exclusive with both the Free WBand Free WCsignals. For example, the memory905may control the selector signals to the multiplexors to ensure the taken signal is never applied with either of the Free WBor Free WCsignals. The Free WBand Free WCsignals, however, may be active simultaneously (in the case of three-write conflict) or one at a time (in the case of a two-write conflict).

In addition to updating the different memory units9321-6in the freelist array930, the memory ID tables9201,2are also updated to reflect the changes made in where the addresses are stored. Returning toFIG. 9, the memory905includes two memory ID tables9201,2that each contain a memory ID array9221,2with four memory blocks9231-4and9235-8corresponding to the four read and write ports of the memory905. The memory905includes two copies of the memory ID table920(which may or more not store identical data in the memory ID arrays9221and9222) for enabling the new location of the two addresses to be updated in parallel. For example, if there was only one memory ID table920but two addresses (e.g., Address X and Address Y) were moved to two different memory blocks915, each memory block9231-4in the memory ID array922would need to be written to twice: once to indicate the new assigned block915for the address received on WBand again to indicate the new assigned block915for the address received on WC. However, the memory blocks9231-4may be 1R1W memories, and thus unable to perform two writes in the same cycle. Accordingly, providing two memory ID tables9201,2enable the memory905to update one of the locations of the received address on one the tables920and the other location on the other table920. That is, the memory905updates the four memory blocks9231-4to reflect the new memory location (i.e., the three bit memory block identifier) of the address received on port WBwhile the four memory blocks9235-8are updated to reflect the new memory location of the address received on port WC.

However, this process results in both of the memory ID tables9201,2storing inaccurate data. For example, if Address X was moved to A1and Address Y was moved to A2, memory ID table9201may be updated to reflect the change of Address X but then would not reflect the fact that Address Y has moved. The reverse would be true for memory ID table9202. Accordingly, each memory ID table9201,2includes a memory validity array9241,2which indicates if a memory location stored in one of the memory blocks923in memory ID array922is valid. If memory ID table9201was updated to reflect that Address X is now located in A1and memory ID table9202was updated to reflect that Address Y is now located in A2, the memory905updates the memory block925in memory validity array9241corresponding to Address Y to store an invalid bit and updates the memory block925in memory validity array9242corresponding to Address X to store an invalid bit. Moreover, if necessary, the memory905may update the memory blocks925in the memory validity arrays9241and9242corresponding to Address X and Address Y, respectively, to store valid bits.

When subsequent commands are received on the read and write ports, the memory905queries both memory ID tables9201,2to determine the memory blocks915which store the data associated with the received addresses. Each memory ID array9221,2returns a memory location (i.e., a memory block915) for each received address. However, only one of these memory locations is valid as determined by using the received address to query the memory blocks925in the memory validity arrays9241,2. So long as the memory905queries both memory ID tables9201,2when read and write addresses are received, the memory ID tables9201,2return a single valid memory location. Moreover, each memory block9231-8and9251-8will at most perform one write during any given cycle, thereby enabling the memory905to perform at least three writes simultaneously.

FIG. 11illustrates a method for performing at least three write simultaneously, according to certain embodiments of the present disclosure. The method1100is described below with references to the architecture illustrated inFIG. 9. At block1105, the memory905receives three write commands on three separate write ports WA, WB, and WC. The memory905routes the addresses received on these ports to the two memory ID tables9201,2where the addresses are used to index into the memory ID arrays9221,2. Specifically, each address of the read and write ports is assigned to one of the memory blocks9231-8, and thus, can be accessed in parallel. Moreover, the memory905also routes the received address to the memory blocks9251-8in the memory validity array9241,2which indicates if the corresponding memory location identified by the memory blocks9231-8in the memory ID arrays9221,2are valid. In one embodiment, only one of the memory ID arrays9221,2will store valid data for any particular address.

Once the valid memory locations of the received addresses are determined, at block1110the memory905determines whether there is a write conflict. This may either be a two-write conflict or a three-write conflict. However, for simplicity, it is assumed the received write addresses are a three-write conflict—the memory ID tables9201,2indicate that the addresses all map to the same memory block915. If there is not a two-write or three-write conflict, at block1115the memory905performs the write commands on the three separate memory blocks indentified by the memory ID tables9201,2.

As shown inFIG. 9, the memory905may receive a read command as well as three write commands. Because each of the memory blocks915,923, and925inFIG. 9may be 1R1W memories, the memory905may perform the read command in the same cycle as the three write commands. To do this, the memory905routes the received read address to the memory ID arrays9221,2which will result in one valid memory location. Once that memory location is determined, the memory905accesses the respective memory block915, retrieves the data, and transmits the data to the scheduler/controller910.

If there is a write conflict, at block1120, the memory905uses a LSB portion of at least two of the received write addresses to search the different memory units9321-6of the freelist array930. Because the memory blocks915include two spare blocks9251,2, the memory905is guaranteed to include at least two available memory locations on two different memory blocks915per address, or more specifically, at least two available memory locations on two different memory blocks915per each possible LSB portion of the received address. In the embodiment shown inFIG. 9, the memory905includes two available memory locations for 64 possible bit combinations—i.e., 6 LSBs. Thus, even if the two received address have the same 6 LSBs, the memory905contains the requisite number of available memory locations (on different memory blocks915) to move the addresses. As noted above, this configuration may be changed to suit any addressable memory space.

Once the freelist array930identifies suitable substitute memory blocks915, at block1125, the memory905performs the write commands on these substitute blocks915. Thus, each of the write commands is performed on different memory blocks915. Once the memory905is initialized and begins to operate, the first time there is a conflict, the spare blocks9251,2may be used as the substitute blocks; however, as the memory905continues to detect conflicts, the selected substitute blocks may vary between any of the individual memory blocks915.

As a result of changing the addresses to different memory blocks, at block1130, the method1100updates the memory ID tables9201,2and freelist array930to reflect that the addresses' values are now being stored on different memory blocks915. Depending on the capabilities of the underlying memory blocks making up the memory ID tables9201,2(i.e., the number of independent read or write ports), the memory905may include two separate memory ID tables9201,2where one table is updated to reflect that one of the addresses was moved and the other table is updated to reflect that another address was moved.

In one embodiment, the freelist array930may be similar to the memory ID tables9201,2where the memory905maintains two copies of the array930. Alternatively,FIG. 10illustrates an embodiment where instead of maintaining two copies, the freelist array930may include four memory blocks (X0, X1, Y0, and Y1) that correspond to one of the memory blocks915. As shown in that figure, the mutually exclusive Free and Taken signals update at least two of the memory blocks1015when changing the availability bits. So long as at least one of the availability bits in the memory blocks1015indicates that the memory location is free, the memory905knows it is able to use the corresponding memory block915as a new location for the received address. Because two spare blocks9251,2are used, each memory address (or a LSB portion of a memory address) is guaranteed to include at least two available memory locations on two separate memory blocks915. For example, if Address X is moved from A0to A2, the memory unit9321is updated to store a free bit at Address X in two of the memory blocks while memory unit9323is updated to store a taken bit at Address X in two or more of the memory blocks. In this manner, the memory905is capable of performing one read and three write operations for four independent addresses as well as updating the memory elements that track and maintain the address translation functions.

In sum, embodiments presented herein include a memory for performing at least two read and one write operation in parallel. The memory may include a plurality parity blocks that are based on the data stored in other sub-blocks in the memory. When updating one of the parity blocks in response to the write operation, the other parity blocks may be used in a XOR operation. In another embodiment, a memory performs at least one read and one read-modify write operation in parallel. Here, the memory includes a latency cache for storing data from a previous read operation. The stored data is then accessed during the subsequent read-modify write operation which enables the memory to perform a read operation to any of the sub-blocks in parallel with the read-modify write. In another embodiment, a memory may include two spare sub-blocks that expand the total memory capacity to exceed the addressable space of the memory. The spare blocks ensure that there are at least two available memory locations for each associative set in the memory. Accordingly, if three addresses map to the same sub-block, the memory assigns two of the addresses to available memory locations on a different respective sub-blocks, thereby permitting the write operations to be performed in parallel.