---
tags: 大三
---
# 計算機組識期中考考題精選 Autumn 2020
[](https://i.imgur.com/pUxbdjM.png) []() [](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 的倍數的數字即可
> 圖：
> 
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 使用列表

## 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>