---
title: 第十一週
tags: 計概
---
下禮拜講講OS Internet

### 老師的有趣內容 - 1

:::warning
組語很難寫，所以os會用library 幫你做好

老師說，看一個paper，是看“策略”
例如
上次在做加法時，原本是RCA,後來演進到CLA的混合，核心概念就是大拆小，實現平行運算

也就是說，看一篇舊的論文，要看到的是核心的價值，他的“策略”，
這才是一輩子可以使用的東西

老師說以前pascal很powerful但是現在已經沒人在用了
:::

# Von Neumann Machine


:::info
- Automotor 會 go deeper
- Input device 早期是讀卡機，不像現在是鍵盤滑鼠
:::

## Stored Program Concept

將 Progam 也當作資料的一種給儲存起來，成為了現今所說的軟體

這個突破性的想法，解決了當時，特定機器只能用特定電路的困境
將 Program 給儲存起來後，要利用這些存起來的去寫其他 Program 就很方便

## Turing machine

老師這裡沒有細講
總之，相對於 Von Neumann Machine ， Turing machine 用 抽象的 {人工產物|artifact} 去描述簡單的電腦
主要用來分析 {邏輯架構|logical foundations}

而 Von Neumann Machine 則是現今大多數電腦的實際的架構與藍圖

### 老師的有趣內容 - 2

:::warning
- 老師又提到 CISC 跟 RISC，詳細的內容以及各個優缺點[參考這個]()
- RISC的重點在軟體身上，指令集比較簡單，可以以小搏大；比較好做
- 這也是ARM可以拿下手機市場的原因
- 老師說他覺得最近RISV-5的公司應該會蠻賺錢的
- 老師的 543 -1
- 老師說以前碩士要修計算機理論，他拿A+但是他不知道在上什麼，可能是他忘記了
:::

## The CPU-Memory Gap


因為硬碟跟 CPU 差太大，所以會有很多層級的 buffer 去緩衝


:::success
話說那個表只到 2000，不知道 SSD 的出現有沒有縮小跟 CPU 之間的差距
不過 2000年後也出了一堆很猛的 CPU，看來應該是沒有縮減
:::

### 老師的有趣內容 - 3

:::warning

- Cache、Buffer 也是一個“策略”
- Pyramid 的策略：越頂端的越少，越底端的越多
- L1跟L2快取，會有技巧地去讀取 CPU 「未來」需要的內容；現在也有人帶入機器學習，去預測要的內容
- 老師說以後做分散系統的時候，只要有速度差就一定要想到 Buffering

:::

## Memory Hierarchy

就是上面老師講的 Pyramid 策略


下圖的專有名詞應該要注意


# Hack Machine / Hack Computer

- 16 bit 的Von Neumann platform
- instruction memory 和 data memory 物理上是分開的
- 待會會說明這兩個是什麼樣的 記憶體
- 有一個螢幕
- 256 × 512 個格子，每個格子可以顯示黑與白
- 有一個鍵盤
- 標準的鍵盤
- 被設計用來執行以 Hack Machine Language 所編寫的程式
- 可以簡單的由到目前為止所學過的晶片組建構出來
- ？？？？真的假的

## Main parts of the Hack computer

- Instruction memory
- ROM：只能讀取；畢竟是儲存好的程式，要作為指令集使用
- Memory (RAM):
- 有三種 Memory
- Data memory
- 就是存資料用的
- Screen (memory map)
- 用來對映到螢幕用的
- Keyboard (memory map)
- 用來接收鍵盤訊號的
- CPU
- Computer
- 將全部東西串起來的電路

應該是用來讓初學者更好認識所創造的 CPU 架構


此課程著重在右邊的 Computer Architecture

## Instruction memory


Hack Machine Language：

out = ROM32K[address]

- 會事先讀取一些程式，這裡是指用 Hack Machine Language 所寫出來的程式
- 輸出 16 bit 的數值，告訴電腦現在該做甚麼，也就是 *current instruction*
- 這就是後面 PC 讀取 A 的值的部分
- 至於輸入為何是 15 bit 要搭配後面的圖才知道，原因是因為有一個 bit 的值是固定的

# Memory


這是 Memory 的概觀，從編程人員的角度；在此處有特定的大小
在這裡一個 word 是 16 bits

- Data memory
- 從頭開始數來 16K 個 words
- Screen (memory map)
- 接著數來 8K 個 words
- Keyboard (memory map)
- 接著數來 1 個 words

下圖就是實際物理上的位置


:::info
這三個記憶體區塊組成三個 Chip-part
RAM16K、Screen 跟 Keyboard chip-part
:::

## Data Memory

用來記錄數值用的


這裡老師沒有提到，但總之概念跟以前講記憶體的時候一樣
分為 Low-level (hardware) 跟 High-level (OS) 的 read/write logic

### Low-level

To read  RAM[k]:  
    set addressto k, //定址
    probe out  //輸出
To write RAM[k]=x:
    set addressto k, //定址
    set into x, //先將要存入的數放進一個「空間」裡
    set load to 1, // Load 就是之前提到的 Enable, 1 才允許寫入
    run the clock // clock 決定新資料要不要流過去

### High-level：

OS 都幫我們寫好了

To read  RAM[k]:
    use the OS command  out = peek(k)
To write RAM[k]=x:
    use the OS command  poke(k,x)

:::info
`peek` and `poke` are OS commands whose implementation should effect the same behavior as the low-level commands (in the sample computer)
:::

## Screen / Screen memory map


- 用來輸出螢幕要顯示的內容
- 讀取跟寫入邏輯跟上面的 Data Memory 一樣
- 會一直地刷新


在 Hach Computer 中的螢幕是 256 × 512 個 bit
而 512 = 32×16 = 32 個 words
所以 memory map 中每連續 32 個 words 代表一個螢幕中的 row

### Low-level (machine language)

搭配整數除法跟取餘數達到定址的功能

Screen[row*32+col/16] // col/16 目的是找到須修改的 word，整數除法有向下取整的功能
col % 16 bit // 可以找到該 word 中需要修改的特定 bit

### High-level：

使用 OS command

drawPixel(row,col)

### 老師的有趣內容 - 4

:::warning
- 很早期就是像上面所講，從記憶體讀一個映射表去顯示螢幕畫面
- 現在由於圖像越來越複雜也越來越大，所以有了 VGA 卡，也就是顯示卡，負責幫我們做映射這件事，而且為了讓畫面不斷，所以會有多個buffer ，會預先把下一個畫面給畫出來等等功能
- 此時的顯示卡跟現今的顯示卡不同，就只有做轉換的工作
- 但是隨著時代演進，為了更厲害的功能，像是畫圖等更細緻的東西，所以有了專門的 GPU，也就是顯示晶片，並因此有專門對 GPU 的指令集，也就是cuda
- 老師還問說，班上有沒有人有 4090...那種 5 萬多的東西應該不會隨便生出來
:::

::: info
- 老師說cuda不好寫，比Assembly 好一點點，如果會寫可以很好拿到intern
- 老師說，常用的可以用Assembly 寫成Macro
:::

:::success
如同維基百科所說：
*早期的顯示卡只是單純意義的顯示卡，只起到訊號轉換的作用；目前的顯示卡一般都帶有3D畫面運算和圖形加速功能，所以也叫做「圖形加速卡」或「3D加速卡」*
:::

## Keyboard


- 獲取鍵盤的輸入值
- 輸入值是鍵盤發送過來的特定的 Code，輸出值也是該 Code

例子


### Low-level (machine language)

直接讀取 Keyboard chip-part 的數值

### High-level：

使用 OS 的指令

keyPressed()

### 老師的有趣內容 - 5

:::warning
- 鍵盤因為只有一個 word，所以原本上必須要一直去檢查有沒有東西，否則沒讀取的會被新輸入的覆蓋掉
- 當有了 OS，會提供一個叫 Signal 的指令；不用 CPU 去一直檢查，有人會通知並打斷 CPU ，告訴 CPU 去接收鍵盤的訊號
:::
:::success
老師又提到我們這個世代很有可能是太空的世代，不然就是我們的下一代
:::

---

# CPU


- 內部
- 有三個暫存器 A、D 跟 PC
- 和一個 ALU
- 外部
- 接收 instruction，做出相對應的動作
- 就是前面 instruction 輸出的值
- instruction 有可能會操作到內部的 A 跟 D 兩個暫存器
- 有個暫存器 M ，代表 RAM[A]，也就是以 A 的值做為地址，取出該地址的值

:::success
這裡要搭配 Machine Language 介紹比較好
:::

---

# Machine Language

又叫 instruction set，就是把我們要電腦做的指令用 01 抽象地表示出來
而組合語言就是把特定的 01 片段用英文代號命名

- 組合語言： human-readable format of instructions
- 機器語言： computer-readable format (1’s and 0’s)

例如：`1010 0001 0010 1001` 對應組語就是 `ADD R1, R2, R9`

:::info
- 老師說機器語言的每個bit都有其意義在，跟control 高度相關，跟上次的ALU提到的一樣
- 不同的 cpu 會有不同的機器語言，但是在寫的時候只要寫組合語言就好，會有組譯器 assembler 幫我們編譯成對應的 binary code
:::
:::success
組合語言也有很多種，老師舉例 MIPS
- 拿來寫像是 Nintendo 等商業系統
- 學會一種後，學其他的就很快
:::
:::warning
老師說最近AI加速器需要類似compiler的工作
老師說幾十年的老技術現在還是很紅

當然，也可以在你的程式語言中寫入一些組合碼達到加速的效果
老師說C跟C++是一定要很熟的，不熟的就不是CS的學生

老師說David Patterson 的那本計算機結構的書，到現在還在用

老師說，自己寫的網路分析Query theorem，現在看到居然忘記了

老師也會，年久就忘記自己寫過的東西
所以讓自己容易記起來真的很重要
:::

# Hack computer

就是上面所提到的同一個 computer

- 這裡主要用到 Data(RAM) 跟 Instruction Memory(ROM)
- 三個暫存器 A、D、M
- A 就是 A
- D 就是 D
- M 是 RAM[A] 的意思
- 由 ALU 進行運算
- PC 來決定目前要執行甚麼工作，專門"指"到 ROM
- 兩個 Instrcution Set

:::danger
下面的兩個 Instrcution Set 只適用 hack machine
:::

# A instruction


- 是作為數值進來的唯一入口，雖然缺乏彈性，但是這樣處理起來比較簡單，線路也很簡單
- 低成本簡單比較好用但是缺乏彈性
- 總之就是要有些代價

- 組合語言：@value、機器語言 0vvvv.......
- 就是上下兩張圖的內容

- 不管是 C Instruction 要賦予某變數數值，還是 PC 要決定狀態，都要先把位置或值給讀進 A
- 也就是有關數值操作前都一定要先使用 A Instruction
- 使用 @ 符號，@ 就是 A 的意思
- 總之就只負責帶數值進來
- 第一個 bit 固定是 1 ，如上圖
- 這也是為甚麼不管是讀 Data 還是Instruction 都只有 15 個 bit 的原因


- D = M ：意思是 D = RAM[A]
- 就是上面所講的定義
- 因此這時 A 代表的意義就是某個位置
- JMP ：就是 Jump
- 可以同時伴隨大小等的於，請參照下面 C Instruction 的圖的右下角
- 目的是讓 PC 的位置跳到 A 目前的位置，也就是說跟上面的 D = A 一樣
- 也就是執行了 PC = RAM[A]
<!-- - 為了不要直接讓 PC = A -->
<!-- - 印象中好像是為了達到同步的作用 -->

## Addressing Mode

老師沒有細講，總之就是決定定址的方式

# C instruction

## 組合語言

先講組合語言的形式


左半邊說明式子可能的樣子
像是 AMD = A + D，就是讓 A、M、D 這三個暫存器的值存上 A + D 的結果
翻成文字來說的話就是 Set A,M,D to A + D

右半邊有一堆例子，其中如果是對記憶體操作的話，像是 Set RAM[53] to 171

首先必須要先把 171 放進 D 裡面，也就是要先操作 @171，跟 D = A
再來將 53 放到 M 裡面，這裡就用到 M 的特性，他會以 A 目前的值作為位置
所以要先把 53 存進 A 裡面 @53 ，再來就可以用 M = D 將 位置 53 的值修改為 171 了

## 例子：迴圈加總


### 初始化

`int i` 實際做的事情是，系統會給一個位置，並用 i 表示該位置
要讓 i 等於 1，跟上面的記憶體操作一樣，先把位置讀到 A 裡面，再用 M 去存；sum 也是一樣的

### 迴圈內容

- 首先是 `i<=100` 部分，這裡跟程式碼有不同之處
程式碼內部是判斷 i 有沒有小於 100；但是組合語言是判斷 i-100有沒有大於0
`D；JGT`中， JGT 就是前面提到 JMP 搭配大於的組合，Jump Greater Than，D 就是用來判斷的值
- 那要跳到哪呢？可以注意到前面一行是 `@END`，代表說我把 `END` 這項"動作"給存到 A 裏頭
`D；JGT` 判斷成功就是跟上面敘述的一樣，跳到 A 所指的位置存的值代表的指令
- 或者說，讓 `PC=RAM[A]=RAM[END]`，這裡的 END 就是前面說的 ROM
- 而 END 就是底下 `(END)` 下方的部分

- 再來是 `sum+=i` 部分，要做的操作是對 sum 的記憶體位置進行修改，所以要先把 i 的值存到 D 裡面；然後就是讀取 sum 並修改 sum 的值
- 修改後要跳回迴圈的開頭，所以跟剛剛跳 END 的方式一樣，先把"動作"存到 A：`@LOOP`
- 然後是一般的Jump： `0；JMP`，不過這裡的寫法跟上面的不一樣，是前面帶有分號的寫法
- 似乎是判斷前面的值是否為 0 ，為 0 的話就跳
- 因為在 END 底下也可以看到相同的 `0；JMP` ，註解是寫無限迴圈

## 機器語言


第一個是1，跟A相反；後兩個也是1

### comp

- 有 7 個 bit
- 第一個 bit 叫做 a ，用來判斷是要做 AMD 的哪種操作組合
- 後面 6 個 bit 就是該組合對應的二進制編碼
- 但是由於光這 6 個碼就可以定義超過所需的種類，所以 2,3 bit 才會是 1


### dest

- 是前面組合語言時提到的 dest 的部分
- 所以 comp 就是右邊算式的部分
- 由於種類更少，所以 3 個 bit 就夠了


### jump

- 只有組合語言中該行含有 JMP 家族的才會有值
- 可以看到沒有要 Jump 的話就是 000
- 種類也很少所以也只有 3 個 bit


## 例子

D = D - 1

| comp(a) | comp | dest | jump |
|:-------:|:------:|:----:|:----:|
| 0 | 001110 | 010 | 000 |

所以 D = D - 1 轉換成 Binary Code 就是 111 0001110 010 000

## 例子 JUMP ~~雜誌~~


- 似乎在比大小的部分，組合語言都會跟原程式碼不太一樣
- 像上面 Memory[3]=5，是藉由減法後跟 0 比大小，判斷是否等於

## 清晰的表


- 注意底下講的，D=D+1；JLT

---

# 練習


既然都寫著要練習了，那就來練習吧

- if D<9 goto 507

@9
D = D - A
@507
D；JLT

| sum | 2200 |
|:----:|:----:|
| x | 4000 |
| i | 6151 |
| END | 50 |
| NEXT | 120 |

- if sum > 0 goto END

@2200
D = M // D = RAM[2200]
@50 // @END
D；JGT

- x[i] = 0
- 這個是講義的寫法，但我不確定是不是講義寫錯了

@6165 // @i
D = A
@4000 // @x
A = A + D // 4000 + 6165 ?
M = 0

- 理論上 i 所存的值才是位移量才對，但不知為何講義寫直接位置加位置

- if x[i] <= 0 goto NEXT
- 這裡我採用 i 所存的值作為位移量

@ 4000 // start position of x
D = A
@6151
D = D + M // 4000 + i
@ 120
D；JLE

## WHILE


- 慢慢可以抓到那個感覺了，跟 for 一樣，都是先判斷 甚麼情況會是 END 之後才跳LOOP

## IF


下面這個用法好像很常寫
`@END`
`0；JMP`

---

# Memory Address

介紹如何存取記憶體

# Word-Addressable Memory (Another Assembly Language)

所謂的 Word ，跟上面映射表的不一樣，上面是 16 bit ，這裡是 32 bit


- 每個 word 有自己的位置
- 讀取記憶體的動作叫做 `load`
- 組語中符號是 lw ， 代表 load word
- `lw $s0, 5($t1)`
- $代表是一個變數，所以上面是 $s0,$t1這兩個變數
- $t1 是地址的 base, 5 是位移量
- 然後 $s0 去存 5($t1) 這個地址存的值
- Any register may be used as base address ?
- 不太確定這句的意思

# Byte-Addressable Memory (例如 MIPS)

word 一樣是 32 bit


- 跟上面不一樣，word 中的每個 data 有自己的位置
- 讀取記憶體的方式是 `load byte`,`store byte`
- 組語中符號是 lb 跟 sb ， 代表 load byte 跟 store byte
- 由於每個 word 有 4 個 byte，上圖中是 16 進制
- 所以「Word Address」每次遞加 4
- 所以 word n 的地址，或者說起始位置就是 4n
- 語法

---

# Big-Endian & Little-Endian Memory

- Big-Endian：從 MSB 開始讀跟儲存
- Little-Endian： 從 LSB 開始讀跟儲存
- 但是兩者的 word 地址是一樣的


兩個方法都有人在用，不過當資料要共享的時候，不同系統間就要注意


上圖是將 $t0 所存的值 0x23456789 在 Big-Endian 下給儲存到 起點點 0

如果改以 Little-Endian 讀取起始點 0 的 word，那這樣資料的內容會是反過來的

### 老師的有趣內容 - 6
:::warning
老師說平常os會幫你處理好這類的轉換問題

主要是當你拿到，或者說你去讀 raw data 時，就要注意這個問題，要去看相關的標準
通常在網路相關方面會遇到，像是 MPG 圖片的壓縮，老師舉例假如壓縮方式是
- 有三個 Data 連續排列是 ABC
- B的壓縮是從 A 跟 C 來的，所以解碼時就是從 A 跟 C 去解出 B
- 但如果是相反方向，得到的 B 就會不一樣
:::
:::info
這就是很久以前老師提到的，LSB 跟 MSB，究竟從誰開始
:::

<!--
PC永遠指向現在要執行的地方
A會是時候把位置移到PC

所以jump其實就是扮演d flipflop中，決定要不要讓clock on的角色
A的值是早就在前面等了

複合的運算可以先建一個temp -->

:::success
看open source 或是 linux
看他們怎麼操作file 還有command
變數的命名
:::