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

　　萬晨雨，賀雅娟

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

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

　　0 引言

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

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

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

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

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

　　1.1 AMMS方法的存儲方式

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

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

　　設(shè)輸入B有m比特，固定系數(shù)A有n比特，則需要存儲的乘法結(jié)果數(shù)量為2 m-1 個，位寬為m+n比特。AMMS方法采取對乘法結(jié)果的低m位截?cái)嗟姆教幚硎?，只存儲高n位。在計(jì)算最終結(jié)果時，AMMS方法會對已截?cái)嗟牡蚼位利用固定值進(jìn)行補(bǔ)償。

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

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

　　2 AMMS方法在乘法器上的實(shí)現(xiàn)結(jié)構(gòu)

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

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

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

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

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

　　3 實(shí)驗(yàn)結(jié)果與對比

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

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

　　4 結(jié)論

　　本文提出了一種新的AMMS方法來對基于存儲的乘法器中的LUT進(jìn)行優(yōu)化，該方法可以同時在LUT存儲數(shù)量與存儲位寬上進(jìn)行優(yōu)化，因此適用于不需要精確計(jì)算結(jié)果的應(yīng)用。該方法在一個m×m比特的乘法器中，能夠?qū)UT規(guī)?？s減至傳統(tǒng)存儲方法的1/4，OMS存儲方法的1/2，并能夠顯著的降低整體設(shè)計(jì)的ADP。該方法相比于傳統(tǒng)的存儲方法會引入一些額外的硬件電路，并且?guī)硪欢ǖ慕匚幌鄬φ`差，不過該相對誤差不會超過2 -m ，且會隨著乘法固定系數(shù)位寬的增加而減小。

　　作者簡介：

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

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