Acceleration of nonnumeric operations using hardware support for the Ordered Table Hashing algorithms

The paper introduces a new approach to acceleration of nonnumeric, database, and information retrieval operations. While traditional techniques accelerate the most time-critical high-level software constructs, we propose novel low-level primitives and demonstrate how these primitives improve database operations. Radix sorting, hashing, and bit-vector operations are used to develop a new class of nonnumeric algorithms - OTHER (Ordered Table Hashing and Radix sort algorithms) - based on low-level hashing operations Init, Mark, and Scan. We have proposed and evaluated two hardware accelerators for OTHER algorithms. It is shown that a low complexity hardware support (less than 10 K transistors) can significantly improve the performance of nonnumeric operations.