How does data travel in a butterfly network? I'm trying to learn how communication works in a butterfly network.



The following is a butterfly network of order 3. I'm given the following description:


  Each processor is connected to an output switch in rank 0 and to an input switch in rank k (in this case 3). In other words the switch in column j and rank 0 gets its input message from processor j and the switch in column j and rank k delivers its message to processor j. Messages only travel in one direction - towards switches of increasing rank. 


I'm having trouble interpreting what it means by the input and output switches. At first I thought the messages were traveling from bottom to top, but the last statement makes it sound like it's traveling from top to bottom. Is the processor j mentioned found on top in rank 0? I'm trying to grasp how messages travel from one processor to another.
The description you were given is indeed phrased in a confusing way.  I suspect they're talking about messages travelling from top to bottom.

I suspect by "output switch" they might mean "output from the processor" (input to the butterfly network), which is pretty confusing.  That explanation could have been phrased better.

Butterfly networks are described in many places.  You might want to find another description of butterfly networks and read that.