A novel low overhead fault tolerant Kogge-Stone adder using adaptive clocking

Swaroop Ghosh, Patrick Ndai, Kaushik Roy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations


As the feature size of transistors gets smaller, fabricating them becomes challenging. Manufacturing process follows various corrective design-for-manufacturing (DFM) steps to avoid shorts/opens/bridges. However, it is not possible to completely eliminate the possibility of such defects. If spare units are not present to replace the defective parts, then such failures cause yield loss. In this paper, we present a fault tolerant technique to leverage the redundancy present in high speed regular circuits such as Kogge-Stone adder (KSA). Due to its regularity and speed, KSA is widely used in ALU design. In KSA, the carries are computed fast by computing them in parallel. Our technique is based on the fact that even and odd carries are mutually exclusive. Therefore, defect in even bit can only corrupt the even Sum outputs whereas the odd Sums are computed correctly (and vice versa). To efficiently utilize the above property of KSA in presence of defects, we perform addition in two- clock cycles. In cycle-1, one of the correct set of bits (even or odd) are computed and stored at output registers. In cycle-2, the operands are shifted by one bit and the remaining sets of bits (odd or even) are computed and stored. This allows us to tolerate the defect at the cost of throughput degradation while maintaining high frequency and yield. The proposed technique can tolerate any number of faults as long as they are confined to either even or odd bits (but not in both). Further, this technique is applicable for any type of fault model (stuck-at, bridging, complete opens/shorts). We performed simulations on 64-bit KSA using 180nm devices. The results indicate that the proposed technique incur less that 1% area overhead. Note that there is very little throughput degradation (<0.3%) for the fault-free adders. The proposed technique utilizes the existing scan flip-flops for storage and shifting operation to minimize the area/performance overhead. Finally, the proposed technique is used in a superscalar processor, whereby the faulty adder is assigned lower priority than fault-free adders to reduce the overall throughput degradation. Experiments performed using Simplescalar for a superscalar pipeline (with four integer adders) show throughput degradation of 0.5% in the presence of a single defective adder.

Original languageEnglish (US)
Title of host publicationDesign, Automation and Test in Europe, DATE 2008
Number of pages6
StatePublished - 2008
EventDesign, Automation and Test in Europe, DATE 2008 - Munich, Germany
Duration: Mar 10 2008Mar 14 2008

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
ISSN (Print)1530-1591


OtherDesign, Automation and Test in Europe, DATE 2008

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'A novel low overhead fault tolerant Kogge-Stone adder using adaptive clocking'. Together they form a unique fingerprint.

Cite this