An assumed partition algorithm for determining processor inter-communication

The recent advent of parallel machines with tens of thousands of processors is pre-senting new challenges for obtaining scalability. A particular challenge for large-scale scientific software is determining the inter-processor communications required by the computation when a global description of the data is unavailable or too costly to store. We present a type of rendezvous algorithm that determines communication partners in a scalable manner by assuming the global distribution of the data. We demonstrate the scaling properties of the algorithm on up to 32,000 processors in the context of determining communication patterns for a matrix-vector multiply in the hypre software library. Our algorithm is very general and is applicable to a variety of situations in parallel computing. Key words: global partition, processor inter-communication, rendezvous algorithm, scalability, distributed directory