Patent Description:
Computer systems utilize various types of processors to perform various functions in various contexts. Processors utilize various types of caches to perform various functions in various contexts Document <CIT> discloses a multi-mode, multi-way, set-associative, dynamically configurable, cache memory wherein a fat mode index selects two different sets of the cache memory , whereas in a normal or skinny mode an index and the least significant bit of the tag are used to select one set of the cache memory.

To facilitate understanding, identical reference numerals have been used herein, wherever possible, in order to designate identical elements that are common among the various figures.

Various example embodiments for supporting processor capabilities are presented herein. Various example embodiments for supporting processor capabilities may be configured to support increased efficiency in utilization of a cache of a processor. Various example embodiments for supporting increased efficiency in utilization of a cache of a processor may be configured to support increased efficiency in utilization of the cache of the processor based on implementation of the cache of the processor as a multi-mode indexed cache. Various example embodiments for providing a multi-mode indexed cache may be configured to provide a multi-mode indexed cache configured as a set associative cache having a plurality of sets, wherein the cache is configured to support multiple indexing modes for indexing memory blocks such that, for a memory operation for a given memory block, the multiple indexing modes are configured to cause selection of different ones of the plurality of sets of the cache for the memory operation for the given memory block. Various example embodiments for providing a multi-mode indexed cache may be configured to provide a multi-mode indexed cache configured as a set associative cache having a plurality of sets, wherein the cache is configured to support a memory operation for a memory block, wherein the memory block has a memory block address associated therewith, wherein the cache is configured to support a first indexing mode in which the cache uses a first subset of bits of the memory block address to index into the plurality of sets of the cache for the memory operation and a second indexing mode in which the cache uses a second subset of bits of the memory block address to index into the plurality of sets of the cache for the memory operation. Various example embodiments for providing a multi-mode indexed cache may be configured to implemented various types of caches as multi-mode indexed caches (e.g., an instruction cache (IC) of a processor, a micro-operations cache (UC) of a processor, a data cache (DC) of a processor, a unified cache of a processor that can host instructions and data, a branch target buffer (BTB) associated with a branch predictor of a processor, or the like). It will be appreciated that these and various other example embodiments and advantages or potential advantages of example embodiments for supporting processor capabilities may be further understood by way of reference to the various figures, which are discussed further below.

<FIG> depicts an example embodiment of computing system including a processor and a memory for illustrating an instruction pipeline supported by the processor.

The computing system <NUM> includes a processor <NUM> and a memory <NUM>. The processor <NUM> includes an instruction cache (IC) <NUM>, a micro-operations cache (UC) <NUM>, and a branch predictor (BP) <NUM>. The high level stages in the pipeline supported by the processor <NUM> include a fetch stage <NUM>, a decode stage <NUM>, and an execute stage <NUM>.

In the processor <NUM>, the format and encoding of the instructions in a program to be executed by the processor <NUM> is determined by the Instruction Set Architecture (ISA) of the processor <NUM>. For example, some well-known ISAs include x86/x86-<NUM>, IA-<NUM>/IA-<NUM>, MIPS, ARM, and so forth; however, the micro-architecture of a processor typically cannot execute the instructions of an ISA in their native form because of their complexity. An ISA is designed to offer sophisticated operations which, in turn, also keep the program compact, i.e., reduces the footprint of a program in the memory. It is noted that the optimal footprint of a program in memory is particularly important for optimal use of the IC. A majority of ISAs offer variable-length instructions, which further adds to the complexity of execution. So, at the micro-architectural level of a processor, instructions are represented by fixed-length simpler micro-operations (generally referred to as "micro-ops" or "UOPs"). An ISA instruction is broken down into one or more fixed-length UOPs. UOPs perform basic operations on data stored in one or more registers, including transferring data between registers or between registers and external buses, performing arithmetic and logical operations on registers, or the like. For example, for an add-register-to-memory ISA instruction that performs addition of the value in a register X to the value in a memory location M, the instruction is broken down into a sequence of three separate UOPs as follows: (<NUM>) load from M to a register Y, (<NUM>) add Y to X, and (<NUM>) store X to M.

In the processor <NUM>, execution of a program is based on a pipeline which, as indicated above, includes the fetch stage <NUM>, the decode stage <NUM>, and the execute stage <NUM>. The fetch stage <NUM> retrieves a block of instructions of a program from the IC <NUM> or the memory <NUM>. The IC <NUM> is located on-board the processor <NUM>. The IC <NUM> is generally much smaller in size (e.g., 32kB, 64kB, 128kB, or the like) than the memory <NUM> and, thus, much faster than the memory <NUM>. The IC <NUM> caches blocks of instructions fetched from the memory <NUM> in units called "IC lines" (or, more generally, cache lines). If a set of instructions is repeatedly fetched then those instructions are likely available in the IC <NUM>, so a hit in the IC <NUM> reduces the time to fetch instructions (as compared with fetching the instructions from the memory <NUM>). The IC <NUM> is agnostic of syntax and semantics of instructions and an IC line caches a memory block, i.e., all instructions in a fixed range of addresses in the memory <NUM>. The typical size of an IC line is 64B, although it will be appreciated that other sizes can be supported. The processor <NUM> fetches a block of instructions from the memory <NUM> only if the IC line is not found in the IC <NUM>. In the IC <NUM>, a memory block is identified by the first memory address in the memory block. In the decode stage <NUM>, instructions fetched during the fetch stage <NUM> are dynamically decoded by the processor <NUM> to the native UOPs of the instructions. This dynamic decoding also provides a cleaner separation of the "stable" and "standardized" ISA from the underlying micro-architecture of the processor <NUM> that is free to define its own UOP set. As a result, a program that has been written for an ISA can run on different micro-architectures supporting that ISA. This has enabled program compatibility between different generations of processors to be easily achieved. For example, different micro-architectures can support the same ISA, but each can define their own native UOP set. The execute stage <NUM> executes the UOPs supplied by the decode stage <NUM>.

In the processor <NUM>, the fetch stage <NUM> and the decode stage <NUM> generally are costly in terms of clock cycles as well as power consumption. So, many modern processors implement another instruction cache, typically referred to as a micro-op cache (UC) or decoded stream buffer (DSB), which stores the already decoded UOPs. This is illustrated as the UC <NUM> of the processor <NUM>. When the processor <NUM> needs to execute an instruction and its decoded UOPs already exists in the UC <NUM>, then the UC <NUM> can directly supply the UOPs to the execute stage <NUM>. The UC <NUM> is generally much smaller in size (e.g. <NUM>. 5kB, 2kB, 3kB, or the like) than the IC <NUM> and the memory <NUM> and, thus, much faster than the IC <NUM> and the memory <NUM> (typically operating at the clock speed of the processor <NUM>). A hit in UC <NUM> eliminates the fetch stage <NUM> and the decode stage <NUM>, both of which are costly, thereby improving the performance and power budget of the processor <NUM>. An instruction is fetched and decoded only if it is a miss in the UC <NUM>, otherwise the fetch stage <NUM> and the decode stage <NUM> can be powered off. It is noted that, although omitted from <FIG> for purposes of clarity, some processors may use a component called a Trace Cache (TC) instead of a UC, where a TC is simpler than a UC since a TC is a single large block including all instructions or micro-operations of a control flow.

In the processor <NUM>, the UC <NUM> stores the UOPs received from the decode stage <NUM> in smaller sized blocks, but in the sequential order of execution. This means that each branch, conditional or unconditional, makes the processor <NUM> start with a new UC line even if the current IC line is not yet filled. This simple rule allows high bandwidth fetching from the UC <NUM> since, once there is a hit in UC <NUM>, then the entire UC line can be supplied to the execute stage <NUM> without worrying about a change of execution sequence in the middle of a UC line. Herein, unless indicated otherwise, an address of an instruction in memory is referred to as an Instruction Pointer (IP). A UC line is identified by the IP of the parent instruction of the first UOP in the UC line; other than that no correlation exists between the UOPs in a UC line and their corresponding parent instructions, and it is noted that such correlation is not required since the entire UC line is supplied to the execute stage <NUM>. As a result, UOPs in a UC line typically cannot be looked up by the IPs of their parent instructions.

In the processor <NUM>, the BP <NUM> is configured to predict the outcome of a conditional branch instruction while fetching instructions from the memory <NUM>, the IC <NUM>, or the UC <NUM>. A program may include branch instructions that alter the sequence of instructions executed by the processor <NUM>. Branch instructions generally are of two types: one-way unconditional branch instruction and two-way conditional branch instruction. An unconditional branch instruction always jumps to a different location in program memory where a branch of the program code is stored. A conditional branch instruction can either be (<NUM>) "not taken" and continue execution with the first branch of the code which follows immediately after the conditional branch instruction or (<NUM>) "taken" and jump to a different place in program memory where the second branch of the code is stored. The outcome of a conditional branch instruction depends on certain conditions, such as a predicate variable. It is not known for certain whether a conditional branch will be taken or not taken until the condition has been calculated and the conditional branch has passed the execute stage <NUM> in the instruction pipeline. That means the processor <NUM> would have to wait until the conditional branch instruction has passed the execute stage <NUM> before the next instruction can enter the fetch stage <NUM> in the pipeline, which basically stalls the pipeline. To solve this problem, the front-end of the processor <NUM> tries to guess whether the conditional branch is more likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. The BP <NUM> is logic circuitry that enables the front-end of the processor <NUM> to predict the outcome of a conditional branch instruction. If later it is detected that the guess was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay called "branch misprediction penalty".

It will be appreciated that processors generally implement each of the three high-level stages of the instruction pipeline using component stages. As a result, a pipeline of a processor may be composed of a large number of stages (e.g., <NUM> or more stages). An example of a processor, for illustrating stages used to implement portions of the instruction pipeline, is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a processor for use as the processor of the computing system of <FIG>.

The processor <NUM> may include a frontend and a backend. It is noted that while details of the frontend are illustrated, details of the backend have been omitted for purposes of clarity.

The processor <NUM> includes a level <NUM> (L1) instruction cache (L1-IC) <NUM>, an instruction fetch unit (IFU) <NUM>, a branch prediction unit (BPU) <NUM>, an instruction length decoder (ILD) <NUM>, an instruction queue (IQ) <NUM>, an instruction decoder (ID) <NUM>, a UOP cache (UC) <NUM>, and an instruction decode queue (IDQ) <NUM>. It will be appreciated that the IFU <NUM> and BPU <NUM> may be considered to form the fetch stage while the ILD <NUM>, IQ <NUM>, ID <NUM>, and IDQ <NUM> may be considered to form the decode stage.

The L1-IC <NUM> is a cache that is part of the cache hierarchy of the processor <NUM>, and which may be further understood by considering the cache hierarchy of processors and the cache arrangement of caches in general.

In general, a cache is a smaller, faster memory, closer to a processor, which stores copies of the program instructions or program data from frequently accessed memory locations to reduce the average cost of access (time or energy). The program instructions or program data are stored in the cache by blocks of contiguous memory locations, typically referred to as cache lines, where each cache line is indexed in the cache by the first memory address in the cache line. Caches benefit from the temporal and spatial locality of memory access patterns in a program, where spatial locality refers to use of relatively close memory locations (e.g., within a cache line) and temporal locality refers to the reuse of specific caches line within a relatively small time duration. Many processors use multiple levels of caches. For example, a common processor architecture might utilize at least three levels (L) of caches, which are typically referred to as L1, L2, and L3. The L1 cache is the smallest and nearest to the processor cores and, thus, faster than the other cache levels. Typically, the L1 cache is split into two portions: the L1 Instruction Cache (e.g., 32kB in size, 64kB in size, or the like, although other sizes may be used) which holds only program instructions and the L1 Data Cache (e.g., 32kB in size, 64kB in size, or the like, although other sizes may be used) which holds only program data. The L2 cache (e.g., 256kB in size, 512kB in size, or the like, although other sizes may be used) and the L3 cache (e.g., 2MB in size, 4MB in size, or the like, although other sizes may be used) are the subsequent levels which are usually unified caches (meaning that they hold both program instructions and program data). The L3 cache typically is common for the processor cores in a multi-core processor and, thus, is located outside of the processor cores. It will be appreciated that the cache size and access latency grow according to the levels. If the cache line corresponding to a memory address sought is missing in the L1 cache, then the processor performs lookups in subsequent levels of caches (e.g., L2 cache, then L3 cache, and so forth). If the memory address is missing in all of the available cache levels, then the processor can access the main memory to retrieve the instruction or data at the memory address. So, main memory is accessed only if the memory address is missing in all caches. The missing block, once located, is brought into a cache line in the L1 cache.

In general, a cache is typically organized as set associative array, which can be imagined as MxN matrix. The cache is divided into M sets and each set contains N cache lines. To place a memory block into the cache, its address is typically divided into three fields: tag, index, offset. A memory block is first mapped into a set based on 'index bits' derived from the address of the memory block. Then the memory block is placed into a cache line in the set and a 'tag' is stored in the cache line. The tag is composed of the bits in the address of the memory block (other than the index bits) that can distinguish between the cache lines sharing the same set. The offset field refers to any address within a cache line. The offset field is composed of a few least significant bits of the address of the memory block and the number of bits is dependent on the size of the cache line. For example, if the cache line size is 64B, then the <NUM> least significant bits of the addresses of the memory blocks may be used as the offset bits. As previously indicated, the term "IP" is used to denote the memory address of an instruction, and the three fields of an IP that are used to map a block of instructions into a cache are referred to as IP-tag, IP-index, and IP-offset. In a typical cache, if all cache lines in a set are occupied while trying to store a new memory block, then an existing cache line in the set is evicted (a replacement policy picks which cache line to evict) to make way for the new memory block. When the evicted cache line is accessed later, then it will result in a miss in the cache and, thus, will need to be brought back into the cache from the memory hierarchy. Such misses are referred to as conflict misses and repeated conflict misses due to collisions between cache lines sharing the same set is referred to as thrashing. If a cache line is evicted due to capacity overflow (i.e., no more unused cache lines across the cache) and the evicted cache line is accessed again then it will result in a miss in the cache. Such misses are called capacity misses. Capacity misses are extremely rare and most often the misses are due to thrashing.

The IFU <NUM> is responsible for feeding the processor with instructions to execute, and thus, it is the first component where instructions are processed. The IFU <NUM> mainly includes the required logic to compute the next fetch address and then fetch the instructions from the L1-IC <NUM>. The instructions are fetched from the L1-IC <NUM> by the IFU <NUM> in streams of raw bytes.

The BPU <NUM> is configured to predict the next fetch address for the IFU <NUM> because, otherwise, branch instructions introduce a significant extra level of complexity in fetching streams of instructions, since the correct fetch address cannot be calculated until the branch instruction itself is executed. By default, instructions are processed by a processor sequentially. This sequential execution can be disrupted by the control instructions (e.g., conditional branches, unconditional branches, subroutine calls and subroutine returns, and so forth) to start executing an instruction sequence starting at a new address (the target address). For example, JE (Jump If Equal) is an example of a conditional branch instruction in x86 which is dependent on equality of two variables (data elements). A conditional branch is data-dependent (e.g., value of data acts as the condition) and branches to the target address only if the condition is true. An unconditional branch instruction always branches to the target address. For example, instructions such as CALL, RET, and JUMP are examples of unconditional branches for a subroutine call, a subroutine return, and an unconditional branch, respectively, in x86. Any control instruction other than a conditional branch instruction will switch the execution sequence to the target address specified in the instruction. Herein, the target instruction sequence of a control instruction is referred to generally as a control block. Execution of a program can be viewed as executing a chain of certain control blocks. Herein, an order of execution of control blocks in a program is referred to as a control flow (i.e., flow of control). Conditional branches (e.g., JE) can generate multiple control flows in a program since every such branch is a fork and the execution can go either way on the fork based on the condition of the fork. Control instructions introduce significant extra complexity in fetching streams of instructions, since the correct fetch address after the control instruction cannot be calculated until the backend executes the control instruction itself. For this reason, the frontend of high-performance processors (specifically, the BPU <NUM>) predicts the next fetch address and speculatively starts fetching from the predicted address. There are two parts in this prediction. The first is predicting the direction of the branch taken by the control instruction, i.e., taken to the target sequence or not taken. The second part is predicting the target address of a branch. Once the direction of a branch is predicted, then the memory address of the control instruction and its predicted target address is stored in a Branch Target Buffer (BTB), which is a cache organized similar to the set associative array described in the context of L1-IC <NUM>.

The ILD <NUM> provides a pre-decode phase. The ILD <NUM> separates the raw byte stream from the IFU <NUM> into a sequence of valid instructions and passes them to the IQ <NUM>. For example, as indicated above, the length of an x86 instruction may vary between 1B to 15B and may reside in any byte address in program memory, thus requiring segregation of the raw byte stream into instructions of variable lengths. Decoding the length of several instructions per cycle adds a level of complexity, since the starting addresses have to be speculatively determined. That is, the fact that the starting address of the second instruction is not known until the length of the first instruction is computed, imposes serialization of the length decoding process, and parallelizing this requires determining the length of each instruction before decoding the instruction. The ILD <NUM> provides complex logic, based on many parallel and speculative computations, to help achieve such parallelization (although this comes at the price of increased power consumption).

The IQ <NUM> queues the instructions for the instruction decode phase. The IQ <NUM> queues the instructions, after the ILD <NUM> separates the instructions from the stream of raw bytes, for use by ID <NUM> in the instruction decode phase.

The ID <NUM> provides the instruction decode phase (which also may be referred to as a dynamic translation phase). In this phase, instructions are read from the IQ <NUM> and translated into subsequent functionally-equivalent UOPs. This translation is performed by one of several decoders in a set of decoders <NUM> including a complex decoder <NUM>-C and three simple decoders <NUM>-S <NUM> - <NUM>-S3 (although it will be appreciated that fewer or more instruction decoders may be used). Herein, the ID <NUM>, including the set of decoders <NUM>, also may be referred to as a Micro Instruction Translation Engine (MITE). The resultant UOPs are passed by the ID <NUM> to the IDQ <NUM>, through which the UOPs may then enter the backend of the processor <NUM>. For example, in an x86-based processor, simple instructions can translate into one to four UOPs and complex instructions can translate into five or more UOPs. It will be appreciated that, for processors based on other ISAs, instructions may be translated into other numbers of UOPs.

The UC <NUM>, generally speaking, is a UOP cache that is configured to cache UOPs for instructions previously decoded by the MITE, thereby obviating a need for the MITE to re-decode instructions previously decoded by the MITE in order to obtain the associated UOPs (namely, avoiding the L1-IC->IFU->ILD->1Q->MITE decode path). This type of cache may be referred to as an L0 Instruction Cache (L0-IC), which may store blocks of instructions decoded into UOPs, in units of UC lines. UOP caches benefit from the temporal locality of control flows in a program, due to which previously executed instructions are executed again. Before fetching an instruction address from the L1-IC <NUM>, it is first looked up in the L0-IC. If the corresponding UC line exists (meaning a "hit") in the L0-IC, then the associated UOPs are directly supplied to the IDQ <NUM> for further execution, thereby completely avoiding the L1-IC->IFU->ILD->1Q->MITE decoding path. If the corresponding UC line does not exist (meaning a "miss") in the L0-IC, then the instruction goes through entire complex decoding cycle through the L1-IC->IFU->ILD->IQ->MITE decoding path. The ability to avoid the LI-IC->IFU->ILD->IQ->MITE decoding path in this manner provide significant advantages, as the decoding process from instructions to UOPs (especially for high performance processors) can be costly in terms of circuitry, power consumption, and time, especially where a single complex instruction may perform several operations. It will be appreciated that, since the backend of a processor can execute several UOPs per clock cycle (e.g., six UOPs per cycle), the rate at which UOPs are supplied from the frontend of the processor <NUM> to the backend of the processor <NUM> is a key element of performance which may be achieved by high hit rate in the UC <NUM>.

The IDQ <NUM> queues UOPs to be provided to the backend of the processor <NUM>. The UOPs that are queued by the IDQ <NUM> may include UOPs decoded by the ID <NUM> (MITE) and UOPs delivered from the UC <NUM>.

The backend of the processor <NUM>, although the details are omitted for purposes of clarity, may include various elements such as a reorder buffer (e.g., configured to receive UOPs from the frontend of the processor <NUM>), a unified reservation station having a set of ports configured to direct UOPs to various chains of elements), various elements or chains of elements configured to support execution of UOPs, or the like, as well as various combinations thereof.

<FIG> depicts an example embodiment of a multi-core processor including multiple cores and multiple levels of caches.

The multi-core processor <NUM> includes four cores (denoted as Core <NUM>, Core <NUM>, Core <NUM>, and Core <NUM>) and three levels of caches (denoted using L1, L2, and L3 indicators). In the multi-core processor <NUM>, each of the cores includes a CPU (illustratively, including a micro-operations cache (UC)) and L1 and L2 caches (illustratively, including an L1 instruction cache, an L1 data cache, and an L2 cache), respectively. In the multi-core processor <NUM>, the four cores share an L3 cache.

In general, a core is configured to operate as a processor (e.g., similar to the only core of a single core processor). It will be appreciated that each of the cores has its own pipeline (e.g., following the conceptual pipeline of <FIG>, which may be implemented like the pipeline of <FIG> or using any other suitable pipeline implementation) that independently fetches, decodes, and executes instructions. Accordingly, herein, the term "processor" may be referring to the only core of a single core processor, a core of a multi-core processor, or a combination of multiple cores of a multi-core processor.

In general, a cache is a smaller, faster memory, closer to a processor core, which stores copies of the program instructions or program data from frequently used memory locations to reduce the average cost (e.g., time and/or energy) of operating the processor core. The program instructions or program data are stored in the cache by blocks of contiguous memory locations, referred to as cache lines, where each cache line is indexed in the cache by the first memory address in the cache line. Caches benefit from the temporal and spatial locality of memory access patterns in a program. Spatial locality refers to use of relatively close memory locations (e.g., within a cache line). Temporal locality refers to the reuse of a specific cache line within a relatively small time duration.

In a multi-core processor, the levels of caches generally are arranged hierarchically as discussed below (although it will be appreciated that other arrangements are possible). L1 caches and L2 caches are specific to the processor cores, respectively, of the processor (i.e., each processor core has its own L1 cache(s) and L2 cache associated therewith), whereas the L3 cache of the processor is common for all of the processor cores in the processor. For each processor core, the L1 cache is the smallest cache and nearest to the processor core and, thus, faster than the rest of the cache levels. For each processor core, the L1 cache is split into two caches as follows: an L1 Instruction Cache (e.g., 32KB in size, 64KB in size, or any other suitable size) which holds program instructions and an L1 Data Cache (e.g., <NUM> in size, 64KB in size, or any other suitable size) which holds program data. The L1 Instruction Cache may correspond to the IC in <FIG>. L2 caches (e.g., 256KB in size, 512KB in size, or any other suitable size) and L3 caches (e.g., 2MB in size, 4MB in size, or any other suitable size) are the subsequent levels of caches, which are usually unified caches (meaning that the caches hold both program instructions and program data). For each processor core, the L2 cache is further from the processor core than the L1 cache. As indicated above, the L3 cache of the processor is common for all of the processor cores in the processor. Size and access latency grow according to the levels. If the cache line corresponding to a memory address sought is missing in the L1 cache, then processor performs lookups in subsequent levels of caches. Main memory is accessed only if the memory address is missing in all caches. Eventually, the missing block is read into a cache line in the L1 cache. UC is located inside a core. It will be appreciated that the operation of ICs and UCs in processors may be further understood by first considering the logical organization of an IC in a processor.

<FIG> depicts an example embodiment of an N-way set associative instruction cache for use in a processor.

As illustrated in <FIG>, the IC <NUM> includes two main building blocks: a data array <NUM> and a tag array <NUM>.

The data array <NUM> stores the IC lines, while the tag array <NUM> is used in order to match IPs into data array entries. The data array <NUM> is logically organized as a group of S number of sets. Each set consists of N number of IC lines (which also may be referred to as "IC blocks"). The number of IC lines in a set is called the "degree of associativity" of the cache. It is noted that a cache of associativity N is an N-way associative cache, where each way is an IC line. A memory block is first mapped into a set Si by its IP and then placed into any IC line Nj in the set Si. To map a memory block into the IC <NUM>, the IP is partitioned into three fields as illustrated in <FIG>.

<FIG> depicts an example embodiment of an Instruction Pointer format for an address of an instruction in memory. As previously indicated, the term "IP" may be used to refer to the address of an instruction in memory (which also may be referred to as a memory block address). As illustrated in <FIG>, the IP <NUM>, in order to map a memory block into an IC, is partitioned into the following fields: IP-tag, IP-index, and IP-offset.

The IP-offset field (which also may be referred to as the block offset or, more generally, the offset) includes the K least significant bits of the IP, which are used to identify which bytes inside an IC line are to be accessed. Assuming the size of an IC line is Q bytes, then K = log<NUM>(Q) bits in the IP-offset field. Herein, unless indicated otherwise, these K bits are denoted as IP-offset.

The IP-index field (which also may be referred to more generally as the index) includes the M next least significant bits of the IP, which are used to identify the set Si in the IC. For an IC consisting of S sets, M = log<NUM>(S) bits are needed in the IP-index field. Herein, unless indicated otherwise, these M bits are denoted as IP-index.

The IP-tag field includes the remaining bits of the IP. Herein, unless indicated otherwise, these bits are denoted as IP-tag.

Different IC lines can map to the same set Si in the IC (they have the same IP-index due to overlapping M bits), so a mechanism is needed to reverse-map IP-indexes to IPs. The tag array serves this purpose. The tag array has the same logical organization as the data array (same number of sets S and associativity N). For each IC line in the data array, the tag array holds some metadata: the IP-tag bits and the state of the IC line (valid, etc.).

To lookup an IP, a set Si in both the data array and the tag array is accessed using the IP-index part, but, to know if an IC line within the set corresponds to the given IP, the IP-tag bits must match to an entry in the set Si in the tag array. If the IP-tag bits of the j-th entry in the set Si match, then the correct data is in the j-th IC line of the corresponding data array in the set Si (this is called a "cache hit"). If no IP-tags is in the set Si match in the tag array, then the requested IC line does not reside in the IC (this is a "cache miss"). In the case of a cache miss, a request to the higher levels of the memory hierarchy may be issued and the processor will wait for the IC line to be installed in the IC before the access can proceed.

As an example, consider an <NUM>-way associative cache with <NUM> sets with a cache line size of 64B. Then, each cache line would hold a block of 64B of instructions. Here K=<NUM> and M=<NUM>. If the processor tries to access an instruction at IP 0xf045 (tag = 0x1e, index = 0x1, offset = 0x5), then the processor looks for the cache line in set <NUM> bearing the tag 0x1e. If the IC line is found, then the <NUM>th byte in the IC line is retrieved.

The access to the tag array and data array can occur serially or in parallel. In <FIG>, a whole set is read from the data array while the tag array is accessed. The address is compared with the IP-tag entries to determine in which IC line of the set reside the data that needs to be accessed. This information is fed to a multiplexer at the output of the data array (the way multiplexer) that chooses one of the IC lines of the set. Finally, the offset part of the address is used to extract the appropriate bytes from the chosen IC line (this process is called data alignment).

The number of bits in the IP-offset field determines the size of an IC line, i.e., the size of an IC line is log<NUM>(number of bits in IP-offset field). The set in the IC is selected based on IP-index and an IC line within the set (i.e., a way in the set) is tagged with the IP-tag. In the example in <FIG>, IP-offset is <NUM>-bits, IP-index is <NUM> bits, and IP-tag is <NUM>-bits and, thus, for the exemplary IC line, IP-tag = 0xFF and IP-index = 0x0. Thus, the IC line is tagged with 0xFF in the set <NUM>. As evident, all instructions within an IC line share the same IP-tag and IP-index.

In general, the design of a cache with the paradigm of <FIG> enables a simple and efficient of the cache in hardware and, thus, this design is the foundation of most caches found in processors. However, such a cache will suffer from conflict misses when Q number of frequently accessed memory blocks map to the same set Si, and the cache associativity N is less than Q. In that case, one of the valid cache lines in the set Si needs to be evicted to accommodate a newer memory block. When the evicted memory block is required by the processor again, then it will be a miss and will need to be fetched back to the cache. To make room for the memory block again, another cache line may need to be evicted and the pattern continues. This pattern is called thrashing of cache lines. The thrashing of cache lines may be further understood with respect to the following example.

In the example for illustrating thrashing of cache lines, assume that the <NUM>-bit memory block with address <NUM> needs to be stored in the cache. Also, assume that the size of a cache line is 64B and there are <NUM> sets in the <NUM>-way set associative cache. It is noted that the bit positions start from zero to higher from right to left. Additionally, assume that the Tag, Index, and Offset mappings of an address of a memory block are as shown in <FIG>. As illustrated in the memory address mapping <NUM> of <FIG>, Bits <NUM>-<NUM> are used for indexing an offset in a 64B cache line, Bits <NUM>-<NUM> are used for indexing one of the <NUM> sets in the cache, and Bits <NUM>-<NUM> are used as Tag. The set is determined by the Index bits <NUM>, which maps to set <NUM>.

In the example for illustrating thrashing of cache lines, assume that the current state of the set associative cache, before storing a memory block based on the single mode mapping of <FIG>, is as shown in <FIG>. In the set associative cache <NUM> of <FIG>, only a few of the Sets are shown (for purposes of clarity) and "T" means the Tag bits from the address of the memory block for the indexing mode. In the example for illustrating thrashing of cache lines, it is noted that, when the cache tried to store the memory block in one of the <NUM> ways in set <NUM>, it find that none of the ways are empty. So, the cache needs to evict one cache line to make way for the new memory block. When the evicted cache line is needed later, then it will be a miss.

It will be understood that, the higher the associativity, the less conflict misses the memory blocks will suffer. On the other hand, the more ways the cache has, the bigger the way multiplexer becomes, and this may affect the cycle time of the processor. Hit ratio in various caches is the heart of the performance of a processor. Additionally, conflict misses also lead to poorer capacity utilization of a cache. For example, empty ways in other sets remain unused while conflicting cache lines are evicted from a set.

Various example embodiments presented herein for supporting a multi-mode indexed cache may be configured to improve cache performance (and, thus, processor performance) by improving the hit ratio of the cache and the utilization of the cache. Various example embodiments presented herein for supporting a multi-mode indexed cache may be configured to reduce or prevent conflict misses without requiring an extra cache and/or extra circuitry which consumes additional power and area on the processor die and which requires extra lookups in the extra cache/circuitry in the case of thrashing of cache lines.

Various example embodiments presented herein may be configured to reduce or minimize conflict misses in an N-way set associative cache by dynamically adjusting the indexing mode of the cache so that Q remains less than N for a working set (i.e., memory blocks accessed during program execution). Various example embodiments presented herein may be configured to reduce or minimize conflict misses in an N-way set associative cache by dynamically adjusting the indexing mode of the N-way set associative cache based on configuration of the N-way set associative cache as a multi-mode indexed cache configured to support multiple modes of indexing a memory block. In a multi-mode indexed cache, depending on the indexing mode used, a memory block can get stored in a different cache line. This may be used to guarantee that, for a memory block, each indexing mode selects a different set in the N-way set associative cache. According to the invention, each indexing mode can use a disjoint subset of bits from the memory block address to select the set in the N-way set associative cache.

In a multi-mode indexed cache, the multiple modes may be used to support storage of a memory block as follows. To store a memory block, a first indexing mode is used and, accordingly, a first set of the N-way set associative cache is selected. If an empty cache line is available in the first set of the N-way set associative cache, then the memory block is stored in one of the empty cache lines in the first set. If no empty cache line is available in the first set of the N-way set associative cache, then a second indexing mode is used and, accordingly, a second set of the N-way set associative cache is selected. If an empty cache line is available in the first set of the N-way set associative cache, then the memory block is stored in one of the empty cache lines in the first set. If no empty cache line is available in the second set of the N-way set associative cache then a third indexing mode, if available, may be used. Theoretically, the cache may support up to S number of modes where S is the number of sets in the cache; however, given that cache performance demands limiting the number of clock cycles for various cache operations, there may be an upper limit to the number of indexing modes supported. For simplicity and without loss of generality, various example embodiments presented herein are primarily described within the context of a dual-mode indexed cache supporting two indexing modes (which, in many cases, may be sufficient since it can multiply the hit ratio of the cache by a factor of two); however, it will be appreciated that a larger number of modes may be supported by a multi-mode indexed cache. The operation of a multi-mode indexed cache may be further understood with respect to the following example.

As an example, assume that a <NUM>-bit memory block with address <NUM> needs to be stored in a multi-mode indexed cache. Here, it is noted that the bit positions start from <NUM> to higher from right to left. In this example, assume that the multi-mode indexed cache is an <NUM>-way set associative cache having <NUM> sets and where the size of each cache line is 64B. In this example, further assume that the multi-mode indexed cache supports two modes of indexing memory blocks, which are illustrated in <FIG>. In <FIG>, a set of indexing modes <NUM> includes a first indexing mode <NUM> (also denoted as Mode-<NUM>) and a second indexing mode <NUM> (also denoted as Mode-<NUM>). In both the first indexing mode <NUM> and the second indexing mode <NUM>, bits <NUM>-<NUM> are used for indexing an offset in a cache line. It is noted that Offset bit positions are the same across the modes since those <NUM> bits indicate the offset in a 64B cache line. In the first indexing mode <NUM>, bits <NUM>-<NUM> are used for indexing one of the <NUM> sets in the cache and bits <NUM>-<NUM> are used as the Tag. In the second indexing mode <NUM>, bits <NUM>-<NUM> are used for indexing one of the <NUM> sets in the cache and bits <NUM>-<NUM> are used as the Tag. It will be appreciated that, since the two indexing modes use disjoint set of bits to select a set in the multi-mode indexed cache, it is likely that an address will select disjoint sets for the two indexing modes.

In this example, assume that the multi-mode indexed cache attempts to store the memory block with the <NUM>-bit address (i.e., <NUM>) using mode-<NUM>. In mode-<NUM>, the address is partitioned as shown in <FIG>. Namely, as illustrated in <FIG>, the memory address partitioning <NUM> based on the first indexing mode (mode-<NUM>) is such that: (a) Offset(<NUM>-<NUM>) = <NUM>, (b) Index(<NUM>-<NUM>) = <NUM>, and (c) Tag(<NUM>-<NUM>) = <NUM>.

In this example, the set is determined by the Index bits <NUM>, which maps to set <NUM>. Here, assume that the current state of the multi-mode indexed cache is as shown in <FIG>. Namely, as illustrated in <FIG>, the multi-mode indexed cache state <NUM> is such that certain ways are occupied while others are empty. As illustrated in <FIG>, each cache line stores the indication in its metadata about the indexing mode used for the cache line to distinguish the bits from the address that is used as Tag. Here, "M" means the indexing mode and "T" means the Tag bits from the address of the memory block for the indexing mode.

In this example, when the multi-mode indexed cache attempts to store the memory block in one of the <NUM> ways in set <NUM> of the multi-mode indexed cache, the multi-mode indexed cache determines that none of the ways are empty. So, the multi-mode indexed cache, based on a determination that the attempt to store the memory block based on mode-<NUM> was unsuccessful, will then attempt to store the memory block using mode-<NUM>.

In this example, the multi-mode indexed cache then attempts to store the memory block with the <NUM>-bit address (i.e., <NUM>) using mode-<NUM>. In mode-<NUM>, the address is partitioned as shown in <FIG>. Namely, as illustrated in <FIG>, the memory address partitioning <NUM> based on the second indexing mode (mode-<NUM>) is such that: (a) Offset(<NUM>-<NUM>) = <NUM>, (b) Tag(<NUM>-<NUM>) = <NUM>, and (c) Index(<NUM>-<NUM>) = <NUM>.

In this example, the set is determined by the Index bits <NUM>, which maps to set <NUM>. Here, assume that the current state of the multi-mode indexed cache is still as shown in <FIG>, since the attempt to store the memory block based on mode-<NUM> was unsuccessful. When the multi-mode indexed cache attempts to store the memory block in one of the <NUM> ways in set <NUM> of the multi-mode indexed cache, the multi-mode indexed cache determines that way <NUM> and way <NUM> of set <NUM> are empty.

In this example, the multi-mode indexed cache stores the memory block in way <NUM> based on mode-<NUM>. The new state of the multi-mode indexed cache is as shown in <FIG>. Namely, as illustrated in <FIG>, the multi-mode indexed cache state <NUM> is such that way <NUM> of set <NUM> now stores the memory block, and the associated metadata is updated to indicate that the memory block was stored based on mode-<NUM> (M=<NUM>) and the Tag bits from the address of the memory block for the indexing mode are "<NUM>" (T=<NUM>). It is noted that, since there were no additional modes available, if no empty ways were identified in set <NUM> then the multi-mode indexed cache could have evicted a valid cache line from set <NUM> in order to store the memory block.

It is noted that it is possible that, by coincidence, the Index bits in mode-<NUM> and the Index bits in mode-<NUM> may be exactly the same. Consider the address <NUM>, where bits <NUM>-<NUM> are <NUM> and bits <NUM>-<NUM> also are <NUM>. In that case, both the indexing modes will map the address to the same set in the set associative cache. However, probabilistically, such collisions are expected to be quite rate. Further, the probability of such collisions reduces with an increase in the number of indexing modes.

Now, assume that, at some point, the exemplary address needs to be looked up in the cache. First, the cache needs to determine whether mode-<NUM> or mode-<NUM> should be used to start the lookup. This decision as to which mode is used to start the look-up may be based on various rules (e.g., Most Frequecy Used (MFU), Last Used (LU), or the like). In the MFU embodiment, for example, each time there is a hit in lookup of a cache line, a counter is incremented for the number of hits for the mode of the cache line and then the mode with the highest counter is used to start the lookup. In the LU embodiment, for example, the mode that was used for the previous successful lookup is recorded and used to start the lookup. It is noted that the various example embodiments of the MFU scheme may be further understood by way of reference to <FIG> and <FIG>.

As depicted in <FIG> and <FIG>, the cache maintains an MFU record in which the number of hits for each indexing mode is recorded. Assume, for example, that before storing the exemplary memory block, the hits for mode-<NUM> and mode-<NUM> were <NUM> and <NUM>, respectively. Then, the memory block was stored using mode-<NUM>, so the number of hits for mode-<NUM> in MFU record was incremented to <NUM>.

Now, while looking up the address in the cache, mode-<NUM> is used first since it has the highest number of hits (=<NUM>) in the MFU record. So, the address is mapped to set <NUM>. Then, each of the ways of set <NUM> is searched for matching the Tag bits <NUM>-<NUM>. If metadata of any way is marked as mode-<NUM> then that way is ignored. Eventually, no matching cache line is found.

Next, the cache decides to lookup the memory block in the cache using mode-<NUM>. So, the address is mapped to set <NUM>. Then, each of the ways of set <NUM> is searched for matching the Tag bits <NUM>-<NUM>. If metadata of any way is marked as mode-<NUM> then that way is ignored. Eventually, the cache line is found in way-<NUM> in set <NUM>.

Now, assume that a lookup of an address in a set requires C cycles and the cache supports M indexing modes. In that case, lookup of an address in the cache may require at the maximum MxC clock cycles (although if the address is a hit in the first set then it requires only C cycles). In the example, above it required 2xC cycles to lookup the exemplary address.

It will be appreciated that, although primarily presented with respect to example embodiments in which a lookup is performed in the M modes serially, in at least some example embodiments a lookup may be performed in the M modes in parallel or a lookup may be performed in the M modes using a combination of serial and parallel lookups (e.g., performing an initial lookup using the MFU mode or the LU mode and, if the initial lookup is not a hit then performing the lookups in the remaining modes in parallel). It will be appreciated that parallel lookups may be used if the additional power consumption due to parallel lookup is insignificant. Since each indexing mode selects a disjoint set, so parallel lookup among all M sets is possible and each lookup can be performed in C cycles.

<FIG> depicts an example embodiment of method for storing a memory block into a multi-mode indexed cache. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, the method <NUM> begins. As indicated by block <NUM>, the input to method <NUM> is a memory block to be stored in the cache. Block <NUM> retrieves the first indexing mode supported by the cache, and then the method <NUM> proceeds to block <NUM>. Block <NUM> determines the set for the address based on the selected mode, and then the method <NUM> proceeds to block <NUM>. Block <NUM> searches for an empty cache line in the set, and then the method <NUM> proceeds to block <NUM>. Block <NUM> checks if an empty cache line is found. If an empty cache line is not found then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if the cache supports more indexing modes. If the cache supports more indexing modes then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> retrieves the next indexing mode supported by the cache, and then the method <NUM> returns to block <NUM> to repeat subsequent blocks for the next indexing mode. Block <NUM>, which when reached means that no empty cache line is found in the sets selected by all of the supported indexing modes, evicts a valid cache line in the set selected by the last indexing mode, and then the method <NUM> proceeds to block <NUM>. Block <NUM> stores the memory block in the empty cache line, and then the method <NUM> proceeds to block <NUM>. Block <NUM> stores, into the metadata of the cache line, the indexing mode used to store the memory block in the cache line. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of a method for finding an empty cache line in a set of a multi-mode indexed cache. It will be appreciated that the method <NUM> may be used to provide block <NUM> of the method <NUM> of <FIG>. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. As indicated by block <NUM>, the input to method <NUM> is a set in the cache. Block <NUM> retrieves the first cache line in the set, and then the method <NUM> proceeds to block <NUM>. Block <NUM> checks if the cache line is empty. If the cache line is not empty then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if there are more cache lines in the set. If there are more cache lines in the set then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> retrieves the next cache line in the set and then the method <NUM> returns to block <NUM> to repeat subsequent blocks for the next cache line. Block <NUM> returns the empty cache line and then the method <NUM> proceeds to block <NUM> where the method <NUM> ends. Block <NUM> declares that no empty cache line is found in the set and then the method <NUM> proceeds to block <NUM>, where the method <NUM> ends. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of method for looking up a memory block in a multi-mode indexed cache. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, the method <NUM> begins. As indicated by block <NUM>, the input to method <NUM> is an address of a memory block to be looked up in the cache. Block <NUM> determines the mode to start with for looking up the memory block. This method assumes that the MFU scheme is used to determine the mode to start with; however it will be appreciated that the initial mode may be selected in various other ways. From block <NUM>, the method <NUM> proceeds to block <NUM>. Block <NUM> determines the set for the address as mapped by the mode, and then the method <NUM> proceeds to block <NUM>. Block <NUM> looks up the cache line in the set that matches the tag bits of the address as per the selected mode, and then the method <NUM> proceeds to block <NUM>. Block <NUM> checks if matching cache line is found. If the matching cache line is not found then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if there are more modes to try. If there are more modes to try then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> retrieves the next MFU mode and then the method <NUM> returns to block <NUM> to repeat subsequent blocks for the next mode. Block <NUM> declares a hit and then the method <NUM> proceeds to block <NUM> where the method <NUM> ends. Block <NUM> declares a miss and then the method <NUM> proceeds to block <NUM> where the method <NUM> ends. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of a method for finding a matching cache line in a set of a multi-mode indexed cache. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. It will be appreciated that the method <NUM> may be used to implement block <NUM> of the method <NUM> of <FIG>. At block <NUM>, the method <NUM> begins. As indicated by block <NUM>, the inputs to the method <NUM> include: (<NUM>) the set in the cache to lookup the memory block, (<NUM>) the Indexing mode, and (<NUM>) Tag bits from the address of the memory block, as per the indexing mode. Block <NUM> retrieves the first cache line in the set, and then the method <NUM> proceeds to block <NUM>. Block <NUM> checks if the cache line is empty. If the cache line is not empty then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if the indexing mode of the cache line is the same as the input indexing mode (i.e., indexing mode used to search the tag bits). If the indexing mode of the cache line is the same as the input indexing mode then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if the tag bits in the cache line are the same as the tag bits in the address of the memory block. If the tag bits in the cache line are the same as the tag bits in the address of the memory block then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> checks if there are more cache lines in the set. If there are more cache lines in the set then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> retrieves the next cache line in the set and then the method <NUM> returns to block <NUM> to repeat subsequent blocks for the next cache line. Block <NUM> declares a miss and then the method <NUM> proceeds to block <NUM> where the method <NUM> ends. Block <NUM> declares a hit and then the method <NUM> proceeds to block <NUM> where the method <NUM> ends. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of a method for operating a multi-mode indexed cache. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, the method <NUM> begins. At block <NUM>, detect, by a cache configured as a set associative cache having a plurality of sets, a request for a memory operation for a given memory block, wherein the cache is configured to support multiple indexing modes for indexing memory blocks, wherein the multiple indexing modes are configured to cause selection of different ones of the plurality of sets of the cache for the memory operation for the given memory block. At block <NUM>, perform, by the cache based on at least one of the multiple indexing modes, the memory operation for the given memory block. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of a method for operating a multi-mode indexed cache. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, the method <NUM> begins. At block <NUM>, operate a cache configured as a set associative cache having a plurality of sets, wherein the cache is configured to support multiple indexing modes for indexing memory blocks such that, for a memory operation for a given memory block, the multiple indexing modes are configured to cause selection of different ones of the plurality of sets of the cache for the memory operation for the given memory block. At block <NUM>, the method <NUM> ends.

Various example embodiments for providing a multi-mode indexed cache for a processor may be configured to be applied to various types of caches which may be implemented within or otherwise operate in association with processors, such as an instruction cache (IC) of a processor, a micro-operations cache (UC) of a processor, a data cache (DC) of a processor, a unified cache of a processor that can host instructions and data, a branch target buffer (BTB) associated with a branch predictor of a processor, or the like.

Various example embodiments for providing a multi-mode indexed cache for a processor may be configured to be used within various types of processors which may utilize caches, such as Complex Instruction Set Computer (CISC) processors, Reduced Instruction Set Computer (RISC) processors, or any other types of processors or other devices which may utilize caches.

Various example embodiments for providing a multi-mode indexed cache for a processor may provide various advantages or potential advantages. For example, various example embodiments for providing a multi-mode indexed cache for a processor may be configured to minimize conflict misses in a cache by dynamically adjusting the indexing mode of the cache so that Q remains less than N for a working set (i.e., memory blocks accessed during program execution). For example, various example embodiments for providing a multi-mode indexed cache for a processor may be configured to obviate the need for use of a victim cache (e.g., whether it is a supplementary cache or an existing next-level cache), which is used to store evicted cache lines (i.e., victims) and looked up in the case of a cache miss so that recently evicted cache lines can be brought back into the cache, thereby obviating the need for performing additional lookups in the supplementary cache that consume additional clock cycles on the processor and, in the case where a supplementary cache is to be used as the victim cache, obviating the need for use of additional circuitry that consumes power and area on the processor die. Various example embodiments for providing a multi-mode indexed cache for a processor may provide various other advantages or potential advantages.

<FIG> depicts an example embodiment of a computer suitable for use in performing various functions presented herein.

The computer <NUM> includes a processor <NUM> (e.g., a central processing unit (CPU), a processor, a processor having a set of processor cores, a processor core of a processor, or the like) and a memory <NUM> (e.g., a random access memory (RAM), a read-only memory (ROM), or the like). In at least some example embodiments, the computer <NUM> may include at least one processor and at least one memory storing instructions that, when executed by the at least one processor, cause the computer to perform various functions presented herein.

The computer <NUM> also may include a cooperating element <NUM>. The cooperating element <NUM> may be a hardware device. The cooperating element <NUM> may be a process that can be loaded into the memory <NUM> and executed by the processor <NUM> to implement various functions presented herein (in which case, for example, the cooperating element <NUM> (including associated data structures) can be stored on a non-transitory computer readable medium, such as a storage device or other suitable type of storage element (e.g., a magnetic drive, an optical drive, or the like)).

It will be appreciated that computer <NUM> may represent a general architecture and functionality suitable for implementing functional elements described herein, portions of functional elements described herein, or the like, as well as various combinations thereof. For example, computer <NUM> may provide a general architecture and functionality that is suitable for implementing one or more elements presented herein.

It will be appreciated that at least some of the functions presented herein may be implemented in software (e.g., via implementation of software on one or more processors, for executing on a general purpose computer (e.g., via execution by one or more processors) so as to provide a special purpose computer, and the like) and/or may be implemented in hardware (e.g., using a general purpose computer, one or more application specific integrated circuits, and/or any other hardware equivalents).

It will be appreciated that at least some of the functions presented herein may be implemented within hardware, for example, as circuitry that cooperates with the processor to perform various functions. Portions of the functions/elements described herein may be implemented as a computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer such that the methods and/or techniques described herein are invoked or otherwise provided. Instructions for invoking the various methods may be stored in fixed or removable media (e.g., non-transitory computer readable media), transmitted via a data stream in a broadcast or other signal bearing medium, and/or stored within a memory within a computing device operating according to the instructions.

Claim 1:
An apparatus, comprising:
a cache (<NUM>) configured as a set associative cache having a plurality of sets, wherein the cache is configured to support multiple indexing modes (<NUM>) for indexing memory blocks such that, for a memory operation for a given memory block, the multiple indexing modes (<NUM>) are configured to cause selection of different ones of the plurality of sets of the cache (<NUM>) for the memory operation for the given memory block,
characterized in that each indexing mode uses a disjoint subset of bits from the memory block address to select the set in the set associative cache.