Sorting n Numbers on n × n Reconfigurable Meshes with Buses

✍ Scribed by M. Nigam; S. Sahni

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 857 KB
• Volume: 23
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1117

✦ Synopsis

We show how column sort and rotate sort can be implemented on the different reconfigurable mesh with buses (RMB) architectures that have been proposed in the literature. On all of these proposed RMB architectures, we are able to sort (n) numbers on an (n \times n) configuration in (O(1)) time. For the PARBUS RMB architecture, our column sort and rotate sort implementations are simpler than the (O(1)) sorting algorithms developed in Jang and Prasanna (International Parallel Processing Symposium, 1992) and Lin et al. (Proceedings of Ninth European Workshop on Parallel Computing, 1992). Furthermore, our sorting algorithms use fewer bus broadcasts. For the RMESH RMB architecture, our algorithms are the first to sort (n) numbers on an (n \times n) configuration in (O(1)) time. We also observe that rotate sort can be implemented on (N \times) (N \times \cdots \times N(k+1))-dimensional RMB architectures to sort (N^{k}) elements in (O(1)) time. (O 1994) Academic Press, Inc.