Parallel prefix on the star and pancake graphs. (English) Zbl 0902.68149
Summary: We use a routing algorithms we found earlier to develop a parallel algorithm that computes prefix of \(N\) elements on star and pancake interconnection networks with \(P\) processors, where \(N\geq P\). The running time of the algorithm is \(O(N/P +\log P)\), which is optimal in view of the \(\Omega (N/P+ \log P)\) lower bound. This result is interesting, considering the fact that, unlike a hypercube whose degree is logarithmic in terms of the total number of nodes, both stars and pancakes have sub-logarithmic degree.
MSC:
68R10 | Graph theory (including graph drawing) in computer science |