A new voltage binning technique for yield improvement based on graph theory

In this paper, we propose a new voltage binning technique to improve yield. Voltage binning technique tries to assign different supply voltages to different chips in order to improve the yield. A novel valid voltage segment concept is proposed, which is determined by the timing and power constraints of chips. Then we develop a formulation to predict the maximum number of bins required under the uniform binning scheme from the distribution of length of valid supply voltage segment. With the new concept, an optimal binning scheme can be modeled as a set-cover problem. A greedy algorithm is developed to solve the set-cover problem in an incremental way. The new method is also extendable to deal with a range of working supply voltages for dynamic voltage scaling under different operation modes (like lower power and high performance modes). Experimental results on some benchmarks in 45nm technology show that the proposed method can correctly predict the upper bound on the number of bins required. The optimal binning scheme can lead to significant saving for the number of bins compared to the uniform one to achieve the same yield with very small CPU cost.