Inserting bus inversion scheme in bus path without increased access latency

[0002] 1. Field of the Invention

[0003] The invention pertains generally to computer data buses. In particular, it pertains to reducing latency on a bus by performing a data bus inversion operation in parallel with an error correction operation.

[0004] 2. Description of the Related Art

[0005] Improvements in processor speed have increased the pressure to transfer data more quickly throughout the computer system. In a related effort, system designers attempt to minimize power consumption and electrical noise caused by high-speed switching on the data lines. This has led to a development described as Data Bus Inversion (DBI), which is a bus technique that examines the data bits being transmitted over the parallel lines of a data bus, determines the number of bits that are active (meaning the line is being driven by an active transistor output rather than being passively held at a predetermined voltage level by an inactive output), and inverts the data bits if more than half of them are active, thereby resulting in less than half of them being active on the bus. This minimizes the number of line driver transistors that are active during any given data transfer, resulting in a reduction in power consumption and a reduction of the other problems that are caused by multiple high speed lines being turned on at the same time.

[0006] FIG. 1 shows an example of a system 1 using DBI. A bus requester 10 (a device that can initiate a transfer over the bus) makes a request to write to memory 11 over data bus 18, which may have multiple parallel data lines. A diagonal slash across a connecting line in the figures indicates multiple parallel lines (for example, 16 or 32 lines) that are illustrated as a single line for simplicity.

[0007] Requestor 10 can be a processor or any other device capable of initiating a read or write operation to memory. The data lines from requestor 10 go to inverter 16, where they may or may not be inverted before being placed on bus 18. The data lines are also monitored by inversion decision logic 14. In the case of a write operation, the data from device 10 is examined by decision logic 14 to determine if more than half the data lines are active. If they are, decision logic 14 sends a signal to inverter 16 to invert the data lines before placing them on bus 18. If fewer than half of the data lines are not active, the signal from logic 14 to inverter 16 indicates that no inversion is necessary, and inverter 16 allows the data signals to pass to bus 18 without inversion.

[0008] If the data has been inverted, the receiving circuitry must invert it again to restore the original data. If the data has not been inverted, the receiving circuit leaves the data as it is. Since the receiving circuit must know which to do, a status line 19 is incorporated in the bus to indicate whether the data is inverted. If inversion decision logic 15 receives an indication of inversion over line 19, it sends a signal to inverter 17 to invert the data back to its original form before passing the data on to memory 11.

[0009] The system can also work in the opposite direction for data being read from memory, with decision logic 15 deciding whether to invert the data, and sending a signal on status line 19 telling decision logic 14 whether to reinvert the data before passing the data to requester 10.

[0010] While inverting the data is simple and fast, deciding whether to invert the data involves a time-consuming process of counting the active bits. This time is added to the amount of time it takes to complete a data transfer. This increase in latency, while small in absolute terms, can be a significant fraction of bus transfer time when dealing with high-speed data buses capable of transferring data in nanoseconds. An increase of 10-20% in bus latency can reduce bus bandwidth by a comparable amount, resulting in a significant loss of system performance.

[0011] The bus latency problem is further aggravated by the operation of error correction code circuitry, as shown in system 2 of FIG. 2. RAM memory is commonly subject to data errors. To counteract this, most modern memory systems incorporate error correction code (ECC) logic. When write data is received, ECC logic 23 generates a multi-bit code based on the particular bit pattern in the data, and stores that code in memory with the associated data. When the data is later read from memory, the ECC code is calculated again using the same algorithm, based on the data just read from memory 21. If the old and new codes match, the data is considered correct and is handled normally. However, if the two codes disagree, ECC logic 23 assumes an error in the data from memory, so it corrects the error based on the ECC code retrieved from memory. ECC algorithms permit most errors to be corrected in this manner, thus allowing the data to be forwarded and processing to continue. Unfortunately, generating and comparing the ECC code also takes a finite amount of time, which is added to the total time for the data transfer. If an error occurs and the data has to be corrected, the additional time delay is even greater.

[0012] The benefits of ECC data correction are generally considered to outweigh the resultant increase in bus latency. However, when the delay caused by DBI is added to the delay caused by ECC, the total latency in a bus transaction may become intolerable.

[0013] FIG. 1 shows a conventional system using DBI.

[0014] FIG. 2 shows a conventional system using DBI and ECC.

[0015] FIG. 3 shows a system of the invention.

[0016] FIG. 4 shows a more detailed view of the ECC and DBI logic.

[0017] The invention reduces or eliminates the effects of delays in the inversion decision logic by performing that function in parallel with other bus functions that also take time. In one embodiment, the inversion decision logic operates in parallel with the ECC logic.

[0018] FIG. 3 shows one embodiment of a system 3 of the invention, in which inversion decision logic 35 operates in parallel with ECC logic 33. A bus requestor 10 (a device that can initiate a data transfer over the bus) can make a memory request to memory 21 over bus 18. Requestor 10 can be any device that can initiate a memory operation, such as a processor. Depending on the direction of data flow between requestor 10 and memory 21, the data can be inverted by inverter 16 and reinverted by inverter 17, or it can be inverted by inverter 17 and reinverted by inverter 16. Alternately, it can be left as is, without inversion, by both inverters 16 and 17. Therefore, inverters 16 and 17 are each conditional inverters, i.e., they can invert the data or not invert the data, depending on a condition such as the state of a control signal. As previously described, the decision to invert or not can be based on minimizing the number of data signals that are active during the data transfer. A data line is considered active if the driver circuit actively switches the signal, while it is considered inactive if the driver circuit leaves the signal in its default state. Because most computer buses allow multiple devices to control each line, each data line will have a default state in which no devices are actively driving the signal, and an active state in which at least one device is driving the signal. In the case of a bipolar switch with pullup resistors, the line can be considered inactive if the driver transistor is turned off so that the signal is passively pulled up to its idle state, while the line can be considered active if the driver transistor is turned on so that the signal is switched to the opposite state. Generally, the active state is considered a logic ‘1’, and the inactive state is considered a logic ‘0’, but because logic states can be redefined at will, this definition is less useful.

[0019] If more than half the lines on the bus would normally be active during a transfer, all the data lines can be inverted so that less than half the lines on bus 18 will then be active. If less than half the lines on the bus would normally be inactive during a transfer, the data can be passed on to the bus without inversion, so that less than half the lines on bus 18 will be inactive. If exactly half the lines are active, the lines can be inverted or left alone, depending on the convention being followed. In one embodiment, the lines are not inverted, since the inversion does not reduce the number of active lines on bus 18.

[0020] Once the data is transmitted from inverter 16 to inverter 17, inverter 17 must know whether to reinvert the inverted data or leave the non-inverted data as is. This choice is determined by the state of inversion status line 19. If the data was inverted by inverter 16, decision logic 14 can indicate this by activating a signal on inversion status line 19. This signal can be detected by decision logic 35, which uses that information to determine whether to reinvert the data received from bus 18 or leave it as is. Thus the decision to invert or not invert, once made by decision logic 14 at the transmitting end, is transferred to decision logic 35 at the receiving end along with the associated data, so that the receiving end knows whether or not to reinvert the data. As before, inverter 17 is controlled by inversion decision logic 35.

[0021] For data transfers in the opposite direction, the functions are reversed, with decision logic 35 controlling whether the transmitted data is inverted by inverter 17, and simultaneously placing an inversion status signal on line 19 so that decision logic 14 will be able to tell inverter 16 whether or not to reinvert the received data. In one embodiment, status line 19 can be a single bidirectional bus line that both decision logic circuits 14 and 35 use for transmitting and receiving the inversion status signal.

[0022] Data that has gone from inverter 16 to inverter 17, whether it has been inverted/reinverted or not, is presented to error correcting code (ECC) logic 33 by inverter 17. In either case, the data presented to ECC logic 33 is in its normal (non-inverted) form. ECC logic 33 can then calculate an ECC code based on the data pattern, and write both the data and its associated ECC code in memory 21.

[0023] When data is to be transferred in the opposite direction, both the data and associated ECC code can be read from memory and presented to ECC logic 33, which recalculates the ECC code based on the data it receives from memory 21. It can then compare the newly determined ECC code with the code that was retrieved from memory. Since a particular combination of bits will always generate the same ECC code, the retrieved code should match the newly calculated code. It they match, the data will be forwarded to inversion logic 17 for a data transfer as previously described, but in the opposite direction. As before, the data will be inverted by logic 17 or not inverted, depending on the number of active data lines. If the new and old ECC codes do not match, one or more bits of the data retrieved from memory have been corrupted and must be corrected. The nature of ECC algorithms is such that most memory errors can be detected and corrected in this manner. ECC logic 33 has the capability to perform this correction, and the corrected data can then be passed from ECC logic 33 to inverter 17 for transmission to inverter 16. The art of ECC algorithms and circuits is well known, and will not be discussed in further detail.

[0024] The decision to invert or not invert the data before presenting it to bus 18 comes from inverter decision logic 35, which informs inverter 14 of its decision over status line 19. Inverter 16 can then reinvert the inverted data it receives, or not invert the non-inverted data, depending on the status signal received from decision logic 35 over status line 19.

[0025] As described, ECC logic 33 performs various functions during both read and write operations, functions that consume a non-trivial amount of time that can noticeably affect bus latency. Inversion decision logic 35 also performs various functions during both read and write operations. The functions performed during a read operation consume a non-trivial amount of time that can affect bus latency. By placing the inversion decision logic 35 in parallel with ECC logic 33, and performing the ECC functions and inversion decision functions simultaneously, bus latency does not suffer from the accumulated delays of both ECC and inversion decision. Instead, only the longer of the two delays will affect bus latency. In general, ECC calculations take longer than inversion decision calculations, so the time to make the inversion decision at the transmitting end does not affect bus latency at all. For the inversion decision logic at the data receiving end, no calculations are needed. The inversion decision can simply be passed on from inversion status line 19 to the receiving inverter. This can take as little as one gate delay time, so it is not a significant factor in bus latency.

[0026] Although bus inversion operations for a memory read are similar to those for a memory write, there are some differences, so each is described separately in more detail below.

[0027] Write Operations

[0028] A bus requestor 10 can make a memory write request to memory 21 over bus 18. When requestor 10 presents the data to be written, inversion decision logic 14 can monitor the data lines to determine whether more than half of the data signals are active. If more than half are active, logic 14 can send a signal to inverter 16 to invert all the data signals. If less than half are active, logic 14 can send a signal to not invert all the data signals. In one embodiment, the invert and not-invert signals are simply opposite states of the same signal on an inverter control line. Inverter 16 can consist of a group of conditional inverter gates, one for each data line, each of which will invert the associated signal or not invert it, depending on the state of the received control signal. Whether inverted or not, the data can then be placed on bus 18 for transmission to inverter 17. At approximately the same time, inverter decision logic 14 can place a signal on status line 19 indicating whether the data was inverted or not. In one embodiment, the signal on status line 19 and the control signal from decision logic 14 to inverter 16 are the same signal.

[0029] When the data is received at inverter 17, all the data lines may be inverted by a group of conditional inverter gates, similar to the conditional inverter gates of inverter 16, except that these are inverting the data received from bus 18 rather than the data being transmitted on bus 18. Whether all the data signals are inverted or not can be determined by a control signal from inverter decision logic 35. This control signal can be determined by the status of the signal on status line 19, which was generated by decision logic 14 and is received by decision logic 35. In this manner, data which was initially inverted by inverter 16 will be reinverted by inverter 17 to restore the data to its original form, while data which was not inverted by inverter 16 will not be reinverted by inverter 17. In either case, the data presented to ECC logic 33 by inverter 17 is the same data that was originally presented to inverter 16 by bus requestor 10. Thus, the end-to-end transfer of data can be preserved as it would be without DBI, while the benefits of DBI to the system can still be employed.

[0030] Read Operations

[0031] A bus requestor 10 can make a memory read request to memory 21 over bus 18. When memory 21 presents the data to be read (transmitted back to requester 10), inversion decision logic 35 can monitor the data lines to determine whether more than half of the data signals are active. If more than half are active, logic 35 can send a signal to inverter 17 to invert all the data signals. If less than half are active, logic 35 can send a signal to not invert all the data signals. In one embodiment, the invert and not-invert signals are simply opposite states of the same signal on an inverter control line. Inverter 17 can consist of a group of conditional inverter gates, one for each data line, each of which will invert the associated signal or not invert it, depending on the state of the received control signal. Whether inverted or not, the data can then be placed on bus 18 for transmission to inverter 16. At approximately the same time, inverter decision logic 35 can place a signal on status line 19 indicating whether the data was inverted or not. In one embodiment, the signal on status line 19 and the control signal from decision logic 35 to inverter 17 are the same signal.

[0032] At the same time the data lines are being monitored by decision logic 35, the data and the associated ECC code that were read from memory 21 are presented to ECC logic 33. ECC logic 33 recalculates the ECC code based on the data it receives from memory 21. It then compares the newly-determined ECC code with the code that was retrieved from memory. Since a particular combination of bits will always generate the same ECC code, the retrieved code should match the newly-calculated code. If they match, the data is forwarded to inversion logic 17 for a data transfer over bus 18. As previously described, inverter 17 can invert or not invert the data, depending on the control signal from decision logic 35, which in turn depends on the number of active lines in the data.

[0033] When the data is received over bus 18 by inverter 16, inverter 16 can invert or not invert the data, depending on the state of the control signal from decision logic 14. The state of this control signal depends on the state of the status signal on line 19, which was generated by decision logic 35. Thus, inverter 16 will reinvert the data if that data was previously inverted by inverter 17. Inverter 16 will not invert the data if it was not previously inverted by inverter 17. This choice is based on the control signal from decision logic 14 which is in turn determined by the state of the signal on status line 19. In either case, the data presented to requestor 10 from inverter 16 will have the same form as the data presented to inverter 17 by ECC logic 33. Thus, the end-to-end transfer of data can be preserved as it would be without DBI, while the benefits of DBI to the system can still be employed.

[0034] However, if ECC logic 33 determines that the newly calculated ECC code and the old ECC code read from memory do not match, one or more bits of the data retrieved from memory has been corrupted and must be corrected. The nature of ECC algorithms is such that most memory errors can be detected and corrected in this manner. ECC logic 33 has the capability to perform this correction, and the corrected data can then be passed from ECC logic 33 to inverter 17 for transmission to inverter 16. However, the correction process requires additional time, thus adding to the delay before the corrected data is presented to inverter 17 by ECC logic 33.

[0035] As described, in a memory read operation, ECC logic 33 calculates a new ECC code and compares it with the old ECC code before passing the data on to inverter 17. In addition, sometimes ECC logic 33 may also have to calculate a data correction and correct the data before passing the data on. At the same time, inversion decision logic 35 performs its own calculation to determine if more than half the bits in the data are active, and generates a signal to invert or not invert the data depending on the results of the data bit calculation. By placing the inversion decision logic 35 in parallel with ECC logic 33, and performing the ECC functions and inversion decision functions simultaneously, bus latency does not suffer from the accumulated delays of both ECC and inversion decision. Instead, only the longer of the two delays will affect bus latency. In general, ECC calculations, even without data correction, take longer than inversion decision calculations, so the time to make the inversion decision when ECC is employed does not affect bus latency at all. However, in the event that the inversion calculation may take longer than the ECC calculation, both ECC logic 33 and decision logic 35 can present separate ‘ready’ signals to inverter 17 or to a separate bus transmission circuit, so that the data will not be placed on the bus until both ECC logic 33 and decision logic 35 have completed their work.

[0036] For inversion decision logic 14 at the data receiving end, no calculations are needed. The decision to reinvert the inverted data or not invert the non-inverted data can simply be passed on from inversion status line 19 to the receiving inverter 16. This can take as little as one gate delay time, so it is not a significant factor in bus latency.

[0037] FIG. 4 shows a more detailed view of the DBI and ECC logic at the memory portion of the system. ECC logic 33 includes two portions, ECC generator 42 and ECC detection/correction logic 43. When incoming data is received by ECC logic 33 from inverter 17, ECC generator 42 calculates an error correction code that is unique for the specific data pattern contained in the incoming data. Both the data and the associated code are then passed on to memory 21, where they are stored together in a designated memory location. When the data is later read from that memory location, the associated code is also read and both are presented to ECC detection/correction logic 43. A new ECC code is then calculated from the data just read from memory, typically by the same circuit that calculated the original code. The new code and old code are then compared by ECC detection/correction logic 43. Since the same data pattern will always generate the same ECC code, the old and new codes should be identical. If they are, the data from memory is considered valid and is passed on to inverter 17 for placement on bus 18. If the codes do not match, the data read from memory is assumed to be in error, in the form of one or more incorrect bits. The nature of ECC technology is such that most such errors can be isolated and corrected, based on the ECC code, the data pattern, and the ECC algorithms. ECC detection/correction logic 43 performs this correction, and then passes the corrected data on to inverter 17 for presentation to bus 18.

[0038] When read data is presented to ECC logic 33 from memory 21, the data is also monitored by inversion decision logic 35, which determines how many bits in the data are active. This determination can take several forms. In one embodiment, the number of bits is determined by bit counter 44, which adds up the number of active bits in the data. If the number exceeds a predetermined total, bit counter 44 indicates this to inversion control logic 45, which sends the appropriate ‘invert’ control signal to inverter 17. If the number does not exceed the predetermined total, bit counter 44 also indicates this to inversion control logic 45, which sends the appropriate ‘don't invert’ control signal to inverter 17. The predetermined total can be one-half of the total number of bits in the data.

[0039] Since the data being monitored by decision logic 35 is the data directly from memory, this data may contain errors that are later corrected by ECC logic 33. Thus, the data seen by decision logic 35 may contain fewer than one-half active data lines, while the data presented to the data bus may contain more, or vice-versa. This apparent conflict can be handled in several ways.

[0040] In one embodiment, the discrepancy is ignored. The data is inverted or not, based on the faulty data pattern retrieved from memory, which can result in more than one half of the data lines on bus 18 being active. However, regardless of the number of active lines, the data is still inverted at both ends or not inverted at both ends, so the correct data is still received by the requesting device. Since this condition should rarely occur, an occasional transfer involving more than one-half active lines should not be of concern.

[0041] In another embodiment, ECC logic 33 writes the corrected data back to the same memory location so that subsequent reads should retrieve the correct data. While doing so, this corrected data will be seen by decision logic 35, which can then properly compute whether or not the data contains more than one-half active lines.

[0042] Although the foregoing description is written in terms of data lines, the same principle can be applied to address lines, status lines, or any other types of lines. Also, multiple types of functional lines can be treated as a single group by the bus inversion scheme. Thus, a bus with a 32 address lines and 32 data lines can be treated as a single 64-bit wide bus by the bus inversion scheme if the address and data signals are transmitted at the same time.

[0043] Although only a single requestor 10 and a single memory 21 are shown in the figures, the invention can also be employed on a bus having more than two devices, in which each device has its own inverter and inversion decision logic.

[0044] Although the previous description of the bus describes all lines on the bus being inverted or not inverted as a group, the bus may be divided into smaller sections, with each section having its own independent bus inversion logic that operates independently of the other sections. For example, a 64-bit bus might have four 16-bit sections, with each section operating to limit the number of active lines to eight.

[0045] Although ECC has been described in the disclosure as the function to be operated in parallel with DBI, similar benefits can be obtained by operating DBI in parallel with other time-consuming bus functions.

[0046] The foregoing description is intended to be illustrative and not limiting. Variations will occur to those of skill in the art. Those variations are intended to be included in the invention, which is limited only by the spirit and scope of the appended claims.