Use this resource - and many more! - in your textbook!
AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.
Multiphase complete exchange: a theoretical analysis
By: Bokhari, S.H.;
1996 / IEEE
This item was taken from the IEEE Periodical ' Multiphase complete exchange: a theoretical analysis ' Complete exchange requires each of N processors to send a unique message to each of the remaining N-1 processors. For a circuit switched hypercube with N=2/sup d/ processors, the direct and standard algorithms for complete exchange are time optimal for very large and very small message sizes, respectively. For intermediate sizes, a hybrid multiphase algorithm is better. This carries out direct exchanges on a set of subcubes whose dimensions are a partition of the integer d. The best such algorithm for a given message size m could hitherto only be found by enumerating all partitions of d. The multiphase algorithm is analyzed assuming a high performance communication network. It is proved that only algorithms corresponding to equipartitions of d (partitions in which the maximum and minimum elements differ by at most one) can possibly be optimal. The runtimes of these algorithms plotted against m form a hull of optimality. It is proved that, although there is an exponential number of partitions: (1) the number of faces on this hull is /spl Theta/(/spl radic/(d)); (2) the hull can be found in /spl Theta/(/spl radic/(d)) time; and (3) once it has been found, the optimal algorithm for any given m can be found in /spl Theta/(log d) time. These results provide a very fast technique for minimizing communication overhead in many important applications, such as matrix transpose, fast Fourier transform, and alternating directions implicit (ADI).
Alternating Directions Implicit
Multiphase Complete Exchange
Circuit Switched Hypercube
Very Small Message Sizes
Hybrid Multiphase Algorithm
High Performance Communication Network
Hull Of Optimality
Communication Overhead Minimisation
Fast Fourier Transform
Algorithm Design And Analysis
Partial Differential Equations
Multiprocessor Interconnection Networks
Computing And Processing