Presents parallel algorithms for computation of time-slot assignments in time-division multiplex (TDM) switching systems. The algorithms apply to a general class of TDM switching systems called hierarchical switching systems (HSS), which have a three-stage switching structure. The algorithms are based on modeling the time-slot assignment problem as a network-flow problem. Previous algorithms for finding an optimal time-slot assignment in these switching systems are inherently sequential and no parallel algorithms are known for this problem. If M is the number of users of the switching system, N is the switch-size, and L is the length of an optimal time-slot assignment, the best-known sequential TSA algorithm runs in O(M/sup 2/.min(N, square root M).min(L, M/sup 2/)) time. The authors first describe an algorithm using L/2 processors with running time O(M/sup 3/ log L) on a PRAM model of computation. They then generalize it to P>or=L/2 processors, with running time O(M/sup 3/ log P+M/sup 2/.min(N, square root M).min(L/P, M/sup 2/)). An efficient implementation of the algorithm on a hypercube multiprocessor with P processors has the same time-complexity. A massively parallel version of the algorithm runs in O(M/sup 2/ log M log L) time on ML/2 processors. Finally, the authors discuss how the above algorithms can be applied to the class of SS/TDMA switching systems.
展开▼
