具機率性的布林邏輯電路的正確性分析與最佳化

A Scalable Approach to Correctness Analysis and Optimization for Probabilistic Boolean Circuits

俞政杉(Zheng-Shan Yu)

指導教授 ： 王俊堯

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

摘要

傳統上，我們希望一個電路能夠完全執行正確，沒有任何錯誤發生。然而，對於一些可容忍錯誤的應用，如：影像處理，100%的正確性也許不是必需的。一項有趣的研究指出，如果可以不追求100%的正確性，則可以在能量消耗上獲得大量的好處，此種電路稱為機率性布林邏輯電路。近年來，機率性布林邏輯電路已被提出，在開發最佳化的演算法之前，需要一個有效的方法來分析此種電路的正確性。本文中提出了一個統計的方法，可以快速且準確的分析出機率性布林邏輯函數的正確性。實驗結果顯示我們提出的方法平均上比運算完全正確答案的方法快了122倍，而且有很小的誤差。我們也提出了一個最佳化的方法來使用機率性布林邏輯電路，在使用固定數量的機率性邏輯閘時，我們的方法可以確保機率性邏輯電路保持較高的正確性。例如：C1355這的電路，當機率性邏輯閘的數量佔總邏輯閘數量的60%以下時，我們最佳化的方法可以讓電路維持相當高的正確性。

關鍵字

機率邏輯

並列摘要

Traditionally, we expect that the designs can be performed without errors. However, for error-resilience applications, e.g., image processing, 100% correctness is not a must. An interesting study reveals that if we do not pursue 100% correctness for the operations, the energy consumption would be significantly reduced. Recently, Probabilistic Boolean Circuits (PBCs) have been proposed. However, prior to developing the algorithms for PBC optimization, having an efficient method for correctness analysis is necessary. In this paper, we propose a statistical approach that efficiently and accurately evaluates the correctness of PBCs. The experimental results show that the proposed approach performs about 122 times faster than the golden result method on average with little correctness difference. We also propose an optimization strategy that assigns probabilistic gates with little correctness suffering, e.g., when the percentage of probabilistic gates in C1355 is <60%. Thus, the proposed approaches are very promising.

並列關鍵字

Probabilistic CMOS ； Probabilistic Boolean Circuit ； Correctness

參考文獻

[1] R. S. Asamwar et al., “Successive image interpolation using lifting scheme approach,” Journal of Computer Science, vol. 6, pp. 969-978, 2010.

Technical Report of Department of CS, Rice University, 2008.

[6] L. N. B. Chakrapani et al., “Probabilistic design: A survey of probabilistic CMOS technology and future directions for terascale IC design,” in VLSI-SoC: Research Trends in VLSI and Systems on Chip,, vol. 249, pp. 101-118, Springer Boston,

[7] S. C. Chang et al., “TAIR: testability analysis by implication reasoning,” IEEE Trans. Computer-Aided Design, vol. 19, pp. 152-160, 2000.

[9] M. R. Choudhury, et al., “Reliability analysis of logic circuits”, IEEE trans. on