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.
관계형 DBMS에서 n개의 튜플을 처리하기 위한 선택 연산의 시간 복잡도는 O(pn)이다 (p : 선택 조건의 프레디키트의 수). 보조 기억장치와 주 기억장치 사이에 온더플라이 필터를 삽입함으로써 시간 복잡도를 O(l)로 줄일 수 있다. 본 논문에서는 선택 조건에 따라 바이트 단위의 순차적인 튜플을 비교할 수 있는 하드웨어 선택기를 설계하였다. 설계된 선택기는 간단한 선형 어레이 처리기와 이밸류에이터로 구성되었다. 선택 연산을 수행하기 위하여 각 처리기는 할다된 프레키트를 병렬적으로 처리하며 각각의 결과들은 선택 조건에 따라 이밸류에이터에서 최종 선택 결정을 한다. 선택기의 VLSI 구현은 cell-based CAD 시스템에서 수행되었다. 기능 모의 실험의 결과로 설계된 선택기는 다양한 데이타 형태를 처리함을 확인했다. 레이아웃을 위한 floorplanning이 계층적으로 수행되었으며 최종 칩의 다이 크기는 2u n-well 프러세스 기술로 0.894×0.795 Cm$^2$이고 23001개의 트랜지스터를 포함하고 있다. 타이밍 분석에 의해 데이타 처리 속도는 최대 10 Mbytes/sec 임을 확인했다.
