Acceleration of nonnumeric operations using hardware support for the Ordered Table Hashing algorithms
Tóm tắt
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.
Từ khóa
#Acceleration #Hardware #Database machines #Very large scale integration #Information retrieval #Sorting #Statistics #Time factors #Digital arithmetic #LogicTài liệu tham khảo
10.1145/356643.356645
10.1145/320831.320834
10.1145/321341.321349
kitsuregawa, 1987, Design and Implementation of High Speed Pipeline Merge Sorter with Run Length Tuning Mechanism, Database Machines and Knowledge Base Machines, 89
aleksic, 1986
andrews, 1990, The AS/400 Alternative
10.1016/0165-6074(88)90368-7
1986, 80386 Programmer's Reference Manual
jovanov, 1993, The Architecture of Accelerator for Database Operations
10.1109/HICSS.1992.183180
10.1109/12.641938
stojkov, 1993, An Implementation of Relational Algebra Operations
feller, 1968, An Introduction to Probability Theory and Its Applications
10.1109/TC.1978.1675200
knuth, 1973, The Art of Computer Programming Vol 3 Sorting and Searching
10.1007/978-1-4613-1679-4_8
date, 2000, An Introduction to Database Systems
miller, 1995, Parallel Architectures for Data/Knowledge Based Systems
10.1109/TC.1986.1676715
10.1109/HICSS.1992.183179
10.1109/71.744832
10.1109/40.108569
10.1109/HICSS.1992.183181
10.1145/320064.320065
10.1109/40.108573
10.1109/32.52778
10.1002/spe.4380231105
date, 1993, A Guide to SQL Standard
10.1145/362686.362692
eustace, 1994, ATOM: A Flexible Interface for Building High Performance Program Analysis Tools
2002
10.1007/978-3-642-95432-0_3
10.1109/32.129222
dewitt, 1987, A Single User Evaluation of the Gamma Database Machine, Database Machines and Knowledge Base Machines, 370
10.1145/602259.602283