This article provides foundation for ASIC linked list design architecture considerations. First, an ANSI-C model is presented to explain and mimic ASIC Linked List Implementation. After this, basic linked list operations are identified and performance analysis is performed. At the same time, various tradeoffs are  discussed and few unique methods are presented to increase Link List performance and throughput.

In Linked List Implementation in ASIC, overview of dynamic memory allocation in ASIC was presented. This article further explains the need for Linked List and provides foundation for software implementations for Linked List. Also, a migration path from very dynamic linked list implementation to some-what static implementations of Linked List is explained. A typical pointer based Link List implementation in ANSI C is described and later, an array based link list software implementation is explained.

This is starting of series of articles on Link List Memory Implementation in Hardware. First overview article is presented (this article). Later, software implementation specific details are presented in another article. Last, Hardware specific implementation is analyzed and architecture is drived from software implementation.

In networking ASICs, typically aggregated bandwidth of a system is known a priory. But how this bandwidth is distributed across different ports is not known, which requires dynamic memory allocation to be implemented in hardware/ASIC.

In many real systems, size of memory and objects are not known and can not be determined statically and is mainly dependent on data set during run time. For example, a compiler for a programming language will maintain symbol tables and type information which is dynamically constructed by reading the source program where source program can be of any size. In fact, there are very few large programs (or none), not having dynamic memory allocation. Dynamically created data structures like trees, linked lists and hash tables (which can be implemented as arrays of linked lists) are key to the construction of many large software systems.