This post is about how VHDL 2008 can be used to implement a FIFO or list of items of any type by implementing a “protected type”.
At the top of the package is the definition of fifo_ptr and fifo_cnt. The fifo_ptr item is the pointer to the top of the linked list of items. The fifo_cnt integer is a count of how many items there are on the fifo.
Of course to test this the VHDL Test Bench was used and the following stimulus commands were created.
Many applications store or delay data transfers as part of the implementation. For instance, packet switching, video processing and Digital Signal Processing all usually have some delay element during the processing of the information. A packet switch may store hundreds of packets in order to meet traffic constraints. A video processing unit may store several frames of video data as it processes the video data stream. A DSP application may have delays as it processed blocks of data.
What ever the case is, you have supplied stimulus to the DUT and there is a delay before you get results out. Where do you store the input or the expected results? Wouldn't it be nice to include a time stamp in your input data so you could determine the time it took to process the data?
This can all be realized using VHDL 2008 protected types. A protected type can be used as a shared variable as well, so, knowing how to do this can save time and make life easier.
First step is to decide what kind of record to define that will be the FIFO or list item. This can include anything that you can define in a VHDL record type. For the example, the arr128x8 type will be associated with a FIFO type of fifo_data_type. The type that is going to be the FIFO or list item must include a pointer to the type. In the case of this example the FIFO item type is called fifo_item, defined as a record. The pointer is fifo_item_ptr is a type of pointer to a fifo_item type. The pointer to fifo_item type enables a linked list of fifo_items to be traversed. This implementation is called a single linked list. In order to implement a double link list, a prev_rec definition could be added to the fifo_item definition. The fifo_item type must be defined in a separate package. The pgen package used in the example packet generation BFM example, has been extended and put in a separate file. Included below:
------------------------------------------------------------------------------
-- First we start of with the definition of the packet array type
-- and the pack_out record for pins on the entity and comp.
-- The size of the whole system can be changed by changing the
-- array and record types.
library IEEE;
use IEEE.STD_LOGIC_1164.all;
package pgen is
type arr128x8 is array(0 to 127) of std_logic_vector(7 downto 0);
type fifo_data_array is array(0 to 127) of std_logic_vector(7 downto 0);
-- define the fifo_item type and access pointer
type fifo_item; -- the item
type fifo_item_ptr is access fifo_item; -- pointer to item
type fifo_item is record -- full definition of item
data : fifo_data_array;
next_rec : fifo_item_ptr;
end record;
type pack_out is record
dout : arr128x8;
drdy : std_logic;
end record;
end package pgen;
Once the type has been defined in a package the protected type is defined in another package. For this example the package is simply called fifo_pkg. The example is presented as a pure implementation of a protected type in the fifo_pkg, but of course you could have many other items defined, including other protected types.
The first thing to define is the header portion of the package. It include the definition of the protected type and its impure functions and procedures.
use std.textio.all ;
library ieee ;
use ieee.std_logic_1164.all ;
use ieee.numeric_std.all ;
use ieee.math_real.all ;
use work.pgen.all; -- include the types, as needed by shared variables
package fifo_pkg is
type tb_fifo is protected
procedure push(data : fifo_data_array);
impure function push(data : fifo_data_array) return integer;
impure function pop return fifo_data_array;
impure function fifo_depth return integer;
end protected tb_fifo;
end fifo_pkg;
Some simple utilities are defined, push in both a procedure and function form, a pop function and a fifo_depth function. Basic FIFO functions. Note the “is protected”, “end protected” and “impure function” syntax.
The body section is there the implementation of the procedures and impure functions are done. The example code for the body is presented below:
package body fifo_pkg is
type tb_fifo is protected body
variable fifo_ptr : fifo_item_ptr := null;
variable fifo_cnt : integer := 0;
-- push function
impure function push(data : fifo_data_array) return integer is
variable new_pkt : fifo_item_ptr;
variable tmp_ptr : fifo_item_ptr;
begin
if(fifo_cnt = 0) then
new_pkt := new fifo_item; fifo_ptr := new_pkt;
-- copy the packet to the new space
new_pkt.data := data;
new_pkt.next_rec := null;
fifo_cnt := 1;
else
new_pkt := new fifo_item;
tmp_ptr := fifo_ptr;
-- get to the end of the fifo
while(tmp_ptr.next_rec /= null) loop
tmp_ptr := tmp_ptr.next_rec;
end loop;
-- copy the packet to the new space
new_pkt.data := data;
new_pkt.next_rec := null;
tmp_ptr.next_rec := new_pkt;
fifo_cnt := fifo_cnt + 1;
end if;
return 1;
end function push;
-- push procedure
procedure push(data : fifo_data_array) is
variable new_pkt : fifo_item_ptr;
variable tmp_ptr : fifo_item_ptr;
begin
if(fifo_cnt = 0) then
new_pkt := new fifo_item;
fifo_ptr := new_pkt;
-- copy the packet to the new space
new_pkt.data := data;
new_pkt.next_rec := null;
fifo_cnt := 1;
else
new_pkt := new fifo_item;
tmp_ptr := fifo_ptr;
-- get to the end of the fifo
while(tmp_ptr.next_rec /= null) loop
tmp_ptr := tmp_ptr.next_rec;
end loop;
-- copy the packet to the new space
new_pkt.data := data;
new_pkt.next_rec := null;
tmp_ptr.next_rec := new_pkt;
fifo_cnt := fifo_cnt + 1;
end if;
end procedure push;
-- pop function
impure function pop return fifo_data_array is
variable data : fifo_data_array := (others => (others => 'U'));
variable tmp_ptr : fifo_item_ptr;
variable prev_ptr : fifo_item_ptr;
begin
case fifo_cnt is
when 0 =>
return data;
when 1 =>
fifo_cnt := 0;
data := fifo_ptr.data;
fifo_ptr := null;
return data;
when others =>
tmp_ptr := fifo_ptr;
fifo_ptr := tmp_ptr.next_rec;
tmp_ptr.next_rec := null;
fifo_cnt := fifo_cnt - 1;
return tmp_ptr.data;
end case;
end function pop;
-- fifo_depth function
impure function fifo_depth return integer is
begin
return fifo_cnt;
end function fifo_depth;
end protected body tb_fifo;
end fifo_pkg;
At the top of the package is the definition of fifo_ptr and fifo_cnt. The fifo_ptr item is the pointer to the top of the linked list of items. The fifo_cnt integer is a count of how many items there are on the fifo.
The package is very simple and does not have many of the nice things like overloaded write and print functions, searching, indexing, deleting and replacing that could be implemented.
Of course to test this the VHDL Test Bench was used and the following stimulus commands were created.
Define just after the architecture statement shared variable test_fifo : tb_fifo;
or it can be defined as a regular variable as part of the read_file process
-------------------------------------------------------------------------------------------
elsif (instruction(1 to len) = "PUSH") then
for i in 0 to test_data'high loop
--v_dat_array(i) := std_logic_vector(conv_unsigned(v_randv.RandInt(0, 255),8));
--test_data(i) := std_logic_vector(conv_unsigned(v_randv.RandInt(0, 255),8));
test_data(i) := std_logic_vector(conv_unsigned(i, 8));
end loop;
test_fifo.push(test_data);
print("fifo depth is: " & integer'image(test_fifo.fifo_depth));
temp_int := test_fifo.push(test_data);
print("fifo depth is: " & integer'image(test_fifo.fifo_depth));
------------------------------------------------------------------------------------------
elsif (instruction(1 to len) = "POP") then
test_data := (others => (others => 'X'));
print("POPing fifo depth is: " & integer'image(test_fifo.fifo_depth));
test_data := test_fifo.pop;
As well the packages have to be included in the tb_ent file. If randomization is used to generate the data, the synthworks Random package must be included.
And the stimulus file used to test the example FIFO implementation:
PUSH
PUSH
POP
POP
POP
POP
POP
PUSH
PUSH
POP
POP
POP
POP
POP
FINISH
PUSH
POP
POP
POP
POP
POP
PUSH
PUSH
POP
POP
POP
POP
POP
FINISH
The operation was observed by setting break points in the code and looking at the content and status as the simulation progressed.
The example is simple, and could easily be adapted to implement list functions and others. The actual “item” in the FIFO can be changed to include such things as message strings, time stamps, and any other VHDL type. The only draw back is that a FIFO of an unknown type can not be created. If the FIFO item definition is expected to change, some planning should go into the definition so that compatibility can be maintained in the future.
I have used linked lists in the past for storing packet data, but it was not easy. The VHDL Test Bench Package uses linked list techniques extensively. So the only new part to this presentation is the protected types and how you can associate functions and procedures to them. Makes the code that uses protected types more readable I think. As well, access the shared variables of protected types is controlled. I plan to use this FIFO in a checker BFM and in the model of the DUT in the expanded example currently being worked on. (slowly)
The FIFO example could be converted to a list implementation with some additions. For each instance of the example tb_fifo there will be an instance of fifo_cnt. For a list, an index may be needed so that a particular item can be found quickly or ordering can be achieved. Several other functions or procedures will be need to be added to search, re-order and manipulate the list of items. An index field would be added to the record, as it is record specific. Where as a FIFO ID string would be added in the protected body section of the protected type definition, one ID string per fifo. A function or procedure will have to be created that enables the ID string to be set. This is like the fifo_cnt field in the above example code.
Hope that helps some get more acquainted with VHDL 2008 and how it can help your verification efforts.
Sckoarn