The sorting operation which was regarded as a heavy load in computer application area, especially DBMS, is implemented into a specialized hardware VLSI chip so that more efficient sorting operation is guaranteed by.
It is reported that the theoretical lower bound for sorting without a hardware parallelism is the time complexity of O(n $log_2$ n) to sort n items. But it is also reported for that limit to be overcomed by using hardware parallelism. Then, our goal is to obtain the time complexity of O(n) with the size complexity of O ($log_2$ n) using a hardware parallelism.
For that goal, a two-way merge sorting is used for sorting algorithm and a pipelining is used for hardware parallelism. From those schemes, we developed a finite state machine which is adequate for the VLSI implementation of Pipelined Merge Sorter.
For the layout of such a VLSI pipelined merge sorter, some floor-planning methods are introduced and estimated the effects on chip performance for each method and consider test problems of chip in aspect of functional test, manufacturing defect coverage by fault simulation.
컴퓨터 응용 분야에서, 특히 데이터 베이스 관리 시스템, 큰 부하의 하나로 알려져 있는 Sorting 동작을 효과적으로 하기위하여 그 동작을 전담하는 특별한 Hardware 를 구현하는 것이 본 논문의 목적이다.
병렬처리 기법이 사용되지 않는 경우 n 개의 데이타를 정렬하는데 O(n $log_2$ n) 의 시간 복잡도가 걸린다고 알려져 있다. 그러나 병렬처리 기법이 적용 된다면 O($log_2$ n) 의 Hardware 복잡도를 가지고 O(n) 의 시간 복잡도로 정렬할 수 있다.
따라서 본 논문에서는 그러한 정렬을 위해서 Two-way Merge Sorting 알고리즘과 Pipelining 기법을 사용했다. 그러한 계획하에 VLSI 구현에 적합한 Pipelined Merge Sorter 를 설계하고 Layout 데이터를 얻기위하여 A-R Placement, TimberWolf, Hand Placement 등의 방법을 이용하여 Floorplan 하였다. 그리고 그 결과에 적절한 Cost function 을 적용하여 만족할 만한 성능을 얻을 수 있는 방법을 선정하였다. 또한 만들어 질 Chip 의 Test 를 위하여 Test 가 가능한 Latch 를 Controller 앞과 뒤에 배치함으로써 특정한 Test pattern 을 강제로 가하거나 가해진 Test pattern 의 결과를 관찰하여 원하는 동작을 하는지를 알 수 있게 하였다. 그와 더불어 Fault Simulation 을 통하여 몇개의 Block 에 대해 Fault Coverage 를 계산하였다.
그 결과 데이터들에 대한 정렬동작을 Hard Disk 와 Host Computer 사이의 데이터 전송시간을 이용하는 Pipelined Merge Sorter 를 하나의 Chip 으로 구현하였다. 완성된 PMS Chip 은 전체 크기가 371.7×358.7$mils^2$ 이고 동작 주파수가 4.27 Mbytes/sec 이며 54 개의 입출력 Pads 와 Test 를 위하여 10 개의 Pads 를 두었다.
