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 < g, two slots when d = g, and d/g 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 POPS network, n = dg and d < g, 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.

Hypercube Computations on Partitioned Optical Passive Stars Networks

RIZZI, ROMEO
2006

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 < g, two slots when d = g, and d/g 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 POPS network, n = dg and d < g, 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.
Parallel architectures; partitioned optical passive stars network; hypercube simulation; prefix sums; permutation routing.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/409574
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact