FIFO 깊이 계산기

write clock과 read clock이 다른 두 block 사이로 burst가 지나갈 때 FIFO가 몇 word를 담아야 넘치지 않는지 계산합니다. 쓰기·읽기 패턴과 pointer synchronizer 단수를 넣으면 필요한 최소 깊이와, gray code pointer를 쓰는 async FIFO에 맞춘 2의 거듭제곱 깊이가 함께 나옵니다.

쓰는 쪽이 멈출 수 없으면 burst 동안 쌓인 양이 깊이가 된다

센서 interface나 DMA처럼 80 MHz로 도는 block이 한 번에 120 word를 이어서 내보내고, 50 MHz로 도는 block이 그것을 받는 경우를 생각해 보겠습니다. 보내는 쪽은 line이나 packet 단위로 데이터를 쏟아 내고, 받는 쪽이 늦다고 중간에 멈추지 않습니다. 받는 쪽이 매 cycle 한 word씩 꺼내도 clock이 느리니 그 차이만큼 FIFO에 쌓입니다.

FIFO가 이 최대량을 담지 못하면 full 상태에서 들어온 word는 버려지거나 아직 읽지 않은 칸을 덮어씁니다. 그래서 FIFO 깊이는 burst 하나가 지나가는 동안 쌓이는 가장 큰 양으로 정합니다.

평균 속도가 충분해도 burst 동안의 순간 속도가 깊이를 정한다

120 word burst가 5 µs마다 한 번 온다면 평균 쓰기 속도는 24 Mword/s로, 읽기 속도 50 Mword/s의 절반도 되지 않습니다. 그래도 burst가 지나가는 1.5 µs 동안에는 초당 80 M word가 들어오고 50 M word가 나갑니다. 그 차이 30 Mword/s가 1.5 µs 동안 쌓이면 45 word입니다.

평균 속도는 FIFO가 결국 비워지는지를 정하고, 순간 속도는 그 사이에 얼마나 차오르는지를 정합니다. 둘은 따로 확인해야 합니다.

burst를 다 쓰는 시간 동안 읽힌 개수를 빼면 깊이가 나온다

fw, fr = write, read clock 주파수(MHz). 1 MHz는 1 µs에 한 cycle이므로 MHz × µs가 곧 cycle 수입니다. B = burst 길이(word), Iw, Ir = 쓰기 사이, 읽기 사이 idle cycle 수, floor = 소수점 아래 버림

동기화 여유를 끄면 계산기는 이 식을 그대로 씁니다. 순서는 다음과 같습니다.

1. idle cycle을 cycle당 word로 바꿉니다. 쓰기 사이에 1 cycle을 쉬면 두 cycle에 한 번 쓰므로 r_w = 0.5입니다. write enable의 duty cycle이 50%라고 주어져도 같은 값입니다.
2. burst B개를 다 쓰는 시간 T를 구합니다. 쓰기 속도 f_w × r_w로 B를 나눕니다.
3. T 동안 읽힌 개수 R을 구합니다. 읽기는 burst와 동시에 시작한다고 보고, 끝나지 않은 읽기는 세지 않으려고 버림합니다.
4. B에서 R을 빼면 burst가 끝나는 순간 FIFO에 남은 word 수, 곧 필요한 최소 깊이 D입니다.

면접 문제 풀이 자료들이 쓰는 방식이 이것이고, 아래 예제 1, 2의 숫자도 그 자료들과 같습니다. 이 식은 읽기가 첫 word와 같은 순간에 시작한다고 봅니다. 서로 다른 clock의 async FIFO에서는 그렇게 되지 않는데, 이 차이는 뒤에서 따로 다룹니다.

Y cycle마다 X개라는 조건은 2X개가 이어서 오는 경우로 푼다

쓰기가 “Y cycle 동안 X개, 위치는 임의”로 주어지면 최악은 한 window의 마지막 X cycle에 X개를 쓰고, 다음 window의 처음 X cycle에 다시 X개를 쓰는 경우입니다. window 경계를 사이에 두고 2X개가 2X cycle 동안 이어서 들어옵니다. 계산기는 이 패턴을 B_eff = 2X, r_w = 1인 burst로 바꿔 같은 식에 넣습니다.

f_w 80 MHz, f_r 50 MHz, Y = 100 cycle마다 X = 80개라면 B_eff = 160입니다. T = 160 ÷ 80 MHz = 2 µs, 그동안 읽는 양은 2 µs × 50 MHz = 100개라 D = 160 − 100 = 60입니다.

2X가 최악인 것은 평균 쓰기 속도가 읽기 속도 이하일 때뿐이다

window 세 개에 걸친 구간을 보면 앞 window 끝에 X개, 가운데 window에 X개, 뒤 window 앞에 X개가 들어와 Y + 2X cycle 동안 3X개가 됩니다. 2X개 경우와 비교하면 Y cycle이 길어진 대신 X개가 더 들어옵니다. 그 Y cycle 동안 X개 이상을 읽을 수 있어야 세 window 구간이 2X 구간보다 더 차지 않습니다. 이 조건을 속도로 쓰면 f_w × X ÷ Y가 f_r × r_r 이하입니다.

위 예는 이 조건을 어깁니다. 평균 쓰기 속도가 80 × 80 ÷ 100 = 64 Mword/s로 읽기 50 Mword/s보다 빠릅니다. 100 cycle(1.25 µs)마다 80개가 들어오고 62.5개가 나가니 window마다 17.5개씩 더 쌓입니다. 패턴이 계속되면 어떤 깊이로도 넘치므로, 60은 쓰기가 이 두 window에서 끝날 때만 맞는 값입니다. 계산기는 이 경우 결과 아래에 경고를 띄웁니다.

async FIFO에서는 pointer 동기화 때문에 읽기가 늦게 시작하고 full이 늦게 풀린다

Cummings의 async FIFO(SNUG 2002, Rev 1.2)는 write pointer와 read pointer를 gray code로 바꿔 상대 clock의 FF 두 개로 넘깁니다. empty는 read clock에서, full은 write clock에서 판정하고, 두 flag 모두 비교 결과를 register에 한 번 더 담습니다. 논문은 이 구조에서 full과 empty가 켜질 때는 제때 켜지고 풀릴 때는 늦게 풀린다고 설명합니다. 넘치거나 빈 칸을 읽는 일은 막아 주지만, 늦게 풀리는 두 지연이 필요한 깊이를 늘립니다.

empty가 늦게 풀려 첫 읽기가 d_r만큼 늦어진다

첫 word를 쓰면 그 write edge에서 write pointer가 바뀝니다. read 쪽은 synchronizer N단을 지난 뒤에야 바뀐 값을 봅니다. pointer가 바뀐 직후 read clock edge를 막 놓쳤다면 첫 단까지 한 주기 가까이 기다리므로, 위상까지 넣으면 N 주기입니다. 그다음 edge에서 rempty register가 내려가고, 그다음 edge부터 꺼낼 수 있습니다.

읽기 사이에 idle cycle이 있는 block은 보통 정해진 slot에서만 읽습니다. 그러면 꺼낼 수 있게 된 뒤에도 다음 slot까지 한 읽기 주기 1 ÷ (f_r × r_r)를 더 기다릴 수 있습니다. 계산기는 이 경우까지 넣어 d_r을 잡습니다. I_r = 0이면 이 항은 read clock 한 주기라 앞의 “그다음 edge”와 같은 것입니다.

full 판정은 N + 1 write cycle 전의 read pointer를 본다

wptr_full module은 다음 write pointer(wgraynext)를 synchronizer 끝단의 read pointer(wq2_rptr)와 비교합니다. 그 결과는 wfull register에 담깁니다. 어떤 write edge에서 쓸 수 있는지는 직전 edge에 담긴 wfull이 정합니다. 따라서 그 판정에 쓰인 read pointer는 N + 1 write cycle 전에 표본을 뜬 값입니다.

그 사이에 읽힌 word는 실제로는 빠졌는데도 full 판정에는 차 있는 것으로 보입니다. 이 지연 d_w는 write edge 기준으로 정해지므로 위상 항이 따로 붙지 않습니다.

d_r의 첫 항은 첫 word가 첫 write slot이 끝날 때 써진다는 뜻입니다. 둘째 항은 synchronizer N 주기와 rempty register 1 주기, 셋째 항은 다음 읽기 slot까지의 대기입니다. 읽기는 d_r부터 1 ÷ (fr × rr) 간격으로 일어나므로 R은 d_r 시점의 첫 읽기까지 세려고 1을 더하고, Rs는 T − d_w보다 앞선 읽기를 세려고 올림(ceil)합니다. 괄호 안이 음수면 0으로 둡니다.

읽기가 쓰기보다 빠르거나 같으면 burst 동안 쌓이지 않습니다. 이때 남는 깊이는 한 word를 쓴 뒤 full 판정이 그 word가 빠진 것을 알기까지의 왕복 지연 L 동안 쓴 word 수입니다.

Cummings의 RTL을 직접 돌려 위 식과 맞춰 보았다

식이 실제 회로와 맞는지 보려고 논문의 Example 2~7 code를 옮겨 Icarus Verilog 13.0으로 돌려 보았습니다. synchronizer만 단수를 바꿀 수 있게 고쳤고, 2단일 때는 논문 그대로입니다. 쓰는 쪽은 wfull을 보지 않고 burst를 밀어 넣고, FIFO는 1,024칸으로 크게 잡았습니다. 대신 write마다 full 판정이 보고 있던 차 있는 칸 수를 기록해, 그 write가 막히지 않으려면 몇 칸이 필요했는지를 얻었습니다.

f_w 80 MHz, f_r 50 MHz, B 120, N 2에서 read clock 위상을 250 ps 간격으로 바꿔 가며 돌렸습니다. 필요한 깊이는 위상에 따라 50이나 51이었고, 최악값 51이 위 식과 같았습니다. 같은 조건에서 N을 3으로 늘리면 53, Y cycle 예제(2X = 160)는 66으로 역시 식과 같았습니다.

주파수(33~200 MHz), burst 길이, idle cycle, N(2~4)을 무작위로 바꾼 40가지 조합도 돌려 보았습니다. 위상을 500 ps 간격으로 바꿔 얻은 최악값이 40가지 모두 식과 같았습니다. 이 확인에서 읽는 쪽은 정해진 slot에서만 읽게 했습니다. 데이터가 보이는 즉시 읽게 바꾸면 필요한 깊이는 같거나 1 작았습니다.

두 clock edge가 정확히 겹치는 위상에서 simulator는 synchronizer가 바뀌기 전 값을 잡게 합니다. 실제 회로에서 metastability가 이전 값 쪽으로 풀린 경우와 같은 결과라 최악값에 그대로 넣었습니다.

synchronizer와 gray code pointer의 full 조건은 CDC의 metastability와 synchronizer, async FIFO의 gray code에서 자세히 다뤘습니다.

gray code pointer를 쓰면 깊이를 2의 거듭제곱으로 올린다

async FIFO의 pointer는 한 번 셀 때 한 비트만 바뀌어야 하고, 끝에서 처음으로 돌아갈 때도 마찬가지여야 합니다. 표준 reflected gray code가 이 조건을 지키며 도는 길이는 2의 거듭제곱입니다. Cummings는 홀수 길이 gray code가 없어 23-deep은 만들 수 없고 이 구조의 FIFO는 2ⁿ deep이라고 씁니다. 같은 논문은 132 word가 필요할 때 표준 gray pointer로는 256 word를 쓰게 된다는 예를 듭니다.

계산기의 권장 깊이는 D 이상인 가장 작은 2^k이고, 최소 2로 둡니다. address는 k비트, pointer는 full과 empty를 가르려고 한 비트 더 넓은 k + 1비트입니다. 깊이 64면 address 6비트, pointer 7비트입니다.

같은 clock으로 도는 sync FIFO는 count나 binary pointer를 쓰므로 D를 그대로 깊이로 써도 됩니다. Cummings는 binary pointer를 표본으로 떠서 handshake로 넘기면 깊이를 마음대로 정할 수 있다고 소개합니다. 다만 그 방식은 받는 쪽 두 edge와 보내는 쪽 두 edge만큼 지연이 늘어 깊이가 더 필요할 수 있다고 덧붙입니다. 2의 거듭제곱이 아닌 짝수 깊이로 gray code를 쓰는 방법은 위 CDC 글에 적었습니다.

평균 쓰기 속도가 평균 읽기 속도보다 빠르면 어떤 깊이로도 넘친다

burst가 쉬지 않고 이어지면 burst 속도가 곧 평균 속도가 됩니다. f_w × r_w가 f_r × r_r보다 크면 매 µs 그 차이만큼 쌓이고, 깊이를 늘려도 넘치는 시점이 늦어질 뿐입니다. Satish의 정리 자료도 데이터가 끊김 없이 흐르면 필요한 FIFO 깊이가 무한이 된다고 적고 있습니다.

그래서 계산기는 burst 뒤 FIFO를 비우는 데 걸리는 시간을 “다음 burst 전 최소 간격”으로 보여 줍니다. 동기화 여유를 끄면 (B_eff − R) ÷ (f_r × r_r)이고, 켜면 여기에 full 판정이 마지막 읽기를 알기까지의 d_w를 더합니다. 예제 1의 조건이면 45 word를 비우는 데 0.9 µs가 걸립니다. burst 1.5 µs와 합해 2.4 µs마다 120 word가 오면 평균 50 Mword/s로 읽기 속도와 같아지고, 이보다 자주 오면 앞 burst의 잔량 위에 다음 burst가 쌓입니다.

손으로 따라 해 보는 예제

아래 세 예제는 위 계산기에 같은 값을 넣으면 같은 숫자가 나옵니다.

예제 1. 80 MHz로 120 word를 이어서 쓰고 50 MHz로 매 cycle 읽는다

동기화 여유는 끄고, I_w = I_r = 0입니다.

1.5 µs 동안 20 ns마다 한 word씩 75 word가 나가고 45 word가 남습니다. 깊이를 마음대로 정할 수 있는 구조라면 45칸으로 되고, gray code pointer async FIFO라면 64칸입니다.

예제 2. 쓰기 사이 1 cycle, 읽기 사이 3 cycle을 쉰다

예제 1에 I_w = 1, I_r = 3을 넣습니다. 동기화 여유는 끕니다.

37.5에서 반 개는 아직 끝나지 않은 읽기라 버립니다. 쓰기 쪽 idle cycle은 burst를 두 배로 늘이고, 읽기 쪽 idle cycle은 읽는 속도를 4분의 1로 줄입니다. 그 결과 예제 1보다 38 word가 더 필요합니다.

예제 3. 예제 1을 2단 synchronizer async FIFO로 받는다

예제 1과 같은 값에 동기화 여유를 켜고 N = 2를 넣습니다.

읽기가 92.5 ns 늦게 시작해 burst 동안 4 word를 덜 읽고(75에서 71), 마지막 write 순간 full 판정은 그중 2 word가 빠진 것을 아직 모릅니다. 예제 1보다 6 word 많은 51이 됩니다.

이 조건에서는 권장 깊이가 둘 다 64라 차이가 드러나지 않습니다. Y cycle 예제는 다릅니다. 교과서 식으로는 60이라 64칸에 들어가지만, 같은 조건에 2단 synchronizer 여유를 넣으면 66이 되어 128칸이 필요합니다.

이 계산기가 다루지 않는 것

참고 자료

• Clifford E. Cummings, Simulation and Synthesis Techniques for Asynchronous FIFO Design, SNUG San Jose 2002 (Rev 1.2)
• Putta Satish, Calculation of FIFO Depth – Made Easy
• VLSI Universe, FIFO depth calculation

모든 계산은 브라우저 안에서만 이루어지며 입력한 값은 어디에도 전송되거나 저장되지 않습니다. 결과는 설계 초기에 규모를 가늠하는 용도이고, 실제 깊이는 사용하는 FIFO IP의 flag 지연을 확인해 정해야 합니다.