Research Article
NMR: A New Approach for Optimal Design of Strictly Non-Blocking Multistage Interconnection Networks
Islamic Azad University, Science and Research, Tehran, Iran
Mehdi N. Fesharaki
Islamic Azad University, Qazvin, QIAU, Iran
Optimizing the strictly non-blocking multistage interconnection networks has served as one of the extensive research areas after the introduction and publication paper of clos (Hwang et al., 2003; Clos, 1953). These networks have been selected because of their economical, regularity, cost effectiveness and technicality characteristics (Liotopoulos and Logothetis, 2000), as well as, modularity, scalability, measurability, fault tolerant, high efficiency, having multi-passage tracking and routing (Liotopoulos, 2001). In Vaez and Lea (2000), a multistage Banyan architecture was proposed that has much maximum number of crosspoints on signal transfer path and number of crosspoints. Tree-Hypercube (Almobaideen et al., 2007) and Mesh-Hypercube (Al-Mahadeen and Omari, 2004), are two types of this networks used extensively in telephone switching and optical fiber networks. They are also used for data communication between memory components with the least propagation delay in parallel processing systems and multiprocessors (Ngo, 2003).
A multistage interconnection network can appear in various forms such as a strictly non-blocking, wide-sense non-blocking, rearrangeable non-blocking and blocking network (Hwang and Liaw, 2000). If a pair of inputs and outputs can always be connected without any considerations, the network is called strictly non-blocking. If a routing mechanism and modification is required to connect each pair of input and output, the network is called wide-sense non-blocking. A rearrangeable non-blocking network refers to the one in which to connect each input and output pair, a modification in the arrangement and rerouting of other input and output pairs must be applied. If a pair of inputs and outputs cannot be connected under any conditions, the network is called a blocking network (Yang and Wang, 2005). The dominating conditions in different types of interconnection networks are discussed in form of theories in (Chang et al., 2004). The complexity criteria of multistage interconnection networks (Coppo et al., 1993; Gragopoulos and Pavlidou, 1997) are determined and evaluated according to three factors of CN, PN and SN.
Definition 1: CN refers to the number of crosspoints or Switching Elements (SEs) in multistage interconnection networks which is equal to the hardware cost of network.
Definition 2: PN refers the maximum number of crosspoints or SEs on signal transfer path multistage interconnection networks which indicate the delay propagation in multistage interconnection networks.
Definition 3: SN is the maximum number of connections that may tolerance while passing from input to output multistage interconnection networks.
The CN, PN and SN are equal in Crossbar and Benes networks and are computed according to O(N2), O(N) and O (N), respectively (Salehnamadi and Fesharaki, 2002). These factors in clos network are calculated and set as O (NN), O (N) and O (N), respectively. However, it will be shown that these factors enjoy an optimal conditions in NMR and eventually, in CNMR are equal to O (NN) and O (log2N) and a constant value, respectively. The rest of the study is organized as follows:
First, the abovementioned factors are studied and computed in crossbar, benes and clos multistage interconnection networks. Afterwards, the design of proposed NMR and CNMR interconnection networks is discussed and the mentioned factors are analyzed. Then the evaluation and comparison of the results are described. Finally, the findings are discussed.
CROSSBAR, BENES AND CLOS MULTISTAGE INTERCONNECTION NETWORKS
Here, the three factors CN, PN and SN are studied and computed in crossbar, benes and clos multistage interconnection networks.
Crossbar non-blocking multistage interconnection network: Crossbar strictly non-blocking multistage interconnection network with N number of input and M number of output is shown in Fig. 1.
Considering M = N, the three factors of CN, PN and SN are computed as follows:
CN | = | N*N = N2 |
PN | = | N+N-1 = 2N-1 |
SN | = | Min (N, N)-1 = N-1 |
Benes non-blocking multistage interconnection network: Figure 2 shows a Benes non-blocking multistage interconnection network with N number of input and M number of output. This network is called Benes N.
The three factors of CN, PN and SN are computed as follows:
CN | = | N/2*2*2+2*N/2*N/2+N/2*2*2 = N2/2+4N |
PN | = | (2+2-1)+(N/2+N/2-1)+(2+2-1) = N+5 |
SN | = | Min (2.2)-1+Min(N/2,N/2)-1+Min(2.2)-1 = N/2+1 |
Fig. 1: | Structure of a crossbar network with N input and M output |
Fig. 2: | Structure of a Benes non-blocking multistage interconnection network with N input and output |
Fig. 3: | Structure of a Clos three-stage interconnection network C (n1, r1, m, r2, n2) |
Clos non-blocking three-stage interconnection network: This type of network is shown in Fig. 3 as C (n1, r1, m, r2, n2).
This network consists of N number of input and M number of output while it has r1 number of n1*m switches in the first stage, m number of r1*r2 switches in the middle stage and r2 number of m*n2 switches in the third stage. If N equals M, then n1 = n2 and r1 = r2. Therefore, we will have in the first stage r number of m*n switches, in the middle stage m number of r*r switches and in the third stage r number of m*n switches. In the optimal case, N = n2, n = r and m = 2n-1 will assure the strictly non-blocking character of the network (Holmberg, 2008). Therefore, the three factors of CN, PN and SN are computed in this type of network as follows:
CN | = | r*Cn*m +m*Cr*r+r*Cm*n = r*n*m+m*r*r+r*m*n = r*m*(2n+r) |
CN | = | n*(2n-1)*(2n+n) = 3n2*(2n-1) = 3N*(2N-1) |
PN | = | Pn*m+Pr*r+Pm*n = (n+m-1)+(r+r-1)+(m+n-1) = 2n+2r + 2m-3 |
PN | = | 4n+2(2n-1)-3 = 8n-5 = 8N-5 |
SN | = | Sn*m+Sr*r+Sm*n = Min(n,m)-1+Min(r,r)-1+Min(m,n)-1 = n-1+r-1+n-1 |
SN | = | 3n-3 = 3(N-1) |
NMRN*M NON-BLOCKING MULTISTAGE RECURSIVE INTERCONNECTION NETWORK
Having a recursive structure and breaking down a problem into a group of smaller problems are of great importance in extensive and complex network designs. Therefore, a strictly non-blocking multistage interconnection network N*M can be designed in a recursive way through strictly non-blocking multistage interconnection networks of N*M/2 or N/2*M or N/2*M/2 and by using 1*2 and 2*1 switches. This strictly non-blocking multistage recursive interconnection network N*M is named as NMRN*M. In special cases, if the number of inputs equals the number of output (N = M), the network is called a non-blocking multistage recursive interconnection network of N or a NMRN. To prove that the interconnection multistage network is strictly non-blocking, the following theorems are discussed.
Theorem 1: A strictly non-blocking multistage interconnection network N*M can be constructed by shuffling and exchanging the inputs of two strictly non-blocking multistage interconnection network N*M/2 with the outputs of N number of 1*2 switches (Fig. 4).
Proof: Let`s assume that I(N) = {1, 2,..., N} and O(M) = {1, 2,..., M} are, respectively, the inputs and outputs set of a strictly non-blocking multistage interconnection network N*M. Also, let`s assume that I1(N) = I2(N) = {1,2,...,N}, O1(M/2) = {1, 2,..., M/2} and O2(M/2) = {M/2+1,M/2+2,...,M} are, respectively, the inputs and outputs set of two strictly non-blocking multistage interconnection networks of N*M/2. As the outputs of N number of 1*2 switches connect to the inputs of two strictly non-blocking multistage interconnection networks N*M/2 according to a shuffle-exchange pattern, each input i ε I(N) can connect through one of the N switch 1*2 to one of sets I1(N) or I2(N) and through one of the two strictly non-blocking multistage interconnection networks N*M/2 to any output j ε O(M) non-blocking in any given time.
Fig. 4: | Strictly non-blocking multistage recursive interconnection network N*M constructed from 1*2 switches and N*M/2 networks |
Fig. 5: | Strictly non-blocking multistage recursive interconnection network N*M constructed from N/2*M networks and 2*1 switches |
As a result, any i ε I(N) input can connect to each j ε O(M) output without any blocking.
Theorem 2: A strictly non-blocking multistage interconnection network N*M can be constructed by shuffling and exchanging the outputs of two strictly non-blocking multistage interconnection network N/2*M with the inputs of M number of 2*1 switches (Fig. 5).
Proof: Let`s assume that I(N) = {1, 2,..., N} and O(M) = {1, 2,...,M} are, respectively, the inputs and outputs set of a strictly non-blocking multistage interconnection network N*M.
Fig. 6: | Strictly non-blocking multistage recursive interconnection network N*M constructed from 1*2 switches, N/2*M/2 networks and 2*1 switches |
Also, let`s assume that I1(N/2) = {1,2,...,N/2}, I2(N/2) = {N/2+1, N/2+2,..., N} and O1(M) = O2(M) = {1, 2,...,M} are, respectively, the inputs and outputs set of two strictly non-blocking multistage interconnection networks of N/2*M. Each input i ε I(N) can connect through one of the strictly non-blocking multistage interconnection networks N/2*M to one of the two O1(M) or O2(M) in any given time. On the other hand, as the outputs of the two strictly non-blocking multistage interconnection networks N/2*M are connected to M inputs switches 2*1 in a shuffle-exchange pattern, any element of O1(M) or O2(M) can connect to any output j ε O(M) through a 2*1 switch without any blocking. Therefore, any i ε I(N) input can connect to any j ε O(M) output with no blocking.
Theorem 3: A strictly non-blocking multistage interconnection network N*M can be constructed by shuffling and exchanging the inputs of four strictly non-blocking multistage interconnection network N/2*M/2 with the outputs of N number of 1*2 switches and its outputs with M switches 2*1 (Fig. 6).
Proof: Considering Theorem 3, in a number of stages and in a recursive mode this network can be converted into a strictly non-blocking multistage recursive interconnection network k*p and simple switches 1*2 and 2*1, assuming that the values of N/k and M/p are exponents of number two. In other words, the network NMRN*M is converted into a number of switching elements 1*2 and 2*1 and number of k*p networks after some stages.
Definition 4: An NMRN*M network, which is converted to a strictly non-blocking multistage recursive interconnection network k*p and simple switching elements 1*2 and 2*1 after multiple of stages is called NMRN*M(k*p).
Here, the three criteria CN, PN and SN in NMRN*M(k*p) networks are studied and calculated, using the following theorems.These factors (CN, PN and SN) are assumed as Ck*p, Pk*p and Sk*p in strictly non-blocking multistage interconnection network of k*p.
Theorem 4: In NMRk*M strictly non-blocking multistage recursive interconnection network the value of Ck*M is equal to:
Ck*M | = | k*(M/p-1)+(M/p)*Ck*p |
Proof: According to Theorem 1, this network is constructed by shuffling and exchanging the inputs of two strictly non-blocking multistage interconnection network k*M/2 with the k outputs of 1*2 switches. Therefore, Ck*M is equal.
Ck*M | = | k+2Ck*M/2 = k+2(k+2Ck*M/4) = k+2k+4Ck*M/4 |
Ck*M | = | k+2k+4(k+2Ck*M/8) = k+2k+4k+8Ck*M/8 |
Ck*M | = | k+2k+4k+...+(2i-1)*k+(2i)*Ck*p = k*(2i-1)+(2i)*Ck*p |
Assuming that M/p = 2i or p = M/2i:
Ck*M | = | k*(M/p-1)+(M/p)*Ck*p |
Theorem 5: In NMRN*p strictly non-blocking multistage recursive interconnection network the value of CN*p is equal to:
CN*p | = | p*(N/k-1)+(N/k)*CK*p |
Proof: According to Theorem 2, this network is constructed by shuffling and exchanging the outputs of two strictly non-blocking multistage interconnection network N/2*p with the p inputs of 2*1 switches. Therefore, CN*p is equal.
CN*p = p+2CN/2*p = p+2(p+2CN/4*p) = p+2p+4CN/4*p |
Assuming that N/k = 2j or k = N/2j:
CN*p | = | p*(N/k-1)+(N/k)*Ck*p |
Theorem 6: In NMRN*M strictly non-blocking multistage recursive interconnection network which is constructed by k*p strictly non-blocking multistage interconnection network and 1*2 and 2*1 simple switching elements, the value of CN*M(k*p) is equal to:
CN*M(k*p) | = | (Ck*p+k+p)*(N*M)/(k*p)-(N+M) |
Proof: According to Theorem 4 and Theorem 5:
CN*M(k*p) | = | N*(M/p-1)+(M/p)*CN*p |
CN*M(k*p) | = | N*M/p-N+(M/p)*(P*(N/k-1)+(N/k)*Ck*p) |
CN*M(k*p) | = | N*M/p-N+N*M/k-M+(N*M/k*p)*Ck*p |
CN*M(k*p) | = | (Ck*p+k+p)*(N*M)/(k*p)-(N+M) |
If in a strictly non-blocking multistage recursive interconnection network the number of inputs equals the number of outputs, N= M, called NMRN(k*p), then:
CN(k*p) | = | (Ck*p+k+p)*(N2/(k*p))-2N |
And also if in an NMRN network, strictly non-blocking multistage interconnection networks with the equal number of inputs and outputs are used (k = p), then:
CN(k) | = | (Ck+2k)*(N2/k2)-2N |
Theorem 7: In the network discussed in Theorem 6, the value of PN*M(k*p) is equal to:
PN*M(k*p) | = | Pk*p+log2((N*M)/(k*p)) |
Proof: It is proved in a similar way. However, in a specific condition if N = M, then:
PN (k*p) | = | Pk*p+log2(N2/(k*p)) |
And if k = p, then:
PN(k) | = | Pk+2log2(N/k) |
Theorem 8: In the network discussed in Theorem 6, the value of SN*M(k*p) is equal to:
SN*M(k*p) | = | Sk*p |
Proof: To determine the factor SN*M(k*p) in NMRN*M network, it should be noted that switches 1*2 and 2*1 have no effect on SN*M(k*p), since Min (2, 1)-1 = Min (1, 2)-1 = 0 and therefore, SN*M(k*p) is dependent only on the value of this parameter in k*p strictly non-blocking multistage interconnection network, then:
SN*M(k*p) | = | Sk*p. |
CNMRN*M STRICTLY NON-BLOCKING MULTISTAGE RECURSIVE INTERCONNECTION NETWORK
Since in clos three-stage interconnection network CN has an optimal value and NMRN(k) network optimizes the values of PN and SN, we can use an NMRN(k) network in designing a clos strictly non-blocking three-stage interconnection network.
Fig. 7: | Clos strictly Non-blocking Multistage Recursive interconnection network in CNMRN*M |
This type of network is called Clos strictly Non-blocking Multistage Recursive interconnection network or CNMRN(k), which is shown in Fig. 7.
Considering the following lemmas, we analyze and compute the three factor CN, PN and SN in CNMRN(k) network.
Lemma 1: In CNMRN(k) network, the value of CN is equal to:
CN | = | [6(Ck+2k)/k2]*NN-10N |
Proof: In order to calculate the value of CN in CNMRN(k) network, first it must be calculated in Clos strictly non-blocking three-stage interconnection network. It will be as follows:
CN | = | r*Cn*m+m*Cr*r+r*Cm*n = 2r*Cn*m+m*Cr*r |
In an optimum case of Clos strictly non-blocking three-stage interconnection network, r = n = N and m≥2n-1. Furthermore, as the number of inputs and outputs in any NMRN(k) network must be an exponentiation of two, then m = 2n.
As a result, in a Clos strictly non-blocking three-stage interconnection network we will have:
CN | = | 2n*Cn*2n+2n*Cn*n=2n*(Cn*2n+Cn*n) |
On the other hand, in CNMRN(k) network, an NMRN*M(k) network is used to calculate the values of Cn*2n and Cn*n. According to Theorem 6:
Cn*n(k) | = | Cn(k) = (Ck+2k)*(n2/k2)-2n |
Cn*2n(k) | = | (Ck+2k)*(2n2/k2)-3n |
According to the above equation:
CN | = | 2n*[(Ck+2k)*(2n2/k2)-3n+(Ck+2k)*(n2/k2)-2n] |
CN | = | [6(Ck+2k)/k2]*n3-10n2 |
And considering n = N, then:
CN | = | [6(Ck+2k)/k2]*NN-10N |
Lemma 2: Value of PN in CNMRN(k) network equals to:
PN | = | 6log2N-6log2k+3Pk+2 |
Proof: As in Lemma 1, in Clos strictly non-blocking three-stage interconnection network factor PN is as following:
PN | = | Pn*m+Pr*r+Pm*n = Pn*2n+Pn*n+P2n*n |
On the other hand, based on Theorem 7, in an NMRN*M(k) network the value of PN*M(k) equals:
PN*M(k) | = | Pk+log2(N*M/k2) |
P2n*n(k) | = | Pn*2n(k) = Pk+log2(2n2/k2) = Pk+log22+log2(n2/k2) = 2log2(n/k)+Pk+1 |
Pn*n(k) | = | Pk+log2(n2/k2) = 2log2(n/k)+Pk |
According to the above equations, the value of PN in CNMRN(k) network equals:
PN | = | 2log2(n/k)+Pk+1+2log2(n/k)+Pk+2log2(n/k)+Pk+1 = 6log2n-6log2k+3Pk+2 |
Considering n = N, then:
PN | = | 6log2N-6log2k+3Pk+2 |
Lemma 3: In CNMRN(k) network, the value of SN equals:
SN | = | 3Sk |
Proof: As in Lemma 1 and Lemma 2, in order to calculate the value of factor SN in CNMRN(k) networks, first the value of this factor must be calculated in Clos strictly non-blocking three-stage interconnection network as follows:
SN | = | Sn*m+Sr*r+Sm*n = Sn*2n+Sn*n+S2n*n |
On the other hand, according to Theorem 8, in NMRN*M(k) network, the value of SN*M(k) equals Sk. Therefore the value of factor SN in CNMRN(k) networks, is calculated as follows:
SN | = | Sk+Sk+Sk = 3Sk. |
DISCUSSION AND PERFORMANCE EVALUATION
Here, the proposed NMR and CNMR networks are compared with Crossbar, Benes and Clos multistage interconnection networks based on the three factors of CN, PN and SN.
Comparing the criterion of CN: According to the computed equations, Fig. 8 shows the number of crosspoints or switching elements (CN) in different networks.
In other words, according to the different values of N and k, the obtained results can be shown in Fig. 8.
As it can be shown in Fig. 8, the CN in the CNMRN(8) network enjoys a more optimal value compared to the other types of networks.
Comparing the criterion of PN: According to the computed equations, Fig. 9 shows the maximum number of crosspoints or switching elements existing in the transferring path (PN) in different types of networks.
According to the different values of N and k, the obtained results can be shown in Fig. 9.
Fig. 8: | Comparative graph between CN in NMR, CNMR, crossbar, benes and clos networks |
Fig. 9: | Comparative graph between PN in NMR, CNMR, crossbar, benes and clos networks |
Fig. 10: | Comparative graph between SN in NMR, CNMR, Crossbar, Benes and Clos networks |
As Fig. 9 shows, the PN in the NMRN(4), NMRN(8), CNMRN(4) and CNMRN(8) network enjoys a more optimal value compared to the other types of networks.
Comparing the criterion of SN: According to the computed equations, Fig. 10 shows the maximum number of connections passing from input to output (SN) in different types of networks.
According to the different values of N and k, Fig. 10 is shown.
As Fig. 10 shows, the SN in the NMRN(4), NMRN(8), CNMRN(4) and CNMRN(8) network enjoys a more optimal value compared to the other types of networks.
CONCLUSION
Three criteria of CN, PN and SN play a important role in the design of interconnection networks. The optimal multistage interconnection networks is a network with the and least value of CN, PN and SN, which is distributed with the minimum overhead and simpler routing algorithm. The obtained results indicate that Crossbar and Benes networks, though being non-blocking and simple in routing mechanism, have higher factors of CN, PN and SN, hence higher cost. A Clos network, on the other hand, has fewer number of CN, but the SN and PN factors are more costly. While in the proposed networks NMR and finally CNMR, the three factors of CN, PN and SN have optimal values of O (NN), O(log2N) and a constant value, respectively. As results, this networks can be used and applied extensively in parallel processing systems and high speed telecommunication networks.