ALL PAIRS SHORTEST PATHS ON A HYPERCUBE MULTIPROCESSOR.

Abstract

this paper, we consider parallel solutions to the all pairs problem only. As with other studies, our development considers finding only the length of the shortest paths. We are interested in solving the all pairs problems on an MIMD hypercube in which each processor has local memory. Specifically, our experimentation is done on an NCUBE/7 hypercube. A block diagram of this computer is shown in Fig 1.1 External Memory Host Processor Hypercube Processor Memory Host Memory Figure 1.1 Block diagram of the NCUBE hypercube A detailed description of the architecture of the NCUBE hypercube appears in [6]. This is an MIMD computer. Each hypercube processor is a custom 32 bit, 2 MIPS, 500,000 FLOPS processor. The local memory for each hypercube processor is either 128 K or 512 K bytes. In the configuration avaliable to us, each processor has 128 K bytes of local memory. The high level language support currently includes FORTRAN and C. Both have been extended to allow for communication between the host and the hypercube and among the hypercube processors. When designing a parallel algorithm for a shared memory machine such as the HEP, one focus on the creation of multiple processes that avoid memory access coflicts. In the case of a computer such as the hypercube the focus is on partitioning the data so as to reduce the time spent in inter processor communication. We consider two methods of partitioning the data for the all pairs problem. These are called: by stripes and by rectangles. These two methods are evaluated experimentally and are also compared with the alternative of running a single source sequential algorithm on each of the hypercube processors. 4 2 Floyd's All Pairs Algorithm Floyd's all pairs algorithm (see[3] for e.g.) is given in Fig 2.1. Here L [i, j ] is initial...