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

朱鵬程，管致錦

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

0 引 言

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

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

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

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

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

1.1 相關(guān)概念

首先介紹文章中涉及的幾個(gè)概念。

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

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

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

1.2 PISA指令系統(tǒng)

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

表1 PISA 指令集

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

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

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

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

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

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

1.3 可逆編程原則

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

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

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

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

（3）另外采用形如結(jié)構(gòu)化程序設(shè)計(jì)的 “單入口單出口”控制結(jié)構(gòu)，以簡(jiǎn)化編程難度，防止出現(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ǎn)單分支結(jié)構(gòu)中，為降低編程難度可以使前置條件和后置條件保持相同，前提是分支執(zhí)行過(guò)程中條件判斷涉及的寄存器狀態(tài)不能被改變。循環(huán)結(jié)構(gòu)中的前置條件和后置條件一般不同，在初次進(jìn)入循環(huán)時(shí)前置條件一般不滿足，否則直接跳過(guò)循環(huán)結(jié)構(gòu)，當(dāng)循環(huán)若干次后，后置條件不滿足時(shí)退出循環(huán)。更詳細(xì)的說(shuō)明或更復(fù)雜的控制結(jié)構(gòu)請(qǐng)查閱文獻(xiàn) ［4］。

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

圖3 可逆子過(guò)程

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

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

2.1 設(shè)計(jì)約束

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

2.1.1 乘除法指令格式

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

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

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

2.1.2 參數(shù)傳遞方式

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

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

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

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

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

2.1.4 指令執(zhí)行效果

除法指令和乘法指令正向執(zhí)行效果如表4所示，反向執(zhí)行效果只要交換表4中的前后狀態(tài)即可得到。對(duì)于除法指令 （以20÷6＝3…2為例），執(zhí)行前R3 存放被除數(shù)20，R2存放除數(shù)6，R1為0，執(zhí)行后R3存放余數(shù)2，R2保持不變，R1存放商。對(duì)于乘法指令，執(zhí)行前R3初值為2 （對(duì)應(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í)行過(guò)程可以使用除R3、R2、R1以外的輔助寄存器，但為了邏輯可逆，這些寄存器在指令執(zhí)行后需恢復(fù)為執(zhí)行前的狀態(tài)。

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

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

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

圖5 可逆乘法子過(guò)程

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

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

圖6 可逆乘法子過(guò)程代碼

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

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

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

除法的實(shí)現(xiàn)采用恢復(fù)余數(shù)法，但和傳統(tǒng)的恢復(fù)余數(shù)法略有差別，其運(yùn)算過(guò)程如圖7所示 （以10101111÷1010為例）。該運(yùn)算共有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ù)法

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

02行代碼為除法子過(guò)程的出入口。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)計(jì)數(shù)器R5加1。27行代碼表示循環(huán)退出條件。28行代碼表示交換R3和R8寄存器的內(nèi)容，實(shí)際上PISA 指令集中無(wú)EXCHR 指令，需通過(guò)使用3次異或指令實(shí)現(xiàn)R3和R8交換，此處使用EXCHR 代替3次異或指令。29 行代碼恢復(fù)R7的初值0，也稱為反初始化。

圖8 可逆除法子過(guò)程

2.4 算法分析

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

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

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

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

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

3.1 仿真平臺(tái)

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

圖9 運(yùn)行可逆指令集的仿真平臺(tái)

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

3.2 仿真結(jié)果

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

圖10 乘法指令和除法指令正／反向運(yùn)行效果

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

最后，本文雖然是通過(guò)子過(guò)程實(shí)現(xiàn)了乘法指令和除法指令，但其本質(zhì)上是一種軟件形式的可逆串行乘法器和除法器，因此其設(shè)計(jì)思路可以指導(dǎo)相關(guān)硬件運(yùn)算器［8－10］的實(shí)現(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)麗華.可逆編程語(yǔ)言R－JAVA 及其語(yǔ)言處理系統(tǒng)的設(shè)計(jì) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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ì)算模型與仿真分析 ［J］.計(jì)算機(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.