Abstract:
In general, in one aspect, the disclosure describes an apparatus inluding a representative majority voter gate to analyze bit transitions of a pluraility of bits. The plurailuty of bits are analzed in groups. The representative majority voter gate generates an invert signal based on the analysis. The apparatus further inludes a conditional inverter to apply the invert signal to the pluraility of bits.

Description:
BACKGROUND  
       [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.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0003]     The features and advantages of the various embodiments will become apparent from the following detailed description in which:  
         [0004]      FIG. 1  illustrates an exemplary eight bit bus transitioning over several clock cycles, according to one embodiment;  
         [0005]      FIG. 2  illustrates an exemplary nine bit (eight bits data, one invert bit) bus transitioning over several clock cycles, according to one embodiment;  
         [0006]      FIG. 3  illustrates an exemplary bus-invert coding system, according to one embodiment;  
         [0007]      FIG. 4  illustrates an exemplary representative majority voter gate using 2:1 voting gates for a 8-bit bus, according to one embodiment;  
         [0008]      FIG. 5  illustrates an exemplary logic diagram (implementation) of a 2:1 gate, according to one embodiment;  
         [0009]      FIG. 6  illustrates an exemplary logic diagram (implementation) of a 2:1 gate, according to one embodiment;  
         [0010]      FIG. 7  illustrates an exemplary representative majority voter gate using 3:1 voting gates for a 9-bit bus, according to one embodiment;  
         [0011]      FIG. 8  illustrates an exemplary logic diagram (implementation) of a 3:1 gate, according to one embodiment;  
         [0012]     FIG. 9  illustrates the worst-case switching percentage for buses of different width using both 2:1 and 3:1 voters, according to one embodiment; and  
         [0013]      FIG. 10  illustrates an exemplary process flow of bus invert coding, according to one embodiment.  
     
    
     DETAILED DESCRIPTION  
       [0014]      FIG. 1  illustrates an exemplary eight bit bus transitioning over several clock cycles. During a first clock cycle (t 0 ) the bus transmits all 0s. During a second clock cycle (t 1 ) the bus transmits 5 0s (bits b 0 -b 4 ) and3 1s (b 5 -b 7 ). Comparing the bits transmitted during t 0  and t 1  indicates that 3 bits (bits b 5 -b 7 ) are being transitioned. Accordingly, the 3 bus lines associated with b 5 -b 7  would be switched. During a third clock cycle (t 2 ) the bus transmits all 1s. Comparing the bits transmitted during t 1  and t 2  indicates that 5 bits (bits b 0 -b 4 ) are being transitioned. Accordingly, the 5 bus lines associated with b 0 -b 4  would be switched. During a fourth clock cycle (t 3 ) the bus transmits all 0s. Comparing the bits transmitted during t 2  and t 3  indicates that all bits (bits b 0 -b 7 ) are being transitioned. Accordingly, all 8 bus lines would be switched. During a fifth clock cycle (t 4 ) the bus transmits 4 0s (bits b 4 -b 7 ) and 4 1s (b 0 -b 3 ). Comparing the bits transmitted during t 3  and t 4  indicates that 4 bits (bits b 0 -b 3 ) are being transitioned. Accordingly, the 4 bus lines associated with b 0 -b 3  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 0 ) the bus transmits all 0s. During a second clock cycle (t 1 ) the bus has 5 0s (bits b 0 -b 4 ) and 3 1s (b 5 -b 7 ) prepared for transmission. Comparing the bits transmitted during t 0  and those prepared for transmission during t 1  indicates that 3 bits (bits b 5 -b 7 ) are being transitioned. As less then half of the bits are being transitioned the invert bit (bit b 8 ) will not be set and the real data is transmitted. Accordingly, the 3 bus lines associated with b 5 -b 7  would be switched. During a third clock cycle (t 2 ) the bus has all 1s prepared for transmission. Comparing the bits transmitted during t 1  and those prepared for transmission during t 2  indicates that 5 bits (bits b 0 -b 4 ) are being transitioned. As more then half of the bits are being transitioned the invert bit (bit b 8 ) 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 5 -b 7  and the invert bit) being transitioned. The inverted data is transmitted during t 2 . Accordingly, the 4 associated bus lines would be switched.  
         [0017]     During a fourth clock cycle (t 3 ) the bus has all 0s prepared for transmission. Comparing the bits transmitted during t 2  (the inverted data) and the bites prepared for transmission t 3  indicates that no bits are being transitioned. As less then half of the bits are being transitioned the invert bit (bit b 8 ) 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 4 ) the bus has 4 0s (bits b 4 -b 7 ) and 4 1s (b 0 -b 3 ) prepared for transmission. Comparing the bits transmitted during t 3  and the bits prepared for transmission during t 4  indicates that 4 bits (bits b 0 -b 3 ) are being transitioned. As exactly half of the bits are being transitioned, the invert bit (bit b 8 ) is not set and the real data is transmitted. Accordingly, the 4 bus lines associated with b 0 -b 3  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 0  and t 1  both normal and bus invert coding had 3 transitions. Between t 1  and t 2  the normal transmission had 5 transitions while bus invert coding had 4 transitions (3 data bits and the invert bit). Between t 2  and t 3  the normal transmission had 8 transitions while bus invert coding had 1 transition (the invert bit). Between t 3  and t 4  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 0 -b 7 ) are first compared to the previous data on the bus (b′ 0 -b′ 7 ) 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&#39;t, both the Y and the N bits will be set to 0 indicating a “don&#39;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&#39;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&#39;t care”. Neither bit is set (Y=0, N=0) if both inputs have a “don&#39;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 0 ) and an invert of a second No input (N 1 ). A second NAND gate  620  receives a second Yes input (Y 1 ) and an invert of a first No input (N 0 ). A third NAND gate  630  receives the No and an invert of the Y 1 . A fourth NAND gate  640  receives the N, and an invert of the Y 0 . 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 0 -b 8 ) are first compared to the previous data on the bus (b′ 0 -b′ 8 ) 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 0 ) and a second input (t 1 ). A second NAND gate  820  receives the t 1  and a third input (t 3 ). A third NAND gate  830  receives the t 0  and the t 2 . 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.