Previous | Next --- Slide 18 of 34
Back to Lecture Thumbnails

Question: Why is the cost O(N lg N) here?


There are log(N) rows (stages according to wikipedia) and each row has N/2 nodes. So total cost is O(N lg N). In the picture, N=8, there are 3 rows and 4 nodes per row.


Bisection bandwidth is O(N) as can be noted due to (in this case) n wires between switches.


Many variations of multi-stage logarithmic networks, such as the Omega and butterfly networks, are isomorphic (topologically equivalent). These networks (delta networks), are "digit controlled" networks. In other words, the reason why there are $\log_2(n)$ rows (columns, in this picture) is because, starting from the left, each node is connected to exactly one 2x2 switch. Routing is entirely determined by the packet ("digit controlled"), which has $\log_2(n)$ bits. Each bit determines whether the packet is routed to the high connection or the low connection. Because each origin must be capable of reaching $n$ destinations, there must be exactly $\log_2(n)$ bits to account for the full $n$ outcomes.