Patent ID: 7966442

Claim:
A method comprising: programming a fully associative instruction cache of a network device to apply a perfect hash function, wherein the fully associative instruction cache includes a set of instruction cache slots capable of being associated with any memory address of a memory within the network device, and wherein the perfect hash function maps memory addresses of a set of software instructions installed on the network device to different hash values that each correspond to one of the different instruction cache slots of the fully associative instruction cache; loading, with the network device, the 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 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.