DEFINITIONS topological characteristics of CLUSTER FOR FIVE scalable MPP (Massively Parallel Processor) Systems

Laboratory works 1-5

The purpose of work: the study of the properties of different scalable MPP systems based on their topological characteristics.

General theoretical information

MPP systems or systems with mass parallelism - a multi-Computer Systems (CS) with local memory. Their main advantage - unlimited scalability (possibility of increasing the number of processors in the system without changing their properties). In this regard MPP system can consist of hundreds, thousands or even tens tysch processors. So, today the most productive systems such as Roadrunner include more than 192 thousand processors, and Blue Jene / L - about 213,000 processors.

The most important aspect of MPP systems is how to interact separate processors. System configuration interprocessor communication significantly affect the order of connection lines connecting individual processors. Organization of internal communications cop called topology.

Depending on whether the configuration remains unchanged relationships (unless performed the appropriate tasks), distinguish the computer system with static and dynamic topologies. Static computer system structure fixed interconnections. In the Constitutional Court in the dynamic topology relationships computing configuration using the software can be quickly changed.

• The static topologies include those where between two nodes is only possible one or more fixed routes, ie no switching devices. Of the possible classification criteria computer system elect their static dimension. From this perspective rozriznyayutodnovymirni topology (linear array);

• Two-dimensional topology (ring, star, tree, grid);

• multidimensional topology (topology povnozv'yazana);

• hiperkubichnu topology.

In simple linear topology system components

form a one-dimensional array and connected to the circuit (Figure 1).

Fig. 1. Point-to-Point topology of computer system

In linear topologies are transmitted message depends on the distance between nodes, and the refusal of one of them can lead to the inability to transmit messages. At this point in linear computer system using failover nodes that failure isolate itself from the network, allowing you to avoid the notice defective unit.

Fig. 2. Ring topology of computer system

Standard ring topology (Figure 2) is a linear chain, the ends of which are interconnected. Disadvantage: adding or removing a node requires dismantling the network.

Torx organization nodes (Fig. 3) are rarely used to combine multi-processor computer system , but works well when the flow of information coming from several secondary nodes connected to a primary node, such as connecting terminals. The total network bandwidth is usually limited speed hub. The main advantage of a star schema that constructive response units at the ends cbcntvb can be very simple.

Fig. 3. Star topology of computer system

In tree topology (Figure 4) system is based on a scheme of binary tree where each node is a higher level associated with two nodes following the order of a lower level. A node that is at a higher level, called parent and two connected to it downstream unit - subsidiaries. In turn, each child node acts as a parent for the two units next lower level. Each node is connected only with two subsidiaries and one parent.

Fig. 4. Tree topology of computer system

When large volumes of data between 'non nodes tree topology is not enough effective, because messages must pass through one or more intermediate processors. At higher levels of congestion probability by insufficient bandwidth lines above.

lattice topology of computer system (Figure 5) focused on tasks related to processing areas. Their configuration is determined by the type and dimension of the array.

Fig. 5. lattice topology of computer system

In systems where each processor is connected to several neighboring processors can achieve a compromise between the complexity of the system interprocessor communication, its bandwidth and latency data exchange. In the one-dimensional lattices processors often called linear array, each processor except the extreme connected to two neighbors. This data is sent from the source CPU processor receiver series processors transit are located between the source and receiver. In the two-dimensional lattice, each processor is connected to the northern, southern, eastern and western neighbors. Grill processors are characterized by regularity, locality and ease routing interprocessor communications. In three-dimensional array of processors each connected with six neighbors. The advantage of this system is the minimum number of lines (with each processor comes less than two lines).

In the fully bound system, each processor has a direct connection to any other processor.

Merging parallel processors is very popular hypercube topology. The line connecting two nodes (Figure 6, a) defines a one-dimensional hypercube. Square, which is formed by four nodes (Figure 6, b) - dimensional hypercube, a cube with 8 nodes (Fig. 6 in) - dimensional hypercube and etc.

Messaging hypercube based on the binary representation of numbers of nodes. Numbering units is such that for any pair of adjacent nodes binary representation of the numbers of nodes differ in only one position. Units 010 and 110 - the neighbors and nodes 110 and 101 are not.

Fig. 6. Hypercube topology of computer system

This architecture provides a small number of links between processors. In the Constitutional Court with the computational process architecture is constructed as follows: in each processor node has its own memory and accordingly has a powerful computing resource. If processing power is not enough, the solution to attract processors with neighboring nodes or the entire cube. If this is not enough, involve processors, which are located in sites outside hypercube respect to this.

Deficiencies of certain types of systems are minimized in their combination (hybrid systems interprocessor communication). For example, the configuration of the pyramid is obtained by adding links between processors belonging to the same tier of the tree, according to the configuration of two-dimensional arrays. Thus, the combined benefits of the pyramid and wood lattice.

The structures of clusters computer system also referred to as hybrid communication systems. Within the cluster processors connected according to one of the configurations of connections, such as common rail, and several clusters merged at computer system with a different configuration of connections, such as lattice or hypercube.

In the dynamic topology computer system connection node is provided with electronic key, varying settings which can change the topology of the system. The nodes are dynamic computer system switching elements and devices that exchange messages (terminals) are connected to the inputs and outputs of the network. As the terminals can act as processors or processors and memory modules. For these computer system most often used single or multistage switching based matrix switches.

“Bus” type architecture - the most simple and inexpensive dynamic computer system . In this topology (Fig. 7), all components connected to the same bus that is used together. At a time messaging can conduct only one pair of nodes, ie during transmission message bus can be seen as a network that consists of two nodes.

Fig. 7. Bus topology computer system

More efficient dynamic architecture computer system is a system in which processors are interconnected via the matrix switch. In this case, each time messaging can lead n / 2- pairs of nodes, where n - the number of nodes in the system. The disadvantage of this architecture is the high cost.

1. Today, most of MPP is based on clusters. Because lab work is devoted to such systems with static topologies. To analyze their potential in terms of efficiency funktsionuvannyanyh use different topological characteristics. The main topological characteristics are:
1. The diameter (D). The diameter of - a minimum distance between the most remote processors. For example, the diameter of a consistent system for fully equal to 1, and for topology "star" is 2. The diameter of the ring topology is , a linear topology is n-1, where n - the number of processors in the system. The best value is the minimum diameter.
2. The average diameter ( ). This characteristic is determined according to the formula:
(8)
where d_ij - minimum distance between i-th and j-th processors. The best is the minimum value of the average diameter.
3. Degree (S). This characteristic is defined as the maximum number of arcs (relationships) incidental top (CPU) in a graph topology system. Thus, the degree of linear and ring topologies is 2, is fully consistent, topology n-1, and the tree topology is 3. The best is the minimum value of the degree.
4. Cost (C). There is a set of options for determining the cost of the system. According to one of them value is defined as the total number of links in the system. Under the second option value determined according to the formula:
C = (9)
In the works you can use any version of the definition of value. The best value is the minimum value.
5. topological traffic (T). This characteristic (for symmetric systems) determined according to the formula:
T = (10)
Topological traffic determines the degree of use of links in the system. The optimum value T = 1, which means the potential use all the existing relations between processors. If T <1, this means that some physical links in the system when sending data will not be used. If T> 1, when sending data existing in the system connections will not be enough, so have extra time delay.

Input for laboratory work 1-5

Input data for laboratory work are five scalable topologies MPP systems based on cluster (for each laboratory work has its own system). Variants of such systems are presented in Table 1. It includes 38 clusters of options that can be combined in one of the following topologies:

• line

• ring

• star

• binary tree

• grid

• tor

Option agreement with each of the teacher.

Table 1

Variants of tasks for laboratory work 1-5

The types of topologies:

1. lyniyka

2. ring

3. tree

4. grille

5 star

6. Thor

Set on laboratory work and the procedure for its implementation.

For each set of topologies:

1. Determine the order numbering system processors in clusters scaling.

Example. Let set linear topology system that consists of clusters shown in Figure 11.

Figure 11

Define numbering CPU scaling (Fig. 12).

1 step zoom

Step 2 Zoom

3 step Zoom

p Step Zoom

Fig. 12

2. Determine the number of processors that are attached to every step of scaling. For this example a number of processors equal to 3 (for certain topologies that value is not const and may be determined by analytical formula).

3. Describe Software connection between processors (vnutrshnoklasterni and mizhklasterni) every step of scaling by appropriate adjacency matrix. The size of matrix determined by the number of processors. If there is a connection between the i - th and j - m processors corresponding to the matrix at the intersection of i - th row and j - th column is equal to "1", otherwise equal to "0". For example, the adjacency matrix for 1 - First step zoom is as follows:

N 1 2 3

1 0 1 1

2 1 0 1

3 1 1 0

Adjacency matrix for 2 - First step zoom topology shown in Fig. 12 is:

N 1 2 3 4 5 6

1 0 1 1 0 0 0

2 1 0 1 0 0 0

3 1 1 0 1 0 0

4 0 0 0 0 1 1

5 0 0 0 1 0 1

6 0 0 1 0 0 1

Zoom all topologies to perform as long as the number of processors the system reaches a value of 100.

4. For each step of scaling using software adjacency matrix to calculate basic topological characteristics (diameter, diameter, degree, value, topological traffic).

To determine the diameter (D), you can use the following formula:

D = max {dij}

where dij - the shortest distance between the i-th and j-th column processors in the system. To determine dij can use one of the algorithms (Dijkstra, Floyd, wave).

The value of the degree system is defined as the maximum "1" in the line adjacency matrix. Cost is determined by the system or by the formula (9) or the sum of "1" in the adjacency matrix divided by 2.

To determine the (average diameter) can use the formula (8) .Topolohichnyy traffic given by (10). For example, one step scaling topology in Figure 12, the characteristics have the following meanings: D = 1, = 1.0, S = 2, C = 3, T = 1. For 2 - First step zoom topology in Figure 12, the characteristics are the following values: D = 3, = 1.8, S = 3, C = 7, T = 1.2.

The results of calculating topological characteristics of each topology may be presented in the following table 2:

n (number of processors) topological characteristics