單一指令處理器 (OISC)

資料整理: jserv

指令集 (instruction set) 的定義是由 CPU 指令所組成的集合，你可能會有這個疑惑：指令集是否僅由一個或甚至零個指令構成？確實存在這樣的指令集，且某些特殊處理器的設計甚至已商業化。探討這些特殊案例並非無的放矢，它們能驗證我們對電腦科學的理解，甚至你會在人工智慧領域見到。

在微處理器的設計中，單一指令集電腦 (One-Instruction Set Computer，簡稱 OISC) 採用極度簡潔的設計風格 —— 整個處理器僅能執行一種指令。因此，處理器不需要考慮指令編碼和解碼器的問題。OISC 也被稱為超精簡指令集電腦 (Ultimate Reduced Instruction Set Computer)，這種設計仍能達到圖靈完備 (Turing-completeness，參見 1936 年的論文〈On Computable Numbers, with an Application to the Entscheidungsproblem〉)，亦即只要這樣的機器被實作出來，就能解決任何可計算的問題 (不考慮執行時間和記憶體容量)。

衍生自 OISC 的微處理器在實務上也有應用，例如紐約大學持有美國專利編號 US9619658B2 的 Homomorphically encrypted one instruction computation systems and methods，該專利將 Paillier 密碼系統與 OISC 結合。這項技術針對雲端運算中的隱私與敏感資訊處理問題，透過同態加密技術，能在加密訊息上進行運算與保存處理，並透過特製的 OISC 進一步提升處理效率，詳見其論文〈Cryptoleq: A Heterogeneous Abstract Machine for Encrypted and Unencrypted Computation〉。

SUBLEQ 指令

OISC 的一種形式稱為 SUBLEQ，由 SUB (減法)和 LEQ (小於等於) 組成，其組合語言的形式如下：

subleq a, b, c

由於處理器僅有一種指令，SUBLEQ 常被簡化寫為：

a b c

這三個運算元儲存在連續的三個記憶體位置中。每個運算元代表一個地址，其執行的虛擬碼如下：

*(b) = *(b) - *(a);
if (*(b) <= 0)
    goto c;

有三種特殊情況：

終止執行：若 c 為負數，則執行終止(或有時若 c 指向無法存取的記憶體位置時終止)。
輸入操作：若 a 為 -1，則從輸入讀取一個位元組並存入地址 b。
輸出操作：若 b 為負數，則從地址 a 輸出一個位元組。

除了 I/O 操作，SUBLEQ 對數字的表示、位元長度 (或每個單元是否為任意精度數字)及負數的實作方式 (如二補數、符號幅度等) 並未做出規定。通常採用二補數系統，但也有 8, 16, 32 和 64 位元版本的 SUBLEQ，32 位元版本最為普遍。

下方程式碼展示用 C 語言撰寫 SUBLEQ 指令模擬器：

#include <stdio.h>
int main(int C, char **A)
{
    FILE *F = fopen(A[1], "r");
    int P = 0, _[9999], *i = _;
    while (fscanf(F, "%d", i++) > 0)
        ;
    while (P >= 0) {
        int a = _[P++], b = _[P++], c = _[P++];
        a < 0 ? _[b] += getchar() :
                b < 0 ? printf("%c",_[a]) :
                        (_[b] -= _[a]) <= 0 ? P = c :
                                              0;
    }
}

Implement Subleq 展示用不同程式語言 (包含機械碼) 開發的 SUBLEQ 虛擬機器的實作。

儘管指令集極為簡單，但在資源無限的情況下，SUBLEQ 仍能達到圖靈完備，意味著單一指令的組合即可構建出功能強大的程式。

SUBLEQ 源自於 1988 年論文〈URISC: The Ultimate Reduced Instruction Set Computer〉提出的 URISC 概念，其目的是為電腦工程學生提供一個簡單的平台，以設計他們自己的指令集和微碼。SUBLEQ 屬於以算術為基礎的單一指令處理器，與其他類型如位元操作或資料搬運觸發架構（以 MOVE 指令為基礎）的架構形成對比。儘管其設計簡單，SUBLEQ 藉由增加僅一種額外指令，如 NAND 或右移指令，即可提高處理效率。

MUXLEQ 架構是 SUBLEQ 增強版本，提供額外的一種指令來提升效能並縮減程式大小。MUXLEQ 系統保持設計的簡潔，使其在硬體實作上幾乎與 SUBLEQ 一樣簡單。現有的 SUBLEQ 程式通常在 MUXLEQ 無需修改即可運作。以下是 MUXLEQ 的虛擬碼：

while pc >= 0:
    a = m[pc + 0]
    b = m[pc + 1]
    c = m[pc + 2]
    pc += 3
    if a == -1:
        m[b] = get_byte()  # Input a byte to memory at address b
    elif b == -1:
        put_byte(m[a])     # Output the byte stored at memory address a
    elif c != -1 and c < 0:
        m[b] = (m[a] & ~m[c]) | (m[b] & m[c])  # Multiplex operation
    else:
        r = m[b] - m[a]   # SUBLEQ subtraction
        if r <= 0:
            pc = c        # Branch if the result is less than or equal to zero
        m[b] = r

倘若移除 elif c != -1 and c < 0: 這條件，就會將 MUXLEQ 還原為典型的 SUBLEQ 機器，因為該條件處理 MUXLEQ 特有的多工器 (multiplexing) 邏輯。

詳見 jserv/muxleq

程式結構

因為 SUBLEQ 不區分暫存器和記憶體，類似於通用圖靈機，只需給予無限的資源，單一指令的組合即可達到多指令電腦的計算能力。由於不需要處理指令編碼，運算元 a, b, c 可循序構建成以下程式格式：

a1 b1 c1
a2 b2 c2
a3 b3 c3
...

更有趣的是，指令與資料可交叉存在，例如：

a1 b1 c1
Data1 Data2
a2 b2 c2
Data3
a3 b3 c3

標示方式:

# 開頭表示記憶體地址的編號，例如 #3 為記憶體地址 3
* 開頭表示 C 語言的取值 (value of) 操作，取得指定記憶體地址的內容，例如 *A

考慮記憶體預先存放以下 SUBLEQ 指令:

3 4 6
7 7 7
3 4 0

初始記憶體地址 (表格上方) 和對應記憶體內容 (表格下方):

`#0`	`#1`	`#2`	`#3`	`#4`	`#5`	`#6`	`#7`	`#8`
3	4	6	7	7	7	3	4	0

第一道指令位於地址 0，其內容為 subleq 3 4 6，該指令的執行過程如下：

A = 3（即記憶體地址 #3，對應內容為 7）
B = 4（即記憶體地址 #4，對應內容為 7）
C = 6（即記憶體地址 #6，對應內容為 3）

執行步驟：

從記憶體地址 #4 取得內容值 7，從記憶體地址 #3 取得內容值 7
計算 *B - *A = 7 - 7 = 0
將結果 0 存回記憶體地址 #4
由於結果 0 ≤ 0，依據 SUBLEQ 指令語意，跳躍到記憶體地址 #6

接下來，從記憶體地址 #6 執行指令 3 4 0：

A = 3（即記憶體地址 #3，對應內容為 7）
B = 4（即記憶體地址 #4，對應內容為 0）
C = 0（即記憶體地址 #0，對應內容為 3）

此時記憶體地址和對應內容:

`#0`	`#1`	`#2`	`#3`	`#4`	`#5`	`#6`	`#7`	`#8`
3	4	6	7	0	7	3	4	0

執行步驟：

從記憶體地址 #4 取得內容值 0，從記憶體地址 #3 取得內容值 7
計算 *B - *A = 0 - 7 = -7
將結果 -7 寫入記憶體地址 #4
由於結果 -7 ≤ 0，跳躍到記憶體地址 #0

由於第二道指令執行後，會跳躍到記憶體地址 #0，也就是說又從 subleq 3 4 6 開始執行：

A = 3（即記憶體地址 3，對應內容為 7）
B = 4（即記憶體地址 4 對應內容為 -7）
C = 6（跳躍到記憶體地址 #6）

執行步驟：

計算 -7 - 7 = -14
將 -14 存回記憶體地址 #4
由於 -14 ≤ 0，跳躍到記憶體地址 #6

只要指令持續執行，我們可發現記憶體地址 #4 的內容從最初的 7 變成 0, -7, -14, -21, -28, …

相關示範可參見 Gary Explains 的 YouTube 短片 "A CPU With Just One Instruction"。SIC-1 是建構在 SUBLEQ 的互動遊戲。

擴充 SUBLEQ 的指令

要如何用 SUBLEQ 指令進行常見運算？首先我們運用 SUBLEQ 擴充若干「巨集指令」(macro instruction)，協助之後程式開發使用。需要注意的是，SUBLEQ 機器沒有堆疊 (stack)、沒有函式呼叫和返回，沒有間接讀取或存取，但這些可藉由 SUBLEQ 指令的組合達成。前述的組合語言形式 subleq a, b, c 中，運算元 c 不能被目前指令修改，因此若 b 指向 c 的位置，下次執行該指令時，它會有個新的跳躍位置。

接下來定義我們的第一道巨集指令：無條件跳躍指令，簡稱 JMP，可按照以下方式製作，使用 A, B 和 C 作為運算元，一如稍早所及：

.macro JMP c
    subleq Z, Z, c
.endm

其中 .macro 和 .endm 是提供給組譯器識別，不會產生指令。

跳躍可在單一指令中達成，該巨集指令中的 Z 是包含 0 的記憶體單元位置，它可能會被暫時修改，使其不再包含 0，但在序列結束時應該總是恢復為0。上述標記表示運算元 A 和 B 應該指向那個包含 0 的記憶體單元位置。跳躍位置就放在第三個運算元中。由於從 0 減去 0 仍然是 0，因此總是執行跳躍到位置 C。

NOP 可編碼如下：

.macro NOP
    subleq Z, Z
.endm

注意其第三個運算元被省略，我們將其解釋為跳躍位置是下一道指令的位置。

重要的巨集指令 ADD 定義如下： (將 a 和 b 的值相加，並將總和存入 b)

.macro ADD a, b
    subleq a, Z
    subleq Z, b
    subleq Z, Z
.endm

ADD 巨集指令在 Z 中儲存一個暫時的結果，但它應該始終從 0 開始，它實際上是對從 a 讀取的值進行反向 (not)，將其儲存在 Z 中，然後從 Z 中減去並將結果儲存在 b 中。然而 Z 包含一個未知的、可能非零的值，因此第三道 SUBLEQ 指令從自身減去 Z ，從而在 ADD 巨集指令結束時恢復其 0 狀態，於是這三道指令的作用成為 *c = *a + *b。

資料複製/搬動的巨集指令 MOV 可定義如下： (將位置 a 的資料複製到 b。重用 ADD 巨集)

.macro MOV a, b
    subleq  b, b
    ADD     a, b
.endm

條件分支，當 mem[b] ≥ 0 時跳躍，即 JGE 可定義如下： (重用 JMP 巨集)

.macro JGE b, c
    subleq b, Z, gte
    JMP    done
gte:
    subleq Z, Z, c
done:
    subleq Z, Z
.endm

條件分支，當 mem[b] = 0 時跳躍，即 JE 可定義如下： (重用 JMP 巨集)

.macro JE b, c
    subleq Z, b, lte
    JMP    done
lte:
    subleq b, Z, gte
    subleq Z, Z, done
gte:
    subleq Z,Z, c
done:
    subleq Z, Z
.endm

以上展示如何利用 SUBLEQ 的單一指令來構建更高級的操作，隨後我們可定義更多巨集指令，包括間接存取、跳躍及條件分支等巨集指令，從而建構經典的電腦程式。

以下利用前述巨集指令，撰寫可計算 Fibonacci 數列的程式：

.def n   0xfa 6             ; Input value 'n' for the Fibonacci sequence
.def a   0xfc 0
.def b   0xfd 1
.def out 0x07 0             ; Output register for displaying the result

; Temporary registers, necessary because SUBLEQ instructions modify the original
; registers. The program could be optimized to use only one temporary register.
.def tmp1 0xfe 0
.def tmp2 0xff 0

; Constant values. Since SUBLEQ does not support immediate instructions, these
; values are stored in registers.
.def Z   0x00 0
.def one 0xfb 1
.def two 0xf9 2

    mov n, tmp1             ; Copy 'n' to tmp1 to use it for calculations
    subleq two, tmp1, done  ; If n <= 2, jump to 'done'
    subleq one, n, loop     ; Start computation by decrementing n (n := n-1)

loop:
    mov a, tmp1             ; Save the current value of 'a'
    mov b, tmp2             ; Save the current value of 'b' to tmp2 for addition
    add tmp1, tmp2          ; Add tmp1 and tmp2, store the result in tmp2
    mov b, a                ; Update 'a' with the value of 'b'
    mov tmp2, b             ; Update 'b' with the new sum stored in tmp2
    subleq one, n, done     ; Decrement 'n' by 1
    subleq Z, Z, loop       ; If n > 0, jump back to 'loop'

done:
    mov b, out              ; Move the final Fibonacci number to the output register

指令與資料的混合

在 OISC 中，指令與資料可交叉存在，例如：

MOV a L1 <- *L1 = *a
data Z
data Z
L1: data Z

這樣可在記憶體位址 L1 指定 a 的地址，供後續跳躍或查表使用。更複雜的 SUBLEQ 指令運用案例，可參考：

OISC 的實用性與安全性

OISC 的實用性雖然看似有限，但若能有效抵抗旁道攻擊 (side-channel attack)，例如透過運算裝置的實體資訊(如反應時間、電能消耗、觸發頻率等)進行統計分析來竊取資訊，則基於 SUBLEQ 指令的程式也能增強抵抗能力。這可透過插入隨機資料或在執行時期進行程式碼自我修改 (Self-Modifying Code，SMC) 等手段來達成。

其他指令變形

除了 SUBLEQ，還有其他形式的 OISC 指令變形，詳情可參見 esolangs: Subleq。在 Derbycon 2015 研討會上，有場精彩的演講展示如何透過 OISC 混淆程式碼：

Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas
movfuscator：針對 M/o/Vfuscator 發展的 C 語言編譯器，輸出 OISC 指令。

OISC 在 FPGA 與多處理器系統中的應用

由於 OISC 在 FPGA 實作上僅需約 500 個 CLB (Configurable Logic Block)或 LAB (Logic Array Block)這類基礎區塊，有研究嘗試開發多處理器的 OISC，如〈A Simple Multi-Processor Computer Based on Subleq〉。

在 2022 年的 Forum on Specification & Design Languages (FDL) 研討會中，奧地利約翰·克卜勒林茲大學 (Johannes Kepler University Linz) 的研究人員發表題為〈Formal Verification of SUBLEQ Microcode implementing the RV32I ISA〉的論文，並獲得大會最佳論文獎。他們利用微處理器早期開發的微碼 (microcode)，在 OISC 的基礎上逐步擴充，成功實作出 RISC-V 32 位元指令集 (RV32I)。在 Goldcrest 的實作中，微碼用於 OISC 的 SUBLEQ 指令，展示其圖靈完備，並透過形式化驗證 formal verification) 檢驗微碼與 RV32I 的實作，發現並修正多處潛在錯誤。

無指令處理器設計

OISC 不是唯一的極簡處理器指令集設計，還有無指令集計算 (No Instruction Set Computing, NISC) 和零指令集電腦 (Zero Instruction Set Computer, ZISC)。這些設計形式不提供傳統意義上的指令，通常針對特定應用場域設計，如類人工神經網路 (Artificial Neural Network, ANN)。知名廠商如 IBM、Facebook、Google 等，已針對這類特殊形式發展硬體或加速器。

Transformer (TF) 已成為各種機器學習任務中的熱門選擇，並取得卓越的成果。但它還能如何應用？來自普林斯頓大學和威斯康辛大學的研究團隊在其論文〈Looped Transformers as Programmable Computers〉，探索如何利用 Transformer 網路來實作通用電腦，而且跟 OISC 高度相關。

研究團隊藉由設定特定的權重並將 Transformer 放入循環中來將其轉變為通用電腦，他們參照 SUBLEQ 的風格，構建一個專用的 Transformer，稱為 FLEQ，作為更靈活的單一指令，其形式為：
FLEQ

其中 $f_{m}$ 可從一組函數 (例如矩陣乘法、非線性函數、多項式等) 中選取，並將其硬編碼到網路中。能夠執行 FLEQ 程式的循環 Transformer 的深度不依賴於程式的複雜度或程式碼行數，而是取決於實作單一 FLEQ 指令所需的深度，且這一深度保持不變。這是藉由在輸入序列上反覆運行 Transformer，類似於中央處理器的運作方式來實作的。

研究團隊運用這個框架，展示 Transformer 在推理過程中模擬各種函數的能力，包括基本的計算器、基礎的線性代數函式庫 (如矩陣轉置、乘法、求逆、冪迭代)，以及在隱式全連接網路上實作反向傳播的 in-context learning (ICL) 演算法。用於執行這些程式的 Transformer 網路深度均不超過 13 層，並提供所有這些模型的權重矩陣。

整體的架構如下圖，從記憶體解析出一條指令，讀取由記憶體指標指向的資料，執行加法運算，接著進行條件分支。下方的每個區塊大約是 1 到 2 層的 Transformer。