The interconnection network plays a vital role in the design of high performance computing systems as it defines the means of data exchange among many standalone processing units. The interconnection network also presents the underlying architecture i.e. topology used for these systems. Hence, the performance of these systems mainly depends on their interconnection network. Thus, in order to design a highly reliable high performance computing system, it must be ensured that the used interconnection network should be highly reliable i.e. it should work satisfactorily for a specific period of time even occurrence of some failures like link and/or computing units. Further the use of interconnection network in these systems should be economical. One way to measure the cost of the interconnection network is the product of its degree to diameter. In other words, it can be said that highly reliable as well as economical interconnection network must be deployed to design such systems. Some examples of Interconnection network include Hypercube and its variants, Torus, Mesh, eTVC.The hypercube (HC) has been used in [1-2, 20, 28-31] due to its properties like small diameter, strong connectivity regularity, symmetricity, recursive construction, partionability, fault tolerance, and reliability. Many variants of hypercube have been proposed in the past either to enhance its reliability or to decrease its cost. The variant includes cube connected cycles [23], twisted hypercube [3], folded hypercube [5], crossed cube [6, 8], exchanged hypercube [4,41], incomplete crossed cube [5], banyan hypercube [15], varietal hypercube eTVC. The hypercube is also a good choice of researchers to propose many hierarchical interconnection networks viz. hierarchical hypercubes, hierarchical crossed cubes, hierarchical cube networks, extended hypercube, eTVC. [30]. However, the main problem associated with hypercube and its variants is their implied constraint to scale. The prominent topologies to provide a high degree of scalability are Mesh and torus [24-27]. These networks are found to be used widely in the area of scientific calculations, flow dynamics, structural analysis, eTVC. However, the large diameter of mesh network prohibits its use in the design of a massively parallel computer system [9-10]. In addition to this, high cost and difficulty in set-up and maintenance of this network further make it difficult to implement in real life parallel machines. In comparison to mesh, Torus has high connectivity and more reliable. Hence, it is used in the design of various parallel machines such as Alpha 21364-based HPGS 1280 [4], Cray XT3 [11] and XT4 [12], X1E [13], Cray X1-E vector computer [14]. Moreover, IBM Blue Gene family of massively parallel computers are some remarkable examples of mixed Radix 3D Tori [30-32]. In order to decrease very large diameter of the torus, a new class of recursively structured torus connections networks called recursive diagonal torus (RDT) has been proposed in [22].The discussion carried out so far reveals that the torus has a fixed degree but has a relatively large diameter (2n). While, the diameter of the hypercube is comparatively small, but its node connectivity increases logarithmically with the size of the network. Under such conditions taking the product of two standard topologies is a potential process of constructing a new interconnection network [16-19]. The cross product of interconnection networks is observed to be outperforming traditional topologies with different structural properties [11]. Hence, the problem of designing a scalable, cost effective, highly reliable, fault tolerant network with the lower diameter and strong connectivity with less hardware complexity is yet a challenge. This motivates us to propose a new hybrid interconnection network called TOR- VARIETAL CUBE (TVC) which inherits the properties of two popular interconnection topologies: varietal hypercube and torus. The proposed topology (TVC) exploits most of the important properties of hypercube and torus. The present work focuses and analyzes the different design factors of TOR-VCUBE (TVC) and compares its topological properties with that of other important interconnection topologies.

PROPOSED INTERCONNECTION TOPOLOGY: TOR-VCube (TVC)

The proposed interconnection network uses an n-dimensional hypercube as its base. Additional links from a torus interconnection network are added to the base Varietal hypercube interconnection network to form an n-dimensional TOR-Varietal CUBE. e.g. For a 3D TVC, first a 3D Varietal hypercube (VHC) is taken (Fig. 1), and then extra 4 links from the torus interconnection topology are added to it. The extra links are connected to the adjacent opposite nodes in torus pattern (Fig. 2). The proposed topology is scalable and therefore is most suitable for large scale parallel processing (Fig. 3).

. Fig. 1 Varietal Hypercube

Fig. 2 Torus

Fig. 3 TOR Vcube (TVC) of Dimension 3

Fig. 4 TOR Vcube (TVC) of Dimension 4

TOPOLOGICAL PROPERTIES OF TOR-VCUBE INTERCONNECTION NETWORK

The TOR-VCUBE is viewed as an undirected graph G (V, E), where , V is the node set representing the processing elements and E represents the set of edges representing the connecting links between the processing elements.

The different topological properties of TOR-VCube are presented in this Section.

Nodes

The number of nodes of n-dimensional TOR-VCUBE is 2ⁿ.

Degree

The degree of an interconnection network is the degree of the node which has a maximum number of links connected to it. The degree of TOR-VCUBE is (n+1) since every node is connected to exactly n+1 of its neighbor nodes.

Links

A link denotes a communication edge between two processing elements in a network. The nodes u and v are said to be adjacent if a link .

Theorem 1: The total number of links of n-dimensional TOR-VCUBE is (n+1)2^n-1

Proof:  Let TOR-VCUBE is an undirected graph G (V, E) consisting of 2ⁿ number of nodes,

 If L is the total number of links of TOR-VCUBE (V, E) having dimension ‘n’ then the L can be computed by using Handshaking Lemma of Graph Theory.

Further the degree of TOR-VCUBE is (n+1) since every node is connected to exactly n+1 of its neighbor nodes.

By Handshaking Lemma of Graph Theory

Sum of the degree of vertices = 2 * Number of edges of the graph

                                2L = (n+1) * 2ⁿ

                                  L = {(n+1) * 2ⁿ} / 2

                                      = (n+1) * 2^n-1

Diameter

The diameter of graph G (  ), is the maximum of the minimum distances between any two distinct vertices  of G. The is measured in terms of a number of distinct hops between any two nodes. It determines the number hops a node will take to broadcast a message to all other nodes in the network. Therefore, it should be kept small.

Theorem 2 : The diameter of the TOR-VCUBE is ┌  2n/3 ┐ - 1

Proof: Since every node is connected to its neighboring nodes by n+1 links , So the distance to nonadjacent node of

  TOR-VCUBE is ┌  2n/3 ┐ - 1 as the diameter of varietal hypercube is  ┌  2n/3 ┐

Cost

For a symmetric interconnection network, the cost is defined as the product of the degree and the diameter of the network. This is an important factor is broadly used in performance evaluation.

Mathematically,

Therefore, the cost of TOR-VCUBE  can be computed as follows  :

Cost = Degree * Diameter

        =  (n+1)  * ┌  2n/3 ┐ - 1

As the degree of  TOR-VCUBE  is (n+1) and  the diameter of the TOR-VCUBE is ┌  2n/3 ┐ - 1

Lemma 1 :  D _TOR-VCube   <  D _VHC  <  D _TOR-Cube <  D _HC

                    where  D _TOR-VCube      is the diameter of  TOR- VCube TVC(n,k)

                                D _VHC              is the diameter of  Varietal Hyper Cube VHC(n,k)

                                D _HC              is the diameter of  Hyper Cube HC(n,k)

Proof :  The diameter of  TOR-VCUBE is ┌  2n/3 ┐ - 1  , the diameter of  Varietal Hyper Cube VHC(n,k) is ┌  2n /3  ┐ and the diameter of  Hyper Cube HC(n,k) is n .

Lemma 2 :  Cost _TOR-VCube  <  Cost _TOR-Cube  

where   Cost _TOR-VCube      is the cost factor of  TOR- VCube TVC(n,k)

             Cost _TOR-Cube         is cost factor of  TOR- Cube TC(n,k)

Proof :  The cost of cube network is given by the product of the degree of the node and the diameter . As the the diameter of           TOR- VCube  is   ┌  2n/3 ┐ - 1   and the degree of the node is  n+1 . Hence The cost of  TOR- VCube  is  { ┌  2n/3 ┐ - 1   } * (n+1)  .    As the  diameter of  TOR-Cube    n-1  and the degree of the node is  n+1 . Hence the cost of  TOR- Cube   is  { (n-1) * (n+1)}  .

Average Distance

In practice, the average distance describes the performance of the interconnection network. The average distance of the interconnection network is the summation of distances of all nodes from a specified node over the entire number of nodes. The average distance of an interconnection network is mathematically represented as:

    Theorem 3:   (I) The local  average distance of  TVC(n,k) is

                          where k=3x+y, y<3 and x, y are integer values.

                        (II) The global  average distance of  TVC(n,k) is      d  ∑dNd  /(N  M )

                              Where  Nd =  No of processor at distance d from the source node

                        N   =  Total number of PCs = 2^nk

                      M   =  Total number of NCs = 2 (2^nk – 1) / (2ⁿ – 1)

Proof : I.  The average distance is an important parameter to measure the actual performance of the network. The average distance of the network is the summation of distances of all nodes from a given node over the total number of nodes . In TVC(n,k) there exist two types of communication namely local and global. Therefore, there are two average distances i.e. local average distance and global average distance.

In the TVC(n,k) network the lower level is a Crossed cube. So, the average distance in the basic module is same as that of the Varietal cube and it is    

 where k=3x+y, y<3 and x, y are integer values .

∑dNd  = 2k (n 1)  2 (2ⁿ (n 1)) (k 1) (2ⁿ (n 1))    2k 2^n(k1) (2k 1) n 2^n(k1)  2 ∑_j=1n2 ^jn2k 1 j2ⁿn 12jn    2k  j dNd

∑dNd  =2  n  2(2 ⁿ  (n 1))   for k=1

Processing Elements

The number of  processing elements is an important parameter to measure the actual performance of the network. The number of processing elements of the network is the summation of  all nodes at each level.

Theorem 4 :  The number of Processing Elements in  TVC(n,k) is  2^nk

                        The number of Network Controllers at level 1  =  j  =  k  in  TVC(n,k)  is  2 * 2^n(k-j)

Proof :  I.  In TVC(n,k) all the Processing Elements (PEs) are at level j=0 . These PEs are connected to

NCs at level 1 for which the value of j=1 . Thus the number of NCs at level 1 at one side is 2^n(k-1)

To each NC 2ⁿ PEs are connected hierarchically

Thus to  2^n(k-1) NCs , the number of PEs connected =  2^n(k-1)  *   2ⁿ

At level 1  =  j  =  k  there are  2^n(k-j) NCs at one side and also same number of NCs at opposite side as seen from the construction . The number of Network Controllers at level j   in  TVC(n,k)  is  2 * 2^n(k-j)\

In particular when j=k : When we are at highest level of TVC(n,k)  where there two NCs

Put j=k in formula  2 * 2^n(k-j) i.e. 2 * 2^n(k-k) =  2 * 2⁰ = 2

The formula agrees with the 2 NCs .

P(j) :  2 * 2^n(k-j)  1  =  j  =  k

P(1) :  2 * 2^n(k-1)

At level 1 we have   2^n(k-1) NC at one side and also same number of NCs at opposite side as seen from the construction

According to the Induction Hypothesis P(m) is true .

P(m) :  2 * 2^n(k-m)

 At level m we have   2 * 2^n(k-m) NC

Induction Step : As we go higher the number of PE/NC is divided 2ⁿ

The number of NC at level m+1 = Number of NC at level m / 2ⁿ

                                                    = 2 * 2^n(k-m) /  2ⁿ

                                                    = 2 * 2^{n(k-m) – n}

                                                       = 2 * 2^{n(k-m – 1)}

Message Traffic Density

An effective interconnection network must have extensive bandwidth to incorporate the consequential traffic in order to keep the traffic density minimum. If every node is sending message to another node at distance ’d’ apart, then it is required to analyze the performance of the network in managing the message traffic. The message traffic density is

defined by   .

Theorem 5:  The message traffic density of  TOR-VCUBE (TVC)  is     dNt / L

                              Where Nt    = N + M  and L is the number of links

Proof : Assuming that each node is sending one message to a node at distance d on the average and considering the availability of n links to accommodate such a traffic,   can be a good measure to estimate message traffic in the network

As we know that N = 2^nk    and   M = (2^nk - 1) / ( 2ⁿ – 1)

At level 1 we have 2*  2^n(k-1) NCs and at level k there are only two NCs . So the sum of processors from level 1 to k-

1 is

2  *  { [  (2^nk - 1) / ( 2ⁿ – 1) ] -   2^n(k-1)  – 1) }

Now assuming handshaking lemma from graph i.e.

2( Number of edges of the graph) = Sum of the degrees of vertices

We have ,

2L = 2^nk ( n + 2) + 2  *  { [  (2^nk - 1) / ( 2ⁿ – 1) ] -   2^n(k-1)  – 1) } ( 2ⁿ + n + 3) + 2  * 2^n(k-1) * (2ⁿ + n+2) + 2* 2ⁿ⁺¹

  L  = 2^nk-1 ( n + 2) + { [  (2^nk - 1) / ( 2ⁿ – 1) ] -   2^n(k-1)  – 1) } ( 2ⁿ + n + 3) +  2^n(k-1) * (2ⁿ + n+2) +  2ⁿ⁺¹

RESULTS

The following Table for message density of ECC and Table for message density of TVC  shows the simulated result for the values of d , N , M , L and  

 for ECC(3,k) and  TVC(3,k) basing on the given proposition.

The above table depicts that TVC has less message traffic density  not only from its parent topologies but also from some other important topologies. Therefore, the hardware complexity for the design of TVC is also economical, reasonable and feasible.

CONCLUSIONS AND FUTURE SCOPE

A new interconnection topology namely TOR-VCUBE (TVC) is proposed in this paper. The proposed topology is inherited from two base class topologies: Varietal hypercube and torus. It can be observed that the proposed interconnection network is more suitable for parallel computer architecture because of its high connectivity, lesser diameter, low cost, more fault tolerant and low average distance. It can be concluded that the proposed interconnection network is highly reliable and cost effective with a better degree of scalability.  it can be concluded that the proposed interconnection network is highly reliable and cost effective with a better degree of scalability. The different reliability measure of the TVC like network reliability, two-terminal reliability and k-terminal reliability can be evaluated and compared against that of other interconnection networks of interest in future. We can also study the broadcasting algorithms in near future. The work carried out in this paper may further be extended to propose a new hierarchical interconnection network using TOR-VCUBE as the base network.

REFERENCES

1. R. Adiga, G. Almási, G. S. Almasi, Y. Aridor, R. Barik, D. Beece,
2. Bellofatto, G. Bhanot, R. Bickford, M. Blumrich, et al. “An overview of the Bluegene/l Supercomputer”, In Supercomputing, ACM/IEEE 2002 Conference, pp. 60-60, 2002.
3. -P. Chang, T. -Y. Sung, and L. -H Hsu, “Edge Congestion and Topological Properties of Crossed Cubes”, IEEE Transactions on Parallel Distributed System, vol. 11, no. 1, pp. 64-80, 2000.
4. -P. Chang, J. -N. Wang and J. -H. Hsu, “Topological Properties of
5. Cvetanovic, “Performance Analysis of the Alpha 21364- Based HP GS1280 Multiprocessor,” InProceedings of 30th Annual International Symposium on Computer Architecture, pp. 218-228, 2003.
6. K. Dash and C. R. Tripathy, “A New Fault-tolerant Interconnection Topology for Parallel Systems”, IE(I) Journal-CP, vol. 89, pp. 8-13, 2008.
7. Efe, “The Crossed Cube  Architecture  for  Parallel Processing”, IEEE Transactions on Computers, vol. 41, no. 5, pp. 513-524, Sept. 1992.
8. M. H. Rahman and  S.  Horiguchi,  “HTN:  a  New Hierarchical Interconnection Network for Massively Parallel Computers”,  IEICE Transactions of Information System, E86-D, pp. 1479-1486, 2003.
9. -C. Hsu, C. -H. Tsai, C. -H. Tsai, G. -J. Wu, S. -H. Liu and P. -L. Lai, “Hierarchical Crossed Cube: A New Interconnection Topology”, InProceedings of 25th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, pp. 70-79, 2008.
10. IBM, “IBM System Blue Gene Solution,” http://www-03.ibm.com / servers / deepcomputing / bluegene.html, 2008.
11. Imani and H. Sarbazi-Azad, “Properties of a Hierarchical Network Based on the Star Graph”, Information Sciences, vol. 180, no. 14, pp. 2802–2813, 2010.
12. Cray Inc., “Cray XT3 Datasheet,” http:// www.cray.com/ downloads/

Cray_XT3_Datasheet.pdf, 2008.

12. Cray Inc., “Cray XT4 Datasheet,” http://www.cray.com/ downloads/

Cray_XT4_Datasheet.pdf, 2008.

13. Cray Inc., “Cray X1E Supercomputer,” http://www.cray.com/ downloads/ X1E_datasheet.pdf, 2008.
14. Lai, H. Hsu, C. Tsai and I. A. Stewart,  “A  Class  of Hierarchical Graphs  as  Topologies  for  Interconnection Networks”, Theoretical Computer Science, vol. 411, no. 31-33, pp. 2912-2924, 2010.
15. Miguel-Alonso, J. Navaridas, and F. J. Ridruejo, “Interconnection Network Simulation Using Traces of MPI Applications,” International Journal Parallel Programming, vol. 37, no. 2, pp. 153-174, 2009.
16. Rajabzadeh, H.  Sarbazi-Azad,  H.  R.  Zarandi  ,  E.  Khodaie, H. Hashemi-Najafabadi, and M. Ould-Khaouae, “Performance Modeling of n-dimensional Mesh Networks”, Performance Evaluation, vol. 67, no. 12, pp. 1304–1323, 2010.
17. Razavi and H. Sarbazi-Azad, “The Triangular  Pyramid: Routing and Topological Properties”, Information Sciences, vol. 180, no. 11, pp. 2328–2339, 2010.
18. Sabbaghi-Nadooshan, M. Modarressi,  and  H.  Sarbazi-Azad, “A Novel High-Performance and Low-Power Mesh-Based NoC,” In IEEE International Symposium on Parallel and Distributed Processing IPDPS, pp. 1-7, 2008.
19. Sun, P. Y. S. Cheung and X. Lin, “Recursive Cube of Rings: A New Topology for  Interconnection  Networks”,  IEEE Transactions on parallel and distributed systems, vol. 11, no. 3, pp. 275-286, 2000.
20. Szlachcic, “Fault Tolerant Topological Design for Computer Networks”, In Proceedings of the International Conference on Dependability of Computer Systems (DEPCOS-RELCOMEX), pp. 150-159, 2006.
21. Bhardwaj, ”C2Torus New Interconnection Network Topology Based on 2D Torus”, American Journal of Networks and Communications. Special Issue: Ad Hoc Networks. vol. 4, no. 3-1, 2015, pp. 1-4.
22. Yang, A. Funahashi, A. Jouraku, H. Nishi, H. Amano and T. Sueyoshi, “Recursive Diagonal Torus: An Interconnection Network for Massively Parallel Computers”, IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 7, pp. 701-715, 2001.
23. -H. Liu, M.-F. Zhu, L.-M. Xiao, and J. Wang, “Asymmetrical Topology and Entropy-based Heterogeneous Link for Many-core Massive Data Communication,” Cluster Computers., vol. 16, no. 4, pp. 679–691, 2013.
24. J. Andujar-Munoz, J. A. Villar-Ortiz, J. L. Sanchez, F. J. Alfaro, and J. Duato,   “N-Dimensional  Twin   Torus  Topology,”  IEEE  Trans.

Comput., vol. 64, no. 10, pp. 2847–2861, 2015.

25. Yadav and C. R. Krishnai, “CCTorus : A New Torus Topology for Interconnection Networks,” In Proc.of International Conference on Advanced Computational Technologies and Creative Media, pp.8- 14,2014.
26. K. Arora and Rajkumar, “C2Mesh,”, 3rd IEEE International Advance Computing Conference (IACC), 2013, pp. 282–286.
27. Punhani, P. Kumar, and N. Nitin, “Routing for Center Concentrated Mesh,” Int. J. Intell. Eng. Syst., vol. 10, no. 1, pp. 86– 94, Feb. 2017.
28. Chauhan, A. Punhani, and Nitin, “Comparative analysis of traffic patterns on center connected topologies based on burton normal form,” in IEEE Region 10 Annual International Conference, Proceedings/TENCON, 2016, vol. 2016.
29. Punhani, P. Kumar and, Nitin, “Diagonal Connected T Mesh,”

Indian J. Sci. Technol., vol. 9, no. 32, pp. 1–7, 2016.

30. S. Kim, H. O. Lee, M. Kim, and S. W. Kim, “The new Petersentorus networks,” J. Supercomput., vol. 71, no. 3, pp. 894–908, 2015.
31. Akash Punhani, Pardeep Kumar and Nitin Nitin, “Three-Dimensional Topology based on Modified Diagonal Mesh Interconnection Network”, Journal of Telecommunication, Electronic and Computer Engineering, vol 9, no 3-6, pp. 1-6, 2017.
32. A Punhani, P Kumar, “A horizontal fat mesh interconnection network”, Tenth International Conference on Contemporary Computing (IC3), pp. 1-5, 2017.