US 7,743,200 B1Granted

Instruction cache using perfect hash function

AssigneeJuniper Networks, Inc.

InventorsRamesh Panwar, Philip A. Thomas

Life of this patent

Estimating the term…

Abstract

In general, this disclosure describes techniques of storing data in and retrieving data from a cache of a computing device. More specifically, techniques are described for utilizing a “perfect hash” function to implement an associative cache within a computing device. That is, the associative cache implements a fully associative map between a predetermined set of addresses and data values, employing only a single tag fetch comparison.

Claims37

Dependent claims

A method comprising:

profiling, with a network device deployed within a network, rates at which one or more processors of the network device utilize different software instructions, wherein the software instructions are stored to a memory of the network device and executed by the network device to process network communications;
identifying, with the network device based on the profiled rates, a set of software instructions that are most frequently utilized by the one or more processors to process the network communications;
identifying, with the network device, a perfect hash function that only maps memory addresses of the identified set of software instruction to different hash values, wherein each of the different hash values corresponds to a different instruction cache slot of a fully associative instruction cache module of the network device;
programming, with the network device, the fully associative instruction cache module of the network device to apply the perfect hash function, wherein the fully associative instruction cache module includes a set of instruction cache slots, and wherein each instruction cache slot is capable of being associated with any memory address of the memory;
loading, with the network device, each of the identified software instructions into the corresponding instruction cache slots indicated by the hash values calculated by applying the first perfect hash function to the memory addresses of the identified software instructions;
receiving, with the fully associative cache module, a read request for one of the instructions stored to a memory address of the memory;
applying, with the fully associative cache module, the perfect hash function to the memory address in order to calculate a hash value that indicates one of the instruction cache slots when the fully associative cache module receives the read request;
determining whether the one of the instruction cache slots stores the software instruction requested by the read request;
returning a copy of the one of the instructions that is stored in the one of the instruction cache slots in response to the determination that the one of the instruction cache slots stores the software instruction requested by the read request;
and
forwarding the read request to the memory in response to the determination that the software instruction requested by the read request-has a memory address that is not within the set of memory addresses for which the perfect hash function was calculated and cannot be retrieved from the fully associative cache module.

8 more elements

A device comprising:

one or more processors;
a memory that stores software instructions of computer programs;
a data utilization profiler (DUP) that profiles rates at which the one or more processors utilize different one of the software instructions of the computer programs to process network communications;
an address identification module (AIM) that identifies, based on the rates, a set of the software instructions that are most frequently utilized by the one or more processors to process the network communications;
a function identification module (FIM) that identifies a perfect hash function that, for each of the identified software instructions, only maps a memory address of each one of the identified set of software instructions to a different hash value, wherein each of the different hash values corresponds to a different instruction cache slot of a fully associative instruction cache module of the network device;
and
the fully associative instruction cache module that comprises:
a set of instruction cache slots that are capable of storing the software instructions, wherein each instruction cache slot is capable of being associated with any memory address of the memory;
and
a hash value calculator that applies the perfect hash function to the memory addresses in order to generate hash values that indicate ones of the cache slots;
a cache initialization module that programs the cache module to apply the perfect hash function and to load each of the identified software instructions into the corresponding instruction cache slots indicated by the hash values calculated by applying the perfect hash function to the memory addresses of the identified software instructions,
wherein, when the fully associative instruction cache module receives a read request for one of the software instructions stored to a memory address of the memory, the hash value calculator applies the perfect hash function to the memory address of the read request in order to calculate a hash value that indicates one of the instruction cache slots;
and
a single comparator to determine whether the one of the instruction cache slots stores the software instruction requested by the read request;
wherein the cache module returns an instruction stored in a first one of the instruction cache slots in response to the determination that the one of the instruction cache slots stores the software instruction requested by the read request and forwards the read request to the memory in response to the determination that the software instruction requested by the read request has a memory address that is not within the set of memory addresses for which the perfect hash function was calculated and cannot be retrieved from the fully associative cache module.

12 more elements

A computer-readable storage medium storing software instructions that cause at least one of one or more processors of a computing device to:

profile rates at which the one or more processors of the computing device utilize different ones of the software instructions to process network communications;
identify, based on the profiled rates, software instructions that are most frequently utilized by the one or more processors to process the network communications;
identify a perfect hash function that only, for each of the identified software instructions, maps a memory address of the identified software instruction to a different hash value, wherein each of the different hash values corresponds to a different instruction cache slot of a fully associative instruction cache module of the network device;
program a fully associative instruction cache module to apply the perfect hash function, wherein the fully associative instruction cache module includes a set of instruction cache slots, and wherein each of the set of instruction cache slots is capable of being associated with any memory address of the computer-readable storage medium;
load each of the identified software instructions into the corresponding instruction cache slots indicated by hash values calculated by applying the perfect hash function to the memory addresses of the identified software instructions;
wherein the cache module receives a read request for a memory address, applies the perfect hash function to the memory address in order to calculate a hash value that indicates one of the instruction cache slots, determines whether the one of the instruction cache slots stores the software instruction requested by the read request, returns a copy of a one of the instructions that is stored in the first one of the instruction cache slots in response to the determination that the one of the instruction cache slots stores the software instruction requested by the read request, and forwards the read request to the memory in response to the determination that the software instruction requested by the read request has a memory address that is not within the set of memory addresses for which the perfect hash function was calculated and cannot be retrieved from the fully associative cache module.

3 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A method comprising:

profiling, with a network device deployed within a network, rates at which one or more processors of the network device utilize different software instructions, wherein the software instructions are stored to a memory of the network device and executed by the network device to process network communications;
identifying, with the network device based on the profiled rates, a set of software instructions that are most frequently utilized by the one or more processors to process the network communications;
identifying, with the network device, a perfect hash function that only maps memory addresses of the identified set of software instruction to different hash values, wherein each of the different hash values corresponds to a different instruction cache slot of a fully associative instruction cache module of the network device;
programming, with the network device, the fully associative instruction cache module of the network device to apply the perfect hash function, wherein the fully associative instruction cache module includes a set of instruction cache slots, and wherein each instruction cache slot is capable of being associated with any memory address of the memory;
loading, with the network device, each of the identified software instructions into the corresponding instruction cache slots indicated by the hash values calculated by applying the first perfect hash function to the memory addresses of the identified software instructions;
receiving, with the fully associative cache module, a read request for one of the instructions stored to a memory address of the memory;
applying, with the fully associative cache module, the perfect hash function to the memory address in order to calculate a hash value that indicates one of the instruction cache slots when the fully associative cache module receives the read request;
determining whether the one of the instruction cache slots stores the software instruction requested by the read request;
returning a copy of the one of the instructions that is stored in the one of the instruction cache slots in response to the determination that the one of the instruction cache slots stores the software instruction requested by the read request;
and
forwarding the read request to the memory in response to the determination that the software instruction requested by the read request-has a memory address that is not within the set of memory addresses for which the perfect hash function was calculated and cannot be retrieved from the fully associative cache module.

8 more elements