Abstract
The reconfigurable mesh (R-Mesh) has drawn much interest in recent years, due in part to its ability to admit extremely fast algorithms for a large number of problems. For these algorithms to be useful in practice, the R-Mesh must be scalable; that is, any algorithm designed for a large R-Mesh should be able to run on a smaller R-Mesh without significant loss of efficiency. This amounts to designing a ‘scaling simulation” that simulates an arbitrary step of an N×N R-Mesh on a smaller P×P R-Mesh in O(N 2/P 2 f(N, P)) steps; f(N,P) is a nondecreasing function representing the simulation overhead. The aim is to minimize this overhead, ideally to a constant.
In this paper, we present a scaling simulation for the general (unconstrained) R-Mesh. This simulation has an overhead of log N (smaller than the log PlogN/P overhead of the previous fastest scaling simulation), using a CREW LRN-Mesh (a weaker version of the General R-Mesh) as the simulating model; prior simulations needed concurrent write.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Ben-Asher, Y., Gordon, D., Schuster, A.: Efficient Self Simulation Algorithms for Reconfigurable Arrays. J. Parallel Distrib. Comput. 30 (1995) 1–22
Ben-Asher, Y., Lange, K.-J., Peleg, D., Schuster, A.: The Complexity of Reconfiguring Network Models. Info. and Comput. 121 (1995) 41–58
ElGindy, H., Wetherall, L.: A Simple Voronoi Diagram Algorithm for a Reconfigurable Mesh. IEEE Trans. Parallel Distrib. Systems 8 (1997) 1133–1142
Fernández-Zepeda, J.A., Trahan, J.L., Vaidyanathan, R.: Scaling the FR-Mesh under Different Concurrent Write Rules. World Multiconf. on Systemics, Cybernetics, and Informatics (1997) 437–444
Fernández-Zepeda, J.A., Vaidyanathan, R., Trahan, J.L.: Scaling Simulation of the Fusing-Restricted Reconfigurable Mesh. IEEE Trans. Parallel Distrib. Systems 9 (1998) 861–871
Jang, J.-w., Nigam, M., Prasanna, V. K., Sahni, S.: Constant Time Algorithms for Computational Geometry on the Reconfigurable Mesh. IEEE Trans. Parallel Distrib. Systems 8 (1997) 1–12
Li, H., Stout, Q. F.: Reconfigurable SIMD Massively Parallel Computers. IEEE Proceedings 79 (1991) 429–443
Maresca, M.: Polymorphic Processor Arrays. IEEE Trans. Parallel Distrib. Systems 4 (1993) 490–506
Matias, Y., Schuster, A.: Fast, Efficient Mutual and Self Simulations for Shared Memory and Reconfigurable Mesh. 7th IEEE Symp. Par. Distrib. Processing (1995) 238–246
Miller, R., Prasanna-Kumar, V. K., Reisis, D., Stout, Q.: Parallel Computations on Reconfigurable Meshes. IEEE Trans. Comput. 42 (1993) 678–692
Pavel, S., Akl, S. G.: On the Power of Arrays with Optical Pipelined Buses. Int’l. Conf. Par. Distr. Proc. Techniques and Appl. (1996) 1443–1454
Trahan, J. L., Bourgeois, A. G., Vaidyanathan, R.: Tighter and Broader Complexity Results for Reconfigurable Models. Parallel Processing Letters, special issue on Bus-based Architectures 8 (1998) 271–282
Trahan, J. L., Vaidyanathan, R.: Relative Scalability of the Reconfigurable Multiple Bus Machine. Proc. Workshop Reconfigurable Arch. and Algs. (1996)
Trahan, J. L., Vaidyanathan, R., Thiruchelvan, R. K.: On the Power of Segmenting and Fusing Buses. J. Parallel Distrib. Comput. 34 (1996) 82–94
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag
About this paper
Cite this paper
Fernández-Zepeda, J.A., Vaidyanathan, R., Trahan, J.L. (1999). Improved scaling simulation of the general reconfigurable mesh. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097946
Download citation
DOI: https://doi.org/10.1007/BFb0097946
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65831-3
Online ISBN: 978-3-540-48932-0
eBook Packages: Springer Book Archive