Multidimensional binary partitions: distributed data structures for spatial partitioning
- 1 December 1991
- journal article
- research article
- Published by Taylor & Francis in International Journal of Control
- Vol. 54 (6) , 1335-1352
- https://doi.org/10.1080/00207179108934215
Abstract
A multidimensional binary partition (MBP) is a data structure determined by a set of points in n -dimensional space. On certain parallel architectures, this data structure can be easily distributed across the processing nodes of the machine and can provide a natural technique for load balancing and partitioning of application problems that depend on a distribution of dynamically changing points in multidimensional space. This paper describes parallel algorithms for generating and using MBPs on a hypercube parallel machine. It is also shown how these distributed data structures allow efficient parallel searches of the data set. The performance of an implementation of these algorithms on an NCUBE hypercube is presented.Keywords
This publication has 11 references indexed in Scilit:
- Assigning modules to processors in linear arrays and ringsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Dynamic load balancing for distributed memory multiprocessorsJournal of Parallel and Distributed Computing, 1989
- A Partitioning Strategy for Nonuniform Problems on MultiprocessorsIEEE Transactions on Computers, 1987
- Fixed hypercube embeddingInformation Processing Letters, 1987
- A Comparison of Domain Decomposition Techniques for Elliptic Partial Differential Equations and their Parallel ImplementationSIAM Journal on Scientific and Statistical Computing, 1987
- A vectorized “near neighbors” algorithm of order N using a monotonic logical gridJournal of Computational Physics, 1986
- Computational GeometryPublished by Springer Nature ,1985
- Load Balancing in Distributed SystemsIEEE Transactions on Software Engineering, 1982
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973