Hypercube Computations on Partitioned Optical Passive Stars Networks
|
Abstract—This paper shows that an n=2^k processor Partitioned Optical Passive Stars (POPS) network with g groups and d processors per group can simulate every bidirectional move of an n processor hypercube using one slot when d, two slots when d=g, and \lceil d/g\rceil slots when d>g. Moreover, the same POPS network can simulate every monodirectional move of an n processor hypercube using one slot when d=g. All these results are shown to be optimal. Our simulations improve on the literature whenever d\neq g and directly yield several important consequences. For example, as a direct consequence of our simulations, a {\rm{POPS}} network, n=dg and d, can compute the prefix sums of n data values in \log_2 n slots. This is faster than the best previously known ad hoc algorithm and is actually optimal. Similarly, we improve on the best POPS network algorithms for both the prefix sums problem on general POPS networks and the fundamental online permutation routing problem, among others.
[1] 497 D. Chiarulli, S. Levitan, R.G. Melhem, J. Teza, and G. Gravenstreter, “Multiprocessor Interconnection Networks Using Partitioned Optical Passive Star (Pops) Topologies and Distributed Control,” Proc. First Int'l Workshop Massively Parallel Processing Using Optical Interconnections, 1994.
[2] G. Gravenstreter, R.G. Melhem, D. Chiarulli, S. Levitan, and J. Teza, “The Partitioned Optical Passive Star (Pops) Topology,” Proc. Ninth Int'l Parallel Processing Symp., 1995.
[3] G. Gravenstreter and R.G. Melhem, “Realizing Common Communication Patterns in Partitioned Optical Passive Stars Networks,” IEEE Trans. Computers, vol. 47, no. 9, Sept. 1998.
[4] R.G. Melhem, G. Gravenstreter, D. Chiarulli, and S. Levitan, The Comm. Capabilities of Partitioned Optical Passive Star Networks, pp. 77-98, Kluwer Academics Publishers, 1998.
[5] S. Sahni, “The Partitioned Optical Passive Stars Network: Simulations and Fundamental Operations,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 7, July 2000.
[6] A. Datta and S. Soundaralakshmi, “Summation and Routing on a Partitioned Optical Passive Stars Network with Large Group Size,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 12, Dec. 2003.
[7] S. Sahni, “Matrix Multiplication and Data Routing Using a Partitioned Optical Passive Stars Network,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 7, July 2000.
[8] A. Mei and R. Rizzi, “Routing Permutations in Partitioned Optical Passive Stars Networks,” J. Parallel and Distributed Computing, vol. 63, no. 9, pp. 847-852, Sept. 2003.
[9] P. Berthomé and A. Ferreira, “Improved Embeddings in POPS Networks through Stack-Graph Models,” Proc. Third Int'l Workshop Massively Parallel Processing Using Optical Interconnections, 1996.
[10] T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo, Calif.: Morgan Kaufmann, 1992.
[11] S. Ranka and S. Sahni, Hypercube Algorithms with Applications to Image Processing and Pattern Recognition. New York: Springer Verlag, 1990.
Index Terms:
Parallel architectures, partitioned optical passive stars network, hypercube simulation, prefix sums, permutation routing.
Citation:
Alessandro Mei, Romeo Rizzi, "Hypercube Computations on Partitioned Optical Passive Stars Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 6, pp. 497-507, June 2006, doi:10.1109/TPDS.2006.72
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb