Your Search Results

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.

Experience the freedom of customizing your course pack with AcademicPub!
Not an educator but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

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).