Real-Time Embedded System 心得(4): FIFO 的奧秘

一則老笑話：「號稱10年經驗，其實是1年經驗用10次」，FIFO 還有什麼好說的? First In First Out，搞不好國中生都會(不是 linked list 就是 ring buffer)，最多討論一下 critical section，加個 mutex，大概過個 10 年你的 FIFO  不會有任何變化，筆者也是這麼想，直到有一天...

FIFO 容量越大越好? 

考慮以下問題：

1. 當 FIFO 爆掉時，加大 FIFO 就好?
2. FIFO 大部分時間為空還是應該不為空?

大部分人碰到 #1 時，可能就是把 FIFO 容量加大，然後再丟出去測試看看， 至於 #2 如果是 在 PC  上可能一些人就迷迷糊糊的混過去了，但如果是 Embedded System，就會發現產品怎麼 gg 了，或是反應變得其慢無比等等...

很多人會想，那我就換更快的 CPU 就好了啊，但有很多情境不是換 CPU 就能解決問題(先別提老闆是否同意)，以一項網路設備來說：

1. 頻寬本來就有上限
2. 頻寬與 CPU loading 正相關(尤其該 SoC沒有提供 TCP offloading之類的硬體加速影響會更大)
3. 外界干擾，現在光是一根電線桿都插滿了各種 2.4G 裝置

所以若是沒有處理好， 你的系統可能就會發散掉，再也救不回來，直到 reboot

筆者在參與 IPCam 開發過程中，頻頻碰到此類問題，既然 10 年經驗行不通，筆者就開始搜尋手邊各種可行的方案，包含以前沒有想過的...

很幸運的，筆者在 2001/4 Embedded System Programming 雜誌(現已停刊，多年前從網路下訂請對方從美國寄過來，現在有線上版)找到了一篇名為 "Queueing Theory for Dummies" 的文章，瞬間打通任督二脈，下面就是這篇文章的精華懶人包。

首先我們定義兩個函數

• P(t): Production Rate，訊息進入某個子系統/部件的速率
• C(t): Consumption Rate， 訊息離開某個子系統/部件的速率

t 代表時間，也就是 P(t), C(t) 是 t 的函數。顯然會有兩種情形：

1. P(t) <= C(t): 訊息離開速率大於進入速率，此時不需要 FIFO。
2. P(t) > C(t): 訊息進入速率大於訊息離開速率，此時需要 FIFO。

但如果 #2 永遠成立，則不管你的記憶體多大都會發生 overflow。這邊帶出一個重要的觀念，就是 FIFO 只在一小段時間有效，這一小段時間就是從開始有訊息進入到訊息停止進入，P(t) > C(t) 的時間，作者 Dr. David Kalinsky 稱為 "burst"。

舉個具體的例子，假設有一個 IPCam 以 H264 產生 streaming，15 FPS，下圖解釋了什麼是 burst：

假設 P(t)、C(t) 為常數，從訊息開始進入到停止的時間為 T，那麼 FIFO 最後的長度：

L = P*T - C*T = (P - C)*T

假設 T = t1 - t0，那麼在 t1 之後，消化這些訊息所需的時間稱為 Emptying Time，簡稱為 E：

E = L/C or E = (P/C - 1)*T

這個可以輕易的用 Excel 模擬，假設 P(t) = 5，C(t) = 3，P(t) 持續 10 個時間單位，FIFO 的成長狀況如下圖所示：

這邊帶出另一個重要的觀念，如果 E 太大，大到與下一次 burst 重疊，那實際上 FIFO 是永遠處於非空的狀態，那你會發現 CPU loading 怎樣都降不下來，這是一種危險的狀態！

另外一方面，P/C 比例過大時，可能需要 "quite time" 用於恢復 FIFO(清空)。

一般的情況是 P(t), C(t) 不是常數，而是非線性函數，所以 burst 結束時 FIFO 未必處於長度最大的情形，要取得 burst 內任一個時間點的 FIFO 長度，普通的四則運算行不通，這時要用積分：

(設 t1~ t2 為 burst，Tx 為 t1 ~ t2 內的時間)

L(最長) 則是 L(Tx) 的極大值:

當然，要用積分的方式取得極大值太難了，Dr. David Kalinsky 建議用作圖的方式，有個簡便的方法是用 UART 輸出 log 後，配合 grep, python 導入到 Excel 裡畫出折線圖。

看到這裡，你會不會覺得：「原來 FIFO 水很深!」「原來我沒有學過 FIFO」

如何求 C(t)?

以 IPCam 來說，假如能知道 MINIMUM[C(Tx)]，就可以以 MINIMUM[C(Tx)] 降低 FPS，調高壓縮比，降低 frame rate，讓網路封包頭過身就過。但是你會發現要從積分方程中取得 MINIMUM[C(Tx)] 太難了，尤其是還要寫成程式。

此時有兩種實務上的作法：

1. 接收端(例如手機)回報 bps，以此作為 MINIMUM[C(Tx)]
2. 利用 FIFO 計算 MINIMUM[C(Tx)]

#1 有個問題，當接收端把 bps 傳回給發送端(IPCam)時，因為網路延遲，可能已經「人事全非」，資訊已經過時了。#2 則是利用系統當下的 FIFO 長度計算 C(t)，即時性最好(扯了這麼久終於跟 Real-Time 有關連了)。

問題是要怎麼計算呢?筆者的懶人作法是如果測試出的最大頻寬為 MaxB，則：

MINIMUM[C(Tx)] = MaxB/2 -  MAXIMUM[L(Tx)]

如果你測出來 10Mbps，MAXIMUM[L(Tx)] 中的 Tx 長度為秒，那這個公式就很容易應用了

MINIMUM[C(Tx)] = 10Mbit/2 -  MAXIMUM[L(Tx)]

(當然，你可能要把 bit 換算成 byte)

除 2 是筆者的個人經驗法則，很多案例中，用測試程式(e.g iperf)測試時頻寬很高，但系統中經過幾層 IPC(Inter-Process Communication) 後降的很快，或者是因為加密等其他原因可能只有測試程式頻寬的 50%-60%。

把 MINIMUM[C(Tx)] 除以 FPS，再比較上一秒每個 frame 的平均大小，就可以知道是該降低畫質還是要提高畫質。

PID

筆者以前唸書時有一門課考試靠死背考古題，學完也不知道自己在學什麼，叫做自動控制(Control Theory)，筆者查閱資料才知道，原來這個調整的演算法，在控制理論稱為比例(Proportional)控制，各位書唸得比我多的讀者，應該會猜到還有積分控制(Integral)，微分控制(Derivative)，組合成 PID。

在工控中最常用到 PID 的是馬達與溫控器，以溫控器來說，假如希望把溫度控制在 80 度，溫控器就會利用 PID 演算法平滑的把溫度升到 80 度，經由實際值(PV)的回授比對設定值(SV = 80)，把溫度鎖在 80 度。

而在 IPCam 這類應用裡，假設頻寬只有 10Mbps，那我們就會希望每秒送出去的 audio/video 資料量不要超過這個上限，如果遠低於這個上限，雖然會很流暢但畫質會很差FPS 也太低，最好是逼近這個上限，既能維持畫質與FPS，又能充分利用頻寬。但之前提過，網路會被干擾，阻塞，更慘的是，如果 IPCam 照到的場景是有變化+細節多，那壓縮比就會變小，所以這是一件很有挑戰的任務，因為你無法預知網路與鏡頭前的變化。

筆者才弄了老半天，也只能參透 P 值，例如上一秒送出的資料是 300KB，MINIMUM[C(Tx)] = 200KB，以 15FPS 計算，平均 frame size = 300KB/15 = 20KB，200KB/20KB = 10FPS，所以要降成 10FPS。

至於 I 值要怎麼找?實在是沒有頭緒，某天在街上發現下面這本神奇的小冊子，雖然作者(也是一位物理博士)想要寫得很容易入門，但看了1/2 還是不知道要怎麼找 I 值(看來控制理論要寫到一般大眾都能接受還是很難)，總不能硬套一些係數用 try 的，畢竟這是科學不是黑魔法吧?

不過這本書還是給學資訊的人很大的啟發，畢竟資訊系很少開控制理論的課程，但把控制理論用在資訊裡，的確開了眼界，有興趣的朋友可以找來看看！

(出版社現在應該很後悔選這個封面)

其實問題的癥結在於，降頻寬我們可以降的很有信心，但升回來呢? 你敢很有種的一次從15FPS 調回 30FPS，從 480P 一次跳回 FHD，但過一陣子?其實網路上有個前輩叫做 TCP，他的作法是「乘法遞減，加法遞增」，也就是降頻寬時可能是用指數後退的方式，1/2,1/4,1/8，加頻寬時卻是往上一點一點加回去。

在控制理論中有一個「滯後」的概念，你的修改不會馬上生效，得讓子彈飛一會兒，前人在實踐中顯然是發現了網路從擁塞到疏通是一個漸進的過程，所以不會把頻寬馬上升回去，這也是為何講 TCP/IP 的書裡 1/2-1/3 幾乎都是在講 TCP，時不時還穿插一堆數學公式。

(如果你有在看 Netflix 就會發現，有時一開始畫質很差，但過一陣子畫質就變好了，顯然也是有用到類似的理論)

尾聲

雖然只是短短的一篇文章，但可是筆者加班無數，搭最後一班捷運，走30min回家，被逼出人體潛能的心血結晶。筆者有天逛特力屋時，發現架上兜售的無線監視器會卡頓，說不定就跟這篇文章有關係。

ChamberPlus 老大常感嘆台灣為何寫不出精緻的 firmware，筆者越來越能體會，你看人家老外是個 FIFO 就分析的如此徹底，台灣有可能嗎?沒有了解的這麼深入，碰到問題是否只能用 CPU 不夠快塘塞?還是能找出 root cause?平平都是學數學，為何人家能把數學應用到實際工程中，而我們只能 trial & error?

而筆者也感覺到，控制理論不是玄學，是一門非常實用的學科，只能說感嘆自己的修為不足，看來進 IC design house 真的要多唸點書...

經此一役，筆者領會了什麼才是上乘武功，這些日子裡常常寫程式寫到懷疑人生，雖然挺過來了，但身體也搞壞了，在離別之際趕緊把一些領會寫下來分享給大家，各位有任何意見歡迎留言，謝謝!