Keywords

1 Introduction

At present, the researchers are attempting several ways to achieve more and more computational power. To adjust the intensive demand of computational power, different methodologies are considered such as the clock pulse, multi-core and many-core processor as well as multi-node massively parallel computer (MPC) system [1]. All above techniques improved the computational power, but MPC systems exceed the limit of others. It consists of millions of nodes [2, 3], and the node of the MPC itself is a multi-core processor. These huge numbers of node cannot be connected by conventional connection topologies, for that apposite method is needed. In MPC, interconnection network plays a fateful role to connect those huge numbers of nodes and it is also a reliable alternative process which can be interconnected together with different types of networks. The use of interconnection network with MPC systems has become tremendous and increases performance radically.

The overall performance of MPC such as fault tolerant [4], inter-node communication, and network on chip depends on its interconnection network. However, due to the lack of enough connectivity, the MPC industry community does not get attracted to the potential attention of the hierarchical interconnection network. As mentioned earlier, MPC systems are consisted by huge number of nodes. Therefore, optimal diameter degree (ODD) network is needed for obtaining the credibility of a hierarchical interconnection networks. The midimew-connected mesh network (MMN) [5] is the better option of ODD; it supports small distance parameters, less number of wire required connecting nodes, low cost, and constant node degree [6]. The midimew network is enwrapped by the 2D mesh network where one dimension enwraps like Tori-connected and the other dimension enwraps diagonally. However, in MMN, long diagonal links bring some limitation by which routing algorithm becomes complex and long length wires in VLSI realization [7]. To avoid those limitations, reinvestigate the MMN network.

Considering investigation, remove the 2D mesh BM from the MMN network and integrate flattened butterfly network in it. 2D torus network is considered for the higher-level TFBN to have the less number of long links because long links are not desirable for VLSI implementation. It also speeds up the inter-node communication. Then, we can achieve a new hierarchical interconnection network that is Tori-connected flattened butterfly network (TFBN) [8]. The hierarchical interconnection network TFBN is a combination of flattened butterfly network denoted as a basic module (BM) and the torus network denoted as a higher-level interconnection network which are connected hierarchically. Despite all of those research works, the thing is essential and important to study how case to be implemented of the mentioned TFBN network in VLSI realization.

In this consideration, the packing density is one of the essential parameters that determine the implementability of mentioned interconnection network. The key objective of this paper is to study packing density of the mentioned TFBN over other networks. The remainder section of the paper is arranged as follows: In Section II, the basic architecture of the TFBN is described. The main contribution of this paper, packing density, and the conclusion of this study are discussed in Section III and Section IV, respectively.

2 Tori-Connected Flattened Butterfly Network

Tori-connected flattened butterfly network (TFBN) is a hierarchal interconnection network formed with basic module (BM) and higher-level networks in a hierarchal fashion. In this paper, 2D TFBN is considered and the static network architecture of it is discussed. The BM can be defined as Level_1, and higher-level networks can be defined as Level_2 network, Level_3 network, and so on.

2.1 Basic Module

The basic module of a TFBN is a 2D flattened butterfly network consists of (2n × 2n) grid where total numbers of row and column are 2n and nodes 22n, n is the value of positive integer. There is no obligatory to select the value of n, here taking n = 2 for excellent granularity. In Fig. 1, the basic modules (BM) are imprinted which are (4 × 4) and contain 2n+2 free ports. Those free ports and links are used to connect higher-level interconnection of a TFBN. Figure 1 shows free ports of BMs that are denoted as Level_1.

Fig. 1
figure 1

Basic module of a TFBN

Full size image

Considering the value of n = 2, a (4×4) BM will have 22+2 = 16 free ports. For r = 0, four (i.e., 4(2r) = 4(20) = 4) free ports will be available for inter-level connectivity: 2 for vertical and 2 for horizontal. For higher-level network, two adjacent BMs are connected with bidirectional link which is fixed with ongoing and outbound links. Vertical links consist of vertical in and vertical out. On the other hand, horizontal links consist of horizontal in and horizontal out.

2.2 Higher-Level Network

The number of lower-level network is 22n which are inserted in one higher-level networks; this connection process remains for connecting every node of first level to higher level. In Level_2, (2n × 2n) torus networks are connected with BM where every torus network is connected with 22n = 16 BM. In the same way, the single network of Level_3 is connected with 16 networks of Level_2; thus, TFBN is constructed which is shown in Fig. 2. Removing the complexity of Fig. 2 is not imprinted of BMs links. Level_1 contains 4 × (2r) = 2r±2 free link where 2(2r) are vertical and 2(2r) are horizontal. Here, r belongs to {0, 1… n}, and r is the symbol of inter-level connectivity whose minimal and maximum values are r = 0 and r = n.

Fig. 2
figure 2

Higher-level interconnection of a TFBN

Full size image

TFBN is described as TFBN (n, L, r) whose BM is (2n × 2n) and where levels hierarchy is denoted as L and inter-level connectivity r. In this paper, n = 2 for excellent granularity. Observing TFBN (2, L, r) can be calculated Lmax from (2n × 2n) basic modules, applying the equation Lmax = 2n−r + 1. For example, taking r = 0 and n = 2, Lmax = 22−0 + 1 = 5. Thus, the highest value is 5 for (4 × 4) BM, free ports and links. In Level_L TFBN, the total number of nodes is N = 22nL and those can be interconnected with highest number of nodes by a TFBN (n, L, r). N= 22n(2^(n−r) +1) when maximum hierarchy Lmax = 2 m−r+ 1. It means at least one million nodes can be interconnected when m = 2 and r = 0 which can be constructed by massively parallel computer system.

3 Topological Analysis

Basically, multi-node massively parallel computer (MPC) system performance depends on several fundamental technology and their implementation outcomes. To study the perfectness of any interconnection network, static appraisal is broadly used in particular for a MPC system. Some static performance metrics are focused in this section to classify the performance and effectiveness of the TFBN considering packing density.

3.1 Cost Parameters

An interconnection network’s exact cost depends on its total number of interconnection links and the cost of particular node. The mutual cost of the processor and memory calculates the cost of particular node and also the cost of I/O interfaces of the specific node equivalent to its node degree. The node degree determines the router cost which is one of the significant cost parameters in a node. Table 1 illustrates the node degree where node degree of TFBN is 8, node degree of TTN is 6, and the remaining networks node degree is 4. Therefore, the router cost is not the same for all considered networks.

Table 1 Topological analysis of different interconnection networks
Full size table

3.2 Distance Parameters

The MPC system design influences the distance between two nodes. To illustrate the distance parameters, there are some predefined scales such as meter denotes the system-level hierarchy distance, cm denotes the board level, and mm denotes the chip level. However, hop distance is used for measuring two nodes distance which are static. We have obtained the distance parameter that is hop distance using shortest path algorithm via computer simulation. The highest value of hop distance in a network is called diameter. All considered networks diameter is shown in Table 1, where we have noticed that mesh network holds the highest diameter value and the TFBN holds lowest.

3.3 Packing Density

The product of degree and diameter is called the static cost of any interconnection network. The ratio between the total number of nodes and this static cost is known as packing density [9]. For very-large-scale integration (VLSI) layout, the lower the chip area and the higher the packing density are essential. Actual packing density will depend upon the actual VLSI realization of any interconnection networks, and actual VLSI realization is cost handy. However, before the real implementation of any interconnection network in the VLSI chip, static analysis of packing density gives a significant result whether the interconnection network is suitable or not. This is why, the static analysis of packing density for any interconnection network or hierarchical interconnection network is crucial for the next step of performance analysis. The packing density of any interconnection is defined by the following equation.

$$ {\text{Packing Density}} = \frac{\text{Total Number of Nodes}}{{{\text{Diameter}} \times {\text{Degree}}}} $$
(1)

3.4 Some Generalization

TFBN stands at lowest diameter and highest degree, and that high node degree results in slightly low packing density than that of MMN and torus network. However, the diameter is extremely lower than that of MMN. The maximum hop distance in a shortest path among all distinct pairs of nodes in an interconnection network is known as diameter. And the diameter yields an idea about the maximum latency in that network. This is why, the diameter is broadly used for the comparison of static network performance of different interconnection and hierarchical interconnection networks.

The distance parameter, diameter, of mesh and torus networks is assessed by applying their specific formula. Also, we have evaluated the diameter of the proposed TFBN along with its rivals MMN [5], TTN [9], and TESH [10] network by applying computer simulation. Due to high diameter of mesh network, the packing density of mesh network is low. The packing density of TTN and TESH network is also a bit low because of slightly high diameter of TESH network and high degree of TTN. The proposed TFBN results in high packing density because of low diameter even though the degree is high.

The different types of network’s packing density are determined considering 256 nodes which are illustrated in Table 1. It is depicted that packing density of a TFBN is higher than that of TTN, TESH, and mesh networks and also lower to some extent to that of MMN.

4 Conclusion

In this paper, we have viewed the packing density of the TFBN in detail. For determining the effectiveness, we also consider this parameter of mesh, torus, TESH, TTN as well as MMN and compared with TFBN’s one, and excellence of TFBN is determined by the comparison. The TFBN’s interconnection links reduce the hop distance and remove long diagonal links that improve the distance parameters compared with others, and it also brings the high packing density. Due to high node degree of TFBN, the packing density of TFBN is slightly lower than that of other networks considered in this paper. In the next steps of our study, we are intending to evaluate the cost-effectiveness and time cost-effectiveness of TFBN.

The Tori-connected flattened butterfly networks (TFBN) architecture and its packing density are illustrated in this paper. We have the plan to study and work in the future with: (1) Evaluation of TFBN for higher-dimensional static network and (2) evaluation of MMN where 2D mesh is replaced by torus network and higher-level network as a flattened butterfly network.