Gulati, Kanupriya (2003-05). Computing leakage current distributions and determination of minimum leakage vectors for combinational designs. Master's Thesis. Thesis uri icon

abstract

  • Analyzing circuit leakage and minimizing leakage during the standby mode of oper- ation of a circuit are important problems faced during contemporary circuit design. Analysis of the leakage profiles of an implementation would enable a designer to select between several implementations in a leakage optimal way. Once such an im- plementation is selected, minimizing leakage during standby operation (by finding the minimum leakage state over all input vector states) allows further power reduc- tions. However, both these problems are NP-hard. Since leakage power is currently approaching about half the total circuit power, these two problems are of prime rel- evance. This thesis addresses these NP-hard problems. An Algebraic Decision Diagram (ADD) based approach to determine and implicitly represent the leakage value for all input vectors of a combinational circuit is presented. In its exact form, this technique can compute the leakage value of each input vector, by storing these leakage values implicitly in an ADD structure. To broaden the applicability of this technique, an approximate version of the algorithm is presented as well. The approximation is done by limiting the total number of discriminant nodes in any ADD. It is experimentally demonstrated that these approximate techniques produce results with quantifiable errors. In particular, it is shown that limiting the number of discriminants to a value between 12 and 16 is practical, allowing for good accuracy and lowered memory utilization. In addition, a heuristic approach to determine the input vector which minimizes leakage for a combinational design is presented. Approximate signal probabilities of internal nodes are used as a guide in finding the minimum leakage vector. Probabilistic heuristics are used to select the next gate to be processed, as well as to select the best state of the selected gate. A fast satisfiability solver is employed to ensure the consistency of the assignments that are made in this process. Experimental results indicate that this method has very low run-times, with excellent accuracy, compared to existing approaches.
  • Analyzing circuit leakage and minimizing leakage during the standby mode of oper-
    ation of a circuit are important problems faced during contemporary circuit design.
    Analysis of the leakage profiles of an implementation would enable a designer to
    select between several implementations in a leakage optimal way. Once such an im-
    plementation is selected, minimizing leakage during standby operation (by finding
    the minimum leakage state over all input vector states) allows further power reduc-
    tions. However, both these problems are NP-hard. Since leakage power is currently
    approaching about half the total circuit power, these two problems are of prime rel-
    evance.
    This thesis addresses these NP-hard problems. An Algebraic Decision Diagram
    (ADD) based approach to determine and implicitly represent the leakage value for all
    input vectors of a combinational circuit is presented. In its exact form, this technique
    can compute the leakage value of each input vector, by storing these leakage values
    implicitly in an ADD structure. To broaden the applicability of this technique, an
    approximate version of the algorithm is presented as well. The approximation is done
    by limiting the total number of discriminant nodes in any ADD. It is experimentally
    demonstrated that these approximate techniques produce results with quantifiable
    errors. In particular, it is shown that limiting the number of discriminants to a value between 12 and 16 is practical, allowing for good accuracy and lowered memory
    utilization.
    In addition, a heuristic approach to determine the input vector which minimizes
    leakage for a combinational design is presented. Approximate signal probabilities of
    internal nodes are used as a guide in finding the minimum leakage vector. Probabilistic
    heuristics are used to select the next gate to be processed, as well as to select the
    best state of the selected gate. A fast satisfiability solver is employed to ensure the
    consistency of the assignments that are made in this process. Experimental results
    indicate that this method has very low run-times, with excellent accuracy, compared
    to existing approaches.

publication date

  • May 2003