First Input First Output的縮寫，先入先出隊(duì)列，這是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令。是一種先進(jìn)先出的數(shù)據(jù)緩存器，他與普通存儲器的區(qū)別是沒有外部讀寫地址線，這樣使用起來非常簡單，但缺點(diǎn)就是只能順序?qū)懭霐?shù)據(jù)，順序的讀出數(shù)據(jù)，其數(shù)據(jù)地址由內(nèi)部讀寫指針自動加1完成，不能像普通存儲器那樣可以由地址線決定讀取或?qū)懭肽硞€指定的地址。

FIFO是隊(duì)列機(jī)制中最簡單的，每個接口上只有一個FIFO隊(duì)列，表面上看FIFO隊(duì)列并沒有提供什么QoS保證，甚至很多人認(rèn)為FIFO嚴(yán)格意義上不算做一種隊(duì)列技術(shù)，實(shí)則不然，F(xiàn)IFO是其它隊(duì)列的基礎(chǔ)，F(xiàn)IFO也會影響到衡量QoS的關(guān)鍵指標(biāo)：

報文的丟棄、延時、抖動。既然只有一個隊(duì)列，自然不需要考慮如何對報文進(jìn)行復(fù)雜的流量分類，也不用考慮下一個報文怎么拿、拿多少的問題，即FIFO無需流分類、調(diào)度機(jī)制，而且因?yàn)榘错樞蛉笪?，F(xiàn)IFO無需對報文重新排序。簡化了這些實(shí)現(xiàn)其實(shí)也就提高了對報文時延的保證。

FIFO關(guān)心的就是隊(duì)列長度問題，隊(duì)列長度會影響到時延、抖動、丟包率。因?yàn)殛?duì)列長度是有限的，有可能被填滿，這就涉及到該機(jī)制的丟棄原則，F(xiàn)IFO使用Tail Drop機(jī)制。如果定義了較長的隊(duì)列長度，那么隊(duì)列不容易填滿，被丟棄的報文也就少了，但是隊(duì)列長度太長了會出現(xiàn)時延的問題，一般情況下時延的增加會導(dǎo)致抖動也增加；如果定義了較短的隊(duì)列，時延的問題可以得到解決，但是發(fā)生Tail Drop的報文就變多了。類似的問題其它排隊(duì)方法也存在。

Tail Drop機(jī)制簡單的說就是如果該隊(duì)列如果已經(jīng)滿了，那么后續(xù)進(jìn)入的報文被丟棄，而沒有什么機(jī)制來保證后續(xù)的報文可以擠掉已經(jīng)在隊(duì)列內(nèi)的報文。

FIFO隊(duì)列原理簡述

FIFO隊(duì)列不對報文進(jìn)行分類，當(dāng)報文進(jìn)入接口的速度大于接口能發(fā)送的速度時，F(xiàn)IFO按報文到達(dá)接口的先后順序讓報文進(jìn)入隊(duì)列，同時，F(xiàn)IFO在隊(duì)列的出口讓報文按進(jìn)隊(duì)的順序出隊(duì)，先進(jìn)的報文將先出隊(duì)，后進(jìn)的報文將后出隊(duì)。

FIFO隊(duì)列具有處理簡單，開銷小的優(yōu)點(diǎn)。但FIFO不區(qū)分報文類型，采用盡力而為的轉(zhuǎn)發(fā)模式，使對時間敏感的實(shí)時應(yīng)用（如VoIP）的延遲得不到保證，關(guān)鍵業(yè)務(wù)的帶寬也不能得到保證。

FIFO應(yīng)用

FIFO一般用于不同時鐘域之間的數(shù)據(jù)傳輸，比如FIFO的一端是AD數(shù)據(jù)采集，另一端是計(jì)算機(jī)的PCI總線，假設(shè)其AD采集的速率為16位100K SPS，那么每秒的數(shù)據(jù)量為100K×16bit=1.6Mbps，而PCI總線的速度為33MHz，總線寬度32bit，其最大傳輸速率為1056Mbps，在兩個不同的時鐘域間就可以采用FIFO來作為數(shù)據(jù)緩沖。

另外對于不同寬度的數(shù)據(jù)接口也可以用FIFO，例如單片機(jī)位8位數(shù)據(jù)輸出，而DSP可能是16位數(shù)據(jù)輸入，在單片機(jī)與DSP連接時就可以使用FIFO來達(dá)到數(shù)據(jù)匹配的目的。

FIFO的寬度：

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

FIFO的深度：

THE DEEPTH，它指的是FIFO可以存儲多少個N位的數(shù)據(jù)（如果寬度為N）。如一個8位的FIFO，若深度為8，它可以存儲8個8位的數(shù)據(jù)，深度為12 ，就可以存儲12個8位的數(shù)據(jù)，F(xiàn)IFO的深度可大可小，個人認(rèn)為FIFO深度的計(jì)算并無一個固定的公式。

在FIFO實(shí)際工作中，其數(shù)據(jù)的滿/空標(biāo)志可以控制數(shù)據(jù)的繼續(xù)寫入或讀出。在一個具體的應(yīng)用中不可能由一些參數(shù)精確算出所需的FIFO深度為多少，這在寫速度大于讀速度的理想狀態(tài)下是可行的，但在實(shí)際中用到的FIFO深度往往要大于計(jì)算值。

一般來說根據(jù)電路的具體情況，在兼顧系統(tǒng)性能和FIFO成本的情況下估算一個大概的寬度和深度就可以了。而對于寫速度慢于讀速度的應(yīng)用，F(xiàn)IFO的深度要根據(jù)讀出的數(shù)據(jù)結(jié)構(gòu)和讀出數(shù)據(jù)由那些具體的要求來確定。

滿、空標(biāo)志：

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

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

讀、寫時鐘：

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

寫時鐘：寫操作所遵循的時鐘，在每個時鐘沿來臨時寫數(shù)據(jù)。

讀、寫指針

讀指針：指向下一個讀出地址。讀完后自動加1。

寫指針：指向下一個要寫入的地址的，寫完自動加1。

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

FIFO分類

根據(jù)FIFO工作的時鐘域，可以將FIFO分為同步FIFO和異步FIFO。

同步FIFO是指讀時鐘和寫時鐘為同一個時鐘。在時鐘沿來臨時同時發(fā)生讀寫操作。

異步FIFO是指讀寫時鐘不一致，讀寫時鐘是互相獨(dú)立的。

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

FIFO設(shè)計(jì)的難點(diǎn)FIFO設(shè)計(jì)的難點(diǎn)在于怎樣判斷FIFO的空/滿狀態(tài)。

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

在用到觸發(fā)器的設(shè)計(jì)中，不可避免的會遇到亞穩(wěn)態(tài)的問題（關(guān)于亞穩(wěn)態(tài)可查看FPGA中的亞穩(wěn)態(tài)）。在涉及到觸發(fā)器的電路中，亞穩(wěn)態(tài)無法徹底消除，只能想辦法將其發(fā)生的概率將到最低。

其中的一個方法就是使用格雷碼。格雷碼在相鄰的兩個碼元之間只由一位變換（二進(jìn)制碼在很多情況下是很多碼元在同時變化）。這就會避免計(jì)數(shù)器與時鐘同步的時候發(fā)生亞穩(wěn)態(tài)現(xiàn)象。但是格雷碼有個缺點(diǎn)就是只能定義2^n的深度，而不能像二進(jìn)制碼那樣隨意的定義FIFO的深度，因?yàn)楦窭状a必須循環(huán)一個2^n，否則就不能保證兩個相鄰碼元之間相差一位的條件，因此也就不是真正的格雷碼了。

第二就是使用冗余的觸發(fā)器，假設(shè)一個觸發(fā)器發(fā)生亞穩(wěn)態(tài)的概率為P，那么兩個級聯(lián)的觸發(fā)器發(fā)生亞穩(wěn)態(tài)的概率就為P的平方。但這會導(dǎo)致延時的增加。亞穩(wěn)態(tài)的發(fā)生會使得FIFO出現(xiàn)錯誤，讀/寫時鐘采樣的地址指針會與真實(shí)的值之間不同，這就導(dǎo)致寫入或讀出的地址錯誤。

由于考慮延時的作用，空/滿標(biāo)志的產(chǎn)生并不一定出現(xiàn)在FIFO真的空/滿時才出現(xiàn)?？赡蹻IFO還未空/滿時就出現(xiàn)了空/滿標(biāo)志。這并沒有什么不好，只要保證FIFO不出現(xiàn)overflow or underflow 就OK了。

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

編輯：jq