Architectural support for SWAR text processing with parallel bit streams: the inductive doubling principle

Parallel bit stream algorithms exploit the SWAR (SIMD within a register) capabilities of commodity processors in high-performance text processing applications such as UTF-8 to UTF-16 transcoding, XML parsing, string search and regular expression matching. Direct architectural support for these algorithms in future SWAR instruction sets could fur-ther increase performance as well as simplifying the pro-gramming task. A set of simple SWAR instruction set ex-tensions are proposed for this purpose based on the princi-ple of systematic support for inductive doubling as an al-gorithmic technique. These extensions are shown to signifi-cantly reduce instruction count in core parallel bit stream al-gorithms, often providing a 3X or better improvement. The extensions are also shown to be useful for SWAR program-ming in other application areas, including providing a sys-tematic treatment for horizontal operations. An implemen-tation model for these extensions involves relatively sim-ple circuitry added to the operand fetch components in a pipelined processor