[Vijay A.Nebhrajani]Asynchronous FIFO Architecture

网上比较多的是翻译版的FIFO原理讲解，这里上传的是英文原版。这里把三部分内容整合在一起，方便阅读。pointer points to the location that will be read next. a write increments the write pointer,and a read increments the read pointerThe last block we see is the status" block. The responsibility of this block is togenerate the empty and full signals to the FIFO. These signals tell the outsideworld that the fifo has reached a terminal condition If full is active then the fifo hasreached a terminal condition for write and if emptysis active, the fiFo has reached aterminal condition for read. a terminal condition for write implies that the FIFo has nospace to accommodate more data and a terminal condition for read implies that theFiFo has no more data available for readout. The status block may also report thenumber of empty or full locations in the FIFO, and this is accomplished by an arithmeticoperation on the pointersThe actual count of empty or full locations does not play much of a part in the FIFo itselfit is used as a reporting mechanism to the outside world. However, the empty and fullsignals play a very important role within the fifo they block access to further readsand writes respectively. the importance of this blocking does not lie in the fact that datamay be overwritten(or read out twice); the critical importance lies in the fact that pointerpositions are the only control we have over the FIFO, and writes or reads change thepointers. If we do not block the pointers from changing state at terminal conditions, wewill have a fifo that either eats" data or generates"data, and that is quiteunacceptableFurther analysis: The DPRAM could have " registered"reads - this means that theoutput data from the array is registered. If this is so, the read pointers will have to bedesigned to read and increment". This means that you will have to provide an explicitread signal before the data at the output of the FIFo is valid. On the other hand, if theDPRAM does not have registered outputs, valid data is available as soon as it is writtenyou read this data first, and increment the pointer later. This affects the logic that readsdata out from the FIFo and the logic that performs the empty/full calculation For thesake of simplicity we will only treat the case where the dPRAM does not provideregistered outputs. It is not very complex to extend the same reasoning(that we will use)to the case of a registered output dPRAMFunctionally the FIFO works as follows: At reset, the pointers are both 0. This is theempty condition of the FIFO, and empty is pulled high(we will use the active highconvention) and full is low. At empty, reads are blocked and so the only operationpossible is write. A write loads location 0 of the array and increments the write pointer to1. This causes the empty signal to go LOW. Assuming that there are no reads andsubsequent cycles only write to the FIFO, there will be a time when the write pointer willequal array size -1. This means that the last location in the array is the next locationthat will be written to. At this condition, a write will cause the write pointer to become 0,and set fuNote that in this condition the write and read pointers are equal, but the fifo is full, andnot empty. This implies that the fulllempty decision is not based on the pointer valuesalone, but on the operation that caused the pointers to become equal. If the cause ofpointer equality is a reset or a read, the FIFo is deemed empty; if the cause is a write,the fifo is fullNow assume that we begin a series of reads Each read will increment the read pointer,to the point where the read pointer equals array size -1. At this point, the data fromthis location is available on the output bus of the FIFo. Succeeding logic reads this dataand provides a read signal (active for one clock ) This causes the read pointer tobecome equal to the write pointer again (after both pointers have completed one cyclethrough the array ) However, since this equality came about because of a read, empty issetThus, we have the following for the empty flag: A write unconditionally clears emptyread pointer = (array size -1) and a read sets emptyand the following for the full flag: A read unconditionally clears fuwrite pointer =(array size -1)and a write sets fullHowever, this is a special case, since in general reads may start as soon as the FIFO isnot empty(the reading logic need not wait for the fifo to become full), so theseconditions have to be modified to accommodate any read pointer andwrite pointer valuesA little thought shows that we have organized the array as a circular list. Thus, if thewrite pointer is numerically greater than the read pointer by 1 and a read occurs,theFIFO is empty. This works just fine for the boundary case described above as long aswe use unsigned(n-bit)arithmetic. Similarly, if the read pointer is numerically greaterthan the write pointer by 1 and a write occurs, the FIFo is fullThis leads to the conditionsa write unconditionally clears empty(write pointer read pointer 1)and a read sets emptya read unconditionally clears fu(read pointer write pointer 1)and a write sets fullNote that a simultaneous read and write increments both pointers, but does not alter thestate of the empty and full flags. A simultaneous read and write is not allowed at the fulland empty boundariesWith this we can now define the status block of the FIFO.I am providing the code inVHDL, but since this is synthesizable, translation to Verilog is easylibrary IEEE, STDuse IEEE std logic 1164.alluse IEEE std logic arith. alluse IEEE std logic unsigned. allentity status isP○t(resetin std logiciClkin std logicfifo wrstd logicfifo rdin sta logralid rdout std_1。givalid wrout std logicrd ptrout std logic vector(4 downto 0)wr ptrout std logic vector(4 downto 0)emptyout std logfullt std logend statusarchitecture status a of status issignal rd ptr ssta logic vector(4 downto 0)signal wr ptr sstd logic vector (4 downto 0)signa valid rd sstd lesignal valid wr s std logicbegiempty P: process(clk, reset)beginif (reset =1 thenempty1elsif (clk' event and clk =1 )thenif (fifo wr = 1 and fifo rd =i1 thendo nothing1lsif (fifo wr1 thenwrite unconditionally clears emptyempty <=0 ilsif (fifo rdtr sd ptr sset emptyemptyend ifend ifend process;full P process(clk, reset)beqinf ( reset1) thenfull0elsif (clk' event and clk1thenif (fifo rdfifo wr)thendo nothingnu11;lsif (fifo rd1thenread unconditionally clears fullfulllsif (fifo wr =1 and (rd ptrr ptr s+- set fullfullend ifend ifiend process ivalid rd s<=1 when (empty =0 and fifo rd =1)ivalid wr s <-1 when (full =10 and fifo wr =I 11)wr ptr s p: process(clk, resetbeginif (reset = 1)thenwr otr s p <=others =>0)elsif (clk event and clk =1) thenif (valid wr s=l1 thenwr rtr s < wr ptr s +1end ifend ifend processrd ptr s p process(clk, resetbeginif(res∈t='1')therrd otr s p < (otherselsif (clkl event and clk =1) thenif (valid rd s=i1)thenra ptr s<= rd ptr s+'1'end ifend ifend process;rd ptr < rd ptr swr ptr < wr ptr s;end status AiThe circuit for this is shown in Fig 2valid rd swr ptr s=rd ptr s+empt(INC)fifo wrrd eRD CLK DOMAINWR CLK DOMAINvalid wr srd ptr s=wr ptr s+ 1fifo rdwr ptr(INC)fifo wrwr en valid_wr_sclkFigure 2: Circuit for Status block and pointers of FIFo of Figure 1The observant reader will notice that generating the full or empty flags requires the useof both pointers In the case of a dual clock design the read pointer is expected to workoff the read clock and the write pointer off the write clock. This raises unexpectedlythorny issues --as you may try and see for yourself. These issues and some solutionswill be covered in future articles in this seriesAsynchronous FIFO Architectures(Part 2)Vijay A. NebhrajaniIn the previous part of this series we saw how a synchronous FIFO may be designed usinga dual port, non-registered output RAM. This part examines how the same concept maybe extended to yield a FiFo that has separate, free running read and write clocks. Havingfree running clocks simplifies some problems, but this leads to a case-specific solutionThe most general case is one in which nothing is assumed about the clocks -not eventhat they are free running. I will present this in the concluding part of this seriesIf you refer to the previous article, you will observe that other than the status block,nothing really needs to work off two clocks. The memory does not have registered readsso it does not really use the read clock; and even if it did have registered reads, thesecould run on the read clock without problems. The status block fundamentally performsoperations on the two pointers, and these run off two different clocks. This is what causesthe real difficulty. If you were to sample the read pointer with the write clock (or viceversa), you would potentially run into a problem called metastability. This would causeyou to calculate the empty and full flags incorrectly, and that would in a word, kill the1 MetastabilitySo let us proceed systematically and tackle problems as they arise. The first problem is tounderstand metastability. Metastability is the name for the physical phenomenon thatappens when an event tries to sample another event. mathematically the case is asfollows: Assume that a signal changes instantaneously from 0 to 1 at time t=0. What,then is the value of the signal at t=0? Is it 0 or 1 or something in between? Inmathematics, this problem is circumvented by defining two more instants, called 0-and0+ At t=0- the signal is defined to have the value 0, and at t= 0+ it is defined to havethe value 1. of course, 0-=0-0 and 0+=0 +0. Note that this is a mathematical trickonly, and if you did the same thing with a physical circuit, the output will eitheer be alogical 0(0 volts)or a logical 1(5 volts, nominally) or anything in between(0-5 volts). Inphysical systems as in mathematical ones sampling an event by another event yieldsunpredictable results. Unpredictability also implies another phenomenon -and this isthe real danger that metastability poses11 Resolution TimeWhen an event samples a static value, ( or a value that has been stable for a while) thesampled value resolves itself to that of that static value. If you talk in terms of a D flip-flop,Q resolves itself to the value of D. The time taken for this resolution, defined with respectto the sampling event is called resolution time. You are familiar with this term as theclock-to-Q time, or to, If you meet the setup time and hold time of the flip-flop, this is thetime that the cell designer guarantees the output will be resolved by Metastability affectsthe resolution time of the physical system as well as the resolved value. think of this interms of unstable equilibrium",or the ball on the hill. If you have a ball on a hillanother spherical surface, say) the ball is considered to be in a state of unstableequilibrium. If completely undisturbed, it may rest on the hill forever, but the tiniestperturbation will cause the ball to roll to one side of the hill or another. There is no way ofcalculating how long the ball will rest on the hill, or which side the ball will fall. This is theexact case with metastability - you cannot predict which value the physical systemoutput will resolve to, and more dangerously, after how long. Put another way, there is afinite, nonzero probability that the output will remain metastable forever. In practicethough this is rarely the case and a figure of 20 times clock-to-g is taken as a reasonablefigure for resolution. In theory resolution time follows an asymptotic curve to infinity asthe sampling instant comes closer to the event being sampled1.2 MTBF and ReliabilityIf you have an asynchronous element in your design, you will run into metastabilitywhether or not you want to. There is absolutely no way of eliminating metastabilitycompletely, so what we do is calculate a probability of error and express this in terms oftime. Let us say that there is a probability of a metastable failure of a physical system andthat this is one in 1000. In other words, for every 1000 samples, one will cause a failurebecause of metastability. This also means that once every thousand times, the output doesnot resolve itself by the time the next clock edge comes along. If your clock frequency is 1kHz, this implies a failure rate of once every second, and so the Mean Time BetweenFailures is calculated to be 1 second. This is of course, oversimplified MTBF is a statisticameasure of failure probability, and requires some more complex, empirical andexperimental data to arrive at. For flip-flops, this relationship depends on a physicaconstant of the circuit itself, and on the clock frequency It is important to remember thatmetastability itself has nothing to do with clock frequency -but mtbF does. We define acircuit with higher mtbf to be a more reliable circuit, naturally1.3 SynchronizationSince metastability is absolutely unavoidable you must design the circuit so that itHandles errors gracefullyThe probability of occurrence of such errors is minimizedThe first requirement varies greatly from design to design, and is not in the scope of thisbrief introduction. For the second requirement, a technique called synchronization"isused. This technique simply consists of two flip-flops as shown in Figure 1. Q2 will gometastable only when Q1 changes too close to the clock. If we take a 20x figure for tc as thetime for resolution in the event of metastability then the clock period would be given bt ck= 20t t setup What this really means that the probability that the output is still notresolved after 20 times the clock-to-q time is rather small. Thus, the probability of Q2 notbeing resolved by the time a clock edge comes along is approximately p where p is theprobability that the first stage output does not get resolved by the time a clock edge comesalong. This is called dual stage synchronization. When you use this probability with thelock frequency to calculate MTBF, you will find that the mTBF has increased greatly. Ifyou want, you may increase the MTBF further by having a three-stage synchronizer, butthis is rarely needed in practiceAsynchronoussynchronizedoutputDclklkFigure 1 Dual Stage SynchronizationYou can make the circuit more resistant to metastability by having redundantsynchronizers as shown in Figure 2. The final output is calculated as the majority(2 out of) for triple redundancy and equality for double redundancy. In this case small routingand device differences imply that if one of the synchronizers has a metastable failure, theother two will, in all probability have resolved themselves. Once again, this technique isneeded in only the most critical requirementsFor more on metastability and synchronization, see thisGrosse, Debora;Keep metastability from killing your digital designhttp://www.ednmag.com/reg/1994/062394/13df2.htm