Portal de Periódicos da CAPES

Minimizing communication in the bitonic sort

2000; Institute of Electrical and Electronics Engineers; Volume: 11; Issue: 5 Linguagem: Inglês

10.1109/71.852399

2161-9883

Jae-Dong Lee, Kenneth E. Batcher,

Advanced Data Storage Technologies

This paper presents bitonic sorting schemes for special-purpose parallel architectures such as sorting networks and for general-purpose parallel architectures such as SIMD and/or MIMD computers. First, bitonic sorting algorithms for shared-memory SIMD and/or MIMD computers are developed. Shared-memory accesses through the interconnection network of shared memory SIMD and/or MIMD computers can be very time consuming. A scheme is introduced which reduces the number of such accesses. This scheme is based on the parity strategy which is the main idea of the paper. By reducing the communication through the network, a performance improvement is achieved. Second, a recirculating bitonic sorting network is presented, which is composed of one level of N/2 comparators plus an /spl Omega/-network of (log N-1) switch levels. This network reduces the cost complexity to O(N log N) compared with the O(N log/sup 2/ N) of the original bitonic sorting network, while preserving the same time complexity. Finally, a simplified multistage bitonic sorting network, is presented. For simplifying the interlevel wiring, the parity strategy is used, so N/2 keys are wired straight through the network.