一種基于存儲的乘法器查找表的近似優(yōu)化方法

　　萬(wàn)晨雨，賀雅娟

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

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

　　0 引言

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

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

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

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

　　1 AMMS方法的實(shí)現原理

　　1.1 AMMS方法的存儲方式

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

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

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

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

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

　　2 AMMS方法在乘法器上的實(shí)現結構

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

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

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

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

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

　　3 實(shí)驗結果與對比

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

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

　　4 結論

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

　　作者簡(jiǎn)介：

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

　　本文來(lái)源于科技期刊《電子產(chǎn)品世界》2019年第7期第44頁(yè)，歡迎您寫(xiě)論文時(shí)引用，并注明出處