Patent Description:
<CIT> discloses an apparatus, system, and method for destaging cached data.

The claimed subject-matter is defined in the independent claims.

It has been recognized that achieving high-level communication performance at a node of a packet-based communication system, even under drop and congestion scenarios, requires efficient storage support for a large number of outstanding packets where each request could be as large as Maximum Transmission Unit (MTU) size. In view of the desire for efficient packet storage support, the presently disclosed technology is provided.

In accordance with the presently disclosed technology a packet cache configuration provides efficient data management for spillover from cache memory to non-cache memory (e.g., on-chip SRAM to off-chip DRAM), and provides a transparent interface to the user independent of the data storage location (e.g., on-chip or off-chip).

In one aspect, the technology provides a packet cache system including a cache memory allocator for receiving a memory address corresponding to a non-cache memory and allocated to a packet, and associating the memory address with a cache memory address; a hash table for storing the memory address and the cache memory address, with the memory address as a key and the cache memory address as a value; a cache memory for storing the packet at a location indicated by the cache memory address; and an eviction engine for determining one or more cached packets to remove from the cache memory and place in the non-cache memory when occupancy of the cache memory is high.

In another aspect, the technology provides a method for storing packets in a cache memory of a device, including allocating a memory address, corresponding to a non-cache memory, to a packet; associating the memory address with a cache memory address; storing the memory address and the cache memory address in a hash table, with the memory address as a key and the cache memory address as a value; storing the packet in cache memory at a location indicated by the cache memory address; and when occupancy of the cache memory is high, determining one or more cached packets to remove from the cache memory and place in the non-cache memory.

Also, for purposes of clarity not every component may be labeled in every drawing. In the drawings:.

The example embodiments described herein are not meant to be limiting. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations, all of which are explicitly contemplated herein.

<FIG> is a block diagram of a packet cache system <NUM> and a packet cache system user <NUM> according to an embodiment, in which the flow of write information is depicted. The system hardware is optimized when packets stored in the system are handled in one or more fixed size units, and thus the system <NUM> is described in the context of packets being divided into <NUM> byte units called cells. The system <NUM> stores and manages cells for packets received in both a cache memory <NUM> (e.g., an on-chip static random-access memory, SRAM) and a non-cache memory (not shown) (e.g., off-chip dynamic random-access memory, DRAM) based on occupancy of the cache memory <NUM> and other parameters. The system <NUM> manages the eviction of cells from the cache memory <NUM> to the non-cache memory, and read/write transactions from the user <NUM> are handled transparently from the perspective of the user <NUM>, irrespective of whether the data being read/written is stored in the cache memory <NUM> or the non-cache memory. Moreover, in some embodiments, the system <NUM> stores data in the cache memory <NUM> in 64B flits (flow control units/flow control digits).

The packet cache system <NUM> may include an eviction engine <NUM> to move data from the cache memory <NUM> to non-cache memory based on occupancy of the cache memory <NUM> and packet priority. The eviction engine <NUM> may also use the age of cache memory <NUM> entries as a factor in determining whether a packet may be evicted. The eviction engine <NUM> attempts to ensure that the cache memory <NUM> has space to accommodate write requests from user <NUM>. In rare cases that eviction is not fast enough to accommodate write requests, the write request interface will be back-pressured.

The packet cache system <NUM> of <FIG> has a cache subsystem <NUM>. The cache subsystem <NUM> includes a cache memory allocator <NUM> for receiving a memory address corresponding to a non-cache memory and allocated to a packet, and a hash table <NUM> for associating the memory address with a cache memory address corresponding to a location in the cache memory <NUM>. The packet, or part of the packet, may be stored in the cache memory <NUM> at a location indicated by the cache memory address. The memory address may be hashed to hash table location in the hash table <NUM> by applying a hash function to the memory address, and the cache memory address may be stored in the hash table <NUM> at the hash table location. In this manner, one may rapidly search out the packet from the cache memory <NUM> based on the memory address of the packet (e.g., in response to a read request) by hashing the memory address to a location in the hash table <NUM>, noting the cache memory address from the location in the hash table <NUM>, and accessing the cache memory <NUM> based on the noted address. Operations within the cache subsystem <NUM> may be controlled according to a finite state machine (FSM) <NUM>.

In some embodiments, both the memory address and the cache memory address for a packet or cell data may be stored at a location in the hash table <NUM> as a "key-value pair. " Such configuration facilitates use of the memory address (or key) to locate the cache memory address(es) of a desired packet when the hash table <NUM> is used to store multiple cache memory addresses at each location of the hash table <NUM>.

In embodiments employing 256B cells and 64B flits, the cache memory <NUM> may be organized in four banks, and the cache memory allocator <NUM> may allocate a branch of memory addresses according to the length of write data, at a rate of up to four addresses per cycle.

In any event, each packet in the cache memory <NUM> may correspond on a one-to-one basis with a priority memory entry in a priority memory <NUM> of the eviction engine <NUM>. When a packet or cell is assigned a cache memory address in cache memory <NUM> and is stored in the cache memory <NUM> at the cache memory address, the packet or cell is assigned a corresponding priority memory address in the priority memory <NUM> and a priority for the packet or cell is stored at the corresponding priority memory address. A valid/invalid indicator (e.g., a valid/invalid bit) is stored with the priority, as indicated by a validity section <NUM> of the priority memory <NUM>. The eviction engine <NUM> uses eviction logic <NUM> to initiate and conduct an evict scan, when occupancy of the cache memory <NUM> is high, although an evict scan can also be triggered by the user <NUM> through an evict interface (not shown). When a packet or cell is evicted/deallocated from the cache memory <NUM>, its corresponding valid/invalid indicator is set to invalid.

The <FIG> embodiment further includes a memory allocator <NUM> for allocating non-cache memory addresses to packets. The memory allocator <NUM> is shown as part of the user <NUM>; however, it should be noted that in some embodiments the memory allocator <NUM> may be part of the packet cache system <NUM>.

The packet cache system <NUM> supports the following features:.

Data is written back to non-cache memory only when a packet is evicted from the cache memory <NUM>.

Regarding the dividing of packets into cells, each cell may be associated with a non-cache memory address (e.g., a DRAM address). Each cell may include 256B. Further, each cell may be in one of <NUM> formats:.

If a packet can fit into one cell, the packet will fit in one control cell with inline payload. If a packet cannot fit into one cell, the packet will use a first cell as a control cell with payload pointers, and packet data will be stored in data cells.

In general, a packet is subjected to a write, read, deallocate process. For example, a packet received by user <NUM> is written to cache memory <NUM> while the packet awaits processing, then during processing the packet is read from the cache memory <NUM> multiple times, and when the processing for the packet is complete the space in the cache memory <NUM> that was allocated to the packet is deallocated.

The write process contains the following steps:.

The read process contains the following steps:.

Turning now to <FIG>, the figure is a block diagram of the packet cache system <NUM> and the packet cache system user <NUM> of <FIG>, in which the flow of deallocation information is depicted.

The deallocate process contains the following steps:.

Regarding eviction, no matter how many cells one packet has, all cells will be evicted together. Thus, all cells for a packet will be either in the cache memory <NUM> or in the non-cache memory.

The evict process contains the following steps:.

Turning now to <FIG>, the figure is a block diagram of a packet cache system <NUM>, the packet cache system user <NUM>, and a non-cache memory <NUM> according to an embodiment. As can be seen from the <FIG>, the packet cache system <NUM> has six interfaces, a non-cache memory read interface <NUM>, a non-cache memory write interface <NUM>, an evict request interface <NUM>, a write interface <NUM>, the deallocation interface <NUM>, and a read interface <NUM>. The read interface couples the user <NUM> to a reorder engine <NUM> which, in turn, may include and maintain the ROB. The reorder engine <NUM> serves to reorder read responses from the cache memory <NUM> and non-cache memory <NUM>, as necessary. The reorder engine <NUM> and cache subsystem <NUM> define a data packet cache <NUM>.

In some embodiments, the data packet cache <NUM>, the evict engine <NUM> and the user <NUM> are parts of a single integrated circuit chip, and the non-cache memory <NUM> is external to the chip. For example, the data packet cache <NUM>, the evict engine <NUM> and the user <NUM> are part of an ASIC, with the user <NUM> being a TX/RX module of the ASIC, the cache memory being SRAM internal to the chip, and the non-cache memory <NUM> being DRAM external to the chip. In such embodiments, the data packet cache <NUM> includes the cache memory <NUM> to store packets on-chip, the cache memory allocator <NUM> to allocate available space in cache memory <NUM> when a write event happens, the reorder engine <NUM> to reorder read responses from either cache memory <NUM> or non-cache memory <NUM>, the hash table <NUM> to remember the mapping between non-cache memory addresses and cache memory addresses, and the finite state machine <NUM> to manage all the flows.

The user <NUM> will initiate read, write, deallocate events to the data packet cache <NUM>, while the eviction engine <NUM> handles priority/age based evictions.

Regarding the reorder engine <NUM>, it will record the order of all read requests and return all read responses in the same order, no matter whether the data is from the cache memory <NUM> or the non-cache memory <NUM>.

<FIG> is a block diagram of a packet cache system <NUM>, a TX/RX controller <NUM>, and DRAM <NUM> according to an embodiment, in which elements of a reorder engine <NUM> are depicted. In the <FIG> configuration, the TX/RX <NUM> is a packet cache system user, and the DRAM <NUM> is a non-cache memory As can be seen from <FIG>:.

It should be noted that there are instances for which data corresponding to a read request does not need to be stored in the reorder buffer <NUM>. To accommodate such instances, the reorder engine <NUM> may include a register <NUM>. The register <NUM> is used to store data read prior to such data being sent from the reorder engine <NUM> to the TX/RX controller <NUM>. Further, the reorder engine FSM <NUM> may include a multiplexer function <NUM> for switching between supplying data from the reorder buffer <NUM> and the register <NUM>.

Turning now to <FIG> the figure is a flowchart describing operation of the reorder engine <NUM> according to an embodiment. <FIG> is described in reference to the <FIG> configuration. As can be seen from <FIG>, when the reorder engine <NUM> receives a read request (step <NUM>), a determination is made as to whether the received read request corresponds to a connection ID that matches the connection ID of a pending read request for which DRAM <NUM> is being read (step <NUM>). If the received read request corresponds to a connection ID that matches the connection ID of a pending DRAM read request, then there is a possibility that the data for received read request and the data for the pending read request will be available out of order; and therefore the received read request is sent to the request array <NUM> of the reorder engine <NUM> for handling (step <NUM>), and the reorder engine <NUM> will reorder the out-of-order responses to make sure TX/RX controller <NUM> sees the read responses for same connection in order. When the received read request is in the request array <NUM>, data pertaining to the request is read and from the DRAM <NUM> and placed in the reorder buffer <NUM>, and when all the data for the received request is in the reorder buffer <NUM> a valid bit for the received request is set in the request array <NUM> (step <NUM>). Following receipt of all the data by the reorder buffer <NUM> and setting of the valid bit, the reorder engine <NUM> may send the data for the received read request to the TX/RX controller <NUM> (step <NUM>).

If, in step <NUM>, it is determined that the received read request does not correspond to a connection ID that matches the connection ID of a pending read request for which DRAM <NUM> is being read, then a lookup is performed in the hash table <NUM> for the dram_cell_addr of the first cell (or only cell) for the received read request (step <NUM>), and a determination is made as to whether or not the lookup results in a hash table miss (step <NUM>). If the lookup results in a hash table miss, the operation proceeds to step <NUM>, with the received read request being sent to the request array <NUM> for handling so as to avoid the data for the read request being provided to the TX/RX controller out of order (e.g., due to slow speed of retrieval of the data from DRAM <NUM>).

If the lookup of step <NUM> results in a hash table hit, the data corresponding to the received read request is read from the cache memory <NUM> and stored in the register <NUM>, without the read request being sent to the request array <NUM> (step <NUM>). Following receipt of all the data by the register <NUM>, the reorder engine <NUM> sends the data for the received read request to the TX/RX controller <NUM> (step <NUM>).

Claim 1:
A packet cache system comprising:
a memory allocator (<NUM>) for assigning a memory address to a packet;
a cache memory allocator (<NUM>) for receiving the memory address corresponding to a non-cache memory (<NUM>) and allocated to the packet, and associating the memory address with a cache memory address;
a hash table (<NUM>) for storing the memory address and the cache memory address, with the memory address as a key and the cache memory address as a value;
a cache memory (<NUM>) for storing the packet at a location indicated by the cache memory address; and
an eviction engine (<NUM>) for determining one or more cached packets to remove from the cache memory (<NUM>) and place in the non-cache memory (<NUM>) when occupancy of the cache memory (<NUM>) is high,
characterized in that
the memory allocator (<NUM>) is operable to form the packet into one or more cells, the one or more cells comprising a control cell when the packet is formed into one cell, and comprising a control cell and one or more data cells when the packet is formed into more than one cell, wherein the memory allocator (<NUM>) assigns the memory address to the control cell, and respectively assigns one or more additional memory addresses to the one or more data cells.