Browse Prior Art Database

Improved Table Lookup

IP.com Disclosure Number: IPCOM000021515D
Publication Date: 2004-Jan-21
Document File: 3 page(s) / 308K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method that improves table lookups, specifically addressing the need to move through a linked list in memory when the processor executes at a much faster rate.

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 72% of the total text.

Improved Table Lookup

Disclosed is a method that improves table lookups, specifically addressing the need to move through a linked list in memory when the processor executes at a much faster rate.

Background

When a processor operates faster than external memory, the latency associated with accessing the memory is quite large and the processor typically has to idle until its I/O request is completed. Often, performance of the system depends upon how efficiently the table lookup can be performed. Therefore, it is essential to find ways to improve the table lookup to improve performance. A linked list of elements is the main component of tables (such as hash tables, Trie tables etc.), which are used for packet processing (see Figure 1).

General Description

The disclosed method pre-fetches data for the next iteration, while the data in the current iteration is processed (see Figure 2). While the program moves through the list, the pre-fetching continues. For the last entry there is no need to pre-fetch the data. When a match is found before the list is terminated, the pre-fetched data is discarded.

This method reduces the idle cycles for the processor accessing the list in memory, and therefore improves the performance; while the data is pre-fetched for the next iteration, the processor has enough data in the current iteration to operate on before waiting for the I/O to complete.

The disclosed method is especially suitable for network processors where each packet is subjected to...