✦ LIBER ✦

Optimally Scaling Permutation Routing on Reconfigurable Linear Arrays with Optical Buses

✍ Scribed by Jerry L. Trahan; Anu G. Bourgeois; Yi Pan; Ramachandran Vaidyanathan

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 171 KB
Volume: 60
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.2000.1643

No coin nor oath required. For personal study only.

✦ Synopsis

We present an optimal and scalable permutation routing algorithm for three reconfigurable models based on linear arrays that allow pipelining of information through an optical bus. Specifically, for any P N, our algorithm routes any permutation of N elements on a P-processor model optimally in O( N P ) steps. This algorithm extends naturally to one for routing h-relations optimally in O(h) steps. We also establish the equivalence of the three models: linear array with a reconfigurable pipelined bus system,

📜 SIMILAR VOLUMES

Efficient Parallel Algorithms for Hierar

Efficient Parallel Algorithms for Hierarchical Clustering on Arrays with Reconfigurable Optical Buses

✍ Chin-Hsiung Wu; Shi-Jinn Horng; Horng-Ren Tsai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 225 KB

Clustering is a basic operation in image processing and computer vision, and it plays an important role in unsupervised pattern recognition and image segmentation. While there are many methods for clustering, the single-link hierarchical clustering is one of the most popular techniques. In this pape

Communication-Efficient Sorting Algorith

Communication-Efficient Sorting Algorithms on Reconfigurable Array of Processors With Slotted Optical Buses

✍ Mounir Hamdi; Chunming Qiao; Yi Pan; J. Tong 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 222 KB

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 implementatio