三值光學(xué)計(jì)算機(jī)的多數(shù)位MSD乘法算法及運(yùn)算分析＊

李 梅

（西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安710021）

乘法運(yùn)算是數(shù)字計(jì)算中非常重要的算術(shù)操作，在計(jì)算機(jī)上主要通過基本的加法運(yùn)算實(shí)現(xiàn)，光具有空間巨并行性、自由空間互連能力和無高頻輻射衰減特性，很多學(xué)者嘗試用光學(xué)方法實(shí)現(xiàn)加法，文獻(xiàn)［1-2］用光學(xué)方法模擬電子計(jì)算機(jī)實(shí)現(xiàn)加法；文獻(xiàn)［3-4］采用光學(xué)并行邏輯實(shí)現(xiàn)按位片做并行加法的全加器；文獻(xiàn)［5-6］使用SEED陣列實(shí)現(xiàn)先行進(jìn)位加法器．三值光學(xué)計(jì)算機(jī)［7］的核心構(gòu)成器件是三值邏輯光學(xué)處理器，其采用液晶陣列和偏振片組合實(shí)現(xiàn)，擁有104以上量級(jí)的處理像素即數(shù)據(jù)位數(shù)，具有位數(shù)眾多、邏輯運(yùn)算可重構(gòu)以及實(shí)現(xiàn)三值運(yùn)算的特點(diǎn)，因此很多研究者考慮利用該處理器實(shí)現(xiàn)位數(shù)巨大 的 無 進(jìn) 位 加 法［8-9］．改 良 符 號(hào) 數(shù) （Modified Signed-Digit，MSD）系統(tǒng)［10］是符號(hào)數(shù)系統(tǒng)的子集，基于MSD編碼的加法沒有進(jìn)位傳播，算法的復(fù)雜度與加法操作數(shù)的位數(shù)無關(guān)，這些特性有利于充分發(fā)揮光的并行性，特別適合用光學(xué)方法實(shí)現(xiàn)［11］．因此研究人員在探索如何用三值光學(xué)計(jì)算機(jī)實(shí)現(xiàn)加法時(shí)，找出更適合三值光學(xué)計(jì)算機(jī)特點(diǎn)的數(shù)值表示和編碼方式，設(shè)計(jì)出充分發(fā)揮三值光計(jì)算機(jī)優(yōu)勢的算法．因?yàn)槔霉鈱W(xué)方法實(shí)現(xiàn)加法運(yùn)算能夠充分發(fā)揮光計(jì)算的二維并行處理信息的特性，所以光計(jì)算在降低運(yùn)算復(fù)雜度方面具有顯著優(yōu)勢．文中在三值光計(jì)算機(jī)上實(shí)現(xiàn)大數(shù)位MSD加法的基礎(chǔ)上，研究用于三值光學(xué)計(jì)算機(jī)光學(xué)邏輯處理器的MSD乘法運(yùn)算，提出完成n位數(shù)MSD乘法的算法，進(jìn)行算法分析，提出改進(jìn)方法，為三值光學(xué)計(jì)算機(jī)在數(shù)值運(yùn)算方面的進(jìn)一步應(yīng)用提供了MSD乘法運(yùn)算的理論基礎(chǔ)．

1 MSD加法算法

設(shè)被加數(shù)X和加數(shù)Y的MSD表示分別為X＝xn-1，…，xi，…，x0，Y ＝y(tǒng)n-1，…，yi，…，y0，他們之和的 MSD表示為S＝sn，…，si，…，s0．MSD加法運(yùn)算步驟為

① 對位．若X與Y的位數(shù)不相等，則在位數(shù)較少者的最高位前補(bǔ)若干個(gè)0以使X與Y的位數(shù)相等．

⑦ 補(bǔ)0．令t′0＝0，w′n＋1＝0．

⑧ 計(jì)算t′i＋w′iT→si（i＝0，1，2，…，n＋1），即對相應(yīng)的每一位t′i和w′i進(jìn)行T變換，得到X與Y的MSD加法和S的每一位si．

可以看出兩個(gè)n位的MSD數(shù)相加的結(jié)果是一個(gè)n＋2位MSD數(shù)，而且所需的步數(shù)與兩操作數(shù)的位數(shù)無關(guān)，MSD加法可以克服兩高位數(shù)相加時(shí)由于進(jìn)位傳播導(dǎo)致的計(jì)算速度瓶頸問題．

2 三值光學(xué)計(jì)算機(jī)的MSD乘法算法

2．1 改進(jìn)的MSD加法算法

使用MSD加法算法實(shí)現(xiàn)加法時(shí)，首先把兩個(gè)加法操作數(shù)的每一個(gè)數(shù)據(jù)位轉(zhuǎn)換成中間數(shù)，然后對中間利用數(shù)倍于數(shù)據(jù)位數(shù)的運(yùn)算器位數(shù)和許多邏輯運(yùn)算器進(jìn)行多次邏輯運(yùn)算，最終完成運(yùn)算，導(dǎo)致以前各種實(shí)現(xiàn)MSD加法的方法通用性較差．三值光學(xué)計(jì)算機(jī)的位數(shù)多，而且三值邏輯光學(xué)處理器具有可重構(gòu)特性，隨時(shí)把處理器的任意區(qū)域構(gòu)造成需要的二元三值邏輯運(yùn)算器，這使得三值光計(jì)算機(jī)更適合處理數(shù)據(jù)位之間沒有關(guān)聯(lián)的邏輯運(yùn)算，因此在三值光計(jì)算機(jī)上實(shí)現(xiàn)MSD加法既能發(fā)揮三值光計(jì)算機(jī)位數(shù)多、易于完成邏輯運(yùn)算的優(yōu)點(diǎn)，又能彌補(bǔ)MSD加法的不足；較以往的實(shí)現(xiàn)方法而言，三值光計(jì)算機(jī)實(shí)現(xiàn)MSD加法的方法的通用性得到提高．

2．2 n位MSD乘法算法

設(shè)A＝an-1…a1a0，B＝bn-1…b1b0．它們的乘積P＝p2n-1…p1p0是一個(gè)2n位的二進(jìn)制數(shù)．計(jì)算A與B相乘時(shí)，先初始化乘積P為0，然后從最低位向最高位依次檢查乘數(shù)B的每一位：若b0為1，則乘積P加上an-1…a1a0；若b0為0，則乘積P加上0．若b1為1，則an-1…a1a0向左移動(dòng)一位，加入乘積P；若b1為0，則乘積P加上0．依此類推，若bi為1，則an-1…a1a0向左移動(dòng)i位，即把a(bǔ)n-1…a1a0加入乘積P；若bi為0，則乘積P加0．可得

式中：A×bi為第i個(gè)部分積，用si表示；si×2i為第i個(gè)和數(shù)項(xiàng)，用p（i）表示．

2．2．1 生成和數(shù)項(xiàng)p（i）

和數(shù)項(xiàng)p（i）是被乘數(shù)A向左移動(dòng)i位與乘數(shù)B的第i位bi相乘后得到的結(jié)果，分為兩步完成為

① 生成部分積si．兩個(gè)1位數(shù)的MSD乘法的運(yùn)算規(guī)則為T變換直值，可以看出1位MSD乘法不產(chǎn)生進(jìn)位，因此可把它看作二元三值邏輯變換，稱為MSD數(shù)的M變換，記為M，M變換的直值為

2）生成和數(shù)項(xiàng)p（i）．給si后面補(bǔ)充i個(gè)0即可得到和數(shù)項(xiàng)p（i）．可作并行計(jì)算過程同時(shí)執(zhí)行得到p（i）（i＝0，1，2，…，n-1）．

2．2．2 累加和數(shù)項(xiàng)p（i）

設(shè)兩個(gè)n位數(shù)相乘，乘積P是個(gè)2n位數(shù)，由n個(gè)和數(shù)項(xiàng)p（i）相加而成，和數(shù)項(xiàng)p（i）均不超過2n-1位．

累加和數(shù)項(xiàng)MSD加法完成．若只有一個(gè)加法器，那么必須在這個(gè)加法器經(jīng)過n-1次的串行計(jì)算才能得到最后的乘積P．初始化乘積P為0，即P ＝p（0），依次對 P 加 上p（1）、p（2）、p（3），…，p（n-1），因此要加n-1次，顯然這樣非常耗時(shí)．為了提高乘法的運(yùn)算速度，加快和數(shù)項(xiàng)的累加速度，引入數(shù)字運(yùn)算中的二叉樹乘法算法，算法步驟為

① 把由n個(gè)和數(shù)項(xiàng)p（i）構(gòu)成的n×2n的數(shù)字矩陣分成n／2對加法操作數(shù)，將相鄰的p（i）和p（i＋1）分配到一個(gè)MSD加法器上運(yùn)算，得到的結(jié)果稱為部分和．經(jīng)過對這n／2對和數(shù)項(xiàng)完成MSD加法，得到n／2個(gè)部分和；若n為偶數(shù)時(shí)需要n／2個(gè)MSD加法器；當(dāng)n為奇數(shù)時(shí)需要（n-1）／2個(gè) MSD加法器．

② 把步驟①產(chǎn)生的n／2個(gè)部分和看作n／4對加法操作數(shù)，完成MSD加法后得到n／4個(gè)部分和；若n／2為偶數(shù)時(shí)需要n／4個(gè)MSD加法器；當(dāng)n／2為奇數(shù)時(shí)需要（n／2-1）／2個(gè) MSD加法器．

③重復(fù)這個(gè)過程log2n步，直到得到一個(gè)輸出結(jié)果，也就是最后的積P．

由于每一步產(chǎn)生的輸出比前一步少1／2，該算法具有二叉樹結(jié)構(gòu)，和數(shù)項(xiàng)作為葉子節(jié)點(diǎn)，最后的積P是根節(jié)點(diǎn)．完成第一步需要n／2個(gè)MSD加法器，完成第二步需要n／4個(gè)MSD加法器，依此類推，完成最后一步需要1個(gè)MSD加法器，共計(jì)需要m＝n／2＋n／4＋…＋1＝n-1個(gè)加法器，且每步所需加法器的位數(shù)不同．三值光學(xué)計(jì)算機(jī)是巨位數(shù)計(jì)算機(jī)，其近千位的光學(xué)處理器實(shí)現(xiàn)了任意的拆分和重組，為了利用光學(xué)的并行處理和MSD加法的全并行性優(yōu)勢，假設(shè)三值光學(xué)處理器可以拆分為符合每一個(gè)MSD加法器的位數(shù)要求的n-1個(gè)MSD加法器，進(jìn)而利用二叉樹乘法算法實(shí)現(xiàn)向量矩陣乘法．

3 實(shí)例驗(yàn)證與分析

計(jì)算 MSD數(shù)A和B的乘積P．A＝ （14）10＝（1110）MSD，B ＝ （9）10＝ （101）MSD，部分積為

其中所填的Φ為補(bǔ)充的0．

累加和數(shù)項(xiàng)得

其運(yùn)算過程如圖1所示．圖1中最左邊是和數(shù)項(xiàng)p（i）構(gòu)成的n×2n的數(shù)字矩陣，其余部分為以二叉樹乘法算法對和數(shù)項(xiàng)累加直到得到最后的積P．

圖1 兩個(gè)4位MSD數(shù)相乘Fig．1 Multiplication of two 4-bit MSD numbers

在三值光學(xué)計(jì)算機(jī)上的運(yùn)行結(jié)果如圖2所示．

3．1 時(shí)間性能分析

兩個(gè)n位MSD數(shù)相乘的時(shí)間性能分析：

①采用全并行方式同時(shí)生成所有的部分積，這個(gè)過程的運(yùn)行時(shí)間相對運(yùn)算時(shí)間而言可以忽略不計(jì)；②采用二叉樹乘法算法對部分積進(jìn)行累加，共需要log2n步，每一步并行完成一次MSD加法，等于完成log2n個(gè)MSD加法的時(shí)間．

在MSD乘法算法中，“基本操作”指的是MSD加法．因此用二叉樹乘法算法實(shí)現(xiàn)MSD乘法的時(shí)間復(fù)雜度表示為O（log2n）．在僅有一個(gè)加法器的情形下，采用順序累加的方法實(shí)現(xiàn)MSD乘法需要完成n-1步MSD加法．因此，二叉樹乘法算法的時(shí)間性能可用式（2）的參數(shù)E表示為

參數(shù)E反映了二叉樹乘法算法的運(yùn)算效率，對于乘數(shù)的位數(shù)n的不同取值，E值的變化如圖3所示．由圖3可以看出，隨著乘數(shù)位數(shù)n的增大，E線性增大．例如當(dāng)n＝256時(shí)，E＝31．875．

圖2 運(yùn)行結(jié)果Fig．2 Operating results

圖3 MSD乘法算法的時(shí)間性能Fig．3 Time performance of MSD multiplication algorithm

3．2 MSD乘法的三值光學(xué)加法器利用率分析

二叉樹乘法算法能夠執(zhí)行并行操作，可提高乘法運(yùn)算速度，但不能充分利用所有的光學(xué)加法器．定義參數(shù)U表示所需加法操作的數(shù)目與可提供加法操作的最大數(shù)目的比值，U反映了系統(tǒng)中加法器的利用率．

在二叉樹乘法算法中，設(shè)有n／2個(gè)光學(xué)加法器，共執(zhí)行l(wèi)og2n 個(gè)步驟，則系統(tǒng)最大可完成n／2log2n 個(gè)加法操作．第一步使用了n／2個(gè)加法器，同時(shí)執(zhí)行n／2個(gè)加法；第二步使用了n／4個(gè)加法器，同時(shí)執(zhí)行n／4個(gè)加法；以此類推；第log2n步使用了1個(gè)加法器，執(zhí)行1個(gè)加法．一共需要執(zhí)行n／2＋n／4＋…＋1＝n-1個(gè)加法．因此，二叉樹乘法算法的并行加法器的利用率為

隨著n的增大，參數(shù)U的值是遞減的．從時(shí)間性能的分析可知，n越大的二叉樹乘法的時(shí)間性能越好，因此對于光處理器而言更適合處理n較大的乘法，但加法器利用率卻與n成反比，這將降低并行光學(xué)加法器運(yùn)行的吞吐量．為了提高U，應(yīng)充分利用光學(xué)處理器的資源，并行處理盡可能多的乘法，增加單位時(shí)間內(nèi)完成乘法的數(shù)量．

假設(shè)有n個(gè)加法器，則每一步最大可并行執(zhí)行n個(gè)加法．當(dāng)U＝1，并行處理n個(gè)乘法（設(shè)每個(gè)乘法的乘數(shù)位數(shù)為n）時(shí)，每個(gè)乘法均由n個(gè)和數(shù)項(xiàng)的加法構(gòu)成，這n個(gè)和數(shù)項(xiàng)通過二叉樹乘法算法進(jìn)行n-1次加法得到積；因此n個(gè)乘法由n2個(gè)和數(shù)項(xiàng)的加法構(gòu)成，通過二叉樹乘法算法進(jìn)行n（n-1）個(gè)次加法得到n個(gè)積．加法器利用率U＝1，則每一步都執(zhí)行n個(gè)加法．計(jì)算過程：① 用n個(gè)加法器對n2個(gè)和數(shù)項(xiàng)進(jìn)行兩兩相加操作，進(jìn)行 n2／2n ＝n／2 次并行相加，得到n2／2 個(gè)部分和；② 用n個(gè)加法器對n2／2個(gè)部分和進(jìn)行兩兩相加操作，進(jìn)行（n2／2）／2n ＝ n／4 次并行相加，得到n2／4 個(gè)部分和；③ 以此類推，用n個(gè)加法器對n2／2k-1個(gè)部分和進(jìn)行兩兩相加操作，進(jìn)行 （n2／2k-1）／2n ＝ n／2k次并行相加，得到n2／2k個(gè)部分和（k＝1，2，…，log2n）；④ 用n個(gè)加法器對2n個(gè)和數(shù)項(xiàng)進(jìn)行兩兩相加操作，進(jìn)行2n／2n＝1次并行相加，得到n個(gè)乘積．

從上述計(jì)算過程可以看出，完成所有n個(gè)乘法需n／2＋n／4＋…＋1＝n-1步并行相加．雖然每一個(gè)乘法都是采用二叉樹算法完成的，但是由于所有的乘積在最后一步得到，因此至少有一個(gè)乘法要經(jīng)過n-1步才能完成，這與單加法器的情形下，采用順序累加的方法實(shí)現(xiàn)乘法所需的時(shí)間延遲一樣，因此在U＝1的情況下并行處理n個(gè)乘法的時(shí)間性能并不理想．

為了提高光學(xué)加法器的利用率，要并行完成多個(gè)乘法；但如果U＝1，時(shí)間性能又會(huì)下降到最差的情況；因此需要做一些改進(jìn)，在保證乘法計(jì)算時(shí)間性能的同時(shí)，充分利用加法器，提高系統(tǒng)的計(jì)算吞吐量．利用二叉樹乘法算法實(shí)現(xiàn)乘法會(huì)導(dǎo)致光學(xué)加法器的利用率下降，這是由于加法器輸出結(jié)果的個(gè)數(shù)是輸入數(shù)據(jù)的一半，再以輸出作為輸入繼續(xù)相加，利用率就大大下降了，為此文中提出在二叉樹乘法算法兩兩相加的基礎(chǔ)上加入循環(huán)反饋．假設(shè)有n個(gè)加法器，完成n個(gè)乘法（設(shè)每個(gè)乘法的乘數(shù)位數(shù)為n），改進(jìn)后運(yùn)算過程：① 用n個(gè)加法器并行地對第一個(gè)乘法M1的n個(gè)和數(shù)項(xiàng)以及第二個(gè)乘法M2的n個(gè)和數(shù)項(xiàng)進(jìn)行兩兩相加操作，分別得到n／2和n／2個(gè)部分和；② 將得到的兩個(gè)n／2個(gè)部分和反饋到n／2個(gè)加法器的輸入端繼續(xù)求和，同時(shí)用剩余n／2個(gè)加法器對第三個(gè)乘法M3的n個(gè)和數(shù)項(xiàng)進(jìn)行兩兩求和．經(jīng)過這一步，分別得到n／4個(gè)、n／4個(gè)和n／2個(gè)部分和；③依此類推，經(jīng)過log2n步得到第一個(gè)乘法M1和第二個(gè)乘法M2的積，第三個(gè)乘法M3得到了2個(gè)部分和，…，第log2n＋1個(gè)乘法的n個(gè)和數(shù)項(xiàng)經(jīng)過兩兩相加得到n／2個(gè)部分和；④ 經(jīng)過log2n ＋1步得到第三個(gè)乘法M3的積，…，經(jīng)過log2n＋n-2步得到第n個(gè)乘法的積．改進(jìn)后光學(xué)加法器利用率為U ＝ （（n／2-1）＋（n／4-1）＋…＋1）／（nlog2n）．

4 結(jié)論

1）MSD乘法算法實(shí)現(xiàn)了n位數(shù)的乘法，用于三值光學(xué)計(jì)算機(jī)有效可行，得出每個(gè)乘法的時(shí)間延遲為執(zhí)行l(wèi)og2n個(gè)加法的時(shí)間，與二叉樹算法的時(shí)間延遲相同；時(shí)間復(fù)雜度從傳統(tǒng)乘法算法的O（n）降低到O（log2n），運(yùn)算速度得以提高．

2）MSD乘法算法提高了加法器的利用率．計(jì)算乘法M1和M2的過程中，加法器的利用率為1；之后直到開始計(jì)算第n個(gè)乘法Mn的每一步里，第一個(gè)加法器空閑不用，加法器利用率為（n-1）／n；計(jì)算乘法Mn的過程中，每一步使用的加法器是上一步的一半，且第一個(gè)加法器空閑不用，加法器利用率為U ＝ （（n／2-1）＋（n／4-1）＋．．．＋1）／（n log2n）．

［1］ 羅金平．基于符號(hào)替換邏輯的光學(xué)數(shù)字計(jì)算［J］．計(jì)算機(jī)科學(xué)，1996，23（1）：5．LUO Jin-ping．Optical Digital Computation Based on Symbol Substitution Logic ［J］．Computer Science，1996，23（1）：5．（in Chinese）

［2］ 李國強(qiáng)．負(fù)二進(jìn)制編碼的光學(xué)陣列化復(fù)數(shù)運(yùn)算［J］．光學(xué)學(xué)報(bào)，1995，15（10）：1419．LI Guo-qiang．Complex Number Computation Based on Negative Binary Coding Optical Array［J］．Acta Optica Sinica，1995，15（10）：1419．（in Chinese）

［3］ DRAKE B L，BOCKER R P，LASHER M E，et al．Photonic Computing Using the Modified Signed Digit Number Representation［J］．Opt Eng，1986，25：38．

［4］ ALAM M S．Efficient Binary Signed-digit Symbolic Arithmetic［J］．Opt Lett，1994，19：353．

［5］ ALAM M S，AHUJA Y，CHERRI A K，et al．Symmetrically Recoded Quaternary Signed-digit Arithmetic Using a Shared Content-addressable Memory［J］．Opt Eng，1996，35：1141．

［6］ LI G，LIU L，CHENG H，et al．Simplified Quaternary Signed-digit Arithmetic and Its Optical Implementation［J］．Opt Commun，1997，137：389．

［7］ JIN Yi，HE Hua-can，LU Yang-tian．Ternary Optical Computer Principle［J］．Science in China：Information Sciences，2003，46 （2）：145．

［8］ JIN Y，HE H C，AI L R．Lane of Parallel Through Carry in Ternary Optical Adder［J］．Science in China：Information Sciences，2005，48（1）：107．

［9］ WANG H J，ZHOU Y，JIN Y．Design and Implementation of 1Pixel Bit Reconfigurable Ternary Optical Processor［J］．Journal of Shanghai University，2011（15）：430．

［10］ HUANG H X，MASAHIDE I，TOYOHIKO Y．Modified Signed-digit Arithmetic Based on Redundant Bit Representation［J］．Applied Optics，1994，33（26）：6146．

［11］ 李梅，何華燦，金翊，等．一種實(shí)現(xiàn) MSD加法的光學(xué)方法［J］．光子學(xué)報(bào)，2010，39（6）：1053．LI Mei，HE Hua-can，JIN Yi，et al．An Optical Method for MSD Addition［J］．Acta Photonica Sinica，2010，39（6）：1053．（in Chinese）