Technique for determining if a logical sum of a first operand and a second operand is the same as a third operand

A system is used to determine if a sum of a first operand and a second operand is the same as a third operand wherein a comparison to the third operand is of variable length. This is particularly useful in a content addressable memory (CAM) where the likelihood of hit is commonly improved over a set associative cache and allows for the CAM to identify different things. For example, an entry can be one length to identify a page of a memory and another entry be a different length to identify a page of memory. This is better understood by reference to the following description and the drawings.

BACKGROUND

This disclosure relates generally to memories, and more specifically, to determining a hit in a content addressable memory.

2. Related Art

Cache memories are common for improving speed. The improved speed is achieved with a high speed memory that is small but fast compared to main memory. Cache accesses may be performed with a variety of techniques. Sometimes these techniques involve the sum of a first operand and a second operand. Caches are useful only when there is a hit in the cache. Because the cycle time of a system may be limited by the cache access speed, it is useful to improve the speed of operation in such a case where the stored data is accessed using the sum of the first and second operands. This quickens access and system speed or allows more entries for a given speed. Also there are benefits to having a cache that can variably size entries. For example, it may desirable to allow variation in how a hit is determined.

Thus, there is a need for a technique that improves upon one or more of the issues described above.

DETAILED DESCRIPTION

A system is used to determine if a sum of a first operand and a second operand is the same as a third operand wherein a comparison to the third operand is of variable length. This is particularly useful in a content addressable memory (CAM) where the likelihood of hit is commonly improved over a limited set associative cache and allows for the CAM to identify different things in different entries. For example, one entry can be one length to identify a page of a memory and another entry can be a different length to identify a page of memory of a different size. This is better understood by reference to the following description and the drawings.

Shown inFIG. 1is a system10comprising propagate and generate logic12, a CAM14, a carry-in circuit20, and a controller22. CAM14comprises a RAM select circuit16, a RAM array18, and a plurality of rows of which a row24, a row26, a row28, and a row30are shown inFIG. 1. Rows24,26,28, and30provide inputs h0, h1, h2, and h3, respectively, to RAM select circuit16. Row24comprises compare logic32and bitcell portion34. Row26comprises compare logic36and bitcell portion38. Row28comprises compare logic40and bitcell portion42. Row30comprises compare logic44and bitcell portion46. RAM18has a plurality of readable segments of which RAM0, RAM1, RAM2, and RAMj are shown coupled to RAM select circuit16. Controller22provides signals mask0, mask1, mask2, and mask j to logic circuits32,36,40, and44, respectively.

In operation, system10determines if the sum of input signals A and B is the same as the contents of one of the bitcell portions such as bitcell portions34,38,42, and46and if there is a hit, then RAM18will provide the selected entry as an output. The determination is made concurrently with all of the bitcell portions. As an example, the determination will be explained with regard to bitcell portion38. Inputs A and B are multi-bit and are shown as a0-ai and b0-bi, respectively. The number of bits is the same as the number of bits of the bitcell portions34,38,42, and46. For each bit location, propagate and generate circuit12provides a propagate signal p and a generate signal g. For example, corresponding to bit location k1of bitcell portion38, a propagate signal p1and a generate signal g1are generated in response to signal a1and signal b1. Similarly, propagate signal p2and generate signal g2are generated in response to signals a2and b2. Compare logic36receives mask1which includes bits m10-m1iwhich identify which portion of bitcell portion38is relevant and required carry information. Carry-in logic20receives inputs A and B and determines a true carry for each bit location for the most significant bit location to next to least significant bit location shown as signals tc0-tc(i-1). Simply providing the carry information for each bit location is much simpler and faster than having to perform a full add. Thus, carry-in circuit20provides the carry information in less than a clock cycle. Compare logic circuit36thus uses propagate signals p0-pi, generate signals g0-gi, stored information k10-k1i, mask1signals, and true carry information tC0-tC(i-1) to determine if there is a match between the sum of A and B and the contents of bitcell portion38. If there is a match, this a considered a hit and signal h1is asserted which causes RAM select circuit16to cause the contents of RAM1to be provided as the selected output. If there is not a match, this a considered a miss and signal h1is deasserted so that RAM select circuit16does not cause RAM1to provide its contents as the selected entry. A similar operation is performed with regard to the all of the bit locations to determine if any contents of RAM18are output as the selected entry.

Shown inFIG. 2is logic circuit36comprising bit logic39, bit logic41, bit logic43, bit logic45, and AND circuit47. Additional logic circuits are present but not shown. Bit logic39receives propagate signal p0, generate signal g0, bitcell bit k10, bitcell bit bar kb10, mask m10, mask m11, true carry tc0, and required carry rc0. Bit logic41receives propagate signal p1, generate signal g1, bitcell bit k11, bitcell bit bar kb11, mask m11, mask m12, true carry tc1, and required carry rc1. Bit logic43receives propagate signal p2, generate signal g2, bitcell bit k12, bitcell bit bar kb12, mask m12, mask m13, true carry TC2, and required carry rc2. Bit logic45receives propagate signal pi, generate signal gi, bitcell bit k1i, bitcell bit bar kb1i, mask1j, a deasserted signal0for a second mask signal and deasserted signals0for the carry bits. Bit logic circuits39,41,43, and45correspond to bit locations,0,1,2, and i, respectively. Bit location0in this example is the most significant bit. Thus bit location i is the least significant bit, which is why no carry is provided for that bit.

In operation, each bit logic circuit39,41,43, and45may determine if there is a match for its corresponding bit location. Using bit logic circuit41as an example, mask signal m11determines if a compare function is to be performed by bit logic circuit41. If Mask m11is a asserted then a compare is performed. If Mask m11is deasserted, then the output z1is asserted and no comparison is required. When the mask signal associated with the bit logic is deasserted, there is no need for a carry. If mask m12is asserted, the required carry rc1is used. If mask m12is deasserted, then true carry tc1is used. When the preceding bit location is not performing a compare but the present bit location is, then the true carry must be used because the required carry is not valid. If both the preceding and present bit location are performing a compare then the required carry is valid. The required carry can be generated faster than the true carry so is preferred when available. Also the true carry may become prohibitively slow when near the most significant bit. The compare is performed by adding the bitcell value to the propagate value and comparing to the carry. If they are the same that is a hit for that bit location. If they are different then there is a miss for that bit location which also means there is a miss for the compare logic. Thus, for bit logic41, propagate signal p1is added to signal k11and compared to either required carry rc1or true carry tc1. If the comparison is that they are the same, then that is a hit. If they are different, then that is a miss. Generate signal g1is used to provide the required carry signal for the next bit location. Thus, if generate signal g1is asserted, then required carry signal rc0is asserted to bit logic39. Required carry rc0can also be asserted by signal k11being deasserted and propagate signal p1being asserted.

Shown inFIG. 3is a logic diagram of bit logic41. Bit logic41comprises a multiplexer48, an Exclusive OR gate50, an Exclusive NOR gate52, an OR gate54, an AND gate56, and an OR gate58. Multiplexer48has a first input for receiving true carry tc1, a second input for receiving required carry rc1, a select input for receiving mask m12, and an output. Exclusive OR gate50has a first input for receiving signal k11, a second input for receiving propagate signal p1, and an output. Exclusive NOR gate52has a first input coupled to the output of multiplexer48, a second input coupled to the output of Exclusive OR gate50, and an output. OR gate54has a first input for receiving mask signal m11, a second input coupled to the output of Exclusive NOR gate52, and an output providing signal z1. AND gate56has a first input for receiving signal k11b, which is the logical complement of signal k11, a second input for receiving signal p1, and an output. OR gate58has a first input coupled to the output of AND gate56, a second input for receiving generate signal g1, and an output for providing required carry signal RC0.

In operation, Exclusive OR gate50functions as an adder so that a zero (logic low) is output when signals p11and k11both are a one or both are a zero. Otherwise a one is output by Exclusive OR gate50. Multiplexer48provides the proper carry to the first input of Exclusive NOR gate52. Exclusive NOR gate52responds by providing a logic high output if the carry, signal tc1or tc1, and the output of Exclusive OR gate are the same. This is a match which is also commonly called a hit. If the inputs to Exclusive NOR gate are different a logic low is output and that indicates a miss. OR gate54provides a hit signal z1at a logic low, which indicates a miss, if both the output of Exclusive NOR gate52and mask m1are a logic low. Mask m11can force a hit by being a logic high. This would occur, for example, if the bit location corresponding to bit logic41does not have data that is relevant. AND gate56provides a logic high if both signal kb11and propagate signal p1are a logic high. Or gate58provides required carry rc0at logic high, representing a one, if the output of AND gate56is a logic high or generate signal g1is a logic high. Thus a carry is indicated for the next bit location if either the generate signal is a logic high or the stored logic state is a logic low and the propagate signal is a logic high.

Shown inFIG. 4is a circuit using N and P channel transistors implementing compare logic41. The P channel transistors are indicated by a small circle on the gate symbol.

Shown inFIG. 5is a combination block diagram and logic diagram of propagate and generate circuit12comprising a propagate and generate block60, a propagate and generate block62, a propagate and generate block64, and a propagate and generate block66. Propagate and generate block62is shown comprising an AND gate68and an Exclusive OR gate70. AND gate68has a first input for receiving signal a1, a second input for receiving signal b1, and an output for providing generate signal g1. Exclusive OR gate70has first input for receiving signal a1, a second input for receiving signal b1, and an output for providing propagate signal p1. Generate signal g1is provided as a logic high when both signals a1and b1are a logic high and otherwise is provided as a logic low. Propagate signal p1is provided as a logic high when signals a1and b1are different and a logic low when signals a1and b1are the same. Blocks60,64, and66operate in the same way with regard to the a and b signals they receive. Each of blocks60,62,64, and66correspond to a bit location in CAM14. Block62for example corresponds to bit location1in bitcell portions34,38,42, and46. Similarly blocks60,64, and66correspond to bit locations0,2, and l, respectively. Blocks60,62,64, and66each provide the propagate and generate signals to compare logic32,36,40, and44, respectively, for the bit location to which they correspond.

The combination of a propagate and generate block and a bit logic circuit effectively form an adder of a bit location of signals A and B and a comparison to that same bit location in stored entry K. For example, bit logic41and propagate and generate block62correspond to bit location1. Thus, propagate and generate block62and bit logic41together function to be equivalent to an add of signals A and B that results in a value for bit location1and compare that value to the value of k11, which is the value stored in bit location1of bit cell portion38. This function of propagate and generate of block62and bit logic41can be considered a logic operation on a bit location. This logic operation can also be viewed as achieving this result by performing a full add of single bits of signal A, signal B, and Kb (complement of K) at the particular bit location with the real carry signal for the next most significant bit location being the carry of the add. This logic operation is performed on each bit location of a bitcell portion that is within the selected length for that bitcell portion. For example, if bitcell portion includes bit locations0-7, then the logic operation is performed on each of bit locations0-7, which is eight bit locations. These bit operations can be performed concurrently by the bit logic circuits, such as bit logic39,41,43and45shown inFIG. 2. The generation of the true carry is a little slower for the more significant bits, but the bit logic circuits are not in a chain in which a signal propagates through them serially. Thus, they can function concurrently.

Shown inFIG. 6is compare logic80that may be used in an alternative embodiment. In the case of system10, the various compare logic circuits, such as compare logic36, has the ability to define the length of an operand between any two bits. This can cause delays that may be excessive. Compare logic80is limited to defining the operand length on every fourth bit location. Compare logic80has bit logic for each bit location. Shown inFIG. 6are bit logic82, bit logic84, bit logic86, bit logic88, bit logic92, bit logic94, bit logic96, bit logic98, and bit logic102corresponding to bit locations k0, k1, k2, k3, k4, k5, k6, k7, and k8, respectively. Each bit logic circuit provides the required carry to the next most significant bit location except for every fourth bit location where the true carry may be used instead. Between every fourth bit logic is a size logic circuit. Shown inFIG. 6are size logic90between bit logic88and bit logic90and size logic100between bit logic98and bit logic102which is between the bit logic circuits corresponding to bit location4and bit location3. Bit logic92outputs required carry rc3to size logic90. Size logic90also receives true carry tc3. Size logic90also receives a mask signal m0from the controller. In this case mask signal m0indicates if the size includes those locations and thus also if the true carry should be coupled to bit logic88. Bit logic90outputs carry signal c3to bit logic88which thus may be either true carry tc3or required carry rc3in response to mask m0. A size logic circuit, size logic100, is between bit logic98and bit logic102and similarly performs a selection between true carry tc7and required carry rc7for coupling as carry signal c7to bit logic98. At the point at which the boundary is set, all less significant bits are considered a hit. Shown inFIG. 6is an AND gate108which has inputs connected to the hit/miss outputs z4, z5, z6, and z7of logic and asserts an output if all of these hit/miss outputs are asserted. Also shown is an OR gate106that has an input coupled to the output of AND gate108and an input coupled to mask m0. If mask m1is deasserted meaning that the boundary does not include the previous locations, then OR gate106asserts an output indicating a hit for bit locations4-7. That is to say, bit locations not within the length of the operand are forced to indicate a hit. The most significant four bits in this example are always considered to be within the operand length so only have a single AND gate104to indicate a hit or miss for those four bit locations.

By now it should be appreciated that there has been provided a circuit comprising an input to receive a first operand, an input to receive a second operand, a first circuit for providing a length indication, and a logic circuit for providing an indication of a match between a logical sum of the first operand and the second operand with a set of bits of a third operand. A length of the set of bits is determined by the length indication. The first operand includes a first plurality of bits. The second operand includes a second plurality of bits. The logic circuit generates the indication of the match by performing a plurality of bit logic operations. Each of the plurality of bit logic operations includes a logic operation on a bit of the first operand of a corresponding bit location, a bit of a second operand of the corresponding bit location, and a bit of the third operand of the corresponding bit location to generate a result and comparing the result with a carry indication generated from a logic operation on bits including bits of an immediately less significant bit location from the corresponding bit location. Each of the bit logic operations of the plurality of bit logic operations is performed for a different corresponding bit location of a plurality of bit locations. The circuit may further comprise a first carry determination circuit, the first carry determination circuit generating a first carry indication of at least one bit of carry bits of an add operation of the first operand and the second operand; and a selection circuit; wherein the selection circuit selects, based on the length indication, one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of a first bit location, one bit of the second operand of the first bit location, and one bit of the third operand of the first bit location, as the carry indication for the bit logic operation of an adjacent less significant bit location to the first bit location. The circuit may be further characterized by, for the bit location, a bit logic operation of the plurality of bit logic operations being for generating a result of a bit addition of a bit of the first operand, a bit of a second operand, and a bit of the third operand, and a comparison of the result with the one of the group. The circuit may be further characterized by the bit logic operation for generating the result using a first representation of a bit of the third operand, wherein the logic operation to generate the second carry indication uses a second representation of the bit of the third operation, wherein the second representation is complementary to the first representation. The circuit may be further characterized by each of the plurality of bit logic operations performed by the logic circuit generating a bit result of a plurality of bit results, the logic circuit masks the plurality of bit results as per the length indication. The circuit may further comprise a first carry determination circuit, the first carry determination circuit generating a first carry indication of at least one bit of carry bits of an add operation of the first operand and the second operand; wherein for each bit location of a first subset of the plurality of bit locations, the carry indication is selected, based on the length indication, from one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the first subset, one bit of the second operand of the immediately less significant bit location to each bit location of the first subset, and one bit of the third operand of the immediately less significant bit location to each bit location of the first subset; and wherein for each bit of a second subset of the plurality of bit locations, the carry indication is generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the second subset, one bit of the second operand of the immediately less significant bit location to each bit location of the second subset, and one bit of the third operand of the immediately less significant bit location to each bit location of the second subset. The circuit may be further characterized by a bit location of the first subset occurring at every fourth bit location of the plurality of bit locations wherein intervening three bit locations are bit locations of the second subset. The circuit may be further characterized by the second subset having a greater number of bit locations of the plurality of bit locations than the first subset. The circuit may be further characterized by the logic circuit being implemented in a content addressable memory, the third operand being stored in a storage location of a plurality of storage locations of the content addressable memory, the logic circuit generating a plurality of indications wherein each indication of the plurality is an indication of a match between a logical sum of the first operand and the second operand with a set of bits of a value from each storage location of the plurality of storage locations, wherein the length of the set of bits for each storage location is determined by the length indication. The circuit may be further characterized by the length indication for a first storage location of the plurality of storage locations being capable of indicating a different length than for a second storage location of the plurality of storage locations.

Also described is a method of comparing a logical sum of a first operand and second operand with a third operand. The method includes receiving a first operand by logic circuitry. The method further includes receiving a second operand by the logic circuitry. The method further includes receiving a length indication by the logic circuitry. The method further includes generating, by the logic circuitry, an indication of a match between a logical sum of the first operand and the second operand with a set of bits of a third operand, wherein the length of the set of bits is determined by the length indication. The generating includes performing a plurality of bit logic operations by the logic circuitry, wherein each bit logic operation on the plurality of bit logic operations corresponds to a bit position of a plurality of bit positions, wherein each of the plurality of bit logic operations includes performing a logic operation on a bit of the first operand of a corresponding bit location of the plurality of bit locations, a bit of a second operand of the corresponding bit location, and a bit of the third operand of the corresponding bit location to generate a result and comparing the result with a carry indication generated from a logic operation on bits including bits of an immediately less significant bit location from the corresponding bit location. The method may further comprise generating a first carry indication of at least one bit of a plurality of carry bits of an add operation of the first operand and the second operand; selecting, based on the length indication, one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of a first bit location, one bit of the second operand of the first bit location, and one bit of the third operand of the first bit location; wherein for a next significant bit location to the first bit location, the carry indication used for the bit logic operation of the plurality of logic operations as the selected one of the group. The method may be further characterized by the logic operation for generating the second carry indication including an addition operation of the one bit of the first operand of a first bit location, the one bit of the second operand of the first bit location, and the one bit of the third operand of the first bit location. The method may be further characterized by the performing a plurality of bit logic operations generating a plurality of bit results; and the generating an indication of a match including masking the plurality of the bit results as per the length indication. The method may further comprise generating a first carry indication of at least one bit of a plurality of carry bits of an add operation of the first operand and the second operand; wherein for each bit location of a first subset of the plurality of bit locations, the carry indication is selected, based on the length indication, from one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the first subset, one bit of the second operand of the immediately less significant bit location to each bit location of the first subset, and one bit of the third operand of the immediately less significant bit location to each bit location of the first subset; and wherein for each bit of a second subset of the plurality of bit locations, the carry indication is a carry indication is generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the second subset, one bit of the second operand of the immediately less significant bit location to each bit location of the second subset, and one bit of the third operand of the immediately less significant bit location to each bit location of the second subset.

Described also is a content addressable memory that includes a an input to receive a first operand, an input to receive a second operand, a plurality of storage locations, and logic circuitry for providing a plurality of indications where each indication of the plurality of indications corresponds to a storage location of the plurality of storage locations, wherein each indication of the plurality of indications is an indication of a match between a logical sum of the first operand and the second operand with a set of bits of a value from a corresponding storage location of the plurality of storage locations. F or each indication of the plurality of indications, the logic circuit generates the indication of the match by performing a plurality of bit logic operations, wherein each of the plurality of bit logic operations includes a logic operation on a bit of the first operand of a corresponding bit location, a bit of a second operand of the corresponding bit location, and a bit of the corresponding bit location of a value from the corresponding storage location to generate a result and comparing the result to a carry indication generated from a logic operation on bits including bits of an immediately less significant bit location from the corresponding bit location, wherein each of the bit operations of the plurality is performed for a different corresponding bit location of a plurality of bit locations. The content addressable memory may be further characterized by, for each indication of the plurality of indications, each of the plurality of bit logic operations including a bit addition of the bit of the first operand of a corresponding bit location, the bit of a second operand of the corresponding bit location, and the bit of the corresponding bit location of the value from corresponding storage location. The content addressable memory may further comprise a first circuit for providing a length indication, wherein for each indication of the plurality of indications, the bit length of the set of bits is determined by the length indication. The content addressable memory may further comprise a first carry determination circuit, the first carry determination circuit generating a first carry indication of at least one bit of carry bits of an add operation of the first operand and the second operand, wherein for each indication of the plurality of indications, for each bit location of at least some bit locations of the plurality of bit locations, the carry indication is selected, based on the length indication, from one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location, one bit of the second operand of the immediately less significant bit location to each bit location, and one bit of a value from a corresponding storage location of the immediately less significant bit location to each bit location. The content addressable memory may further comprise a first carry determination circuit, the first carry determination circuit generating a first carry indication of at least one bit of carry bits of an add operation of the first operand and the second operand, wherein for each indication of the plurality of indications, for each bit location of a first subset of the plurality of bit locations, the carry indication is selected, based on the length indication, from one of a group consisting of a bit of the first carry indication and a second carry indication generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the first subset, one bit of the second operand of the immediately less significant bit location to each bit location of the first subset, and one bit of a value from a corresponding storage location of the immediately less significant bit location to each bit location of the first subset, and for each bit of a second subset of the plurality of bit locations, the carry indication is generated from a logic operation on one bit of the first operand of an immediately less significant bit location to each bit location of the second subset, one bit of the second operand of the immediately less significant bit location to each bit location of the second subset, and one bit of a value from a corresponding storage location of the immediately less significant bit location to each bit location of the second subset.