(A) VLSI implementation of merge sort algorithm on linearly and tree connected processor arrays

Abstract

Since sorting is one of the most fundamental operation in a computer system, many hardware sorters havew 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 merege sorting. A sewt of the P-TMS, can organize several sorting machines such as pipeline 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\,\gamma$) respectively, where $\gamma$ 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 CMOS2 $\mu$ n-well process technology and maximum data rate of 5.7 Mbytes/sec.