Re: [問卦] cpu 和指令集為什麼要設計那麼複雜？

看板Gossiping作者 (松鼠)時間4年前 (2020/04/26 14:46), 編輯推噓340(345推 5噓 68→)
留言418則, 362人參與, 4年前最新討論串3/3 (看更多)
※ 引述《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) ; 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; } } 提到這裡，要如何用 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 語言編譯器，輸出 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 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1587883587.A.A82.html
推
04/26 14:46, 4年前 , 1F
推
04/26 14:46, 1F
推
04/26 14:46, 4年前 , 2F
推
04/26 14:46, 2F
→
04/26 14:47, 4年前 , 3F
看個PTT膝蓋又軟軟的= = 我以為老師都是半夜發文的
04/26 14:47, 3F
推
04/26 14:47, 4年前 , 4F
宅瑟夫推
04/26 14:47, 4F
推
04/26 14:48, 4年前 , 5F
10推內
04/26 14:48, 5F
推
04/26 14:48, 4年前 , 6F
有神快拜
04/26 14:48, 6F
推
04/26 14:48, 4年前 , 7F
先推
04/26 14:48, 7F
推
04/26 14:48, 4年前 , 8F
推
04/26 14:48, 8F
推
04/26 14:48, 4年前 , 9F
有神先跪
04/26 14:48, 9F
推
04/26 14:48, 4年前 , 10F
先拜了
04/26 14:48, 10F
推
04/26 14:49, 4年前 , 11F
給大神跪了 我只有看過有人提過OISC概念 第一次看到這
04/26 14:49, 11F
推
04/26 14:49, 4年前 , 12F
推
04/26 14:49, 12F
→
04/26 14:49, 4年前 , 13F
先推再說
04/26 14:49, 13F
→
04/26 14:49, 4年前 , 14F
麼易懂的附例說明的 上八卦也能學到新知
04/26 14:49, 14F
推
04/26 14:49, 4年前 , 15F
先推
04/26 14:49, 15F
推
04/26 14:49, 4年前 , 16F
老師好
04/26 14:49, 16F
推
04/26 14:50, 4年前 , 17F
八卦版可以不要那麼專業嗎
04/26 14:50, 17F
推
04/26 14:50, 4年前 , 18F
先推免得被發現看不懂
04/26 14:50, 18F
推
04/26 14:50, 4年前 , 19F
有神快拜
04/26 14:50, 19F
推
04/26 14:50, 4年前 , 20F
馬桶的圖呢？沒圖說個j8
04/26 14:50, 20F
推
04/26 14:51, 4年前 , 21F
XDDDD
04/26 14:51, 21F
推
04/26 14:51, 4年前 , 22F
教授給推
04/26 14:51, 22F
推
04/26 14:51, 4年前 , 23F
看不懂 QQ
04/26 14:51, 23F
推
04/26 14:51, 4年前 , 24F
推
04/26 14:51, 24F
推
04/26 14:51, 4年前 , 25F
教授好
04/26 14:51, 25F
推
04/26 14:51, 4年前 , 26F
趕快先說自己看的懂
04/26 14:51, 26F
推
04/26 14:51, 4年前 , 27F
看到一半就看不懂了
04/26 14:51, 27F
推
04/26 14:51, 4年前 , 28F
你是在這邊認真三小啦!!!!XDDD
04/26 14:51, 28F
推
04/26 14:52, 4年前 , 29F
推
04/26 14:52, 29F
推
04/26 14:52, 4年前 , 30F
看不懂....
04/26 14:52, 30F
推
04/26 14:52, 4年前 , 31F
看不懂
04/26 14:52, 31F
推
04/26 14:53, 4年前 , 32F
推 去阿姆斯特丹有沒有去嫖妓？
04/26 14:53, 32F
→
04/26 14:53, 4年前 , 33F
恩 還是一樣看不懂
04/26 14:53, 33F
推
04/26 14:53, 4年前 , 34F
有神先拜再看
04/26 14:53, 34F
推
04/26 14:53, 4年前 , 35F
看不懂..我真的有學過記組嗎
04/26 14:53, 35F
推
04/26 14:53, 4年前 , 36F
恩 好 我都懂了
04/26 14:53, 36F
推
04/26 14:54, 4年前 , 37F
一樣先推再看
04/26 14:54, 37F
推
04/26 14:54, 4年前 , 38F
可惜了 ,被一堆火災政治文埋過
04/26 14:54, 38F
推
04/26 14:54, 4年前 , 39F
馬桶以下都看不懂 太專業推
04/26 14:54, 39F
還有 339 則推文
推
04/26 21:14, 4年前 , 379F
......
04/26 21:14, 379F
推
04/26 21:18, 4年前 , 380F
推推 學完計算機結構都不知道有這種東西www
04/26 21:18, 380F
推
04/26 21:18, 4年前 , 381F
原來是選修課廣告文啊！
04/26 21:18, 381F
推
04/26 21:20, 4年前 , 382F
看到中間就開始精神恍惚惹QQ
04/26 21:20, 382F
→
04/26 21:23, 4年前 , 383F
八卦版101%的人看不懂這篇文章
04/26 21:23, 383F
推
04/26 21:40, 4年前 , 384F
跟之前讀組語的時候一樣恍神，痛扣
04/26 21:40, 384F
推
04/26 21:41, 4年前 , 385F
帥啊
04/26 21:41, 385F
推
04/26 21:44, 4年前 , 386F
推推
04/26 21:44, 386F
推
04/26 21:54, 4年前 , 387F
只看到馬桶那邊，剩下的是哪國文字呀
04/26 21:54, 387F
推
04/26 22:14, 4年前 , 388F
有神快拜！！
04/26 22:14, 388F
推
04/26 22:16, 4年前 , 389F
04/26 22:16, 389F
噓
04/26 22:19, 4年前 , 390F
抽大麻 抓到
04/26 22:19, 390F
推
04/26 23:09, 4年前 , 391F
jserv竟然還沒被推爆==
04/26 23:09, 391F
推
04/26 23:23, 4年前 , 392F
推
04/26 23:23, 392F
推
04/26 23:28, 4年前 , 393F
jserv的課都是硬到不行....
04/26 23:28, 393F
推
04/26 23:55, 4年前 , 394F
還沒看完先給推
04/26 23:55, 394F
推
04/26 23:58, 4年前 , 395F
每個字都認識 合起來就看不懂了
04/26 23:58, 395F
推
04/27 00:19, 4年前 , 396F
我跪
04/27 00:19, 396F
推
04/27 00:28, 4年前 , 397F
神串留名，會收入精華區吧！
04/27 00:28, 397F
推
04/27 01:20, 4年前 , 398F
跟我想的差不多
04/27 01:20, 398F
推
04/27 01:28, 4年前 , 399F
看不懂
04/27 01:28, 399F
噓
04/27 01:33, 4年前 , 400F
幹好屌
04/27 01:33, 400F
推
04/27 01:34, 4年前 , 401F
推！！！
04/27 01:34, 401F
推
04/27 01:36, 4年前 , 402F
剛剛按錯 補推
04/27 01:36, 402F
推
04/27 01:44, 4年前 , 403F
我比較驚訝八卦版這麼多人看得懂O_O????
04/27 01:44, 403F
推
04/27 01:55, 4年前 , 404F
老師好
04/27 01:55, 404F
推
04/27 01:57, 4年前 , 405F
推
04/27 01:57, 405F
推
04/27 02:22, 4年前 , 406F
推
04/27 02:22, 406F
推
04/27 02:57, 4年前 , 407F
文組看不懂，但已加入文章收集冊。（慢慢理解
04/27 02:57, 407F
推
04/27 04:38, 4年前 , 408F
嗯嗯跟我想得差不多
04/27 04:38, 408F
推
04/27 06:03, 4年前 , 409F
看不懂 現在我覺得自己像個白癡 +1 XDDD
04/27 06:03, 409F
推
04/27 06:25, 4年前 , 410F
看不懂
04/27 06:25, 410F
推
04/27 08:57, 4年前 , 411F
可以考慮一下文組感受ㄇQQ
04/27 08:57, 411F
推
04/27 09:02, 4年前 , 412F
優文一定要推
04/27 09:02, 412F
推
04/27 09:55, 4年前 , 413F
嗯嗯，到大麻菸那邊我還看得懂
04/27 09:55, 413F
推
04/27 10:40, 4年前 , 414F
嗯嗯 我也是這樣想的
04/27 10:40, 414F
推
04/27 12:31, 4年前 , 415F
嗯嗯跟我想的差不多
04/27 12:31, 415F
推
04/27 14:06, 4年前 , 416F
我以為這個大家都知道耶
04/27 14:06, 416F
推
04/27 14:07, 4年前 , 417F
原PO貼心安插一段小故事 讓文組有參與感
04/27 14:07, 417F
推
04/27 14:07, 4年前 , 418F
推
04/27 14:07, 418F
‣ 更多 jserv 的文章
文章代碼(AID): #1UfIv3g2 (Gossiping)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 jserv 的文章
文章代碼(AID): #1UfIv3g2 (Gossiping)