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.

At a given time, a port may be using 95% of bandwidth and remaining 5% being distributed to remaining ports. Allocating maximum resources (in this case, Memory) to each port is not economical. For example, if a port may utilize up to 95% of bandwidth then memory needed is 0.95*k*N, where k is arbitrary constant defined by system requirements. Another possibility is to have shared resources/memory and distribute the resources as required (i.e. dynamic allocation of resources/Memory). Memory required in this scenario will be k + overhead (~1.2k). For large N (typically it can be 16-64), memory saving can be multifold. In fact, Link List Manager is one the most complicated block in Networking ASICs.

Memory allocation provides a way to dynamically create buffers and arrays. Dynamic means that the space is allocated in memory as the program is executing. On many occasions the sizes of objects will not be known until run time. For instance, the length of a string a user inputs will not be known prior to execution. The size of an array may depend on parameters unknown until program execution. Certain data structures such as linked lists utilize dynamic memory allocation.

In software world, operating systems has to support dynamic memory management and very little attention is paid by programmer on how allocation is being performed (Dynamic Memory Allocation Performance). However, this allocation mechanism has to be built into the ASIC and etched onto the silicon. And that is focus of this discussion.

In next article, software implementations of Link List are briefly explained. A typical pointer based Link List implementation in ANSI C is shown and analyzed. After that array based software implementation is designed and explained since Array based implementations are simpler to implement in ASIC.

And lastly, Link List requirements are analyzed from Hardware specific viewpoint. Also a typical architecture is shown and possible bottlenecks are identified. At the same time, how various issues can be resolved are presented.

Stay Tuned... 

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.