單一指令計算機

單一指令計算機

單一指令計算機(英語:one instruction set computer,OISC)也稱最簡指令集計算機(ultimate reduced instruction set computer,URISC),它是一種抽象計算機,該計算機只有一條指令。巧妙地選取這一條指令,並且給予無限的資源,單一指令計算機就能成為和其他多指令計算機一樣的圖靈機。在教學上,這種計算機被推薦來幫助理解計算機架構,同時,也能用它來研究計算機的結構模型。

機器架構

在圖靈完備模型中,每個存儲位置可以存儲任意整數,並且根據模型可能存在任意多個位置。 指令本身作為這樣的整數序列駐留在存儲器中。

存在一類具有基於位操作的單指令的通用計算機,例如位複製或位反轉。 由於它們的記憶體模型是有限的,就像在真實計算機中使用的記憶體結構一樣,這些位操作機器相當於真實計算機而不是圖靈機。

當前已知的OISC大致可分為三大類:

•位操縱機

•Transport Triggered Architecture機器

•基於算術的圖靈完備機器

位操縱機:位操作機器是最簡單的一類。

BitBitJump:一個名為BitBitJump的位複製機在記憶體中複製一位,並無條件地將執行傳遞給指令的一個運算元指定的地址。 該過程證明能夠進行通用計算(即能夠執行任何算法並解釋任何其他通用機器),因為複製位可以有條件地修改隨後將執行的代碼。

Toga電腦:另一台稱為Toga計算機的機器反轉一點並根據反轉結果有條件地執行執行。

多位複印機:另一位操作機器,類似於BitBitJump,同時複製幾個位。在這種情況下,通過在記憶體中保留預定義的跳轉表來解決計算普遍性的問題。

傳輸觸發架構:傳輸觸發架構(TTA)是一種設計,其中計算是數據傳輸的副作用。通常,公共地址空間內的一些存儲器暫存器(觸發連線埠)在指令引用時執行指定的操作。例如,在使用單個記憶體到記憶體複製指令的OISC中,這是通過觸發在寫入時執行算術和指令指針跳轉的連線埠來完成的。

基於算術的圖靈完備機:基於算術的圖靈完備機器使用算術運算和條件跳轉。與之前的兩台通用計算機一樣,這個類也是圖靈完備的。該指令對整數運算,整數也可以是存儲器中的地址。

基於不同的算術運算,該類有幾種已知的OISC:

•加法(addleq,如果小於或等於零則增加和分支)

•減少(DJN,如果非零則減量和分支(跳躍))

•增加(P1eq,如果等於另一個值則加1和分支)

•減法(subleq,如果小於或等於則減法和分支)

指令類型

單指令的常見選擇是:

•如果小於或等於零,則減去和分支

•如果否定則減去並分支

•如果借用,則反向減去並跳過

•移動(用作傳輸觸發架構的一部分)

•如果非零則減去和分支(SBNZ a,b,c,定義)

•Cryptoleq(異構加密和未加密計算)

在給定的實現中僅使用這些指令中的一個。因此,不需要操作碼來識別要執行的指令;指令的選擇是機器設計中固有的,OISC通常以其使用的指令命名。上述每條指令均可用於構建圖靈完備OISC。

本文僅介紹非傳輸觸發的基於減法的指令。然而,可以使用基於其他算術運算的指令(例如,加法)來構造圖靈完備機器。例如,一種稱為DLN(遞減和跳轉,如果不為零)的變化只有兩個運算元,並使用遞減作為基本操作。

如果不等於零減去並且分支

SBNZ a,b,c,d指令(“減去和分支,如果不等於零”)從地址b的內容中減去地址a的內容,將結果存儲在地址c,然後,如果結果不是 0,將控制轉移到地址d(如果結果等於零,則按順序執行下一條指令)。

如果小於或等於零減去並且分支

subleq指令(“SUbtract和分支,如果小於或EQual為零”)從地址b的內容中減去地址a的內容,將結果存儲在地址b,然後,如果結果不是肯定的,則將控制轉移到 地址c(如果結果為正,則按順序執行下一條指令)。

通過將第三個運算元設定為依次等於下一個指令的地址,可以抑制條件分支。 如果未寫入第三個運算元,則表示存在此抑制。

使用兩個運算元和一個內部累加器也可以有一種變體,其中累加器從第一個運算元指定的存儲單元中減去。 結果存儲在累加器和記憶體位置,第二個運算元指定分支地址:

儘管每個指令僅使用兩個(而不是三個)運算元,但是相應地需要更多指令來實現各種邏輯操作。

合成指令

只使用subleq指令就可以合成多種類型的高階指令。

無條件分支:

JMP c

可以通過重複減法進行加法,沒有條件分支; 例如,以下指令導致位置a處的內容被添加到位置b處的內容:

ADD a, b

第一條指令從位置Z(即0)處的內容中減去位置a處的內容,並將結果(在a處的內容的負數)存儲在位置Z中。第二條指令從b中減去該結果,存儲在 b這個差異(是原來在a和b的內容之和); 第三條指令將值0恢復為Z.

複製指令可以類似地實現; 例如,以下指令導致位置b處的內容被位置a處的內容替換,再次假設位置Z處的內容被維持為0:

MOV a,b

可以構建任何所需的算術測試。 例如,一個”分支 - 如果 - 零“服從以下指令彙編條件:

BEQ b,c

Subleq2也可用於合成高階指令,儘管它通常需要針對給定任務執行更多操作。例如,轉換給定位元組中的所有位需要不少於10個subleq2指令:

NOT a

仿真

以下程式(以偽代碼編寫)模擬基於subleq的OISC的執行:

該程式假定memory[]由非負整數索引。 因此,對於subleq指令(a,b,c),程式將小於0,b小於0或執行的分支解釋為c小於0作為暫停條件。 可以在下面的外部連結中找到以基於subleq的語言編寫的類似解釋器(即,自解釋器,其可以使用subleq指令的性質所允許的自修改代碼)。

編譯

Oleg Mazonka編寫了一個名為Higher Subleq的編譯器,它將簡化的C程式編譯成subleq代碼。

如果否定則減去並分支

subneg指令(“SUbtract and Branch if NEGative”),也稱為SBN.

通過將第三個運算元設定為依次等於下一個指令的地址,可以抑制條件分支。 如果未寫入第三個運算元,則表示存在此抑制。

合成指令

僅使用subneg指令可以合成許多類型的高階指令。 為簡單起見,此處僅顯示一條合成指令,以說明subleq和subneg之間的區別。

JMP c

其中Z和POS分別是先前設定為包含0和正整數的位置;

只有當Z最初包含0(或小於存儲在POS中的整數的值)時,才能確保無條件分支。 假設Z的內容必須保持為0,則需要後續指令在分支後清除Z.

一個變體也可能有四個運算元-subneg4。 minuend和subtrahend的逆轉簡化了硬體的實現。 非破壞性結果簡化了合成指令。

如果借用則反向減去並跳過

在Reverse Subtract和Skip if Borrow(RSSB)指令中,累加器從存儲器位置中減去,如果存在借位(存儲器位置小於累加器),則跳過下一條指令。 結果存儲在累加器和存儲器位置。 程式計數器映射到記憶體位置0.累加器映射到記憶體位置1.

例子

要將x設定為y減去z的值:

[注1]如果存儲在“temp”的值最初為負值,並且在此例程中第一個“RSSB temp”之前執行的指令借用,那么例程工作將需要四個“RSSB temp”指令。

[注2]如果存儲在“z”的值最初是負值,則將跳過最終的“RSSB x”,因此例程將不起作用。

相關詞條

熱門詞條

聯絡我們