InterPSS Grid Computing Extension

1. Introduction

InterPSS has shown its tremendous computational capability by both the Grid-Computing edition and the Cloud edition. However, the parallelisms of the two mentioned editions are only implemented on the so-called “task level”, say, a power flow calculation can only be run within a certain computing node, while only a large number of similar power flow calculations can be distributed to different computing nodes. The most obvious example is the steady state N-1 security analysis, where similar power flow calculations tasks are generated by trigger the electrical power elements one by one, then the tasks are sent to all the computing nodes within the same computing grid.

Such efforts are far more advanced than most of the power system simulators, especially when approximately inverse relation between the computing time and the scale of the computing grid is verified for bulk power system examples[1]. However, the task-level grid computing cannot fulfil all the requirements; for example, it cannot be grid-enabled when continuous power flow calculation (CPF) is implementing. Thus grid-enabled power flow algorithm is required essentially.

The reason that calculations like CPF cannot be grid-enabled as usual mainly because that the solution cannot be earned by the combination of independent similar power flow calculations, since on the PV curve each point can only be calculated when its previous point is determined, then logically serial computing should be used instead of parallel computing in this scenario. On the other hand, if each point on the PV curve (basically power flow solution) can be calculated via grid computing, the entire PV curve can also be plotted gridifiedly. In fact, almost everything related with steady-state electrical power system analysis can be grid-enabled when a grid-computing version of power flow calculation is available.

The key essential element of the “gridifiability” of a certain computing task is that the task can be split into several sub-tasks; the sub-tasks should be similar and independent with each other, such as the N-1 analysis example mentioned above. This document want to show such gridifiability of Gauss-Seidel algorithm (GS), while detailed implementation of the grid-computing edition of GS is described in the following section to further extend the computational capability of InterPSS.

Section 2 will explain the inherent gridifiability of GS, which will be the basis of the entire document’s discussion. Section 3 gives a primary network partitioning algorithm used to split the calculated electrical power network into feasible sub-networks considering of the topologies of both the electrical power network and the computing grid. The result of this partitioning algorithm is a list of InterPSS network objects[w1] , which can be serialized and distributed to corresponding computing nodes. Section 4 and 5 discuss the realization of the grid-enabled GS, verified with several case studies. Section 6 concludes finally.

2. Analysis of the Gauss-Seidel Algorithm

2.1.Basic idea of Gauss-Seidel Algorithm[2]

Suppose Yn is the admittance matrix of the electrical power network without the swing bus and its adjacent branches, then the following equation can be drawn:

where Un and In are the node voltage vector and node inject current vector correspondingly, Vs is the voltage of the swing bus, Ys is the admittance matrix part related with the swing bus. The current variable can be eliminated by

Express Yn as follow with a diagonal matrix D, a strictly upper triangular matrix U and a strictly lower triangular matrix L:

(3)

then

The iteration format of the voltages considering of the relationship between current and power would be

The main improvement of Gauss-Seidel algorithm than traditional Gauss algorithm is that new information can be utilized immediately, as shown in Equation 5.

2.2. Local information requirements and inherent gridifiability

GS is usually considered poor convergence property, means that more iterations than Newton-Raphson algorithm (NR) are required to get the final result. However, GS is much easier to be gridified than NR, which will counteract this shortage and enhance the power flow solver dramatically.

As mentioned before, the gridifiability of an algorithm depends on the possibility of splitting the whole algorithm into (a).similar (b).independent sub-tasks. The two requirements can be termed as local information requirements, since no macroscopic information is needed at all. One can see clearly from Equation 5 that these two requirements can be fulfilled inherently, explained in the follow:

(a). Similarity

Voltages for all the buses except the swing bus have the same expression. In fact, to calculate the voltage of a certain bus i, only the voltages of those buses adjacent to bus i (means that

One can imagine a computing grid with the same number of computing nodes, each node’s duty is to calculate the voltage of its corresponding bus iteratively. Notice that this is a parallel approach, say, all the computing nodes can execute simultaneously, thus Equation 5 can be further simplified. This implementation can be generalized in Section 3, where each computing node contains a sub-network other than a single bus.

(b). Independence

Since the topology of the computing grid might be changed dynamically, the robustness of the algorithm should be emphasized. At least, the algorithm should be able to execute whenever there is temporary information congestion.

As discussed before, only local information is required for each computing nodes in GS. That is to say, only boundary information of a certain sub-network is useful to other sub-networks. However, the computing job within the node will be halt when abnormal things happened inside it, while other computing jobs related to the halt job may use the fixed information before the halt happened and continue to iterate without any modification of their own jobs. From this point of view, the computing jobs generated by the gridified Gauss-Seidel algorithm are really independent with each other.

3. Network Partitioning

The kernel task of the gridified Gaussian Seidel algorithm is how to partition the electrical power network dynamically with the detailed information of the topologies of both the power system and the computing grid. After that, one can send each sub-networks (as an InterPSS network object) to its corresponding computing node, thus the load flow algorithm can be implemented with the already-defined load flow algorithm by InterPSS within each computing node, what the gridified algorithm has to do is to coordinate the boundary information among those computing nodes.

Since each node can communicate with all the other nodes equally, the gridgain-enabled computing grid can be treated as a complete graph, then only the scale of the computing grid will be influential.

3.1. Simple serial Method

3.1.1. Idea explained by a simple case

The partitioning algorithm can be explained briefly as follow:

a. Calculate the total computation amount of the entire graph;

b. Calculate the computation amount of each computing node (approximately, suppose that the node number n is known);

c. Generate first n-1 sub-graphs by breadth-first search:

c.1. Select the first vertex of the remained graph to be the seed of the generating sub-graph;

c.2. Iterate until the scale of the generating sub-graph is large enough:

c.2.1. Select the first vertex breadth-firstly and attatch it and the corresponding edge to the generating sub-graph;

c.2.2. If the remained graph is disconnected, attach the smallest part to the generating sub-graph;

d. Generate the n-th (the last) sub-graph with the remained graph.

The algorithm can be explained in detail with the simple 5-bus system, shown in Figure 1.

Figure 1. 5-bus system

The original electrical power system can be abstracted as the graph in Figure 2. There are 5 vertices and 5 edges in the graph, thus total computing amount is 10.

Figure 2. Original graph (abstracted from the real electrical power system)

2 computing nodes

The original graph should be split into 2 parts, thus the computing amount (CA) of each computing node is 10/2=5. The partitioning steps are described with the following figures.

a) Node 1 is selected as the seed of the generating sub-graph. CA=1<5

b) According to the breadth-first rule, node 2 is selected as the new node to be added to the generating sub-graph, the edge between node 1 and node 2 is also added to the same sub-graph. CA=3<5

c) According to the breadth-first rule, node 3 is selected as the new node to be added to the generating sub-graph, the edge between node 1 and node 3 is also added to the same sub-graph. CA=5. The first sub-graph is generated.

d) Since the first n-1=1 sub-graph has been generated, the remain graph will be treated as the 2nd sub-graph. The final result is

3 computing nodes

The original graph should be split into 3 parts, thus the computing amount (CA) of each computing node is int(10/3)=3. The partitioning steps are described with the following figures.

a) Node 1 is selected as the seed of the first generating sub-graph. CA=1<3

b) According to the breadth-first rule, node 2 is selected as the new node to be added to the generating sub-graph, the edge between node 1 and node 2 is also added to the same sub-graph. CA=3, the first sub-graph is generated.

c) Node 1 is selected as the seed of the second generating sub-graph. CA=1<3

d) According to the breadth-first rule, node 3 is selected as the new node to be added to the generating sub-graph, the edge between node 1 and node 3 is also added to the same sub-graph. CA=3, the second sub-graph is generated.

e) Since the first n-1=2 sub-graphs have been generated, the remain graph will be treated as the 3rd sub-graph. The final result is

4 computing nodes

The original graph should be split into 4 parts, thus the computing amount (CA) of each computing node is int(10/4)=2. The partitioning steps are described with the following figures.

a) Node 1 is selected as the seed of the first generating sub-graph. CA=1<2

c) Node 1 is selected as the seed of the second generating sub-graph. CA=1<3

e) Node 2 is selected as the seed of the third generating sub-graph. CA=1<3

f) According to the breadth-first rule, node 3 is selected as the new node to be added to the generating sub-graph, the edge between node 2 and node 3 is also added to the same sub-graph. CA=3, the third sub-graph is generated.

g) Since the remained graph is not connected, the smallest part will be attached to the generating sub-graph. However, both of the two parts are with the same scale, so the part with smaller index will be attached, thus the third sub-graph will be

h) Since the first n-1=3 sub-graphs have been generated, the remain graph will be treated as the 4th sub-graph. The final result is

3.2. Simplified greedy graph growing partitioning method

3.2.1. Idea explained by a simple case

The partitioning algorithm can be explained briefly as follow (suppose there are n computing nodes in the grid):

a. Select the first n vertice with highest degree as the seeds of the n sub-graph, delete the n vertice from the vertice list;

b. Expand the n sub-graph synchronously until the vertice list is empty, for each sub-graph do the follow step when growing:

b.1. Find the first vertex fulfill the following conditions: 1) connected to current sub-graph, 2) with lowest degree, 3) found breadth-firstly;.

b.2. Connect the vertex found in b.1. to current sub-graph;

b.3. Connect all the edges interlinking the sub-graph and the new found vertex;

c. Delete all the edges of the n sub-graphs from the original graph;

d. Add all the remaining edges to the n sub-graphs:

d.1. Find the two sub-graphs that contain the two terminals of a certain edge;

d.2. Add the edge and another terminal vertex to the smaller sub-graph found in d.1. (to make the scales of the n sub-graphs as close as possible).

3.2.2. Case Study

// TODO

3.3.Discussion

One may be afraid that the generated sub-networks may be not suitable for power flow calculations. For example, the electrical power may be quite unbalanced in the sub-network, which usually means that the power flow can hardly converge. However, this problem can be solved by handling the boundary nodes carefully, which will be discussed in detail in Section 4.2. Furthermore, in fact the power flow of each sub-network need not to be converged for the grid-computing algorithm, since the essential goal of the algorithm is to get the power flow solution of the entire power system, not part of the system, say, the sub-networks.

3.4.Extensibility

// TODO: Currently the graph to be partitioned is without any weight, a real application should consider of different computing consumptions as weights of a graph. Leaved to be finished in the future.

4. Distributing Computing Jobs

4.1.Generate InterPSS computing job

4.1.1. Output of the graph-partitioning algorithm

The graph-partitioning algorithm uses JGraphT package[3] to handle issues related with graph objects, such as adding/removing vertices/edges to a graph, connectivity verification of an exist graph, etc.. An advanced function of JGraphT package is the ability to export a graph object into GML[4] format. An example of a generated GML string is shown as follow:

<?xml version="1.0" encoding="UTF-8"?>

</node>

</node>

</node>

</node>

</node>

</node>

</node>

</node>

</node>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</edge>

</graph>

</graphml>

The above GML string is generated when the IEEE 14-bus network is partitioned into 2 parts. The tags of all the vertices are the same with corresponding bus IDs in the original InterPSS object. A convenient conversion from such GML string to InterPSS object can be implemented intuitively by the help of ODM[w5] .

4.1.2. Definition of InterPSS computing job

// TODO: Leave to Mike

4.1.3. Conversion from generated GML to serialized InterPSS computing job

//TODO: Leave to Mike

4.2.Handling boundary information

As mentioned before, the computing job for a certain sub-network will communicate with its adjacent sub-networks, thus boundary information between the sub-networks would be required. In fact, the boundary information should be included in any sub-network, while a certain boundary information object should have the information of the two intersecting sub-networks, as shown in the following figure.

Figure 3. Modeling boundary information

A boundary set actually only include the BusIDs of those buses that located in both of the two sub-networks, so it can be easily attached to the serialized computing jobs for further purpose.

4.3.Generating computing jobs

4.3.1. Overview

There are two ways to generate computing jobs by InterPSS, named master node job creation and remote node job creation, respectively[5]. Since a single GS iteration is very fast, most of the computing time is paid for partitioning the network as well as serializing and de-serializing calculation tasks. In this condition, it will be much efficient to generate the computing jobs on remote nodes[w6] , while the base/parent network is only sent to each slave node once.

4.3.2. Detailed distributed computing jobs to be serialized

A distributed GS computing job should includes the following information:

1) An electrical power system object corresponding to the part of the original power system described by the sub-graph, InterPSS can initialize a GS-algorithm object with this sub-system object;

2) A set of boundarySets, each boundarySet are including:

2.1) two IDs of computing nodes that handling two adjacent sub-system object in 1),

2.2) the intersection of busIDs of the two sub-system objects and

2.3) voltage magnitudes and angles for all the members in the intersection (notice that such voltages should be updated and be invoked by other sub-systems via the intersection);

4.3.3. Serialization of the computing job

// TODO

4.4.Implementation of computing jobs

4.4.1. Diagram of Grid-enabled Gauss-Seidel Algorithm

Traditional Gauss-Seidel Algorithm can be illustrated in Figure 4. One can see that the update in each iteration uses much less information (comparing with Newton-Raphson algorithm), that is why GS algorithm is usually considered as “poor convergence”. However, the totally sequential calculation can be flattened with the grid-enabled Gauss-Seidel Algorithm, shown in Figure 5.

Figure 4. Traditional Gauss-Seidel Algorithm

Figure 5. Grid-enabled Gauss-Seidel algorithm

The grid-enabled Gauss-Seidel algorithm will improve the convergence observably for the following two sakes: (1). The scale of each sub-network is much smaller than the original one, thus the consuming time for each iteration is reduced; (2). Information used to update voltages and inject powers is more than the traditional algorithm, since all the boundary nodes are related, while only buses with smaller numbers than current bus are used for updating in the traditional algorithm.

4.4.2. Single-step iteration of Traditional Gauss-Seidel Algorithm

// Stopped here

4.4.3. Sharing and updating boundary information

4.4.3.1. Updating boundary voltages

// TODO

4.4.3.2. Adjusting boundary injected power

Suppose the original power network is partitioned into two parts, shown in Figure 6. (It can be directly generalized to arbitrary number of partitions).

Figure 5. Partitioned networks and the boundary conditions

In figure 1, is the final converged voltage of a certain boundary bus, P and Q are injected active power and reactive power correspondingly at the same bus. The injected powers should be separated into two parts, when individual load flow calculations are implemented in the two sub-networks. However, the final load separating pattern should be as shown in Figure 7 where

, .

Figure 6. Load separating pattern

The target of the load separating pattern is to get the same converged voltage value in the two sub-networks, thus load flow equations in the two sub-networks can be written as

(4)

Please notice that only the relationship between the injected boundary power and boundary voltage of the converged load flow is considered here, thus the 4 variables can be calculated by equation (1). However, a load injection adjusting strategy should be used to make the algorithm applicable. To realize this goal, an initial load separating pattern should be drawn reasonably, say, each sub-network shares half of the original load power. Then the load separating pattern should be adjusted slightly considering of the imbalanced power after each iteration step. A Newton-style modification is proposed as follow:

(5)

One can easily find that is nothing but the mismatches of powers after current iteration step, while the coefficient matrix can be easily calculated that

where i and j are the index of the boundary bus in both of the two sub-networks, means the i-th diagonal element of the sub matrix H of the normal Jacobi matrix with current load flow solution of sub-network 1, where the elements of H are with the expression that

. The sub-matrices H, N, M and L are most common variables for any load flow calculation based on Newton-Laphson algorithm.

Since equation (5) is only a 4-variable linear equation, it can be solved with very small amount of additional computational time. Thus the two new injected powers after current iteration step can be calculated as

(6)

The above discussion assumes that the boundary bus is a PQ bus. If it is a PV bus, the equations and variables related with reactive power and voltage magnitude can be omitted, and then the correction equation (2) is degraded as

(7)

while the modification of the two injected active powers can be formulated as

(8)

Such calculations can be omitted directly if the boundary bus is a slack bus.

4.4.4. Convergence

// Discussion of possible fault of the computing grid

5. Result output

// TODO

6. Conclusion

// TODO

[1] Guanji Hou, Yao Zhang, Zhigang Wu, Michael Zhou, Xiaochuan Luo, A New Power System Grid Computing Platform Based on Internet Open Sources, 电力系统自动化, 200x

[2] Boming Zhang, Shousun Chen, Advanced Electrical Power Network Analysis, 清华大学出版社, 1996

[3] www.jgrapht.org

[4] GraphML is a comprehensive and easy-to-use file format for graphs. It consists of a language core to describe the structural properties of a graph and a flexible extension mechanism to add application-specific data. It is based on XML and hence ideally suited as a common denominator for all kinds of services generating, archiving, or processing graphs. (From http://graphml.graphdrawing.org/)

[5] http://sites.google.com/a/interpss.org/interpss/Home/grid-computing/grid-computing-overview

[w1]To Mike: a list of serialized xml strings?

[w2]To Mike: a serialized XML string?

[w3]That is to say, remote node job creation other than master node job creation.

[w4]Already been done, but need time to illustrate.

[w5]To Mike: Am I correct?

[w6]To Mike: how to do that?