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

Maze routing on a hypercube multicomputer

โœ Scribed by Youngju Won; Sartaj Sahni

Publisher
Springer US
Year
1988
Tongue
English
Weight
1010 KB
Volume
2
Category
Article
ISSN
0920-8542

No coin nor oath required. For personal study only.

โœฆ Synopsis

The implementation of Lee's maze routing algorithm on an MIMD hypercube multiprocessor computer can follow several plausible mappings and synchronization strategies. These are evaluated experimentally on an NCUBE/7 hypercube computer with 64 processors. Different grid partitioning and mapping strategies result in a different balance between computation and communication time. The total routing time is significantly impacted by the synchronization and termination detection scheme used. Further, by rearranging the computation, it is possible to overlap much of the interprocessor communication with the computation and realize a significant reduction in the overall run time. By choosing the right partitioning and synchronization scheme and by overlapping computation and communication, a good speedup is obtained on large routing grids.

๐Ÿ“œ SIMILAR VOLUMES

Computing Hough transforms on hypercube
Computing Hough transforms on hypercube multicomputers
โœ Sanjay Ranka; Sartaj Sahni ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Springer US ๐ŸŒ English โš– 843 KB

Efficient algorithms to compute the Hough transform on M1MD and SIMD hypercube multicomputers are developed. Our algorithms can compute p angles of the Hough transform of an N x N image, p < N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ~) processors. We also