---
# System prepended metadata

title: Catatan Implementasi Q-Updater

---

---
title: Catatan Implementasi Q-Updater
description:
tag: Reinforcement Learning, Q Learning, Verilog
---

[ToC]
# Blok Q-learning Accelerator
Modul berikut merupakan salah satu modul utama dalam implementasi Q-learning. Modul ini merupakan realisasi persamaan matematis yang akan memperbarui nilai sebuah Q-value dalam Q-learning. Persamaan matematis yang direalisasikan adalah sebagai berikut.
![](https://i.imgur.com/NLOpWiv.png)

Persamaan tersebut telah disusun ulang untuk mengurangi jumlah operasi perkalian yang dilakukan dan dapat meningkatkan efisiensi dalam implementasi. Persamaan yang telah disusun ulang menjadi sebagai berikut.
![](https://i.imgur.com/Laqy7kJ.png)

Berdasarkan persamaan tersebut maka arsitektur modul Q-updater yang akan direalisasikan adalah sebagai berikut.
![](https://i.imgur.com/BpLAc0e.png)


Pada arsitektur diatas, kecepatan proses dibatasi oleh operasi perkalian. Karena itu, berdasarkan [1], operasi perkalian akan digantikan dengan *right shifter*. Untuk memaksimalkan akurasi akan diimplementasikan tiga *right shifter* untuk setiap operasi perkalian yang dilakukan.
:::info
Dengan tiga *right shifter*, rentang nilai α dan β adalah 0 sampai 0.875

0.XYZ~2~ = 2^-1^×X+2^-2^×Y+2^-3^×Z
:::

Karena itu, arsitektur modul Q-updater yang direalisasikan dalah sebagai berikut.
![](https://i.imgur.com/774NFde.png)

Untuk meralisasikan arsitektur diatas, dirancang juga subblok-subblok yang akan menyusun modul ini. Modul direalisasikan dengan menggunakan verilog dengan detail kode sebagai berikut.

:::spoiler Verilog Modul Q-updater
```verilog=
module qUpdater_32bit(
 input signed [31:0] Q, Qmax, rt,
 input [1:0] alfa_i, alfa_j, alfa_k, 
 input [1:0] gamma_i, gamma_j, gamma_k,
 output signed [31:0] Qnew
);
 wire signed [31:0] yi_a0, yj_a0, yk_a1;
 wire signed [31:0] a0_a1, a1_a2, a2_s0;
 wire signed [31:0] s0_alfa, ai_a3, aj_a3, ak_a4;
 wire signed [31:0] a3_a4, Qn;

//PortMap
 rShift_32bit yi(.Q(Qmax), .S(gamma_i), .Y(yi_a0));
 rShift_32bit yj(.Q(Qmax), .S(gamma_j), .Y(yj_a0));
 rShift_32bit yk(.Q(Qmax), .S(gamma_k), .Y(yk_a1));
 add_32bit a0(.in0(yi_a0), .in1(yj_a0), .out(a0_a1));
 add_32bit a1(.in0(a0_a1), .in1(yk_a1), .out(a1_a2));
 
 add_32bit a2(.in0(a1_a2), .in1(rt), .out(a2_s0));
 sub_32bit s0(.in0(a2_s0), .in1(Q), .out(s0_alfa));
 
 rShift_32bit ai(.Q(s0_alfa), .S(alfa_i), .Y(ai_a3));
 rShift_32bit aj(.Q(s0_alfa), .S(alfa_j), .Y(aj_a3));
 rShift_32bit ak(.Q(s0_alfa), .S(alfa_k), .Y(ak_a4));
 add_32bit a3(.in0(ai_a3), .in1(aj_a3), .out(a3_a4));
 add_32bit a4(.in0(a3_a4), .in1(ak_a4), .out(Qn));
 add_32bit a5(.in0(Q), .in1(Qn), .out(Qnew));
endmodule
```
:::

:::spoiler Verilog Submodul Adder
```verilog=
module add_32bit(
 input signed [31:0] in0, in1,
 output signed [31:0] out
);
 assign out = in0 + in1;
endmodule
```
:::
:::spoiler Verilog Submodul Substractor
```verilog=
module sub_32bit(
 input signed [31:0] in0, in1,
 output signed [31:0] out
);
 assign out = in0 - in1;
endmodule
```
:::
:::spoiler Verilog Submodul Right Shifter
```verilog=
module rShift_32bit (
 input signed [31:0] Q,
 input [1:0] S,
 output signed [31:0] Y
);
 assign Y = 
    (S == 2'd0) ? 32'd0 :
    (S == 2'd1) && (Q[31] == 1'b1) ? (Q >> S)|32'h8000_0000 :
    (S == 2'd2) && (Q[31] == 1'b1) ? (Q >> S)|32'hc000_0000 :
    (S == 2'd3) && (Q[31] == 1'b1) ? (Q >> S)|32'he000_0000 :
    (Q >>> S) ;
endmodule
```
:::

## Hasil Simulasi
Simulasi dilakukan pada 28 September 2021
![](https://i.imgur.com/C2XDd0y.png)

## 2. Modul Q-agent v0.5
![](https://i.imgur.com/NvXXmXe.png)
![](https://i.imgur.com/qLN6WX9.png)


:::spoiler Verilog Modul Q-agent v0.5
```verilog=
module qAgent_32bit(
        // *** clock ***
        input wire clk,
        // *** Q(st+1,A)
        input wire [31:0] Qin0, Qin1, Qin2, Qin3,
        // *** Q(st,A) ***
        output wire [31:0] Qout0, Qout1, Qout2, Qout3,
        // *** Qnew ***
        output wire [31:0] Qnew,
        // *** Q Updater Input ***
        input wire [31:0] rt,
        input wire [5:0] alfa, gamma,
        // *** Mux Input ***
        input wire [1:0] action
    );
    
    // Register for Q(st+1,A)
    reg [31:0] qReg0, qReg1, qReg2, qReg3;
    
    wire [31:0] muxOut, maxOut;
    
    //PORTMAP
    mux_32bit mux(
        .in0(qReg0), .in1(qReg1), .in2(qReg2), .in3(qReg3),
        .sel(action),
        .out(muxOut)
    );
    
    max_32bit max(
        .D1(Qin0), .D2(Qin1), .D3(Qin2), .D4(Qin3),
        .Y(maxOut)
    );
    
    qUpdater_32bit qUpdt(
        .Q(muxOut), //FROM MUX BLOCK
        .Qmax(maxOut), //FROM MAX BLOCK
        .rt(rt),//REWARD
        .alfa_i(alfa[5:4]), .alfa_j(alfa[3:2]), .alfa_k(alfa[1:0]), 
        .gamma_i(gamma[5:4]), .gamma_j(gamma[3:2]), .gamma_k(gamma[1:0]),
        .Qnew(Qnew)
    );
    
    //Delay operation
    always @ (posedge clk)
    begin
        qReg0 = Qin0;
        qReg1 = Qin1;
        qReg2 = Qin2;
        qReg3 = Qin3;
    end
    
    assign Qout0 = qReg0;
    assign Qout1 = qReg1;
    assign Qout2 = qReg2;
    assign Qout3 = qReg3;
endmodule
```
:::

:::spoiler Verilog Submodul Multiplexer
```verilog=
module mux_32bit(
 input [31:0] in0, in1, in2, in3,
 input [1:0] sel,
 output [31:0] out
);
 assign out =
  (sel == 2'd0) ? in0 :
  (sel == 2'd1) ? in1 :
  (sel == 2'd2) ? in2 :
  (sel == 2'd3) ? in3 :
                32'd00;
endmodule
```
:::

:::spoiler Verilog Submodul Max Block
```verilog=
module max_32bit(
 input [31:0] D1, D2, D3, D4,
 output [31:0] Y
);
 wire [31:0] max0_out, max1_out;
//portmap
 comp_32bit max0(.A(D1), .B(D2), .C(max0_out));
 comp_32bit max1(.A(D3), .B(D4), .C(max1_out));
 comp_32bit max2(.A(max0_out), .B(max1_out), .C(Y));
endmodule

module comp_32bit (
 input [31:0] A, B,
 output [31:0] C
);
 assign C = (A > B) ? A: 
            (A < B) ? B:
                      B;
endmodule

```
:::

# Blok Interpreter
Blok yang memodelkan *environment* sehingga dapat ditentukan *state* dan *reward* dari *action* yang ditentukan oleh *agent*. Dalam implementasinya blok ini terdiri dari dua subblok, `state decider` dan `reward decider`.

![](https://i.imgur.com/Hq17Iu6.png)

## Subblok Reward Decider
Subblok ini menentukan *reward* yang akan didapatkan oleh *agent* ketika mengambil *action* pada setiap *state*. Pada implementasi ini terdapat 4 nilai reward.
1. *Agent* akan mendapatkan *reward* -50 jika *agent* pindah ke *state* yang terdapat *demon*.
2. *Agent* akan mendapatkan *reward* -100 jika *action* yang diambil menyebabkan *agent* menabrak tembok.
3. *Agent* akan mendapatkan *reward* 100 jika *agent* pindah ke *state goal*.
4. *Agent* akan mendapatkan *reward* -1 untuk kondisi lainnya.

Dalam implementasinya, subblok ini terdiri dari tiga buah modul. 

![](https://i.imgur.com/3oBXNVy.png)
### Modul Reward Mux
`Reward Mux` berupa *multiplexer* yang memilih nilai *reward* yang akan diteruskan. Pada kasus implementasi ini, keempat *reward* dipilih berdasarkan nilai *selector* dengan aturan seperti tabel dibawah.
![](https://i.imgur.com/DMrNBLy.png =300x)

### Modul RSE
`Reward Selector Encoder (RSE)` akan menghasilkan nilai *selector* untuk memilih reward yang akan diteruskan. Modul ini menerima input, *reward selector row* yang menyimpan nilai *selector* untuk keempat *action* pada sebuah *state*. Modul ini hanya akan meneruskan nilai *selector* untuk *action* yang diambil pada *state* saat ini.
:::spoiler Verilog RSE
```verilog=
module rse(
    input wire [7:0] rsr, // Reward Selector Row, from Reward Memory
    input wire [1:0] sel,
    output wire [1:0] rSel //Reward Selector
    );
    
    assign rSel = (sel == 2'd0) ? rsr[7:6] :
                  (sel == 2'd1) ? rsr[5:4] :
                  (sel == 2'd2) ? rsr[3:2] :
                  (sel == 2'd3) ? rsr[1:0] :
                                      2'd0 ;
endmodule
```
::: 

### Modul Reward Memory
`Reward Memory` merupakan blok memori yang menyimpan nilai *selector* untuk seluruh *action* yang ada pada sebuah *state*. Masukan berupa *state* akan menjadi *read address* memori karena setiap baris menyimpan nilai *reward selector* yang ada untuk *state* tersebut. Nilai *selector* disimpan sebagai satu baris 8-bit dengan setiap 2-bit merupakan nilai *selector* untuk sebuah action. Sehingga setiap baris akan menyimpan 4 nilai *selector* secara berurutan. 
![](https://i.imgur.com/s6RUxbq.png)
Gambar diatas merupakan contoh isi memori berdasarkan *environment* yang harus dipelajari oleh *agent*.

## Subblok State Decider
Subblok ini menentukan *state* baru berdasarkan *action* yang diambil *agent* pada *state* saat ini. Pada kasus implementasi ini, agent harus berpindah state setelah melakukan action. Karena itu, ketika agent berada di pinggiran map dan mengambil *action* untuk keluar batasan *map*, maka *state decider* justru akan memindahkan *agent* ke arah sebaliknya. Misalnya digunakan map seperti dibawah. Ketika agent berada di S1 dan mengambil *action* keatas, maka agent justru akan berpindah ke S6.
![](https://i.imgur.com/3dKYbYy.png)

Dalam implementasinya subblok ini terdiri dari tiga buah modul.
![](https://i.imgur.com/p4wz9LQ.png)
### Modul Next State Generator
`Next State Generator (NSG)` akan menghasilkan *state* baru dengan menambah atau mengurangi nilai dari *state* saat ini sesuai dengan *action* yang diambil. Perilaku modul dapat dijelaskan oleh persamaan berikut.
![](https://i.imgur.com/18ecUlT.png)
:::spoiler Verilog NSG
```verilog=
module nsg(
    input wire [12:0] state,
    input wire [1:0] action,
       
    output wire [31:0] nextState
    );

    assign nextState = (action == 2'd0) ? (state - 32'd5):
                       (action == 2'd1) ? (state + 32'd1):
                       (action == 2'd2) ? (state - 32'd1):
                       (action == 2'd3) ? (state + 32'd5):
                                                   32'd0 ;
endmodule
```
::: 
### Modul Wall Detect
`Wall Detect (WD)` akan membuat action sebaliknya jika *action* yang ingin dilakukan oleh *agent* tidak diperbolehkan pada *state* saat ini. Action yang tidak diperbolehkan untuk diambil akan di-*invert*, misal dari `00` (keatas) menjadi `11` (kebawah).
:::spoiler Verilog Wall Detect
```verilog=
module wd(
    input wire en0, en1, en2, en3, //Wall Enable Row
    input wire [1:0] act,
    output wire [1:0] actOut
    );
    
    assign actOut = ((act == 2'd0)&(en0)) ? act :
                    ((act == 2'd1)&(en1)) ? act :
                    ((act == 2'd2)&(en2)) ? act :
                    ((act == 2'd3)&(en3)) ? act :
                                           ~act ;
endmodule
```
:::


### Modul Wall Memory
`Wall Memory` merupakan blok memori yang menyimpan nilai *enable* untuk semua *action* pada sebuah *state*. Masukan berupa *state* akan menjadi *read address* memori karen setiap baris menyimpan nilai *action enabler* yang ada untuk *state* tersebut. Nilai *enable* disimpan sebagai 4-bit dengan setiap bitnya merupakan nilai *enable* untuk sebuah *action*.
![](https://i.imgur.com/EozTe6i.png)
Gambar diatas merupakan contoh isi *wall memory* berdasarkan *environment* yang harus dipelajari oleh *agent*.

# Blok Policy Generator
Blok yang yang menentukan *action* untuk iterasi *agent* selanjutnya. Action ditentukan berdasarkan dua aturan:
- Secara acak 
- Berdasarkan Q-value paling besar dalam sebuah *state*

Pemilihan *action* dirancang sehingga pada tahap awal pembelajaran, *agent* akan cenderung menentukan *action* secara acak dan semakin mendekati akhir pembelajaran *agent* akan menentukkan *action* berdasarkan Q-value.

Dalam implementasinya, subblok ini terdiri dari dua buah subblok.
![](https://i.imgur.com/vcntSsW.png)

## Subblok Greed Action (GA)
Subblok `ga` akan menerima keempat nilai Q-value untuk sebuah *state* atau dapat disebut bahwa subblok ini menerima masukan berupa satu baris dari Q-Matrix. Dari Q-Value, yang diterima, akan dipilih terbesar sehingga akan dihasilkan *action* sesuai dengan nilai Q-value terbesar. Perilaku subblok dapat dijelaskan oleh persamaan berikut.
![](https://i.imgur.com/CZFOUOj.png)
:::spoiler Verilog GA
```verilog=
module ga(
    // *** Q-Value Inputs ***
    input wire [31:0] q0, q1, q2, q3,
    // *** Action Output ***
    output wire [1:0] act
    );
    
    wire [31:0] maxVal;
    
    //Port map
    max4to1 max(
        .in0(q0),
        .in1(q1),
        .in2(q2),
        .in3(q3),
        .out0(maxVal)
    );
    
    assign act = (maxVal == q0) ? 2'd0 :
                 (maxVal == q1) ? 2'd1 :
                 (maxVal == q2) ? 2'd2 :
                 (maxVal == q3) ? 2'd3 :
                                  2'd0 ;
endmodule
```
:::
## Subblok Action Decider
Subblok `actionDecider` akan memilih *action* yang akan diteruskan menjadi *action* untuk *agent* pada iterasi selanjutnya. Pemilihan ditentukan berdasarkan nilai *selector* yang diterima. Perilaku subblok dapat dijelaskan oleh persamaan berikut.
![](https://i.imgur.com/OTTamOD.png)
Untuk merealisasikan perilaku diatas, digunakan desain *multiplexer* 2-to-1 dengan lebar 2-bit.
:::spoiler Verilog Action Decider
```verilog=
module mux2to1(
    input wire [1:0] in0, in1,
    input wire sel,
    output wire [1:0] out0
    );
    
    assign out0 = sel ? in0 : in1;
endmodule
```
:::
<!-- :::spoiler kode verilog
```verilog=

```
::: -->
