Browse Prior Art Database

Small Linked List Table Handling Simplification Using CAM

IP.com Disclosure Number: IPCOM000237147D
Publication Date: 2014-Jun-05
Document File: 5 page(s) / 137K

Publishing Venue

The IP.com Prior Art Database

Abstract

Linked lists are commonly used for handling chains of cyclic structures for scheduling and passing commands or tokens to nodes in a controlled sequence. For example in Profibus, the List of Master (LMS) stations table is a linked list where a Profibus master can use its address as an index into this table, at the index resides the address of the master that this station will pass the token to. Therefore finding the master that this station passes the token to is computationally efficient using a simple indexed lookup. However, using software to find the master that passes the token to this station, or indeed any station, can take a relatively large number of cycles as the table needs to be walked using successive index dereferencing.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Small Linked List Table Handling Simplification Using CAM

Abstract

Linked lists are commonly used for handling chains of cyclic structures for scheduling and passing commands or tokens to nodes in a controlled sequence. For example in Profibus, the List of Master (LMS) stations table is a linked list where a Profibus master can use its address as an index into this table, at the index resides the address of the master that this station will pass the token to. Therefore finding the master that this station passes the token to is computationally efficient using a simple indexed lookup. However, using software to find the master that passes the token to this station, or indeed any station, can take a relatively large number of cycles as the table needs to be walked using successive index dereferencing.

Problem Description

Figure 1 below details the format of the LMS and explains the performance issue when finding the station that passes the token to this station using the LMS.

Figure 1 Profibus LMS Problem Description

 
 

Profibus addresses are in the range 0-126, any value greater than this, in the LMS, can be used to designate an unused network address. In this case the value 255 (0xFF) is being deployed to this aim. This type of table usage is specified by (i). Figure 1 illustrates well that predecessor identification is inefficient regarding a linked list table formatted in this manner.

A simple solution would be to have a successor and predecessor table however this requires double the memory and necessitates more complex handling for managing the tables, especially if synchronization is required in a multi-core environment. Therefore an alternative solution relying on a single table is sought.

Solution Architecture

Figure 2 shows the solution architecture.

Figure 2 Solution Architecture

 

One solution to the intensive nature of using software for predecessor identification with the table described in (i) is to use a small CAM. This CAM supports parsing through a table, or a subset of the table, to identify either:

  1. A value contained within the range of offsets searched
  2. The maximum value found within the search range
  3. The minimum value found within the search range

The CAM also supports a wildcard feature for ignoring a specific value, or specific values, during its search. Note that the RISC engine can process other instructions while the CAM is orthogonally performing its search.

Minimum and Maximum Search Using the Mini-CAM

Figure 3 details the CAM functionality when using min and max modes.

Figure 3 Linked List Predecessor and Successor Identification Minimum and Maximum

 
.

Note Figure 3 shows that the LMS table is configured differently to that of Figure 2. The table in Figure 3 is implemented where each entry in the list corresponds to the index. The CAM’s wildcard option is programmed to ignore the value 255. To find the predecessor of station 2 firstly a maximum operation is performed encompassing indexes 0 to 2-1. No maximum result res...