一種基于存儲的乘法器查找表的近似優化方法

　　萬晨雨，賀雅娟

　?。娮涌萍即髮W電子科學與工程學院，成都 610054)

　　摘要：本文提出了一種近似高輸入結果存儲(approximate-most-significant-multiple-storage, AMMS)的查找表(LUT)優化方法。該方法利用移位操作來替代部分存儲，并將存儲內容進行截位使存儲位寬縮減，對基于存儲的乘法器中的查找表進行了優化。該方法在一個mm位的乘法器中，可以將查找表的規?？s減至傳統存儲方法的1/4，并明顯改善乘法器的面積延遲積(ADP)，不過與此同時，該方法也因截位而產生了相對誤差，該誤差最大不超過2 -m 。此外，該方法會比傳統存儲方法多消耗一些額外的硬件，如多路復用器，移位邏輯以及編碼模塊。

　　0 引言

　　基于存儲的乘法器的工作原理是利用乘法系數(乘數)固定的特性，將所有輸入(被乘數)會產生的可能乘法結果預存儲在LUT中。如此，乘法運算過程轉換為了從LUT中讀取數據的過程，因此基于存儲的乘法器無論在運算速度還是動態功耗上相較于傳統的乘法器都有著顯著的優勢。雖然該類乘法器已被廣泛使用于移動無線通信等對電路工作速度與功耗均有一定要求的應用中，不過它也有著缺陷，即用于預存儲乘法結果的LUT所占用的面積資源過大，當輸入具有m比特時，該乘法器使用傳統存儲方式需要存儲的所有可能的乘法結果為2 m 種，所以當m較大時，乘法器所占用的LUT規模過大。

　　為了降低基于存儲結構中LUT的規模，前人已經做了不少研究。例如文獻[1]使用了(offset binarycoding) OBC的編碼方法，用簡單的加減操作來代替部分存儲數據，將分布式算法中需要在LUT中存儲的內積數量縮減至傳統存儲方式的1/2；文獻[2]采用了(antisymmetric product coding) APC的存儲方法，思想與文獻[1]類似，但是應用在了乘法器中，該方法同樣利用了額外的簡單加減運算來降低需要預存儲在LUT中的乘法結果數量，且也能夠將存儲數量降至傳統存儲方式的1/2；該作者還在文獻^[3]中提出了(odd-multiple-storage) OMS存儲方法，該方法只需存儲奇數輸入所產生的乘法結果，并通過將存儲結果移位的方式來恢復所有可能產生的乘法結果。

　　該方法同樣能夠將LUT中的存儲數量降至傳統存儲方式的1/2；文獻^[4]則更進一步地將OMS與APC存儲方法進行了修改與結合，使得LUT中的存儲數量更少，不過這樣雖然可以縮減LUT規模，可帶來了很多的額外硬件開銷。以上前人的各種優化方法都是著重于減少在LUT中的預存儲數量，更適用于精確的乘法計算，然而在一些不需要精確結果的實際應用中，其實可以利用近似存儲的方式來更進一步降低LUT規模，因為LUT規模不僅取決于其存儲數量，也取決于其存儲位寬。因此，本文采用近似截位存儲文獻^[5-6]與移位替代部分存儲結合的方式重新優化LUT，不僅能夠將LUT的存儲數量降至傳統存儲方法的1/2，同時也能夠將LUT的存儲位寬縮減。相較于前人的存儲方法，該方式在更進一步縮減LUT的規模時，并不會帶來過多的硬件消耗。

　　本文提出了一種名為近似高輸入結果存儲方法，下文都將稱其為AMMS方法。該方法能夠同時在LUT的存儲數量與存儲位寬上進行優化。在一個m×m比特的乘法器中，該方法能夠有效的將LUT規?？s減至傳統存儲方法的1/4，同時顯著的降低整體設計的ADP，且在乘法器的輸入位寬較大時，該方法能夠降低關鍵路徑延遲。由于方法本身引入了近似截位，因此該方法得到的近似計算結果相對正確結果而言會有一個不超過2 -m 的相對誤差。

　　1 AMMS方法的實現原理

　　1.1 AMMS方法的存儲方式

　　表1用輸入位寬為4比特的基于存儲的乘法器展示了AMMS方法的存儲方式，其中B為輸入，A為固定系數。該方法對于能夠由移位來相互得到的所有乘法結果，只存儲其中的最大值，例如A，2A，4A和8A都能夠由8A通過分別右移3，2，1位來得，因此只有8A才會被存儲到LUT中?；谶@種存儲方式，在除了0之外所有的乘法結果中，只會有一半的數量會被存儲到LUT中，這些被存儲的乘法結果也正是當輸入最高位為1時，較大的一半乘法結果。AMMS方法的其他乘法結果都是通過這些存儲結果右移來恢復的，因此該方法需要記錄恢復正確乘法結果所需要的具體右移比特數。表1中的取地址表示用來將LUT中存儲結果讀出的編碼地址，每個取地址都唯一對應一個存儲在LUT中的數，但是每個取地址可以對應多個輸入，不同輸入之間以恢復正確結果需要的右移數來區分。

　　1.2 AMMS方法的截位存儲策略與截位所帶來相對誤差的理論推導

　　設輸入B有m比特，固定系數A有n比特，則需要存儲的乘法結果數量為2 m-1 個，位寬為m+n比特。AMMS方法采取對乘法結果的低m位截斷的方處理式，只存儲高n位。在計算最終結果時，AMMS方法會對已截斷的低m位利用固定值進行補償。

　　設截位之前的某個正確乘法結果為Z i ，表達式如式(1)所示，需要存儲的內容為Xi，1 ≤ i ≤ 2 m-1 ，為n比特，被截位的部分為Y i ，為m比特。AMMS方法計算最終結果時采用的補償方式為：用所有被截斷的低m位的平均值來固定取代最終結果的低m位，的表達式如式(2)所示。該方法計算得到的近似結果Z i ’的表達式如式(3)所示。截位誤差error的表達式如式(4)所示。

　　由于在最壞情況時，絕對誤差|Y i -'?2 mi iZ X Y = ? + |的最大值不會超過2 m-1 ，而依據AMMS的較大半數存儲方式，Z i 的最小值不會小于2 n+m-1 ，因此根據式(4)，理論上的最大相對誤差不會大于2 -n ，且當乘法的固定系數的位寬很大時，該截位存儲策略所帶來的相對誤差會很小。

　　2 AMMS方法在乘法器上的實現結構

　　圖1使用了輸入位寬為4比特的基于存儲的乘法器來展示AMMS方法的實現結構，其中固定系數為A為n比特。

　　在該結構中，輸入B被分為兩部分，第一部分為最高位，主要作為部分模塊的判斷條件。第二部分為剩下的低3位，為各模塊的主要輸入。當最高位為1時，多路復用器會使用低3位直接作為取地址，反之，低3位將會進入編碼模塊來產生取地址。取地址經過地址譯碼模塊后可以將LUT中的存儲結果讀出，這些被讀出的結果會經過右移模塊處理來得到正確對應輸入的乘法結果。

　　移位控制模塊利用低3位來產生移位碼并以此控制右移模塊進行正確的右移操作。當最高位為1時，LUT中讀取的結果不需要移位，因此移位重置模塊會將移位碼置0。由于右移模塊輸出的結果為截位結果，因此還需要用'?2 mi iZ X Y = ? + 來固定補償被截去的低4位，并形成最終的計算結果。最后還需要判斷輸入B是否為全0，如果低三位為0，編碼模塊會產生一個低有效的清零信號傳遞至或非門，若這時最高位也為0，或非門將會產生一個高有效的信號，表示輸入為全0，該信號會傳遞到輸出重置模塊，并將最終結果清零。下面將詳細介紹部分模塊的工作原理與具體電路結構。

　　編碼模塊的具體電路結構如圖2所示，輸入B的低3位進入該模塊后會按照表1所示的編碼規則進行編碼輸出，該模塊具體的工作原理為：當輸入的最高位為0時，需要將輸入左移，直至新的最高位為1，此時得到左移后數據的新低3位即為編碼模塊的輸出，該模塊會將此輸出與原始輸入的低3位一一映射與進行邏輯優化，最后產生具體的電路結構。由于編碼過程的前提條件為輸入B的最高位為0，因此編碼是輸入必將左移至少一位，所以產生的新低3位的最低位必為0，即取地址第0位為0。

　　移位控制模塊的具體電路結構圖如圖3所示，移位碼由輸入B的低3位產生。移位控制模塊需要根據當前輸入的位寬來決定移位碼的位寬，因此，當輸入位寬為m比特時，移位碼需要[log 2 m] 比特的位寬來覆蓋表示所有可能移位的比特數。該模塊的工作原理為：當輸入最高位為0并在編碼模塊進行左移編碼時，會產生具體的左移比特數，這些比特數即作為移位碼為該模塊的輸出，該模塊會將移位碼與原始輸入低3位一一映射并進行邏輯優化，最終得到具體的硬件電路。

　　3 實驗結果與對比

　　本文將AMMS方法與傳統存儲方法以及OMS存儲方法分別應用于88比特和1616比特的乘法器中進行實驗，并根據實驗結果對比了這些乘法器的ADP。乘法器代碼由Verilog編寫使用了Design Compiler綜合，綜合過程中使用了0.18mm標準CMOS工藝庫，所得實驗結果如表2所示。

　　從表2中不難看出，本文所提出的AMMS方法相較于其他方法來說可以更進一步地縮減乘法器中的LUT規模并顯著地降低乘法器的ADP。當輸入位寬較小時，該方法由于引入了額外的硬件電路，因此在最大延遲上的對比上不如傳統的存儲方式，但隨著輸入位寬的增大，該方法的最大延遲特性會逐漸比傳統存儲方法更好。一方面是由于LUT規模的增大會導致額外硬件電路所產生的延遲的比重下降，另一方面是截位策略所帶來的延遲縮減會隨著LUT規模的增加而增加，足以抵消并超過額外硬件電路所產生的延遲。

　　4 結論

　　本文提出了一種新的AMMS方法來對基于存儲的乘法器中的LUT進行優化，該方法可以同時在LUT存儲數量與存儲位寬上進行優化，因此適用于不需要精確計算結果的應用。該方法在一個m×m比特的乘法器中，能夠將LUT規?？s減至傳統存儲方法的1/4，OMS存儲方法的1/2，并能夠顯著的降低整體設計的ADP。該方法相比于傳統的存儲方法會引入一些額外的硬件電路，并且帶來一定的截位相對誤差，不過該相對誤差不會超過2 -m ，且會隨著乘法固定系數位寬的增加而減小。

　　作者簡介：

　　萬晨雨 (1994-)，男，碩士研究生，研究方向：低功耗數字集成電路設計賀雅娟 (1978-)，女，副教授，研究方向：專用集成電路與系統、超低壓超低功耗數字集成電路設計等

　　本文來源于科技期刊《電子產品世界》2019年第7期第44頁，歡迎您寫論文時引用，并注明出處