Communication-efficient sorting algorithms on reconfigurable array of processors with slotted optical buses

The reconfigurable array with slotted optical buses (RASOB) has recently received a lot of attention from the research community. In this paper, we first discuss the reconfiguration methods and communication capabilities of the RASOB architecture. Then, we use this architecture for the implementation of efficient sorting algorithms on the 1D RASOB and the 2D RASOB. Our parallel sorting algorithm on the 1D RASOB is based on an efficient divide-and-conquer scheme. It sorts N data items using N processors in O(k) communication cycles where k is the size of the data items to be sorted in bits. We further develop a parallel sorting algorithm on the 2D RASOB based on the sorting algorithm on the 1D RASOB in conjunction with the well known Rotatesort algorithm. Similarly, this algorithm sorts N data items on a 2D RASOB of size N in O(k) communication cycles. These sorting algorithms an much more efficient than state-of-the-art sorting algorithms on reconfigurable arrays of processors with electronic buses using the same number of processors. (C) 1999 Academic Press