fifo

fifo簡(jiǎn)介

　在計(jì)算機(jī)中，先入先出隊(duì)列是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令（指令就是計(jì)算機(jī)在響應(yīng)用戶(hù)操作的程序代碼，對(duì)用戶(hù)而言是透明的）。如圖1所示，當(dāng)CPU在某一時(shí)段來(lái)不及響應(yīng)所有的指令時(shí)，指令就會(huì)被安排在FIFO隊(duì)列中，比如0號(hào)指令先進(jìn)入隊(duì)列，接著是1號(hào)指令、2號(hào)指令……當(dāng)CPU完成當(dāng)前指令以后就會(huì)從隊(duì)列中取出0號(hào)指令先行執(zhí)行，此時(shí)1號(hào)指令就會(huì)接替0號(hào)指令的位置，同樣，2號(hào)指令、3號(hào)指令……都會(huì)向前挪一個(gè)位置，這樣解釋大家清楚了吧？

fifo百科

　　First Input First Output的縮寫(xiě)，先入先出隊(duì)列，這是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令。

　　FIFO簡(jiǎn)介

　　在計(jì)算機(jī)中，先入先出隊(duì)列是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令（指令就是計(jì)算機(jī)在響應(yīng)用戶(hù)操作的程序代碼，對(duì)用戶(hù)而言是透明的）。如圖1所示，當(dāng)CPU在某一時(shí)段來(lái)不及響應(yīng)所有的指令時(shí)，指令就會(huì)被安排在FIFO隊(duì)列中，比如0號(hào)指令先進(jìn)入隊(duì)列，接著是1號(hào)指令、2號(hào)指令……當(dāng)CPU完成當(dāng)前指令以后就會(huì)從隊(duì)列中取出0號(hào)指令先行執(zhí)行，此時(shí)1號(hào)指令就會(huì)接替0號(hào)指令的位置，同樣，2號(hào)指令、3號(hào)指令……都會(huì)向前挪一個(gè)位置，這樣解釋大家清楚了吧？

　　圖1 先進(jìn)先出隊(duì)列FIFO是隊(duì)列機(jī)制中最簡(jiǎn)單的，每個(gè)接口上都存在FIFO隊(duì)列，表面上看FIFO隊(duì)列并沒(méi)有提供什么QoS（Quality of Service，服務(wù)質(zhì)量）保證，甚至很多人認(rèn)為FIFO嚴(yán)格意義上不算做一種隊(duì)列技術(shù)，實(shí)則不然，F(xiàn)IFO是其它隊(duì)列的基礎(chǔ)，F(xiàn)IFO也會(huì)影響到衡量QoS的關(guān)鍵指標(biāo)：報(bào)文的丟棄、延時(shí)、抖動(dòng)。既然只有一個(gè)隊(duì)列，自然不需要考慮如何對(duì)報(bào)文進(jìn)行復(fù)雜的流量分類(lèi)，也不用考慮下一個(gè)報(bào)文怎么拿、拿多少的問(wèn)題，而且因?yàn)榘错樞蛉?bào)文，F(xiàn)IFO無(wú)需對(duì)報(bào)文重新排序。簡(jiǎn)化了這些實(shí)現(xiàn)其實(shí)也就提高了對(duì)報(bào)文時(shí)延的保證。FIFO關(guān)心的就是隊(duì)列長(zhǎng)度問(wèn)題，隊(duì)列長(zhǎng)度會(huì)影響到時(shí)延、抖動(dòng)、丟包率。因?yàn)殛?duì)列長(zhǎng)度是有限的，有可能被填滿(mǎn)，這就涉及到該機(jī)制的丟棄原則。常見(jiàn)的一個(gè)丟棄原則叫做Tail Drop機(jī)制。簡(jiǎn)單地說(shuō)就是該隊(duì)列如果已經(jīng)滿(mǎn)了，那么后續(xù)進(jìn)入的報(bào)文被丟棄，而沒(méi)有什么機(jī)制來(lái)保證后續(xù)的報(bào)文可以擠掉已經(jīng)在隊(duì)列內(nèi)的報(bào)文。在這種機(jī)制中，如果定義了較長(zhǎng)的隊(duì)列長(zhǎng)度，那么隊(duì)列不容易填滿(mǎn)，被丟棄的報(bào)文也就少了，但是隊(duì)列長(zhǎng)度太長(zhǎng)了會(huì)出現(xiàn)時(shí)延的問(wèn)題，一般情況下時(shí)延的增加會(huì)導(dǎo)致抖動(dòng)也增加。如果定義了較短的隊(duì)列，時(shí)延的問(wèn)題可以得到解決，但是發(fā)生Tail Drop的報(bào)文就變多了。

　　FIFO隊(duì)列原理簡(jiǎn)述

　　FIFO隊(duì)列不對(duì)報(bào)文進(jìn)行分類(lèi)，當(dāng)報(bào)文進(jìn)入接口的速度大于接口能發(fā)送的速度時(shí)，F(xiàn)IFO按報(bào)文到達(dá)接口的先后順序讓報(bào)文進(jìn)入隊(duì)列，同時(shí)，F(xiàn)IFO在隊(duì)列的出口讓報(bào)文按進(jìn)隊(duì)的順序出隊(duì)，先進(jìn)的報(bào)文將先出隊(duì)，后進(jìn)的報(bào)文將后出隊(duì)。FIFO隊(duì)列具有處理簡(jiǎn)單，開(kāi)銷(xiāo)小的優(yōu)點(diǎn)。但FIFO不區(qū)分報(bào)文類(lèi)型，采用盡力而為的轉(zhuǎn)發(fā)模式，使對(duì)時(shí)間敏感的實(shí)時(shí)應(yīng)用（如VoIP）的延遲得不到保證，關(guān)鍵業(yè)務(wù)的帶寬也不能得到保證。

　　使用FIFO

　　FIFO一般用于不同時(shí)鐘域之間的數(shù)據(jù)傳輸，比如FIFO的一端是AD數(shù)據(jù)采集，另一端是計(jì)算機(jī)的PCI總線(xiàn)，假設(shè)其AD采集的速率為16位 100K SPS，那么每秒的數(shù)據(jù)量為100K×16bit=1.6Mbps，而PCI總線(xiàn)的速度為33MHz，總線(xiàn)寬度32bit，其最大傳輸速率為1056Mbps，在兩個(gè)不同的時(shí)鐘域間就可以采用FIFO來(lái)作為數(shù)據(jù)緩沖。另外對(duì)于不同寬度的數(shù)據(jù)接口也可以用FIFO，例如單片機(jī)位8位數(shù)據(jù)輸出，而DSP可能是16位數(shù)據(jù)輸入，在單片機(jī)與DSP連接時(shí)就可以使用FIFO來(lái)達(dá)到數(shù)據(jù)匹配的目的。

　　重要參數(shù)

　　FIFO的寬度：也就是英文資料里常看到的THE WIDTH，它指的是FIFO一次讀寫(xiě)操作的數(shù)據(jù)位，就像MCU有8位和16位，ARM32位等等，F(xiàn)IFO的寬度在單片成品IC中是固定的，也有可選擇的，如果用FPGA自己實(shí)現(xiàn)一個(gè)FIFO，其數(shù)據(jù)位，也就是寬度是可以自己定義的。

　　FIFO的深度：THE DEEPTH，它指的是FIFO可以存儲(chǔ)多少個(gè)N位的數(shù)據(jù)（如果寬度為N）。如一個(gè)8位的FIFO，若深度為8，它可以存儲(chǔ)8個(gè)8位的數(shù)據(jù)，深度為12 ，就可以存儲(chǔ)12個(gè)8位的數(shù)據(jù)，F(xiàn)IFO的深度可大可小，個(gè)人認(rèn)為FIFO深度的計(jì)算并無(wú)一個(gè)固定的公式。在FIFO實(shí)際工作中，其數(shù)據(jù)的滿(mǎn)/空標(biāo)志可以控制數(shù)據(jù)的繼續(xù)寫(xiě)入或讀出。在一個(gè)具體的應(yīng)用中不可能由一些參數(shù)精確算出所需的FIFO深度為多少，這在寫(xiě)速度大于讀速度的理想狀態(tài)下是可行的，但在實(shí)際中用到的FIFO深度往往要大于計(jì)算值。一般來(lái)說(shuō)根據(jù)電路的具體情況，在兼顧系統(tǒng)性能和FIFO成本的情況下估算一個(gè)大概的寬度和深度就可以了。而對(duì)于寫(xiě)速度慢于讀速度的應(yīng)用，F(xiàn)IFO的深度要根據(jù)讀出的數(shù)據(jù)結(jié)構(gòu)和讀出數(shù)據(jù)由那些具體的要求來(lái)確定。

　　滿(mǎn)標(biāo)志：FIFO已滿(mǎn)或?qū)⒁獫M(mǎn)時(shí)由FIFO的狀態(tài)電路送出的一個(gè)信號(hào)，以阻止FIFO的寫(xiě)操作繼續(xù)向FIFO中寫(xiě)數(shù)據(jù)而造成溢出（overflow）。

　　空標(biāo)志：FIFO已空或?qū)⒁諘r(shí)由FIFO的狀態(tài)電路送出的一個(gè)信號(hào)，以阻止FIFO的讀操作繼續(xù)從FIFO中讀出數(shù)據(jù)而造成無(wú)效數(shù)據(jù)的讀出（underflow）。

　　讀時(shí)鐘：讀操作所遵循的時(shí)鐘，在每個(gè)時(shí)鐘沿來(lái)臨時(shí)讀數(shù)據(jù)。

　　寫(xiě)時(shí)鐘：寫(xiě)操作所遵循的時(shí)鐘，在每個(gè)時(shí)鐘沿來(lái)臨時(shí)寫(xiě)數(shù)據(jù)。

　　讀指針：指向下一個(gè)讀出地址。讀完后自動(dòng)加1。

　　寫(xiě)指針：指向下一個(gè)要寫(xiě)入的地址的，寫(xiě)完自動(dòng)加1。

　　讀寫(xiě)指針其實(shí)就是讀寫(xiě)的地址，只不過(guò)這個(gè)地址不能任意選擇，而是連續(xù)的。

　　4．FIFO的分類(lèi)

　　根據(jù)FIFO工作的時(shí)鐘域，可以將FIFO分為同步FIFO和異步FIFO。同步FIFO是指讀時(shí)鐘和寫(xiě)時(shí)鐘為同一個(gè)時(shí)鐘。在時(shí)鐘沿來(lái)臨時(shí)同時(shí)發(fā)生讀寫(xiě)操作。異步FIFO是指讀寫(xiě)時(shí)鐘不一致，讀寫(xiě)時(shí)鐘是互相獨(dú)立的。

　　5．FIFO設(shè)計(jì)的難點(diǎn)

　　FIFO設(shè)計(jì)的難點(diǎn)在于怎樣判斷FIFO的空/滿(mǎn)狀態(tài)。為了保證數(shù)據(jù)正確的寫(xiě)入或讀出，而不發(fā)生溢出或讀空的狀態(tài)出現(xiàn)，必須保證FIFO在滿(mǎn)的情況下，不能進(jìn)行寫(xiě)操作。在空的狀態(tài)下不能進(jìn)行讀操作。怎樣判斷FIFO的滿(mǎn)/空就成了FIFO設(shè)計(jì)的核心問(wèn)題。由于同步FIFO幾乎很少用到，這里只描述異步FIFO的空/滿(mǎn)標(biāo)志產(chǎn)生問(wèn)題。

　　在用到觸發(fā)器的設(shè)計(jì)中，不可避免的會(huì)遇到亞穩(wěn)態(tài)的問(wèn)題（關(guān)于亞穩(wěn)態(tài)這里不作介紹，可查看相關(guān)資料）。在涉及到觸發(fā)器的電路中，亞穩(wěn)態(tài)無(wú)法徹底消除，只能想辦法將其發(fā)生的概率將到最低。其中的一個(gè)方法就是使用格雷碼。格雷碼在相鄰的兩個(gè)碼元之間只由一位變換（二進(jìn)制碼在很多情況下是很多碼元在同時(shí)變化）。這就會(huì)避免計(jì)數(shù)器與時(shí)鐘同步的時(shí)候發(fā)生亞穩(wěn)態(tài)現(xiàn)象。但是格雷碼有個(gè)缺點(diǎn)就是只能定義2^n的深度，而不能像二進(jìn)制碼那樣隨意的定義FIFO的深度，因?yàn)楦窭状a必須循環(huán)一個(gè)2^n，否則就不能保證兩個(gè)相鄰碼元之間相差一位的條件，因此也就不是真正的格雷碼了。第二就是使用冗余的觸發(fā)器，假設(shè)一個(gè)觸發(fā)器發(fā)生亞穩(wěn)態(tài)的概率為P，那么兩個(gè)級(jí)聯(lián)的觸發(fā)器發(fā)生亞穩(wěn)態(tài)的概率就為P的平方。但這會(huì)導(dǎo)致延時(shí)的增加。亞穩(wěn)態(tài)的發(fā)生會(huì)使得FIFO出現(xiàn)錯(cuò)誤，讀/寫(xiě)時(shí)鐘采樣的地址指針會(huì)與真實(shí)的值之間不同，這就導(dǎo)致寫(xiě)入或讀出的地址錯(cuò)誤。由于考慮延時(shí)的作用，空/滿(mǎn)標(biāo)志的產(chǎn)生并不一定出現(xiàn)在FIFO真的空/滿(mǎn)時(shí)才出現(xiàn)。可能FIFO還未空/滿(mǎn)時(shí)就出現(xiàn)了空/滿(mǎn)標(biāo)志。這并沒(méi)有什么不好，只要保證FIFO不出現(xiàn)overflow or underflow 就OK了。

　　很多關(guān)于FIFO的文章其實(shí)討論的都是空/滿(mǎn)標(biāo)志的不同算法問(wèn)題。

　　在Vijay A. Nebhrajani的《異步FIFO結(jié)構(gòu)》一文中，作者提出了兩個(gè)關(guān)于FIFO空/滿(mǎn)標(biāo)志的算法。

　　第一個(gè)算法：構(gòu)造一個(gè)指針寬度為N+1，深度為2^N字節(jié)的FIFO（為方便比較，將格雷碼指針轉(zhuǎn)換為二進(jìn)制指針）。當(dāng)指針的二進(jìn)制碼中最高位不一致而其它N位都相等時(shí)，F(xiàn)IFO為滿(mǎn)（在Clifford E. Cummings的文章中以格雷碼表示是前兩位均不相同，而后兩位LSB相同為滿(mǎn)，這與換成二進(jìn)制表示的MSB不同其他相同為滿(mǎn)是一樣的）。當(dāng)指針完全相等時(shí)，F(xiàn)IFO為空。這也許不容易看出，舉個(gè)例子說(shuō)明一下：一個(gè)深度為8字節(jié)的FIFO怎樣工作（使用已轉(zhuǎn)換為二進(jìn)制的指針）。FIFO_WIDTH=8，F(xiàn)IFO_DEPTH= 2^N = 8，N = 3，指針寬度為N+1=4。起初rd_ptr_bin和wr_ptr_bin均為“0000”。此時(shí)FIFO中寫(xiě)入8個(gè)字節(jié)的數(shù)據(jù)。wr_ptr_bin =“1000”，rd_ptr_bin=“0000”。當(dāng)然，這就是滿(mǎn)條件?，F(xiàn)在，假設(shè)執(zhí)行了8次的讀操作，使得rd_ptr_bin =“1000”，這就是空條件。另外的8次寫(xiě)操作將使wr_ptr_bin 等于“0000”，但rd_ptr_bin 仍然等于“1000”，因此FIFO為滿(mǎn)條件。

　　顯然起始指針無(wú)需為“0000”。假設(shè)它為“0100”，并且FIFO為空，那么8個(gè)字節(jié)會(huì)使wr_ptr_bin =“1100”，， rd_ptr_bin 仍然為“0100”。這又說(shuō)明FIFO為滿(mǎn)。

　　在Vijay A. Nebhrajani的這篇《異步FIFO結(jié)構(gòu)》文章中說(shuō)明了怎樣運(yùn)用格雷碼來(lái)設(shè)置空滿(mǎn)的條件，但沒(méi)有說(shuō)清為什么深度為8的FIFO其讀寫(xiě)指針要用3+1位的格雷碼來(lái)實(shí)現(xiàn)，而3+1位的格雷碼可以表示16位的深度，而真實(shí)的FIFO只有8位，這是怎么回事？而這個(gè)問(wèn)題在Clifford E. Cummings的文章中得以解釋。三位格雷碼可表示8位的深度，若在加一位最為MSB，則這一位加其他三位組成的格雷碼并不代表新的地址，也就是說(shuō)格雷碼的0100表示表示7，而1100仍然表示7，只不過(guò)格雷碼在經(jīng)過(guò)一個(gè)以0位MSB的循環(huán)后進(jìn)入一個(gè)以1為MSB的循環(huán)，然后又進(jìn)入一個(gè)以0位MSB的循環(huán)，其他的三位碼仍然是格雷碼，但這就帶來(lái)一個(gè)問(wèn)題，在0100的循環(huán)完成后，進(jìn)入1000，他們之間有兩位發(fā)生了變換，而不是1位，所以增加一位MSB的做法使得該碼在兩處：0100~1000，1100~0000有兩位碼元發(fā)生變化，故該碼以不是真正的格雷碼。增加的MSB是為了實(shí)現(xiàn)空滿(mǎn)標(biāo)志的計(jì)算。Vijay A. Nebhrajani的文章用格雷碼轉(zhuǎn)二進(jìn)制，再轉(zhuǎn)格雷碼的情況下提出空滿(mǎn)條件，僅過(guò)兩次轉(zhuǎn)換，而Clifford E. Cummings的文章中直接在格雷碼條件下得出空滿(mǎn)條件。其實(shí)二者是一樣的，只是實(shí)現(xiàn)方式不同罷了。

　　第二種算法：Clifford E. Cummings的文章中提到的STYLE#2。它將FIFO地址分成了4部分，每部分分別用高兩位的MSB 00 、01、 11、 10決定FIFO是否為going full 或going empty （即將滿(mǎn)或空）。如果寫(xiě)指針的高兩位MSB小于讀指針的高兩位MSB則FIFO為“幾乎滿(mǎn)”，

　　若寫(xiě)指針的高兩位MSB大于讀指針的高兩位MSB則FIFO為“幾乎空”。

　　在Vijay A. Nebhrajani的《異步FIFO結(jié)構(gòu)》第三部分的文章中也提到了一種方法，那就是方向標(biāo)志與門(mén)限。設(shè)定了FIFO容量的75%作為上限，設(shè)定FIFO容量的25%為下限。當(dāng)方向標(biāo)志超過(guò)門(mén)限便輸出滿(mǎn)/空標(biāo)志，這與Clifford E. Cummings的文章中提到的STYLE #2可謂是異曲同工。他們都屬于保守的空滿(mǎn)判斷。其實(shí)這時(shí)輸出空滿(mǎn)標(biāo)志FIFO并不一定真的空/滿(mǎn)。

　　說(shuō)到此，我們已經(jīng)清楚地看到，F(xiàn)IFO設(shè)計(jì)最關(guān)鍵的就是產(chǎn)生空/滿(mǎn)標(biāo)志的算法的不同產(chǎn)生了不同的FIFO。但無(wú)論是精確的空滿(mǎn)還是保守的空滿(mǎn)都是為了保證FIFO工作的可靠。