From Nand To Tetris:想理解電腦運作,就先做出一台吧!


Posted by aszx87410 on 2019-12-27


前言

一直以來我都很推薦一門課叫做 CS50,原因是又深又廣,而且教得深入淺出,作業又紮實,是很棒的一堂課。

而今天要介紹的這門課,我會形容它是「電腦底層版的 CS50」。

From Nand to Tetris 由兩位教授 Shimon Schocken 與 Noam Nisan 開設,與 CS50 一樣,一開始都是大學的課程,後來才轉為線上課程,在官網上這堂課還有一個副標題:「Building a Modern Computer From First Principles」,沒錯,要建一台電腦出來。

這堂課分為兩個部分,Part1 是 From Nand To HACK,Nand 是一個邏輯閘的名稱,就像 Or、And、Xor 這些也都是邏輯閘。而 HACK 是在 Part1 最後會建造出來的電腦。因此 Part1 就是帶你從最基本的邏輯閘開始,一步步把一台電腦建立出來,所以是很偏向硬體的部分。

Part2 則是 From HACK To Tetris,以電腦為基礎往軟體去延伸,會介紹到 Compiler 與作業系統等等的軟體。

課程的概觀可以參考這張圖片:

從知道這門課以來我就一直很想修但沒有付諸行動,前陣子終於認真了一段時間把課程修完,名不虛傳,果然是一門好課!因此在這邊寫一篇介紹兼推坑文,希望能推廣給大家。

為什麼想修這門課?

七年前我還是大一的時候,就跑去修了資工系的「計算機組織與組合語言」還有資管系的「計算機組織與結構」,會修這兩門課的原因很簡單,因為我有組合語言情節。

雖然說自己不太會寫組語,但覺得會寫組語很帥。不管是什麼 C++、Go、Rust 還是我自己最擅長的 JavaScript,在我心目中都比不過組合語言。我也不知道為什麼,但覺得會寫組語就是帥。

為了學還有寫組合語言,就修了那兩門課。那兩門課前半段都在講一些電腦比較底層的東西,我到現在還是沒搞懂,前兩次作業都拿了很低分,那些電路圖從來沒看懂過,而課程後半段進入到組合語言之後就如魚得水了,終於到我喜歡且比較擅長的主題。

總之呢,在這兩門課上面除了組合語言以外,我其實沒什麼太大的收穫,因為好多東西都聽不懂。上完之後,我知道有 register,我知道有 L1 L2 cache,我知道有 branch prediction,也知道 instruction pipeline,但我還是不知道電腦到底怎麼做的,不知道怎麼執行。

但因為之後沒有要考資工所,工作上也碰不到這麼底層的東西,就漸漸沒有去注意了。可是在我心裡,還是想知道電腦到底怎麼做出來的。

長大以後無意間聽說了 From Nand To Tetris(以下簡稱 nand2tetris)這門課程,帶你從最簡單的邏輯閘開始,把電腦建出來,然後在這台電腦上跑一個俄羅斯方塊的程式,哇,聽起來超棒。

這就是我想修這門課的理由,我想知道電腦到底怎麼做出來的。我想知道 CPU 裡面到底有什麼,而不只是一個黑盒子。

課程到底上了些什麼?

課程有六週,分成七個單元(單元 0~6),第 0 個單元是課程的介紹,底下我直接依照各個單元來跟大家介紹。

Unit0:課程介紹

這個單元除了介紹課程以外,也介紹了兩個很重要的概念:Abstraction(抽象)與 Implementation(實作)。

直接舉個例子會比較容易懂,例如說今天給你一台電腦,要你在上面寫個輸出 Hello World 的程式,你不用去擔心print到底怎麼把東西印出來,你可以直接假設它就是會印出東西。換句話說,你無須擔心print是怎麼被實作的(Why),只需要知道它可以做什麼就好(What)。

大概就像是疊床架屋一樣,你把第一層蓋好之後就蓋第二層,蓋到第十層的時候,你不用擔心前九層是怎麼蓋的,你只要知道前九層已經蓋好了就可以了,因為你現在的任務是蓋第十層。

這樣的概念在電腦科學裡面超級重要,因為電腦就是個分很多層的東西,從最底層的電子電路,再到基本邏輯閘(And、Or 與 Not),到比較複雜的硬體(Register、ALU),再到更複雜的硬體(CPU、RAM)等等,這些都是一層一層往上建構的。

而這堂課就是帶你從最底層開始,一路往上建,讓你知道一台電腦是由哪些東西所組成的。

這邊的「最底層」指的是邏輯閘,你不用知道在實體世界的電路到底怎麼接的(因為那是電子或是電機的領域了),也不用知道「輸入」到底怎麼輸入,「輸出」到底會輸出到哪裡。

Unit1:Boolean functions ans logic gate

這一週會介紹基本的邏輯閘,例如說 Or, And, Xor, Nand 以及 Nor 等等,讓你知道他們的功用,還會教你畫真值表(Truth table),讓你熟悉這些基本邏輯。

而這週的作業是只給你一個邏輯閘 Nand,要你做出以下 15 種電路:

  1. Not
  2. And
  3. Or
  4. Xor
  5. Mux
  6. DMux
  7. Not16
  8. And16
  9. Or16
  10. Mux16
  11. Or8Way
  12. Mux4Way16
  13. Mux8Way16
  14. DMux4Way
  15. DMux8Way

那要怎麼做呢?用課程團隊自己做的 HDL(hardware description language) 還有硬體模擬器就可以了。

舉例來說,若是想要用 Nand 做出 Not,可以這樣寫:

CHIP Not { // 我要寫一個叫做 Not 的 chip
    IN in; // 輸入的訊號叫做 in
    OUT out; // 輸出叫做 out

    PARTS:
    Nand (a=in, b=in, out=out); // 把 in 跟 in 傳進 Nand chip,輸出到 out
}

如果我的輸入是 0,那 in 就是 0,而 0 Nand 0 的結果是 1,所以 out 就會是 1,就是 0 經過 not 以後的結果。若是輸入是 1,1 Nand 1 是 0,out 就會是 0。

因此,我們可以只用 Nand 這個邏輯閘就完成 Not 的功能。

這一個單元就是讓你去熟悉 HDL 的寫法,並且試著把電路組合起來。在測試的部分,課程團隊也貼心地提供了自製的硬體模擬器,讓你可以載入電路,很方便地去測試到底是不是對的:


(圖片取自官網)

Unit2:Boolean arithmetic and the ALU

這一週要來介紹電腦中的數字運算了,會講到電腦怎麼表示數字,也就是大家熟知的二進位,也會提到負數的表示方法(二的補數),作業是要做出以下的電路:

  1. HalfAdder
  2. FullAdder
  3. Add16
  4. Inc16
  5. ALU

ALU 的全名是 Arithmetic Logic Unit,有修過相關課程的人應該對這個不陌生,總之就是拿來做算術運算的一個電路,輸入兩個數字以及你想進行的操作,就會輸出結果。

Unit3:Memory

前兩週的難度都還好,這一週我覺得難度突然上升,主因是引入了一個新的概念:Sequential logic(序向邏輯電路)。

在前幾個單元所設計的電路,都叫做 Combinational logic(組合邏輯電路),簡單來說呢,可以用這樣的式子來表示:out[t] = function(in[t]),你在某個時間點 t 輸入值,就會回傳相對應的結果,一切十分簡單明瞭。

但是 Sequential logic 不一樣,它的輸出不只與當前的輸入有關,與「以前的輸入」也有關,換句話說,Sequential logic 有記憶東西的能力。

以程式來做比喻,Combinational logic 大概就像是 pure function,你給一樣的 input,一定會產生一樣的 output;而 Sequential logic 則是有 side-effect 的 function。

這一週的作業是要做出以下電路:

  1. 1 bit register
  2. 16-bit register
  3. RAM8(16-bit / 8-register memory)
  4. RAM64
  5. RAM512
  6. RAM4K
  7. RAM16K
  8. PC(Program Counter)

Unit4:Machine Language

其實上個單元對於電腦怎麼做的只差最後一個步驟了,但這週先暫時脫離一下硬體與電路,先假設電腦已經做好了,那應該要怎麼讓電腦去執行程式?

解答應該大家都聽過,就是 machine language,機器語言,是 CPU 唯一看得懂的語言,由 0101010 組成。但是要你直接寫 machine language 有點太殘酷,所以官方提供了 Assembler,讓你只要寫 assembly language 就好。

因此這週就是要來寫 assembly language,讓你熟悉 HACK 這台電腦的指令格式。作業有兩個,一個是輸入兩個數字以後回傳相乘的結果,另一個是互動式的程式,按下鍵盤時螢幕會變黑,放開時會變白。

這週我覺得比較有趣的是講解了 input 與 output 的原理。舉例來說,鍵盤打字之後電腦要怎麼知道剛剛按了什麼按鍵?可以很簡單地簡化成這樣:每當鍵盤被按下,就會傳送一個訊號到電腦,並且在某一個特定記憶體位置放入剛剛按的按鍵的代碼,這樣子我只要去那個記憶體位置看有沒有值,就知道使用者有沒有按按鍵了。

輸出也是一樣,有某個記憶體區塊,每一個 bit 代表一個 pixel,1 代表黑色,0 代表白色,而螢幕會用很快的頻率(例如說一秒 50 次之類的)去讀取這塊記憶體,並且把該顯示的在螢幕上顯示出來。

如此一來,輸入與輸出都可以透過記憶體的特定位置來達成。

Unit5:Computer Architecture

這週把之前第三週沒有做完的電腦繼續做,要來做 Memory 以及 CPU,同時也告訴你電腦是怎麼執行這些指令的。這個單元的內容滿重要的,把之前第三週所做出來的東西整合起來,最後做成了一部電腦。

Unit6:Assembler

第四週的時候我們用了官方提供的 assembler 轉成機器碼,而 part1 的最後一週就是要讓你自己寫 assembelr,自己把組合語言轉成機器語言。

若是不會寫程式的話,官方也提供了另外一種交作業的方式,那就是手動翻譯。自己把每一行程式碼查表然後翻成機器語言。

做到這邊,七個單元就都結束了,在這七個單元裡面做出了很多的電路,最後做出了 CPU、Memory 以及一台電腦,也知道要怎麼在這台電腦上執行指令,知道怎麼寫一個 assembler。

課程心得

這堂課與 CS50 一樣,都標榜著毫無基礎也可以上。但我之前就說過了,我不認為 CS50 真的適合所有沒有基礎的人,對有些人來說,梯度依舊太高,難度上升太快,還有改進的空間。

那這堂課呢?我覺得新手可以嘗試看看,因為真的不需要任何程式基礎,但我猜作業的部分依舊會卡關的滿嚴重的。雖然說不需要程式基礎,但有些作業還是很吃你的邏輯跟思考能力,一個恍神就忘記自己現在想到哪裡了。

在修這堂課的過程中,有幾個讓我驚豔到的點,以下有雷,可能會破壞修課的樂趣,可自行斟酌是否觀看。

第一個是 HACK 的機器語言有分兩種,一種是 A-instruction,另一種是 C-instruction,區別的方法是最高位,一個是 0 一個是 1。前者是拿來載入一個 15bit 的值用的。

第四週在寫組合語言時沒注意到為什麼,一直到第五週做 CPU 的時候才恍然大悟。因為 A-instruction 要載入一個 15bit 的值,但 register 是 16bit,原本想說要怎麼把 15bit 多加一個 bit 變成 16bit。後來才突然想到 A-instruction 因為是 0 開頭,所以整個 instruction 直接丟到 register 去就好,值是一樣的。

再來是第二週的 ALU,它可以做的操作很多,原本一直很好奇要怎樣才能指定做哪個操作,如果是程式語言,我的想像會是這樣:

if (op === 1) {
  return x
} else if (op === 2) {
  return y
} else if (op === 3) {
  return x+y
} else if (op === 4) {
  return x&y
}

可是電路基本上沒有這種 if 可以用,那該怎麼辦呢?

結果答案令我大吃一驚,是透過 6 個 control bit 對 input 做操作,而這 6 個 bit 的組合就可以產生出不同種想要的結果,詳情可見下圖:

而 ALU 的另外兩個 output:ng(輸出是否為負數)與 zr(輸出是否為零)原本看似無用,但其實是為了之後會碰到的 jump 做準備,這也是課程上到後面才會知道的事情。

總之呢,這堂課我覺得安排得很好,從最基礎的電路開始一直慢慢變複雜,同時也讓你學會機器語言跟組合語言,對電腦底層的東西熟悉了許多。

接著來講一下身為老師,這堂課裡面有哪些東西是值得在教學上借鏡的。

第一是客製化的工具,例如說他們為了這堂課特別開發出的 HDL 跟硬體模擬器,就是為了讓毫無基礎的初學者也能方便學習,這個很值得參考。

第二是作業的批改方式,在作業的資料夾裡面其實都有附上相對應的測試檔,藉由測試檔,學生就可以自己確認是否正確。

第三是作業的替代方案,在最後一週的作業裡,特別為不會寫程式的同學準備了另外一個方案,那就是手動翻譯程式碼,這個也可以學起來。

第四是課程的編排,雖然有講到電路但不會講到太深,因為太深的話就是電子電機的領域了,而不斷往前推進的課程編排也很棒,從 Nand 開始一路做到 CPU。

第五是課程順序的選擇,前幾週都是 bottom-up,由下往上慢慢建立觀念,到第四週突然由上往下,先寫組合語言再去組電腦,這樣的編排反而會讓學生更有感,在做電腦的時候已經對那些 machine code 有一定的熟悉程度。

第六是常見問題的處理方式,在每一個單元最後都有一個 Perspectives 的影片,由兩位教授來回答常見問題,利用這樣的方式統一回答省了滿多時間。

結語

無論你有沒有程式基礎,我覺得都可以試試看這堂課,在此誠心推薦給大家。

我自己是上 Coursera 的版本,完全免費,但若是要改作業拿證書的話要付 50 塊美金,為了支持這個課程我是二話不說就付了,不過要不要購買大家可以自己斟酌。

然後這只是 part1 而已,明年我要繼續來上 part2,等 part2 上完再來跟大家分享心得。之前金門大學資工系的教授陳鍾誠也有寫過心得文:Nand2Tetris 慕課記 -- 從邏輯閘到方塊遊戲,有興趣的朋友也可以參考看看。

最後,別再猶豫了,趕快去修吧!

關於作者:
@huli 野生工程師,相信分享與交流能讓世界變得更美好


#nand2tetris






訂閱電子報




Comment