본문 바로가기
Digital Design/SoC

[SoC] Round-Robin Arbiter_LRG (Design with Verilog)

by 스테고사우르스 2023. 4. 26.

안녕하세요.

지난 글에서 Fixed History 기반의 Round-Robin Arbiter을 설계하였습니다.

 

Fixed History의 경우 공평하게 bus 사용권을 배분할 수 있겠지만 

아래의 케이스에서는 공평하지 않을 수 있습니다.

예를 들어, Master 4개 중

M0, M1, M2, M0, M1, M2, M0, M1, M2, M0 순으로 Grant 하다가

M0, M1, M2, M3의 요청이 동시에 들어왔다고 가정해보겠습니다.

어떤 Master부터 버스를 사용할 수 있을까요?

M0로 끝났기 때문에 M1, M2, M3 순으로 사용 가능할 것입니다.

M3의 경우 오래 전에 Grant 되었는데 아이러니하게도 가장 늦게 선택권이 주어집니다.

 

이 점을 보완한 것이 Least Recently Granted 알고리즘입니다.

가장 오래전에 Grant 되었던 M3를 먼저 승인해주는 구조를 가지고 있습니다.

 

오늘은 History Queue를 이용해서 이 LRG 기반 Round-Robin Arbiter를 설계해보겠습니다.

 

Architecture

먼저 상태도를 보겠습니다.

LRG history queue의 첫번째 채널에 "input으로 들어온 REQ_n"이 존재하는지 묻고 있습니다.

여기서 history queue가 필요하다는 것과,

이 queue의 LSB에 가장 오래된 데이터가 들어있다는 것을 알 수 있습니다.

MSB에는 가장 최근에 GNT된 데이터가 들어있겠죠.

 

예를들어 history queue의 LSB에 M0가 들어있을 때 REQ0이 들어오면 Yes 입니다.

들어있지 않으면 No겠죠.

 

이후 Yes라면, GNT할 마스터에 대한 정보를 history queue의 MSB에 넣어줍니다.

그리고 GRANT 해주면 됩니다.

 

No의 경우는 WAIT라고 써있는데 기다리진 말고,

두 번째 history와 비교해줄게요.

그래도 No면 세번째, 그래도 No면 네번째... 이어가면 됩니다.

순차적으로 가니까 MUX를 계층구조로 놓으면 되겠죠?

그럼 if else 구문으로 작성하면 좋을 것 같습니다.

 

if 문 내부는 queue[n]에 들어있는게 M0인지 M1인지, M2인지, M3인지에 따라 나뉘기 때문에

큰 MUX, 즉 case문으로 구성해 볼게요.

 

그럼 코드를 보겠습니다.

 

Verilog Code

DUT

module rr1 (
input i_clk,
input i_reset,
input i_req0,
input i_req1,
input i_req2,
input i_req3,

output reg o_gnt0,
output reg o_gnt1,
output reg o_gnt2,
output reg o_gnt3
);

parameter [3:0] m_0 = 4'b0001;
parameter [3:0] m_1 = 4'b0010;
parameter [3:0] m_2 = 4'b0100;
parameter [3:0] m_3 = 4'b1000;

reg [3:0] queue [0:3];
reg [1:0] shift_case;
reg shift_trigger;
wire [3:0] req = {i_req3, i_req2, i_req1, i_req0};
  wire [3:0] queue0 = queue[0];
  wire [3:0] queue1 = queue[1];
  wire [3:0] queue2 = queue[2];
  wire [3:0] queue3 = queue[3];


/* history queue
*  _____3________2_______1_______0________
  | recently | ... ..| .. .. | granted   |
  | granted  | ..->..| ..->. | long time |
  |__________|_______|_______|___ago_____|
1. REQn input
2. Is REQn in queue[0]? (!(queue[0] & req == 0))
	Yes: GNT, update(shift) history queue
	No: go to queue[1]
3. Is REQn in queue[1]?
	Yes: GNT, update(shift) history queue
	No: go to queue[2]
	.
	.
**Initial Value: queue <= {M3, M2, M1, M0} 
*/

always @ (posedge i_clk or negedge i_reset) begin
    if (!i_reset) begin
        {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0000;
	shift_case <= 2'b00;
	shift_trigger <= 1'b0;
    end
    else if (!((queue[0] & req) == 4'b0000)) begin
        case (queue[0])
	    m_0: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0001;
	            shift_case <= 2'b11;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_1: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0010;
	            shift_case <= 2'b11;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_2: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0100;
	            shift_case <= 2'b11;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_3: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b1000;
	            shift_case <= 2'b11;
		    shift_trigger <= ~shift_trigger;
	        end
	    default: begin
		         {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= {o_gnt3, o_gnt2, o_gnt1, o_gnt0};
			 shift_case <= shift_case;
			 shift_trigger <= shift_trigger;
		     end
	endcase
    end
    else if (!((queue[1] & req) == 4'b0000)) begin
        case (queue[1])
	    m_0: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0001;
	            shift_case <= 2'b10;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_1: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0010;
	            shift_case <= 2'b10;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_2: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0100;
	            shift_case <= 2'b10;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_3: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b1000;
	            shift_case <= 2'b10;
		    shift_trigger <= ~shift_trigger;
	        end
	    default: begin
		         {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= {o_gnt3, o_gnt2, o_gnt1, o_gnt0};
			 shift_case <= shift_case;
			 shift_trigger <= shift_trigger;
		     end
	endcase
    end
    else if (!((queue[2] & req) == 4'b0000)) begin
        case (queue[2])
	    m_0: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0001;
	            shift_case <= 2'b01;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_1: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0010;
	            shift_case <= 2'b01;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_2: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0100;
	            shift_case <= 2'b01;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_3: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b1000;
	            shift_case <= 2'b01;
		    shift_trigger <= ~shift_trigger;
	        end
	    default: begin
		         {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= {o_gnt3, o_gnt2, o_gnt1, o_gnt0};
			 shift_case <= shift_case;
			 shift_trigger <= shift_trigger;
		     end
	endcase
    end
    else if (!((queue[3] & req) == 4'b0000)) begin
        case (queue[3])
	    m_0: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0001;
	            shift_case <= 2'b00;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_1: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0010;
	            shift_case <= 2'b00;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_2: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b0100;
	            shift_case <= 2'b00;
		    shift_trigger <= ~shift_trigger;
	        end
	    m_3: begin
		    {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= 4'b1000;
	            shift_case <= 2'b00;
		    shift_trigger <= ~shift_trigger;
	        end
	    default: begin
		         {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= {o_gnt3, o_gnt2, o_gnt1, o_gnt0};
			 shift_case <= shift_case;
			 shift_trigger <= shift_trigger;
		     end
	endcase	
    end
    else begin
        {o_gnt3, o_gnt2, o_gnt1, o_gnt0} <= {o_gnt3, o_gnt2, o_gnt1, o_gnt0};
	shift_case <= shift_case;
	shift_trigger <= shift_trigger;
    end
end

//shift_case
always @ (shift_trigger) begin
    case (shift_case)
        2'b00: begin //when queue[3] POP
	           //No-op
	       end
        2'b01: begin //when queue[2] POP
	           queue[3] <= queue[2];
		   queue[2] <= queue[3];
		   //queue[1] <= queue[1];
		   //queue[0] <= queue[0];
	       end
        2'b10: begin //when queue[1] POP
	           queue[3] <= queue[1];
		   queue[2] <= queue[3];
		   queue[1] <= queue[2];
		   //queue[0] <= queue[0];
	       end
        2'b11: begin //when queue[0] POP
	           queue[3] <= queue[0];
		   queue[2] <= queue[3];
		   queue[1] <= queue[2];
		   queue[0] <= queue[1];
	       end
        default: begin
	           //No-op
	       end
    endcase
end

endmodule

웹 컴파일러를 썼더니 띄어쓰기가 이상한 부분이 있는데.. 양해 부탁드려요!

 

if문 안에 있는 !((queue[0] & req) == 4'b0000) 가 뭘까요?

받은 요청(req) 중에 queue[0]에 들어있는 Master가 있는가? 라고 이해하시면 됩니다.

비트연산자를 이용해서 쉽게 정리한 것입니다.

 

만약 queue에 M0를 뜻하는 0001이 담겨 있고 req가 1011이라고 해볼게요.

req는 req3 ~ req0까지 묶은 것이니까 M3, M1, M0의 req이 들어왔다는 뜻입니다.

이때 0001 & 1011 의 결과는 0001 입니다.

0이 아니죠? 따라서 if문을 실행하게 되는 구조입니다.

 

shift_case는 네가지로 구분하였습니다.

  • queue[0]에서 POP되면 전체 shift
  • queue[1]에서 POP되면 queue[0]를 제외하고 나머지 shift
  • queue[2]에서 POP되면 queue[1], queue[0]를 제외하고 나머지 shift
  • queue[3]에서 POP되면 그대로 유지

그리고 이 shift를 실행하기 위한 신호인 shift_trigger도 만들어 주었습니다.

 

 

Testbench

`timescale 1ns / 1ps
module tb_rr1();

reg i_clk;
reg i_reset;
reg i_req0;
reg i_req1;
reg i_req2;
reg i_req3;
wire o_gnt0;
wire o_gnt1;
wire o_gnt2;
wire o_gnt3;

rr1 rr (.i_clk   (i_clk),
	.i_reset (i_reset),
	.i_req0  (i_req0),
	.i_req1  (i_req1),
	.i_req2  (i_req2),
	.i_req3  (i_req3),
	.o_gnt0  (o_gnt0),
	.o_gnt1  (o_gnt1),
	.o_gnt2  (o_gnt2),
	.o_gnt3  (o_gnt3) );

always #5 i_clk = ~i_clk;

initial begin
    i_clk = 1'b0; i_reset = 1'b1;
    {i_req3, i_req2, i_req1, i_req0} = 4'b0000;
    rr.queue[0] = 4'b0001;
    rr.queue[1] = 4'b0010;
    rr.queue[2] = 4'b0100;
    rr.queue[3] = 4'b1000;  #1
    i_reset = 1'b0;         #1
    i_reset = 1'b1;         #8
    {i_req3, i_req2, i_req1, i_req0} = 4'b0110;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1010;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b0101;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1110;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b0011;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b0100;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1100;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1001;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b0111;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b0011;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1011;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1101;  #20
    {i_req3, i_req2, i_req1, i_req0} = 4'b1111;  #20
    $finish;
end
initial begin
    $dumpfile ("rrarbiter.vcd");
    $dumpvars();
end
endmodule

검증은 아직 어렵네요.

테스트 벡터는 최대한 다양하게, 많이 넣어주겠습니다.

 

Simulation

하나만 예시로 볼게요.

50ns에서 req0 (M0), req2 (M2) 가 들어왔습니다.

55ns인 clk rising edge 기준에서 history queue에는

{M1, M3, M2, M0} 가 담겨 있습니다. (오른쪽이 가장 오래된)

따라서 gnt0이 먼저 HIGH가 되고 (M0 grant),

gnt2가 나중에 HIGH가 되는 것을 볼 수 있습니다. (M2 grant)

 

 

'Digital Design > SoC' 카테고리의 다른 글

[SoC] DMAC_arbiter_top.v (최종)  (2) 2023.04.30
[SoC] Arbiter_Fixed Priority (Design with Verilog)  (0) 2023.04.30
[SoC] Round-Robin Arbiter_Fixed History (Design with Verilog)  (0) 2023.04.25
[SoC] DMAC LRG Arbitration (ARM DMAC Reference Manual)  (0) 2023.04.24
[SoC] Timing Violation (Setup/Hold/Skew/Jitter/해결법)  (1) 2023.04.14

관련글

댓글

티스토리툴바