可逆乘除法指令的設(shè)計與仿真

朱鵬程，管致錦

（1.南通大學(xué) 杏林學(xué)院 計算機科學(xué)與技術(shù)系，江蘇 南通226019；2.南通大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 南通226019）

0 引 言

可逆計算在計算過程中不丟失信息，因此可從根本上避免由于信息丟失而導(dǎo)致的熱耗散，目前對可逆計算的研究主要集中在低功耗CMOS電路［1］、量子電路［2］的邏輯綜合方面，對可逆編程語言［3］和可逆指令系統(tǒng)［4－6］也有所涉及。

指令系統(tǒng)處于軟件層和硬件層之間，其設(shè)計是否邏輯可逆對整個系統(tǒng)能否物理可逆至關(guān)重要。PISA （Pendulum instruction set architecture）［4］是運行在可逆處理器Pendulum 的可逆指令系統(tǒng)，其設(shè)計遵循RISC 規(guī)范，包含各類使用頻度較高的簡單指令。Axelsen 對PISA 作了形式化描述［4］，對個別指令的實現(xiàn)細節(jié)作了調(diào)整 （如RBRA 指令），并驗證了PISA 中無論是算術(shù)／邏輯運算指令，還是各種跳轉(zhuǎn)指令，都是對系統(tǒng)狀態(tài)的可逆更新。由于可逆乘法器和除法器的設(shè)計較為復(fù)雜，可逆處理器Pendulum 的ALU 中未包含乘法和除法部件，因此PISA 指令集中也未包含乘法、除法指令。Bob是一種基于哈佛體系結(jié)構(gòu)［5］的可逆處理器，其指令系統(tǒng)BobISA［6］定義了一種用于整數(shù)的可逆乘法指令和除法指令，但這兩個指令只能進行乘2或除2操作，且除2操作只有當(dāng)被除數(shù)是偶數(shù)時能返回相應(yīng)結(jié)果。這種乘除法指令所受局限性較大，不能進行任意整數(shù)間的乘除操作，因此不具備通用性。

本文擬為PISA 指令系統(tǒng)擴展可逆乘法和除法指令。指令擴展通常有兩種常用方式：一是通過硬件實現(xiàn)，二是通過指令串或子程序模擬。本文采用第二種方式，基于PISA指令系統(tǒng)中的原有指令，根據(jù)可逆編程原則，構(gòu)建乘除法的可逆子程序段。最終得到的乘法除法指令應(yīng)滿足以下條件：①乘法指令和除法指令在格式上保持一致，即在操作數(shù)的個數(shù)以及操作數(shù)的意義保持對稱；②組成乘法或除法的子程序必須邏輯可逆，即無論正向運行還是反向運行都應(yīng)具備確定性；③乘法指令和除法指令互為逆指令，即乘法的正向運行效果等價于除法反向運行，反之亦然。鑒于計算機中的運算可以由硬件實現(xiàn)，也可以由軟件實現(xiàn)，但其在邏輯上存在共通之處，因此本文采用的子程序擴展指令的方式，對如何設(shè)計硬件乘法器和除法器有一定指導(dǎo)意義。

1 PISA指令系統(tǒng)以及可逆編程原則

現(xiàn)代計算機的指令系統(tǒng)在設(shè)計時均沒有考慮邏輯可逆性，因此絕大多數(shù)指令都是邏輯不可逆，PISA 對這些指令通過增加操作數(shù)的方式進行擴展，確保其中每一條指令均可逆。另外，使用機器語言或匯編語言編程原本就比使用高級語言要復(fù)雜很多，再加上邏輯可逆的約束，工作將更為復(fù)雜，因此有必要參照結(jié)構(gòu)化程序設(shè)計的方式，對可逆匯指令串中的分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)以及方法調(diào)用等在形式上作一些規(guī)范。

1.1 相關(guān)概念

首先介紹文章中涉及的幾個概念。

概念1：逆指令。指令i和指令inv（i）互為逆指令當(dāng)且僅當(dāng)滿足以下條件

式中：Sin和Sout——指令執(zhí)行前后的系統(tǒng)狀態(tài) （由各寄存器、存儲器狀態(tài)構(gòu)成），→exe——指令執(zhí)行。

概念2：可逆更新。給定函數(shù)f：D →B 和運算符⊙：（A×B）→C，其中運算符⊙對其第一參數(shù)A 單射，存在函數(shù)g（A×D）→（C×D）使得g（x，y）＝（x⊙f（y），y）是對其第一參數(shù)x 的可逆更新，且其逆更新為：g－1（x，y）＝（x⊕f（y），y），其中⊙和⊕互為逆運算符 （比如加法運算符與減法運算符）。

1.2 PISA指令系統(tǒng)

PISA 是一個完備的指令系統(tǒng)，含近40 條指令，其中包括算術(shù)／邏輯運算指令、程序控制指令以及數(shù)據(jù)傳輸指令等。表1中給出部分PISA 指令，其中指令欄顯示PISA 指令，逆指令欄顯示語義與其相反的逆指令，語義欄顯示該指令執(zhí)行的效果，其它未在表中展示的指令可查閱文獻［4］。表1中R1、R2、R3表示寄存器，IMM 表示立即數(shù)，ROL表示循環(huán)左移操作，⊕表示異或運算，∧表示與運算，∨表示或運算，＜＜表示邏輯左移操作，OFF 表示跳轉(zhuǎn)偏移量，DIR 表示程序運行方向 （正向時取1，反向時取－1），BR 表示跳轉(zhuǎn)寄存器，表示交換。

表1 PISA 指令集

現(xiàn)流行指令系統(tǒng)如8086等，雖然設(shè)計時沒有考慮邏輯可逆性，但確實包含一部分指令是可逆的，這部分指令可以不作變動直接納入可逆指令集，比如表1中指令1－5。這幾條指令邏輯可逆的根本原因在于，無論是加法運算、減法運算還是異或運算都是對其第一參數(shù)的單射變換，這樣的運算必然存在逆運算，因此其對系統(tǒng)狀態(tài)的更新屬于可逆更新［7］。比如 “ADD R2，R1”指令，其將寄存器R2和R1的值相加并將結(jié)果保存在R2中，反向執(zhí)行時，將該指令替換為其逆指令即 “SUB R2，R1”，逆指令執(zhí)行結(jié)束后，R1和R2回復(fù)初始狀態(tài)。

此外，現(xiàn)有指令系統(tǒng)中大部分指令是邏輯不可逆的，比如8086中的 “AND R2，R1”，其將寄存器R1和R2的內(nèi)容相與并將結(jié)果保存到R2中去，但由于與運算的運算規(guī)則，反向運行時無法根據(jù)R1和R2的當(dāng)前狀態(tài)回復(fù)到初始狀態(tài)，所以該指令邏輯不可逆。PISA 中通過擴展指令的方式使相應(yīng)指令實現(xiàn)邏輯可逆，比如 “ANDX R3，R2，R1”，其將R1和R2相與的結(jié)果與R3進行異或，并將最終結(jié)果保存在R3中，R1和R2的內(nèi)容在指令執(zhí)行過程保持不變，當(dāng)R3初值為0時，該指令執(zhí)行后R3中保存的內(nèi)容便是R1與R2 進行與運算的結(jié)果。由于異或是一種可逆運算，ANDX的逆指令便是本身。表1中的指令6～8均是通過類似擴展從而實現(xiàn)邏輯可逆的。

為使程序可逆，僅算術(shù)運算、邏輯運算指令可逆還不夠，只有當(dāng)控制邏輯同時可逆時程序才能真正具備反向確定性。8086等類似指令系統(tǒng)中的轉(zhuǎn)移指令是不可逆，如圖1 （a）所示，反向運行到JTO 處時存在二義性，無法判斷是該逐條執(zhí)行還是跳轉(zhuǎn)。PISA 通過轉(zhuǎn)移指令對的形式實現(xiàn)控制結(jié)構(gòu)的可逆，如圖1 （b）所示，PISA 要求轉(zhuǎn)移指令的目的地必須同樣是轉(zhuǎn)移指令，且該目的指令指向源轉(zhuǎn)移指令。表1所示指令9是無條件移指令，PISA 中還包含其它條件轉(zhuǎn)移指令如BEQ、BGEZ 等。指令11 和12 是特殊指令，其中RBRA 指令主要用于反向子過程調(diào)用，SWAPBR指令主要作為子過程的入口和出口。

圖1 轉(zhuǎn)移指令的結(jié)構(gòu)

為確保控制邏輯可逆，PISA 中的轉(zhuǎn)移指令不直接修改PC寄存器，僅修改BR 寄存器 （該寄存器用于保存跳轉(zhuǎn)偏移量），然后由控制器根據(jù)執(zhí)行方向DIR 和BR 寄存器的內(nèi)容對PC寄存器進行可逆更新，更新邏輯如下

表1中的指令13是PISA 中用于訪問內(nèi)存的指令，該指令通過交換寄存器和指定內(nèi)存單元的內(nèi)容實現(xiàn)內(nèi)存訪問，顯然該指令的逆指令就是其自身。

1.3 可逆編程原則

使用PISA 指令集進行編程，應(yīng)該注意以下幾點：

（1）“ANDX R3，R2，R1”等擴展指令在程序中原則上應(yīng)成對出現(xiàn)，如表2 所示。第一次使用該指令將R1 和R2相與的結(jié)果保存在R3中，第二次使用則借助R1和R2相與的結(jié)果清空R3。為能正確清空R3，兩次使用期間R3、R2以及R1寄存器的值均不能被改變。可以發(fā)現(xiàn)，經(jīng)過兩次執(zhí)行ANDX 指令，相關(guān)寄存器的狀態(tài)回復(fù)為指令執(zhí)行前的初態(tài)，這表明ANDX 指令是可逆的，且其逆指令為自身。在兩次使用類似擴展指令期間，應(yīng)盡量避免相關(guān)寄存器內(nèi)容發(fā)生改變，否則會破壞邏輯可逆性。

表2 擴展指令的使用原則 （數(shù)字形式以二進制表示）

（2）通過指令對的形式保持程序控制結(jié)構(gòu)可逆，即某轉(zhuǎn)移指令的目的指令必須是指向其自身的轉(zhuǎn)移指令 （如圖1所示），或是SWAPBR 指令。前者主要用于控制分支結(jié)構(gòu)或循環(huán)結(jié)構(gòu)，后者主要用于子過程調(diào)用或反向子過程調(diào)用。

（3）另外采用形如結(jié)構(gòu)化程序設(shè)計的 “單入口單出口”控制結(jié)構(gòu)，以簡化編程難度，防止出現(xiàn)面條式代碼。PISA中采用的分支結(jié)構(gòu)以及循環(huán)結(jié)構(gòu)如圖2所示。

圖2 可逆分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)

圖2中豎直箭頭表示順序執(zhí)行，折線箭頭表示跳轉(zhuǎn)執(zhí)行，虛線表示反向執(zhí)行。區(qū)別于經(jīng)典分支結(jié)構(gòu)，可逆分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)在入口和出口處均要作條件判斷以確保反向確定性。在簡單分支結(jié)構(gòu)中，為降低編程難度可以使前置條件和后置條件保持相同，前提是分支執(zhí)行過程中條件判斷涉及的寄存器狀態(tài)不能被改變。循環(huán)結(jié)構(gòu)中的前置條件和后置條件一般不同，在初次進入循環(huán)時前置條件一般不滿足，否則直接跳過循環(huán)結(jié)構(gòu)，當(dāng)循環(huán)若干次后，后置條件不滿足時退出循環(huán)。更詳細的說明或更復(fù)雜的控制結(jié)構(gòu)請查閱文獻 ［4］。

（4）子過程結(jié)構(gòu)及其正向和反向調(diào)用如圖3 所示，BRA、RBRA 等指令含義如表1所示。與經(jīng)典子過程不同的是，可逆子過程調(diào)用時的入口和返回時的出口相同，即圖3中的SWAPBR 指令處。對于同一子過程 （如二進制轉(zhuǎn)換十進制子過程BinToDec），正向調(diào)用 “BRA BinToDec”表示按如圖3 （a）所示箭頭方向執(zhí)行子過程，并用原語義解釋所遇的每條指令，最終實現(xiàn)二進制向十進制的轉(zhuǎn)換；反向調(diào)用 “RBRA BinToDec”則表示按如圖3 （b）所示箭頭方向反向執(zhí)行子過程，并以相應(yīng)逆指令語義解釋所遇的每條指令，最終實現(xiàn)十進制向二進制的轉(zhuǎn)換。這種子過程實現(xiàn)和調(diào)用方式，使得二進制與十進制間相互轉(zhuǎn)換能共享同一子過程。本文中的乘法和除法子過程均是采用這種結(jié)構(gòu)，因此兩個子過程均支持正向調(diào)用和反向調(diào)用。關(guān)于子過程調(diào)用更詳細的解釋可以查閱文獻 ［4］。

圖3 可逆子過程

2 可逆乘法指令和除法指令

為清晰的說明設(shè)計思路并降低實現(xiàn)難度，以下乘法運算和除法運算均針對無符號正整數(shù)，其中乘法運算限于4位×4位，除法運算限于8位÷4位。

2.1 設(shè)計約束

擬基于現(xiàn)有PISA 指令集，通過子過程的方式擴展乘法和除法指令，擴展的乘除法指令能像加減法指令一樣，互為逆指令。因為可逆子過程既支持正向運行，又支持反向運行，所以由此擴展的指令同樣具備雙向運行的特性。

2.1.1 乘除法指令格式

邏輯可逆要求在運算過程不能丟失信息，因此若要正整數(shù)除法指令可逆，則應(yīng)保留足夠的信息。除法運算涉及4個操作數(shù)，分別是被除數(shù)、除數(shù)、商以及余數(shù)，但結(jié)果只要保留除數(shù)、商以及余數(shù)便可實現(xiàn)邏輯可逆，因此如圖4所示可逆除法指令需要3個操作數(shù)，其中操作數(shù)1在指令執(zhí)行前表示被除數(shù)，在執(zhí)行后表示余數(shù)。

雖然正整數(shù)乘法指令一般只需要保存兩個操作數(shù) （如積和乘數(shù)）就能邏輯可逆，但為了實現(xiàn)乘除法指令互為逆指令的目的，也將采用3操作數(shù)以在指令格式上與除法指令對稱，如圖4所示，操作數(shù)1 初值可以不為零，對應(yīng)除法指令的余數(shù)，乘法指令執(zhí)行后操作數(shù)1的值等于被乘數(shù)與乘數(shù)的積和其初值之和，對應(yīng)除法指令中的被除數(shù)，圖4中的箭頭表示乘法指令和除法指令各操作數(shù)之間的對稱關(guān)系。

圖4 乘除法指令格式及其操作數(shù)對應(yīng)關(guān)系

2.1.2 參數(shù)傳遞方式

圖4僅是乘法指令和除法指令的邏輯結(jié)構(gòu)，其實際功能將通過如圖3所示的子過程實現(xiàn)。調(diào)用子過程時需傳遞參數(shù)，擬采用寄存器參數(shù)傳遞法實現(xiàn)傳參，即在主程序中將操作數(shù)存入事先約定的寄存器中，進入子程序后再取出進行處理。擬將操作數(shù)OP1、OP2以及OP3分別存放在寄存器R3、R2以及R1中。

2.1.3 子過程調(diào)用形式以及執(zhí)行模式

將乘法子過程命名為Multx，除法子過程命名為Divx。由于可逆處理機Pendulum 在程序運行過程中可以通過翻轉(zhuǎn)DIR 的取值隨時切換運行方向，因此被調(diào)用的子過程是正向執(zhí)行還是反向執(zhí)行由調(diào)用時的跳轉(zhuǎn)指令和處理器DIR 當(dāng)前值共同決定，見表3。

表3 子過程執(zhí)行模式

在處理機的DIR 方向位預(yù)設(shè)為1時 （即平臺處于正向運行模式），通過 “BRA Multx”指令跳轉(zhuǎn)到乘法子過程并正向執(zhí)行；通過 “RBRA Multx”指令跳轉(zhuǎn)到乘法子過程，翻轉(zhuǎn)方向位DIR，并反向執(zhí)行。當(dāng)處理機的DIR 方向位預(yù)設(shè)為－1時 （即平臺處于反向運行模式），通過 “BRA Multx”指令跳轉(zhuǎn)到乘法子過程并反向執(zhí)行；通過 “RBRA Multx”指令跳轉(zhuǎn)到乘法子過程，翻轉(zhuǎn)方向位DIR，并正向執(zhí)行。即乘法子過程Multx是正向執(zhí)行還是反向執(zhí)行關(guān)鍵取決于進入子過程后DIR 的取值，如為1則正向執(zhí)行，如為－1則反向執(zhí)行。可以發(fā)現(xiàn)在DIR 取值為1和－1時，正向乘法所對應(yīng)的跳轉(zhuǎn)指令是不同的。為方便起見，余下部分以Multx代表執(zhí)行執(zhí)行乘法指令，以Multx－1代表反向執(zhí)行執(zhí)行指令。同樣，Divx 代表正向執(zhí)行除法指令，以Divx－1代表反向執(zhí)行除法指令。

2.1.4 指令執(zhí)行效果

除法指令和乘法指令正向執(zhí)行效果如表4所示，反向執(zhí)行效果只要交換表4中的前后狀態(tài)即可得到。對于除法指令 （以20÷6＝3…2為例），執(zhí)行前R3 存放被除數(shù)20，R2存放除數(shù)6，R1為0，執(zhí)行后R3存放余數(shù)2，R2保持不變，R1存放商。對于乘法指令，執(zhí)行前R3初值為2 （對應(yīng)除法指令中的余數(shù)），R2存放被乘數(shù)，R1存放乘數(shù)，執(zhí)行后R3等于2＋6＊3即20，R2保持不變，R1清零。容易發(fā)現(xiàn)，除法指令Divx和乘法指令Multx執(zhí)行前后的寄存器狀態(tài)正好相反，如將這兩條指令看作是系統(tǒng)狀態(tài)的變換函數(shù)，兩者互為逆函數(shù)，即兩條指令互為逆指令。需注意的是，在指令執(zhí)行過程可以使用除R3、R2、R1以外的輔助寄存器，但為了邏輯可逆，這些寄存器在指令執(zhí)行后需恢復(fù)為執(zhí)行前的狀態(tài)。

表4 乘除法指令執(zhí)行效果

2.2 乘法指令的設(shè)計

乘法實現(xiàn)擬采用原碼一位乘方法，但和傳統(tǒng)方法略有不同。其主要思想是，從乘數(shù)低位開始，如當(dāng)前位為1，將被乘數(shù)與部分積相加并消除乘數(shù)的當(dāng)前位，然后再根據(jù)乘數(shù)高一位作類似操作，但被乘數(shù)須左移一位，直到乘數(shù)最高位為止。可逆乘法子過程的流程如圖5所示，圖中方框表示1個或1串指令，每一個方框都是對系統(tǒng)狀態(tài)的可逆更新，為節(jié)約空間相鄰方框間的箭頭被略去，同樣表示反向運行路線的虛線箭頭也被略去。

圖5 可逆乘法子過程

圖5 （a）展示了乘法子過程的整體結(jié)構(gòu)，其中保護現(xiàn)場是將子過程中涉及到的輔助寄存器內(nèi)容保存到堆棧中，恢復(fù)現(xiàn)場則相反；初始化操作為相關(guān)寄存器賦初值，反初始化將相關(guān)寄存器值恢復(fù)為零。圖5 （a）中①處除法指令串的實現(xiàn)細節(jié)在圖5 （b）中展示，其中②和瑏瑡是控制循環(huán)開始與結(jié)束的條件轉(zhuǎn)移指令對；③處取乘數(shù)第i位；④到⑧是根據(jù)乘數(shù)第i位是否為零決定是否在部分積中加上左移的被乘數(shù)；⑨處消除③處對系統(tǒng)狀態(tài)的更新。⑩處通過一串指令消除乘數(shù)的第i位以使乘數(shù)寄存器在循環(huán)結(jié)束后值為零。

可逆乘法子過程的代碼如圖6所示，為節(jié)約空間省去保護現(xiàn)場和恢復(fù)現(xiàn)場相關(guān)代碼。圖6中各寄存器作用如下：R0存放常量0，R1、R2和R3分別對應(yīng)乘法指令的3個參數(shù)：乘數(shù)、被乘數(shù)以及初值／乘積和，R4暫存BR 寄存器內(nèi)容，R5暫存常量4 （表示最大位數(shù)），R6暫存用于取乘數(shù)第i位的掩碼，R7暫存循環(huán)計數(shù)器 （＜4），R8暫存乘數(shù)的第i位，R9暫存移位后的乘數(shù)。

圖6 可逆乘法子過程代碼

除保存參數(shù)的R1、R2、R3 寄存器外，其它輔助寄存器R0、R4－R9應(yīng)在使用前通過EXCH 指令進行現(xiàn)場保護（篇幅原因省去相關(guān)代碼），隨后這些寄存器內(nèi)容將為零，在子過程執(zhí)行過程中其內(nèi)容可能會發(fā)生改變，2.1.3 要求在子過程返回前須將這些輔助寄存器再次清零，然后再對這些寄存器恢復(fù)現(xiàn)場。圖6中02行代碼是乘法子過程的入口和出口。03行代碼將進入子過程的跳轉(zhuǎn)偏移量取負，為將來再次返回到調(diào)用點做準備。04－05行代碼初始化R5、R6寄存器。06行代碼表示循環(huán)入口條件。07－13 行代碼表示在第i次循環(huán)中如乘數(shù)R1當(dāng)前位為1，則將被乘數(shù)R2左移i－1位并與R3相加，并將結(jié)果保存在R3中。14－20行代碼表示在第i次循環(huán)中消除乘數(shù)R1第i位以達到最終R1清零的目的。21行代碼表示R6循環(huán)左移一位。22行代碼表示循環(huán)計數(shù)器R7加一。23行代碼表示循環(huán)出口條件。24－26代碼將R5、R6 以及R7 清零，也稱反初始化，R8和R9 寄存器循環(huán)前后其值未發(fā)生變化，所以無需反初始化。

需特別注意的是，07行代碼是進行與運算的擴展指令，按上文可逆編程原則 （1）在13行再次使用該指令以清空R9。類似的擴展指令對還有09行和11行、14行和20行。

2.3 除法指令的設(shè)計

除法的實現(xiàn)采用恢復(fù)余數(shù)法，但和傳統(tǒng)的恢復(fù)余數(shù)法略有差別，其運算過程如圖7所示 （以10101111÷1010為例）。該運算共有8步操作，每一步將被除數(shù)R3寄存器和輔助寄存器R8共同左移一位，并將R3的最高位移入R8的最低位，然后將R8寄存器與除數(shù)寄存器R2相減，如果結(jié)果大于等于零，則將商R1左移一位并在末尾上一，否則商左移一位末尾上零并將R8與R2相加以恢復(fù)余數(shù)。第八步操作執(zhí)行后，R1中存放商，交換R3和R8的值，從而使R8清零，R3中存放余數(shù)。

圖7 恢復(fù)余數(shù)法

可逆除法子過程如圖8所示。圖8中各寄存器作用如下：R0存放常量0，R1存放商，R2存放除數(shù)，R3存放被除數(shù)／余數(shù)，R4暫存BR 寄存器內(nèi)容，R5暫存循環(huán)計數(shù)器，R6暫存被除數(shù)最高位，R7暫存常量8，R8為如圖7所示的輔助存儲器，R9暫存被乘數(shù)算術(shù)右移7位的結(jié)果，R10暫存R8或R1最后一位。

02行代碼為除法子過程的出入口。04 行代碼初始化R7寄存器。05行代碼表示循環(huán)入口條件。06－09行代碼將R8寄存器左移一位，并將被除數(shù)R3寄存器的最高位移入R8的最低位。10－15行代碼表示如R8最低位為1 （由R3最高位移入），則消去R3中最高位的1并循環(huán)左移一位以得到R3算術(shù)左移一位的結(jié)果。16行代碼將商R1邏輯左移1位。代碼17將R8與除數(shù)R2相減，并將結(jié)果保存到R8。18－20代碼表示若R8 大于等于零，則在商的末尾加1。21－25行代碼表示若R8小于零，則要恢復(fù)余數(shù)。26行代碼使循環(huán)計數(shù)器R5加1。27行代碼表示循環(huán)退出條件。28行代碼表示交換R3和R8寄存器的內(nèi)容，實際上PISA 指令集中無EXCHR 指令，需通過使用3次異或指令實現(xiàn)R3和R8交換，此處使用EXCHR 代替3次異或指令。29 行代碼恢復(fù)R7的初值0，也稱為反初始化。

圖8 可逆除法子過程

2.4 算法分析

圖6和圖8所示的乘法子過程和除法子過程中從單條指令到整體結(jié)構(gòu)均邏輯可逆。因此對于乘法子過程而言，正向執(zhí)行表示做乘法運算，反向執(zhí)行表示消除乘法運算對系統(tǒng)狀態(tài)的更新，效果上類似于對乘法運算后的寄存器作除法運算。對于除法子過程而言，正向執(zhí)行表示做除法運算，反向執(zhí)行表示消除除法運算對系統(tǒng)狀態(tài)的更新，效果上類似于對除法運算后的寄存器作乘法運算。

最好和最壞情況下兩個子過程循環(huán)體中的加法、移位等操作次數(shù)統(tǒng)計如表5所示。統(tǒng)計時需注意，除法子過程18－20行代碼和22－24 行代碼是互斥的，不可能同時執(zhí)行。

表5 子過程循環(huán)中的關(guān)鍵操作次數(shù)

從表5可得，無論在最好情況還是最壞情況下，乘法效率略高于除法。

3 仿真與仿真結(jié)果

3.1 仿真平臺

根據(jù)可逆處理機Pendulum 的架構(gòu)，為可逆指令集的運行設(shè)計了一個軟件仿真平臺。平臺如圖9所示，以Java類模擬Pendulum 各主要部件，通過類中的成員方法實現(xiàn)各部件的功能。

圖9 運行可逆指令集的仿真平臺

圖9中控制器的主要作用如下：根據(jù)PC寄存器取出指令并解析，然后根據(jù)指令性質(zhì)調(diào)用運算器中相應(yīng)方法處理數(shù)據(jù)；指令執(zhí)行后，根據(jù)BR 寄存器、DIR 方向位的狀態(tài)更新PC寄存器。運算器中包含若干執(zhí)行相應(yīng)運算的成員方法，一般情況下每條指令對應(yīng)兩種運算方法，分別表示正向語義和反向語義，但有些指令其逆指令為其本身 （如EXOR指令），僅對應(yīng)運算器中的一個方法，該方法既表示正向語義，又表示反向語義。寄存器組包含32 個8 位通用寄存器，但在乘除法指令中只用到其中11 個 （R0－R10）。DIR方向位表示仿真平臺執(zhí)行程序的方向，為1時正向執(zhí)行，為－1 時反向執(zhí)行，在運行過程中可以被隨時切換。

3.2 仿真結(jié)果

仿真平臺上正向或反向執(zhí)行乘法或除法子過程時前后的寄存器狀態(tài)如圖10 所示 （數(shù)值以16 進制表示），其中“Multx”表示正向執(zhí)行乘法指令， “Multx－1”表示反向執(zhí)行乘法指令， “Divx”表示正向執(zhí)行除法指令， “Divx－1”表示反向執(zhí)行除法指令。

圖10 乘法指令和除法指令正／反向運行效果

從圖10 （a）可發(fā)現(xiàn)，在相同寄存器初態(tài)下正向執(zhí)行乘法指令和反向執(zhí)行除法指令取得的終態(tài)相同，即無論Multx還是DIVX－1，執(zhí)行完畢后R3的值等于其初值與R2乘R1之和，而R2不變、R1清零。從圖10 （b）可發(fā)現(xiàn)，在相同寄存器初態(tài)下正向執(zhí)行除法指令和反向執(zhí)行乘法指令取得的終態(tài)相同。如將Multx看作是系統(tǒng)狀態(tài)的變換函數(shù)，則Multx和Divx－1等價，Divx和Multx－1等價，但這種等價關(guān)系有時需滿足特定約束條件才能成立。這是由于乘法和除法指令設(shè)計時在參數(shù)上取值區(qū)間的不對稱引起的，第一種不對稱存在于參數(shù)1即R3，除法運算得到的余數(shù)R3必然小于除數(shù)R2，而在乘法運算中R3的初值沒有這個限制；第二種不對稱存在于參數(shù)3即R1，本文設(shè)計的乘法指令局限于4×4 （即乘數(shù)R1最大為15）運算，而8÷4除法指令的商可能超過4 位 （如圖7 所示）。由于以上兩種不對稱性，正向運行模式下 （DIR 預(yù)設(shè)為1）僅在滿足相應(yīng)約束條件時程序中相關(guān)運算可被其等價運算替換，等價關(guān)系見表6。

表6 正向模式下乘法和除法操作的等價關(guān)系

從乘法和除法子過程的分析已知乘法效率略高于除法的事實。通過將除法運算替換等價的乘法運算可以提高程序效率。如表6所示，第3行和第4行的除法運算可被無條件地替換為相應(yīng)乘法運算以提高程序效率。因此在正向模式下下，除法指令無存在必要性。

反向模式時 （即DIR 在程序執(zhí)行過程中被設(shè)為－1），則按相反順序執(zhí)行指令串并按相反語義解釋所遇指令，即相當(dāng)于用逆指令取代當(dāng)前指令。根據(jù)上述分析并通過反復(fù)試驗得如表7 所示結(jié)論，形如inv （Multx）表示對Multx以相反語義進行解釋，可以發(fā)現(xiàn)每個指令都對應(yīng)兩個逆指令。由于指令Multx和Divx都是通過可逆子過程實現(xiàn)的，因此表中第1、3、5以及7行容易理解。同樣由于前述的兩種不對稱性，對第2、4、6 以及8 行指令反向解釋時，只有滿足相關(guān)約束條件時才能用逆指令替換。

表7 DIR 方向位為－1時相關(guān)指令的逆指令

根據(jù)表7以及乘法比除法效率高的結(jié)論，在DIR 方向位為－1的前提下，并在滿足相應(yīng)約束條件時，將表中第6和8行的除法運算替換成相應(yīng)乘法運算，可以有效提高程序運行效率。但在不滿足約束條件的情況下除法運算不能被乘法運算取代，因此DIR 為－1 時除法指令有其存在必要性。

4 結(jié)束語

本文為PISA 指令集擴充的乘法指令和除法指令均為可逆指令，即既支持正向執(zhí)行，又支持反向執(zhí)行。另外，正向的乘法指令和反向的除法指令以及反向的乘法指令和正向的除法指令在滿足特定約束條件時相互等價，即乘法指令和除法指令在滿足特定約束條件時互為逆指令。利用乘除法指令互為逆指令的特性，根據(jù)乘法指令的效率要高于除法指令的結(jié)論，在滿足表6和表7相關(guān)約束時盡量使用乘法指令實現(xiàn)乘除法操作，有助于提高程序運行效率。

最后，本文雖然是通過子過程實現(xiàn)了乘法指令和除法指令，但其本質(zhì)上是一種軟件形式的可逆串行乘法器和除法器，因此其設(shè)計思路可以指導(dǎo)相關(guān)硬件運算器［8－10］的實現(xiàn)。

［1］Saeedi M，Markov IL.Synthesis and optimization of reversible circuits－a survey ［J］.ACM Computing Surveys，2013，45（2）：1－34.

［2］Hirata Y，Nakanishi M，Yamashita S，et al.An efficient conversion of quantum circuits to a linear nearest neighbor architecture［J］.Quantum Information ＆ Computation，2011，11（1）：142－166.

［3］ZHU Pengcheng，GUAN Zhijin，WEI Lihua.Design of reversible programming language R－JAVA and its language processing system ［J］.Computer Engineering and Design，2013，34 （10）：3502－3510 （in Chinese）. ［朱鵬程，管致錦，衛(wèi)麗華.可逆編程語言R－JAVA 及其語言處理系統(tǒng)的設(shè)計 ［J］.計算機工程與設(shè)計，2013，34 （10）：3502－3510.］

［4］Axelsen HB，Glück R，Yokoyama T.Reversible machine code and its abstract processor architecture ［G］.LNCS 4649：Computer Science－Theory and Applications. Heidelberg：Springer，2007：56－69.

［5］LI Bin，YANG Jiaqi.Computational model and simulation analysis for container terminal operation systems under Harvard architecture ［J］.Computer Integrated Manufacturing Systems，2013，19 （9）：2300－2314 （in Chinese）. ［李斌，楊家其.哈佛體系結(jié)構(gòu)下的集裝箱碼頭操作系統(tǒng)計算模型與仿真分析 ［J］.計算機集成制造系統(tǒng)，2013，19 （9）：2300－2314.］

［6］Thomsen MK，Axelsen HB，Gluck R.A reversible processor architecture and its reversible logic design ［G］.LNCS 7165：Reversible Computation.Heidelberg：Springer，2012：30－42.

［7］Axelsen HB.Clean translation of an imperative reversible programming language［G］.LNCS 6601：Compiler Construction.Heidelberg：Springer，2011：144－163.

［8］Dastan F，Haghparast M.A novel nanometric reversible signed divider with overflow checking capability ［J］.Research Journal of Applied Sciences，Engineering and Technology，2012，4 （6）：535－543.

［9］Dastan F，Haghparast M.A novel nanometric fault tolerant reversible divider ［J］.International Journal of the Physical Sciences，2011，6 （24）：5671－5681.

［10］Moallem P，Ehsanpour M.A novel design of reversible multiplier circuit（technical note）［J］.International Journal of Engineering－Transactions C：Aspects，2013，26 （6）：577.