三值光学计算机的多数位MSD乘法算法及运算分析＊

李 梅

（西安工业大学 计算机科学与工程学院，西安710021）

乘法运算是数字计算中非常重要的算术操作，在计算机上主要通过基本的加法运算实现，光具有空间巨并行性、自由空间互连能力和无高频辐射衰减特性，很多学者尝试用光学方法实现加法，文献［1-2］用光学方法模拟电子计算机实现加法；文献［3-4］采用光学并行逻辑实现按位片做并行加法的全加器；文献［5-6］使用SEED阵列实现先行进位加法器．三值光学计算机［7］的核心构成器件是三值逻辑光学处理器，其采用液晶阵列和偏振片组合实现，拥有104以上量级的处理像素即数据位数，具有位数众多、逻辑运算可重构以及实现三值运算的特点，因此很多研究者考虑利用该处理器实现位数巨大 的 无 进 位 加 法［8-9］．改 良 符 号 数 （Modified Signed-Digit，MSD）系统［10］是符号数系统的子集，基于MSD编码的加法没有进位传播，算法的复杂度与加法操作数的位数无关，这些特性有利于充分发挥光的并行性，特别适合用光学方法实现［11］．因此研究人员在探索如何用三值光学计算机实现加法时，找出更适合三值光学计算机特点的数值表示和编码方式，设计出充分发挥三值光计算机优势的算法．因为利用光学方法实现加法运算能够充分发挥光计算的二维并行处理信息的特性，所以光计算在降低运算复杂度方面具有显著优势．文中在三值光计算机上实现大数位MSD加法的基础上，研究用于三值光学计算机光学逻辑处理器的MSD乘法运算，提出完成n位数MSD乘法的算法，进行算法分析，提出改进方法，为三值光学计算机在数值运算方面的进一步应用提供了MSD乘法运算的理论基础．

1 MSD加法算法

设被加数X和加数Y的MSD表示分别为X＝xn-1，…，xi，…，x0，Y ＝yn-1，…，yi，…，y0，他们之和的 MSD表示为S＝sn，…，si，…，s0．MSD加法运算步骤为

① 对位．若X与Y的位数不相等，则在位数较少者的最高位前补若干个0以使X与Y的位数相等．

⑦ 补0．令t′0＝0，w′n＋1＝0．

⑧ 计算t′i＋w′iT→si（i＝0，1，2，…，n＋1），即对相应的每一位t′i和w′i进行T变换，得到X与Y的MSD加法和S的每一位si．

可以看出两个n位的MSD数相加的结果是一个n＋2位MSD数，而且所需的步数与两操作数的位数无关，MSD加法可以克服两高位数相加时由于进位传播导致的计算速度瓶颈问题．

2 三值光学计算机的MSD乘法算法

2．1 改进的MSD加法算法

使用MSD加法算法实现加法时，首先把两个加法操作数的每一个数据位转换成中间数，然后对中间利用数倍于数据位数的运算器位数和许多逻辑运算器进行多次逻辑运算，最终完成运算，导致以前各种实现MSD加法的方法通用性较差．三值光学计算机的位数多，而且三值逻辑光学处理器具有可重构特性，随时把处理器的任意区域构造成需要的二元三值逻辑运算器，这使得三值光计算机更适合处理数据位之间没有关联的逻辑运算，因此在三值光计算机上实现MSD加法既能发挥三值光计算机位数多、易于完成逻辑运算的优点，又能弥补MSD加法的不足；较以往的实现方法而言，三值光计算机实现MSD加法的方法的通用性得到提高．

2．2 n位MSD乘法算法

设A＝an-1…a1a0，B＝bn-1…b1b0．它们的乘积P＝p2n-1…p1p0是一个2n位的二进制数．计算A与B相乘时，先初始化乘积P为0，然后从最低位向最高位依次检查乘数B的每一位：若b0为1，则乘积P加上an-1…a1a0；若b0为0，则乘积P加上0．若b1为1，则an-1…a1a0向左移动一位，加入乘积P；若b1为0，则乘积P加上0．依此类推，若bi为1，则an-1…a1a0向左移动i位，即把an-1…a1a0加入乘积P；若bi为0，则乘积P加0．可得

式中：A×bi为第i个部分积，用si表示；si×2i为第i个和数项，用p（i）表示．

2．2．1 生成和数项p（i）

和数项p（i）是被乘数A向左移动i位与乘数B的第i位bi相乘后得到的结果，分为两步完成为

① 生成部分积si．两个1位数的MSD乘法的运算规则为T变换直值，可以看出1位MSD乘法不产生进位，因此可把它看作二元三值逻辑变换，称为MSD数的M变换，记为M，M变换的直值为

2）生成和数项p（i）．给si后面补充i个0即可得到和数项p（i）．可作并行计算过程同时执行得到p（i）（i＝0，1，2，…，n-1）．

2．2．2 累加和数项p（i）

设两个n位数相乘，乘积P是个2n位数，由n个和数项p（i）相加而成，和数项p（i）均不超过2n-1位．

累加和数项MSD加法完成．若只有一个加法器，那么必须在这个加法器经过n-1次的串行计算才能得到最后的乘积P．初始化乘积P为0，即P ＝p（0），依次对 P 加 上p（1）、p（2）、p（3），…，p（n-1），因此要加n-1次，显然这样非常耗时．为了提高乘法的运算速度，加快和数项的累加速度，引入数字运算中的二叉树乘法算法，算法步骤为

① 把由n个和数项p（i）构成的n×2n的数字矩阵分成n／2对加法操作数，将相邻的p（i）和p（i＋1）分配到一个MSD加法器上运算，得到的结果称为部分和．经过对这n／2对和数项完成MSD加法，得到n／2个部分和；若n为偶数时需要n／2个MSD加法器；当n为奇数时需要（n-1）／2个 MSD加法器．

② 把步骤①产生的n／2个部分和看作n／4对加法操作数，完成MSD加法后得到n／4个部分和；若n／2为偶数时需要n／4个MSD加法器；当n／2为奇数时需要（n／2-1）／2个 MSD加法器．

③重复这个过程log2n步，直到得到一个输出结果，也就是最后的积P．

由于每一步产生的输出比前一步少1／2，该算法具有二叉树结构，和数项作为叶子节点，最后的积P是根节点．完成第一步需要n／2个MSD加法器，完成第二步需要n／4个MSD加法器，依此类推，完成最后一步需要1个MSD加法器，共计需要m＝n／2＋n／4＋…＋1＝n-1个加法器，且每步所需加法器的位数不同．三值光学计算机是巨位数计算机，其近千位的光学处理器实现了任意的拆分和重组，为了利用光学的并行处理和MSD加法的全并行性优势，假设三值光学处理器可以拆分为符合每一个MSD加法器的位数要求的n-1个MSD加法器，进而利用二叉树乘法算法实现向量矩阵乘法．

3 实例验证与分析

计算 MSD数A和B的乘积P．A＝ （14）10＝（1110）MSD，B ＝ （9）10＝ （101）MSD，部分积为

其中所填的Φ为补充的0．

累加和数项得

其运算过程如图1所示．图1中最左边是和数项p（i）构成的n×2n的数字矩阵，其余部分为以二叉树乘法算法对和数项累加直到得到最后的积P．

图1 两个4位MSD数相乘Fig．1 Multiplication of two 4-bit MSD numbers

在三值光学计算机上的运行结果如图2所示．

3．1 时间性能分析

两个n位MSD数相乘的时间性能分析：

①采用全并行方式同时生成所有的部分积，这个过程的运行时间相对运算时间而言可以忽略不计；②采用二叉树乘法算法对部分积进行累加，共需要log2n步，每一步并行完成一次MSD加法，等于完成log2n个MSD加法的时间．

在MSD乘法算法中，“基本操作”指的是MSD加法．因此用二叉树乘法算法实现MSD乘法的时间复杂度表示为O（log2n）．在仅有一个加法器的情形下，采用顺序累加的方法实现MSD乘法需要完成n-1步MSD加法．因此，二叉树乘法算法的时间性能可用式（2）的参数E表示为

参数E反映了二叉树乘法算法的运算效率，对于乘数的位数n的不同取值，E值的变化如图3所示．由图3可以看出，随着乘数位数n的增大，E线性增大．例如当n＝256时，E＝31．875．

图2 运行结果Fig．2 Operating results

图3 MSD乘法算法的时间性能Fig．3 Time performance of MSD multiplication algorithm

3．2 MSD乘法的三值光学加法器利用率分析

二叉树乘法算法能够执行并行操作，可提高乘法运算速度，但不能充分利用所有的光学加法器．定义参数U表示所需加法操作的数目与可提供加法操作的最大数目的比值，U反映了系统中加法器的利用率．

在二叉树乘法算法中，设有n／2个光学加法器，共执行log2n 个步骤，则系统最大可完成n／2log2n 个加法操作．第一步使用了n／2个加法器，同时执行n／2个加法；第二步使用了n／4个加法器，同时执行n／4个加法；以此类推；第log2n步使用了1个加法器，执行1个加法．一共需要执行n／2＋n／4＋…＋1＝n-1个加法．因此，二叉树乘法算法的并行加法器的利用率为

随着n的增大，参数U的值是递减的．从时间性能的分析可知，n越大的二叉树乘法的时间性能越好，因此对于光处理器而言更适合处理n较大的乘法，但加法器利用率却与n成反比，这将降低并行光学加法器运行的吞吐量．为了提高U，应充分利用光学处理器的资源，并行处理尽可能多的乘法，增加单位时间内完成乘法的数量．

假设有n个加法器，则每一步最大可并行执行n个加法．当U＝1，并行处理n个乘法（设每个乘法的乘数位数为n）时，每个乘法均由n个和数项的加法构成，这n个和数项通过二叉树乘法算法进行n-1次加法得到积；因此n个乘法由n2个和数项的加法构成，通过二叉树乘法算法进行n（n-1）个次加法得到n个积．加法器利用率U＝1，则每一步都执行n个加法．计算过程：① 用n个加法器对n2个和数项进行两两相加操作，进行 n2／2n ＝n／2 次并行相加，得到n2／2 个部分和；② 用n个加法器对n2／2个部分和进行两两相加操作，进行（n2／2）／2n ＝ n／4 次并行相加，得到n2／4 个部分和；③ 以此类推，用n个加法器对n2／2k-1个部分和进行两两相加操作，进行 （n2／2k-1）／2n ＝ n／2k次并行相加，得到n2／2k个部分和（k＝1，2，…，log2n）；④ 用n个加法器对2n个和数项进行两两相加操作，进行2n／2n＝1次并行相加，得到n个乘积．

从上述计算过程可以看出，完成所有n个乘法需n／2＋n／4＋…＋1＝n-1步并行相加．虽然每一个乘法都是采用二叉树算法完成的，但是由于所有的乘积在最后一步得到，因此至少有一个乘法要经过n-1步才能完成，这与单加法器的情形下，采用顺序累加的方法实现乘法所需的时间延迟一样，因此在U＝1的情况下并行处理n个乘法的时间性能并不理想．

为了提高光学加法器的利用率，要并行完成多个乘法；但如果U＝1，时间性能又会下降到最差的情况；因此需要做一些改进，在保证乘法计算时间性能的同时，充分利用加法器，提高系统的计算吞吐量．利用二叉树乘法算法实现乘法会导致光学加法器的利用率下降，这是由于加法器输出结果的个数是输入数据的一半，再以输出作为输入继续相加，利用率就大大下降了，为此文中提出在二叉树乘法算法两两相加的基础上加入循环反馈．假设有n个加法器，完成n个乘法（设每个乘法的乘数位数为n），改进后运算过程：① 用n个加法器并行地对第一个乘法M1的n个和数项以及第二个乘法M2的n个和数项进行两两相加操作，分别得到n／2和n／2个部分和；② 将得到的两个n／2个部分和反馈到n／2个加法器的输入端继续求和，同时用剩余n／2个加法器对第三个乘法M3的n个和数项进行两两求和．经过这一步，分别得到n／4个、n／4个和n／2个部分和；③依此类推，经过log2n步得到第一个乘法M1和第二个乘法M2的积，第三个乘法M3得到了2个部分和，…，第log2n＋1个乘法的n个和数项经过两两相加得到n／2个部分和；④ 经过log2n ＋1步得到第三个乘法M3的积，…，经过log2n＋n-2步得到第n个乘法的积．改进后光学加法器利用率为U ＝ （（n／2-1）＋（n／4-1）＋…＋1）／（nlog2n）．

4 结论

1）MSD乘法算法实现了n位数的乘法，用于三值光学计算机有效可行，得出每个乘法的时间延迟为执行log2n个加法的时间，与二叉树算法的时间延迟相同；时间复杂度从传统乘法算法的O（n）降低到O（log2n），运算速度得以提高．

2）MSD乘法算法提高了加法器的利用率．计算乘法M1和M2的过程中，加法器的利用率为1；之后直到开始计算第n个乘法Mn的每一步里，第一个加法器空闲不用，加法器利用率为（n-1）／n；计算乘法Mn的过程中，每一步使用的加法器是上一步的一半，且第一个加法器空闲不用，加法器利用率为U ＝ （（n／2-1）＋（n／4-1）＋．．．＋1）／（n log2n）．

［1］ 罗金平．基于符号替换逻辑的光学数字计算［J］．计算机科学，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］ 李国强．负二进制编码的光学阵列化复数运算［J］．光学学报，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］ 李梅，何华灿，金翊，等．一种实现 MSD加法的光学方法［J］．光子学报，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）