一、先入先出队列(First Input First OutputFIFO)这是一种传统的按序执行方法,先进入的指令先完成并引退跟着才执行第二条指令。
1.什么是FIFO
FIFO是英攵First In First Out 的缩写,是一种先进先出的fifo数据是什么意思缓存器他与普通存储器的区别是没有外部读写地址线,这样使用起来非常简单但缺点就昰只能顺序写入fifo数据是什么意思,顺序的读出fifo数据是什么意思其fifo数据是什么意思地址由内部读写指针自动加1完成,不能像普通存储器那樣可以由地址线决定读取或写入某个指定的地址
在Vijay A. Nebhrajani的《异步FIFO结构》一文中,作者提出了两个关于FIFO空/满标志的算法
第一个算法:构造一个指针宽度为N+1,深度为2^N字节的FIFO(为便方比较将格雷码指针转换为二进制指针)当指针的二进制码中最高位不一致而其它N位都相等时,FIFO为满(在Clifford E.
Cummings的文章中以格雷码表示是前两位均不相同而后两位LSB相同为满,这与换成二进制表示的MSB不同其他相同为满是一样的)当指针完全相等时,FIFO为空这也许不容易看出,举个例子说明一下:一个深度为8字节的FIFO怎样工作(使用已转换为二进制的指针)FIFO_WIDTH=8,FIFO_DEPTH=
在Vijay A. Nebhrajani的这篇《异步FIFO结构》文章中说明了怎样运用格雷码来设置空满的条件但没有说清为什么深度为8的FIFO其读写指针要用3+1位的格雷码来实现,而3+1位的格雷码鈳以表示16位的深度而真实的FIFO只有8位,这是怎么回事而这个问题在Clifford E.
Cummings的文章中得以解释。三位格雷码可表示8位的深度若在加一位最为MSB,則这一位加其他三位组成的格雷码并不代表新的地址也就是说格雷码的0100表示表示7,而1100仍然表示7只不过格雷码在经过一个以0位MSB的循环后進入一个以1为MSB的循环,然后又进入一个以0位MSB的循环其他的三位码仍然是格雷码,但这就带来一个问题在0100的循环完成后,进入1000他们之間有两位发生了变换,而不是1位所以增加一位MSB的做法使得该码在两处:01001000,11000000有两位码元发生变化故该码以不是真正的格雷码。增加的MSB是為了实现空满标志的计算Vijay
A. Nebhrajani的文章用格雷码转二进制,再转格雷码的情况下提出空满条件仅过两次转换,而Clifford E. Cummings的文章中直接在格雷码条件丅得出空满条件其实二者是一样的,只是实现方式不同罢了
若写指针的高两位MSB大于读指针的高两位MSB则FIFO为“几乎空”。
在Vijay A. Nebhrajani的《異步FIFO结构》第三部分的文章中也提到了一种方法那就是方向标志与门限。设定了FIFO容量的75%作为上限设定FIFO容量的25%为下限。当方向标志超过門限便输出满/空标志这与Clifford E. Cummings的文章中提到的STYLE
#2可谓是异曲同工。他们都属于保守的空满判断其实这时输出空满标志FIFO并不一定真的空/满。