FIFO is an acronym for First In, First Out, an abstraction in ways of organizing and manipulation of data relative to time and prioritization. This expression describes the principle of a queue processing technique or servicing conflicting demands by ordering process by first-come, first-served (FCFS) behaviour: what comes in first is handled first, what comes in next waits until the first is finished, etc.
Thus it is analogous to the behaviour of persons standing in line, where the persons leave the queue in the order they arrive, or waiting one's turn at a traffic control signal. FCFS is also the shorthand name (see Jargon and acronym) for the FIFO operating system scheduling algorithm, which gives every process CPU time in the order they come. In the broader sense, the abstraction LIFO, or Last-In-First-Out is the opposite of the abstraction FIFO organization, the difference perhaps is clearest with considering the less commonly used synonym of LIFO, FILO—meaning First-In-Last-Out. In essence, both are specific cases of a more generalized list (which could be accessed anywhere). The difference is not in the list (data), but in the rules for accessing the content. One sub-type adds to one end, and takes off from the other, its opposite takes and puts things only on one end.[1]
A priority queue is a variation on the queue which does not qualify for the name FIFO, because it is not accurately descriptive of that data structure's behavior. Queueing theory encompasses the more general concept of queue, as well as interactions between strict-FIFO queues.
1 //==========================================
2 // Function : Asynchronous FIFO (w/ 2 asynchronous clocks).
3 // -
4 // Date : 15/May/2005.
5 // Notes : This implementation is based on the article
6 // 'Asynchronous FIFO in Virtex-II FPGAs'
7 // writen by Peter Alfke. This TechXclusive
8 // article can be downloaded from the
9 // Xilinx website. It has some minor modifications.
10 //=========================================
11
12 `timescale 1ns/1ps
13
14 module aFifo
15 #(parameter DATA_WIDTH = 8,
16 ADDRESS_WIDTH = 4,
17 FIFO_DEPTH = (1 << ADDRESS_WIDTH))
18 //Reading port
19 (output reg [DATA_WIDTH-1:0] Data_out,
20 output reg Empty_out,
21 input wire ReadEn_in,
22 input wire RClk,
23 //Writing port.
24 input wire [DATA_WIDTH-1:0] Data_in,
25 output reg Full_out,
26 input wire WriteEn_in,
27 input wire WClk,
28
29 input wire Clear_in);
30
31 // 32 reg [DATA_WIDTH-1:0] Mem [FIFO_DEPTH-1:0];
33 wire [ADDRESS_WIDTH-1:0] pNextWordToWrite, pNextWordToRead;
34 wire EqualAddresses;
35 wire NextWriteAddressEn, NextReadAddressEn;
36 wire Set_Status, Rst_Status;
37 reg Status;
38 wire PresetFull, PresetEmpty;
39
40 // 41 //Data ports logic:
42 //(Uses a dual-port RAM).
43 //'Data_out' logic:
44 always @ (posedge RClk)
45 if (ReadEn_in & ! Empty_out)
46 Data_out <= Mem[pNextWordToRead];
47
48 //'Data_in' logic:
49 always @ (posedge WClk)
50 if (WriteEn_in & ! Full_out)
51 Mem[pNextWordToWrite] <= Data_in;
52
53 //Fifo addresses support logic:
54 //'Next Addresses' enable logic:
55 assign NextWriteAddressEn = WriteEn_in & ~Full_out;
56 assign NextReadAddressEn = ReadEn_in & ~Empty_out;
57
58 //Addreses (Gray counters) logic:
59 GrayCounter GrayCounter_pWr
60 (.GrayCount_out(pNextWordToWrite),
61
62 .Enable_in(NextWriteAddressEn),
63 .Clear_in(Clear_in),
64
65 .Clk(WClk)
66 );
67
68 GrayCounter GrayCounter_pRd
69 (.GrayCount_out(pNextWordToRead),
70 .Enable_in(NextReadAddressEn),
71 .Clear_in(Clear_in),
72 .Clk(RClk)
73 );
74
75
76 //'EqualAddresses' logic:
77 assign EqualAddresses = (pNextWordToWrite == pNextWordToRead);
78
79 //'Quadrant selectors' logic:
80 assign Set_Status = (pNextWordToWrite[ADDRESS_WIDTH-2] ~^ pNextWordToRead[ADDRESS_WIDTH-1]) & 81 (pNextWordToWrite[ADDRESS_WIDTH-1] ^ pNextWordToRead[ADDRESS_WIDTH-2]);
82
83 assign Rst_Status = (pNextWordToWrite[ADDRESS_WIDTH-2] ^ pNextWordToRead[ADDRESS_WIDTH-1]) & 84 (pNextWordToWrite[ADDRESS_WIDTH-1] ~^ pNextWordToRead[ADDRESS_WIDTH-2]);
85
86 //'Status' latch logic:
87 always @ (Set_Status, Rst_Status, Clear_in) //D Latch w/ Asynchronous Clear & Preset.
88 if (Rst_Status | Clear_in)
89 Status = 0; //Going 'Empty'.
90 else if (Set_Status)
91 Status = 1; //Going 'Full'.
92
93 //'Full_out' logic for the writing port:
94 assign PresetFull = Status & EqualAddresses; //'Full' Fifo.
95
96 always @ (posedge WClk, posedge PresetFull) //D Flip-Flop w/ Asynchronous Preset.
97 if (PresetFull)
98 Full_out <= 1;
99 else
100 Full_out <= 0;
101
102 //'Empty_out' logic for the reading port:
103 assign PresetEmpty = ~Status & EqualAddresses; //'Empty' Fifo.
104
105 always @ (posedge RClk, posedge PresetEmpty) //D Flip-Flop w/ Asynchronous Preset.
106 if (PresetEmpty)
107 Empty_out <= 1;
108 else
109 Empty_out <= 0;
110
111 endmodule
|
1 //==========================================
2 // Function : Code Gray counter.
3 // -
4 // Date : 15/May/2005.
5 //=======================================
6
7 `timescale 1ns/1ps
8
9 module GrayCounter
10 #(parameter COUNTER_WIDTH = 4)
11
12 (output reg [COUNTER_WIDTH-1:0] GrayCount_out, //'Gray' code count output.
13
14 input wire Enable_in, //Count enable.
15 input wire Clear_in, //Count reset.
16
17 input wire Clk);
18
19 // 20 reg [COUNTER_WIDTH-1:0] BinaryCount;
21
22 // 23
24 always @ (posedge Clk)
25 if (Clear_in) begin
26 BinaryCount <= {COUNTER_WIDTH{1'b 0}} + 1; //Gray count begins @ '1' with
27 GrayCount_out <= {COUNTER_WIDTH{1'b 0}}; // first 'Enable_in'.
28 end
29 else if (Enable_in) begin
30 BinaryCount <= BinaryCount + 1;
31 GrayCount_out <= {BinaryCount[COUNTER_WIDTH-1],
32 BinaryCount[COUNTER_WIDTH-2:0] ^ BinaryCount[COUNTER_WIDTH-1:1]};
33 end
34
35 endmodule
|
