TY - JOUR
T1 - A parallel algorithm for traffic control problems in three-stage connecting networks
AU - Funabiki, Nobuo
AU - Takefuji, Yoshiyasu
PY - 1994/2
Y1 - 1994/2
N2 - A parallel heuristic algorithm for traffic control problems in three-stage connecting networks is presented in this paper. A three-stage connecting network consists of an input crossbar switching stage, an intermediate crossbar switching stage, and an output crossbar switching stage. The goal of our algorithm is to quickly and efficiently find a conflict-free switching assignment for communication demands through the network. The algorithm requires n2 × m processing elements for the network composed of n input/output switches and m intermediate switches, where it runs not only on a sequential machine, but also on a parallel machine with maximally n2 × m processors. The algorithm was verified by 1100 simulation runs with the network size from 102 × 7 to 502 × 27. The simulation results show that the algorithm can find a solution in nearly constant time with n2 × m processors.
AB - A parallel heuristic algorithm for traffic control problems in three-stage connecting networks is presented in this paper. A three-stage connecting network consists of an input crossbar switching stage, an intermediate crossbar switching stage, and an output crossbar switching stage. The goal of our algorithm is to quickly and efficiently find a conflict-free switching assignment for communication demands through the network. The algorithm requires n2 × m processing elements for the network composed of n input/output switches and m intermediate switches, where it runs not only on a sequential machine, but also on a parallel machine with maximally n2 × m processors. The algorithm was verified by 1100 simulation runs with the network size from 102 × 7 to 502 × 27. The simulation results show that the algorithm can find a solution in nearly constant time with n2 × m processors.
UR - http://www.scopus.com/inward/record.url?scp=33747683570&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33747683570&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1994.1022
DO - 10.1006/jpdc.1994.1022
M3 - Article
AN - SCOPUS:33747683570
SN - 0743-7315
VL - 20
SP - 236
EP - 240
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 2
ER -