Patent Description:
D2 <CIT> discloses a configurable n-way TLB, in terms of number of ways, page sizes, number of entries per way; and various TLB replacement algorithms.

D3 <NPL>, discloses a skewed set-associative TLB with page size control and a TLB replacement algorithm.

D4 <CIT> discloses the configuring of a subset of cache ways into groups.

D5 <NPL>, is a seminal paper disclosing the concept of skewed set-associative TLB.

D6 <CIT> discloses the enabling of a delayed replacement of entries of e.g. four-way set associative cache, by determining whether first and second replacement entries in the cache are respectively replaced corresponding to large and small page sizes.

Some alternatives provide a method for determining an address in a physical memory which corresponds to a virtual address using a skewed-associative translation lookaside buffer. A virtual address and a configuration indication are received using receiver circuitry. A physical address corresponding to the virtual address is output on a condition that a TLB hit occurs. A first subset of a plurality of ways of the TLB is configured to hold a first page size. The first subset includes a number of the ways that is based on the configuration indication.

In some alternatives, a second subset of the plurality of ways is configured to hold a second page size. The second subset includes a number of the ways that is based on the configuration indication. In some alternatives, a ratio of the number of ways included in the first subset to the number of ways included in the second subset is based on the configuration indication. In some alternatives, an index to the plurality of ways is calculated by a skewing function based on the configuration indication. In some alternatives, a subset of bits of the virtual address is input to the skewing function. Which bits of the virtual address are included in the subset of bits is calculated based on the configuration indication. In some alternatives, the configuration indication is received from a basic input output system (BIOS), a blown fuse, an operating system (OS), or a configuration register. In some alternatives, the configuration indication includes a single bit.

Some alternatives provide a skewed-associative translation lookaside buffer (TLB). The TLB includes a plurality of ways, input circuitry configured to receive a virtual address and a configuration indication, and output circuitry configured to output a physical address corresponding to the virtual address on a condition that a TLB hit occurs. The first subset of the ways is configured to hold a first page size. The first subset includes a number of the ways that is based on the configuration indication.

In some alternatives, a second subset of the plurality of ways is configured to hold a second page size. The second subset includes a number of the ways that is based on the configuration indication. In some alternatives, a ratio of the number of ways included in the first subset to the number of ways included in the second subset is based on the configuration indication. In some alternatives, an index to the plurality of ways is calculated by a skewing function based on the configuration indication. In some alternatives, a subset of bits of the virtual address is input to the skewing function. Which bits of the virtual address are included in the subset of bits is calculated based on the configuration indication. In some alternatives, the configuration indication is received from a BIOS, a blown fuse, an OS, or a configuration register. In some alternatives, the configuration indication includes a single bit.

Some alternatives provide an accelerated processing device (APD) including a skewed-associative translation lookaside buffer (TLB). The TLB includes a plurality of ways, input circuitry configured to receive a virtual address and a configuration indication, and output circuitry configured to output a physical address corresponding to the virtual address on a condition that a TLB hit occurs. A first subset of the ways is configured to hold a first page size. The first subset includes a number of the ways that is based on the configuration indication.

In some alternatives, a second subset of the plurality of ways is configured to hold a second page size. The second subset includes a number of the ways that is based on the configuration indication. In some alternatives, a ratio of the number of ways included in the first subset to the number of ways included in the second subset is based on the configuration indication. In some alternatives, an index to the plurality of ways is calculated by a skewing function which is based on the configuration indication. In some alternatives, a subset of bits of the virtual address is input to the skewing function. Which bits of the virtual address are included in the subset of bits is calculated based on the configuration indication. In some alternatives, the configuration indication is received from a BIOS, a blown fuse, an OS, or a configuration register. In some alternatives, the configuration indication includes a single bit.

Some alternatives provide a method for determining an address in a physical memory which corresponds to a virtual address using a skewed-associative translation lookaside buffer (TLB). The method includes using receiver circuitry to receive a virtual address and a configuration indication and retrieving a physical address corresponding to the virtual address from a page table if a TLB miss occurs at least a portion of the physical address is installed in a least recently used (LRU) way of a subset of a plurality of ways the TLB. The LRU way is determined according to a replacement policy. The replacement policy is based on the configuration indication.

In some alternatives, the subset of the ways includes a number of the plurality of ways that is based on the configuration indication. In some alternatives, a ratio of the number of the plurality of ways included in the subset to a number of ways included in a second subset is based on the configuration indication. In some alternatives, an index to the plurality of ways is calculated by a skewing function based on the configuration indication. In some alternatives, a subset of bits of the virtual address is input to the skewing function. Which bits of the virtual address are included in the subset of bits is calculated based on the configuration indication. In some alternatives, the configuration indication is received from a BIOS, a blown fuse, an OS, or a configuration register. In some alternatives, the configuration indication includes a single bit.

Some alternatives provide a skewed-associative translation lookaside buffer (TLB). The TLB includes a plurality of ways, input circuitry configured to receive a virtual address and a configuration indication, to retrieve a physical address corresponding to the virtual address from a page table on a condition that a TLB miss occurs, and replacement circuitry configured to install at least a portion of the physical address in a least recently used (LRU) way of a subset of a plurality of ways the TLB. The LRU way is determined according to a replacement policy. The replacement policy is based on the configuration indication.

Some alternatives provide an accelerated processing device (APD) including a skewed-associative translation lookaside buffer (TLB). The TLB includes a plurality of ways, input circuitry configured to receive a virtual address and a configuration indication. The input circuitry is also configured to retrieve a physical address corresponding to the virtual address from a page table if a TLB miss occurs. The TLB also includes replacement circuitry configured to install at least a portion of the physical address in a least recently used (LRU) way of a subset of a plurality of ways the TLB. The LRU way is determined according to a replacement policy. The replacement policy is based on the configuration indication.

In some alternatives, the subset of the ways includes a number of the plurality of ways that is based on the configuration indication. In some alternatives, a ratio of the number of the plurality of ways included in the subset to a number of ways included in a second subset is based on the configuration indication. In some alternatives, an index to the plurality of ways is calculated by a skewing function based on the configuration indication. In some alternatives, a subset of bits of the virtual address is input to the skewing function; wherein which bits of the virtual address are included in the subset of bits is calculated based on the configuration indication. In some alternatives, the configuration indication is received from a BIOS, a blown fuse, an OS, or a configuration register. In some alternatives, the configuration indication includes a single bit.

<FIG> is a block diagram of an example device <NUM> in which one or more disclosed alternatives can be implemented. The device <NUM> includes, for example, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device <NUM> includes a processor <NUM>, a memory <NUM>, a storage <NUM>, one or more input devices <NUM>, and one or more output devices <NUM>. The device <NUM> can also optionally include an input driver <NUM> and an output driver <NUM>. It is understood that the device <NUM> can include additional components not shown in <FIG>.

The processor <NUM> includes, for example, a central processing unit (CPU), a graphics processing unit (GPU), a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core can be a CPU or a GPU. The memory <NUM> can be located on the same die as the processor <NUM>, or can be located separately from the processor <NUM>. The memory <NUM> includes, for example, a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The storage <NUM> includes, for example, a fixed or removable storage, for example, a hard disk drive, a solid state drive, an optical disk, or a flash drive. The input devices <NUM> include, for example, a keyboard, a keypad, a touch screen, a touch pad, a detector, a microphone, an accelerometer, a gyroscope, a biometric scanner, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals). The output devices <NUM> include, for example, a display, a speaker, a printer, a haptic feedback device, one or more lights, an antenna, or a network connection (e.g., a wireless local area network card for transmission and/or reception of wireless IEEE <NUM> signals).

The input driver <NUM> communicates with the processor <NUM> and the input devices <NUM>, and permits the processor <NUM> to receive input from the input devices <NUM>. The output driver <NUM> communicates with the processor <NUM> and the output devices <NUM>, and permits the processor <NUM> to send output to the output devices <NUM>. It is noted that the input driver <NUM> and the output driver <NUM> are optional components, and that the device <NUM> will operate in the same manner if the input driver <NUM> and the output driver <NUM> are not present. The output driver <NUM> includes an accelerated processing device ("APD") <NUM> which is coupled to a display device <NUM>. The APD is configured to accept compute commands and graphics rendering commands from processor <NUM>, to process those compute and graphics rendering commands, and to provide pixel output to display device <NUM> for display.

As described in further detail below, the APD <NUM> includes one or more parallel processing units configured to perform computations in accordance with a single-instruction-multiple-data ("SIMD") paradigm. Thus, although various functionality is described herein as being performed by or in conjunction with the APD <NUM>, the functionality described as being performed by the APD <NUM> can also be performed by other computing devices having similar capabilities that are not driven by a host processor (e.g., processor <NUM>) and configured to provide graphical output to a display device <NUM>. For example, it is contemplated that any processing system that performs processing tasks in accordance with a SIMD paradigm can be configured to perform the functionality described herein. Alternatively, it is contemplated that computing systems that do not perform processing tasks in accordance with a SIMD paradigm can perform the functionality described herein.

<FIG> is a block diagram of the device <NUM>, illustrating additional details related to execution of processing tasks on the APD <NUM>. The processor <NUM> maintains, in system memory <NUM>, one or more control logic modules for execution by the processor <NUM>. The control logic modules include an operating system <NUM>, a kernel mode driver <NUM>, and applications <NUM>. These control logic modules control various aspects of the operation of the processor <NUM> and the APD <NUM>. For example, the operating system <NUM> directly communicates with hardware and provides an interface to the hardware for other software executing on the processor <NUM>. The kernel mode driver <NUM> controls operation of the APD <NUM> by, for example, providing an application programming interface ("API") to software (e.g., applications <NUM>) executing on the processor <NUM> to access various functionality of the APD <NUM>. The kernel mode driver <NUM> also includes a just-in-time compiler that compiles programs for execution by processing components (such as the SIMD units <NUM> discussed in further detail below) of the APD <NUM>.

The APD <NUM> executes commands and programs for selected functions, such as graphics operations and non-graphics operations, such as those that are suited for parallel processing. The APD <NUM> can be used for executing graphics pipeline operations such as pixel operations, geometric computations, and rendering an image to display device <NUM> based on commands received from the processor <NUM>. The APD <NUM> also executes compute processing operations that are not directly related to graphics operations, such as operations related to video, physics simulations, computational fluid dynamics, or other tasks, based on commands received from the processor <NUM>.

The APD <NUM> includes compute units <NUM> that include one or more SIMD units <NUM> that are configured to perform operations at the request of the processor <NUM> in a parallel manner according to a SIMD paradigm. The SIMD paradigm is one in which multiple processing elements share a single program control flow unit and program counter and thus execute the same program but are able to execute that program with different data. In one example, each SIMD unit <NUM> includes sixteen lanes, where each lane executes the same instruction at the same time as the other lanes in the SIMD unit <NUM> but can execute that instruction with different data. Lanes can be switched off with predication if not all lanes need to execute a given instruction. Predication can also be used to execute programs with divergent control flow. More specifically, for programs with conditional branches or other instructions where control flow is based on calculations performed by an individual lane, predication of lanes corresponding to control flow paths not currently being executed, and serial execution of different control flow paths allows for arbitrary control flow.

The basic unit of execution in compute units <NUM> is a work-item. Each work-item represents a single instantiation of a program that is to be executed in parallel in a particular lane. Work-items are executed simultaneously as a "wavefront" on a single SIMD processing unit <NUM>. Multiple wavefronts are included in a "work group," which includes a collection of work-items designated to execute the same program. A work group are executed by executing each of the wavefronts that make up the work group. The wavefronts are executed sequentially on a single SIMD unit <NUM> or partially or fully in parallel on different SIMD units <NUM>. Wavefronts are the largest collection of work-items that can be executed simultaneously on a single SIMD unit <NUM>. Thus, if commands received from the processor <NUM> indicate that a particular program is to be parallelized to such a degree that the program cannot execute on a single SIMD unit <NUM> simultaneously, then that program is broken up into wavefronts which are parallelized on two or more SIMD units <NUM> or serialized on the same SIMD unit <NUM> (or both parallelized and serialized as needed). A scheduler <NUM> is configured to perform operations related to scheduling various wavefronts on different compute units <NUM> and SIMD units <NUM>.

The parallelism afforded by the compute units <NUM> is suitable for graphics related operations such as pixel value calculations, vertex transformations, and other graphics operations. A graphics pipeline <NUM> which accepts graphics processing commands from the processor <NUM> can thus provide computation tasks to the compute units <NUM> for execution in parallel.

The compute units <NUM> are also used to perform computation tasks not related to graphics or not performed as part of the "normal" operation of a graphics pipeline <NUM> (e.g., custom operations performed to supplement processing performed for operation of the graphics pipeline <NUM>). An application <NUM> or other software executing on the processor <NUM> transmits programs that define such computation tasks to the APD <NUM> for execution.

Processor <NUM> can support virtual memory, and memory <NUM> includes, for example, a page table having page table entries which map virtual page numbers to physical page numbers in memory. Processor <NUM> includes or is in operative communication with a translation lookaside buffer (TLB) which caches page table entries so that processor <NUM> does not need to access memory <NUM> to retrieve a physical address from the page table for recently used virtual addresses.

Depending upon the virtual memory behavior of an application, different virtual page sizes can yield different performance. For example, using a small page size can avoid allocating physical memory space for unused data or instructions, and using a large page size can result in a single page fault affecting a large amount of data and/or instructions. Accordingly, some architectures support more than one virtual page size.

Set-associative TLBs cannot efficiently support multiple page sizes for a single process. Thus, architectures supporting the use of more than one page size have implemented either fully associative TLBs or using separate TLBs for each page size. A fully associative TLB is limited to a small number of entries, and using distinct partially associative TLBs for different page sizes requires knowledge of the distribution of page sizes for the intended use of the system. This can result in inefficiency where the actual use varies from the predicted page size distribution.

A skewed associative TLB is a variation on an n-way set associative TLB where an input index is modified by a skewing function that is different for some or all of the n-ways of the TLB. A skewed associative TLB can also be used to support more than one page size. In such implementations a fixed number of the ways of a skewed associative TLB is used to support certain page sizes. For example, in a skewed associative TLB having <NUM> ways, for any TLB lookup, <NUM> of the ways are dedicated to holding <NUM> kilobyte size pages, <NUM> of the ways are dedicated to holding <NUM> kilobyte size pages, and <NUM> of the ways are dedicated to holding <NUM> megabyte size pages. The mapping of which ways hold which page size is not fixed, but is determined by bits of the virtual address.

For some workloads, such as those that heavily utilize small pages, one page size way configuration can work well (e.g., having a small number of ways dedicated for <NUM> kilobyte and <NUM> megabyte sized pages, and a greater number dedicated for <NUM> kilobyte sized pages). Here, more ways are allocated for handling of small pages. For other workloads, such as those that heavily utilize large pages, another page size way configuration can work well (e.g., having a greater number of ways dedicated for <NUM> kilobyte and <NUM> megabyte sized pages, and a smaller number dedicated for <NUM> kilobyte sized pages).

A typical skewed associative TLB is non-configurable, and cannot be optimized for all workloads because although all ways of such TLBs can hold all page sizes, such TLBs are tuned to a particular distribution of page sizes. A non-skewed associative TLB can have even worse performance because not all ways of the TLB can hold all page sizes (and is thus area-inefficient, wasting storage space on page sizes that are not used by some workloads), and because it is also tuned to a particular distribution of page sizes.

<FIG> is a block diagram of an example configurable skewed associative TLB <NUM>. The illustration of skewed associative TLB <NUM> is simplified for clarity; and it is noted that a skewed associative TLB can include various components (e.g., relating to permissions, additional tagging bits, flushing, etc.) that are not shown. Configurable skewed associative TLB <NUM> is implemented in device <NUM> in this example, although it will be appreciated that other implementations are possible. For example, in various implementations TLB <NUM> is implemented as a component of processor <NUM>, as a component of memory <NUM>, or in a device operatively coupled with processor <NUM> and memory <NUM>, such as a memory management unit (MMU). Various other implementations of TLB <NUM> are also possible, both in and out of the context of device <NUM>.

TLB <NUM> is implemented as a content-addressable memory (CAM) in this example, where the search key is a virtual page number (from a virtual memory address), and the search result is a physical page number for a physical memory address (e.g., of memory <NUM>). TLB <NUM> includes <NUM> ways <NUM> (only three of which, <NUM>', <NUM>", <NUM>‴, corresponding to ways <NUM>, <NUM>, and <NUM>, are shown for clarity; all ways are collectively referred to as <NUM>). Ways <NUM> each include <NUM> entries, each of which are <NUM> bits wide. Each entry of ways <NUM> includes a tag and a payload, where the tag is used for indexing by comparison with the virtual page number, and the payload is a corresponding physical page number (or includes a corresponding physical page number). The page offset of the virtual address can be the same as the page offset of the physical address, and can be used to construct the physical memory address by combining the offset with the physical page number.

TLB <NUM> supports three different virtual page sizes, <NUM> kilobytes (<NUM>), <NUM> kilobytes (<NUM>) and <NUM> megabytes (<NUM>). For any lookup in the TLB <NUM>, each way holds a translation that is defined with respect to only one of the different virtual page sizes, and the distribution of supported page sizes among ways <NUM> is configurable. For example, in an <NUM>-<NUM>-<NUM> configuration, <NUM> of ways <NUM> are configured to support <NUM> pages, <NUM> of ways <NUM> are configured to support <NUM> pages, and <NUM> of ways <NUM> are configured to support <NUM> pages. In contrast, a <NUM>-<NUM>-<NUM> configuration would have <NUM> of ways <NUM> configured to support <NUM> pages, <NUM> of ways <NUM> configured to support <NUM> pages, and <NUM> of ways <NUM> configured to support <NUM> pages. The number of ways, the number and width of way entries, the number and sizes of supported virtual pages, and the number and distribution of way configuration are all exemplary, and any suitable configuration of these components can be used. This applies to all implementations described herein with respect to any figure.

In order to configure the supported page size for each of ways <NUM> (i.e., to select between the <NUM>-<NUM>-<NUM> and <NUM>-<NUM>-<NUM> configurations in this example), a configuration bit <NUM> is input to a skewing function of each way. In some implementations, the configuration bit <NUM> selects a ratio of the number of ways allocated to each supported page size. Each way includes or is operatively coupled to its own skewing function block (only skewing function blocks <NUM>', <NUM>" and <NUM>‴ are shown; all skewing function blocks are collectively referred to as <NUM>) which implements the skewing function for that way. The same configuration bit <NUM> is input to each skewing function block <NUM>. Configuration bit <NUM> can be set statically or dynamically in any suitable manner. For example, configuration bit <NUM> can be set by blowing fuses or setting nonvolatile memory registers in TLB <NUM> (or other components of a processor on which the TLB is implemented or to which the TLB <NUM> is operatively coupled), or can be set in the basic input output system (BIOS) of a computer system of which TLB <NUM> is a component. Configuration bit <NUM> can also or alternatively be set by an operating system, or otherwise set in a register of the TLB <NUM> or other component of a processor on which the TLB is implemented or to which the TLB <NUM> is operatively coupled.

In order to translate a virtual address to a physical address, a virtual address <NUM> is input to TLB <NUM>. If TLB <NUM> is a level two (L2) TLB, virtual address <NUM> can be input from a level one (L1) TLB following an L1 TLB miss for example, although other suitable implementations are possible. Virtual address <NUM> includes a virtual page number and an offset into the virtual page. Virtual address <NUM> is <NUM> bits wide in this example, although other implementations can use any suitable width. In <FIG>, the <NUM> bits of virtual address <NUM> are expressed as [<NUM>:<NUM>]. A subset of the <NUM> bits corresponds to the virtual page number, and another subset of the <NUM> bits corresponds to the offset. Which bits are used depends upon the virtual page size relevant to virtual address <NUM>.

If virtual address <NUM> reflects a <NUM> page, bits [<NUM>:<NUM>] are the page number, and bits [<NUM>:<NUM>] are the offset into the page. If virtual address <NUM> reflects a <NUM> page, bits [<NUM>:<NUM>] are the page number, and bits [<NUM>:<NUM>] are the offset into the page. If virtual address <NUM> reflects a <NUM> page, bits [<NUM>:<NUM>] are the page number, and bits [<NUM>:<NUM>] are the offset into the page. The least significant bit which is common to all three page sizes is [<NUM>]. Accordingly, bits [<NUM>:<NUM>] are used to determine which ways are used to hold which page sizes for that value of [<NUM>:<NUM>], and are input to skewing function block <NUM> for each way. Bits below [<NUM>] in the range are not chosen for this purpose because for a <NUM> page those bits are part of the offset - not the page number, and are not processed by the translation hardware (the offset is passed through to the physical address). In some implementations however, other bits above [<NUM>] could be used. Further, one bit or more than two bits could be used for indexing if way configurations supporting only two or greater than three page sizes are implemented.

Skewing function blocks <NUM> each input the configuration bit <NUM> and bits [<NUM>:<NUM>] of virtual address <NUM>, and output a value which generated by applying a skewing function <NUM> to the inputs. The skewing function <NUM> for each way can be different (only skewing functions <NUM>', <NUM>" and <NUM>‴ are shown; all skewing functions are collectively referred to as <NUM>). Tables <NUM> and <NUM> list examples of which ways of the <NUM> ways <NUM> are used to store physical addresses of the different page sizes based on the configuration bit <NUM> (selecting between the <NUM>-<NUM>-<NUM> configuration and the <NUM>-<NUM>-<NUM> configuration) and bits [<NUM>:<NUM>] of virtual address <NUM>.

Each way <NUM> is indexed by an index multiplexer (<NUM>', <NUM>" and <NUM>‴ are shown, all index multiplexers are collectively referred to as <NUM>). Each index multiplexer <NUM> inputs three possible indexes, one for each possible page size of the input virtual address <NUM>. The indexes are ranges of bits of the virtual page number portion of virtual address <NUM>. The range of bits differs for each page size. In this example, index multiplexer <NUM> inputs bits [<NUM>:<NUM>] of virtual address <NUM> if virtual address <NUM> reflects a <NUM> page size, inputs bits [<NUM>, <NUM>:<NUM>] of virtual address <NUM> if virtual address <NUM> reflects a <NUM> page size, or inputs bits [<NUM>:<NUM>] of virtual address <NUM> if virtual address <NUM> reflects a <NUM> page size. Each multiplexer <NUM> selects which of the three possible indexes to use for each way (<NUM>', <NUM>" and <NUM>‴ are shown; all indexes are collectively referred to as <NUM>) based on its respective skewing function <NUM>.

Each way <NUM> outputs the payload of the entry corresponding to the index selected by multiplexer <NUM> as read data (read data <NUM>', <NUM>" and <NUM>‴ are shown; all read data are collectively referred to as <NUM>). The read data <NUM> registers are each checked by comparison circuitry <NUM> to determine whether a TLB hit has occurred (i.e., that one of the ways has a translation that matches the lookup address). Comparison circuitry <NUM> determines whether a TLB hit has occurred by determining whether the virtual address tag held in the entry matches the lookup virtual address, and that the page size of the entry read out as read data <NUM> matches the page size determined by the skewing function (e.g., where the page size is indicated by a page size field in the payload). If a hit has occurred, the read data <NUM> which resulted in the TLB hit is selected, and the physical address <NUM> corresponding to the virtual address <NUM> is output from the TLB.

<FIG> is a flow chart illustrating an example method <NUM> for translating a virtual address to a physical memory address using the configurable skewed associative TLB <NUM> of <FIG>.

On a condition <NUM> that virtual address <NUM> is input to the TLB, index multiplexers <NUM> are set in step <NUM>, based on a subset of the bits of the virtual address <NUM> (in this example, bits [<NUM>:<NUM>]) to input one of the three possible indexes, one for each page size, using bits from virtual address <NUM>.

The range of bits differs for each page size. On a condition <NUM> that bits [<NUM>:<NUM>] indicate that virtual address <NUM> corresponds to a first page size (in this example, <NUM>), index multiplexers <NUM> input a first subset of the bits of the virtual address <NUM> (in this example, bits [<NUM>:<NUM>]) in step <NUM>. On a condition <NUM> that bits [<NUM>:<NUM>] indicate that virtual address <NUM> corresponds to a second page size (in this example, <NUM>), index multiplexers <NUM> input a second subset of the bits of the virtual address <NUM> (in this example, bits [<NUM>, <NUM>:<NUM>]) in step <NUM>. On a condition <NUM> that bits [<NUM>:<NUM>] indicate that virtual address <NUM> corresponds to a third page size (in this example, <NUM>), index multiplexers <NUM> input a third subset of the bits of the virtual address <NUM> (in this example, bits [<NUM>:<NUM>]) in step <NUM>.

After the index multiplexers <NUM> have input the appropriate bits of virtual address <NUM>, each multiplexer <NUM> selects one the inputs based on its respective skewing function <NUM> to generate indexes <NUM> to each way <NUM> (step <NUM>). If any of indexes <NUM> hits an entry in one of ways <NUM>, the corresponding physical page number is output to the respective read data <NUM> register (step <NUM>). On a condition <NUM> that the result is a TLB miss, TLB <NUM> initiates a page walk in step <NUM>. If the result is a TLB hit, physical address <NUM> corresponding to the virtual address <NUM> is output from the TLB based on the physical address output as read data <NUM> and the page offset of the virtual address <NUM> (step <NUM>).

If a TLB miss occurs, TLB <NUM> retrieves the corresponding physical address <NUM> via known methods, such as by walking a page table, and installs the retrieved physical address <NUM> in one of ways <NUM> according to a replacement policy. The replacement policy used can depend upon the distribution of supported page sizes among ways <NUM>. For example, a different replacement policy can be used for <NUM> pages depending upon whether <NUM> pages are stored in an <NUM>-way associative configuration (e.g., the <NUM>-<NUM>-<NUM> configuration described above) or in a <NUM>-way associative configuration (e.g., the <NUM>-<NUM>-<NUM> configuration described above).

In one example, a standard pseudo-least-recently-used (pseudo-LRU; i.e., tree-LRU) scheme is implemented to determine which way <NUM> contains an entry corresponding to the index <NUM> that is least recently used for <NUM> pages in the <NUM>-way associative configuration. A hybrid LRU scheme can be implemented to determine the LRU entry for <NUM> pages in the <NUM>-way associative configuration. Which LRU scheme to use can be selected using the configuration bit <NUM>.

Each line of TLB <NUM> has an associated sequence of <NUM> bits (which can be referred to as LRU bits) for tracking how recently the line has been accessed. The seven LRU bits apply to the same index in all ways, so in this example there are <NUM> groups of LRU bits. Each set of LRU bits indicates which way is least recently used for its respective index of TLB <NUM>. By selecting the appropriate LRU scheme to apply to the LRU bits, the same LRU bits can be used to track which way is least recently used for the <NUM>-<NUM>-<NUM> configuration or the <NUM>-<NUM>-<NUM> configuration.

<FIG> is a flow chart which illustrates an example method <NUM> for handling a TLB miss. On a condition <NUM> that a TLB miss has occurred (e.g., as in step <NUM> of <FIG>), TLB <NUM> initiates a page walk according to known methods in step <NUM> to retrieve the physical address. On a condition <NUM> that configuration bit <NUM> indicates that <NUM> of the <NUM> ways <NUM> are configured to support <NUM> pages (i.e., the <NUM>-<NUM>-<NUM> configuration described above), the least recently used one of ways <NUM> that is configured for <NUM> pages is determined using LRU logic in step <NUM>. In some implementations, the LRU logic includes pseudo-LRU (i.e., "tree" LRU) logic. On a condition <NUM> that configuration bit <NUM> indicates that <NUM> of the <NUM> ways <NUM> are configured to support <NUM> pages (i.e., the <NUM>-<NUM>-<NUM> configuration described above), the least recently used one of ways <NUM> that is configured for <NUM> pages is determined using LRU logic in step <NUM>. In some implementations, the LRU logic in step <NUM> follows a hybrid scheme including both "tree" LRU and "true" LRU logic. In either case, the physical address retrieved during the page walk is installed in the least recently used of ways <NUM> that is configured for <NUM> pages, as determined in either step <NUM> or <NUM> (step <NUM>). Corresponding procedures are also used for the <NUM> and <NUM> page sizes.

It should be understood that many variations are possible based on the disclosure herein. Although features and elements are described above in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements.

The methods provided can be implemented in a general purpose computer, a processor, or a processor core. Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine. Such processors can be manufactured by configuring a manufacturing process using the results of processed hardware description language (HDL) instructions and other intermediary data including netlists (such instructions capable of being stored on a computer readable media). The results of such processing can be maskworks that are then used in a semiconductor manufacturing process to manufacture a processor which implements aspects of the alternatives.

Claim 1:
A method for determining an address in a physical memory (<NUM>) which corresponds to a virtual address (<NUM>) using a skewed-associative translation lookaside buffer (<NUM>), the method comprising:
receiving a configuration indication (<NUM>);
receiving a virtual address (<NUM>), wherein the configuration indication is not part of the virtual address;
inputting the configuration indication and a first subset of bits of the virtual address to a skewing function (<NUM>) of each way (<NUM>) of the translation lookaside buffer (<NUM>);
configuring, based on the configuration indication (<NUM>) and the first subset of bits of the virtual address (<NUM>), a first subset of a plurality of ways (<NUM>) of the translation lookaside buffer to look up physical addresses (<NUM>) based on a second subset of bits of the virtual address with respect to a first page size and not with respect to a second page size, wherein the first subset of the plurality of ways is based on the configuration indication;
configuring, based on the configuration indication (<NUM>) and the first subset of bits of the virtual address (<NUM>), a second subset of the plurality of ways (<NUM>) of the translation lookaside buffer to look up physical addresses (<NUM>) based on a third subset of bits of the virtual address with respect to the second page size and not with respect to the first page size, wherein the second subset of the plurality of ways is based on the configuration indication; and
outputting a physical address (<NUM>) corresponding to the virtual address (<NUM>) on a condition that a translation lookaside buffer hit occurs.