Linked List Implementation in ASIC – Hardware

2 commands per cycle

First, intuitive step is to avoid such scenario by architecture design i.e. by making large buffer or by providing FIFO as temporary storage for data etc. If this performance requirement is still must, there are ways to improve performance for worst case scenario by allowing temporary memory leaks. But cost function of this solution is very high and long term throughput is still one queue-command per cycle.

First improvement can be by increasing Link Memory Access throughput. Implementing Link Memory in registers is one option but is very silicon intensive. Another way is to use three port memory which has one write port and two read ports. This memory can be constructed with two similar memories with write ports tied together so same data is written in both memories and remaining two ports provided as independent read ports. Since each queue -command requires 1 read and 1 write to Link Memory, half of the problem is the solved i.e. 2 reads and 1 write can be performed (need is of 2 writes).

Second improvement is to defer these write till worst case scenario is over. In real systems, It is very unlikely that there will be 2 queue-commands issued forever. In fact, even having one queue command per cycle is very unlikely. The deferred write can only be of deallocation/de-queue request, because allocated nodes are required to store data so we can not mess with allocation request. What it means is that two allocation requests can not be supported even with this modifications.

Deferred writes are stored in a special FIFO.Since, this FIFO stores memory leaked buffer and can be called leaked buffer FIFO or transit FIFO, as shown in following figure.


Addition of three port Link Memory and transit buffer FIFO permits us to achieve worst case performance of 2 commands per cycle. SImilar improvements may be made to support high performance requirements.

Please comment or provide any suggestion, you might have to improve Linked List performance. This article can be discussed in forum .

Disclaimer, the evil necessity: Posted views are of author only and this website and author are no way responsible for any damages caused by usage of this information.

Leave a Reply

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