The routing rule is based on the bit representation of destination. For example, if destination is 3, whose bit representation is (011)_2, then the routing rule is up, down, down.
418_touhenying
Why in this case the cost O(N lgN), and what is the most general way to consider the cost, for all models discussed in this lecture?
zvonryan
@418_touhenying about the cost of omega network, you can check out the definition of Omega Network. An Omega network contains N/2 switches at each stage, and log2N stages, which is determined by its nature, a shuffling connection system.
rmanne
@418_touhenying Just count the number of connections (links), that is the 'cost' that we are concerned about in this lecture.
As we see in this diagram, every intermediary node has two outgoing connections, there are $log(n) * n / 2$ nodes, so there are $log(n) * n / 2 * 2$ connections not including the ones from the left most to the left most intermediary nodes, of which there are $n$. So in total, $n * log(n) + n \in O(n log(n))$.
ArbitorOfTheFountain
Perhaps another way to think of this network would be to consider each "source" node as the root of a binary tree. In order to maintain paths from this root to all possible destinations there need to be O(log(n)) levels. Each connecting "tree" can share with other "trees" since each intermediate node allows 2 input links and 2 output links.
xingdaz
You can think of each layer of switches as routing on the bit position of the destination node; switches in the leftmost layer route on the MSB of the dst node binary encoding and the ones in the last layer routes in the LSB of the encoding.
huehue
Where would you bisect the network to find the bisection bandwidth here?
eknight7
@huehue I think the bisection bandwidth in this network is 4, since at each switch, we can only send one packet at a time and 4 packets can go across simultaneously in parallel.
nmrrs
@eknight7 I believe the bisection bandwidth is actually 8 here. It's the number of edges across a cut in the network, not just the number of packets that can move simultaneously across the network.
The routing rule is based on the bit representation of destination. For example, if destination is 3, whose bit representation is (011)_2, then the routing rule is up, down, down.
Why in this case the cost O(N lgN), and what is the most general way to consider the cost, for all models discussed in this lecture?
@418_touhenying about the cost of omega network, you can check out the definition of Omega Network. An Omega network contains N/2 switches at each stage, and log2N stages, which is determined by its nature, a shuffling connection system.
@418_touhenying Just count the number of connections (
links), that is the 'cost' that we are concerned about in this lecture.As we see in this diagram, every intermediary node has two outgoing connections, there are $log(n) * n / 2$ nodes, so there are $log(n) * n / 2 * 2$ connections not including the ones from the left most to the left most intermediary nodes, of which there are $n$. So in total, $n * log(n) + n \in O(n log(n))$.
Perhaps another way to think of this network would be to consider each "source" node as the root of a binary tree. In order to maintain paths from this root to all possible destinations there need to be O(log(n)) levels. Each connecting "tree" can share with other "trees" since each intermediate node allows 2 input links and 2 output links.
You can think of each layer of switches as routing on the bit position of the destination node; switches in the leftmost layer route on the MSB of the dst node binary encoding and the ones in the last layer routes in the LSB of the encoding.
Where would you bisect the network to find the bisection bandwidth here?
@huehue I think the bisection bandwidth in this network is 4, since at each switch, we can only send one packet at a time and 4 packets can go across simultaneously in parallel.
@eknight7 I believe the bisection bandwidth is actually 8 here. It's the number of edges across a cut in the network, not just the number of packets that can move simultaneously across the network.