@mangocourage: Here's the reason: in multi-stage logarithmic topology, there are log(2,N) columns(stages) in total. And in each of the column, there are N/2 switch. So this sum up to O(NlogN) switches.
Also, as is mentioned in the course:
Even though the above graph is still a blocking network(if 1 sending to 6, 2 sending to 7), but logarithmic topology is considered one of the cheapest ways to build a non-blocking network.
Compare with the brute-force method: using crossbar, which takes up to O(N^2) cost, this is much better.
top
Interestingly enough this type of network is used in computation of FFT's(Fast Fourier Transforms). A diagram is linked below but the basic idea is to continuously divide the input by 2 and computer N/2 size FFT's until you are reduced down to a butterfly(also linked below). This gave an intuitive sense as to why the cost is nlogn for me.
FFTButterfly
ESINNG
Is there any explanation about how the interconnection between each column of the routers is designed?
zhiyuany
@ESINNG, for the column 0, switch i connects processor i and i+n/2; for the column 1 and 2, switch i connects switch i/2 and i/2+n/2/2. The formula of index may be confusing, but it's easy to find the pattern by looking carefully at the graph. But one thing I'm not sure is, whether there is only one design given the number of processors in multi-stage logarithmic network.
Could someone explain why the cost is nlogn?
Hint: N/2 boxes per column. And how many columns?
@mangocourage: Here's the reason: in multi-stage logarithmic topology, there are log(2,N) columns(stages) in total. And in each of the column, there are N/2 switch. So this sum up to O(NlogN) switches.
Also, as is mentioned in the course: Even though the above graph is still a blocking network(if 1 sending to 6, 2 sending to 7), but logarithmic topology is considered one of the cheapest ways to build a non-blocking network. Compare with the brute-force method: using crossbar, which takes up to O(N^2) cost, this is much better.
Interestingly enough this type of network is used in computation of FFT's(Fast Fourier Transforms). A diagram is linked below but the basic idea is to continuously divide the input by 2 and computer N/2 size FFT's until you are reduced down to a butterfly(also linked below). This gave an intuitive sense as to why the cost is nlogn for me. FFT Butterfly
Is there any explanation about how the interconnection between each column of the routers is designed?
@ESINNG, for the column 0, switch i connects processor i and i+n/2; for the column 1 and 2, switch i connects switch i/2 and i/2+n/2/2. The formula of index may be confusing, but it's easy to find the pattern by looking carefully at the graph. But one thing I'm not sure is, whether there is only one design given the number of processors in multi-stage logarithmic network.