# SystemVerilog : Testbench練習
[code](https://github.com/zBING-QIAN/Algorithm/tree/main/NTT)
這篇主要紀錄一下如何使用OOP的概念去寫testbench，這裡我選擇寫一個testbench驗證 捲積兩個1-D array取模P的演算法
## 演算法概念
兩個長度為n的array捲積操作直觀的來說要O(n^2)的複雜度，利用FFT則可以達到O(nlogn)，但是要處理虛數和捨入誤差之類的問題實在太麻煩，且input的數值都是整數的情況可以考慮使用Number Theroem Transform去處理，控制好modulo P的大小(避免overflow)可以使整個操作都在整數域上，且複雜度也是O(nlogn)。

* 這邊我設定array的長度為256，在不同的模數P下捲積(cyclic convolution)。也可以用128長度的array(後面補0)做非循環捲積。

詳細理論推導可以查[wiki](https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring)

## Software Simulation
這邊解釋軟體層面驗證算法的流程
### Naive convolution approach
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/SW/BasicConv.cpp)
就是最原始的捲積，方便後續產生測資和debug
### NTT convolution approach
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/SW/NTTConv.cpp)
這邊是使用257和12289當作模數，對應的原根為3,11在這個設定之下只要捲積的結果小於257*12289，都可以使用Chinese Remainder Theorem(CRT)還原出一般捲積正確的結果，所以如果長度為256，輸入值域就約只能是111(sqrt(12289*257/256))。
(因為257=256+1, 12289 = 48*256+1,所以選擇他們來當模數，對應的NTT kernel e為3和11^48 ，這樣3^256 = 1(mod 257), 11^(48*256) = 1(mod 12289) 滿足kernel的要求，不同模數元根的暴力求法可以[參考](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/SW/preset_ntt.cpp))
* 不過為求簡化，hardware實作我就沒有寫CRT，只單純做捲積mod p
### Compile and test - makefile
直接在SW路徑底下run make，會生成10筆測資，並比較暴力產生的結果和NTT的結果有沒有吻合

# Compiler and flags
CXX = g++
CXXFLAGS = -std=c++17 -O2 -Wall

# Executables
GEN = gen.exe
RUN = NTTConv.exe
BRUTE = BasicConv.exe

# Source files
GEN_SRC = gen.cpp
RUN_SRC = NTTConv.cpp
BRUTE_SRC = BasicConv.cpp

# Test directory
TEST_DIR = ./test_cases

# Number of test cases
NUM_CASES = 10

# Default target
all: $(GEN) $(RUN) $(BRUTE) test

# Compile rules
$(GEN): $(GEN_SRC)
	$(CXX) $(CXXFLAGS) -o $@ $<

$(RUN): $(RUN_SRC)
	$(CXX) $(CXXFLAGS) -o $@ $<

$(BRUTE): $(BRUTE_SRC)
	$(CXX) $(CXXFLAGS) -o $@ $<

# Create test directory if not exist
# $(TEST_DIR):
# 	mkdir -p $(TEST_DIR)


# Test rule: generate multiple inputs, run both programs, compare outputs
test: $(GEN) $(RUN) $(BRUTE) $(TEST_DIR)
	@echo Running $(NUM_CASES) test cases...
	@for /L %%i in (1,1,$(NUM_CASES)) do ( \
		echo == Test case %%i == & \
		$(GEN) $(TEST_DIR)\input_%%i.txt & \
		$(RUN) < $(TEST_DIR)\input_%%i.txt > $(TEST_DIR)\output_run_%%i.txt & \
		$(BRUTE) < $(TEST_DIR)\input_%%i.txt > $(TEST_DIR)\output_brute_%%i.txt & \
		fc $(TEST_DIR)\output_run_%%i.txt $(TEST_DIR)\output_brute_%%i.txt >nul && \
		echo Test %%i: Outputs match! || echo Test %%i: Outputs differ! Check input_%%i.txt \
	)

# Clean rule
clean:
	rm -f $(GEN) $(RUN) $(BRUTE)
	rm -rf $(TEST_DIR)

## 哈味 Simulation (Testbench)
SystemVerilog testbench
設計的思路會是使用兩個memory當作輸入，一個memory當作輸出。這邊使用interface去串接DUT和testbench，所以會有三個memory interface和一個DUT interface，另外要check NTT結果是否正確也會有NTT的interface從DUT接去testbench。
### Memory interface and class memory
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/aux_if.sv)
其中memory_if是為了連接DUT和TB，其中clocking block是為了模擬output delay 5 timescale。
另一個類似的memory_linker_if，主要負責DUT內部memory傳來傳去使用，如果DUT內使用memory_if，modelsim會爆出底下的錯誤
`Variable '/mytb/u_conv/u_ntt/rearrange_memif/valid' driven in a combinational block, may not be driven by any other process. See ./verification/aux_if.sv(17).`
[參考](https://verificationacademy.com/forums/t/driving-with-and-without-clocking-blocks/38008/8) 主要就是clocking block的問題，因為clocking block為了模擬delay所以提供了透過clocking block去drive output的signal，且output在always_comb中被assign(drive)，所以會被always_comb檢查出來output在不同地方被drive(always@(\*)則不會)，簡而言之always_comb會比較嚴格檢查是不是可合成的，always@(\*)則不完全，所以systemverilog要寫DUT要用always_comb和always_ff(雖然有時候會忘記哈哈)。可以參考[[Behavior difference between always_comb and always@(*)]](https://stackoverflow.com/questions/32778798/behavior-difference-between-always-comb-and-always)
class memory提供一個delay cycle的選項，方便不同memory條件做調整
### DUT/NTT interface
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/dut_if.sv)
由於主要的結果和資料都是透過memory_if存在memory裡面，所以這邊定一些簡易的控制signal像是clk,rst,enable,done。
### Environment
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/environment.sv)
負責初始化gen(產生data)，drv(負責控制DUT和蒐集結果)，scb/scb_ntt(負責計算groundtruth和比較結果)

### Driver(drv)
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/driver.sv)
這邊定義了整個verification的流程
1.先向gen要test case
2.rest DUT
3.等待第一組array做NTT
4.打包結果送給scb_ntt
5.等待第二組array做NTT
6.打包結果送給scb_ntt
7.等待前兩項結果內積並INTT
8.打包INTT結果送給scb_ntt
9.等待conv的結果
10.打包結果送給scb

### Generator(gen)
[code](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/generator.sv)
簡單地走個生測資的流程
由於modelsim要使用random()要有licence，但我就是個免費仔只好繞個彎路在[transcation](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/transaction.sv)自訂義一個random，另外systemverilog的random真的不好用，所以我改用DPI-C調用我用C++寫得函數產生測資。
簡單說一下DPIC定義時除了要定義參數類型，還要定義是input/inout，否則會發生各種問題。

### Scoreboard(scb/scb_ntt)
兩個基本差不多，主要就是用DPI-C去調用之前寫好的[C++函數](https://github.com/zBING-QIAN/Algorithm/blob/main/NTT/verification/NTTConv.cpp)然後驗證答案，優點是就不用重寫一次NTT和convolution，也不受限於開檔讀固定測資，只要`#include "svdpi.h"`並修改一些就可以使用。

// DPIC
#include "svdpi.h"
extern "C" bool SW_CONV_check(svOpenArrayHandle *a, svOpenArrayHandle *b, svOpenArrayHandle *a_res, svOpenArrayHandle *b_res, svOpenArrayHandle *res)
{
    int N = 256, P = 257, PRT = 3;
    // int N = 256, P = 12289, PRT = 11;
    int *aptr = (int *)svGetArrayPtr(a);
    int *bptr = (int *)svGetArrayPtr(b);
    int *aresptr = (int *)svGetArrayPtr(a_res);
    int *bresptr = (int *)svGetArrayPtr(b_res);
    int *resptr = (int *)svGetArrayPtr(res);
    vector<int> atmp(N, 0), btmp(N, 0), restmp(N, 0);
    for (int i = 0; i < N; i++)
    {
        atmp[i] = aptr[i];
        btmp[i] = bptr[i];
    }
    Conv(atmp, btmp, restmp, N, P, PRT);
    for (int i = 0; i < N; i++)
    {
        // if diff -> print error
        if (restmp[i] != resptr[i])
        {
            for (int j = 0; j < N; j++)
            {
                printf("SW : %d %d %d\n", j, restmp[j], resptr[j]);
            }
            return 0;
        }
    }

    return 1;
}
extern "C" bool SW_NTT_check(svOpenArrayHandle *a, svOpenArrayHandle *res)
{

    int N = 256, P = 257, PRT = 3;

    // int N = 256, P = 12289, PRT = 11;
    int *aptr = (int *)svGetArrayPtr(a);
    int *resptr = (int *)svGetArrayPtr(res);
    vector<int> atmp(N, 0), restmp(N, 0);
    for (int i = 0; i < N; i++)
    {
        atmp[i] = aptr[i];
    }
    NTT(atmp, restmp, N, P, PRT);
    for (int i = 0; i < N; i++)
    {
        // if diff -> print error
        if (restmp[i] != resptr[i])
        {
            for (int j = 0; j < N; j++)
            {
                printf("%d %d %d\n", j, restmp[j], resptr[j]);
            }
            return 0;
        }
    }
    return 1;
}

extern "C" void gencase(svOpenArrayHandle *a, svOpenArrayHandle *b)
{
    // srand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    int N = 256, P = 257;

    // int N = 256, P = 12289, PRT = 11;
    int *aptr = (int *)svGetArrayPtr(a);
    int *bptr = (int *)svGetArrayPtr(b);
    vector<int> atmp(N, 0), restmp(N, 0);
    // i< N/2 is for non cyclic convolution, otherwise i<N is for cyclic convolution
    for (int i = 0; i < N / 2; i++)
    {
        aptr[i] = rand() % P;
        bptr[i] = rand() % P;
    }
    cout << "a :\n";
    for (int i = 0; i < N; i++)
        cout << aptr[i] << " ";
    cout << endl;

    cout << "b :\n";
    for (int i = 0; i < N; i++)
        cout << bptr[i] << " ";
    cout << endl;
}

svOpenArrayHandle : 負責接dpic inout的array handler，要透過svGetArrayPtr轉成int*，這邊只處理1維最簡單的狀態，高維或複雜的資料的處理方式[參考](https://www.doulos.com/knowhow/systemverilog/systemverilog-tutorials/systemverilog-dpi-tutorial/)
另外就是不要想在systemverilog中操作C/C++的物件型態，即便有chandle可以用，chandle也只能傳給另一個DPI-C function去使用，如果想要在systemverilog使用就必須要用systemverilog的型態或結構去接值。

## 哈味 Simulation (Naive Implementation)
這邊說一下Decimation-in-Time(DIT)，在C++中要很麻煩的[預處理](https://github.com/zBING-QIAN/Algorithm/blob/4d852c678627dd56d7ff509535acf16daa1ccd38/NTT/SW/NTTConv.cpp#L26)位置，但是如果仔細觀察可以發現其實轉換的位置的binary representation是原位置的顛倒，舉個例子(長度為256的FFT):

    00000000 -> 00000000             00000100 -> 00100000    ... 
    00000001 -> 10000000             00000101 -> 10100000     ...
    00000010 -> 01000000             00000110 -> 01100000     ...
    00000011 -> 11000000             00000111 -> 11100000     ...

用硬體描述語言的話這一塊是相對容易寫的，可以在向momory要位置時做mapping:

for (i = '0; i < $clog2(DEPTH); i++) begin
  addr_r1[i] = addr_r0[$clog2(DEPTH)-1-i];
end

其他實作的部分就是很單純的硬寫出來，純苦力沒甚麼重點。

## Murmur
做完一件事真的要寫紀錄會比較好，像是SW模擬時input range老實說我一開始隨便估一下，沒特別考慮random的limit，所以一開始是設定128，為了要在這邊解釋清楚SW的模擬反而需要仔細算，才發現一開始亂設限制其實會錯(在不modulo的情況)，只不過random之後比較不會碰到那種爆掉的測資。
systemverilog寫起來就很像多執行續的程式，一開始做的時候常常會搞出deadlock，習慣之後就還可以，不過有可能是我用到的機制還沒有複雜到要處理active region,NBA region之類的dependency來debug，之後再看看會不會用到。