Sorting is a fundamental process in many computer and communication systems. For example, sorting plays an important role in parallel computing and also in packet switching. In the case of packet switching, it is known that a packet switch based on an interconnection network such as a banyan network is internally non-blocking, if the packets inputted to the banyan network are sorted according to their destination addresses. Thus, an internally non-blocking packet switch may be formed by connecting a sorting network and a banyan network in sequence. In addition, sorters play an important role in the areas of relational databases. For example, sorters may be utilized to perform relational database operations such as join operations in a distributed computer system.
Many sorting networks and algorithms have been proposed. (See e.g., D. E. Knuth, "The Art of Computer Programming", Vol. 3, Addison Wesley, Reading, Mass., 1973). Recently, a network with a size on the order of nlogn for sorting n numbers has been discovered. (See e.g. M. Ajtai et al, "An O(nlogn) Sorting Network" Proc. 15.sup.th Annual ACM Symposium on Theory of Computing, 1983, pp. 1-9). Although this network is asymptotically optimal, it performs poorly for practical values of n.
Merging is a process of arranging m ordered lists of numbers into one ordered list. In his pioneer paper, "Sorting Networks and Their Applications" AFIPS Proceeding of the Spring Joint Computer Conference, 1960, pp. 307-318, K. E. Batcher proposed two binary merging networks. A binary merging network receives two ordered lists at its inputs and merges these lists to form a single ordered list at its outputs. A plurality of binary merging networks may be utilized recursively to form a sorting network. A recursive sorting network for sorting 2.sup.n input numbers into an ordered list comprises n stages. The first stage comprises 2.sup.n-1 two-by-two merging networks, each of which orders a pair of adjacent input numbers. Thus, the output of the first stage is 2.sup.n-1 ordered lists of two numbers each. The second stage comprises 2.sup.n-2 four-by-four merging networks, each of which merges two of the ordered lists outputted by the first stage. Thus, the second stage outputs 2.sup.n-2 ordered lists, each of which comprises four numbers. The third stage comprises 2.sup.n-3 eight-by-eight merging networks, each of which merges two of the four-number lists outputted by the second stage. This structure continues until in the last stage there is only one merging network which outputs a single ordered list comprising all of the input numbers.
The binary merging networks which are utilized in the above-described sorting network are themselves formed from 2.times.2 comparator modules which are organized into stages. In particular, an nxn binary merging network comprise log.sub.2 n stages, each of which comprises n/2 2 .times. 2 comparator modules.
A binary sorting network of the type described above has a number of disadvantages. Because each merging network utilized in the sorting network can sort at most two ordered lists, a relatively large number of stages and a correspondingly large number of merging networks are required. Furthermore, with each successive stage in the binary sorting network, the merging networks are increasingly larger and comprise increasingly large numbers of two-by-two comparator modules. In addition, the length of the interconnection wires between stages in a binary sorting network grows geometrically as the number of stages increases, although the logic complexity of the 2 .times.2 comparator modules remains the same. In fact, the overall latency of a binary sorting network may be dominated more by the propagation delays of interconnection wires than by the processing delays of the two-by-two comparator elements.
A great simplification in sorting networks formed recursively from merging networks would be achieved if merging networks were available which could merge more than two ordered input lists.
The problem of providing a merging network which can merge more than two ordered input lists is well known and is intimately related to the problem of forming a merging network from comparator modules which are larger than 2 .times. 2. These problems have not been completely solved heretofore.
A partial solution is provided by the ColumnSort network (see, e.g., F. T. Leighton, "Tight Bounds on the Complexity of Parallel Sorting", IEEE Trans. on Computer, Vol. 34, No. 4, 1985, pp. 344-354). The ColumnSort network is based on the transformation of matrices. However, this network cannot be utilized recursively to form a large sorter and is limited by a number of constraints on the dimensions of the matrices involved.
Accordingly, it is an object of the present invention to provide a merging network which merges more than two ordered input lists to form a single ordered output list.
It is a further object of the invention to provide a merging network which is formed by comparator modules which can be larger than two-by-two.
It is also an object of the present invention to provide a merging network which can be utilized recursively to form a large sorting network that has fewer stages and simpler interconnection wiring than the conventional binary sorting network.
USPTO Backgrounds
USPTO Backgrounds