Browse Prior Art Database

Fast parsing using multiple parallel comparator units

IP.com Disclosure Number: IPCOM000029072D
Original Publication Date: 2004-Jun-15
Included in the Prior Art Database: 2004-Jun-15
Document File: 3 page(s) / 110K

Publishing Venue

IBM

Abstract

A technique is proposed for optimizing the implementation of a parsing engine based on a programmable state machine.

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

Page 1 of 3

Fast parsing using multiple parallel comparator units

The paper "XML Accelerator Engine" by van Lunteren et al. [1] presents a new concept for accelerating the parsing of XML documents. Section IV-B in [1] describes how the XML accelerator engine can perform a string compare operation for detecting the occurrence of selected character strings in an input character stream. This string compare operation involves a so called character memory and is performed under tight control of a (programmable) state machine as illustrated in Figure 9 in [1]. For a detailed description is referred to [1].

The presented idea extends the compare function discussed in [1] in two ways:

(1) the use of multiple comparator units under control of the (programmable) state machine instead of only one compare unit as described in [1]. (2) the use of a wider character memory to process multiple characters in a single step and/or clock cycle

The objective is to improve the performance of the parsing engine by increasing the number of characters that can be processed (e.g., compared) per clock cycle.

The presented idea will now be explained using the example shown in Figure 1. This example involves four comparator units as shown in Figure 1 (b). The character memory stores up to 8 characters in each memory location as shown in Figure 1 (c). In addition, also four masks are stored in each memory location, one corresponding to each comparator unit, which select the characters that have to be loaded in each of the comparator units.

The state transition diagram illustrated in Figure 1 (a) contains a transition to state s0 (shown at the top) which is associated with an instruction "load comp[7]". This instruction will load the characters that are stored at the memory location corresponding to address (or index) 7 in the character memory, into the comparator units under control of the four masks contained in the same memory location in the character memory. Figure 1 (b) shows the result of this load operation. This figure also shows the "load mask" for each comparator unit in binary notation. For example, the mask corresponding to comparator unit 1 equals 11111000b (F8h). The set bits in this mask indicate that the characters at the corresponding character positions within the selected memory location in the character memory, have to be loaded into the comparator unit. In this case, the five left-most characters are loaded into comparator unit 1 as can be seen in Figure 1 (b). The characters do not necessarily have to be loaded from adjacent character positions within a memory location. For example, the "load mask" for comparator unit 2 equals 100000111b (87h). As a result the left-most character and the three right-most characters are loaded from the memory location into the comparator unit (note that these characters are stored at adjacent character positions within the comparator unit). Comparator unit 3 and 4 are loaded in a similar way based on the two remaining...