Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Ernst W. Mayr; Ralph Werchner 
Titel:
Optimal Tree Contraction and Term Matching on the Hypercube and Related Networks 
Abstract:
An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is based on novel routing techniques and, for certain small subtrees, simulates optimal PRAM algorithms. For trees of size $n$, stored on a $p$ processor hypercube in in-order, the running time of the algorithm is $O(\lc\frac{n}{p}\rc\log p)$. The resulting speed-up of $O(p/\log p)$ is optimal due to logari...    »
 
Stichworte:
parallel algorithms; hypercube; tree contraction; term matching; optimal speed-up 
Jahr:
1995 
Jahr / Monat:
1995-11-08 00:00:00 
Seiten/Umfang:
17