看板 Gossiping作者 jserv (松鼠)標題 Re: [問卦] cpu 和指令集為什麼要設計那麼複雜?時間 Sun Apr 26 14:46:11 2020
※ 引述《Gold740716 (項為之強)》之銘言:
: 第一次碰組語的時候,才知道 cpu 裡有一堆暫存器,
: 各個暫存器能存的資料大小不一樣,
: 每個暫存器還要用專門的指令用來存取和寫入。
: 雖然也是有直接存取記憶體位址的指令,
: 但跑起來好像會比暫存器慢。
: 設計 cpu 的在想什麼?
: 為什麼要設計那麼多指令和暫存器?
: 有沒有八卦?
回到 instruction set (指令集) 的定義:由 CPU 指令構成的集合。有可能指令集僅由
一個或零個指令構成嗎?還真的有,而且某些特殊處理器的設計還商業化了。探討這些
特別的案例絕非「吃飽撐著」,可驗證我們對電腦科學的認知,難說未來的某時會派上
用場。
繼續探討前,我先岔開說個小故事。十年前我受邀去荷蘭發表演說,主辦單位很貼心地
安排一個可眺望阿姆斯特丹運河的寧靜住處,採光明亮,床鋪整潔又舒服,不過我很快
就發現讓我困擾的事 -- 飯店怎麼沒內建馬桶呢?後來我才發現,不是房間沒有馬桶,
而是佈景採用高度簡潔風格,沒有浴廁隔間,僅用布幕區隔,且馬桶和其後的造景融為
一體,讓剛抽完大麻煙的我,一時無法辨識呀!
在微處理器的設計中,one-instruction set computer (簡稱 OISC) [1] 就採用高度的
簡潔風格打造 -- 整個處理器只能處理一種指令,自然也就不用在處理器中考慮到指令
編碼 (instruction encoding) 和指令解碼器 (instruction decoder)。OISC 也被稱為
ultimate reduced instruction set computer,直譯是超精簡指令集電腦,這樣的設計
仍可達到 Turing-complete (圖靈完備性) [2],只要這樣的機器能被實作出來,就能用
來解決任何可計算 (computable) 的問題。
怕你覺得這又是個「吃飽撐著」、跟 Brainf*ck [3] 一樣「空幹」的怪東西,我趕快說
,OISC 衍生的微處理器不乏有實務應用,例如由紐約大學所持有的美國專利編號
US9619658B2 [4] 就將 Paillier 密碼系統 [5] 和 OISC 結合起來,該專利就針對雲端
運算裡頭,使用者往往不願將隱私和敏感的資訊放上雲端進行處理,但若透過 Paillier
這樣的同態加密技術,即可在加密的訊息上進行運算和保存處理,而且透過特製的 OSIC
則進一步強化處理效率。可參見紐約大學的研究 Cryptoleq [6]。
OISC 其中一種形式稱為 SUBLEQ,由 SUB (SUbtract; 減法) 和 LEQ (Less than or
EQual to zero; 小於等於 0) 所組合,其組合語言的形式為:
subleq a, b, c
由於處理器只有一種指令,上述也可略寫為 "a, b, c"。其語意用 C 語言來表示則是:
*(b) = *(b) - *(a);
if (*(b) <= 0) goto *c;
貼文發問者提到:
> 像程式語言一樣,變數就是變數,不要分什麼暫存器和記憶體不是很好嗎?
SUBLEQ 就貫徹這想法,不區隔暫存器和記憶體 -- 有如 Universal Turing Machine,在
OISC 中,只要給予無限的資源,單一種指令所組合出來的程式就能和典型多指令電腦,
達到 Turing-complete。前述不需要處理指令編碼,所以 a, b, c 這三個 operand 就
可循序建構出以下的「程式」:
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");
int P = 0, _[9999], *i = _;
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
也就是:
於是 *a 的內容被指派到 *b 去,用「略為高階」的組合語言來表示 (你也可稱為這叫
macro [巨集]) 就是 MOV a b
好,繼續練習:
subleq a Z $+1
subleq b Z $+1
CLR c
subleq Z c $+1
CLR Z
拆解如下:
看出這段程式碼的作用是 *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 中,最關鍵的操作就是
更新記憶體,沒有「暫存」與否的事實。拆解上述程式碼:
原來這樣就組合出除法的操作 (不考慮除數為 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
語言編譯器,輸出 OISC 指令!)
不過慕尼黑大學的研究員發展特製工具來處理 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 等陸續針對這類特別形式去發展硬體或加速器。
(什麼?你竟然不小心讀到這裡了?那來看廣告吧)
你可曾想過,你手上的 Apple Watch 內建著雙核處理器,但自己卻說不出裡頭的原理,
翻閱報章雜誌關於資訊技術的描述後,反而更加懷疑自己是否真的學過電腦科學,到底
書本和現實的落差有多大呢?開設於國立成功大學資訊工程研究所的「進階電腦系統理論
與實作」課程定位於回顧資訊工程必修科目,並著眼於逐步解析資訊科技工業的發展,
期望學員得以銜接當今的科技脈動 (state-of-the-art)。本課程的教材、練習題目和
講解錄影悉數公開,請見:
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
Unencrypted Computation"
對應於美國專利 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
→ dklash: 看個PTT膝蓋又軟軟的= = 我以為老師都是半夜發文的3F 04/26 14:47
推 flysonics: 給大神跪了 我只有看過有人提過OISC概念 第一次看到這11F 04/26 14:49
→ flysonics: 麼易懂的附例說明的 上八卦也能學到新知14F 04/26 14:49
推 db: 八卦版可以不要那麼專業嗎17F 04/26 14:50
推 Slowbro: 先推免得被發現看不懂18F 04/26 14:50
推 tanby: 有神快拜19F 04/26 14:50
推 aaaba: 馬桶的圖呢?沒圖說個j820F 04/26 14:50
推 choux: 推24F 04/26 14:51
推 anoreader: 你是在這邊認真三小啦!!!!XDDD28F 04/26 14:51
推 jdchbo: 看不懂....30F 04/26 14:52
→ giaour …
推 giaour: 推 去阿姆斯特丹有沒有去嫖妓?32F 04/26 14:53
→ s860134: 恩 還是一樣看不懂33F 04/26 14:53
推 zamperla: 看不懂..我真的有學過記組嗎35F 04/26 14:53
推 Imdream: 可惜了 ,被一堆火災政治文埋過38F 04/26 14:54
推 monar: 馬桶以下都看不懂 太專業推39F 04/26 14:54
推 HMKRL: 推40F 04/26 14:54
推 kingtama: 有必要這樣讓一堆人看不懂嗎?42F 04/26 14:54
推 flysonics: 再推一次 這篇我要站內信收藏 很有趣43F 04/26 14:54
→ jserv: @kingtama, 從「空幹」、「腦幹」,到「專一」指令46F 04/26 14:55
推 C10202: 看不懂 QQ 還是推47F 04/26 14:55
→ jserv: 志祥 -> Brainf*ck -> OISC (符合時事的教學?)49F 04/26 14:55
→ NX9999: 已站內信戰略收藏50F 04/26 14:55
推 AUwalker: 看不懂 現在我覺得自己像個白癡51F 04/26 14:56
推 quartics: Zero instruction 不就state machine!!53F 04/26 14:56
→ BJ0912: 我想講的都被你講走了54F 04/26 14:57
→ jserv: @AUwalker, 這是篇廣告文,補習班都是先嚇你再推課程56F 04/26 14:57
推 teremy: 看沒有 但推一個57F 04/26 14:57
推 shiwa: 看不太懂但好像很厲害64F 04/26 14:59
→ dklash: 所以這篇是招生文嗎?66F 04/26 14:59
推 loxic: 推67F 04/26 14:59
→ diiky: 推68F 04/26 14:59
→ jserv: @dklash, 是呀,之前課程退選率超過七成,我要趕快招生70F 04/26 15:00
→ jserv: @giaour, 大麻有助於思考 (煙)74F 04/26 15:01
推 airyptt: 可惜沒有時間管理,推75F 04/26 15:01
推 prmea: 文組不懂76F 04/26 15:03
推 MrWTF: 嗯嗯跟我想的一樣==86F 04/26 15:05
推 supersu1a: 我想問個問題 x86 cpu動不動就3GHz 5GHz 其他類型asic87F 04/26 15:05
→ jserv: @realtw5566, 有請唐鳳發展中文程式語言和指令集89F 04/26 15:06
→ supersu1a: 同製程頂多2G上下,我知道是算法不同,但是有沒有關鍵字可以讓我找文章的?90F 04/26 15:06
推 b0920075: 之前有人提出過在x86下用mov指令取代所有指令達到obfuscation的效果,老師可以解說一下嗎92F 04/26 15:06
→ jserv: @supersu1a, 一句話解釋是 microarchitecture 落差
@b0920075, 上面的演講錄影有提到呀94F 04/26 15:06
Jim Huang
@jserv
/*SUBLEQ interpreter*/
#include<stdio.h>
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?_
+=getchar():b<0
?printf("%c",_[a]):(_[b]-=_[a])<=0?P=c:0;}}
→ jserv: OISC 的模擬器原始程式碼可塞進一道 twit 中102F 04/26 15:08
推 pp787753: 跟我想的差不多 要不是我在大便 不然真想再補充一些104F 04/26 15:09
→ jserv: @b0920075, 歡迎看懂後補上重點提示,共筆分享 :)109F 04/26 15:11
推 gwofeng: 嗯 跟我想的一樣110F 04/26 15:11
推 durga: 哇,真的是長知識了!!112F 04/26 15:12
→ supersu1a: 再請教一下老師 高時脈算法是跟一次處理指令指令/clock cycle相關嗎?113F 04/26 15:12
→ giaour …
推 giaour: [url]https://wy-lang.org/[/url]115F 04/26 15:12
→ giaour …
→ giaour: 應該請譚鳳發展台語文的程式語言120F 04/26 15:13
推 x21198: 看到一半就看不懂了啦124F 04/26 15:17
推 q0500: 嗯嗯128F 04/26 15:19
推 kodato: 是宅瑟夫,給跪了130F 04/26 15:19
→ jserv: 處理器時脈對於現代處理器實際的速度已不是最關鍵的因素131F 04/26 15:20
推 supersu1a: 感謝老師 這個問題關鍵字有夠難查 我會用功的133F 04/26 15:21
→ jserv: @gR7P4zXH, 在處理器的領域中,"CAT" 這字樣不算少見,貓咪134F 04/26 15:22
→ AZ09 …
推 AZ09: 文組看不懂了 不能簡單講嗎?137F 04/26 15:22
→ jserv: CAT: Cache Allocation Technology #138F 04/26 15:22
→ giaour …
推 giaour: cat指令常用,就是貓咪的意思。喵。140F 04/26 15:23
推 Martie: 請問老師你十年前抽的大麻煙是不是ㄎㄧㄤ到現在143F 04/26 15:24
→ jserv: @Martie, 要不是人在學校教書,我就殺去阿姆斯特丹了146F 04/26 15:25
推 mosw: 跪推156F 04/26 15:28
推 firxd: 嗯嗯嗯 跟我想的差不多157F 04/26 15:28
→ jserv: @aaaba, 馬桶和電腦科學也有關
Toilet Paper Algorithms159F 04/26 15:30
推 Strokes: 嗯嗯 跟我想的很接近161F 04/26 15:31
推 brabra: 有神先跪163F 04/26 15:32
→ jserv: @kevin850717, 學習是一輩子的事,所以你更需要線上課程165F 04/26 15:33
推 lairx: 對沒錯就是這樣我也這麼覺得168F 04/26 15:35
推 a2470abc: 我覺得我要重修計組了....170F 04/26 15:36
→ sa12e3: 沒人覺得應舉例更好及更清楚的例子嗎?直接存取記憶體位址的指令與暫存器的執行差異比較的部分在這篇內文可能沒精準的指出? 應比較兩者間的執行時間長度及功能,例如兩者間只有指令或暫存器可達成某功能,但暫存器或指令比較耗時或省時/節省或消耗硬體資源…173F 04/26 15:38
推 godnnn: 跟我想的一樣179F 04/26 15:39
噓 daye2012: 寫到人家看不懂,那乾脆不要寫185F 04/26 15:42
推 KNVSEOC: 還好你說的abc我都看得懂187F 04/26 15:43
推 ip10: 推 謝謝老師188F 04/26 15:43
→ jixiang: 太深奧了,層次差太多了… 幾乎看不懂 QQ193F 04/26 15:46
推 wsung: 跟我想的一樣195F 04/26 15:48
推 evevt: 先承認看不懂XD
不過看不懂不檢討自己的噓文是在...?197F 04/26 15:49
推 jaid: 推,應該是「代入」而非「帶入」?205F 04/26 15:51
推 lbjstar: 大概跟我想的一樣206F 04/26 15:51
推 ukfa: 有神快推210F 04/26 15:53
推 dou0228: 只看到空幹(拖走211F 04/26 15:55
噓 wsx88432: 對民眾沒幫助 這種掛有意義212F 04/26 15:55
推 ttff: 我真的從沒想過可以只有一個指令 太屌了213F 04/26 15:55
推 Noxus: 馬桶以下就看不懂ㄌ= =214F 04/26 15:56
推 ChoDino: 我只看到馬桶,就來看推文了216F 04/26 15:57
推 cactuar: 謝謝你的解說可惜我看不懂QQ219F 04/26 15:59
推 Sirctal: 看不懂是你廢阿,還有臉噓220F 04/26 15:59
推 Busufu: 仔細咀嚼這篇有很多有意思的東西225F 04/26 16:01
推 Erika98: 推推~~~長知識惹229F 04/26 16:04
推 k51686tw: 跟我想得差不多~英雄所見略同236F 04/26 16:08
推 conq: 推老師!!241F 04/26 16:12
推 ptta: 意猶未盡!感謝老師!242F 04/26 16:13
推 homer00: 看了前五行就回頭確認一下誰的文章…243F 04/26 16:14
推 HFang: 什麼東西…247F 04/26 16:16
推 yerin15: 請問旁聽進階電腦系統理論與實作和 Linux 核心設計的建議順序?252F 04/26 16:18
推 upeo: OISC會取代RISC嗎?255F 04/26 16:19
推 reon: 八卦版年度最專業文259F 04/26 16:22
推 SupCat: 嗯嗯 跟我想的差不多261F 04/26 16:24
推 guinsoo: 我理組也看不懂,給噓266F 04/26 16:27
推 hujj11: 看八掛學知識267F 04/26 16:30
推 aokitaka: 看到是jserv大神趕快過來拜一下269F 04/26 16:37
推 wju1230: 感覺會超難debug的 XD271F 04/26 16:38
推 louis0724: 大麻煙之後我就看不懂了 先推再說XD272F 04/26 16:39
推 orz145: 嗯嗯嗯跟我想說的一樣278F 04/26 16:44
推 gydiaw: 嗯嗯 我就說是這樣嘛279F 04/26 16:44
推 jj0321: 又釣出神人282F 04/26 16:46
--