Linked List Implementation in ASIC – Hardware

There are three major components in linked list.

  • First is Buffer Memory. As evident from name, buffer memory stores application data, managed in buffer unit sizes. Assuming  that buffer size is BUF_SIZE and number of buffers are NUM_BUF, then total memory size is BUF_SIZE*NUM_BUF.
  • Link Memory stores all link pointers and address of all buffers. Number of entries in this memory are equal to NUM_BUF.

Please note: Each individual buffer address is of N bits, where 2^N = NUM_BUF. Assuming K is number of bits required to access a location within a buffer, where 2^K =BUF_SIZE, then any location in buffer memory can be accessed by concatenation of buffer address ( N bits) and location address ( K bits).

  • Queue Information Set – Each queue/List requires three sets of information, start pointer, end pointer and size of the list/queue. For NUM_QUE queues, NUM_QUE+1 Lists must be implemented, extra list being the free list.

Hardware operations are explained with help of ANSI C model. Please note that port list size is not implemented in ANSI C Model but is integral part of hardware for debug purposes. 

typedef unsigned char byte;

#define NUM_BUF    512
#define BUF_SIZE   64
#define MEM_SIZE   (NUM_BUF*BUF_SIZE)
#define NUM_QUE    16

// Replaces *next or Link Pointers
// All pointer should have number of bits N where 2^N = NUM_OF_BUF
// Possible Address are 0 – (NUM_BUF-1)
// For example for 512, pointer width is 9. For example,
//              <bits9> linkmem[NUM_BUF];
int linkmem[NUM_BUF];

// Memory Size: NUM_BUF*BUF_SIZE.
//        Each Buffer Starts at K*BUF_SIZE where K: 0-(NUM_BUF-1)
//        Memory Address is Mapped by K*BUF_SIZE+L where L:0-(BUF_SIZE-1)
byte buf_arr[MEM_SIZE];   // Replaces struct data buffer

// Free List & Que Pointer are of same width as linkmem
int flStart, flEnd;
int qStart[NUM_QUE], qEnd[NUM_QUE];

// Any number out of bound is considered NULL
//     -999 is safe bet for now.

All data structures need to be Initialized after reset, because Link Memory and queue information contains invalid data at reset. All nodes must be added to Free List, indicating that all nodes are free after reset. Initialization requires minimum NUM_BUF cycles and the chip can not be used in normal operational mode during this period. Please look at following figure for further explaination of initialization sequence. For simplicity, a Link Memory for 10 buffers is shown with 2 Port Lists only.

 

linklisthw00

As shown in above figure, Link Memory is initialized in incremental fashion with free list start pointer assigned to zero and free list end pointer assigned to NUM_BUF-1 (Last buffer address). All queues/port lists (except free list) are initialized to NULL (-999).

 // Initialize
//     * Initialize Free List
//     * Initialize Link memory
//     * Initialize Queue Lists
void init (void) {
   int i;

   // Initialize Free List
   // Initial Buffer Address is 0 and End buffer is NUM_BUF-1
   flStart = 0;
   flEnd = NUM_BUF-1;

   for (i = 0; i < NUM_BUF; i++)
     linkmem[i] = i+1;

   linkmem[NUM_BUF-1] = -999;   // Acts as NULL

   // Initial Queue Lists
   for (i = 0; i < NUM_QUE; i++) qStart[i] = -999;
   for (i = 0; i < NUM_QUE; i++) qEnd[i] = -999;

}

Leave a Reply

Your email address will not be published. Required fields are marked *