Linked List Implementation in ASIC – ANSI C

linklist00

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.

Continue reading “Linked List Implementation in ASIC – ANSI C”

Linked List Implementation in ASIC

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.

Continue reading “Linked List Implementation in ASIC”

Dynamic Memory Allocation Performance

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.

Continue reading “Dynamic Memory Allocation Performance”

8 Queens on A Chessboard

Image

Image Placing 8 Queens on a chessboard is a classic problem and is one of the good software interview question. Following code is my take on this problem. Though instead of starting queen placement at predefined position (at 0,0 or at a corner), 1st queen placement in first row can be specified by user. Discussion/Comments are welcome, please click here to go to discussion forum.

An fun webpage is created with CGI/PERL script where above algorithm can be seen in work. Please go here to experiment with the algorithm.

Continue reading “8 Queens on A Chessboard”