TOPOLOGICAL PROPERTIES, COMMUNICATION, AND COMPUTATION ON WK-RECURSIVE NETWORKS

Recently, with the support of the CAPRI (Concurrent Architecture and PRogramming environment for highly Integrated system) project, Vecchia and Sanges proposed a new general class of recursively scalable networks, termed WK-recursive networks, and developed routing and broadcasting algorithms on them. They have also implemented the WK-recursive networks using VLSI technology. This paper studies WK-recursive networks by first investigating their topological properties such as diameter, connectivity, and Hamiltonicity. We then develop new and more efficient routing and broadcasting algorithms. Our routing algorithm can guarantee the shortest paths. Our broadcasting algorithm is much simpler and requires fewer extra bits to be transmitted. The broadcasting tree of our broadcasting algorithm is of minimal height (equal to the diameter), and each node receives the message exactly once. Moreover, we show the execution of descend/ascend algorithms on the WK-recursive networks using the bitonic sort as an illustrative example. (C) 1994 John Wiley & Sons, Inc.