LIFO

Recently I had an application that needed a LIFO rather than a FIFO. Where FIFO stands for “first in first out”, LIFO stands for “”last in first out”. LIFOs are not as common as FIFOs but they are used whenever you need to remember something you are currently working on and start on something new. When the new thing is done, you can go back to what it was you were doing before you were interrupted. Due to the sequential nature of software, LIFOs are used a lot in processors as parameter or return “stacks”, and the write operations is called a “push” and the read operation is a “pop”.

A simple implementation

At first blush, implementing a LIFO should be pretty much the same as implementing a FIFO. You have a read pointer and a write pointer and a dual port RAM. Here is a figure of a LIFO with two entries.

two_entries1

A LIFO with two entries.

You can see we will read from location 2 if necessary and we will write to location 3. However, unlike a FIFO, a pop operation will affect the write pointer, and worse yet, it will affect the write pointer before the write takes place. In this example, if we were to perform a pop and push operation simultaneously, then we would need to write to location two after doing the read. Afterwards, the read and write pointers would have the same values as before.

Digging deeper

Another thing to think about is that it seems wasteful to use a dual port RAM here. We could use a single port RAM if it weren’t for the pesky case of simultaneous pushes and pops. However, when we do a simultaneous push and pop, the pointers don’t change. We only read and write the location pointed to by the read pointer, taking care to do the read operation before the write operation. Also, if you think about it, we don’t need two pointers either. They really need to move in lock step with each other. The write pointer is always the read pointer if you are pushing and popping, and the read pointer plus one if you are just pushing.

A better approach

The “aha!” moment comes when you realize that the critical memory location is the top of the stack. We need to read and write this location if we are pushing and popping at the same time. Otherwise we only need to read or write the RAM, never both. If we keep the top of the stack in a register instead of the RAM, then we can do a simultaneous push and pop without using the memory at all. If we do just a push, then we need to write the top of the stack register to the RAM and store the pushed value in the top of stack register. For a pop without a push, we just need to read the RAM and store the result in the top of stack register, while providing the current top of stack register value as the pop result. The figure below shows a stack with two entries using a top of stack register.

A stack with two entries using a top of stack register

A stack with two entries using a top of stack register

The code

Ports for the LIFO are the usual clock and reset. We have status outputs empty and full as well as a count of the number of data items in the LIFO. Then we have a signal indicating a push with its associated data, and another indicating a pop. A top of stack value rounds out the ports. Just a note, you can use the top of stack value all you want without popping the stack.


`timescale 1ns/1ns
module lifo
  #(
    parameter depth = 32,
    parameter width = 32,
    parameter log2_depth = log2(depth),
    parameter log2_depthp1 = log2(depth+1)
    )
  (
   input clk,
   input reset,
   output reg empty,
   output reg full,
   output reg [log2_depthp1-1:0] count,
   input push,
   input [width-1:0] push_data,
   input pop,
   output [width-1:0] tos
   );

You can read my other posts about the synchronous FIFO or constant functions to find out more about the log2 parameters. Here’s the log2 function just for completeness though.


   function integer log2;
      input [31:0] value;
      begin
	 value = value-1;
	 for (log2=0; value>0; log2=log2+1)
	   value = value>>1;
      end
   endfunction

Next we use a flag to tell when we are writing. That is when we are asked to push and we have room for the data. This means that either we are not full, or if we are full, we are also popping. Reading is similar but a little simpler. We are reading if asked to pop and there is data available.


  wire writing = push && (count < depth || pop);
  wire reading = pop && count > 0;

Now for counting the data. We compute a combinational next_count value because that allows us to register the empty and full outputs. The logic is really quite simple. The count goes up when we write and don’t read, it goes down if we read and don’t write. Otherwise it just stays the same.


  reg [log2_depthp1-1:0] next_count;
  always @(*)
    if (reset)
      next_count = 0;
    else if (writing && !reading)
      next_count = count+1;
    else if (reading && !writing)
      next_count = count-1;
    else
      next_count = count;

  always @(posedge clk)
    count <= next_count;

Full and empty are pretty self explanatory.


  always @(posedge clk)
    full <= next_count == depth;

  always @(posedge clk)
    empty <= next_count == 0;

For the memory pointer, if we are writing, then we use the location pointed to by the count and if we are reading then we will use the location one before.


  wire [log2_depth-1:0] ptr = writing ? count [log2_depth-1:0] : (count [log2_depth-1:0])-1;

Writing to the memory is simple enough. If we are writing and not reading then we write the current top of stack into the RAM. The top of stack will be replaced with what we are pushing onto the stack. If we are writing and reading, we don’t want to write anything. The top of stack register will do all the work in this case.


  reg [width-1:0] mem [depth-1:0];

  always @(posedge clk)
    if (writing && !reading)
      mem[ptr] <= tos;

Reading is a little more tricky. It would be great if we could just say


 always @(posedge clk)
   if (reading && !writing)
     tos <= mem[ptr];
   else if (writing)
     tos <= push_data;

But this won’t work. You can’t map that into the read output register of a BRAM. Synthesis tools aren’t smart enough to map part of this onto the RAM and the rest onto outside logic. So we have to give it a little hint. First we just use a simple register that can map onto the read output register.


  reg [width-1:0] mem_rd;
  always @(posedge clk)
    if (reading)
      mem_rd <= mem[ptr];

Then we create a top of stack “shadow” register. This will hold the value being written to the top of the stack since we can’t store it in the RAM output register. Only the RAM can do that.


  reg [width-1:0] tos_shadow;
  always @(posedge clk)
    if (writing)
      tos_shadow <= push_data;

Finally we need a MUX to select who really holds the top of stack value.


  reg use_mem_rd;
  always @(posedge clk)
    if (reset)
      use_mem_rd <= 0;
    else if (writing)
      use_mem_rd <= 0;
    else if (reading)
      use_mem_rd <= 1;

  assign tos = use_mem_rd ? mem_rd : tos_shadow;

Wrapup

So with this design you get an efficient LIFO using a single port RAM. Why is it important to do this in a single port? I’ll answer that question in a future post. For now, you can download the entire LIFO module here.

October 23, 2009 • Posted in: HDL, Verilog

One Response to “LIFO”

  1. Kulwant Nagi - April 30th, 2012

    Thanks for providing the code !!

Leave a Reply