# 2017q1 Homework5 (matrix)
contributed by < `twzjwang` >
作業說明: [B10: matrix](https://hackmd.io/s/rkrrpHm2e)
github: [twzjwang/matrix_oo](https://github.com/twzjwang/matrix_oo)

# 開發環境
- Ubuntu Ubuntu 16.04.2 LTS
Linux 4.8.0-36-generic

- cpu
version: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K

- memory
size: 4GiB

# 開發前
## Makefile
- 看不懂這個作業的 Makefile...
- [GNU make](http://www.gnu.org/software/make/manual/make.html)
### 語法
- 宣告變數
- `:=` 與 `=` 差別
- 如果重複宣告,使用 `=` 由 Makefile 中最後一次宣告決定
- 使用 `:=` 根據所在位置決定
- e.g.
- x 為 c

                a = b
                x = $(a)
                a = c

- x 為 b

                a := b
                x := $(a)
                a := c

- `？=` 與 `=` 差別
- 若 `?=` 前未宣告才宣告

- 規則

    target: dependencies
    <Tab>Commands

- 其他
- `@`+指令 ：不要顯示執行的指令。
- `$%` : it matches any target whatever
- `$@` : set to the name of the target
- main.c -> main
- `$^` : a list of all the prerequisites of the rule, including the names of the directories in which they were found, and the value of ‘$@’ is the target

- [字串函數](http://jukpan.blogspot.tw/2009/02/makefile_19.html)
- ` $(addprefix ,) `
- 名稱：加前綴函數——addprefix。
- 功能：把前綴加到中的每個單詞後面。
- 返回：返回加過前綴的文件名序列。
- 示例：$(addprefix src/,foo bar)返回值是「src/foo src/bar」。
$(join ,)

### 解析
- 宣告 `EXEC` `GIT_HOOKS` `OUT`

    EXEC = \
        tests/test-matrix \
        tests/test-stopwatch

    GIT_HOOKS := .git/hooks/applied
    OUT ?= .build

- `.PHONY` :
- .PHONY in Makefile
Make 主要的工作目標都是針對檔案，所以萬一你定義的工作目標並不是檔案，或是正好與檔案重複的時候，其實是會讓人丈二金剛摸不著頭的。
所以，.PHONY 被用來定義假工作目標，這樣 Make 就知道這不是針對檔案。[.PHONY](http://blog.xuite.net/tzeng015/twblog/113272262-.PHONY)
- `all`
- 只下 `make` 指令時的 target
- target ` $(GIT_HOOKS) ` ` $(OUT) ` ` $(EXEC) `
- $(GIT_HOOKS)

    @scripts/install-git-hooks
	@echo

- 宣告 `CC` `CFLAGS` `LDFLAGS`

    CC ?= gcc
    CFLAGS = -Wall -std=gnu99 -g -O2 -I.
    LDFLAGS = -lpthread

- 宣告 `OBJS` `deps`
- `OBJS` : stopwatch.o matrix_naive.o
- `deps` : stopwatch.o.d matrix_naive.o.d
- `OBJS` : .build/stopwatch.o .build/matrix_naive.o
- `deps` : .build/stopwatch.o.d .build/matrix_naive.o.d

    OBJS := \
        stopwatch.o \
        matrix_naive.o

    deps := $(OBJS:%.o=%.o.d)
    OBJS := $(addprefix $(OUT)/,$(OBJS))
    deps := $(addprefix $(OUT)/,$(deps))

- target `tests/test-%`
- 產生所有 `tests/test-%`
- dependencies : `$(OBJS)` 和 `tests/` 下所有 `test-%.c`

    tests/test-%: $(OBJS) tests/test-%.c
        $(CC) $(CFLAGS) -o $@ $^ $(LDFLAGS)

- target `$(OUT)/%.o`
- `$(CC) $(CFLAGS) -c -o $@ -MMD -MF $@.d $<`
- `-M` : Instead of outputting the result of preprocessing, output a rule suitable for make describing the dependencies of the main source file.
- `-MM` : link `-M`,(不包含header file)的訊息
- `-MMD` : link `-MM`,並輸出到 `.d` 檔
- `-MF file` : When used with -M or -MM, specifies a file to write the dependencies to
- target `$(OUT)`
- `@mkdir -p $@`
- target `check`

	@for test in $^ ; \
	do \
		echo "Execute $$test..." ; $$test && echo "OK!\n" ; \
	done

- target `clean`

    $(RM) $(EXEC) $(OBJS) $(deps)
	@rm -rf $(OUT)

- `-include $(deps)`
- If you want make to simply ignore a makefile which does not exist or cannot be remade, with no error message, use the -include directive instead of include, like this `-include filenames…`

# 開發
## 整合 `SSE`
- 移植 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx#avx-version) 中用 SSE 實做矩陣乘法的 code
- 實做 AVX2 部份因為 cpu 不支援暫時跳過
- 結果
- `$ make check `

    Execute tests/test-matrix...
    test : Naive
        equal!

    test : SSE
        equal!

    OK!

    Execute tests/test-stopwatch...
    OK!

- 使用 `stopwatch` 計時 (只計乘法運算部份)
- `$ make check `

    Execute tests/test-matrix...
    test     : Naive
    result   : equal!
    exe time : 0.000001 ms

    test     : SSE
    result   : equal!
    exe time : 0.000000 ms

    OK!

- 問題
- 只支援 4x4 大小矩陣
- 矩陣是否能相乘?
- e.g. 1 * 2 跟 3 * 4 不能相乘
- memory leak?
- ...

## 修改只支援 4x4 矩陣的限制
- 修改 `naive_priv` 結構

    struct naive_priv {
        float **values;
    };

- 修改 `static void assign(Matrix *thiz, Mat4x4 *data)`

    struct naive_priv *construct = malloc(sizeof(struct naive_priv));
    construct->values = (float **) malloc(thiz->row * sizeof(float *));
    for (int i = 0; i < thiz->row; i++)
        construct->values[i] = (float *) malloc(thiz->col * sizeof(float));
    thiz->priv = construct;

- 問題
- 不同大小的 matrix 呼叫 `static void assign(Matrix *thiz, Mat4x4 *data)` 時， 第二個參數 datatype 會不一樣
- 用多型很麻煩針對每個大小要重新定義
- 用 Union ，傳較小的矩陣會浪費空間( Union size 與 size 最大的變數相同)，並且要把所有可能的矩陣大小 (Mat1x1 Mat2x2 ...) 設為member
- 改變用其他結構

- 捨棄 `Matmxn` , 直接傳 二維陣列和大小
- `void (*assign)(Matrix *thiz, int row, int col, int **data);`

- 在 user interface 只要改變 `MatrixAlgo`,就可以切換矩陣運算方法

MatrixAlgo *matrix_providers[] = {
    &NaiveMatrixProvider,
    &SSEMatrixProvider,
};

MatrixAlgo *algo = matrix_providers[i];

- 加上驗證程式與測量效能
- 測試 1 * 1 到 512 * 512 時間,算 50 次取平均
- (SSE 仍只能處理 row 和 col 皆為 4 的倍數的矩陣乘法)
- 後面可嘗試將其他數字補至 4 的倍數解決問題
- 如 3 * 3 填到 4 * 4 不足的地方補 0

        1 1 1
        1 1 1
        1 1 1

=>

        1 1 1 0
        1 1 1 0
        1 1 1 0
        0 0 0 0

- 結果
- sse 時間遠低於 naive
- (下圖 x y 軸為 log scale)

n | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512
--|---|---|---|---|----|----|----|-----|-----|-----
naive(10^-6^ms)|0|0|1|2|7|54|366|2765|21930|230525
sse(10^-6^ms) |-|-|0|1|2|12|74|556|4966|45404
- 問題
- 處理不同 datatype 如 float
- SSE 仍只能處理 row 和 col 皆為 4 的倍數的矩陣乘法
- cache
- memory leak?
- data alignment
- thread-safe
- ...
:::info
記憶體管理的議題，可引入 reference counting 技巧，請見: [Generic C Reference Counting](http://nullprogram.com/blog/2015/02/17/) --jserv
:::

## 使用 `posix_memalign`
- 在記憶體沒有對齊的狀況下，可能會需要額外的 cycle 才能完整的抓取到資料。
- [Matrix Multiplication using SIMD 記憶體對齊](https://hackmd.io/s/Hk-llHEyx#記憶體對齊)
- [posix_memalign](http://man7.org/linux/man-pages/man3/posix_memalign.3.html)
- `int posix_memalign(void **memptr, size_t alignment, size_t size);`
- posix_memalign 配置 `size` bytes 給 `*memptr`
- 配置記憶體位置為 `alignment` 的倍數
- alignment 必須是 2 的次方
- alignment 也必須 `sizeof(void *)` 的倍數
- 如果 `size` 為 0, `*memptr` 的值可能為
- NULL
- a unique pointer value that can later be successfully passed to free(3).
- Attribute : Thread safety
- Value : MT-Safe
- can be freed using free(3)
- 結果
- 
- 使用 malloc 比較快
- 原因
- [malloc](https://linux.die.net/man/3/malloc)
- `The malloc() and calloc() functions return a pointer to the allocated memory that is suitably aligned for any kind of variable`
- 在 32-bit 的電腦上已經以 8 bytes 進行對齊，64-bit 的電腦則是已經以 16 bytes 對齊
- [Matrix Multiplication using SIMD 記憶體對齊](https://hackmd.io/s/Hk-llHEyx#記憶體對齊)

# Reference
- [你所不知道的C語言：技巧篇](https://hackmd.io/s/HyIdoLnjl)
- [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx#matrix-multiplication-using-simd)
- [GNU make](http://www.gnu.org/software/make/manual/make.html)
- [Makefile 語法筆記](http://wandachiang.blogspot.tw/2012/12/makefile.html)
- [Makefile 語法簡介](http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185)
- [字串函數](http://jukpan.blogspot.tw/2009/02/makefile_19.html)
- [GCC online documentation](https://gcc.gnu.org/onlinedocs/)
- [posix_memalign](http://man7.org/linux/man-pages/man3/posix_memalign.3.html)
- [Small-Size Optimization in C](http://nullprogram.com/blog/2016/10/07/)

###### tags: `twzjwang`