VLSI (Very Large Scale Integration) Optimality of the AKS Sorting Network

摘要

Ajtai, Komlos, and Szemeredi recently proposed a sorting network of O(nlogn) comparators and O(logn) depth. Their construction is of great theoretical interest, for it shows that O(nlogn) comparisons suffice to sort n elements, even under the constraint that comparisons be nonadaptively executed in O(logn) parallel stages. At present, the AKS network appears not suitable for practical implementations, due to the large value of the constraints; however, improvements are conceivable that could make the network more attractive for real-world applications, It is therefore natural to ask what is the performance of the AKS network in the synchronous VLSI model of computation which has been proposed to capture the essential features of planar very large scale integration as a computing environment. In this model it is known that any chip capable of sorting n words of length q = (1+ alpha)logn. with alpha > 0, must satisfy a certain relationship where A is the chip area, and T is the computation time.