Verilog심화(2) - FIFO (Single Clock)

이번 글에서는 디지털 회로설계에서 자주 사용된다고 알려져있는 FIFO(First In First Out)구조에 대해 설명하고자 합니다.

FIFO는, Data structure(자료구조)에서 Queue라는 이름으로 많이 알려져있습니다. 혹시나 자료구조를 듣지 않았다고 걱정할 필요는 없습니다. 알고있다면 이해가 빠르시겠지만 모르더라도 이번 글에서 다룰 내용을 이해하는데는 문제없으니까요.

FIFO라는 것은 직역하자면 '선입선출'로 시간 or 우선순위와 관련하여 data를 정리하고 이용하는 방식을 의미합니다. 자료구조에서는 시간의 개념을 넘어서서 priority(우선순위)를 기준으로 data를 출력하는 방식도 사용되지만 저희가 HW로 다룰 FIFO는 시간이 항상 우선순위인 구조를 의미합니다.

말 그대로 '먼저 들어온 것을 먼저 출력한다'는 의미입니다. 그렇다면 이게 어디에 쓰이는가 먼저 좀 알아보도록 하겠습니다.

위의 그림은 2015년도에 발표된 Google의 TPU(Tensor processing Unit)와 관련하여 학계에 올라온 논문 내용 중 일부입니다. 관심있으시다면 한번 읽어보시는 걸 추천드립니다. 오른쪽 그림의 파란색으로 감싸둔 부분에 무언가 직사각형 여러개가 붙어있는 부분이 있는데 이것이 바로 FIFO입니다. 논문에서는 이게 무엇인지 적혀있지 않을 정도로 당연스럽게 사용되고 있습니다. 아래의 다른 예시를 보시죠.

위의 그림은 또다른 AI용 연산을 위한 processor로 2016년부터 학계에 나타나기 시작한 NPU의 일종인 'Eyeriss'라는 하드웨어의 논문 내용의 일부입니다. PE(Processing Unit)가 외부의 통신을 위해서 FIFO가 interface로 사용되는데 논문에 적혀있는 내용은 다음과 같습니다.

"FIFO가 PE와 NoC 사이의 workload balance를 맞추기 위해 사용되었다"

PE가 뭔지, NoC가 뭔지는 중요하지 않습니다. 저희가 초점을 맞춰야 되는 부분은 workload balance입니다.

위의 그림과 같이 저희에게 Core0와 Core1과 같은 module이 존재한다고 생각해봅시다. Core0는 data1, data2, data3 ...이렇게 계속해서 data를 출력하고 있습니다. Core1은 해당 data들을 받아서 연산을 해야되는 module입니다.

그런데 문제점은 Core1이 지금 다른 일을 하고있다는 것입니다. 당장 data1, data2를 받을 수 없는 상황이라는 거죠. 그럴 때 어떻게 해야될까요? Core0에서 data를 나중에 보내면 되는거 아니냐는데 Core0는 모종의 이유로 지금당장 data1, data2, data3를 출력하고 나중에는 다른 Core를 위한 data를 또 생성해야합니다.

그럴때 사용하는 것이 FIFO입니다. data1, data2이렇게 출력되는 Core0의 data들을 FIFO에 잠시 담아두고 있다가 Core1이 준비가되면 data1부터 순차적으로 가져올 수 있게 중간다리, buffer의 역활로 사용됩니다.

이번 글에서 다룰 FIFO를 한번 살펴봅시다. 왼편이 input이고 오른편이 output입니다. wr_en과 rd_en은 각각 write enable, read enable로 FIFO에 값을 넣을 때 write를 한다고 표현하고, 값을 가져올 때 read를 해온다고 표현합니다. 자료구조에서 나오는 push와 pop 또는 enqueue, dequeue동작이라 생각하시면 됩니다.

data의 입력과 출력하는 port가 존재하고 full과 empty라는 port도 존재합니다. full과 empty라는 것은 FIFO라는 HW공간이 꽉차서 더이상 data를 받아드리지 못할 경우(full) 혹은 data가 들어있지 않아서 출력할 수 없는 경우(empty)를 외부에 알려주기 위한 용도로 사용됩니다.

Write동작은 다음과 같습니다. w_ptr라는 내부의 값이 존재하여 memory에 data를 적을 공간을 가르키고 있다가 wr_en이 1로 켜지면 clock에 맞춰 값을 집어넣고, w_ptr 값을 1 증가시킵니다. 위의 그림에서는 8칸짜리 FIFO가 존재하고, w_ptr이 0에서부터 7까지 증가하면서 data를 채워넣는 그림입니다.

Read동작은 다음과 같습니다. r_ptr라는 내부의 값이 존재하며 먼저 들어온 값을 가르키고 있습니다. 그러다가 rd_en이 들어오면 가르키고 있는 공간의 data를 출력하고 r_ptr값을 1 증가시킵니다. 해당 그림과 같은 경우에는 r_ptr이 처음에 0으로 data0부터 가르키고 있다가 7까지 증가하면서 data7까지 8개의 data를 출력하는 것을 나타내는 그림입니다.

그럼 FIFO내부의 w_ptr, r_ptr의 값은 몇 bit일까요? 8칸을 가르켜야 됨으로 3bit를 떠올리실 것 같습니다. 하지만 HW에서 FIFO는 3bit에서 1bit를 추가한 4bit를 사용합니다. 여기서 추가된 1bit는 msb로 full과 empty신호를 만들어내는데 사용됩니다.

위 그림처럼 w_ptr이 4bit로 4'b0111에서 1이 증가되면 4'b1000이 되는데 아래의 [2:0]까지 3bit는 그대로 3'b000으로 제일 첫번째 공간을 가르키게 되지만 msb는 1로 증가합니다. 이를 이용해서 w_ptr, r_ptr의 추가적인 1bit로 FIFO는 full과 empty 신호를 만들어내는데 아래의 예제를 보시면서 이해해보도록 하겠습니다.

해당 그림은 아무것도 들어가있지 않을 경우입니다. w_ptr, r_ptr 4bit모두 동일한 경우로 FIFO에 아무것도 없는 empty를 나타냅니다. 여기서 data가 들어가면(write, push) 어떻게 되는지 아래에서 확인해봅시다.

FIFO에 data0가 write되었습니다. w_ptr은 FIFO의 policy대로 1이 증가하였고 따라서 둘의 하위 3bit가 다릅니다. 해당 경우는 FIFO에 data가 들어가 있음으로 full도 empty도 아닙니다.하나를 더 적으면 아래와 같이 되겠죠.

자 이제 계속해서 data를 집어넣었고 FIFO가 가득 찬 경우를 확인해봅시다.

w_ptr이 4'b1000으로 바뀌었습니다. r_ptr은 그대로라서 4'b0000으로 고정되어있습니다. 하위 3bit를 살펴보면 둘다 모두 000으로 동일합니다. 하지만 msb는 1과 0으로 다릅니다. 이런 경우 FIFO는 full을 1로 출력합니다. 만약 data를 읽으면 어떻게 되는지 아래에서 살펴봅시다.

r_ptr이 1 증가하였습니다. 즉 다시 w_ptr과 r_ptr의 하위 3bit가 다르게 되었습니다. 이런 경우 full도 empty도 아닌 상태로 full, empty둘다 0을 출력하고 있습니다. FIFO는 계속해서 이런 방식으로 data를 관리합니다.

다음으로 넘어가기전에 마지막으로 r_ptr이 계속해서 data를 읽으면 언젠가 둘의 하위 3bit가 같고 msb가 같은 경우가 나타납니다. 즉 최초의 4bit가 동일한 empty상태가 되고 empty값을 1로 출력하게 됩니다. 이제 정리해보겠습니다.

• Empty condition : msb같음 & 하위 addr같음
• Full condition : msb다름 & 하위 addr같음
• Data 존재 : 하위 addr같음

동작을 여러번 보시고 체화하시는 것을 추천드립니다. 다음으로 spec을 다시 한번 확인해보도록 하겠습니다.

그럼 해당 FIFO가 어떤 구조일지 한번 고민해봅시다. 먼저 read, write를 해야 함으로 memroy가 있어야 합니다. 해당 memory는 FPGA의 BRAM이 될 수 도 아니면 register로 합성될 수 도 또는 SRAM을 이용할 수 도 있습니다(해당 실습에서는 reg로 그냥 합성할 것입니다). w_ptr, r_ptr이 1씩 증가하는 구조를 가지고 있음으로 counter가 존재할 것 같습니다. read write interface를 위한 mux와 decoder가 있을 것 같습니다. 이런 개념들을 하나하나 정리하면 아래와 같은 그림을 상상할 수 있게 됩니다.

그런데 여러분이 설계자라면 뭔가 이상한 느낌을 받으셔야 됩니다. "data를 나중에 써야되면 그냥 memory에 read하고 write하면 안되나?" 네 맞습니다. 실제로 많은 processor들이 Cache나 DRAM에 data를 적고 나중에 다시 읽어와서 여러 업무를 수행하니까요.

그런데 FIFO에 이점이 있습니다. 바로 'Address관리가 필요없다'입니다. 다시 생각해봅시다. Memory에서 data를 읽어오거나 쓰려면 어떻게 해야되나요? 주소값과 data를 주고 write enable신호를 줘야 합니다. 이건 write하는 module에서 안사용하는 주소값을 data와 같이 출력해줘야 하는데 그렇다면 address를 전송하기 위한 bandwidth증가, 에너지 소비 증가, address 출력을 관리하기 위한 core의 부담까지 증가하게 됩니다.
(더불어 memory와 외부의 interface가 줄어들기 때문에 timing 문제도 수월해집니다.)

그렇지만 FIFO는 어떤가요? 내부가 어떤지 모르지만 외부에서 보기에는 그냥 data를 전송해야되면 write enable만, data를 읽어오려면 read enable만 주면 됩니다. 물론 data를 시간 순으로 정렬된 형태로 밖에 못가져온다는 고정된 하나의 policy를 대가로 얻은 장점이긴 합니다. 이런 관계를 trade off라고 많이들 표현하죠. 하지만 많은 dataflow architecture에서 가져온 순서대로 data를 사용하는 경우는 많으니 효율성을 위해서 해당 구조를 많이쓴다고 생각하시면 됩니다.

반대로 저희가 흔히 부르는 DRAM(Dynamic Random Access Memory), SRAM(Static Random Access Memory)은 주소를 주면 해당 위치의 data에 접근할 수 있습니다. 이게 바로 Random Access Memory의 앞에 적혀있는 Random Access라는 개념입니다.

지루할 수 있는 이론을 잘 따라와주셔서 감사합니다. 다음은 실습으로 넘어가겠습니다.

코드를 작성해봅시다. 전체 TB를 포함한 전체 코드는 아래의 github링크에서 받아주시면 됩니다. 아래부터는 코드 분석하는 내용을 적어두었습니다. 따라 치셔도 되고, repo에서 코드를 받은 후에 검토하면서 보셔도 됩니다.

input, output port부분입니다. 위의 parameter로 DATA_WIDTH와 FIFO_DEPTH를 설정해줍니다. 여기서 중요한 것은 FIFO_DEPTH는 2의 승수여야 합니다(2, 4, 8 ...). 이유는 아래에서 설명드리겠습니다.

다음 FIFO의 write pointer와 read pointer의 bit수를 정해야 되는데 이를 FIFO_DEPTH로 만들어냅니다. clog2는 Verilog에 내재된 Macro의 일종인데 합성되기 전에 미리 전처리되어 변환됩니다. 동작은 괄호 내부의 값을 log2를 취하여 변환합니다. 여기서 예를 들어 DEPTH가 8이라고 예시를 들자면 clog2의 결과는 3이 나오게 되고 FIFO_DEPTH_LG2 = 3으로 localparam을 설정하게 됩니다.

왜 Depth가 2의 승수여야 할까요? 생각해보면 저희는 2진수의 pointer address를 counter로 순환시키면서 각각의 메모리에 접근하고 있습니다. 그런데 DEPTH가 2의 승수가 아닌 5, 6과 같은 DEPTH를 가진다면 Counter의 동작대로 FIFO를 계속 사용할 때 정상적인 w_ptr, r_ptr의 비교 동작이 불가능해집니다.

따라서 wptr과 rptr은 8칸을 관리하기 위해서 3bit와 추가적인 msb 1bit를 필요로 하기 때문에 [FIFO_DEPTH_LG2:0]로 선언하면 [3:0]으로 4bit를 선언할 수 있게 됩니다. 사용자는 이제 FIFO_DEPTH만 2의 승수로 설정해주면 resuable하게 코드를 사용할 수 있게됩니다.

다음은 FIFO의 write pointer와 read pointer를 관리하는 counter 부분입니다. block diagram처럼 write, read pointer를 위한 counter를 선언하고 wren과 rden으로 counter의 updata를 분기시키는 것을 확인할 수 있습니다.

다음은 memroy inteface부분입니다. 현재 코드에서는 register로 합성하고, write enable, read enable신호를 이용해서 간단히 data를 read, write하는 동작을 기술하는데 이 부분은 사용자가 사용할 sram이나 bram의 코드로 바꾸어 사용해도 됩니다.

위에서 말씀드린 것처럼 wptr, rptr의 msb는 memroy를 access하는데 사용되지 않습니다. 위의 그림처럼 4bit가 선언되어도 실제 memroy접근하는데는 3bit만 뽑아내서 사용한다는 점을 확인해주시기 바랍니다.

마지막으로 full과 empty를 생성하는 combination logic입니다. empty는 4개의 bit가 모두 같은지 확인하고 full은 msb가 다르면서 하위 3bit는 동일한지 확인함에 따라서 판단할 수 있습니다.

Waveform test 다음과 같습니다. reset으로 pointer들을 reset시키고, 0부터 7까지 data를 write하고, 0부터 7까지 값을 read해보는 testbench입니다. 정상적으로 full과 empty신호를 확인할 수 있습니다. testbench코드도 github에서 받을 수 있습니다.

참고로 미리 알아차린 사람도 있겠지만, FIFO의 memory에 reset은 필요가 없습니다. 어짜피 data의 사용여부는 FIFO의 wptr, rptr을 reset하는 것을 이용해서 관리되고, 새로운 data는 기존에 적혀있는 data를 overwrite하기 때문입니다. reset넣으면 안되냐는데 reset을 없애면 전력 측면에서 많은 이점을 얻을 수 있습니다.

이번 글을 마치면서 마지막으로 추가할 하나의 주제가 있습니다. 제목에 Single Clock이라는 용어를 보았을 것입니다. 당연히 Dual Clock FIFO도 있습니다. 이는 더 심화된 주제인데 CDC(Clock Domain Crossing)이라는 상황에 dataflow를 안전하게 buffering하기 위해서 사용됩니다. 해당 주제도 차후에 다룰 예정입니다.
(왼쪽 Eyeriss NPU dual clock domain for DRAM & Processor, 오른쪽 Dual Clock FIFO Block diagram)

CODE.

• Github repo
  https://github.com/gju06051/Verilog_study_public

REF.

• Queue사진
  https://upload.wikimedia.org/wikipedia/commons/thumb/d/d3/Fifo_queue.png/350px-Fifo_queue.png

• FIFO workload core 사진
  https://learnembeddedsystems.co.uk/wp-content/uploads/2021/02/Screenshot-2021-02-03-120445.png

• FIFO buffer사진
  SOC설계및실습(ECE4278-41) 김정래. lab4. DMA Engine 2

• Google TPU 논문
  ISCA '17: Proceedings of the 44th Annual International Symposium on Computer Architecture

• Eyeriss 논문
  IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. 52, NO. 1, JANUARY 2017