# 2017q1 Homework5 (matrix)
constributed by <`chenweiii`>

## Makefile
> 此份作業的 Makefile 有點難閱讀 orz [time=Sat, Apr 8, 2017 6:40 PM]

<br>

## 解除 4x4 限制，可以宣告 mxn 矩陣
> 回頭看前幾天寫的，根本不知道在寫殺小，重新整理。[time=Sun, Apr 9, 2017 4:53 PM]

### 修改的程式碼

typedef struct {
    int row, col;
    void *priv;
} Matrix;

typedef struct {
    Matrix *(*create)(int row, int col);
    void (*assign)(Matrix *thiz, int *data);
    bool (*equal)(const Matrix *l, const Matrix *r);
    bool (*mul)(Matrix **dst, const Matrix *l, const Matrix *r);
} MatrixAlgo;

> 參考了 <```twzjwang```> 大大的 code，才了解原本巨集 PRIV(x) 設計的哲學。但我仍無法解決若矩陣大小在 runtime 才知道，這項技術該如何調整使用？ struct naive_priv 在 compile time 就必須知道。 [time=Sun, Apr 9, 2017 12:04 AM]

* 在 MatrixAlgo 新增 create()，事先分配好矩陣 (mxn) 所需之記憶體。
* assign() 則須傳入欲 assign 的陣列之起始位址，讓裡面的資料複製進 Matrix object。
* 一開始不知道為什麼要宣告一個 void *priv，不直接宣告所需的 data type即可？應該是為了程式好擴充(以後也不需要再修改 matrix.h)。

struct naive_priv {
    int **values;
};

#define PRIV(x) \
    ((struct naive_priv *) ((x)->priv))

static Matrix *create(int row, int col)
{
    Matrix *m = (Matrix *) malloc(sizeof(Matrix));
    m->row = row;
    m->col = col;
    m->priv = malloc(sizeof(struct naive_priv));
    PRIV(m)->values = (int **) malloc(row * sizeof(int *));
    for(int i = 0; i < row; i++)
        PRIV(m)->values[i] = (int *) calloc(col, sizeof(int));
    return m;
}

* 為了能夠使用 mxn 矩陣，修改了 naive_priv，並在 create() 時注意 pointer to pointer 其要求空間的方式，讓其他函式需要修改的程式碼降到最低。

Matrix *m;
m = algo->create(4, 3); 
algo->assign(m, (int []) {
    1, 2, 3,
    5, 6, 7,
    1, 2, 3,
    5, 6, 7,
});  

* 修改後的賦值過程。

### 結果

Execute tests/test-matrix...
OK!

<br>

## 加入 SSE, AVX 等實作
> 使用 SSE 有個限制是 row 及 column 必須為四的倍數，解決方式應該可以添加零列或零行以湊到四的倍數。 [time=Sat, Apr 8, 2017 4:10 PM]
> 先把程式修改為 nxn 可運作，~~且 Matrix struct 裡頭的資料必須為連續的記憶體位置~~。 [time=Sat, Apr 8, 2017 11:01 PM]
> 為能直接移植 SSE, AVX，我先把原本的 data type 改為 int (._.) [time=Sat, Apr 8, 2017 11:17 PM]
> SSE 移植成功! [time=Sun, Apr 9, 2017 11:54 PM]

### 將行跟列湊到四的倍數

static Matrix *create(int row, int col)
{
    /* ... */
    int actual_row = (row % 4 == 0) ? row : row + (4 - row % 4); 
    int actual_col = (col % 4 == 0) ? col : col + (4 - col % 4); 
    /* ... */
    for(int i = 0; i < actual_row; i++)
       PRIV(m)->values[i] = (int *) calloc(actual_col, sizeof(int));
}

* actual_row & actual_col 是實際矩陣所拿的空間，並初始化為零。

### 移植 SSE
* 直接移植 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx) 的成果，並調整會用到的矩陣起始位置。
* 需要注意的是 Matrix dst 實際的大小，應是調整過後的大小
* e.g. A: 4x7, B: 7x5
* 實際大小: A: 4x8, B: 8x8, C:4x8
* 缺點: 浪費過多空間，在此例 dst 便浪費了 37.5% 的空間存放 0。

### 移植 AVX
* 移植 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx) 的成果
* 將行跟列改成湊到八的倍數
* 遇到的問題
* call _mm256_load_si256() 會產生 Segmentation fault
* 因為記憶體前面沒有去處理對齊，所以只能使用 _mm256_loadu_si256()
* 為什麼 sse 版本明明忘記處理對齊，仍能執行成功？因為 ...
> 影片有講! 但我忘記了，晚點補上。[time=Mon, Apr 10, 2017 1:20 PM]
> ~~TODO: free Matrix dst 未使用的記憶體空間。 [time=Mon, Apr 10, 2017 1:21 PM]~~

<br>

## 測量效能
* 撰寫產生亂數矩陣，並使用 stopwatch

int *random_matrix(int row, int col)
{
    int *src = (int *) malloc(row * col * sizeof(int));
    srand(time(NULL));
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            *(src + i * col + j) = rand();
    return src;
}

* 使用 stopwatch 計時運算時間

for (int j = 0; j < 5; j++) {
    MatrixAlgo *algo = matrix_providers[j];
    
    /* ... */
    
    for (int k = 0; k < SAMPLES_NUM; k++) {
        Stopwatch.start(ctx);
        algo->mul(&dst, l, r);
        Stopwatch.reset(ctx);
    }
}

* 各 implementation 運算不同大小矩陣之圖表 (SAMPLES = 30)

<br>

## 學習 crypto API