---
# System prepended metadata

title: Tensor Compression
tags: [tinyML]

---

# Tensor Compression
###### tags: `tinyML`
###### members: 劉育任 林畊廷

### Time: 7/12/2021 - 7/19/2021

## 1. Successes Last Week
* Double check CSR indices size is correct and figure out the reason
* Implement COO format
* Changing weight pruning threshold: See 1) the number zeros 2) accuracy 3) CSR/COO compressed data size (ratio)
*  Figure out the weight pruning method of this paper: https://people.cs.nctu.edu.tw/~ttyeh/course/2020_Fall/IOC5009/file/week4-sparse-tensor-core.pdf

## 2. Progress and Problems Last Week
* There are three array in the CSR format, data, indices, and indptr. (data: save the non-zero data, indices: save the position, indptr: save the number of the non-zero data in each row.)
* Use scipy to implement the CSR format. There are three array to save the non-zero data, which is row, column, and data.
* ![](https://i.imgur.com/BUIGKnL.png)
* Sorts the elements in each vector by their absolute values layer by layer. Then we change at most k elements into zero. In the next layer, we will decrease the number k and pruned at most k elements again and again in order to ensure the accuracy.




## 3. Not Resolved Problems
* CSR/COO 字典和nonzero data大小 (KB)需要了解CSR/COO overhead
* Sparse tensor core所提到的sturctural sparsity是怎麼產生的 ?

## 4. Goals for next week

* 為什麼CSR/COO compression的比例比zero data增加的比例多這麼多 ?
    * 因為CSR/COO compression中有兩個array(data, indices)需要同時去存非零的資料，因此當我們model中的零變多時，壓縮的效果會比預期的好
* 找到一些weight pruning的方式去pruning model，比較CSR/COO壓縮weight的比例 (例如: 實作structural sparsity)
* 分析structural sparsity的accuracy
* 讀現在weight pruning的方式有哪些 ?
https://arxiv.org/pdf/1710.09282.pdf
---
### Time: 7/19/2021 - 7/26/2021
## 1. Successes Last Week
* 了解CSR/COO的overhead
* 找出weight pruning的方式有哪些
* Sparse tensor core所提到的sturctural sparsity是怎麼產生的 ?

## 2. Progress and Problems Last Week
* ![](https://i.imgur.com/JuAUpRu.png)
* Weight pruning methods:
    1. Pruning Filters for Efficient ConvNets:
        使用filter中參數的絕對值和∑∣Fij∣作為pruning的標準，減掉較不重要的filter
    2. Structured Pruning of Deep Convolutional Neural Networks
* 什麼時候COO比CSR好?
    * 當model的column數比row還要多時，COO壓縮model的效率會比CSR好
* 為什麼CSR indptr的大小不會隨著矩陣裡面的zero的資料多寡而改變?
    * matrix #of row 越多時，indptr會越高
* 為什麼CSR跟COO的data 和index的數量在同一個pruning paramter裡面都一樣?
    * 因為同一個model的非零data數目相同

## 3. Not Resolved Problems
* 找到一些weight pruning的方式去pruning model，比較CSR/COO壓縮weight的比例

## 4. Goals for next week
* 實做類似vector sparse pruning的方法
* 讀現在weight pruning的方式有哪些 ? 看看這個paper裡面有哪些weight pruning的方式然後去實做出來，比較CSR和COO在不同weight pruning方法下的壓縮率和accuracy
    * 整理出一個類似上面比較CSR/COO壓縮率/accuracy/非零資料比例表格
https://arxiv.org/pdf/1710.09282.pdf
---
### Time: 7/27/2021 - 8/1/2021
## 1. Successes Last Week
* 實作不同weight pruning的方法

## 2. Progress and Problems Last Week
* 實作weight pruning和比較他們的overhead和accuracy
* ![](https://i.imgur.com/eiPxVJr.png)

## 3. Not Resolved Problems


## 4. Goals for next week
* 實作CSB，DIA，ELL 稀疏矩陣壓縮，跟不同的pruning method和CSR，COO做比較
* 實作一下壓縮non-zero data方式
* idx(16bit) base table index(8bit) stride (8bit)
      15      00000001      0.001
* base table
      2

### Time: 8/2/2021 - 8/8/2021
## 1. Successes Last Week
* 實作不同weight pruning的方法

## 2. Progress and Problems Last Week
* 實作DIA,ELL, 和上週提到的nonzero compression method
* ![](https://i.imgur.com/GuXGIkR.png)

## 3. Not Resolved Problems
* 實作CSB，因找不到這個方法的相關資料

## 4. Goals for next week
* 實作CSB
* idx(16bit) base table index(8bit) stride (8bit)
* 弄excel

### Time: 8/9/2021 - 8/15/2021
## 1. Successes Last Week
* 整理表格
* 實作csb
* 實作 idx(16bit) base table index(8bit) stride (8bit)

## 2. Progress and Problems Last Week
* 各種壓縮方法overhead表格 https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit?usp=sharing

## 3. Not Resolved Problems
* 

## 4. Goals for next week
* check CSB (育任)
http://supertech.csail.mit.edu/papers/csb.pdf
* 如何用新方法處理FP16、INT8 (育任)
* 造一個sparse tensor(COO, CSF) (育任)
* 找支援稀疏矩陣格式的compiler (畊廷)
    [Sparse Tensor format in framework](https://hackmd.io/@ktlin/BJaRp0TgY)
* 了解mixed precision如何應用 (畊廷)
    [Mixed Precision Training](https://hackmd.io/@ktlin/SyTY8b2xK)
* 如何壓縮(儲存)多維sparse tensor(類似CSF) (畊廷)

### Time: 8/16/2021 - 8/22/2021
## 1. Successes Last Week
* check CSB
* 用新方法處理FP16
* 造一個sparse tensor

## 2. Progress and Problems Last Week
* 實作CSF
* 將stride改成FP16
## 3. Not Resolved Problems
* Varying length的idx和data，如果矩陣很小可以不需要用到16bit來記，但若是矩陣很大需要用超過16bit的時候該怎麼辦?
* 如何縮小non-zero data的encoding bit，如果數值不需要用32 bit，該怎麼知道把32bit轉成16bits? 如果數值一定要用32 bit的話，那要怎麼辦?
## 4. Goals for next week
* 對不同稀疏矩陣的資料進行壓縮，稀疏矩陣的資料從paper去找，比較不同壓縮格式的壓縮率，紀錄在google spreadsheet (育任)
https://hackmd.io/@nctu-cas-lab/ByKrKDAJt
* TACO，TVM Compiler如何辨識sparse data compression format (畊廷)
https://hackmd.io/@ktlin/S1Sv1bFZK

### Time: 8/16/2021 - 8/22/2021
## 1. Successes Last Week


## 2. Progress and Problems Last Week

## 3. Not Resolved Problems

## 4. Goals for next week
* 找不同的model做壓縮(育任)
* 比較pruning前後準確率、壓縮率(育任)
* 


* 比較不同格式對甚麼data比較好、優缺點 (畊廷)
    https://hackmd.io/@ktlin/r1sKIlCWK
* Format conversion具體在做甚麼，runtime做2件事
    - 決定format spec
    - 存取方式
### Time: 8/30/2021 - 9/05/2021
## 1. Successes Last Week
* 找不同的model做pruning、壓縮

## 2. Progress and Problems Last Week
* https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit#gid=715999071
## 3. Not Resolved Problems
* 比較pruning前後準確率
## 4. Goals for next week
* 比較pruning前後準確率(育任)
* 為何csr壓出來比coo差(育任)
* 整理不同壓縮方法適合哪種matrix(育任)
* 為甚麼要做不同format的轉換(畊廷)
* Automatic轉換的目的(畊廷)
---
### Time: 9/06/2021 - 9/12/2021
## 1. Successes Last Week
* 比較各種model pruning前後準確率
* check csr, coo壓縮差別

## 2. Progress and Problems Last Week
* https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit#gid=715999071
* 因為在壓縮四維的matrix當中的二維matrix太小，因此壓縮之後coo效率會比csr好
* 壓縮方法適合哪種matrix
    - COO格式常用於從文件中進行稀疏矩陣的讀寫
    - CSR格式常用於讀入數據後進行稀疏矩陣計算
    - DIA適合structured matrix
    - ELL壓縮的優點是快速

## 3. Not Resolved Problems
* 
## 4. Goals for next week
* 比較pruning前後準確率(育任)
* 為何csr壓出來比coo差(育任)
* 整理不同壓縮方法適合哪種matrix(育任)
* 為甚麼要做不同format的轉換(畊廷)
    - 加速data import 和 矩陣計算
        - COO對import data比較efficient，因為在增加nonzero時比較有效率(支援append or random insertion)
        - CSR則是做SpMV比較快 
* Automatic轉換的目的(畊廷)
    - Automatic的目的在於如果遇到library不支援某種format時如果我們要去access data需要hand-implement，他設計了一種方法，只要提供給它某些資訊，他就可以幫我們把code生出來。

### Time: 9/13/2021 - 9/20/2021
## 1. Successes Last Week

## 2. Progress and Problems Last Week

## 3. Not Resolved Problems

## 4. Goals for next week
- CSF implement (畊廷) - done
    https://hackmd.io/@ktlin/HymO-kCmY
- 找65536 * 65536 matrix - get part of the matrix from consph
- 找4096 * 4096 matrix
- 整個矩陣用CSR、COO、DIA壓
- 分塊壓縮 - save in txt file

### Time: 9/27/2021 - 10/04/2021
## 1. Successes Last Week
- CSR policy
[Result](https://docs.google.com/spreadsheets/d/1UWAjg39N8DAqq5NO_U1mTp4ILxIasQBubDWt9lIHo6w/edit?usp=sharing)
    - 和一般的COO、CSR、DIA比的話我們把存index的bit數降低用的memory比較少，但我們目前測試的dataset的matrix size都控制在我們設的bit數可表達的範圍內。
    - 我把csr的policy做進去，效果不太好，推測和切塊的方法或是我們切小塊後所省的memory比我們增加許多小塊所需的memory還少。
## 2. Progress and Problems Last Week
- Survey of tensor format
    ![](https://i.imgur.com/4l0AuQh.png)
## 3. Not Resolved Problems

## 4. Goals for next week
- 找可以用的資料集
- implement our method by using 8-bit and compare with other format
    https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit#gid=376338285

### Time: 10/05/2021 - 10/12/2021
## 1. Successes Last Week
- https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit#gid=1918013700  (育任)
- CSR format sparsity 100%仍會存indptr(= pos array)
- Chart
    - Compression ratio = after compressed / original
    - 4096 X 4096
        ![](https://i.imgur.com/cL13hNw.png)

    - 8192 X 8192
        ![](https://i.imgur.com/bN4Mtvo.png)

    - 16384 X 16384
        ![](https://i.imgur.com/lxvmbCm.png)
    - Mnist
        ![](https://i.imgur.com/b2eBv3s.png)


## 2. Progress and Problems Last Week

## 3. Not Resolved Problems

## 4. Goals for next week
- 測不同稀疏度在不同格式壓縮的結果

### Time: 9/27/2021 - 10/04/2021
## 1. Successes Last Week
- CSR policy
[Result](https://docs.google.com/spreadsheets/d/1UWAjg39N8DAqq5NO_U1mTp4ILxIasQBubDWt9lIHo6w/edit?usp=sharing)
    - 和一般的COO、CSR、DIA比的話我們把存index的bit數降低用的memory比較少，但我們目前測試的dataset的matrix size都控制在我們設的bit數可表達的範圍內。
    - 我把csr的policy做進去，效果不太好，推測和切塊的方法或是我們切小塊後所省的memory比我們增加許多小塊所需的memory還少。
## 2. Progress and Problems Last Week
- Survey of tensor format
    ![](https://i.imgur.com/4l0AuQh.png)
## 3. Not Resolved Problems

## 4. Goals for next week
- 找可以用的資料集
- implement our method by using 8-bit and compare with other format
    https://docs.google.com/spreadsheets/d/19JVwWNLF9U-XmpxtPiDS26kkNeXdBUXXHIArFpUsyNo/edit#gid=376338285

### Time: 10/13/2021 - 10/17/2021
## 1. Successes Last Week
- 分塊壓縮
    - matrix size 4096*4096
    - Compression ratio = after compressed / original
    - 4 bit
        ![](https://i.imgur.com/0UK6nb0.png)
        ![](https://i.imgur.com/02jKuZr.png)

    - 8 bit
        ![](https://i.imgur.com/YwkHs2Z.png)
        ![](https://i.imgur.com/56k2zQ4.png)

- CSB format
    - row, col ,data三個array去儲存每個block中的資訊
    - indptr去儲存每個block中的nonzero data 
    - CSB壓縮效率與CSR相同
## 2. Progress and Problems Last Week

## 3. Not Resolved Problems

## 4. Goals for next week

### Time: 10/18/2021 - 10/24/2021
## 1. Successes Last Week
* https://hackmd.io/@wtdf_NG5TQqy0k4CP2sZlg/HJQslkmUF
* https://hackmd.io/@ktlin/H1vRB__SF
* https://hackmd.io/@ktlin/B1NsbGnVK



### Time: 11/08/2021 - 11/15/2021
## 1. Successes Last Week
https://hackmd.io/@ktlin/Bk5Q-VKwK
## 4. Goals for next week
* 用256*256, 512*512, 1024*1024矩陣去測量不同sparsity做csb parallel, csb sequential, csb compression的時間

### Time: 11/16/2021 - 11/21/2021
## 1. Successes Last Week
* ![](https://i.imgur.com/MJMf2UQ.png)

### Time: 12/06/2021 - 12/12/2021
## 1. Successes Last Week
* https://docs.google.com/spreadsheets/d/1x9WOmDUupV4TVnZAu9Owez-Gb34MKp3_6UsFVtT8NkQ/edit#gid=0

### Time: 12/13/2021 - 12/19/2021
## 1. Successes Last Week
* ![](https://i.imgur.com/CmqISZI.png)





