---
tags : 課餘資料
---
# Computer Architecture
:::spoiler 文章目錄
[toc]
:::
## Week 1
### 名詞:

- ISA:
==I==nstruction ==S==et ==A==rchitecture，又稱指令集或指令集體系。

- memory Cache:記憶體快取

- Moore's Law:
IC上可容納的電晶體數目，約每隔18個月便會增加一倍，性能也將提升一倍。摩爾定律是簡單評估半導體技術進展的經驗法則，其重要的意義在於長期。

- nibble:
半位元組。在計算機中，通常將8位二進制數稱為位元組，而把4位二進制數稱為半位元組。
- IEEE 754:
二進位浮點數算數標準，是20世紀80年代以來最廣泛使用的浮點數運算標準，為許多CPU與浮點運算器所採用。
- decimal:10進制(base 10)
- hexadecimal:16進制(base16)
- binary:2進制(base2)

- 處理器的指令集主要可分為 2 種:
- CISC（Complex Instruction Set Computer）:
用一個簡單舉例來示範，假如你叫你的電腦「開門」，複雜指令集電腦能立即了解您的意思，直接執行該動作，採用複雜指令集架構的處理器，可以執行需要好幾個時脈週期才能完成的複雜指令，最常見的複雜指令集架構產品，為「x86」處理器。

- RISC（Reduced Instruction Set Computer）:
假如你叫電腦去「開門」，精簡指令集則需要進一步說明：一、抓住把手，二、旋轉把手，三、推開（或拉開）門……常用架構為ARM、MIPS、RISC-V。

RISC的優點列舉如下：
1.指令長度固定，方便CPU解碼，簡化解碼器設計。
2.盡量在CPU的暫存器（最快的記憶體元件）裡操作，避免額外的讀取與載入時間。
3.由於指令長度固定，更能受益於執行線路管線化（pipeline）後所帶來的效能提升。
4.處理器簡化，電晶體數量少，易於提升運作時脈。比起同時脈的CISC處理器，耗電量較低。
RISC的缺點列舉如下：
1.複雜指令需要由許多的小指令去完成，程式變得比較大，記憶體也占用比較多，這在硬碟昂貴，常常使用磁帶儲存的時代來說，是個大缺點。
2.程式變長，代表著讀取工作變得繁重，需要更多的時間將指令從記憶體載入至處理器內。

- 補充
:::danger
*(此為記憶體使用的優先順序，還不夠明白 )*
:::
- [Pointers(指標)](https://kopu.chat/c%E8%AA%9E%E8%A8%80-%E8%B6%85%E5%A5%BD%E6%87%82%E7%9A%84%E6%8C%87%E6%A8%99%EF%BC%8C%E5%88%9D%E5%AD%B8%E8%80%85%E8%AB%8B%E9%80%B2%EF%BD%9E/)

### Number Representation:

- 0b11110:
前綴0b表示二進制，11110表30。
第一個bit表示正負，其餘一樣。>>==但會產生兩個0==
**解決方法**: Biased Notation(偏移表示法)

- 補充: [一的補數、二的補數](https://noob.tw/complements/)
- 一的補數:
以-*4*為例，首先先將 *4* 以二進位表示：*0100*。然後將每個 *1* 寫成 *0*、每個 *0* 寫成 *1*（其實就是NOT 運算），就會得到 *1011*。這就是一補數的作法。所以計算 *4−3* 時，其實就是用 *4* 加上 *3* 的補數，也就是 *0100* + *1100* 得到 *0001* （因為只有四個位元，所以 *10000* 溢位變成 *0001* ），換成十進位的 *1*。
最大負數: -2^(n-1)^-1
最大正數:2^(n-1)^-1

- 二的補數:
但如此表示會有兩個 *0* ，於是便產生了二的補數。以 *-3* 為例，首先先將 *3* 以二進位表示： *0011* 。然後先把每個 *1* 寫成 *0*、每個 *0* 寫成 *1*，得到 *1100*。（其實就是先算一次一補數）之後再加上一個 *1*，得到 *1101*。
最大負數:-2^(n-1)^
最大正數:2^(n-1)^-1
- MSB (most significant bit) 為最高有效位元、LSB (least significant bit) 為最低有效位元。
#### Overflow(溢位):
若在全為 *1* 的情況下加 *1* ，會因為位元不夠顯示而溢位，變為全 *0* 。

#### Sign Extension(符號擴展):
計算機算術中在保留數字的正負和值的同時增加二進制數的位數操作。
- 正數:正數來說相對容易(在數字前面全部加 *0*) ex: *0b1010* ，以*16* 位表示為 *0b00* *0000* *0000* *1010*
- 符號及值（sign & magnitude）:方法為在表示正負的位數後都加 *0* 。ex: *0b11* = *0b1001*
- 一的補數和二的補數:copy MSB。 ex: 10位的二補數*1111110001*(負*15*)，以*16*位表示為*1111* *1111* *1111* *0001*

#### Some Tips:
- 2^12^ = 2^2^ x 2^10^ = 4 x kibi
- Coventions
- 用許多常除法找出幾個2用到
- 二進制轉十六進制:先把他每個排成四個一組，就很好看ㄌ。
- 十六進制轉二進制:直接把每個數字用二進位表示即可。
- 二進制轉八進制: *8* 為 *2* 的 *3* 次方，於是變為 *3* 個一組，最左邊只有一個數字 *1* ，加假想的兩個 *0* 變為三個，就可直接用八進制表示。

- Bias Notation:
unsigned value + bias = "actual" value

- Two's Complement:
- 最前面的可以看成-8，直接相減即可。
- 也可先把*1*對調成*0*，再加*1*，得到答案為負數。


### C Memory Management(C語言執行時的記憶體配置)

#### C Memory: C Memory Layout (Stack, Static, Code)

- Stack:
儲存區域變數，其生命週期從其宣告開始至函式結束為止。(用**LIFO**模式儲存資料)，儲存空間會改變(動態記憶體，隨需要而改變)
- 在function內宣告的變數:存在stack裡面
- Heap:
動態記憶體，配置由**malloc**()函數來調整，使用這裡的記憶體主要是用在編譯時期還不知道大小或個數的變數。例如說，你需要用一個陣列，這個陣列的大小要在執行的時候由使用者的輸入來決定，那你就只能使用動態配置，也就是把這個陣列配置在heap中。

- Static Data(靜態記憶體):
儲存全域或靜態變數，儲存空間不會改變
- 在function外宣告變數:儲存在Static Data
- Code:
loaded when program starts(機器碼，由組合語言變成一連串數字，CPU可讀懂的語言)，does not change and read only
- 
- 以此圖為例，varGlobal存在Static Data，varLocal、*varDyn存在Stack
- 補充:
- LIFO manner:
==L==ast ==I==n ==F==irst ==O==ut(後進先出法)，如圖所示。
- [了解記憶體如何存放程式](https://ithelp.ithome.com.tw/articles/10239307?sc=iThomeR)
- [Literal到底是指？](https://ithelp.ithome.com.tw/m/articles/10271062)
- [三種記憶體區間:Global、Stack、Heap](https://note.artchiu.org/2015/10/21/%e4%b8%89%e7%a8%ae%e8%a8%98%e6%86%b6%e9%ab%94%e5%8d%80%e9%96%93-global%e3%80%81stack%e3%80%81heap/)
#### Addressing and Endianness
##### Addresses
- The size of an address(and thus，the size of a pointer)in bytes depends on architecture
- e.g. for 32-bit，have 2^32^ possible addresses
- if a machine is **byte-addressed**，then each of its addresses points to a unique **byte**(存放位址用byte表示)
- woed-addresses = address points to word
##### Endianness
- Big Endian:32-bit的整數存放記憶體位址順序為從左邊開始依序存到上層，專業一點就是MSB存到最高層的memory
- Little Endian:32-bit的整數存放記憶體位址順序為從右邊開始依序存到上層(左右顛倒)，專業一點就是LSB存到最高層的memory
- 以28~10~為例，28=0x00 00 00 1c
- Big Endian:
- Little Endian:
- Common Mistakes
- Endianness <font color="red">ONLY APPLIES</font> to values that occupy multiple bytes
- Endianness refers to <font color="red">STORAGE IN MEMORY，NOT</font> number representation
- Arrays and pointers still have the same order
- int a[5] = {1,2,3,4,5}，assume address is 0x40
- &(a[0]) == 0x40 & a[0] == 1
#### Dynamic Memory Allocation(Heap)
- Dynamically allocated memory goes on the <font color="red">Heap</font>，more permanent than Stack
- Need as much space as possible without interferint with Stack
- Start at opposite end and grow towards Stack(可參考上面圖)
- Use when we don't know size at compile time
- Use sizeof() to know the length。e.g. int x； sizeof(int); sizeof(x)
- Generally，we can't use sizeof to determine a length of an array，but there is an exception!
- int a[61];
- if write sizeof(a)，我將會得到裡面有幾個characters用來fill the array a.
- To get the number of elements，I can do:sizeof(a) / sizeof(int)
- This **ONLY** WORK FOR ARRAYS DEFINED ON THE STACK **IN THESAME FUNCTION**
##### Allocating Memory
- 3 functions for requesting memory: malloc(),calloc(),realloc()
- malloc(n)
- 在記憶體的動態儲存區分配n個byte的連續區域，未經過初始化(包含一些沒用的資料)
- 回傳分配區域的開頭指標，NULL表示failed request
- 不同blocks不一定要相鄰
- Using malloc()
- Almost always used for arrays or structs
- Can use array or pointer syntax 來使用
- Releasing Memory
- Release memory on the Heap using free()
- free ( p )
- 把指向p指標的分配內存刪除，通常配合malloc使用，malloc一次，free一次
- p必須為m/c/realloc()回傳的位址
- Don't call free()on a block that has already been released or on NULL
- calloc()
- void *calloc(size_t nmemb, size_t size)
- like malloc，但會將區域初始化為0
- nmemb is the number of members
- size is the size of each member
- ex: for allocating space for 5 integers
- realloc()
- realloc can move or keep the address the same
- 補充:
- [Struct為何?](https://ithelp.ithome.com.tw/articles/10282907)
- [malloc，calloc，realloc，free](https://blog.gtwang.org/programming/c-memory-functions-malloc-free/)
##### Common Memory Problems
1. 使用未初始化的值時
2. 使用錯誤記憶體
- Null or garbage data as a pointer
- De-allocated stack or heap variable
- Out of bounds(越界) reference to stack or heap array
3. Freeing invalid memory
4. Memory leaks

- Segmentation Fault(*More common in 61c*):
occur when attempts to access memory not allocated to it
- Bue Error(*Less common in 61c*):
invalid address alignment(accessint a multi-byte number at an odd address)
- C String Standard Functions Revised
- Memory Leaks
##### Linked List Example
[之後寫程式來看好了](https://www.youtube.com/watch?v=5yoJjjlTl4o&list=PLDoI-XvXO0aqxW0XGUcDl5r0m_eRU30C9&index=6&ab_channel=CS61CDepartmentalArchive)

### Floating Point
#### Scientific Notation
- Given 32 bits(*a word*)，what can we represent so far?
- Signed and Unsigned Integers
- 4 Characters(ASCII)
- Instructions & Addresses
*將10進制表示小數的觀念沿用到2進制*
*沿用科學記號觀念以統一格式 *
- Consider the number 1.011~two~ x 2^4^
- To convert to ordinary number，shift the decimal to the right by 4
- Result:10110~two~ =22~ten~
- For negative exponents，shift decimal to the left
- 1.011~two~ x 2^-2^ => 0.01011~two~ = 0.34375~ten~
- Go from ordinary number to scientific notation by shifting until in normalized from
- 1101.001~two~ => 1.101001~two~ x 2^3^

#### Floating Point Representation
- Use normalized、Base 2 scientific notation:
<font color="orange">+</font>1.<font color="brown">xxx.....x</font>~two~ X 2<font color="blue">^yyy......y^</font>~two~
- Split a 32-bit word into 3 fields:
- <font color="orange">S</font> represents <font color="orange">Sign</font> (*1* is negative，*0* positive，可想成*1*代表-*1*的*1*次方，*0*代表-*1*的*0*次方)
- <font color="blue">Exponent</font> represents <font color="blue">y</font>'s
- <font color="brown">Significand</font> represents <font color="brown">x</font>'s
##### The Exponent(指數) Field
- Use biased notation(偏移表示法) but with bias of -127(bias notation為中間數，參考Number Represention好讓0位於中間，255中間想成127)，之所以這樣做是因為在二的補數裡通常負數看起來會比正數還大，於是採用此做法
- 讀指數區時，將指數區視為 unsigned，但要加bias(+(-127))=-(127)
- Exponent Field: 0(00000000~two~) to 255(11111111~two~)
- but Actual Exponent: -127(00000000~two~) to 128(11111111~two~)
- 但在編碼時，需要==減==去bias(-(-127)) = +127，再以unsigned 編碼
- 以2^1^為例，此時exp(指數)為1=> 1+127=128 =>10000000~two~
- 以2^127^為例:exp為127 =>127+127=254 => 11111110~two~
- 
##### the Significand Field
- What does this mean?
- 想成:1 + Significand的值
- 由於Significand代表所有2的負次方數，因此Significand的總值必會小於1
- Example:1.<font color="brown">0101</font>~two~ = 1 + 2^-2^ + 2 ^-4^ = 1.<font color="brown">3125</font>
##### Double Precision FP Encoding
- Next multiple of word size(64 bits)
- Dunble Precision(V.S Single Precision)
- C variable declared as **double**
- Exponent bias is 2^10^ - 1 = 1023
- Primary advantage is greater precision due to larger Significand
#### Special Numbers
- Representing Zero
Two zeros! But at least 0x00000000 = 0 like integers
- Representing ± ∞
- 除以0
- ∞視為數字
- 可繼續做運算
- Representing NaN
- 0/0 、 sqrt(-4) 、 ∞ - ∞
- Useful for debugging
- Representing Very Small Numbers
- The normal numbers that are closest to 0(in here，normal means the exponent is nonzero)
- <font color="green">a</font> = 1. <font color="brown">0...0000</font>~two~ x 2^1-127^ = (1+0) x 2^-126^ =2^-126^
- <font color="green">b</font> = 1. <font color="brown">0...0001</font>~two~ x 2^1-127^ = (1+2^-23^) x 2^-126^ =2^-126^ + 2^-149^
- The gap between 0 and <font color="green">a</font> = 2^-126^
- The gap between <font color="green">a</font> and <font color="green">b</font> = 2^-149^
- 若要表達位於0 and <font color="green">a</font>之間的數字該如何表示?
- 解決方法:將前面的1拿掉!此時的數字稱為denormalized numbers(非規格化浮點數)
- Denorm Numbers:
- short for "denormalized numbers"
- No leading 1
:::danger
- implict exponent = -126 when Exp = 0x00(intuitive reason:the "binary point moves one more bit to the left of the leading bit")
:::
- Smallest denorm:<font color="yellow">±</font><font color="red">0</font>.<font color="brown">0.....01</font>~two~ x 2^-126^ = <font color="yellow">±</font>2^-149^
- largest denorm:<font color="yellow">±</font><font color="red">0</font>.<font color="brown">1...01</font>~two~ x 2^-126^ = <font color="yellow">±</font>(2^-126^ - 2^-149^)
- Smallest norm:<font color="yellow">±</font>1.<font color="brown">0...0</font>~two~ x 2^-126^ = <font color="yellow">±</font>2^-126^
- Floating Point Numbers Summary

- 補充: [何為浮點數](https://chi_gitbook.gitbooks.io/personal-note/content/floating_point.html)
#### Floating Point Linitations

##### Floating Point Gap

- adding 0x00000001 does not adding the same value to the floating point number，it's value depends on the exponent field
- ex:　　1.0~two~ x 2^2^ = 4　　1.1~two~ x 2^2^ = 6　=> +2
　　　1.0~two~ x 2^3^ = 8　　1.1~two~ x 2^3^ = 12　=> +4
- Distribution of values is denser toward zero
##### Floating Point Addition and representation
- FP(Float Point) is <font color="red">NOT</font> associative
- Small + Big + Small ≠ Small + Small + Big
- This is due to *rounding* errors:FP approximates results because it only has 23 bits for <font color="brown">Significand</font>
- FP cannot represent all integers
- e.g(example) 2^24^ + 1 = 16777216(FP)，but actual is16777217
- Question:
Big = 2^60^，Tiny = 2^-15^，BigNeg = -Big
1. (Big * Tiny) * BigNeg == (Big * BigNeg) * Tiny
2. (Big + Tiny) + BigNeg == (Big + BigNeg) + Tiny
- 1. is TRUE as Big * BigNeg doesn't overflow
- 2.左邊相加後會等於0，右邊等於Tiny，因此不等於。因將大大數加小小數時並不會改變他的指數，只會改變他的Significand，而FP的Significand field只有23bit，但二者差了75位，因此等於沒有改，(Big + Tiny)==Big
##### Conversions
- FP to Decimal
- Decimal to FP
- Hint:
- 先轉成整數，分成整數Part和小數Part，
- 小數用對照的，從大對到小，整數同
- 轉成2進制後，將其轉成1.多少 x 2^幾次^
- <font color="red">指數別忘記</font>減去bias(bias = -127)

## Week 2