Patent Description:
Using virtual addressing, processors can access memory, using physical addresses that are generated from virtual address to physical address translation. To accelerate the virtual address to physical address translation process, processors can use Translation Lookaside Buffers (TLB), which are content addressable memory (CAM) plus random access memory (RAM) structures that cache virtual address to physical address translations.

TLBs are, therefore, hardware structures that are used in computing systems to cache virtual-to-physical address translations and operating system (OS)-page-granularity metadata (e.g., read/write permissions). The TLB is important to performance scalability in computing systems because the TLB is looked up on every memory access, it is in the critical path, and each processor core or accelerator has its own TLB.

Microprocessors implement multiple threads in order to cut down on cell count to make it appear that more processors are present in a system by taking advantage of what could be "dead" cycles in a microprocessor. In many places in the microprocessor, pipe states are tagged with a thread identifier (ID) and existing resources in the processor are shared across threads. This sharing of resources cuts down on cell count but can be expensive with respect to power, especially if there is a high amount of circuit activity in changing from one thread to the other.

For example, <FIG> shows a block diagram of multi-thread system <NUM> implementing a CAM <NUM>. The CAM <NUM> includes a single bank of registers <NUM> coupled and corresponding to a single bank of comparators <NUM> for performing write and lookup operations. The multi-thread system <NUM> further includes a thread <NUM> (T0) and a thread <NUM> (T1), which each include their own search data registers <NUM> and <NUM> that store an address or tag to input to the CAM <NUM>. The stored tag for each thread is input to the multiplexer <NUM>, which selects one of the tags for input to the CAM <NUM> based on a "T1 active" bit. An input address <NUM> (i.e., the selected tag) is then provided to the CAM <NUM>. Upon performing a lookup operation using the input address <NUM>, the CAM <NUM> outputs a match result <NUM> (e.g., "hit" or "miss") based on the CAM entries stored in the bank of registers <NUM>. Lastly, the match result <NUM> is ANDed with an "any thread valid" bit by an AND gate <NUM>, which ensures that one of the threads (e.g., thread <NUM> or <NUM>) is valid before outputting the match result <NUM> as the output <NUM>.

In a typical operation of the multi-thread system <NUM>, the input address <NUM> is cycled back and forth between thread <NUM> and thread <NUM>. Since each thread shares the same bank of comparators <NUM>, toggling can occur in the configuration of the bank of comparators <NUM> on every cycle depending on the address contents provided by the search data registers <NUM> and <NUM>. A toggling of an input to a component (e.g., XOR, XNOR, OR or AND gate depending on implementation) of a comparator consumes power. Thus, when a larger number of comparators, or components thereof, are toggled, a thrashing of state occurs, resulting in an increase in dynamic power consumption. This can particularly occur when a large number of bits of an input address from one thread are different from bits of an input address from a second thread due to the threads being completely independent. This power consumption can be costly if the toggling occurs cycle to cycle. Thus, there exists the need to reduce power consumption in TLB CAMs implemented in a multi-threaded configuration.

<CIT>) relates to an address translation apparatus and method.

The present invention provides a multi-thread content-addressable memory (CAM) device in accordance with claim <NUM> and a method in accordance with claim <NUM>.

<FIG> is a block diagram of an example device <NUM> in which one or more disclosed embodiments can be implemented. The device <NUM> can include, 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> can include 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 processor <NUM> can implement a multithreaded process using a translation lookaside buffer (TLB) content-addressable memory (CAM) in which the processor <NUM> switches execution resources between threads, resulting in concurrent execution. In the same multithreaded process in a shared-memory multiprocessor environment, each thread in the process can run on a separate processor at the same time, resulting in parallel execution.

The memory <NUM> can include a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The storage <NUM> can include 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> can include 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> can include 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.

It will be understood that the terms "virtual address", "input address", "search address", "input search data" and "tag" are used interchangeably, unless specifically noted otherwise, and that one term can replace or be combined with another term in one or more aspects. As used herein, these terms refer to any binary lookup word being searched by the CAM, and can include a page size, a thread ID (if applicable) and a valid yes/no bit.

A system memory, as described herein, is managed by an operating system, and is allocated to different software applications as needed. The different software applications can run in one or more partitions, and the one or more partitions can run different operating systems (OSs). As noted above, virtual memory techniques can be used in such a computer system to share the physical memory of the computing system among many processes and applications. The software applications therefore deal with effective addresses in a virtual memory space, which allow the applications carry out one or more processes (e.g., to read, write, and/or execute) when required, without being concerned with the actual physical memory locations where the operations are taking place. The applications rely on the operating system that underlies each application to perform the mapping from the effective address used by the application to a physical address in the computer memory. Address translation is the mechanism by which effective addresses that reference virtual memory are translated into real memory addresses. Address translation is a complex procedure that, if not implemented well, can end up on the critical path that determines the clock cycle of the processor.

With a multi-threaded processor, multiple threads of execution exist within the context of each process. The threads of a particular process are executed in a manner in which the processor quickly switches between different threads such that it appears that threads are being simultaneously executed. A simple type of multi-threading is where one thread runs until an event, such as a cache-miss that has to access off-chip memory, which might create a long latency. Rather than waiting, the processor switches to another thread that is ready to run. When the data for the previous thread arrives, the previous thread is placed back on the list of ready-to-run threads. In another type of multi-threading, the processor switches threads every CPU cycle.

Each process is allocated resources, such as a processor, registers, and the like, by the operating system, and such resources are allocated to the process' threads such that each thread "owns" its own resources, which are used when a thread is employed to execute an instruction. When a process is created, it is stored in main memory. Once the kernel assigns the process to a processor, the process is loaded into the processor and the processor executes the thread's instructions using its resources.

A thread arbiter and/or thread priority determines which thread of execution to use to execute an instruction, and a thread identifier (ID) is associated with and follows the instruction through its various states of execution. The instruction is executed using the resources, such as the registers, of the thread that corresponds to the thread ID. When processing multiple threads, the thread arbiter or thread priority determines the next thread to employ, and a thread ID of the next thread is associated with and follows the next instruction through its various states of execution. Likewise, the instruction is executed using the resources of the thread that corresponds to the thread ID of the next thread.

A TLB is a cache that memory management hardware uses to improve virtual address translation speed. A TLB has a fixed number of slots that contain address translation data (entries), which map virtual memory addresses to physical memory addresses. TLBs are content-addressable memory, in which the search key is the virtual memory address and the search result is a physical memory address. The TLBs are a single memory cache, or the TLBs are alternatively organized in a hierarchy as is known in the art. Regardless of how the TLBs are realized, if the requested virtual address is present in the TLB (i.e., "a TLB hit"), the lookup is considered successful and the search yields a match quickly and the physical memory address is returned for accessing memory. If the requested address is not in the TLB (i.e., "a TLB miss"), the translation proceeds by looking through the page table in a process commonly referred to as a "page walk" or "page table walk". After the physical memory address is determined, the virtual memory address to physical memory address mapping is loaded in the respective TLB (that is, depending upon which processor type (CPU or accelerator) requested the address mapping) to map the faulting virtual address to the correct physical address, and the program is resumed.

As with caches, separate TLBs for the instruction and data streams have been provided on many modern processors. An Instruction Translation Lookaside Buffer (ITLB) only handles instructions addresses. TLBs can have multiple levels (e.g., L1, L2, etc.). For example, a small "L1" TLB (fully-associative) that is extremely fast, and a larger "L2" TLB (set-associative) that is somewhat slower. When ITLBs and data TLBs (DTLBs) are used, a CPU can have three or four TLBs (e.g., ITLB1, DTLB1, TLB2). Since the L1TLB is usually a small and fully-associative cache, storage accesses such as loads, stores, and instruction fetches can access the L1TLB at all page sizes in the same clock cycle. However, an L2TLB, because of its relatively large size, may not be a fully-associative structure. As a result, an L2LTB may not be accessed (e.g., searched) across all entries in a single clock cycle due to, for example, the need to access RAM arrays.

Each cache of an L1TLB comprises at least one fully-associative <NUM>n byte segment that supports single-cycle reads, and either one or two-cycle writes depending on the sequentiality of the access. Each cache segment consists of, for example, <NUM> CAM rows that each select one of <NUM> RAM lines. During an L1TLB access, an input address is compared with the <NUM> tags in the CAM. If a match occurs (a "hit"), a matched line of the CAM is enabled and the data can be accessed. If none of the tags match (a "miss"), then a higher-level TLB or external memory is accessed. If a storage access from a cacheable memory region misses, new data is loaded into one of the <NUM> row lines of the <NUM>n byte segment. It will be appreciated that the number of <NUM> CAM rows and RAM lines is for illustration only and the number is not meant to be limiting.

As noted above, a TLB includes a CAM to compare input search data against a table of stored data and return the address of the matching data. A CAM is a special type of computer memory used in certain very-high-speed searching applications. It compares input search data (i.e., a tag) against a table of stored data, and returns the address of the matching data (or in the case of associative memory, the matching data). Thus, CAMs are hardware search engines that are much faster than algorithmic approaches for search-intensive applications. CAMs are composed of conventional semiconductor memory (e.g., static RAM (SRAM)) with added comparison circuitry that enable a search operation to complete in a single clock cycle.

A binary CAM is the simplest type of CAM which uses data search words consisting entirely of <NUM> and <NUM>. A ternary CAM (TCAM) allows a third matching state of "X" or "don't care" for one or more bits in the stored dataword, thus adding flexibility to the search. For example, a ternary CAM might have a stored word of "10XX0" which will match any of the four search words "<NUM>", "<NUM>", "<NUM>", or "<NUM>". The added search flexibility comes at an additional cost over the binary CAM as the internal memory cell must now encode three possible states instead of the two of the binary CAM. This additional state is typically implemented by adding a mask bit ("care" or "don't care" bit) to every memory cell.

One of more of the aspects described above are implemented in the additional examples described below.

According to an example, a multi-thread CAM device is provided. The CAM device includes a first input configured to receive a first virtual address corresponding to a first thread, a second input configured to receive a second virtual address corresponding to a second thread, a register bank including a plurality of registers each configured to store a binary word mapped to one of a plurality of physical addresses, a first comparator bank including a first plurality of comparators each coupled to one of the plurality of registers in a fully-associative configuration, and a second comparator bank including a second plurality of comparators each coupled to one of the plurality of registers in the fully-associative configuration.

In particular, each of the first plurality of comparators is configured to compare the first virtual address to a binary word stored in a register associated therewith for determining whether a first match is present, and the first comparator bank is configured to output first comparison results of the first plurality of comparators. Similarly, each of the second plurality of comparators is configured to compare the second virtual address to the binary word stored in a register associated therewith for determining whether a second match is present, and the second comparator bank is configured to output second comparison results of the second plurality of comparators.

In addition, each of the first plurality of comparators maintain a first input state corresponding to a previous first virtual address input to the first comparator bank on a condition that the first thread is inactive or invalid, and each of the second plurality of comparators maintain a second input state corresponding to a previous second virtual address input to the second comparator bank on a condition that the second thread is inactive or invalid.

According to another example, a multi-thread CAM method is provided. The method includes receiving, by a first comparator bank, a first virtual address corresponding to a first thread, and receiving, by a second comparator bank, a second virtual address corresponding to a second thread. The first comparator bank includes a first plurality of comparators each coupled to one of a plurality of registers of a register bank in a fully-associative configuration, and the second comparator bank includes a second plurality of comparators each coupled to one of the plurality of registers of the register bank in the fully-associative configuration.

The method further includes comparing, by each of the first plurality of comparators, the first virtual address to a binary word stored in a register associated therewith for determining whether a first match is present, maintaining, by each of the first plurality of comparators, a first input state corresponding to a previous first virtual address input to the first comparator bank on a condition that the first thread is inactive or invalid, and outputting, by the first comparator bank, first comparison results from the first plurality of comparators.

The method further includes comparing, by each of the second plurality of comparators, the second virtual address to the binary word stored in a register associated therewith for determining whether a second match is present, maintaining, by each of the second plurality of comparators, a second input state corresponding to a previous second virtual address input to the second comparator bank on a condition that the second thread is inactive or invalid, and outputting, by the second comparator bank, second comparison results from the second plurality of comparators.

<FIG> shows a schematic diagram of a multi-bit logic comparator <NUM> implemented in a CAM according to one or more embodiments. The comparator <NUM> compares two binary words and indicates if they are equal. In this example, the comparator <NUM> is a <NUM>-bit equality comparator that includes four parallel XOR gates 302a, 302b, 302c and 302d and an OR gate <NUM>. The comparator <NUM> receives a <NUM>-bit binary word ADDR (e.g., an input address or tag) provided by an address register <NUM> to be compared with a binary word stored in a TLB register <NUM> corresponding to a TLB entry.

The address register <NUM> is a storage unit (e.g., a search data register or load store unit) corresponding to one of the threads (e.g., thread <NUM> or thread <NUM>) in a multi-thread implementation. Accordingly, multiple address registers <NUM> are present for a multi-thread implementation.

Each XOR gate 302a, 302b, 302c and 302d compares a single corresponding bit of the two words (ADDR and TLB entry) and outputs a <NUM> if the bits match. The outputs of the XOR gates 302a, 302b, 302c and 302d are then combined in the OR gate <NUM>, the output <NUM> of which will be <NUM> (a "hit"), only when all the XOR gates 302a, 302b, 302c and 302d indicate matched inputs. Accordingly, output <NUM>, which is inverted to be a <NUM> (based on implementation design), is one matchline of the CAM that indicates whether there is a hit or not for that comparator.

It will be appreciated that other types of logic components can be used to implement a multi-bit logic comparator. For example, a multi-bit logic comparator alternatively includes parallel XNOR gates that receive the binary words and an AND gate that outputs a <NUM> (a "hit") if all bits match.

Each time an input state to one of the components (e.g., XOR gate or OR gate) changes (e.g., <NUM> to <NUM> or <NUM> to <NUM>), power is consumed by the component and, ultimately, by the comparator <NUM>. The power consumption can be costly when a larger number of comparators, or components thereof, change states. This can occur when a large number of bits of an input address or tag from one thread are different from bits of an input address or tag from a second thread, which can change cycle to cycle. Therefore, the power consumption should be minimized for each thread.

<FIG> is a block diagram of a TLB CAM structure <NUM> having redundant (e.g., identical) sets of comparators for each thread of a multi-thread processor. The TLB CAM structure <NUM> is implemented by a processor (e.g., processor <NUM>) in a multi-threaded environment. The processor uses one or more of the threads of execution when executing an instruction and the TLB CAM structure is implemented as an L1ITLB. For instance, the processor can be run in single thread mode in which only one of the N threads is active. In another instance, the processor can be run in multi-thread mode in which two to N threads are active. Active threads use their respective resources as well as the resources of inactive threads when executing an instruction.

The TLB CAM structure <NUM> includes a set of registers <NUM> and a set of comparators <NUM>, <NUM> for each thread coupled to the set of registers <NUM>. As used herein, a set of registers is referred to as a "bank of registers" or "register bank", and a set of comparators is referred to as a "bank of comparators" or "comparator bank".

A register bank <NUM> is a RAM or other memory logic that is a TLB linear virtual address storage unit. The register bank <NUM> includes, for example, <NUM> registers or storage units, which can also be referred to as slots or CAM rows. Each register contains address translation data (i.e., a TLB entry) that maps to a physical memory address.

The TLB CAM structure <NUM> further includes two comparator banks <NUM> and <NUM> that share, and are fully-associative with, the register bank <NUM>. That is, each register in the register bank <NUM> corresponds, on a one-to-one basis, to a comparator of comparator bank <NUM> and corresponds, on a one-to-one basis, to a comparator of comparator bank <NUM>. Each comparator bank <NUM> and <NUM> includes an input (e.g., thread <NUM> input <NUM> and thread <NUM> input <NUM>) for receiving a virtual address from an address register of a thread.

Each comparator bank <NUM> and <NUM> includes, for example, <NUM> comparators (e.g., comparators <NUM>). Each TLB entry stored in register bank <NUM> is compared by an associated comparator in comparator bank <NUM> or <NUM> (depending on which thread is active) with a virtual address input by thread <NUM> or thread <NUM> (depending on which thread is active). Matchlines <NUM> and <NUM> indicate whether or not a match is present in one of the corresponding comparator numbers, and the matchlines <NUM> and <NUM> are respectively coupled to a logic unit <NUM> and <NUM> (e.g., an OR or a NOR gate depending on implementation). Logic units <NUM> and <NUM> output a summary hit indication <NUM> and <NUM>, respectively, that indicates whether or not one of its inputs from the matchlines <NUM> and <NUM> indicates a match or a hit.

<FIG> is a block diagram of a multi-thread processor <NUM> that implements the TLB CAM structure <NUM> of <FIG>. While two threads are shown, it will be understood that the multi-thread processor <NUM> can implement more than two threads so long as there is a redundant comparator bank for each thread and the comparator banks share a single register bank, as described herein. Furthermore, the CAM implementations shown in <FIG> are merely examples and a CAM can feature a wide variety of different configurations and variations. For example, the number of CAM entries can be varied by altering the number of CAM rows. Additionally, length of the binary words may be varied (e.g., the tag length can be varied by using a different number of RAM blocks, using RAM blocks with a different address space and/or using multi-bit comparators with a different number of parallel gates).

Many other variations are possible, including the type of logic components used for performing a binary word comparison, outputting a match hit, outputting a summary hit indication and outputting a final output result, which will be readily apparent in view of the figures. Furthermore, other variations are possible with respect to memory structures, address load and capture circuity and logic, and input selection circuitry and logic, etc., that are described herein, which will also be readily apparent in view of the figures.

According to <FIG>, thread <NUM> and thread <NUM> in the TLB CAM (e.g., L1ITLB CAM) each contain their own comparator banks. By doing so, this reduces thrashing of comparator states during simultaneous multithread (SMT) operation when an input address has large number of bits changing from cycle to cycle due to the threads being completely independent. Thus, instead of each thread <NUM> and <NUM> sharing a comparator bank, there is a dedicated comparator bank per-thread and the input address to each comparator bank retains its previous value (e.g., via a capture register for each thread) for when a thread is not selected. In this manner, the comparator bank for each thread only needs to change state when a thread moves from one page in memory to another, consuming less power. Thus, dynamic power consumption is reduced.

Thread <NUM> includes an address register <NUM>, an address capture circuit <NUM> (e.g., address capture flip-flop), a multiplexer <NUM> connected to an input <NUM> of comparator bank <NUM>, and an AND gate <NUM> connected to the summary hit indication <NUM>. Thread <NUM> includes an address register <NUM>, an address capture circuit <NUM> (e.g., address capture flip-flop), a multiplexer <NUM> connected to an input <NUM> of comparator bank <NUM>, and an AND gate <NUM> connected to the summary hit indication <NUM>. The outputs of the AND gates <NUM> and <NUM> are provided to the inputs of OR gate <NUM>, and the OR gate <NUM> outputs the final output <NUM>, which indicates a "hit" or "miss. " As described above in <FIG>, comparator banks <NUM> and <NUM> are coupled to register bank <NUM> in a fully associative manner.

Virtual addresses are loaded into and output from the address registers <NUM> and <NUM> simultaneously or at different times. The virtual addresses are output from the address registers <NUM> and <NUM> and are captured by the address capture circuits <NUM> and <NUM> such that the input to the respective comparator bank <NUM> and <NUM> is maintained at its previous value when a thread (i.e., thread <NUM> or <NUM>) is not selected. Thus, the input state for the respective comparator bank <NUM> and <NUM> is maintained at its previous value when a thread is not active and/or valid, as indicated by a corresponding active and valid input (e.g., a T0 active and valid input or a T1 active and valid input).

The corresponding active and valid input, as described below, is a single bit, but is not limited thereto. Alternatively, a corresponding active and valid input is represented by two individual bits, one bit representing an active status of a thread and the other bit representing the validity status of the thread, that are provided as two separate inputs.

Accordingly, when the T0 active and valid input is <NUM>, thread <NUM> is inactive and the virtual address stored in the address capture circuit <NUM> is selected by the multiplexer <NUM> and input to the comparator bank <NUM>. On the other hand, when the T0 active and valid input is <NUM>, the virtual address stored in the address register <NUM> is selected by the multiplexer <NUM> and input to the comparator bank <NUM>. The comparator bank <NUM> then performs a comparison for each TLB entry provided by the register bank <NUM> based on the virtual address input by the multiplexer <NUM>. Finally, a summary hit indication <NUM> is output and fed into the AND gate <NUM>. The AND gate <NUM> ensures that thread <NUM> is active and valid, via the T0 active and valid input, before outputting any hit result. Thus, even if there is a hit indicated by the summary hit indication <NUM>, the output of the AND gate <NUM> will be <NUM> (i.e., miss) if thread <NUM> is not active/valid. Only when there is a hit indicated by the summary hit indication <NUM> and thread <NUM> is active/valid (as indicated by the T0 active and valid input) will the AND gate <NUM> output a hit indication.

Similarly, when the T1 active and valid input is <NUM>, thread <NUM> is inactive and the virtual address stored in the address capture circuit <NUM> is selected by the multiplexer <NUM> and input to the comparator bank <NUM>. On the other hand, when the T1 active and valid input is <NUM>, the virtual address stored in the address register <NUM> is selected by the multiplexer <NUM> and input to the comparator bank <NUM>. The comparator bank <NUM> then performs a comparison for each TLB entry provided by the register bank <NUM> based on the virtual address input by the multiplexer <NUM>. Finally, a summary hit indication <NUM> is output and fed into the AND gate <NUM>. The AND gate <NUM> ensures that thread <NUM> is active and valid, via the T1 active and valid input, before outputting any hit result. Thus, even if there is a hit indicated by the summary hit indication <NUM>, the output of the AND gate <NUM> will be <NUM> (i.e., miss) if thread <NUM> is not active/valid. Only when there is a hit indicated by the summary hit indication <NUM> and thread <NUM> is active/valid (as indicated by the T1 active and valid input) will the AND gate <NUM> output a hit indication.

The AND gates <NUM> and <NUM> each output their result to the OR gate <NUM>, and the OR gate <NUM> outputs the final output <NUM> (i.e., hit or miss) based on whether there is an active/valid hit indicated by either AND gate <NUM> or AND gate <NUM>. It will be further appreciated that the AND gates <NUM> and <NUM> and the OR gate <NUM> can be incorporated into the TLB CAM structure <NUM> or external thereto.

<FIG> is a flow diagram of a multithread CAM method <NUM> according to one or more embodiments. While the flow diagram depicts a series of sequential operations, unless explicitly stated, no inference should be drawn from that sequence regarding specific order of performance, performance of operations or portions thereof serially rather than concurrently or in an overlapping manner, or performance of the operations depicted exclusively without the occurrence of intervening or intermediate operations. The process depicted in the example is implemented by, for example, memory management hardware described above.

The multithread CAM method <NUM> includes storing TLB entries in a single register bank (operation <NUM>) and selectively activating/deactivating a first thread and a second thread such that one is active and the other is inactive (operation <NUM>). The method <NUM> further includes determining whether the first thread is active (operation <NUM>) and determining whether the second thread is active (operation <NUM>). It will be appreciated that a timing of performing operations <NUM> and <NUM>, and the respective operations that follow, includes performing the operations simultaneously, overlapping to at least some degree, non-overlapping, or ahead of or behind the other. If the first thread is inactive, a first register bank compares the TLB entries with a previous first virtual address (VA) (operation <NUM>), and, if the first thread is active, the first register bank compares the TLB entries with an active first VA (operation <NUM>). Similarly, if the second thread is inactive, a second register bank compares the TLB entries with a previous second virtual address (VA) (operation <NUM>), and, if the second thread is active, the second register bank compares the TLB entries with an active second VA (operation <NUM>). The first and the second comparator banks are independent from each other and are both fully-associative with the single register bank. Thus, there are redundant comparator banks dedicated to each thread for comparing a virtual address provided on the corresponding thread to a single set of TLB entries. Furthermore, the input virtual address to each comparator bank retains its previous value via address capture when its thread is inactive.

The method <NUM> further includes generating a first summary hit indication based on the comparison results of the first comparator bank (operation <NUM>) and generating a second summary hit indication based on the comparison results of the second comparator bank (operation <NUM>). A final output (e.g., a "hit" or "miss") is generated based on the first and the second summary hit indication (operation <NUM>). In particular, the final output is generated for a thread that is active and valid based on the first or second summary hit indication that corresponds to the active and valid thread. The comparison results (and hit summary indication) of the inactive or invalid thread are disregarded.

A multi-thread CAM device is disclosed herein. The multi-thread CAM device includes a first input configured to receive a first virtual address corresponding to a first thread, a second input configured to receive a second virtual address corresponding to a second thread, a register bank including a plurality of registers each configured to store a binary word mapped to one of a plurality of physical addresses, a first comparator bank, and a second comparator bank. The first comparator bank includes a first plurality of comparators each coupled to one of the plurality of registers in a fully-associative configuration such that each of the first plurality of comparators is configured to receive the first virtual address while the first thread is active and valid, and receive a previous first virtual address while the first thread is inactive or invalid. The second comparator bank includes a second plurality of comparators each coupled to one of the plurality of registers in the fully-associative configuration such that each of the second plurality of comparators is configured to receive the second virtual address while the second thread is active and valid, and receive a previous second virtual address while the second thread is inactive or invalid. The previous first virtual address is the first virtual address received by the first input a last time the first thread was active and valid, and the previous second virtual address is the second virtual address received by the second input a last time the second thread was active and valid.

In some examples, the first comparator bank is separated from the second comparator bank and is identical to the second comparator bank.

In some examples each of the first plurality of comparators is configured to maintain a first input state corresponding to the previous first virtual address input to the first comparator bank while the first thread is inactive or invalid, and each of the second plurality of comparators is configured to maintain a second input state corresponding to the previous second virtual address input to the second comparator bank while the second thread is inactive or invalid.

In some examples, each of the first plurality of comparators is configured to compare one of the first virtual address and the previous first virtual address, based on an active state of the first thread, to a binary word stored in a register associated therewith for determining whether a first match is present, and the first comparator bank is configured to output first comparison results of the first plurality of comparators, and each of the second plurality of comparators is configured to compare one of the second virtual address and the previous second virtual address, based on an active state of the second thread, to the binary word stored in the register associated therewith for determining whether a second match is present, and the second comparator bank is configured to output second comparison results of the second plurality of comparators.

In some examples, the multi-thread CAM device includes a first logic component coupled to a first plurality of matchlines of the first comparator bank, and a second logic component coupled to a second plurality of matchlines of the second comparator bank. The first logic component is configured to output a first summary hit indication based on the first comparison results received on the first plurality of matchlines, and the second logic component is configured to output a second summary hit indication based on the second comparison results received on the second plurality of matchlines.

In some examples, the first summary hit indication indicates the first match is present on a condition that at least one of the first plurality of comparators matches the first virtual address to the binary word stored in the register associated therewith, and the second summary hit indication indicates the second match is present on a condition that at least one of the second plurality of comparators matches the second virtual address to the binary word stored in the register associated therewith.

In some examples, the multi-thread CAM device includes a logic circuit configured to receive the first summary hit indication and the second summary hit indication, and output a final result. Accordingly, one of the first thread and the second thread is active at a time, and the final result is the first summary hit indication on a condition that the first thread is active and the final result is the second summary hit indication on a condition that the second thread is active.

In some examples, the first comparator bank is configured to output the first comparison results based on the first plurality of comparators determining whether at least one first match is present, and the second comparator bank is configured to output the second comparison results based on the second plurality of comparators determining whether at least one second match is present.

In some examples, the multi-thread CAM includes a logic circuit configured to receive a first summary hit indication based on the first comparison results of the first plurality of comparators, receive a second summary hit indication based on the second comparison results of the second plurality of comparators, and output a final result. Accordingly, one of the first thread and the second thread is active at a time, and the final result is the first summary hit indication on a condition that the first thread is active and the final result is the second summary hit indication on a condition that the second thread is active.

In some examples, the previous first virtual address is the first virtual address provided by a first address register the last time the first thread was active and valid, and the previous second virtual address is the second virtual address provided by a second address register the last time the second thread was active and valid.

In some examples, each of the first plurality of comparators receive the first virtual address from a first address register on a condition that the first thread is active and valid, and each of the second plurality of comparators receive the second virtual address from a second address register on a condition that the second thread is active and valid.

In some examples, the multi-thread CAM device includes a first address register configured to send the first virtual address to the first comparator bank on a condition that the first thread is active and valid, and a second address register configured to send the second virtual address to the second comparator bank on a condition that the second thread is active and valid.

In some examples, the multi-thread CAM device includes a first address register and a second address register. The first address register is configured to store the first virtual address, and the first comparator bank is configured to receive the first virtual address from the first address register on a condition that the first thread is active and valid. The second address register configured to store the second virtual address, and the second comparator bank is configured to receive the second virtual address from the second address register on a condition that the second thread is active and valid.

In some examples, the multi-thread CAM device includes a first address capture circuit and a second address capture circuit. The first address capture circuit is configured to store the first virtual address as the previous first virtual address, and the first comparator bank is configured to receive the previous first virtual address from the first address capture circuit on a condition that the first thread is inactive or invalid. The second address capture circuit is configured to store the second virtual address as the previous first virtual address, and the second comparator bank is configured to receive the previous second virtual address from the second address capture circuit on a condition that the second thread is inactive or invalid.

In some examples, the previous first virtual address is the first virtual address provided by a first address register to the first address capture circuit the last time the first thread was active and valid, and the previous second virtual address is the second virtual address provided by a second address register to the second address capture circuit the last time the second thread was active and valid.

In some examples, the multi-thread CAM device is an instruction translation lookaside buffer CAM.

A multi-thread CAM method is provided. A first virtual address corresponding to a first thread is received by a first comparator bank. The first comparator bank includes a first plurality of comparators each coupled to one of a plurality of registers of a register bank in a fully-associative configuration, and the first virtual address is received while the first thread is active and valid. A second virtual address corresponding to a second thread is received by a second comparator bank. The second comparator bank includes a second plurality of comparators each coupled to one of the plurality of registers of the register bank in the fully-associative configuration, and the second virtual address is received while the second thread is active and valid. A previous first virtual address corresponding to the first thread is received by the first comparator bank while the first thread is inactive or invalid. A previous second virtual address corresponding to the second thread is received by the second comparator bank while the second thread is inactive or invalid. The previous first virtual address is the first virtual address received a last time the first thread was active and valid, and the previous second virtual address is the second virtual address received a last time the second thread was active and valid.

In some examples, a first input state corresponding to the previous first virtual address input to the first comparator bank is maintained by each of the first plurality of comparators on a condition that the first thread is inactive or invalid. In addition, A second input state corresponding to the previous second virtual address input to the second comparator bank is maintained by each of the second plurality of comparators on a condition that the second thread is inactive or invalid.

In some examples, one of the first virtual address and the previous first virtual address, based on an active state of the first thread, is compared by each of the first plurality of comparators to a binary word stored in a register associated therewith for determining whether a first match is present. First comparison results from the first plurality of comparators are output by the first comparator bank. One of the second virtual address and the previous second virtual address, based on an active state of the second thread, is compared by each of the second plurality of comparators to the binary word stored in the register associated therewith for determining whether a second match is present. Second comparison results from the second plurality of comparators are output by the second comparator bank.

In some examples, a first summary hit indication is generated by a first logic component based on the first comparison results. The first summary hit indication indicates the first match is present on a condition that at least one of the first plurality of comparators matches the first virtual address to the binary word stored in the register associated therewith. A second summary hit indication is generated by a second logic component based on the second comparison results. The second summary hit indication indicates the second match is present on a condition that at least one of the second plurality of comparators matches the second virtual address to the binary word stored in the register associated therewith.

In some examples, the first summary hit indication and the second summary hit indication are received by a logic circuit, and a final result is generated by the logic circuit based on the first summary hit indication and the second summary hit indication such that one of the first thread and the second thread is active at a time, and the final result is the first summary hit indication on a condition that the first thread is active and the final result is the second summary hit indication on a condition that the second thread is active.

In some examples, the first virtual address is received by the first comparator bank from a first address register on a condition that the first thread is active and valid. The second virtual address is received by the second comparator bank from a second address register on a condition that the second thread is active and valid.

In some examples, a first one of the first thread and the second thread is selectively activated by a processor, and a second one of the first thread and the second thread is selectively deactivated by the processor. The previous first virtual address is received by the first comparator bank from a first address capture circuit on a condition that the first thread is inactive or invalid such that the previous first virtual address is the first virtual address received the last time the first thread was active and valid. The previous first virtual address is received by the second comparator bank from a second address capture circuit on a condition that the second thread is inactive or invalid such that the previous second virtual address is the second virtual address received the last time the second thread was active and valid.

In some examples, the first virtual address is received by the first comparator bank from a first address register on a condition that the first thread is active and valid, and the second virtual address is received by the second comparator bank from a second address register on a condition that the second thread is active and valid.

Some or all of the method steps can be executed by (or using) a hardware apparatus, like for example, a microprocessor, a programmable computer or an electronic circuit. In some embodiments, some one or more of the method steps can be executed by such an apparatus.

With regard to the various functions performed by the components or structures described above (assemblies, devices, circuits, systems, etc.), the terms (including a reference to a "means") used to describe such components are intended to correspond, unless otherwise indicated, to any component or structure that performs the specified function of the described component (i.e., that is functionally equivalent), even if not structurally equivalent to the disclosed structure that performs the function in the exemplary implementations of the invention illustrated herein.

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 embodiments.

Claim 1:
A multi-thread content-addressable memory, CAM, device comprising:
a first input configured to receive a first virtual address corresponding to a first thread;
a second input configured to receive a second virtual address corresponding to a second thread;
a register bank (<NUM>) configured to store translation lookaside buffer, TLB, linear virtual address information including a plurality of registers, wherein each register is configured to store a binary word corresponding to a TLB entry mapped to one of a plurality of physical addresses;
a first comparator bank (<NUM>) including a first plurality of comparators each coupled to one of the plurality of registers in a fully-associative configuration configured to output a first comparison result of the first plurality of comparators, wherein each of the first plurality of comparators is configured to compare one of the first virtual address and a previous first virtual address, based on an active state of the first thread, to a binary word corresponding to a TLB entry stored in a register of the plurality of registers associated therewith for determining whether a first match is present, wherein the first virtual address is received while the first thread is active and valid, and the previous first virtual address is received while the first thread is inactive or invalid, wherein the previous first virtual address is a first virtual address received by the first input a last time the first thread was active and valid; and
a second comparator bank (<NUM>) including a second plurality of comparators each coupled to one of the plurality of registers in a fully-associative configuration configured to output a second comparison result of the second plurality of comparators, wherein each of the second plurality of comparators is configured to compare one of the second virtual address and a previous second virtual address, based on an active state of the second thread, to a binary word corresponding to a TLB entry stored in a register of the plurality of registers associated therewith for determining whether a second match is present, wherein the second virtual address is received while the second thread is active and valid, and the previous second virtual address is received while the second thread is inactive or invalid, wherein the previous second virtual address is a second virtual address received by the second input a last time the second thread was active and valid.