2018q3 Homework6
===
contributed by < `Jyun-Neng`, `LiuJuiHung` >
## Heat Maps
[Utilization Heat Maps](http://www.brendangregg.com/HeatMaps/utilization.html)
### systat
系統監控的工具
```shell
$sudo apt install sysstat
```
[mpstat](https://linux.die.net/man/1/mpstat) 的功能是顯示 CPU 相關的使用統計資訊
```shell
$export S_COLOR=always
$mpstat -P ALL
```
`S_COLOR=always` 對顯示的使用資訊用顏色區分
`-P ALL` 顯示所有 CPU 的資訊
## 測試環境
* 參考 [performance-5-18](https://hackmd.io/s/rkdzvWJTX)
```shell
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 42
Model name: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
Stepping: 7
CPU MHz: 1599.952
CPU max MHz: 3101.0000
CPU min MHz: 1600.0000
BogoMIPS: 6199.99
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-3
```
```shell
$cpupower -c 0 frequency-info
analyzing CPU 0:
driver: acpi-cpufreq
CPUs which run at the same hardware frequency: 0
CPUs which need to have their frequency coordinated by software: 0
maximum transition latency: 10.0 us
hardware limits: 1.60 GHz - 3.10 GHz
available frequency steps: 3.10 GHz, 3.10 GHz, 3.00 GHz, 2.90 GHz, 2.80 GHz, 2.70 GHz, 2.60 GHz, 2.50 GHz, 2.40 GHz, 2.30 GHz, 2.20 GHz, 2.10 GHz, 2.00 GHz, 1.90 GHz, 1.80 GHz, 1.60 GHz
available cpufreq governors: conservative ondemand userspace powersave performance schedutil
current policy: frequency should be within 1.60 GHz and 3.10 GHz.
The governor "userspace" may decide which speed to use
within this range.
current CPU frequency: Unable to call hardware
current CPU frequency: 1.60 GHz (asserted by call to kernel)
boost state support:
Supported: yes
Active: yes
25500 MHz max turbo 4 active cores
25500 MHz max turbo 3 active cores
25500 MHz max turbo 2 active cores
25500 MHz max turbo 1 active cores
```
更換 governor 為 userspace
```shell
$cpupower frequency-set -g userspace
```
將 cpu 頻率統一設在 1.6GHz
```SHELL
$cpupower frequency-set -f 1600MHz
```
執行測試程式時須多在`./(your app)`前面加以下指令 (須有 root 權限)
```shell
$taskset -c 0 nice --adjustment=-20 ./(your app)
```
目的為選定特定 cpu 及程式執行的優先順序。
## Problem 1
```clike=
#include <stdint.h>
int func(uint32_t x) {
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return x & 1;
}
```
以結論來說，`func` 會回傳 `x` 的 parity bit，也就是當有奇數個位元為 1 時，回傳 1。反之，回傳 0。其運作的原理可用下圖解釋。
每個有顏色的區塊代表 `x` 做完右移的值，而上下區塊則作 XOR 運算。最後第 1 個位元的值為全部位元做 XOR 的結果。
:::info
不明白這段程式要怎麼用 heat maps，要顯示什麼的分佈？
:notes: 考慮給定範圍內的輸入，還有實際執行時間 (注意測量的方法)
:::
### 測試程式
我們沿用 [dict](https://github.com/Jyun-Neng/dict) 中存取程式執行時間的方式，同樣的在我們的 `test.c` 中加入此函式。
```C
double tvgetf()
{
struct timespec ts;
double sec;
clock_gettime(CLOCK_REALTIME, &ts);
sec = ts.tv_nsec;
return sec;
}
```
我們針對不同的輸入區間觀察其運算時間。
### 未考慮現代處理器特徵(多核)
0-100
```shell
$make perf
```
```shell
Performance counter stats for './test 1' (100 runs):
219 cache-misses # 1.216 % of all cache refs ( +- 21.80% )
1,7970 cache-references ( +- 0.52% )
101,9461 instructions # 0.82 insn per cycle ( +- 0.14% )
124,3561 cycles ( +- 0.40% )
0.000959836 seconds time elapsed ( +- 18.23% )
```
```shell
$make plot
```
0-500000
```shell
Performance counter stats for './test 1' (100 runs):
11,0888 cache-misses # 49.880 % of all cache refs ( +- 0.38% )
22,2309 cache-references ( +- 0.38% )
14,2712,1084 instructions # 1.98 insn per cycle ( +- 0.01% )
7,2043,3421 cycles ( +- 0.03% )
0.295742723 seconds time elapsed ( +- 0.58% )
```
### 限定單核處理的測試結果
我們將 `make perf` 內的執行指令改為下面來限定在 cpu0 執行。
```shell
echo 3 | sudo tee /proc/sys/vm/drop_caches;
sudo taskset -c 0 nice --adjustment=-20 \
perf stat -e cache-misses,cache-references,instructions,cycles \
./test 1
```
我們所繪製的 heatmap x軸為輸入的數值範圍，y軸重複的次數
0-20
1000-1020
22200-22220
從這幾張的 heatmap 得到的結果為剛開始測試是熱點所在，主要是跟記憶體存取有關。
## Problem 2
### 題目：
考慮以下程式碼，予以行為解釋和提出測試案例。
```clike=1
#include<stdint.h>
int func(int32_t x)
{
int y = x >> 31;
return (y ^ x) + (~y + 1);
}
```
解讀上面的程式碼，可以先用 4-bit 資料舉例，其運算如下：
```
1 0 0 1 x (因 x 為有號數，所以此二進制的 "1001" 代表十進制的 "-7")
1 1 1 1 y = x >> 3
------------------
0 1 1 0 （y ^ x）
0 0 0 1 （~y + 1）
------------------
0 1 1 1 （y ^ x）+ (~y + 1) result "7"
```
### Shift operation (移位運算)
:::warning
探討為何 `1001 >> 3` 的結果會是 `1111` ，而不是 `0001`?
:::
* C 語言程式中的 shift operation 分成兩類
* Logical shift operation (邏輯移位運算)
* Arithmetic shift operation (算術移位運算)
* Logical shift operation
* 左移：
* 每個位元向左移動 `k` 個位置，丟棄最左邊的位元，最右邊填入 `k` 個 `0`
* ex: 1001 1000 << 1 ---> 0011 000`0`
* 右移：
* 每個位元向右移動 `k` 個位置，丟棄最右邊的位元，最左邊填入 `k` 個 `0`
* e.g. 1001 1000 >> 1 ---> `0`100 1100
* Arithmetic shift operation
* 左移：
* 每個位元向左移動 `k` 個位置，丟棄最左邊的位元，最右邊填入 `k` 個 `0`
* e.g. 1001 1000 << 1 ---> 0011 000`0`
* 右移：
* 每個位元向右移動 `k` 個位置，在左端補上 `k` 個最高的有效值
* e.g. 1001 1000 >> 1 ---> `1`100 1100
* 在 `CS:APP` `第二章 page40` 中有提到，C 語言中並沒有明確定義有號數應該使用哪一種類型的右移（`Logical shift` or `Arithmetic shift`），基本上幾乎所有的編譯器都對`有號數`使用 `Arithmetic shift operation`
### 結論
經過以上測試，此程式主要是將`負數`轉換成`正整數`，也就是實現`絕對值`的功能
```shell
Performance counter stats for './num2' (100 runs):
1004 cache-misses # 7.673 % of all cache refs ( +- 4.11% )
1,3080 cache-references ( +- 0.46% )
58,4762 instructions # 0.77 insn per cycle ( +- 0.23% )
76,1134 cycles ( +- 0.45% )
0.000724491 seconds time elapsed ( +- 1.53% )
```
### 限定單核處理的測試結果
我們所繪製的 heatmap x軸為輸入的數值範圍，y軸重複的次數
0-20
```shell
Performance counter stats for './test 1':
4112 cache-misses # 25.577 % of all cache refs
1,6077 cache-references
190,0272 instructions # 1.17 insn per cycle
161,9297 cycles
0.001382799 seconds time elapsed
```
1000-1020
```shell
Performance counter stats for './test 1':
5507 cache-misses # 33.179 % of all cache refs
1,6598 cache-references
192,5410 instructions # 1.15 insn per cycle
167,4817 cycles
0.001451787 seconds time elapsed
```
22200-22220
```shell
Performance counter stats for './test 1':
5819 cache-misses # 35.211 % of all cache refs
1,6526 cache-references
192,1155 instructions # 1.15 insn per cycle
167,6968 cycles
0.001461565 seconds time elapsed
```
## Problem 3
```clike=
int func(uint32_t x) {
uint32_t i = x;
i = i | (i >> 16);
i = i | (i >> 8);
i = i | (i >> 4);
i = i | (i >> 2);
i = i | (i >> 1);
i = ~i;
return i;
}
```
要解讀上面的程式碼，我們可以先用 4-bit 資料舉例，其運算如下：
```
A B C D i
0 0 A B i >> 2
------------------
A B (AC) (BD) i = i | (i >> 2)
0 A B (AC) i >> 1
------------------
A (AB) (ABC)(ABCD) i = i | (i >> 1)
```
由此我們會發現，這些運算會讓每個 bit 位置的結果都是所有大於等於當前位置的所有 bit OR 的結果。所以其目的是為了去分辨從 MSB 開始何時遇到第一個 bit 為 1。
:::info
一樣不明白這段程式要怎麼用 heat maps，要顯示什麼的分佈？
:::
```shell
2858 cache-misses # 26.876 % of all cache refs
1,0634 cache-references
51,8701 instructions # 0.62 insn per cycle
83,8578 cycles
0.009511835 seconds time elapsed
```
### 限定單核處理的測試結果
0-20
1000-1020
## Problem 4
### 題目
考慮以下程式碼，請分別寫出在 `big-endian` 和 `little-endian` 的機器上，程式碼執行結果為何。
```clike=1
#include<stdio.h>
#include<string.h>
int main()
{
char c[4];
unsigned int i = 0x12345678;
memcpy(c,&i,sizeof(i));
printf("0x%x 0x%x 0x%x 0x%x\n", c[0], c[1], c[2], c[3]);
}
```
```
big-endian : 0x12 0x34 0x56 0x78
little-endian : 0x78 0x56 0x34 0x12
```
### Big-endian and little-endian
現在的 CPU 中最常見的位元組順序有兩種，分別是 `big-endian` 和 `little-endian`
* `big-endian` ： 是指將資料放入記憶體的時候，最高的位元組會放在最低的記憶體位址
* `little-endian` ： 與 `big-endian` 相反，是將最高位元組放在最高的記憶體位址中
```shell
Performance counter stats for './num4' (100 runs):
1028 cache-misses # 7.801 % of all cache refs ( +- 4.39% )
1,3181 cache-references ( +- 0.58% )
58,9949 instructions # 0.76 insn per cycle ( +- 0.48% )
77,4479 cycles ( +- 0.67% )
0.000761556 seconds time elapsed ( +- 1.54% )
```
## Problem 5,6
```clike=
#define CHECK(e) (sizeof(struct { int:-!!(e); }))
int main() {
int a = 2;
return CHECK(a == 2);
}
```
### Macro `CHECK`
這個 macro 在 linux kernal 中有類似的用法 [linux/kernel.h](https://github.com/torvalds/linux/blob/ff2d8b19a3a62559afba1c53360c8577a7697714/include/linux/kernel.h#L677-L682)
針對這個 macro 的說明 [BUILD_BUG_ON_ZERO](https://stackoverflow.com/questions/9229601/what-is-in-c-code?answertab=active#tab-top)
* 功能
檢查 e 是否為 0
* 為什麼要用這個 macro 來檢查 e 是否為 0?
相較於其它用法，這樣的做法可以在 compile time 就得知結果而不需等到 runtime。
* 解讀 `CHECK(e)`
`int: ()` 為 bit-field 的定義方式。
`-!!(e)` 若 e 不為 0 則結果為 -1。反之，結果為 0。
`struct { int:-!!(e); }` -> `struct { int:0; }` or `struct { int:-1; }`
> 6.7.2.1-3
> The expression that specifies the width of a bit-field shall be an ==integer constant== expression with a ==nonnegative value== that does not exceed the width of an object of the type that would be specified were the colon and expression omitted. If the value is zero, the declaration shall have no declarator.
若 `e` 不為 0 則在編譯的時候會產生如下錯誤訊息：
```shell
error: negative width in bit-field ‘<anonymous>’
```
因為根據 C99 規格書 6.7.2.1 第 3 點 bit-field 的寬度不可為負數。
而上面的程式碼在編譯時會產生另一種錯誤訊息如下：
```shell
error: bit-field ‘<anonymous>’ width not an integer constant
```
同樣根據 C99 規格書 6.7.2.1 第 3 點 bit-field 的寬度應該是常數而 `e` 在上面的程式碼在編譯時會被替換為 `a == 2`，但 `a` 並非常數。
Sign in with Wallet
Connect another wallet