(A) VLSI implementation of tuple selection chip based on linear array processors

Abstract

In relational DBMS, the time complexity of selection operation is O(p·n), p: the number of predicates in search condition, to process n tuples. this can be reduced to O(1) by inserting on-the-fly filter between secondary memory and main memory. We designed hardware selector which compares byteserial tuples with search condition. It contains simple linear array processors and evaluator. To perform selection, each processor evaluate charged predicate parallelly and the results of each processor are combined in evaluator to verify search condition. VLSI implementation of hardware selector was performed on cell-based CAD system. Functional simulation reports hardware selector process various data types. Floorplanning for layout is performed hierarchically. The die size of chip is 0.894×0.795 Cm$^2$ with 2μ n-well process technology and 23001 transisters are contained in. From timing analysis of generated layout, the data transfer rate can be maximum 10 Mbytes/sec.