對基於隨機比特序列運算的電路的自動綜合算法的研究

《對基於隨機比特序列運算的電路的自動綜合算法的研究》是依託上海交通大學，由錢煒慷擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：對基於隨機比特序列運算的電路的自動綜合算法的研究
• 項目類別：青年科學基金項目
• 項目負責人：錢煒慷
• 依託單位：上海交通大學

項目摘要

傳統的算數運算電路都是對二進制編碼的數據進行計算的。與二進制編碼不同的一種數據編碼方式是利用一串隨機比特序列來表示一個數值。在這種編碼方式下，複雜的算數運算可以通過很簡單的數字電路來實現。這種編碼相比於二進制編碼具有很強的容錯性。面對未來積體電路中器件的可靠性下降這一問題，設計基於隨機編碼的電路是一種潛在的解決方法。然而，現有的基於隨機編碼計算的電路都是人為的設計，尚沒有自傳動綜合這類電路的算法提出。本課題將對這類電路的自動綜合算法開展研究，針對組合邏輯電路與時序邏輯電路分別提出綜合方法。我們將把傳統的邏輯最佳化技術結合到機率性計算之中，開發出新的數據結構，並依此提出有效的算法來綜合最優的基於隨機編碼計算的組合邏輯電路。同時，本課題將對時序邏輯電路在隨機編碼下實現的計算進行分析，把握其輸入輸出間的規律，提出自動綜合電路的算法。我們將開發相應的計算機輔助設計軟體，為設計者設計這類電路提供便捷。

結題摘要

基於隨機比特序列的計算是一種非傳統的數字電路計算方式。它用一串隨機比特序列來編碼一個實數值。利用它設計的電路具有面積小和容錯性高的優勢。面向這種新的計算模式，需要新的自動綜合電路的方法。本項目對此開展了研究，主要分為以下5方面： 1. 如何綜合最優的產生目標機率值的組合邏輯電路。基於隨機比特序列進行計算的電路的輸入是以特定機率取1的隨機序列。而這種電路常用的設計是一種基於多路選擇器的架構。針對這種設計，我們利用其常數機率值輸入隨機比特序列並不需要相互獨立的特點，提出了一種方法可以綜合產生常數機率值隨機比特序列的電路。利用該算法綜合出的電路相比之前的最佳化設計可減少高達34%的面積。 2. 如何綜合最優的基於隨機比特序列進行計算的組合邏輯電路。我們首先提出了一種通用的基於組合邏輯電路的隨機計算電路的模型。這一基本的形式可以實現任意的多變數線性函式。在此基礎上，提出了如何將任意給定的計算目標映射到這一模型上，並如何綜合最優的電路設計。實驗表明利用該算法生成的電路面積相比之前的方法得到的結果減少高達70%。 3. 如何綜合併行的時序邏輯電路來實現任意目標函式。時序邏輯電路在輸入為隨機比特的情況下可以建模為一個馬爾科夫鏈。之前的設計方法利用它的穩態分布實現所需的計算。然而，為了使馬爾科夫鏈達到穩態分布，需要時序邏輯電路工作足夠多的時鐘周期。我們提出了一種方法可以利用馬爾科夫鏈的初始分布來實現目標函式，從而為通過並行來降低計算時間提供了可行性。實驗表明利用所提的這種方法可以很好地實現所需的計算並達到加速的目的。 4. 提出了一種通過線性變換來減小基於隨機比特計算電路面積的方法。在我們之前的研究中曾提出一種基於Bernstein多項式來綜合基於隨機比特序列計算的電路的方法。這一方法具有普適性。但是對於某些目標函式，其綜合出的電路面積較大。我們提出了採用線性變換來改變目標函式以達到減小電路面積的方法。實驗結果表明，在誤差相同的情況下，利用這一新的方法得到的電路的面積較之前的方法減小至少30%。 5. 針對二值分類套用，提出了對基於隨機比特計算的電路的加速方法。對於二值分類套用，它們往往是將最終的計算結果與一個閾值相比較，根據比較結果的大小來判斷是屬於哪一類。我們利用這類套用不需要較高精度計算結果的特點，提出了一種加速最終判斷的模組。實驗表明利用這一模組可以將計算速度提高4.86倍。