Method and apparatus for accelerating exchange or swap instructions using a register alias table (RAT) and content addressable memory (CAM) with logical register numbers as input addresses

[0002] 1. Field of the Invention

[0003] The invention relates to handling of exchange (XCHG) instructions, and more particularly to accelerating XCHG instructions in a processor by a content addressable memory implementation.

[0004] 2. Background Information

[0005] Many instruction set architectures (ISAs) contain an XCHG instruction. An XCHG instruction exchanges data contents between two registers, i.e. a source register and a destination register. In architectures that use a stack-based register file, such as the IA-32 (Intel® Architecture) floating point instruction set, the XCHG instruction is used frequently. In this case, compilers use the XCHG instruction to move data from a given register to the top-of-stack (TOS) position. Once moved, the data is used in a subsequent operation. This is done because many of the instructions implicitly reference the TOS register. Therefore, it is necessary for the data to be re-located to the TOS register before the operation on that data can proceed.

[0006] The basic method of executing the XCHG instruction is to read both registers from the register file (RF), and then write back each data contained in the original registers to the alternate register from where it was read. For example, if register 0 (r0) contained data value A, and register 3 (r3) contained data value B, then the instruction XCHG r0,r3 would place data value B in r0 and data value A in r3. Any subsequent instructions that were necessary to access either r0 or r3 would need to stall at dispatch until the XCHG instruction had completed execution.

[0007] An improvement in the performance of most type of instructions including XCHG instructions was realized through the concept of register renaming. Register renaming maps the logical registers of each instruction onto a larger set of physical registers. The unit that performs the logical to physical mapping is commonly referred to as the register alias table (RAT). The destinations of the XCHG instruction can be mapped to different physical registers (an example of nomenclature would be physical register #78 or p78) other than the sources. Therefore, the need for dispatching stalls is eliminated. FIG. 1 illustrates an example of a RAT and an RF structure before and after a XCHG r0,r3 instruction.

[0008] Other optimizations include attempts to re-map the renamed registers without physically moving the data. One example requires one or more additional pipeline stages to accomplish re-mapping. This mitigates performance gain achieved by eliminating a data transfer. Another example is to swap the contents of the RAT entries corresponding to the logical registers of the XCHG instruction. This example can be very expensive in terms of implementation. This is due to the RAT entry, not only containing the physical register number, but often containing several status fields related to the logical register and sometimes even embedded logic, such as tag comparators.

[0009] The embodiments are illustrated by way of example and not by way of limitation in the figures of the accompanying drawings in which like references indicate similar elements. It should be noted that references in the specification to “an embodiment,” “one embodiment,” “some embodiments,” or “other embodiments” means that a particular feature, structure, or characteristic described in connection with the embodiments is included in at least some embodiments, but not necessarily all embodiments, of the invention. The various appearances “an embodiment,” “one embodiment,” or “some embodiments,” are not necessarily all referring to the same embodiments. If the specification states a component, feature, structure, or characteristic “may”, “might”, or “could” be included, that particular component, feature, structure, or characteristic is not required to be included. If the specification or claim refers to “a” or “an” element, that does not mean there is only one of the element. If the specification or claims refer to “an additional” element, that does not preclude there being more than one of the additional element.

[0010] FIG. 1 illustrates a register alias table (RAT) and register file (RF) before and after execution of a basic XCHG instruction.

[0011] FIG. 2 illustrates an apparatus in accordance with an embodiment of the invention including an entry swapping content addressable memory (CAM) array with 1 read, 1 write and an 8-entry RAT .

[0012] FIG. 3 is a sample timing diagram for the execution of an entry swap in accordance with an embodiment of the invention.

[0013] FIG. 4 illustrates states of a RAT after ADD, XCHG, and SUB instructions using a CAM mechanism in accordance with an embodiment of the invention.

[0014] FIG. 5 illustrates a CAM embedded in a microprocessor in accordance with an embodiment of the invention.

[0015] FIG. 6 illustrates a microprocessor used in a system having an entry-swapping CAM in accordance with an embodiment of the invention.

[0016] The invention generally relates to a method and apparatus for accelerating an exchange (XCHG) instruction by using a content addressable memory (CAM) to handle renaming. In several embodiments, an entry-swapping CAM mechanism is used to accelerate XCHG instructions. Referring to the figures, exemplary embodiments of the invention will now be described. The exemplary embodiments are provided to illustrate the invention and should not be construed as limiting the scope of the invention.

[0017] FIG. 2 illustrates an embodiment of the invention comprising device 200 that includes entry-swapping CAM 210. Device 200 further includes register alias table (RAT) 220. A CAM, such as CAM 210, is a storage array used to find the location of a particular stored value. The CAM, by comparing the input against the data memory, determines if an input value matches one or more values stored in the array. Typically, a match, when it exists, is found within one clock cycle. Unlike random access memory (RAM), a CAM does not have a limitation of fixed data size. In a RAM, the number of address lines limits the data size. A CAM does not use an address bus to read a location. To find a match of an 8-bit value in 1024 locations, an 8-bit bus on the input is typically required. Upon finding the data in the CAM, a match signal is activated. The output is the address of the matching data. Since a CAM does not need address lines to find data (read mode), the size of the memory can be increased. The width is determined by the storage and comparator size. The core of a CAM has a storage location and a comparator between the storage location value and the input data.

[0018] Device 200 illustrated in FIG. 2 allows for maximum performance gain being accomplished for an XCHG instruction with minimal hardware cost. Instead of indexing a register alias table (RAT) with logical register numbers, RAT 220 is accessed as a CAM structure. Here, the logical register numbers act as CAM 210 input addresses. This is also applied for both read and write ports of RAT 220. Upon completion of the comparator phase of CAM 210, CAM 210's address entries may then be swapped with one another to accomplish the functionality of a XCHG instruction, where the comparator arrays also determine which entries to swap. This allows XCHG instructions to be executed in minimal time while being dispatched in parallel with other instructions.

[0019] FIG. 2 illustrates an embodiment having 1 read and 1 write for 8-entry RAT 220. Other embodiments can be extended to include multiple read/write/swap ports and any number of RAT entries. An illustrative timing diagram for states of CAM 210 and RAT 220 in accordance with the embodiment illustrated in FIG. 2 is shown in FIG. 3. FIG. 3 demonstrates the comparator functionality of using the entry-swapping CAM mechanism to accomplish a XCHG instruction. It should be noted that other embodiments are not limited to the timing as illustrated in FIG. 3. During phase 1, the comparator arrays are enabled to compare the read, write, and swap addresses for instructions being dispatched during this cycle. During phase 2, the results of the comparators are used to simultaneously read RAT 220's data array (containing the physical register number) and to swap the logical register numbers of the two entries indicated by the swap addresses. Upon completion of the swap, RAT 220 has effectively executed a “zero-cycle” XCHG instruction. The results of the XCHG instruction will affect the instructions that are dispatched during the next clock cycle. The timing of the entry-swapping CAM mechanism allows for a fully-pipelined rename mechanism while still integrating to a data array that is read from, and written to, during different phases of the clock.

[0020] For ease of understanding, FIG. 4 illustrates an example of an embodiment using the entry-swapping CAM mechanism to perform, in order, ADD destination, source (addition), XCHG destination, source, and SUB destination, source (subtraction) instructions. The instructions operate on the specified registers as follows:

[0021] ADD r0, r2

[0022] XCHG r0, r3

[0023] SUB r0, r6

[0024] The ADD r0, r2 instruction performs the addition of the value contents in r2 with that of r0 and replaces the value content of r0 with the result of the addition. The XCHG r0, r3 instruction exchanges the value contents of r0 with that of r3, and vice versa. The SUB r0, r6 instruction performs the subtraction of the value contents of r6 from r0 and replaces the content value in r0 with the result of the subtraction. The state of the RAT after the rename stage for each instruction is shown in FIG. 4 by array 450. Initial state 400 illustrates that the CAM bits 440 are reset to constant values out of reset. ADD instruction 410 first reads r0 and r2, which are associated with p56 and p55, respectively. ADD instruction 410 then writes to r0 which, allocates new physical register p81. XCHG instruction 420 swaps the data values of r0 and r3 which, is accomplished without altering the data array portion of the RAT or any part of the RF. One skilled in the art will recognize that ADD instruction 410 and XCHG instruction 420 can both be renamed simultaneously. The states in FIG. 4 are shown individually for ease of understanding. SUB instruction 430 source r0 is renamed to the correct physical register, p57. Therefore, reflecting the effects of XCHG instruction 420. And, SUB instruction 430 correctly renames r0 to newly allocated physical register p82.

[0025] Since the XCHG instruction is completely handled during the time of renaming, no execution resources are required. Also, no dependencies are introduced into the dataflow. Therefore, performance is maximized. In an ISA having 8 registers, as illustrated in the example above, only 6 bits of information are necessary to be read from, or written to, to accomplish the XCHG instruction. The reduction in necessary bits for read/write operations minimizes hardware requirements and also reduces power consumption.

[0026] Additionally, other embodiments using the entry-swapping CAM mechanism can be integrated easily into superscalar microarchitectures because the XCHG instruction can be renamed in parallel with other instructions without requiring additional pipeline stages. Also, since devices that use the entry-swapping CAM mechanism only swap the address bits of the RAT, extra control data and functionality, such as tag comparators, can be added to each RAT entry without requiring additional logic to handle the acceleration of the XCHG instruction. This advantage is quite significant, if for example the RAT contains an associated Logical Scoreboard that is updated by comparators connected to the physical register numbers stored in each entry of the RAT. Further, for ease of understanding, FIG. 5 illustrates an embedded CAM 510 that is part of microprocessor 500. FIG. 6 illustrates microprocessor 500 as part of a system that includes a bus and main memory 610. In the embodiment illustrated in FIG. 6, microprocessor 500 communicates with main memory 610 via the bus.

[0027] While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications may occur to those of ordinary skill in the art.