Browse Prior Art Database

Broadcasting on the Class of Extra Stage Omega-type Networks

IP.com Disclosure Number: IPCOM000122302D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 51K

Publishing Venue

IBM

Related People

Ho, CT: AUTHOR

Abstract

Presented is an efficient method for broadcasting on butterfly networks and the class of Omega-type interconnection networks with extra stage. The broadcasting algorithm is based on the maximum number of edge disjoint spanning trees on butterfly networks. Attained was a speedup of b over the previously best-known algorithms, where b is the base or fanout of the networks.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 74% of the total text.

Broadcasting on the Class of Extra Stage Omega-type Networks

      Presented is an efficient method for broadcasting on butterfly
networks and the class of Omega-type interconnection networks with
extra stage.  The broadcasting algorithm is based on the maximum
number of edge disjoint spanning trees on butterfly networks.
Attained was a speedup of b over the previously best-known
algorithms, where b is the base or fanout of the networks.

      For the base-b butterfly networks (i.e., each node has degree
2b assuming wraparound) 2b (directed) edge disjoint spanning trees
are given.  Based on these disjoint trees, the message to be
broadcast can be split into 2b equal sets and each set is broadcast
based on one spanning tree.  Since all spanning trees are disjoint,
the communication incurred by one spanning tree is conflict free from
any other spanning tree.  A previous broadcast algorithm on butterfly
networks used at most two spanning trees, i.e., one forward and one
backward.  The speedup of b holds regardless of the communication
model whether each node can communicate with one neighbor or all
neighbors at a time.

      In the case of Omega-type networks with extra stage, each node
in the butterfly-type network is replaced by a b x b switch element.
The purpose is to span all switch elements at the last stage.  It was
discovered that if the multistage interconnection network has at
least one extra stage which repeats the first stage, then all switch
el...