Content addressable storage apparatus and register mapper architecture

[0002] The present invention relates generally to information processing systems and more particularly to a methodology and implementation for a high speed content addressable memory and register mapper organization.

[0003] In current computer systems, register mappers are implemented in high-performance “out-of-order” machines to manage a large set of physical registers within an associated register file. New registers are allocated during instruction dispatch for each instruction that writes a new result. The mapper maintains a register map to locate the physical registers that hold the latest or most current results for each logical register. A CAM (content-addressable memory) structure capable of simultaneously performing multi-searches is required to establish such a register map.

[0004] Using a conventional approach, a basic single-compare CAM cell such as the CAM cell illustrated in FIG. 1, can store, read and write a one-bit datum. The single-compare CAM cell can also compare a single incoming bit of data (DATA) against the stored content of the cell (STR) and indicate whether or not there is a match (MATCH). The CAM array consists of a fixed number of word-row's. And each word-row (CAM word) has the same number of CAM bits (one CAM entry). The CAM array is supported by word-row and bit_column logic to update and access the CAM content. The match operation generates a match line (MATCH) if all the bits in the search pattern match all the bits in one CAM entry. The bit-wise compares (“Match” in FIG. 1) in one CAM entry are AND'ed together to produce a match. The output match line is usually used to enable encoding and other readout circuits. Notice that only a single CAM search can be performed at a time with this circuit topology.

[0005] In register mapping applications, the number of word-rows is set equal to the number of physical registers available in the register pool. The CAM bit patterns in a word-row are the binary representation of the logical registers used in the instruction sets. The mapping implemented in the CAM array defines the associations of theological registers with the actual physical registers. This association can also be dynamically updated during instruction dispatch. The output match line is encoded to broadcast the matched physical register. Such circuits are placed outside and nearby the CAM array.

[0006] The CAM cell in FIG. 1 is capable to perform one single search (compare) at a time. For high performance processor, numerous (for example, more than eight) different searches (compares) are required to be made simultaneously against each CAM entry in a single clock cycle. A CAM structure with multi-compare CAM cells is required to accommodate such large number of searches. In this case multi-match lines are needed for each CAM entry. One match line for each search per CAM entry. All these match lines must be driven by the same CAM entry. To obtain this, one must integrate into the CAM cell structure as many bit-wise compare circuits as the CAM searches to be conducted in one clock cycle.

[0007] Theoretically, this can be accomplished by simply integrating the required number of compare circuits (similar to the one in FIG. 1) into the CAM cell topology shown in FIG. 1. Each compare has its own data/data_bar lines, but all compare circuits are connected to the same cell storage nodes (str/str_bar in FIG. 1). However, the overhead of running this many tens of bit-wise compares and match lines across each CAM entry would make the CAM cell and CAM entry area far too large to be used in practical chip design.

[0008] If the bit-wise compare circuits are added to form a vertical stack, this would increase the height of the CAM cell by more than one order of magnitude. It would be impossible to accommodate such CAM size in a chip design. On the other hand, the required compare circuits can be integrated into the CAM cell to form a horizontal stack of bit-wise compare lines. In this case many tens of compare lines must run across the CAM entry to produce the match lines corresponding to the various search vectors presented to the CAM array. The number of horizontal wires across the entry would limit the minimum size of the CAM cell that can be achieved with this approach. The wire loadings on the compare nodes will be excessive and the device sizes should be increased to compensate for that. The CAM cell storage nodes would see increased loads as well due to the increased number of compares. This degrades the speed of cell's search and update. The cross-coupled inverters in FIG. 1 would also have to be made larger.

[0009] The overall size of the CAM entry is determined by the total size of match line generation circuits. For a given search vector, the corresponding bit-wise compare lines are extended across the CAM entry and combined (AND'ed) to obtain the output match lines. The match lines are then driven outside the CAM array to enable encoder and readout circuits. These circuits would present substantial wiring and device loads that require large match line drivers. This would ultimately increase the CAM entry area also.

[0010] All of the above indicate potential integration problems using conventional approaches because exceedingly large number of horizontal wires running across the CAM array would be required and the overall size of the CAM entry would be increased considerably and is clearly a poor utilization of the chip area.

[0011] Thus there is a need for an improved and practical methodology and implementation which provides an optimal approach for CAM and Mapper organization and circuit topologies.

[0012] A non-conventional methodology is provided for designing area efficient CAM (content addressable memory) circuit topology and for organizing a register mapper that uses the CAM array thereby allowing a large number of CAM searches to occur simultaneously. In an exemplary implementation, all compare circuits are placed outside of the CAM in separate match arrays where the actual comparisons occur. The CAM cell contains only latches to hold the CAM stored bit of data and a multi-port MUX to update the CAM content. The bit-wise compare functions of the CAM cells are physically separated from the CAM entry and placed in a “match entry” that is horizontally aligned with the CAM's storage entry. The bits in the CAM storage entry are driven horizontally to all match arrays, and compared simultaneously against all search vectors presented to the various match arrays. The match lines encoder and read-out circuitry are both integrated locally within each match array which minimizes the total load on the match lines and reduces the overall width and area of the match array thereby substantially increasing the speed of the entire match generation and encoding. The structure of the CAM and search engine facilitates the implementation of the register mapper as a group of custom arrays, with each array being dedicated to execute a specific function. All of the arrays are aligned and each row of an array is devoted to one register to keep current state, shadow state and controls for that register. In the exemplary embodiment, eight custom arrays are used to execute various functions of the register mapper. The eight arrays in the example include a CAM storage array, a source match array, a ready bits array, an architected bit array, a destination match array, an allocation array, a free list array and a shadow map array.

[0013] A better understanding of the present invention can be obtained when the following detailed description of a preferred embodiment is considered in conjunction with the following drawings, in which:

[0014] FIG. 1 is an exemplary prior art single-compare CAM cell;

[0015] FIG. 2 is a register mapper organization showing CAM storage array, match arrays and register status arrays for an exemplary embodiment of the present invention; and

[0016] FIG. 3 is an illustration of an entire mapper organization in accordance with the present invention.

[0017] The various methods discussed herein may be implemented within a high performance out-of-order computer system, which may include a workstation or personal computer, and may also be included within a larger system which may further include a plurality of processors in a multi-bus system in a network of similar systems. However, since the workstation or computer system implementing the present invention in an exemplary embodiment, is generally known in the art and composed of electronic components and circuits which are also generally known to those skilled in the art, circuit details beyond those shown are not specified to any greater extent than that considered necessary as illustrated, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

[0018] In FIG. 1, there is illustrated a prior art single-compare CAM storage cell 101. A WL line is connected to corresponding gate terminals of a pair of transistors 103 and 105. Transistor 103 is connected between a DATA terminal 107 and a STR node. Transistor 105 is similarly connected between a DATA_node 109 and a STR_node. The STR node is connected to an output terminal of an inverter 111 and also to an input terminal of an inverter 113. Similarly, the STR_node is connected to the input of inverter 111 and also to the output of inverter 113. The two inverters 111 and 113 are connected in a cross-coupled manner. The STR and STR_nodes are also connected to a second pair of transistors 115 and 117, respectively, which are, in turn, serially connected between node 107 and node 109. A common node between the transistors 115 and 117 is connected to an input terminal of an inverter 121, the output of which is connected to the gate terminal of a MATCH output transistor 123. A PCH signal is applied to a gate terminal of transistor 125, which is connected between a supply potential 127 and the input to inverter 121. The transistor 123 provides a MATCH output signal relative to a reference or ground potential. The MATCH signal is representative of whether there is a match between an input DATA signal and a stored STR signal on a single cell basis as hereinbefore described.

[0019] The present invention discloses a non-conventional approach for designing area efficient CAM circuit topology and for organizing the register mapper that uses the CAM array. This design offers a CAM structure optimal for giga-hertz processor register mapping application. It allows one to execute simultaneously a fairly large number (8 to 12) of CAM searches. During instruction dispatch in out-of-order machines, 8 to 12 logical register binary tags are searched in the same clock cycle against the CAM contents. The matched CAM entries point to the physical registers that are assigned to the logical registers presented to the mapper's CAM map.

[0020] In accordance with the present invention, instead of integrating the bit compare function into the CAM circuit topology, as is the case with the conventional approaches discussed above, the compare is done outside the CAM entry. The CAM content storage/update portion of the CAM cell is separated from the compare component. The CAM cell contains only latches to hold the CAM stored bit of data and a multi-port MUX to update the CAM's content. A CAM's “storage entry” is then a row of these storage cells. The CAM storage array consists of all rows of storage entries. In the exemplary mapper application, the bits of one logical register tag are stored in one storage entry of the CAM array. The bit-wise compare functions of the CAM cells and the match line logic are physically separated from the CAM entry and placed in a “match entry” that is horizontally aligned with the CAM's storage entry. The array of match entries has the same number of rows as the CAM storage array. Each search vector has its own match array. There are as many match arrays as the searches to be made against the CAM stored data. The bits in a CAM storage entry are driven horizontally on long buses to all match arrays. There they are compared simultaneously against all search vectors presented to the various match arrays. Each search vector is transmitted to a separate match array and driven vertically on long buses across the array entries. For a given match array, a match is obtained when all the bits of the transmitted search vector match the corresponding bits of one CAM storage entry which are driven to and available at the entry location of the match array. The match entry contains bit-wise compare circuits (XNOR's) and a gate to AND these compares to generate a CAM match for the presented search vector.

[0021] Each match array in the example also contains an encoder to encode the matched physical register. The encoded physical register tag can then be transmitted to enable different circuits down the pipeline. The array also contains wide MUXs to enable the readout of various register status data. These status data are stored in separate arrays and are driven to the match arrays on long buses similar to driving the CAM storage data. As shown in FIG. 2, the match lines are used local to the match array to drive these encoder and readout circuits. This minimizes the load on the match lines and improves the speed as well as the required area.

[0022] The height of the CAM array is reduced by large amount compared to conventional CAM. The structure of the CAM entry is largely simplified by removing all the compare circuits outside the CAM array. This alone could amount to an order of magnitude reduction in the height of the CAM cell/entry in reference to conventional CAM configurations. The actual comparisons of bit patterns occur outside the CAM array and in the match arrays. The drivers of the CAM bits to the match arrays are sized to optimize the drive delay while keeping the CAM entry dimensions to minimum values. The height of the CAM array sets up the heights of all the remaining arrays included in the mapper and therefore the height of the entire mapper block.

[0023] The match lines for a given search vector (a logical register binary tag in mapper applications) are generated in a separate dedicated array “a match array”. All the match arrays receive the same CAM bit patterns (one pattern per entry) but are presented with different search bit patterns. One search vector runs vertically across the entire match array to generate a match line at each entry. The match lines encoder and the readout circuitry are both integrated locally within each match array and are distributed across the entire depth of the array. This minimizes the total load on the match lines and reduces the sizes of the match line drivers which in turn brings down the bit-wise compare XNOR sizes and the overall width and area of the match array. It also increases the speed of the entire match generation and encoding by a considerable amount. In contrast, the conventional CAM and mapper configuration presents very large loads on the match lines and incurs substantial area and speed penalties. The disclosed configuration provides a compact and area-efficient CAM and mapper floor plan.

[0024] The structure of the exemplary CAM and search (compare) engine is illustrated in FIG. 2. As shown in FIG. 2, a CAM storage array 201 in the exemplary embodiment includes an array of storage cells such as storage cells 209, 211, 213 and 215. The CAM storage array 201, which in the illustration is “M” CAM entries high and “N” CAM cells wide, contains the CAM register map. Only CAM storage update MUXS, e.g. 217, latches, e.g. 219, and CAM data drivers, e.g. 221, are kept in the CAM storage array 201. The CAM data are driven to source and destination arrays (FIG. 3) where the actual comparisons occur. Thus, unlike the prior art, the CAM compare function is separate from the storage cells in the exemplary embodiment.

[0025] A match array, including Match Array “0” (203) to Match Array “K” (205), contains compare/match logic for looking up (8 to 12) logical registers in the mapper. Each of the 8 to 12 logical registers is compared to the contents of the CAM and a match line (MATCH) is produced for each entry (register) in the mapper. These match lines are encoded 229, 237 in their corresponding match array 203, 205, respectively, to provide the register tags, and are also used to enable the readout 231, 239 of register status bits 243, 241 (the so-called “ready bits”) of the register status array 207. The encoded physical register tags and register status output data 232 and 240 are transmitted outside the mapper to enable different circuits down the pipeline.

[0026] The disclosed CAM structure facilitates the implementation of the register mapper as a group of custom arrays 301 as shown in FIG. 3. Each array is dedicated to execute a specific function. The rows of all arrays are aligned together. Each row of the array is devoted to one register to keep current state, shadow state and controls for that specific register. The entire mapper is sliced into eight special custom arrays to execute the various functions of the register mapper as shown in FIG. 3.

[0027] The CAM storage array 321 as shown in FIG. 3, contains the CAM register map. Only CAM storage latches, update MUX and CAM data drivers are kept in this array. The CAM data are driven to source and destination arrays where the actual comparisons occur. The destination logical register tags 323 are used to update the CAM content.

[0028] A source match array 325 contains compare/match logic for looking up between eight and twelve (eight in the example) logical source registers 327 in the mapper. Each of the logical source registers 327 (logical source search vectors) are compared to the contents of the CAM and a match line is produced for each entry (register) in the mapper. These match lines are encoded in their corresponding match array to provide the register tags and are also used to enable the readout of register status bits or “ready bits”. In FIG. 3, only 8 source arrays 325 are shown for the sake of clarity. The outputs 329 of the source array 325 are driven outside the mapper to enable circuits down the pipeline. The word “source” refers to the source logical register of a given instruction and “destination” refers to the destination logical register of that instruction. For example, in the instruction R3=R1+R2, R1 and R2 are source logical registers and R3 is a destination logical register.

[0029] A Ready Bits Array 331 has the latches to hold the ready bit register status information (w, dl0 & dl1). The “w”, “dl0” and “dl1” are special register status bits to indicate whether the register's data is available (possibly conditioned upon the outcome of a load instruction). These latches require some special shifting and resting functions. The ready bit data are driven to the source array and available to be read out for each source (see FIG. 2 also). Update decoders are also required to control update of these bits as register values become available. When a register is allocated, its w and dl bits are cleared. When a register value becomes available, the w bit is set to 1 and the dl bits are set using information from the instruction issue queue logic. Otherwise, the dl bits shift logically each cycle.

[0030] A BIT array 319 (Architected bit array) holds bits to indicate an “architected” state (A bit) and a “replaced” state (R bit) of the physical registers. It also contains logic to generate these two bits during instruction dispatch. These bits are used to update the A bits and are also sent to the free list array 305 and shadow array 303 during subsequent cycles. After flush, this logic also assists in restoring A bits from the shadow maps 303.

[0031] A Destination array 309, 311, 313 and 315 (destination match array) contains logic for looking up four logical destination registers in the mapper. Four logical destination registers 317 (logical destination search vectors) are compared to the contents of the CAM and four match lines are produced for each entry in the mapper. These four match lines are then OR'ed together for use in generating the A and R bits.

[0032] An Allocation array 307 includes “encoded allocation buffers” to keep encoded register tags that must be sent to local and remote instruction issue queues during dispatch. The Allocation array 307 is also used to indicate register availability and generate a resource hold signal for the mapper when necessary. The array 307 also includes “vectored allocation buffers” to keep the same register identifiers in a vectored format to control register allocation within the mapper during dispatch.

[0033] A Free list array 305 holds bits and uses logic to generate and select a set of free registers to be used during subsequent instruction dispatch.

[0034] A Shadow Map array 303 contains the shadow maps that are saved for each group of dispatched instructions. Two bits “A” and “R” are saved for each group of instructions and for each register in the mapper. Bits are written during the cycle after dispatch from latches stored in the architected bit array. Bits are read during the cycle after instruction completion/flush is received.

[0035] The method and apparatus of the present invention has been described in connection with a preferred embodiment as disclosed herein. The disclosed methodology may be implemented in a wide range of sequences, menus and screen designs to accomplish the desired results as herein illustrated. Although an embodiment of the present invention has been shown and described in detail herein, along with certain variants thereof, many other varied embodiments that incorporate the teachings of the invention may be easily constructed by those skilled in the art. Accordingly, the present invention is not intended to be limited to the specific form set forth herein, but on the contrary, it is intended to cover such alternatives, modifications, and equivalents, as can be reasonably included within the spirit and scope of the invention.