利用線性規劃針對非線性多項式函數在隨機電路上之合成的研究

A Linear Programming Approach to Stochastic Circuits for Non-Linear Polynomial Functions

郭家堯(Guo, Chia Yao)

指導教授 ： 王俊堯

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

摘要

由於具有容忍錯誤的能力，隨機電路重新出現作為實作算術函數的一種替代方案。在最近的研究中，已經有許多對於多變數線性函數的合成方法被提出。但對於非線性函數而言，以往的做法是將其轉換為一些特殊的形式，再以處理線性函數之方式處理之。因此，變數之間關連性的資訊就在過程中遺失了，這些資訊在本論文中被稱為等價類（equivalence class）。在本論文中，我們利用等價類的資訊並提出一種基於線性規劃的方法以考慮全局的角度來合成非線性多項式函數。我們也提出了一種基於分解函數來快速提取出等價類之資訊的方法。與先前作法相比，我們的方法能夠產生較小的電路並且運算時間也比較短。

關鍵字

隨機性電路 ； 線性規劃 ； 邏輯電路合成

並列摘要

Stochastic circuits re-emerge as an alternative solution to implement arithmetic functions for its ability to tolerate errors. In recent researches, there have been many solutions to implement linear functions. For non-linear cases, they transform the non-linear functions to the linear functions in a special form and handle them as the linear cases. Hence, the information of the relation between variables, which is called equivalence classes (ECs) in this paper, is lost. In this paper, we exploit the EC and present a linear programming approach to synthesize non-linear polynomial functions from a global view. A fast decomposition-based approach to extract the information of EC is also proposed. Compared to the previous works, our approach generates much smaller circuits and runs faster.

並列關鍵字

stochastic circuits ； linear programing ； logic synthesis

參考文獻

2. A. Alaghi and J. P. Hayes, "A Spectral Transform Approach to Stochastic Circuits," ICCD, pp. 315-321, 2012.

3. A. Alaghi and J. P. Hayes, "Exploiting Correlation in Stochastic Circuit Design," ICCD, pp. 39-46, 2013.

4. A. Alaghi and J. P. Hayes, "Fast and accurate computation using stochastic circuits," DATE, pp. 1-4, 2014.

5. A. Alaghi, C. Li, and J. Hayes, "Stochastic circuits for real-time image-processing applications," DAC, pp. 1–6, 2013.

7. B. Brown and H. Card, "Stochastic neural computation II: Soft competitive learning," IEEE Transactions on Computers, vol. 50, no. 9, pp. 906–920, 2001.