Since sorting is one of the most fundamental operation in a computer system, many hardware sorters have been developed so far. In this thesis, we present multi-functional sorting chip implemented on CAD workstation. This sorting chip, called P-TMS (Pipeline-Tree Merge Sorter), has capability of exploiting pipeline merge sorting and tree merge sorting. A set of the P-TMS, can organize several sorting machines such as pipeline sorting machine, tree sorting machine and combined sorting machine. The combined sorting machine have configuration between a pipeline sorting machine and tree sorting machine. In case of combined sorting machine, the time complexity and number of processors become to O(n) and O($\log_2$ γ) respectively, where γ is always less than n. Especially, a number of records to be sorted are not restricted by a capacity of P-TMS but of external memory. We have designed by performing functional simulation, symbolic layout, and timing analysis of P-TMS chip with aids of GENESIL silicon compiler which can generate symbolic layout data from some higher level description. The size of the implemented in up to $1.05\times1.04 cm^2$ with CMOS 2$\mu$ n-well process technology and maximum data rate of 5.7 Mbytes/sec.
본 논문에서는 CAD 장비하에서 구현된 다기능 정렬 칩 (sorting chip)을 소개한다. P-TMS (Pipeline-Tree Merge Sorter)라 불리는 이 정렬 칩은 파이프라인 정합 정렬 (pipeline merge sorting)과 트리 정합 정렬 (tree merge sorting)을 수행할 수 있다. 여러개의 P-TMS 칩으로 파이프라인 정합 정렬기 (pipeline sorting machine), 트리 정합 정렬기 (tree sorting machine)와 연합 정렬기 (combined sorting machine)을 구성할 수 있으며, 연합 정렬기는 파이프라인 정합 정렬기와 트리 정합 정렬기로 배치될 수 있다.
이 연합 정렬기에 있어서 시간 복잡도와 프로세서 갯수는 O(n)과 $O(\log_2r)$이며, 여기서 r은 항상 n보다 적은 수이다. 특히, 정렬하고자 하는 레코드 (record)의 갯수는 P-TMS 칩의 갯수에 제약받지 않고 다만 외부 기억 장치의 크기에 제한받는다.
P-TMS 칩은 GENESIL이라하는 실리콘 컴파일러 (silicon compiler)하에서 functional simulation, symbolic layout, timing analysis를 통하여 설계되었다. 구현된 칩의 크기는 CMOS 2-micro n-well process에서 $1.05 \times 1.04cm^2$이며, 최대 데이타 전송 속도는 5.7 Mbytes/sec 이다.
