๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Optimal Sorting Algorithm on Reconfigurable Mesh

โœ Scribed by J. Jang; V.K. Prasanna

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
853 KB
Volume
25
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper shows nontrivial ways to use the Reconfigurable Mesh to solve several basic arithmetic problems in constant time. These solutions are obtained by novel ways to represent numbers and by exploiting the reconfigurability of the architecture. In particular, a constant time algorithm to add (n k)-bit numbers using an (n \times n k) bit model of Reconfigurable Mesh is shown. Using these techniques, an optimal sorting algorithm on the Reconfigurable Mesh is derived. The algorithm sorts (\mathrm{n}) numbers in constant time using (n \times n) processors. Our algorithm uses optimal size of the mesh to sort (n) numbers in constant time and satisfies the (A T^{2}) lower bound of (\Omega\left(n^{2}\right)) for sorting (n) numbers in a variation of the word model of VLSI. The sorting algorithm runs on all known variations of the Reconfigurable Mesh model. 1995 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Optimal Algorithms for Constrained Recon
Optimal Algorithms for Constrained Reconfigurable Meshes
โœ Bryan Beresford-Smith; Oliver Diessel; Hossam ElGindy ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 220 KB

model the propagation delay on a bus-unit 1 by a constant, and to only permit the class of algorithms, denoted by A k , which configure bus components bound in size to at most k bus-units to run on the model. We give a detailed description of our reconfigurable mesh model in the following section.

Sorting n Numbers on n ร— n Reconfigurabl
Sorting n Numbers on n ร— n Reconfigurable Meshes with Buses
โœ M. Nigam; S. Sahni ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 857 KB

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.

Time-Efficient Maze Routing Algorithms o
Time-Efficient Maze Routing Algorithms on Reconfigurable Mesh Architectures
โœ F Ercal; H.C Lee ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 396 KB

The routing problem is one of the most widely studied problems in VLSI design. Maze-routing algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on C. Y. Lee's algorithm (1961, IRE Trans. Electron. Comput. (Sept.), 34