---
# System prepended metadata

title: 計算機組識期中考考題精選 Autumn 2020
tags: [大三]

---

---
tags: 大三
---
# 計算機組識期中考考題精選 Autumn 2020
[![](https://img.shields.io/badge/最大連線數-7人%20@Nov%205%2022:28%20-green)](https://i.imgur.com/pUxbdjM.png) [![](https://img.shields.io/badge/dynamic/json?color=blue&label=%E7%B8%BD%E8%A7%80%E7%9C%8B%E6%95%B8&query=viewcount&suffix=%E4%BA%BA&url=https%3A%2F%2Fhackmd.io%2FjZfXixhrTmWPZzYY5IH_fQ%2Finfo)]() [![](https://img.shields.io/badge/%E5%91%BD%E4%B8%AD%E7%8E%87-0.00%25-yellow)](https://hackmd.io/jZfXixhrTmWPZzYY5IH_fQ)
<p id="blessing">祝大家考試都能超過100分</p>

> 精選歷屆考題中，較困難的部分

<style>
#blessing{
    font-weight: bolder;
    font-size: 2.5em;
    text-align: center;
    margin: 20px 0px;
    animation-name: bling;
    animation-duration: 8s;
    /*林子安0.01s是吸大麻哦*/
    animation-iteration-count: infinite;
}
@keyframes bling{
0%  {color: black;}
10% {color: brown;}
20% {color: red;}
30% {color: orange;}
40% {color: yellow;}
50% {color: green; }
60% {color: blue;}
70% {color: purple;}
80% {color: gray;}
90% {color: gold;}
}
</style>

## CPU time
1. Fill the boxes with the following terms:
> (1) Clock cycle time
> (2) CPU time
> (3) IC
> (4) CPI
> (5) MIPS
(　) = (　)×(　)×(　)
＞ Ans: CPU time = IC × CPI × Clock cycle time

## MIPS instruction & machine code
> 考試重點
> 1. RISC-V 轉機器碼
>    + R type
>      > 注意填的位置
>    + I type
>      > 計算相對位址
>    + J type
>      > 絕對位址左4右2去除
> 2. call function, jump and link
stack 類的題目及 `$ra` `jal` `jr`
> 

1. MIPS instruction `bgt rs1, rs2, label` performs a comparison on two signed integers stored in registers `rs1` and `rs2`, and it branches to the labled instruction if `rs1` is greater than `rs2`. However, `bgt` is a pseudo instruction and it is NOT actually implemeted in MIPS hardware. Instead, the assembler converts `bgt` into an equivalent instruction sequence using some real MIPS instruction. Show an instruction sequence equivalent to `bgt`, using 2 real MIPS instructions.

> slt (set less than)
> `R[rd] = (R[rs] < R[rt])? 1 : 0`
> Answer:
> **slt \$at, rs2, rs1**
> 
> (如果 rs1 比 rs2 大 $at會是 1, 若 rs1 與 rs2 一樣大 $at 會是 0，若 rs1 比 rs2 小 $at 會是 0)
> 
> **bne \$at, \$zero, label**
> 當 $at 不是 0 時，跳往 label

2. The folloing MIPS machine code refers to a MIPS floating-point instruction
`001110 10011 01010 1111111110101101`
What is the instruction?

> opcode 001110 → xori
> rs 10011 → \$s3
> rt 01010 → \$t2
> immidiate 1111 1111 1010 1101 (float)
> **xori \$t2, \$s3, -83**

3. Suppose that MIPS reserves four opcodes and uses the func field (bits 5 to bits 0) for instructions extension. In theory, what is maximum number of instructions that can be encoded after the extension?

> 這題有誰會... 答案 252
> $4\times2^6 - 4$
> 4個指令留給extension 各自有$2^6$種組合，扣掉原本四種不能用

4. Cross out the following *decimal* address that cannot become starting addresses of *double words*: 108, 736, 562, 197, 328 

> Answer: 108, 562, 197
> double words 一共有 8 個 bytes
> 因為 MIPS 採用 big endian 所以擺放一個 double words 時，記憶體位址分配如下：
> 8k, 8k+1, 8k+2, 8k+3, ..., 8k+7
> 因此答案選不是 8 的倍數的數字即可
> 圖：
> ![](https://i.imgur.com/0lH52Jg.jpg)
5. Suppose all the numbers are decimal. What value will be in register `$t1` after this instruction is executed: `lw $t1, 4($t1)`

|Register|	Value|	Memory Location|	Value|
|--------|-------|----------------|---------|
|t1|	1000|	1004|	1|
|t2|	31|	1005|	2|
|t3|	1008|	1006|	3|
|t4|	-5|	1007|	4|

> Answer
> `$t1` 值 1000
> `4($t1)` 代表 1004
> 將 1004 開始的 4 個 bytes 填入 `$t1`
> **注意：一個 bytes 由 2 個 16 進位組成**
> 答案為 0x01020304

6. Suppose (\$t1)=0xA0123456. Write down a shift instruction that is equivalent to a *signed divide* of register \$t1 by 256. (　ans1　). What is left in \$t1 after the divide?  (　ans2　)
> $256 = 2^8$
> We need right shift 8 times. Because this is a signed number, we need "arithmetic shift right" which is denoted by `sra` in RISC-V (`sar` in NASM instead)
> ans1: `sra $t1, $t1, 8`
> After right shift
> `0xFFA01234`
> | Original | A | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
> |--|--|--|--|--|--|--|--|--|
> | shift right 4 | F | A | 0 | 1 | 2 | 3 | 4 | 5|
> | shift right 4 again | F | F | A | 0 | 1 | 2 | 3 | 4|
> 
> 

7. in the following code, how many times is the memory accessed? count both instruction read and data read/write.
  > ```nasm
  > lw   $v1, 4($a0)
  > addi $v0, $v1, #1
  > sw   $v0, 0($a1)
  > ```
  > 讀取指令3次+lw,sw各有讀&存的功能總共2次
  > 3+2=5
  > Ans:5

## Adder 
1. Suppose an 8-bit ALU using a ripple-carry adder/subtractor. Give two examples of X-Y, represented in 8-bit binary numbers, that result in *unsigned overflow* and *signed overflow*. Circle the right flags of C, V, Z, N to check overflows, and specify their values.

> 這題經過我的一翻研究後
> 整理一下
> ALU 算完一共有四種 FLAG
> + Flag Z: zero flag (計算結果為零時設為 1) 
> + Flag V: overflow flag (以有號數來看若 overflow 則設為1)
> + Flag C: carry out flag (最後進位的那個位元可供無號數加減判斷有沒有溢位)
> + Flag N: sign flag (計算結果以 signed number 來看為負時設為 1)

> 有號數判斷有沒有溢位直接看 overflow 的 flag 就可以了
> 無號數判斷有沒有溢位的話看 carry out flag 相加時為 1 表溢位，相減時為 0 表溢位(相減時適用於二補數轉換後相加) <!-- (應該吧，我自己試出來的\~\~) 沒錯喔 是這樣-->




## Multiplier / Divider for int

> 這類的題目不難，以下注意
> 1. 講義中的乘法器與除法器只適用無號數
> 2. 乘法先加再右移
> 3. 除法先左移再減
 
## Error correcting code (ECC)

1. What is the SEC code for an 8-bit number 0xA3? (1010 0011)
    
> 先求出要用幾個 check bit 
> $$
> 2^n \geq C+D+1
> $$
> D = 8, C = 4
>
> | Bit position |  12  |  11  |  10  |  9   |  8   |  7   |  6   |  5   |  4   |  3   |  2   |  1   |
> | ------------ | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
> | position     | 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
> | check bit    |      |      |      |      |  C8  |      |      |      |  C4  |      |  C2  |  C1  |
> | data bit     | **1** D8  | **0** D7  | **1** D6  | **0** D5  |      | **0** D4  | **0** D3  | **1** D2  |      | **1** D1  |      |      |
> C1 = D7 xor D5 xor D4 xor D2 xor D1 = 0
> 
> C2 = D7 xor D6 xor D4 xor D3 xor D1 = 0
> 
> C4 = D8 xor D4 xor D3 xor D2 = 0
> 
> C8 = D8 xor D7 xor D6 xor D5 = 0
>
> Ans: 1010 0001 0100

2. Given a 12-bit SEC code 1010 1100 0110 with the rightmost bit as C1, which bit goes wrong?

> C1 = D7 xor D5 xor D4 xor D2 xor D1 = 0
> | Bit position |  12  |  11  |  10  |  9   |  8   |  7   |  6   |  5   |  4   |  3   |  2   |  1   |
> | ------------ | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
> | position     | 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
> | check bit    |      |      |      |      |  **1** C8  |      |      |      | **0** C4  |      | **1** C2  | **0** C1  |
> | data bit     |  **1** D8  |  **0** D7  | **1** D6  | **0** D5  |      | **1** D4  | **0** D3  | **0** D2  |      | **1** D1  |      |      |
> C1' = D7 xor D5 xor D4 xor D2 xor D1 = 0
> C2' = D7 xor D4 xor D6 xor D3 xor D1 = 1
> C4' = D8 xor D4 xor D3 xor D2 = 0
> C8' = D8 xor D7 xor D6 xor D5 = 0
> C' = 0010
> C = 1010
> C' xor C = 1000 = 8(dec)
> 第 8 個 position 出錯 C8 出錯


## IEEE 754

1. How many positive normalized numbers can be represented by IEEE 754 single-precision format? 
> sign: 0
> exponent: 00000000\~11111111 扣除 00000001 和 11111111
> 這個用高中教的列組合算一下知道了 $2^8-2$
> fraction: 23 bits 組合 $2^{23}$
> 用高一下教得排列組合隨便算一下得 $2^{23}(2^8-2) = 2^{31}-2^{24}$

2. What is the value of the smallest, nonzero, positive, denormalized number of the IEEE 754 double-precision formal?

> sign: 0
> exponent: 00000000000 (due to denormalized)
> fraction: 0000...0001 = $2^{-52}$
> 
> Answer: $2^{-52}\times2^{-1022} = 2^{-1074}$
> **補充**
> double-precision 的 denormal form
> $$
(-1)^{sign}\times 0.mantissa\times 2^{-1022}
$$
> 如果是 single 的指數是 -126 反正就是 bias (127) 再減 1
> 

3. Encode $-13.625\times2^{-132}$ in IEEE 754 single-precision format

> sign: 1
> mantissa: 13.625 = 1101.101
> exponent: -132+127 = -5
>
> 轉換一下
> sign: 1
> mantissa: 1101.101 (除以 2 的三次方)
> exponent: -5 (乘以 2 的三次方)
> 
> sign:1
> mantissa: 1.101101
> exponent: -5+3 = -2 = 11111110
> 
> Answer: 1 11111110 101101000....0
>

---

## Machine code 使用列表
![](https://i.imgur.com/Bx7UOBC.png)
![](https://i.imgur.com/ym9KogZ.png)
![](https://i.imgur.com/iF4ZVe8.png)

## ECC 計算方式

| Bit position | 12   | 11   | 10   | 9    | 8    | 7    | 6    | 5    | 4    | 3    | 2    | 1    |
| ------------ |:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| position     | 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 |
| check bit    |      |      |      |      | C8   |      |      |      | C4   |      | C2   | C1   |
| data bit     | D8   | D7   | D6   | D5   |      | D4   | D3   | D2   |      | D1   |      |      |

C1 = D7 xor D5 xor D4 xor D2 xor D1

C2 = D7 xor D4 xor D6 xor D3

C4 = D8 xor D4 xor D3 xor D2

C8 = D8 xor D7 xor D6 xor D5

## IEEE 754 整理
| type             | exponent           | fraction(mantissa) |
| ---------------- | ------------------ |:------------------:|
| normal           | 00...01 \~ 11...10 | 無限制                |
| denormal or zero | 00...00            | denormal:非零 zero:零                |
| infinity         | 11...11            | 0                  |
| NaN              | 11...11            | 非零                 |

---

<style>
#author{
    border: 1px solid gray;
    border-radius: 10px;
    padding: 10px;
    width: 80%;
    margin: 10px auto;
}
</style>
<div id="author">
<p>111級中興資工</p>
<p>作者：<a href="https://github.com/liao2000">廖柏丞</a>、<a title="aka 中興噁男" href="https://github.com/leonardo-lin">林子安</a></p>
</div>
