Error Correction and Crosstalk Avoidance Techniques in on-Chip VLSI Interconnects

Error Correction and Crosstalk Avoidance Techniques in on-Chip VLSI Interconnects

Hitlendra Pratap Singp, Rajesh Mehra2

1Dept. of ECE, MIET Group of Institutions, Meerut, India-250001

2Dept. of ECE, NITTTR, Chandigarh, India-160019

ABSTRACT

In On-Chip VLSI interconnects in deep and or ultra deep submicron technology due to close spacing of buses crosstalk, crosstalk delay, and signal integrity & transient malfunctions are projected to present critical challenges. In order to protect the On-chip interconnect infrastructures against these transient malfunctions and or to modify the data inputs single error correction and multiple error correction type joint crosstalk avoidance with double error correcting and simultaneous quadruple error detecting encoding & decoding techniques are proposed. These not only make the on-chip interconnect architecture tolerant against transient malfunctions, but also lower power dissipation.

KEYWORDS- Crosstalk, Signal Integrity, ECC, Interconnect.

1. INTRODUCTION

In deep submicron and ultra deep submicron on-chip VLSI Interconnects, the spacing among inter-wires decreases rapidly which results in large mutual capacitance. Due to which coupling capacitance between adjacent wires is increased, with negative effects on crosstalk, crosstalk delay, power, and signal integrity. The switching capacitance of a wire segment depends on the transitions on the wire and wires adjacent to it. Crosstalk avoidance codes can be used to reduce the effective coupling capacitance of a wire segment. The worst case switching capacitance of an inter-switch wire segment is given by (1+ )CL , where is the ratio of the coupling capacitance to the bulk capacitance and CL is the load capacitance, including the self capacitance of the wire. The purpose of a crosstalk avoidance code is to reduce the switching capacitance of the wire to

(1+ ) CL , where = 1, 2, or 3, and is called the maximum coupling. To make the system tolerant against transient errors other than crosstalk, in addition to crosstalk avoidance, it is needed to incorporate Error Correcting Codes (ECC). There are a few joint crosstalk avoidance codes (CAC) and single error correction (SEC) codes. The single error correcting codes are Duplicate-add-parity (DAP), Boundary Shift (BSC), and Modified Dual Rail (MDR) codes used to reduce the maximum coupling to =2 [8, 10].

The crosstalk avoidance codes reduces the coupling capacitances and hence results in minimization of crosstalk, crosstalk induced delay, power dissipation, and improvement in signal integrity. When crosstalk avoidance codes are combined with error detecting and correcting codes then signal integrity is improved.

Figure1. Delay on Global Interconnects of near term years [1, 11].

As the development of VLSI technology day by day, resistance capacitance (RC) delay on global interconnect increases inversely with scaling compared with gate delay, so delay on long interconnects is a critical and now dominating the clock cycle of future VLSI systems. The anticipated RC delay in near-term years of global Cu intermediate wires of 1-mm length, according to the

International Technology Roadmap for Semiconductors (ITRS2007) is shown in Figure 1. In 2009, global wire delay went into a warning state, and the solutions for global delay in 2011 are still unknown. Meanwhile, continuously shrinking wire widths demand an increasing height/width ratio to constrain wire resistance. This in turn causes the coupled capacitance among wires to grow rapidly, resulting in serious crosstalk [1, 11].

1. SINGLE ERROR CORRECTION CODES

   1.1 DUPLICATE ADD PARITY (DAP)

   The crosstalk is avoided by using DAP in which data bit lines are duplicated, which reduces the worst case capacitance to Cs + 2Cc .In addition a parity bit is added to correct single errors. The encoder for DAP is shown in Figure 2, it is simple and consisting of only 3 XOR gates which generate the parity bit. The decoder is shown in Figure 3, it consists of 4 XOR gates to detect errors and a multiplexer to select the error-free data bits [13, 15].

   Figure 2. DAP Encoder [13, 15].

   Figure 3. DAP Decoder [13, 15].

   1. MODIFIED DUAL RAIL (MDR)

      Modified dual rail encoding and decoding is similar to duplicate add parity coding method. The modification is only in duplication of the parity bit in order to reduce the effect of crosstalk [13, 15].

   2. BOUNDARY SHIFT CODE (BSC)

      In Boundary Shift Codes, two important definitions must be discussed. First is the invalid transition, which represents a transition from one codeword to another so that adjacent bits changed in opposite directions, which results in the worst case coupling capacitance. For example, code 01100011 and code 11011010 would be an invalid transition. A code is self-shielding if it can avoid invalid transitions. In second definition the dependent boundary is the place where two adjacent bits differ and are denoted by the leftmost bit position the codeword, for example the code 11001110 and 01100111 are having dependent boundary of (2,4,7) and (1,3,5) respectively. The BSC is based on the fact that no overlapping dependent boundaries sets form an invalid transition and fact that one bit circular shift converts the code with odd dependent boundary to code with even dependent boundary and vice versa so by alternation self shielding codes between the codes is generated. The logical diagram of BSC encoder is shown in Figure 4 is used to duplicate the data word even dependent boundary and then to send the duplicated codeword along with the parity bit and the clock signal. On the occurrence of next clock cycle, the next codeword with parity bit circulated is sent. In the last, the transmitted data is a self-shielded codeword. The decoder is similar to the DAP decoder with additional multiplexer array to generate the non- circulated codeword [4, 11].

      Figure 4. BSC Encoder [4, 12].

      Figure 5. BSC Decoder [4, 12].

   3. DUPLICATE ADD PARITY BUS INVERT (DAPBI)

   The DAPBI is the combination of DAP code with low power property. Bus invert refers to invert the codeword if the current data word differs from the previous data word in more than half the number of bits. This is shown in Figure 5, DAPBI is realized by DAP combined with a bus invert module. The low power property of DAPBI is due to reducing the transition activity on the data bus [16].

   Figure 6. DAPBI Encoder-Decoder [16].

2. JOINT CROSSTALK AVOIDANCE AND DOUBLE ERROR CORRECTION CODE (JCADECC)

Error correction code is used to achieve efficiency in energy for on-chip buses. ECC involves mapping of k data bits to be transmitted on the bus to n bit code which results in an (n, k) code having a code rate of k/n. Therefore, ECC encoder adds m or n-k extra parity or check bits in order to obtain codewords belonging to a code space with a minimum Hamming distance. Error control is possible if the Hamming distance between any two codewords is greater than one. Hamming coding provides a linear and

systematic ECCs as a few redundant bits are appended to the input to generate the codewords. Various inductive crosstalk avoidance code (CAC) can be combined with ECC to form a unified coding approach to minimize delay and DSM noise in interconnects. Inductive crosstalk avoidance codes like BI, OEBI, PBI and OEPBI involve nonlinear and disruptive mapping from data bits to codewords. So, in a joint coding framework, these codes need to be the outermost code in the framework and linar ECC like Hamming codes follow CAC. Since Hamming codes are systematic, it will generate some parity bits, which are appended to crosstalk avoidance codewords. These additional parity bits need to be encoded again for crosstalk avoidance and a linear crosstalk avoidance coding is used for this purpose. Figure 6 illustrates a joint coding framework for an on-chip RLC coupled interconnects [8, 9, 10, 12].

Figure 7. Joint Crosstalk Avoidance Coding Frame Work [9, 12]

1. JCADECC ENCODER

   The encoding scheme for the Double-error Correction coupled with crosstalk avoidance in JCADECC is a combination of Hamming encoding followed by DAP or BSC. This is illustrated in Figure 7 in which the 32-bit word is encoded by a standard (38, 32) shortened single error correcting Hamming code which is created by deleting 25 information bits from the standard (63, 57) Hamming code. This is followed by Hamming encoding in which the flit is encoded by either Duplicate-Add-Parity (DAP) or Boundary- Shift-Code (BSC) scheme, which duplicates each bit to produce two copies, and adds a parity bit calculated from one Hamming copy. This provides crosstalk avoidance capability to the overall scheme. The additional parity bit is a part of DAP or BSC codes which allows energy-efficient decoding. The logical diagram of the encoder is shown in Figure 6 [8, 10].

   Figure 6. JCADECC Encoder [8, 10]

2. JCADECC DECODER

The decoding can be done in the following way

i) The parity bits of the individual Hamming copies are calculated and compared with the sent parity. ii) If these two parities obtained in step (i) differ, then the copy whose parity matches with the transmitted parity is selected as the output copy of the first stage.

iii) If the two parities are equal, then any one copy is sent forward for syndrome detection; if the syndrome obtained for this copy is zero then it is selected as the output of the first stage. Otherwise, the alternate copy is selected. iv) The output of the first stage is sent for (38, 32) single error correcting Hamming decoding, finally producing the decoded output of the JCADECC scheme. The logical diagram of the JCADECC is shown in figure [8, 10].

Figure 7. JCADECC Decoder [10].

1. JOINT CROSSTALK AVOIDANCE AND TRIPLE CORRECTION CODE

   Due to aggressive scaling transient errors creates devices in DSM technology more vulnerable. Therefore, higher order error correcting codes along with multiple error corrections are required in which crosstalk avoidance is combined with triple error correction to avoid transient malfunctions [8].

   1. JCATCC ENCODER

      If the original information or data word consist of 32 bits. It is then after encoding with a single error correction (38, 32) shortened, Hamming code of 38 bit is generated in which 6-bits are for parity bits. Now duplicating all the 38 bits results in 76 bits code and then addition of the parity bit that is EX-OR of all the 38bits results in 77 bits, Hamming code. Therefore, for an unencoded 32 bit wide flit, JCATCC is a (77, 32) coding method. The Hamming distance of the (38, 32) SEC Hamming codes is 3. After duplication process Hamming distance increases to six and addition of an overall parity bit makes the final minimum Hamming distance between the codewords to be seven. Hence, triple- error correction is enabled. The duplication is used to avoid opposite bit transitions in adjacent wires so that the worst case transition of a bit pattern from 101 to 010 and vice versa can be avoided [8].

   2. JCATCC DECODER

      The decoder for JCATCC Encoder requires syndrome computation on the two copies and comparisons of the transmitted overall parity bit with the locally generated parities recomputed at the decoder from each individual copy [8].

2. SIMULTANEOUS TRIPLE-ERROR CORRECTION AND QUADRUPLE- ERROR DETECTION

   After modification in JCATCC scheme simultaneous triple-error correction and quadruple-error detection to detect all uncorrectable error patterns results. Thus, the JCATCC and Simultaneous quadruple-error- detection code JCATCC -SQED can correct up to all three-error patterns on the fly as well as detect all four-error patterns that cannot be corrected by the JCATCC scheme alone [8].

   1. JCATCC SQED ENCODER

      The development of encoder requires the Hsiao single error correction and double error detection code of an appropriate size to achieve simultaneous triple-error correction and quadruple-error detection. In this, the original information bits are first now encoded flit contains two Hsiao single error correction double error detection copies. The joint crosstalk avoidance and triple error correction simultaneous quadruple error detection scheme achieves simultaneous triple-error correction and quadruple-error detection, as it differs from the joint triple error correction only in appending a second copy of the last parity bit of the Hsiao single error correction double error detection code to the joint triple error correction bits, preserving all the bits necessary for the joint triple error correction decoding scheme [8].

   2. JCATCC SQED DECODER

      The decoder requires setting a flag whenever it encounters a four-error pattern that cannot be corrected by the triple-error-correcting algorithm. When each of the two Hsiao single error correction and double error detection encoded copies have double errors, then the syndromes of both copies will be able to detect the presence of such double error patterns. When there is a single error in one copy and a triple error in the other, the triple-error pattern in the Hsiao single error correction double error detection code will always give an odd-weight syndrome. The syndromes are used to decode each individual copy. If both decoded copies do not match then there must have been a triple error in one of the copies, indicating an overall quadruple error pattern. The only other possibility is when there are four errors in one copy and none in the other. In that case, the syndrome of the erroneous copy can be either zero, if the errors make it another Hsiao codeword, or nonzero. If it is zero then the copies will be different indicating a quadruple error pattern. If the syndrome of the erroneous copy is nonzero then the joint crosstalk avoidance and triple error correction- decoding algorithm will be able to select the correct copy. The joint crosstalk avoidance and triple error correction simultaneous quadruple error detection scheme simultaneously corrects triple errors and detects quadruple error patterns with additional hardware as compared to the Joint triple error correction scheme alone. The result of the triple-error correction has to be discarded if a quadruple-error pattern is detected, because that result may be

      inaccurate if there is a quadruple error pattern in the flit [8].

3. CONCLUSION

   DAP, MDR, DAPBI, and BSC are all avoids crosstalk along with single error correction in on-chip DSM technology VLSI interconnects. These techniques can also be used for low energy consumption along with reduction in transient malfunctions to improve signal integrity. JCADECC, JCATCC, and JCATCC-SQED avoid crosstalk with multiple error correction capability. These multiple error correction-coding techniques are used in network on-chip fabric. Network on-chip methodology used for integrating a very high number of intellectual property (IP) cores in a single chip. Network on-chip can be incorporated multicore SoC. Because of aggressive scaling network on-chip architectures are exposed to multiple source of transient errors. By incorporating error control coding transients malfunctions can be minimized and hence reduction in energy dissipation. JCATCC, and JCATCC-SQED are much more energy efficient along with tolerance in higher transient errors.

4. ACKNOWLEDGMENT

   The authors would like to thanks to Dr. S.B.L Sachan, Professor and Head Electronics & Commnication Engineering Department, NITTTR, Chandigarh for constant encouragement and guidance during this research work.

5. REFERENCES

1. Semiconductor Industry Association, The international technology roadmap for semiconductors, 2007.

2. S. R. Sridhara and N. R. Shanbhag, Coding for system-on-chip networks: A unified framework, IEEE Trans. Very Large Scale Integr.(VLSI) Syst., vol. 13, no. 6, Jun. 2005, pp. 655667.

3. P. P. Sotiriadis and A. P. Chandrakasan, A bus energy model for deep submicron technology, IEEE Trans. Very Large Scale Integr. (VLSI)Syst., vol. 10, no. 3, Jun. 2002, pp. 341350.

4. K. N. Patel and I. L. Markov, Error-correction and crosstalk avoidance in DSM busses, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 12, no. 10, Oct. 2004, pp. 10761080.

5. L. Benini and G. De Micheli, Networks on chips: A new SOC paradigm, IEEE Comput., vol. 35, no. 1, Jan. 2002, pp. 7078.

6. S.Vangal, An 80-tile 1.28TFLOPS network-on-chip in 65nmCMOS, in Proc. IEEE Int. Solid-State Circuits Conf., Feb. 2007, pp. 98589.

7. S. Kundu, S. T. Zachariah, Y. Chang, and C. Tirumurti, On modeling crosstalk faults, IEEE Trans. Comput.- Aided Des. Integr. Circuits Syst., vol. 24, no. 12, Dec. 2005, pp. 19091915.

8. A. Ganguly, P. P. Pande, and B. Belzer, Crosstalk aware channel coding schemes for energy efficient and reliable NOC interconnects, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 17, no. 11, Nov. 2009, pp. 16261639.

9. S. R. Sridhara, G. Balamurugan, and N. R. Shanbhag, Joint equalization and coding for on-chip bus communication, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 3, Mar. 2008, pp. 314318.

10. Amlan Ganguly, Partha Pratim Pande, Benjamin Belzer1, Cristian Grecu, Addressing Signal Integrity in Networks on Chip Interconnects through rosstalk-Aware Double Error Correction Coding, IEEE Computer Society Annual Symposium on VLSI(ISVLSI'07), 2007, pp. 317 324.

11. Ying Zhang, Huawei Li, Yinghua Min, and Xiaowei Li, Selected Transition Time Adjustment for Tolerating Crosstalk Effects on Network-on-Chip Interconnects , IEEE Transactions on Very Large Scale Integration (VLSI) Systems, VOL. 19, NO. 10, October 2011, pp. 1787-1800.

12. Rahaman M.S and Chowdhury M.H., Crosstalk Avoidance and Error-Correction Coding for Coupled RLC Interconnects, IEEE Conference on IEEE Symposium on Circuits and Systems 2009, pp 141-144.

13. A.Ganguly, P.P.Pande, B.Belzer and C.Grecu."Design of Low Power & Reliable Networks on Chip Through Joint Crosstalk Avoidance and Multiple Error Correction Coding." J. Electron. Test. 24, June 2008, pp. 1-3.

14. P.P.Pande, H.Zhu, A.Ganguly and C.Grecu. "Crosstalk-aware Energy Reduction in NoC Communication Fabrics," SOC Conference, 2006 IEEE International, 24- 27 Sept. 2006, pp.225-228.

15. P.P.Pande, A.Ganguly, B.Feero, B.Belzer and C.Grecu. "Design of Low power & Reliable Networks on Chip through joint crosstalk avoidance and forward error correction coding," dft, 21st IEEE International Symposium on Defect and Fault- Tolerance in VLSI Systems (DFT'06), 2006, pp.466-476.

16. S.R.Sridhara and N.R.Shanbhag. "Coding for system- on-chip networks: a unified framework," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol.13, no.6, pp. 655-667, June 2005.

17. J.-M.Philippe, S.Pillement and O.Sentieys. "Area efficient temporal coding schemes for reducing crosstalk effects," Quality Electronic Design, 2006. ISQED '06. 7th International Symposium on 27-29 March 2006 pp.6 pp.- 339.

18. D.Rossi, C.Metra, A.K.Nieuwland and A.Katoch. "Exploiting ECC redundancy to minimize crosstalk impact," Design & Test of Computers, IEEE, vol.22, no.1, Jan.-Feb. 2005, pp. 59-70.

19. D.Rossi, P.Angelini and C.Metra, "Configurable Error Control Scheme for NoC Signal Integrity," iolts, 13th IEEE International On-Line Testing Symposium (IOLTS 2007), 2007, pp.43-48.