Cache index mapping

• US 10,177,795 B1
• Filed: 12/29/2016
• Issued: 01/08/2019
• Est. Priority Date: 12/29/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Frishman, Ofer, Izenberg, Erez, Nakibly, Guy
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US15/394,635
• Time in Patent Office: 740 Days
• Field of Search: 714807, 714803, 714800
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/174 Telecommunications system
• CPC Class Codes: G06F 2212/60 Details of cache memory
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/63 Joint error correction and other techniques H03M13/31 and H03M13/33 take precedence
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Systems and methods in accordance with various embodiments of the present disclosure provide approaches for mapping entries to a cache using a function, such as cyclic redundancy check (CRC). The function can calculate a colored cache index based on a main memory address. The function may cause consecutive address cache indexes to be spread throughout the cache according to the indexes calculated by the function. In some embodiments, each data context may be associated with a different function, enabling different types of packets to be processed while sharing the same cache, reducing evictions of other data contexts and improving performance. Various embodiments can identify a type of packet as the packet is received, and lookup a mapping function based on the type of packet. The function can then be used to lookup the corresponding data context for the packet from the cache, for processing the packet.

Claims

1. A computer-implemented method comprising:

under the control of one or more computer systems;

receiving a packet, the packet associated with a packet type and an attribute;

parsing the packet to determine the packet type and the attribute;

based on the packet type and the attribute,

determining a cache function for accessing a cache, wherein the cache function is an ambiguous function associated with the packet type, and

determining packet processing data associated with the packet type;

requesting, from the cache and using the cache function, a data context associated with the packet type;

determining that a cache miss has occurred in response to the request;

requesting the data context from a main memory;

storing the data context from the main memory in the cache using the cache function; and

processing the packet using the data context and the packet processing data, the cache processing packets of different packet types.

2. The method of claim 1, wherein the cache function is a cyclic redundancy check (CRC) function using a static seed associated with the packet type.

3. The method of claim 2, wherein an input to the CRC function is an address cache index based on a predetermined number of bits of an address of the data context in the main memory.

4. The method of claim 1, wherein the packet type includes one of a network packet, a storage packet, or a management packet.

5. A computer-implemented method comprising:

under the control of one or more computer systems;

determining a packet type for a packet, the packet type represented by a packet attribute value;

determining a cache access function using the attribute value, the cache access function mapping a main memory address to a cache index;

requesting data context information from a cache using the cache access function, the cache storing a plurality of data contexts, each data context associated with a different cache access function; and

processing the packet using the data context, the cache processing packets of different packet types.

6. The computer-implemented method of claim 5, wherein the cache access function is an ambiguous function.

7. The computer-implemented method of claim 6, wherein the cache access function is a cyclic redundancy check (CRC) function and wherein each packet type is associated with a different static seed value for the CRC function.

8. The computer-implemented method of claim 7, wherein an input to the CRC function is an address cache index based on a predetermined number of bits of an address of the data context information in the main memory.

9. The computer-implemented method of claim 5, wherein the packet type is a storage packet and wherein the data context is a queue ring stored in contiguous addresses in main memory.

10. The computer-implemented method of claim 9, further comprising:

storing the queue ring in the cache using the cache access function, wherein the queue ring is stored in non-consecutive indexes in the cache.

11. The computer-implemented method of claim 5, further comprising:

determining that a cache miss has occurred in response to the request for the data context information from the cache; and

requesting the data context information from a main memory.

12. The computer-implemented method of claim 5, wherein determining a cache access function using the attribute value comprises:

looking up the cache access function in a table, wherein the table is indexed using the attribute value, the table further including packet processing data associated with the packet type.

13. A computing device, comprising:

electronic circuitry, wherein the electronic circuitry is configured to;

determine a packet type for a packet;

determine a cache access function using the packet type, the cache access function mapping a main memory address to a cache index;

request data context information from a cache using the cache access function, the cache storing a plurality of data contexts, each data context associated with a different cache access function; and

process the packet using the data context, the cache processing packets of different packet types.

14. The computing device of claim 13, wherein the cache access function is an ambiguous function.

15. The computing device of claim 13, wherein the packet type is determined according to a packet attribute value of the packet.

16. The computing device of claim 13, wherein the electronic circuitry comprises a cache mapper circuit, and wherein the cache mapper circuit determines the cache access function using the packet type.

17. The computing device of claim 13, wherein the electronic circuitry comprises the cache.

18. The computing device of claim 13, wherein the electronic circuitry comprises a packet inspector circuit, and wherein the packet inspector circuit determines the packet type for the packet.

19. The computing device of claim 13, wherein the electronic circuitry comprises a function table.

20. The computing device of claim 13, wherein the computing device is a processor, a system-on-chip (SoC), a field-programmable gate array (FPGA), or an application-specific integrated circuit (ASIC).