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

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

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

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

　　0 引言

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

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

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

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

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

　　1.1 AMMS方法的存儲(chǔ)方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　4 結(jié)論

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

　　作者簡(jiǎn)介：

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

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