---

※ 引述《Gold740716 (項為之強)》之銘言：
: 第一次碰組語的時候，才知道 cpu 裡有一堆暫存器，
: 各個暫存器能存的資料大小不一樣，
: 每個暫存器還要用專門的指令用來存取和寫入。
: 雖然也是有直接存取記憶體位址的指令，
: 但跑起來好像會比暫存器慢。
: 設計 cpu 的在想什麼？
: 為什麼要設計那麼多指令和暫存器？
: 有沒有八卦？





在微處理器的設計中，one-instruction set computer (簡稱 OISC) [1] 就採用高度的

來解決任何可計算 (computable) 的問題。

怕你覺得這又是個「吃飽撐著」、跟 Brainf*ck [3] 一樣「空幹」的怪東西，我趕快說

運算裡頭，使用者往往不願將隱私和敏感的資訊放上雲端進行處理，但若透過 Paillier

這樣的同態加密技術，即可在加密的訊息上進行運算和保存處理，而且透過特製的 OSIC
則進一步強化處理效率。可參見紐約大學的研究 Cryptoleq [6]。

OISC 其中一種形式稱為 SUBLEQ，由 SUB (SUbtract; 減法) 和 LEQ (Less than or
EQual to zero; 小於等於 0) 所組合，其組合語言的形式為:
    subleq a, b, c

由於處理器只有一種指令，上述也可略寫為 "a, b, c"。其語意用 C 語言來表示則是:
    if (*(b) <= 0) goto *c;

貼文發問者提到:
> 像程式語言一樣，變數就是變數，不要分什麼暫存器和記憶體不是很好嗎？


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

更有趣的是，指令和資料可交叉存在，例如:
    a1  b1  c1
    Data1  Data2
    a2  b2  c2
    Data3
    a3  b3  c3

在 Gary Explains 這個 YouTube 頻道有份短片 "A CPU With Just One Instruction":
    https://youtu.be/jRZDnetjGuo

即以 SUBLEQ 指令來解釋，可別小看這個看似無聊的指令，只要適度組合，可做到絕大多
數我們熟知的功能，甚至還能將類似 C 語言的程式轉為這個 SUBLEQ 指令的組合 [7]。
由於 SUBLEQ 指令語意單純，我們很容易就能用 C 語言撰寫其指令模擬器:

#include <stdio.h>
int main(int C, char **A) {
    FILE *F = fopen(A[1],"r");
    while (fscanf(F, "%d", i++) > 0)
        ;
    }
}

提到這裡，要如何用 SUBLEQ 指令來做尋常的運算呢？首先我們需要預先在記憶體保存
一些常數，供日後使用，如:
    Z :  0
    N : -1

然後來思考 subleq Z Z c 的意義為何？

回想稍早提過 subleq a b c 等價於 C 語言的

    *(b) = *(b) - *(a);

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

將用 a := Z 和 b := Z 帶入上面的表示式後，原本的條件判斷式就變成無條件跳躍，
也就變成 JMP 指令。

再來思考 subleq a a $+1 的意義: 用 a := a 和 b := a 及 c := $+1 (下一道指令
所在的地址) 帶入後，就變成 CLR 指令 (即 "clear" [清除給定地址的記憶體內容])。

牛刀小試後，我們再考慮略為複雜的形式，將上述「擴充」而來的指令組合:
    CLR    b
    subleq a Z $+1
    subleq Z b $+1
    CLR    Z

也就是:

    subleq b b $+1    <- *b = 0;

    subleq a Z $+1    <- Z = -*a;

    subleq Z b $+1    <- *b = 0 - (-*a) = *a;

    subleq Z Z $+1    <- Z = 0;

於是 *a 的內容被指派到 *b 去，用「略為高階」的組合語言來表示 (你也可稱為這叫
macro [巨集]) 就是 MOV a b

好，繼續練習:
    subleq a Z $+1
    subleq b Z $+1
    CLR    c
    subleq Z c $+1
    CLR    Z

拆解如下:

    subleq a Z $+1    <- Z = 0 - *a;

    subleq b Z $+1    <- Z = -*a - *b;

    subleq c c $+1    <- *c = *c - *c = 0;

    subleq Z c $+1    <- *c = 0 + *a + *b;

    subleq Z Z $+1    <- Z = 0;

看出這段程式碼的作用是 *c = *a + *b，我們可用 ADD a b c 來表示將前兩者加總後，
指派到最後最後一項的動作。

將 MOV 和 CLR 這兩個巨集組合，考慮以下程式碼:
    MOV    b v
    MOV    a w
    CLR    c
    subleq N c $+1
    subleq w v $+4
    subleq Z Z $-8

其中 v 和 w 是記憶體某處，概念上是「暫存」，不過在 OISC 中，最關鍵的操作就是
更新記憶體，沒有「暫存」與否的事實。拆解上述程式碼:

    MOV    b v        <-     *v = *b;

    MOV    a w        <-     *w = *a;

    CLR    c          <-     *c = 0;

    subleq N c $+1    <- L1: *c++;

    subleq w v $+4    <-     *v = *v - *w; if (*v <= 0) goto L2;

    subleq Z Z $-8    <-     else goto L1;

                      <- L2:

原來這樣就組合出除法的操作 (不考慮除數為 0 的狀況)，我們可將巨集寫為 DIV a b c

前面提到可將資料和指令混合，我們來看這個案例:

    MOV  a L1        <- *L1 = *a

    data Z
    data Z
L1: data Z

這樣我們就在 L1 這個記憶體位址指定了 a 這個地址，日後可供日後查表跳躍 (對應到
C 語言的 switch-case 敘述) 使用。倘若你想看更複雜的 subleq 指令運用，可參見:
    https://github.com/davidar/subleq

提供若干簡潔的 subleq 指令使用範例，如氣泡排序法、四則計算器、階層運算，和產生
質數序列。

當然，看到這裡實在很難體察 OISC 的實用性，但如果 subleq 指令的實作能夠抵抗
side-channel attack (透過運算裝置的實體資訊，如反應時間、電能開銷、觸發的頻率
等，進行統計分析，從而旁敲側擊出資訊本體的攻擊手法) [8]，那麼建構在 subleq
指令之上的程式也能抵抗 side-channel attack -- 欲執行的程式碼可穿插若干隨機
資料或在執行時期進行程式碼自我修改 (self-modifying code; SMC) [9]，種種手段
都可提高對抗 side-channel attack 的能力。

OISC 不只有 subleq 這形式，還有其他指令變形，可參見:
    https://esolangs.org/wiki/OISC

在 Derbycon 2015 研討會上，有場精湛的演講，即是透過這類 OISC 混淆程式碼，可見:
    https://youtu.be/R7EEoWg6Ekk (演講錄影)
    https://github.com/xoreaxeaxeax/movfuscator (針對 M/o/Vfuscator 發展的 C

不過慕尼黑大學的研究員發展特製工具來處理 M/o/Vfuscator 的程式，有限度分析其
運作。

又因 OISC 在 FPGA 實作大約僅需要 500 個左右的 CLB (Configurable Logic Block)
或 LAB (Logic Array Block) 這類基礎區塊，也有研究嘗試去發展多處理器的 OISC，如
"A Simple Multi-Processor Computer Based on Subleq" [10]

OISC 聽起來已是最簡約的處理器指令集設計，但仍有一種特別的途徑 -- 「沒有指令」
的處理器，存在 No instruction set computing (NISC) [11] 和 zero instruction
set computer (ZISC) [12] 這兩種設計 (彼此不同，但形式都不提供指令)，該形式非常
特別，不算通用的處理器，往往是針對特定的應用場域去設計，像是人工神經網路
(Artificial Neural Network; ANN, 也稱神經網路)，知名廠商如 IBM, Facebook,
Google 等陸續針對這類特別形式去發展硬體或加速器。

(什麼？你竟然不小心讀到這裡了？那來看廣告吧)


書本和現實的落差有多大呢？開設於國立成功大學資訊工程研究所的「進階電腦系統理論


    http://wiki.csie.ncku.edu.tw/sysprog/schedule

在 2020 年秋季，「進階電腦系統理論與實作」預計還會探討自動駕駛和機器人自動化
發展框架，歡迎關注。

[1] one-instruction set computer
    https://en.wikipedia.org/wiki/One-instruction_set_computer
[2] 參見 1936 年的論文 Alan Turing 的論文 "On Computable Numbers, with an
    Application to the Entscheidungsproblem"
[3] Brainf*ck
    https://en.wikipedia.org/wiki/Brainfuck
[4] US9619658B2: Homomorphically encrypted one instruction computation
    systems and methods
    https://patents.google.com/patent/US9619658
[5] Paillier cryptosystem
    https://en.wikipedia.org/wiki/Paillier_cryptosystem
[6] Cryptoleq
    https://esolangs.org/wiki/Cryptoleq
    論文: "Cryptoleq: A Heterogeneous Abstract Machine for Encrypted and
    對應於美國專利 US9619658B2
    相關的開發工具可見: https://github.com/momalab/cryptoleq
[7] 支援 SUBLEQ 的 OISC 模擬器、組譯器，和編譯器
    http://mazonka.com/subleq/
[8] side-channel attack
    https://en.wikipedia.org/wiki/Side-channel_attack
[9] Self Modifying Code
    https://wiki.c2.com/?SelfModifyingCode
[10] "A Simple Multi-Processor Computer Based on Subleq"
    https://arxiv.org/pdf/1106.2593.pdf
[11] No instruction set computing
    https://en.wikipedia.org/wiki/No_instruction_set_computing
[12] Zero instruction set computer (ZISC)
    https://en.wikipedia.org/wiki/Zero_instruction_set_computer

--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.246.163 (臺灣)
※ 文章代碼(AID): #1UfIv3g2 (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1587883587.A.A82.html