Browse Prior Art Database

Technique for Improving Search Performance of a Software-based Search Engine

IP.com Disclosure Number: IPCOM000015922D
Original Publication Date: 2002-Aug-24
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 95K

Publishing Venue

IBM

Abstract

The proposal involves a technique for improving the search performance of a software-based search engine through a special organization/encoding of the data structure. The proposal relates specifically to a search engine that is based on the BART (Balanced Routing Table) search algorithm. Two versions of the BART algorithm for SRAM and wide embedded memory technologies are presented in [1] and [2]. The proposed techniques is applicable only to the wide embedded memory version of the BART algorithm. In this example, the compressed table is searched by performing two parallel comparisons involving the (two) entries in the block selected by the compressed index that is extracted from the search key segment (named "segment 2"). A typical size of each entry would be W 32 bits. Many current processor architectures are also based on 32-bits registers. This means that only one entry can be stored in a single 32-bit register and therefore only one entry can be processed at a time. In order to facilitate processing multiple entries in parallel (i.e., performing multiple parallel comparisons as described in [2]) the data structure of Fig. 1 is reorganized as shown in Fig. 2. If now two concatenated copies of the search key segment are stored in a register R1, the first two fields tval1 and tval2 of the selected block are loaded into a register R2, and the next two fields tmask1 and tmask2 are loaded into a register R3, then the comparison of the search key segment against the test values stored in the two entries in the selected block can be performed fully parallel using the following instructions:

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

Page 1 of 3

Technique for Improving Search Performance of a Software-based Search Engine

   The proposal involves a technique for improving the search performance of a software-based search engine through a special organization/encoding of the data structure. The proposal relates specifically to a search engine that is based on the BART (Balanced Routing Table) search algorithm. Two versions of the BART algorithm for SRAM and wide embedded memory technologies are presented in [1] and [2]. The proposed techniques is applicable only to the wide embedded memory version of the BART algorithm.

In this example, the compressed table is searched by performing two parallel comparisons involving the (two) entries in the block selected by the compressed index that is extracted from the search key segment (named "segment 2").

A typical size of each entry would be W = 32 bits. Many current processor architectures are also based on 32-bits registers. This means that only one entry can be stored in a single 32-bit register and therefore only one entry can be processed at a time.

In order to facilitate processing multiple entries in parallel (i.e., performing multiple parallel comparisons as described in [2]) the data structure of Fig. 1 is reorganized as shown in Fig. 2. If now two concatenated copies of the search key segment are stored in a register R1, the first two fields tval1 and tval2 of the selected block are loaded into a register R2, and the next two fields tmask1 and tmask2 are loaded into a register R3, then the comparison of the search key segment against the test values stored in the two entries in the selected block can be per...