Previous | Next --- Slide 13 of 49
Back to Lecture Thumbnails

Bisection b/w in direct n/w in the previous slide is O(n) and also for indirect n/w its O(n). How is it O(n) in the indirect case ? Shouldn't there be any fixed definition of how to cut it ? For e.g. in the n/w where half nodes are connected with a single link to other half nodes, wont it depend on if you cut it horizontally or vertically, because I think answers will be different in both cases.


I'm sorry if I missed this during lecture. Could someone explain when one would pick a direct network vs when someone would pick an indirect network?


In my idea, the direct network topology is somewhat analogous to a Onion Network, where each node serves as the role of a router.


I have the same question as @bamboo, can someone help clarify?


The Diameters of the above networks should be :
Direct Network: 14
Indirect Network: 2
This is assuming we count only the links between 2 routers and not between node and switch as in previous slide.


@rsvaidya I believe for indirect it may be 3. While in the previous slide we didn't count the distance between the node and switch, this seems to only be the case if each node has its own switch(direct network). In the indirect network the right switches can go to one of two interfaces which i believe counts as a "hop"


I agree with @sadkins. In indirect network, endpoints and switches are different nodes. Thus, we should count link between any node and switch as a hop.


@bamboo: Bisection should be done in such a way that the bandwidth between two partitions is minimum. Bisection bandwidth gives the true bandwidth available in the entire system and accounts for the bottleneck bandwidth of entire network.

Wikipedia has some useful examples as well as the text above.

The bisection bandwidth is not a function of direct/indirect, but rather the topology. I thought the mesh would be O(sqrt(N)) instead of O(N). And the multi-stage log would have a bisection bandwidth that depended on the stage with the smallest number of outgoing links (in this configuration it doesn't matter, each stage has 8 outgoing links).