Representative majority voter for bus invert coding

[0001] Buses are used to transmit data from a device to one or more other devices. Interconnects (e.g., on chip interconnects) are used to transmit data form one function on a chip (e.g., microprocessor) to one or more other functions on the chip. Switching data on a bus or interconnects is a significant source of power consumption.

[0002] In high-performance microprocessor designs power consumption is a critical concern, and bus/interconnect power is a large component. Microprocessors that include several processor cores on a single die may require long (traverse a long distance across the die) and wide (large number of parallel bits) buses as interconnections. Each time a bus line is switched, the entire capacitance of the metal wire must be charged or discharged, as well as the capacitance of the repeaters which are inserted along the bus to reduce the delay. Both of these capacitances can be quite large, thus the switching,power is significant.

[0014] FIG. 1 illustrates an exemplary eight bit bus transitioning over several clock cycles. During a first clock cycle (t₀) the bus transmits all 0s. During a second clock cycle (t₁) the bus transmits 5 0s (bits b₀-b₄) and3 1s (b₅-b₇). Comparing the bits transmitted during t₀ and t₁ indicates that 3 bits (bits b₅-b₇) are being transitioned. Accordingly, the 3 bus lines associated with b₅-b₇ would be switched. During a third clock cycle (t₂) the bus transmits all 1s. Comparing the bits transmitted during t₁ and t₂ indicates that 5 bits (bits b₀-b₄) are being transitioned. Accordingly, the 5 bus lines associated with b₀-b₄ would be switched. During a fourth clock cycle (t₃) the bus transmits all 0s. Comparing the bits transmitted during t₂ and t₃ indicates that all bits (bits b₀-b₇) are being transitioned. Accordingly, all 8 bus lines would be switched. During a fifth clock cycle (t₄) the bus transmits 4 0s (bits b₄-b₇) and 4 1s (b₀-b₃). Comparing the bits transmitted during t₃ and t₄ indicates that 4 bits (bits b₀-b₃) are being transitioned. Accordingly, the 4 bus lines associated with b₀-b₃ would be switched.

[0015] One way to reduce the switching power of a bus is to reduce the number of transitions that occur on the bus lines. One technique to reduce the transitions is bus-invert coding. In bus-invert coding, the number of transitions on the bus is reduced by sending either the true or the complement of the bus inputs on each clock cycle. If less than half of the inputs undergo a transition, the true values are sent. If more than half of the inputs undergo a transition, all are inverted and the complement values are sent, which results in less than half of the bus lines transitioning. An extra bit line is required for the bus to indicate whether real or inverted bits are being sent. A receiver at the end of the bus may invert the received data to recover the original inputs if the data transmitted was inverted. Thus, using this technique, the maximum number of simultaneous transitions on the bus is equal to half of the bus lines plus possibly the additional line which signals whether the true or complement of the inputs is being sent.

[0016] FIG. 2 illustrates an exemplary nine bit (eight bits data, one invert bit) bus transitioning over several clock cycles. It should be noted that the data prepared for transmission during each clock cycle is the same data that was prepared for transmission in FIG. 1, while the data actually transmitted is inverted for certain cycles. During a first clock cycle (t₀) the bus transmits all 0s. During a second clock cycle (t₁) the bus has 5 0s (bits b₀-b₄) and 3 1s (b₅-b₇) prepared for transmission. Comparing the bits transmitted during t₀ and those prepared for transmission during t₁ indicates that 3 bits (bits b₅-b₇) are being transitioned. As less then half of the bits are being transitioned the invert bit (bit b₈) will not be set and the real data is transmitted. Accordingly, the 3 bus lines associated with b₅-b₇ would be switched. During a third clock cycle (t₂) the bus has all 1s prepared for transmission. Comparing the bits transmitted during t₁ and those prepared for transmission during t₂ indicates that 5 bits (bits b₀-b₄) are being transitioned. As more then half of the bits are being transitioned the invert bit (bit b₈) is set and the data received is inverted (to all 0s). Inverting the data results in a total of 4 bus lines (3 data lines associated with b₅-b₇ and the invert bit) being transitioned. The inverted data is transmitted during t₂. Accordingly, the 4 associated bus lines would be switched.

[0017] During a fourth clock cycle (t₃) the bus has all 0s prepared for transmission. Comparing the bits transmitted during t₂ (the inverted data) and the bites prepared for transmission t₃ indicates that no bits are being transitioned. As less then half of the bits are being transitioned the invert bit (bit b₈) will not be set and the real data is transmitted. Accordingly, the only bus line being switched would be the invert bit. During a fifth clock cycle (t₄) the bus has 4 0s (bits b₄-b₇) and 4 1s (b₀-b₃) prepared for transmission. Comparing the bits transmitted during t₃ and the bits prepared for transmission during t₄ indicates that 4 bits (bits b₀-b₃) are being transitioned. As exactly half of the bits are being transitioned, the invert bit (bit b₈) is not set and the real data is transmitted. Accordingly, the 4 bus lines associated with b₀-b₃ would be switched.

[0018] According to an alternative embodiment, the invert bit may be set and the data inverted if exactly half of the bits are being switched. According to an alternative embodiment, the setting of the invert bit when exactly half of the data bits are being transitioned may depend on the previous setting of the invert bit. That is, the invert bit may mirror what the previous invert bit was so as not to cause a transition on that line. In this case if the invert bit was previously set it would stay set and if it was not set it would stay unset.

[0019] Comparing the bus transitions of FIG. 1 (normal) to FIG. 2 (bus invert coding), shows that the bus invert coding has the same or less transitions. Between t₀ and t₁ both normal and bus invert coding had 3 transitions. Between t₁ and t₂ the normal transmission had 5 transitions while bus invert coding had 4 transitions (3 data bits and the invert bit). Between t₂ and t₃ the normal transmission had 8 transitions while bus invert coding had 1 transition (the invert bit). Between t₃ and t₄ both normal and bus invert coding had 4 transitions.

[0020] FIG. 3 illustrates an exemplary bus-invert coding system 300. The system 300 includes a transmission unit 310, a bus 320 and a receiving unit 330. The transmission unit 310 includes a transmitter 340, an encoder 350 and a latch 360. The encoder 350 includes an XOR 365, an adder 370 and a conditional inverter (plurality of XORs) 375. The bus 320 includes a line for each bit being transmitted (e.g., k bits) plus an additional line for a signal identifying whether inverted or real values are being transmitted. The receiving unit 330 includes a conditional inverter (plurality of XORs) 380 and a receiver 390.

[0021] The system 300 may be implemented on a chip (e.g., microprocessor) where the transmission unit 310 and the receiving unit 330 are functions on the chip and the bus 320 is a point-to-point interconnect between the functions. The system 300 may be implemented between chips or devices where the transmission unit 310 is one chip or device and the receiving unit 330 is another chip or device and the bus 320 connects the chips or devices. The transmission unit 310 may transmit the data to more than one receiving unit 330 and the bus 320 may be a point-to-multipoint bus.

[0022] The encoder 350 uses the XOR 355 to compare the data previously sent to the data ready to be transmitted in order to determine if a transition has occurred. The adder 360 examines each bit to determine whether there is a transition and adds all of the transitions to decide whether more or less that half of the bits were transitioned. The adder 360 sends an inverting signal 395 based on number of bits transitioning. If more than half are transitioned the adder 360 sends a ‘1’ to the conditional inverter 375. If less then half are transitioned then the adder sends a ‘0’ to the conditional inverter 375. The conditional inverter 375 inverts the signals if a ‘1’ is received and passes the real signals if a ‘0’ is received. The latch 360 transmits the real or inverted signals along with the inverting signal 395 (0 or 1 depending on whether or not to invert) at the appropriate time. The conditional inverter 380 receives the transitions and the inverting signal 395 and either re-inverts the signals or passes the signals through based on the inverting signal 395.

[0023] There are three main sources of overhead in the bus-invert coding scheme: the encoder 350, the one additional bus line, and the conditional inverter 380. The conditional inverter 380 is simply an XOR gate and thus does not represent a significant overhead for long buses. The extra bus line becomes less important for very wide buses. The encoder 350 presents a significant circuit design problem as the adder 370 examines every input to determine whether there is a transition, and then add up all of the transitions to decide what polarity to send down the bus. The encoder 350 utilizing the adder 370 can be referred to as an “exact” majority voter gate. The complexity of the adder 370 grows exponentially with the number of bits on the bus and represents a large delay and power penalty. The adder 370 severely limits the applications where bus-invert coding can be used.

[0024] According to one embodiment, rather than examining all of the inputs to find the exact number that have a transition (as the adder/exact majority voter gate 370 of FIG. 3 does), a group of inputs is examined at a time and results are combine in a tree to arrive at a final decision. This scheme requires less logic levels than an exact majority gate, reducing the delay and energy overhead for the bus-invert encoder. Examining a group of transitions at a time is known as a “representative” majority voter gate. Several different implementations of the “representative” majority voter gate are possible, depending on how many bits are combined in each level of the tree.

[0025] FIG. 4 illustrates an exemplary representative majority voter gate 400 using 2:1 voting gates for an 8-bit bus. The representative majority voter gate 400 taking the place of the adder/exact majority voter gate 370 of FIG. 3. The incoming bits (b₀-b₇) are first compared to the previous data on the bus (b′₀-b′₇) using XOR gates 410 (e.g., XOR 365 of FIG. 3) which outputs a ‘1’ if a transition occurred and a ‘0’ if the data is the same. A first level 420 of the representative majority voter gate 400 uses 2:1 gates 430 to process two transition bits at a time (e.g., bits 0 and 1). Each gate 430 generates a yes (Y) and a No (N) output. Only one bit can be active (set to ‘1’) at a time. If both bits have a transition, the Y output will be set to one and the N output will be set to zero. If neither bit has a transition, the N bit will be set to one and the Y output will be set to zero. If one bit transitions and the other doesn't, both the Y and the N bits will be set to 0 indicating a “don't care” condition at this stage.

[0026] A second level 440 of the representative majority voter gate 400 uses 2:1 gates 450 to receive and process Y and N outputs from two gates 430 and generate a Y and N output based thereupon. As noted above, the outputs from the gates 430 will only have a Y or an N active so that the input to the gate 450 will only have 1 active input for each set of inputs it is processing. The output Y of a gate 450 is set if both inputs are Y (Y=1, N=0), or if one input is Y and the other is “don't care” (Y=0, N=0). The output N is set if both inputs are N (Y=0, N=1), or if one input is N and the other is “don't care”. Neither bit is set (Y=0, N=0) if both inputs have a “don't care” condition or if one input is Y and one input is N. The 2:1 gates 450 are continually used at the various levels of the tree until all bits have been combined. The exemplary representative majority voter gate 400 includes a third level 460 containing a single gate 450. An “invert” signal is then given by the “Y” output of the final gate. If the “invert” signal is a one, all data bits are inverted before being sent down the bus.

[0027] FIG. 5 illustrates an exemplary logic diagram (implementation) of a 2:1 gate 500 (e.g., gate 430 of FIG. 4). The gate 500 includes an AND gate 510 and an NOR gate 520. The AND gate 510 receives the transition value for each of the two bits and generates a Y output. The Y output is active (set to 1) only if both inputs are 1. The NOR gate 520 receives the transition value for each of the two bits and generates an N output. The N output is active (set to 1) only if both inputs are 0.

[0028] FIG. 6 illustrates an exemplary logic diagram (implementation) of a 2:1 gate 600 (e.g., gate 450 of FIG. 4). The gate 600 includes four NAND gates 610, 620, 630, 640 having one input inverted. Each of the NAND gates 610-640 receives a different combination of inputs. A first NAND gate 610 receives a first Yes input (Y₀) and an invert of a second No input (N₁). A second NAND gate 620 receives a second Yes input (Y₁) and an invert of a first No input (N₀). A third NAND gate 630 receives the No and an invert of the Y₁. A fourth NAND gate 640 receives the N, and an invert of the Y₀. The output of the first and second NAND gates 610, 620 are sent to a fifth NAND gate 650 to generate the Y output. The output of the third and fourth NAND gates 630, 640 are sent to a sixth NAND gate 660 to generate the N output.

[0029] FIG. 7 illustrates an exemplary representative majority voter gate 700 using 3:1 voting gates for a 9-bit bus. The representative majority voter gate 700 taking the place of the adder/exact majority voter gate 370 of FIG. 3. The incoming bits (b₀-b₈) are first compared to the previous data on the bus (b′₀-b′₈) using XOR gates 710 (e.g., XOR 365 of FIG. 3) which outputs a ‘1’ if a transition occurred and a ‘0’ if the data is the same. A first level 720 of the representative majority voter gate 700 uses gates 730 to process three transition bits at a time (e.g., bits 0-2). Each gate 730 generates a yes (Y) output. If at least two bits out of the three bits has a transition the Y output will be active (set to ‘1’). If none of the bits has a transition the Y will be inactive (set to ‘0’).

[0030] This proceeds down the tree until all bits have been combined. The exemplary representative majority voter gate 700 includes a second level 740 containing a single gate 730. An “invert” signal is then given by the “Y” output of the final gate. If this “invert” signal is a one all data bits are inverted before being sent down the bus.

[0031] FIG. 8 illustrates an exemplary logic diagram (implementation) of a 3:1 gate 800 (e.g., gate 730 of FIG. 7). The gate 800 includes three NAND gates 810, 820, 830 with each NAND gate receiving a different combination of inputs. A first NAND gate 810 receives a first input (t₀) and a second input (t₁). A second NAND gate 820 receives the t₁ and a third input (t₃). A third NAND gate 830 receives the t₀ and the t₂. The output of each of the NAND gates 810, 820, 830 are sent to a fourth NAND gate 840 to generate the Y output.

[0032] Comparing the representative majority voter gate 400 of FIG. 4 to the representative majority voter gate 700 of FIG. 7 shows that the representative majority voter gate 700 has a shorter length tree due to the 3:1 compression versus the 2:1 compression of the representative majority voter gate 400.

[0033] The representative majority voter gates (e.g., 400 of FIG. 4, 700 of FIG. 7) approximate the results so there are some cases where the encoder decides not to invert the bus even though the number of transitions on the input is greater than half the number of bits on the bus (num_bits/2). While the exact encoder (e.g., adder 370 of FIG. 3) ensures that the maximum number of lines on the bus that switch at a given time (worst-case switching) is equal to 50% of the bus width (neglecting the extra invert line), using a representative voting encoder results in worst-case switching which is larger.

[0034] FIG. 9 illustrates the worst-case switching percentage for buses of different width using both 2:1 and 3:1 voters. For a standard bus the worst-case switching percentage is 100%. For an exact bus-invert coded bus (e.g., 370) the worst-case switching is 50%. Encoding the bus using representative voting (e.g., 400, 700) results in worst-case switching percentages from 70%-80% for typical width buses. This still represents a 20-30% power reduction over a standard bus, while incurring significantly less delay and power penalty than a full bus-invert encoder (e.g., 370).

[0035] FIG. 10 illustrates an exemplary process flow of bus invert coding. Data bits are prepared for transmission at a transmitter 1000. The data bits being prepared are compared to data bits that were just transmitted to determine which bits were transitioned 1010. The bits transitioned are processed in order to determine how an inverting bit should be set 1020. The inverting bit is applied to the received data 1030. If the inverting bit was set the received data will be inverted and if it was not set the received data will be transmitted as it was received. After application of the inverting bit, the data and the inverting bit are transmitted 1040. The processing transactions 1020 can be further broken down to include examining the bit transactions in groups 1060. Groups of 2 or 3 were discussed above, but the grouping is not limited thereby. After the transitions are examined in groups the results of these groups is continually combined in a tree structure in order to determine the inverter bit setting 1070. The number of levels of the tree depends on the size of the bus and how many bits are combined into a group. The process flow above described the encoding of data as it is prepared for transmission. The transmission of the data entails adding an additional line in the bus to transmit the invert bit. At the receiving end the data and the invert bits are received 1080. If the invert bit it indicates that the data sent was inverted and if the invert bit was not set then the real data was sent. The invert bit is applied to the data 1090 and will either pass the real data or un-invert the inverted data.

[0036] The various embodiments described herein could be utilized in a computer system. As one skilled in the art would recognize a computer system includes processor(s) and memory and may interface to periphery, networks, the Internet, and other computer systems. The computer system may include a single die with the processor(s) and memory or may include a processor die and off die memory (e.g., a memory die). The various embodiments may be implemented as part of the memory and/or part of the processor(s).

[0037] Although the various embodiments have been illustrated by reference to specific embodiments, it will be apparent that various changes and modifications may be made. Reference to “one embodiment” or “an embodiment” means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, the appearances of the phrase “in one embodiment” or “in an embodiment” appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

[0038] Different implementations may feature different combinations of hardware, firmware, and/or software. It may be possible to implement, for example, some or all components of various embodiments in software and/or firmware as well as hardware, as known in the art. Embodiments may be implemented in numerous types of hardware, software and firmware known in the art, for example, integrated circuits, including ASICs and other types known in the art, printed circuit broads, components, etc.

[0039] The various embodiments are intended to be protected broadly within the spirit and scope of the appended claims.