A Multiprocessor is a PC framework with in any event at least two preparing units sharing the access to memory. The basic objective of using a multiprocessor is to process the allotted undertakings simultaneously and lift the framework's exhibition.
An Interconnection Network links multiple caretaking units and has a major effect on the overall framework's presentation. Interconnection Networks, also known as Multi-stage Interconnection Networks, are node-to-node links between processors or groups of processors. These connections transport data from one processor to the next or from the processor to the memory, allowing the task to be isolated and figured in parallel.
Hypercube networks are a type of network topology that connects different processors with memory modules and routes data in a logical manner. 2n node(s) are involved in hypercube systems, with n>0. Any Hypercube can be viewed as a diagram with no directions, in which a node communicates with a processing unit and an edge represents a link between the processors to be conveyed. Degree, Speed, Node Coverage, Connectivity, Diameter, Reliability, Packet loss, Network cost, and other system scales can be used to evaluate the performance of Hypercube Interconnection Networks. Hypercube Network, Folded Hypercube Network, Multiple Reduced Hypercube, Multiply Twisted Cube, Recursive Circulant, Exchanged Crossed Cube Network, Half Hypercube Network, and so on are examples of Hypercube Interconnection Networks [12].
A Hypercube is an n-dimensional geometrical structure that is geometrically equivalent to a Square (n=2) and a Cube (n=3) in terms of dimensions. The number of nodes grows in proportion to the number of Hypercube elements.
A Hypercube is expressed as a shape with an increased number of measurements:
A point is a zero-measurement dimensional hypercube.
1: If this point is shifted one unit length, a line segment, which is a unit Hypercube of measurement one.
2: A 2-dimensional square is obtained by shifting this line segment's length in the opposite direction from itself.
3: A 3-dimensional Hypercube is formed by shifting the starting point unit length toward the direction opposite to the plane it lies on (a Cube).
4: A 4-dimensional Hypercube is formed by transferring the 3D form one unit length into the fourth measurement (a unit Tesseract).
The quantity of vertices, edges and faces of hypercube geography relies upon the quantity of its measurements. The different components of Hypercubes of 0, 1, 2, 3, and 4 measurements alongside their names are appeared in Table 1
Dimension
|
Name
|
Vertex
|
Edge
|
Face
|
0
|
“Point”
|
one
|
|
|
1
|
“Line Segment”
|
two
|
one
|
2
|
“Square”
|
four
|
four
|
one
|
3
|
“Hypercube”
|
eight
|
twelve
|
six
|
Table 1: Components of 0D, 1D, 2D and 3D Hypercubes
Applications of Hypercube Networks:
Hypercube Interconnection Networks are utilized in a differentiated and wide scope of utilizations. A portion of their applications include:
- In Graph Theory, a hypercube is the diagram shaped from the nodes and the links of a n-dimensional hypercube.
Eg: Cubical graph is the diagram shaped by the 8 vertices and 12 edges of a three-dimensional 3D square.
- Hypercubes are extremely intriguing geometric structures which emerge in a wide range of zones of Mathematics including Algebra.
Eg: Finding insignificant types of Boolean (exchanging) capacities, Automation of minimization procedure of Boolean capacities with numerous factors, framework augmentation, and so forth.
- Hypercubes have topological and geometrical properties with applications in a few unique fields, for example, Computer Networks, Parallel Processing, Information Retrieval, Data combination, Social systems, Coding hypothesis, Linguistics and so on.
Eg: Multi entrusting tasks, Computationally Private Information Retrieval (CPIR), Graph shading, phonetic getting the hang of/thinking frameworks for savvy control and recognizable proof.
- Hypercubes are likewise used to perform vector preparing procedure on charts.
Eg: Clustering, Change location, Hypothesis testing with respect to the autonomy of two charts, Feature extraction for neural system, Fuzzy mappings, and so forth.
- The essential calculations for SIMD and MIMD Hypercubes are utilized.
Eg: These incorporate calculations for tackling issues, for example, Data broadcasting, Data aggregate, Prefix total, Shift, Data dissemination, Data gathering, Sorting, Random access peruses and composes and Data change, and so on.
- Hypercubes are pertinent in Image preparing applications.
Eg: These incorporate calculations for picture preparing issues, for example, Image investigation, Image changes, Convolution, Template coordinating, bunching and String altering and so forth. Test results show the adequacy of Hypercubes as a ground-breaking space portrayal both as far as computational time and memory prerequisites.
• And numerous different applications.
Variants of Hypercube Networks
Variants of Hypercube Interconnection Networks include [12]:
- Hypercube Network
- Folded Hypercube Network
- Multiple Reduced Hypercube Network
- Multiply Twisted Cube Network
- Recursive Circulant Hypercube Network
- Exchanged Crossed Cube Network
- Z Cube
- Half Hypercube Network etc…
Hypercube Network:
A Hypercube [13] is an n-dimensional figure that is identical to a shape of cube in three dimensions and a square in two dimensions, according to geometry.
- The base number of steps it takes for one processor to make an impact on the farthest processor is the gap across the interconnection network, termed as the diameter. For example, the diameter of a hypercube with four vertices that resembles a square is two.
- The diameter of a hypercube interconnection network, which is equivalent to an eight-processor cube with each processor and memory module positioned at each vertex of the block, is three.
- For example, if a framework has 2n processors, each of which is directly associated with different processors, its distance across will be n.
A typical Hypercube Network topology is shown in Fig. 2
Folded Hypercube Network:
Folded Hypercube [13] is an undirected graph that interfaces inverse sets of hypercube vertices and is framed from a hypercube by adding ideal coordinating edges.
- Edges between inverse sets of vertices in a hypercube diagram of request k - 1 may be used to frame the collapsed hypercube graph of request k with 2k-1 vertices.
- It can be generated by combining any opposite pair of vertices in a hypercube diagram.
- With 2k-1 vertices and 2k-2 edges, a collapsed hypercube diagram of request k will be k-customary.
- The chromatic number of request k collapsed 3D shape diagram is two when k is even (that is, for this situation, the chart is bipartite) and four when k is odd. The odd circumference of a collapsed 3D square of odd request is k, so for odd k more noteworthy than three the collapsed 3D shape diagrams give a class of sans triangle charts with chromatic number four and self-assertively huge odd size.
- As a separation ordinary diagram with an odd circumference ‘k’ and breadth ‘((k − 1)/2)’, the folded cube of the odd number order are instances of summed up odd charts. At the point when the value of k is an odd number, bipartite two fold front of the order k collapsed solid shape is the k-ordered cube from which it was framed.
- When the value of k is an even number, the request k solid shape is a twofold spread yet not a bipartite twofold spread. For this situation, the collapsed solid shape is itself effectively bipartite. Collapsed 3D shape diagrams acquire from their hypercube sub-charts the feature containing the Hamiltonian cycle, and from the Hypercubes that two fold spread them the property of being a separation transitive chart.
- When the value of k is an odd number, the request k collapsed 3D shape consists as a sub-diagram a total double tree with 2k-1 nodes. Be that as it may, when k is even, this is beyond the realm of imagination, in light of the fact that for this situation the folded cube is a bipartite diagram with equivalent quantities of nodes on each side of the bipartition, altogether different from the almost two-to-one proportion for the bipartition of a complete binary tree [2].
A Folded Hypercube Network topology and Folded Hypercubes of different dimensions are shown in Fig.3
Multiple Reduced Hypercube Network:
- The nodes of a Multiple Reduced Hypercube MRH(n) [13] are communicated as n bit strings Sn, Sn-1, ... Sj ... S2, Sl comprising of double numbers {0,1} (i<i<n).
- The edges of MRH (n) are communicated in three structures. In view of the procedure of association, they are named as Hypercube edge, Exchange edge and Complement edge.
- These are shown as h-edge, x-edge and c-edge separately.
- Each edge is characterized into when n is a much number and n is an odd number [3].
Case 1: When n is an even number, it is assumed that for edge definition, (sn, sn-1, ...si+1) is α and a bit string (si...s2 s1) is β in the bit string of a node U(= sn, sn-1, ..si...s2, s1). Therefore the bit string of a node U(= sn, sn-1,..si ...s2, s1) can be simply expressed as αβ. Assuming that the nodes U and V are adjacent with each other, adjacent edges are as follows [11] [13] [21].
a) Hypercube edge: This edge indicates an edge linking two nodes U(=sn, sn-1,..si ...s2, s1) and V(=sn, sn-1, ...si+1, si...s2, s1) of MRH(n) (n/2≤j≤n).
b) Exchange edge: This edge indicates an edge linking two nodes U(=αβ ) and V(=βα) of MRH(n) if α≠β in the bit string of the nodes.
c) Complement edge: This edge indicates an edge linking two nodes U(=sn α'β') and V(=sn α'β' ) of MRH(n) if α≠β in the bit string of the nodes [11,13, 21].
Case 2: When n is an odd number. It is assumed that for edge definition, (sn-1...si+1) is α’ and a bit string (sn, si...s2, s1) is β’ in the bit string of a node U(=sn, sn-1,..si ...s2, s1). Then the number of bit strings of α’ and β’ is each n /2 . Therefore a node U can be indicated as U (=sn α'β') [11,13, 21].
a) Hypercube edge: This edge indicates an edge linking two nodes U (=sn, sn-1....sj...si+1, si...s2, s1) and V(=sn, sn-1... sj....si+1, si...s2, s1) of MRH(n)
b) Exchange edge: This edge indicates an edge linking two nodes U(=sn α'β') and V(=sn β’α’) of MRH(n) in the bit string of a node.
c) Complement edge: This edge indicates an edge linking two nodes U(=sn α'β') and V(=sn α'β') of MRH(n) if α'= β' in the bit string of a node [11,13, 21].
- Node/edge availability is minimal number of nodes/edges that are required to be wiped out to partition an interconnection network into at least two sections without normal nodes. Regardless of whether k-1 or less nodes are wiped out from a given interconnection network, an interconnection network is connected, and once the interconnection network is isolated when legitimate k nodes are killed, availability of the interconnection network is called k. An interconnection network having a similar node connectivity and degree implies that it has maximal adaptation to non-critical failure [3, 11].
- A Multiple Reduced Hypercube Network is shown in Fig. 4
Multiply Twisted Cube Network:
An n-dimensional Multiply Twisted Cube ‘Qn’ [13, 22] has a similar basic unpredictability as n-dimensional Hypercube Q. That is, it has a similar number of nodes and joins, and every node has a similar degree n, as Q. In any case, past examinations demonstrate that because of a portion of its properties better than hypercube, the Multiply Twisted Hypercube is a decent option for developing multiprocessor systems [4].
- The Multiply Twisted Hypercube is recursively characterized, and it has a relative structure. It is seen that the distance across of Qn is [n+1]/2, which is about portion of the breadth n of the n-dimensional Hypercube Q. Moreover, the normal separation between nodes in Qn is around 3/4 of the normal separation between nodes in Q.
- In combination with the consistency, these properties can be utilized to plan straightforward information correspondence calculations for Qn that are more effective than those for traditional hypercube Q. Additionally, numerous effective hypercube calculations can be straightforwardly adjusted to fit the contorted hypercube [13, 22].
- A Multiply Twisted Cube Network is shown in Fig.5
Recursive Circulant Hypercube Network:
Recursive Circulant Hypercube Network like Recursive Circulant Graph G(N, d) [23, 24] is characterized to be a Circulant chart with N nodes and jumps of powers of d, d⩾2. Here each di is known as a hop. G(N, d) additionally can be characterized as a circulant chart with jumps of powers of ‘d’[5].
- Since Recursive Circulant Graphs are a subclass of Circulant Graphs, they are vertex-symmetric. Recursive Circulant Hypercube Network is node symmetric, and subsequently standard.
- G(N, d) has a Hamiltonian cycle unless N⩽2, and can be recursively constructed when N=cd, 1 ⩽ c ⩽d [23, 24].
- Sample Recursive Circulant Hypercube Graphs G(8,4) and G(16,4) are shown in Fig.6