Sorting is a fundamental operation in data processing. Therefore specialized hardwares for the sort operation are adopted for fast processing. This thesis describes a taxonomy of this hardware sorter according to the environmental characteristics the data access characteristics and the representation of sort ordering. And the design and implementation of a systolic sorter and a pipeline merge sorter is introduced. The systolic sorter consists of a number of identical cells, which are connected as a form of two dimensional array. The systolic sorter has the size complexity of O($N^2$) and the time complexity of O(N). And a pipeline merge sorter which has more simple architecture than ever developed is designed and simulated. The simulation result indicates it has the same performance as the others in spite of its simple architecture. It has the time complexity of O(N) and the size complexity of O(logN). The time complexity of above two sorters indicates that those sorters can make the full use of the transfer time when used between hard disk and host computer. This thesis proves that in the case of using hardware sorter in database management system, the primitive data base operation such as projection, selection, join and set operation can be executed more effectively than without sorter.
정렬은 데이타 처리에 있어서 기본적인 연산이다. 그러므로 그 정렬연산을 빠르게 하기위해서 특화된 하드웨어를 많이 채용하고 있다. 본 논문은 먼저 하드웨어 정렬기에 대한 그 쓰이는 환경에 따르는 분류 - 데이타 입출력 관계 및 최종 정렬순서의 표현 등에 의한 분류 - 에 관하여 언급하고 있다. 또한 실제 하드웨어 정렬기의 대표적인 형태인 시스톨릭 정렬기와 파이프 라인 결합 정렬기를 설계하고 논리회로의 타당성에 관하여 증명하고 있다. 이 시스톨릭 정렬기는 2차원으로 배열된 동일한 기본 회로 단위(cell)들을 이웃하는 회로단위들과 연결하여 전체 하드웨어가 병렬로 정렬연산을 하도록 하는 구조를 가지고 있다. 이 시스톨릭 정렬기는 O($N^2$)의 크기 복잡도(size complexity)와 O(logN)의 시간 복잡도( time complexity )를 갖는다. 그리고 파이프 라인 결합 정렬기는 여태껏 개발된 형태보다 간단하면서도 다른 것에 비해 떨어 지지않는 성능을 갖는다. 이 파이프 라인 결합 정렬기는 O(N)의 시간 복잡도와 O(logN)의 크기 복잡도를 갖는다. 두 하드웨어 정렬기의 시간 복잡도를 통해 볼 때 이 정렬기가 후위 데이타처리 기계로 쓰인다면 하드 디스크와 호스트 컴퓨터사이의 데이터 전송시간을 완전히 낭비 없이 쓸 수 있다는 것을 알 수 있다. 하드웨어 정렬기가 데이타베이스 관리체계에 활용된다면 추출, 선택, 결합 및 집합연산과 같은 기본적인 데이타베이스 연산이 정렬기가 없을 때에 비해 훨씬 더 효율적으로 수행될 수 있음을 알 수 있다.