PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
ESCUELA DE INGENIERIA
SIMULACION DE TRANSITORIOS
ELECTROMECANICOS
EN SISTEMAS ELECTRICOS DE POTENCIA
MEDIANTE PROCESAMIENTO PARALELO
FELIPE ALFONSO MORALES SILVA
Tesis para optar al Grado de
Magister en Ciencias de la Ingenier��a.
Supervisores:
HUGH RUDNICK V. D. W.
ALDO CIPRIANO Z.
Santiago de Chile, 1999
PONTIFICIA UNIVERSIDAD CATOLICA DE CHILE
ESCUELA DE INGENIERIA
Departamento de Ingenier��a El�ectrica
SIMULACION DE TRANSITORIOS
ELECTROMECANICOS
EN SISTEMAS ELECTRICOS DE POTENCIA
MEDIANTE PROCESAMIENTO PARALELO
FELIPE ALFONSO MORALES SILVA
Tesis presentada a la Comisi�on integrada por los profesores:
HUGH RUDNICK V. D. W.
ALDO CIPRIANO Z.
HECTOR PE~NA M.
CELSO GONZALEZ G.
PATRICIO DEL SOL G.
para completar las exigencias del grado de
Magister en Ciencias de la Ingenier��a.
Santiago de Chile, 1999
A mi familia
ii
AGRADECIMIENTOS
Quiero agradecer a mis padres por su apoyo y comprensi�on, y destacar el
sacri�cio que han realizado para costear mi educaci�on.
Tambi�en quiero agradecer, de manera especial y muy sinceramente, la
con�anza y el apoyo recibido de mi tutor el Pr. Dr. Hugh Rudnick y del Pr. Dr.
Aldo Cipriano, quienes me guiaron en mi formaci�on profesional y humana durante
mi estad��a en el Programa de Magister.
A los Prs. Dr. Joaqu��n Astorga y Dr. Hector Pe~na, de la Universidad
Cat�olica de Valpara��so, quienes recomendaron mi ingreso al programa y continuaron
orient�andome.
A los Prs. Dr. Luis Rouco del Instituto de Investigaci�on Tecnol�ogica
de Madrid, Dr. Leonardo P�aucar en la Universidad de Campinas, Dr. Djalma
Falc~ao de la Universidad Federal de Rio de Janeiro y Dr. Jo~ao Tom�e Saraiva del
Instituto de Engenharia de Sistemas e Computadores de Oporto, por su atenci�on
durante las estad��as de investigaci�on �nanciadas a trav�es del Proyecto CYTED VII.7,
\Tecnolog��as Emergentes en Sistemas El�ectricos".
A la Comunidad Europea, a trav�es del Proyecto \Parallel Computing and
Dynamic Optimization", que �nanci�o la adquisici�on del computador paralelo.
A Fondecyt y a la Unidad de Investigaci�on y Desarrollo de ENDESA en
la Universidad Cat�olica de Chile.
A Tamara Reyes, Doris S�aez, Ren�e Vidal y Juan Zolezzi, de quienes he
recibido mucha amistad y ayuda.
Felipe A. Morales S.
Santiago, Marzo de 1999
iii
INDICE GENERAL
P�ag.
DEDICATORIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
AGRADECIMIENTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
INDICE GENERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
INDICE DE TABLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
INDICE DE FIGURAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
RESUMEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
I. INTRODUCCION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Simulaci�on de Fen�omenos Transitorios . . . . . . . . . . . . . . . . 1
1.2 Motivaci�on, Objetivos y Alcances del Trabajo . . . . . . . . . . . . 6
1.3 Organizaci�on de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . 8
II. NOCIONES DE PROCESAMIENTO PARALELO Y APLICACIONES
EN SISTEMAS ELECTRICOS DE POTENCIA . . . . . . . . . . . . . 10
2.1 Nociones de Procesamiento Paralelo . . . . . . . . . . . . . . . . . 11
2.1.1 Caracter��sticas de las arquitecturas para procesamiento pa-
ralelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Arquitecturas para procesamiento paralelo . . . . . . . . . 14
2.1.3 Modelos e ��ndices de desempe~no . . . . . . . . . . . . . . . 17
2.2 Aplicaciones del Procesamiento Paralelo en Sistemas El�ectricos de
Potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Aplicaciones en el an�alisis de sistemas el�ectricos de potencia 21
2.2.2 Aplicaciones potenciales del procesamiento paralelo . . . . . 37
2.2.3 Implementaciones en la industria el�ectrica . . . . . . . . . . 43
III. REPRESENTACION DEL SISTEMA . . . . . . . . . . . . . . . . . . . 47
iv
3.1 Introducci�on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Modelaci�on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 Modelo del generador s��ncrono . . . . . . . . . . . . . . . . 49
3.2.2 Modelo del sistema de excitaci�on . . . . . . . . . . . . . . . 52
3.2.3 Modelo del estabilizador del sistema de potencia . . . . . . 54
3.2.4 Modelo de la turbina y el regulador de velocidad . . . . . . 55
3.2.5 Modelo de las unidades generadoras . . . . . . . . . . . . . 56
3.2.6 Modelo del sistema de transmisi�on y los consumos . . . . . 60
3.2.7 Modelo multim�aquinas . . . . . . . . . . . . . . . . . . . . 64
IV. SIMULACION DE TRANSITORIOS ELECTROMECANICOS Y FOR-
MULACION DE UNA SOLUCION PARALELA . . . . . . . . . . . . . 70
4.1 Introducci�on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Procesamiento Paralelo en la Simulaci�on de Transitorios Electro-
mec�anicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2.1 Alternativas para formular el problema de la simulaci�on de
transitorios electromec�anicos . . . . . . . . . . . . . . . . . 72
4.2.2 Aplicaciones del procesamiento paralelo en la simulaci�on de
transitorios electromec�anicos . . . . . . . . . . . . . . . . . 75
4.3 Formulaci�on y Desarrollo de la Estrategia de Paralelizaci�on . . . . 102
4.3.1 Estrategia de paralelizaci�on . . . . . . . . . . . . . . . . . . 103
4.3.2 M�etodos utilizados en el desarrollo de la estrategia . . . . . 107
4.3.3 Realizaci�on del m�etodo en un multicomputador . . . . . . . 114
V. ESTUDIOS DE SIMULACION Y CONCLUSIONES . . . . . . . . . . . 117
5.1 Estudios de Simulaci�on Paralela . . . . . . . . . . . . . . . . . . . 117
5.1.1 Evaluaci�on de la simulaci�on basada en el concepto de para-
lelizaci�on temporal acoplada . . . . . . . . . . . . . . . . . 121
5.1.2 Evaluaci�on de los m�etodos utilizados para el desarrollo de
la estrategia de paralelizaci�on . . . . . . . . . . . . . . . . . 122
5.1.3 Evaluaci�on del m�etodo de Newton Maclaurin en simulacio-
nes paso a paso . . . . . . . . . . . . . . . . . . . . . . . . 127
5.1.4 Evaluaci�on del m�etodo de Newton Maclaurin en problemas
de dimensi�on elevada: simulaciones del SIC basadas en el
concepto de paralelizaci�on temporal acoplada . . . . . . . . 134
v
5.2 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
BIBLIOGRAFIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
ANEXOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
ANEXO A: Nociones Acerca de la Teor��a de Grafos . . . . . . . . . . . . . . . 155
A.1 Notaci�on y De�niciones Generales . . . . . . . . . . . . . . . . . . 155
A.2 Aplicaci�on en la Obtenci�on de una Descomposici�on � Balanceada . 156
ANEXO B: Descripci�on y Utilizaci�on del Multicomputador . . . . . . . . . . . 159
B.1 Descripci�on del Multicomputador . . . . . . . . . . . . . . . . . . . 159
B.2 Ejecuci�on de Programas y Partici�on del Multicomputador . . . . . 160
ANEXO C: Construcci�on del Programa de Simulaci�on en Lenguaje C . . . . . 162
C.1 T�ecnicas de Programaci�on Basadas en Lenguaje C . . . . . . . . . 162
C.1.1 Programaci�on estructurada basada en subrutinas y directi-
vas #include . . . . . . . . . . . . . . . . . . . . . . . . . . 162
C.1.2 Utilizaci�on de punteros . . . . . . . . . . . . . . . . . . . . 163
C.1.3 Asignaci�on de memoria din�amica . . . . . . . . . . . . . . . 164
C.1.4 Utilizaci�on de estructuras de datos . . . . . . . . . . . . . . 164
C.2 Intercomunicaci�on de Procesadores . . . . . . . . . . . . . . . . . . 165
ANEXO D: Datos del Sistema de Prueba IEEE300 . . . . . . . . . . . . . . . 168
vi
INDICE DE TABLAS
P�ag.
5.1 Caracter��sticas de la representaci�on utilizada para el SIC (A~no 1992) . . 119
5.2 Niveles de tensi�on considerados en la representaci�on SIC . . . . . . . . . 120
5.3 Caracter��sticas de operaci�on de las unidades generadoras representadas
din�amicamente en el modelo del SIC . . . . . . . . . . . . . . . . . . . . 120
5.4 Normas para evaluar la convergencia del m�etodo de Newton-Maclaurin . 123
5.5 Dispositivos eliminados para obtener una descomposici�on en dos bloques
(el n�umero entre par�entesis es el n�umero de dispositivos en paralelo) . . 126
5.6 Balance de los bloques y tiempos requeridos para una etapa de inversi�on
bifactorizada t��pica sobre cuatro procesadores (no incluye substituci�on) . 127
5.7 Caracter��sticas generales del sistema de prueba IEEE300 . . . . . . . . . 132
5.8 Iteraciones requeridas para convergencia de la simulaci�on paso a paso en
funci�on del n�umero de procesadores. Estudio de simulaci�on del sistema
de prueba IEEE300 mediante un multicomputador . . . . . . . . . . . . 134
5.9 Resumen con las caracter��sticas del estudio de simulaci�on basado en el
concepto de paralelizaci�on temporal acoplada . . . . . . . . . . . . . . . 135
B.1 Caracter��sticas t�ecnicas del multicomputador Parsytec PowerXplorer . . 160
B.2 Particiones actuales del multicomputador Parsytec PowerXplorer . . . . 161
D.1 Par�ametros din�amicos utilizados en las simulaciones del sistema de prue-
ba IEEE300 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
D.1 Par�ametros din�amicos utilizados en las simulaciones del sistema de prue-
ba IEEE300 (Continuaci�on) . . . . . . . . . . . . . . . . . . . . . . . . . 169
vii
INDICE DE FIGURAS
P�ag.
1.1 Clasi�caci�on de los tipos de estabilidad . . . . . . . . . . . . . . . . . . 3
1.2 Sistemas y lazos de control en un sistema el�ectrico de potencia . . . . . 4
1.3 Ventana temporal y banda de frecuencia de los fen�omenos din�amicos en
un sistema el�ectrico de potencia . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Contenido de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1 Sistema de intercomunicaci�on de procesadores basado en interruptores . 13
2.2 Red de interconexi�on para procesadores dotados de su propia memoria
local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Arquitecturas de computaci�on paralela basadas en dise~nos h��bridos . . . 14
2.4 Modelo DAG para la operaci�on 2p�x exp(x) . . . . . . . . . . . . . . . 18
2.5 Alternativas para la soluci�on paralela del problema algebraico lineal . . 23
2.6 Matrices especialmente reestructuradas para procesamiento paralelo . . 25
2.7 Modelo utilizado para representar una l��nea de transmisi�on en estudios
de simulaci�on de transtorios electromagn�eticos . . . . . . . . . . . . . . 28
2.8 Diagrama de ujo para la simulaci�on paralela de transitorios electro-
magn�eticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.9 Diagrama de ujo del m�etodo de la TEF para evaluaci�on de la seguridad
din�amica mediante computadores paralelos . . . . . . . . . . . . . . . . 31
2.10 Diagrama de ujo de la versi�on paralela del m�odulo para an�alisis de la
estabilidad de tensi�on EVARISTE . . . . . . . . . . . . . . . . . . . . . 35
2.11 Diagrama de ujo de la versi�on paralela del m�odulo de plani�caci�on
MEXICO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.12 Con�guraci�on de un sistema de procesamiento descentralizado para un
centro de control local . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.13 Herramienta computacional de sistemas el�ectricos de potencia para el
futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.14 Simulador digital en tiempo real . . . . . . . . . . . . . . . . . . . . . . 44
2.15 Prueba en lazo cerrado de un rel�e f��sico . . . . . . . . . . . . . . . . . . 45
3.1 Estructura del modelo utilizado para an�alisis de transitorios electro-
mec�anicos en sistemas el�ectricos de potencia . . . . . . . . . . . . . . . 47
viii
3.2 Representaci�on gr�a�ca de los circuitos en el estator y rotor de una m�aqui-
na s��ncrona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 Marcos de referencia utilizados en la de�nici�on de variables del sistema . 50
3.4 Diagrama de bloques del sistema de excitaci�on y el transductor de tensi�on 53
3.5 Diagrama de bloques del estabilizador del sistema de potencia . . . . . . 54
3.6 Diagrama de bloques de la unidad hidr�aulica . . . . . . . . . . . . . . . 56
3.7 Circuito � equivalente de una l��nea de transmisi�on . . . . . . . . . . . . 61
3.8 Representaci�on de un transformador desfasador . . . . . . . . . . . . . . 61
3.9 Representaci�on de los consumos . . . . . . . . . . . . . . . . . . . . . . 63
4.1 Representaci�on pict�orica de un sistema el�ectrico de potencia . . . . . . . 74
4.2 Alternativas para formular el problema de simulaci�on de transitorios
electromec�anicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Diagrama en bloques para el sistema no lineal representado por la ecua-
ci�on de oscilaci�on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4 Diagrama de ujo del algoritmo de relajaci�on funcional para simulaci�on
mediante computadores paralelos . . . . . . . . . . . . . . . . . . . . . . 80
4.5 Representaci�on de la simulaci�on paralela utilizando el concepto de para-
lelizaci�on temporal en su forma desacoplada . . . . . . . . . . . . . . . . 93
4.6 Secuencia de operaciones paralelas para los esquemas basados en la re-
lajaci�on del m�etodo de Newton . . . . . . . . . . . . . . . . . . . . . . . 95
4.7 Una topolog��a toroidal t��picamente utilizada para la simulaci�on basada
en el paralelismo temporal y espacial (16 nodos: 4 en el espacio y 4 en
el tiempo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.8 Recursos utilizados para la simulaci�on basada en el m�etodo de Picard
Desplazado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.9 Diagrama de ujo para la simulaci�on de transitorios electromec�anicos
mediante el multicomputador Parsytec PowerXplorer . . . . . . . . . . . 115
5.1 Tiempo CPU por etapa de la simulaci�on v=s n�umero de pasos integrados
simult�aneamente. Estudio de simulaci�on del SIC mediante un multicom-
putador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.2 Descomposiciones del Jacobiano para procesamiento paralelo. Estudio
de simulaci�on del SIC mediante un multicomputador . . . . . . . . . . . 124
ix
5.3 Grupos de unidades generadoras obtenidos mediante la Descomposici�on �
Balanceada. Estudio de simulaci�on del SIC mediante un multicomputador125
5.4 Ganancia de velocidad como una funci�on de los t�erminos de la serie de
Maclaurin. Estudio de simulaci�on del SIC mediante un multicomputador 128
5.5 Indices de desempe~no para la simulaci�on paso a paso como una funci�on
del n�umero de procesadores. Estudio de simulaci�on del SIC mediante un
multicomputador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.6 N�umero de iteraciones requeridas para la convergencia como una funci�on
de los t�erminos de la serie de Maclaurin. Estudio de simulaci�on del SIC
mediante un multicomputador . . . . . . . . . . . . . . . . . . . . . . . 130
5.7 Indices de desempe~no para la simulaci�on paso a paso como una funci�on
del n�umero de procesadores. Estudio de simulaci�on del sistema de prueba
IEEE300 mediante un multicomputador . . . . . . . . . . . . . . . . . . 133
5.8 Indices de desempe~no para la simulaci�on basada en el concepto de pa-
ralelizaci�on temporal acoplada. Estudio de simulaci�on del SIC mediante
un multicomputador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
A.1 Matrices utilizadas para representar la aplicaci�on de la teor��a de grafos
en la obtenci�on de una Descomposici�on � . . . . . . . . . . . . . . . . . 157
A.2 Grafos correspondientes a las matrices J1, J2 y J3 . . . . . . . . . . . . 157
A.3 Representaci�on de la inversi�on de la matriz J3 mediante el modelo DAG 158
B.1 Representaci�on gr�a�ca del multicomputador Parsytec PowerXplorer . . 159
x
RESUMEN
En esta Tesis se considera la b�usqueda, desarrollo y prueba de un algorit-
mo adecuado para simular r�apida y e�cientemente transitorios electromec�anicos en
sistemas el�ectricos de potencia mediante un computador paralelo (multicomputador).
El m�etodo de integraci�on seleccionado es la regla trapezoidal. Este, en
conjunto con la soluci�on basada en un m�etodo de Newton modi�cado, con iteracio-
nes caracterizadas por la soluci�on bifactorizada o LU de un conjunto de ecuaciones
lineales cuasivac��o, ha liderado los esquemas de simulaci�on desarrollados para com-
putadores seriales (monoprocesador).
La simulaci�on se formula como un problema algebraico nolineal utilizando
el concepto de paralelizaci�on temporal. La soluci�on concurrente se obtiene descom-
poniendo la matriz Jacobiana como la suma de una matriz bloque diagonal, JD, y una
matriz con los elementos fuera de los bloques diagonales, JO. Entonces, la inversa
del Jacobiano se reescribe como (I+J�1D J0)�1J�1D y, asumiendo que jjJ
�1D JOjj < 1, el
t�ermino (I+J�1D J0)�1 se aproxima por su serie de Maclaurin. Los resultados indican
que la propiedad anterior, la cual es una condici�on su�ciente para la convergencia de
la etapa de inversi�on, permite dirigir la b�usqueda de la descomposici�on.
La Descomposici�on � se utiliza para particionar el Jacobiano mientras se
reduce jjJOjj y el M�etodo del Camino m�as Largo para equilibrar la dimensi�on de
los bloques en JD. Ambos permiten adecuar e�cientemente la estrategia de para-
lelizaci�on propuesta, particularmente en computadores cuya raz�on de velocidad de
procesamiento a comunicaci�on es elevada. El algoritmo se desarrolla casi en su to-
talidad mediante esquemas para tratar matrices cuasivac��as, permitiendo mejorar su
desempe~no y hacer viable la simulaci�on de sistemas de gran escala.
La simulaci�on se incorpor�o en lenguaje C a un computador Parsytec Po-
werXplorer que consta de 8 procesadores PowerPC 601. Se realizan estudios de simu-
laci�on del Sistema Interconectado Central chileno y del sistema de prueba IEEE300
para evaluar las ventajas y desventajas de utilizar el algoritmo paralelo; particular-
mente, en lo que concierne a la reducci�on del tiempo de simulaci�on.
xi
ABSTRACT
This Thesis proposes the search, development and test of a suitable al-
gorithm to simulate fast and e�ciently the electromechanical transients of power
systems on a parallel computer.
The integration method chosen is the trapezoidal rule. This one, together
with the solution based on a modi�ed Newton type method, with iterations charac-
terized by the bifactorized or LU solution of a sparse linear equation set, has been
mostly adopted for serial computer applications.
The simulation is formulated as the nonlinear algebraic problem by using
the time parallelization concept. The concurrent solution is obtained by decomposing
the Jacobian matrix as the addition of a block diagonal matrix, JD, and a matrix
with o� blocks diagonal elements, JO. The Jacobian inverse is re-written as (I +
J�1D J0)�1J�1D and assuming that jjJ
�1D JOjj < 1 the term (I+J
�1D J0)
�1 is approximated
by means of its Maclaurin series. The results show that the above property, which is
a su�ciency condition for the convergence of the inversion stage, orients the search
for the decomposition.
The � Decomposition is used to partition the Jacobian while jjJOjj is
decreased and the Longest Path Scheduling Method to balance the size of the blocks
in JD. These permit to adapt the strategy in an e�cient way, particularly, when it is
incorporated on a coarse grain computer. The algorithm was developed mainly with
sparse matrix schemes, so as to not only improve the performance of the program
but in also making feasible the simulation of large scale systems.
The parallel simulation written in C language was implemented on a
Parsytec computer consisting of eight PowerPC 601 processors. Studies of the Chi-
lean Central Interconnected System (SIC) and the IEEE300 test system are conside-
red to evaluate the advantages and drawbacks in the parallel method, in particular
in relation to the reduction of the simulation time.
xii
1
I. INTRODUCCION
Con el advenimiento de los computadores digitales y el uso de tecnolog��as
cada vez m�as e�cientes, una gran cantidad de los an�alisis realizados por la indus-
tria el�ectrica y los grupos acad�emicos asociados han sido continuamente adaptados
para incluir estudios m�as precisos, con�ables y vers�atiles. Los recursos dirigidos al
desarrollo de herramientas de an�alisis con este tipo de caracter��sticas son enormes
[AF94, Fa96, Rep92, Rud77, Sto79]. Esto no s�olo ha permitido extender la operaci�on
del sistema hacia niveles tecnol�ogicos considerablemente m�as complejos, como lo es
aquella basada en la evaluaci�on de la seguridad y el control en tiempo real, sino que
adem�as ha sido determinante en la evoluci�on hacia un sistema en el cual el bien social
se integra a trav�es del concepto de adaptaci�on econ�omica.
Visto el desarrollo que est�an experimentado los sistemas el�ectricos de po-
tencia, considerando sus nuevas estrategias de regulaci�on y mercado [Rud94], y el
desaf��o que conlleva la operaci�on en condiciones cada vez m�as cercanas a los l��mites
de la estabilidad [Kun94, FV92], el an�alisis de �estos viene a ser considerablemente
m�as dif��cil, requiriendo modelos matem�aticos de elevada complejidad. Esto, sumado
al soporte necesario para implementar algoritmos donde las herramientas de compu-
taci�on convencionales no parecen ser adecuadas, incrementan los requerimientos de
computadores que alcancen un mejor desempe~no.
El procesamiento paralelo, en conjunto con el procesamiento vectorial, el
desarrollo de algoritmos, compiladores, interfaces gr�a�cas y tecnolog��a, entre otros
recursos, constituyen la base de un ambiente computacional e�ciente (HPC: High
Performance Computing). Este tipo de plataforma computacional integrada, cuyo
nivel de desarrollo permite su utilizaci�on con costos relativamente moderados, viene
a ser una de las m�as promisorias en aplicaciones asociadas a los sistemas el�ectricos
modernos [Fa96, Rep92, DFaK96].
1.1 Simulaci�on de Fen�omenos Transitorios
El principal estudio que realiza la industria el�ectrica considerando como
herramienta la simulaci�on de los transitorios electromec�anicos eval�ua la estabilidad
2
angular del sistema frente a perturbaciones de gran magnitud [Sto79]. Tal estudio
presenta un inter�es particular para el �area de la computaci�on e�ciente, dada la poten-
cialidad que �esta presenta para evaluar la seguridad din�amica del sistema en tiempo
real [Fa96]. En un par de aplicaciones se destaca que la utilizaci�on de plataformas
de procesamiento paralelo han permitido alcanzar tal objetivo [TIN+92, CZBT91].
Cuando la simulaci�on est�a dirigida a determinar la seguridad din�amica
del sistema en tiempo real, se hace necesario exponer algunos conceptos que permiten
clari�car las caracter��sticas del problema en cuesti�on. La estabilidad del sistema es
un problema �unico, pero su estudio como tal a�un no es viable; �esto sugiere clasi�car
el problema de acuerdo a consideraciones tales como [Kun94]:
� La naturaleza f��sica de la inestabilidad en cuesti�on;
� la magnitud de la perturbaci�on considerada;
� los dispositivos, procesos y el tiempo que deben ser considerados para evaluar
la estabilidad;
� y el m�etodo seleccionado para determinar y predecir la estabilidad.
En base a un an�alisis como el descrito, y considerando como objetivo el presentar
un medio apropiado y e�ciente para abordar el problema de la estabilidad del siste-
ma, �esta puede ser disgregada en categor��as como las observadas en la Figura 1.1.
En ella, las l��neas segmentadas indican la inexistencia de una clara diferenciaci�on
de los l��mites que caracterizan a uno u otro tipo de estabilidad. Este efecto de su-
perposici�on de problemas viene a ser m�as notorio en la medida que el desarrollo de
algoritmos y plataformas de an�alisis permiten un estudio integrado de estos fen�ome-
nos. Claramente entonces, esta clasi�caci�on surge de la necesidad de acomodar los
estudios del sistema a las herramientas de an�alisis disponibles y en consecuencia,
cuando uno de estos fen�omenos est�a en an�alisis, se debe guardar especial atenci�on a
los efectos que se puedan presentar producto de tal superposici�on.
Habiendo identi�cado algunos de los problemas que se presentan en el
sistema es posible de�nir los alcances del estudio que se desea realizar, y a partir
3
Estabilidad de Tensión
no OscilatoriaInestabilidad
OscilatoriaInestabilidad
ModosLocales Interárea
Modos Modosde Control Torsionales
Modos
Estabilidad de Sistemas Eléctricos de Potencia
Estabilidad de Tensióna Perturbaciones GrandesTransitoria
Estabilidaden Períodos Largos
EstabilidadEstabilidaden Períodos Medios
a Perturbaciones PequeñasEstabilidad
a Perturbación Pequeña
Estabilidad Angular
Estabilidad de Tensión
Figura 1.1: Clasi�caci�on de los tipos de estabilidad
de estos alcances de�nir las limitaciones en la representaci�on del fen�omeno. En con-
secuencia, la utilizaci�on e�ciente de la simulaci�on, u otra herramienta de an�alisis,
requiere de�nir restricciones en lo que respecta a los modelos seleccionados para re-
presentar al sistema, las cuales var��an dependiendo del objetivo del an�alisis y del
tipo de decisi�on requerida. Esto puede lograrse a trav�es de la de�nici�on de subsiste-
mas que agrupen dispositivos y concentran sus efectos sobre el comportamiento del
sistema. La Figura 1.2 muestra un esquema de un sistema el�ectrico de potencia en
el cual se han identi�cado subsistemas y el tipo de control asociado a cada uno de
ellos [AAVN90].
En particular, al considerar la simulaci�on de los transitorios electromec�ani-
cos, el inter�es se concentra en la din�amica de las unidades generadoras y la turbina,
con sus respectivos controles de tensi�on y velocidad. Junto a �estos, la representaci�on
del sistema de transmisi�on y de los consumos es fundamental; la primera para incluir
la interacci�on de las unidades y la segunda para de�nir las condiciones de operaci�on,
4
Generador
Controlde Tensión
Frecuencia
del Sistema
Controlde Velocidad
GeneradaPotencia
en las LíneasFlujos
de Referenciapara el Sistema
Frecuencia
OtrosSistemas
GeneradorasUnidades
Otras
Fuentede Energía
Controlde la Fuentede Energía
Señales de control
de Transmisión
Sistema
Consumos
Centro de Control del Sistema
ωV
para la Generación Deseada
de FlujosAsignación
en las Líneas
Figura 1.2: Sistemas y lazos de control en un sistema el�ectrico de potencia
as�� como para incorporar otras din�amicas de importancia. Sin embargo, la impo-
sibilidad o el exceso de trabajo computacional requerido para obtener simulaciones
que integren otro tipo de transitorios en el sistema, sugiere que la din�amica asociada
a fen�omenos r�apidos, como los electromagn�eticos por ejemplo, no sea incluida. De
igual manera, no se consideran las fuentes de energ��a tales como calderas o reactores
nucleares y las acciones en los centros de control asociadas a fen�omenos temporales
lentos o en baja frecuencia [Kun94, AF94].
A partir del tipo de ecuaciones que representan al problema, principal-
mente en consideraci�on a los par�ametros que generalmente las caracterizan, los tran-
sitorios electromec�anicos, as�� como otros presentes en el sistema el�ectrico de potencia,
pueden caracterizarse por la banda de frecuencia en la que sus efectos son predomi-
nantes. Esta se muestra en la Figura 1.3, de la cual es posible observar que para el
problema electromec�anico el rango de frecuencias de mayor inter�es se concentra en
la banda de frecuencias comprendida entre 0,5 y 10 Hz.
5
seg. 1 hora1 minuto 1 día1 1 mseg. 1 ciclo 1 seg.µ
Sobretensiones debidas a rayos
Balance de carga diario
Tensiones por apertura (cierre) de líneas
Regulacion de flujos en líneas
Dinámicas de períodos largos
10 10 1 10 1010 10 1010 10 10 10
10 10 1 100.1 10 1010 10654310 10 10-6 -5 -4 -3 -2 10210-7
6 5 4 3 2 10 0.1 -2 -3 -4 -5 -6 -7Frecuencia, Hz.
Tiempo, seg.
Estabilidad electromecánica
Resonancia subsíncrona
Figura 1.3: Ventana temporal y banda de frecuencia de los fen�omenos din�amicos en
un sistema el�ectrico de potencia
De�nici�on del problema
La simulaci�on de los transitorios electromec�anicos mediante un computa-
dor paralelo consiste en la soluci�on num�erica de un problema diferencial-algebraico
de valor inicial, en el cual la colaboraci�on y comunicaci�on de los elementos de pro-
cesamiento tiene como �n incrementar la velocidad de dicha soluci�on relativa a la
de su obtenci�on serial (monoprocesador). Esta permite conocer la evoluci�on tem-
poral de un conjunto de variables, previamente de�nido, que resulta de representar
un fen�omeno predeterminado afectando los modos electromec�anicos de las m�aquinas
s��ncronas.
Matem�aticamente, el problema se formula de la siguiente manera:
Considere el conjunto de ecuaciones diferenciales y algebraicas necesario para des-
cribir los transitorios electromec�anicos de un sistema el�ectrico de potencia:
_z = G(z; y)
0 = H(z; y)(1.1)
y las condiciones iniciales z(0) = z0 e y(0) = y0 conocidas. G, el vector de funciones
6
diferenciales, y z, el vector de estado, 2 Rm ; a su vez, H, el vector de funciones
algebraicas, e y, el vector de variables algebraicas, 2 Rn . El objetivo consiste en
conocer la evoluci�on temporal de las variables de inter�es mediante una aproximaci�on
num�erica de la soluci�on de las ecuaciones descritas en 1.1; dicha a ser:
~z�th = ~z(h�t) e ~y�th = ~y(h�t); h = 1; :::; ĥ y ĥ�t = tf ; (1.2)
donde ~z(h�t) e ~y(h�t), para h = 1; : : : ; ĥ, son las aproximaciones discretas respecti-
vas para z(t) e y(t) en el intervalo de tiempo ] 0; tf ]; �t es el paso de integraci�on, el
cual se asume como constante durante el intervalo de simulaci�on, y ĥ es el n�umero de
pasos de integraci�on. Considerando que tal objetivo puede ser alcanzado por un con-
junto de hasta p̂ procesadores de un computador paralelo, el siguiente requerimiento
sobre los tiempos de procesamiento deber��a ser considerado:
Tp < T1; 1 < p � p̂ (1.3)
donde T1 y Tp son, respectivamente, los tiempos requeridos para la soluci�on utilizando
1 y p procesadores de un computador digital. Note que tal requerimiento no es m�as
que una manera formal de representar el deseo de tomar ventaja de una arquitectura
de procesamiento paralelo.
1.2 Motivaci�on, Objetivos y Alcances del Trabajo
El grupo de Autom�atica del Departamento de Ingenier��a El�ectrica de la
Ponti�cia Universidad Cat�olica de Chile cuenta con un computador paralelo Parsytec
PowerXplorer con 8 procesadores y la capacidad de ser escalado. Considerando la
gran cantidad de recursos de investigaci�on dirigidos a la utilizaci�on del procesamiento
paralelo en el an�alisis de los sistemas el�ectricos de potencia, y los bene�cios que �este
puede acarrear, el desarrollo de un trabajo en �el se presenta como una oportunidad
de gran valor. Esto motiv�o la realizaci�on de la Tesis en este campo.
Considerando tal motivaci�on, los objetivos fundamentales del trabajo de-
sarrollado fueron:
7
a) Investigar los m�etodos de simulaci�on paralela propuestos en la literatura; prin-
cipalmente, aquellos planteados para simular los transitorios electromec�anicos
en sistemas el�ectricos de potencia.
b) De�nir una estrategia que permitiese acomodar de manera e�ciente el problema
de la simulaci�on al computador paralelo disponible.
c) Desarrollar la estrategia a trav�es de un programa basado en uno de los lenguajes
disponibles para tal computador.
d) Evaluar el desempe~no de la estrategia propuesta.
e) Dilucidar las ventajas y desventajas tanto en la estrategia como en la aplicaci�on
del procesamiento paralelo al problema de la simulaci�on de los transitorios
electromec�anicos en sistemas el�ectricos de potencia.
A su vez, las restricciones que permitieron acotar los objetivos planteados se concen-
tran principalmente en el desarrollo del programa:
a) La estrategia de paralelizaci�on se plante�o en la etapa de soluci�on de las ecua-
ciones. Como se ver�a posteriormente, esta suposici�on consider�o paralelizar la
etapa m�as compleja y cr��tica de la simulaci�on.
b) La representaci�on del sistema el�ectrico de potencia debi�o realizarse con mo-
delos adecuados para el estudio de los transitorios electromec�anicos. Para tal
efecto, se incluyeron los modelos din�amicos com�unmente m�as utilizados para
representar a los generadores s��ncronos, sistemas de excitaci�on, estabilizadores
del sistema de potencia, turbinas y reguladores de velocidad.
c) El programa se desarroll�o con objetivos acad�emicos; sin embargo, debi�o pre-
sentar caracter��sticas como:
i) Disponibilidad para estudiar sistemas en gran escala, con restricciones
asociadas a la capacidad de memoria (RAM) disponible en el computador.
ii) Escalabilidad, lo que permite la utilizaci�on de tantos procesadores como
de�na el usuario.
8
1.3 Organizaci�on de la Tesis
Habiendo de�nido el problema de simular los transitorios electromec�ani-
cos de un sistema el�ectrico de potencia, y los objetivos y alcances de esta Tesis, el
desarrollo del trabajo se estructur�o seg�un el diagrama presentado en la Figura 1.4
Representación
Esquemas para Solución
de las Ecuacionesde Integración
Métodos
de SimulaciónEstudios
en Sistemas Eléctricos de Potenciapara Procesamiento Paralelo
Plataformas y Modelos
εDescomposición
del Sistema
Electromecánicos
de Sistemas Eléctricos de Potencia
Estado Actual
Newton-MaclaurinMétodo de
Estrategia de paralelización:
de las Aplicaciones en el Area
Conclusiones
Basado en el MétodoAlgoritmo de Balance
del Camino Más Largo
Simulaciónde Transitorios
Figura 1.4: Contenido de la Tesis
En el Cap��tulo II se describen algunas plataformas y un modelo com-
putacional utilizados para realizar procesamiento paralelo en sistemas el�ectricos de
potencia. Posteriormente, se revisa el estado actual de las investigaciones asociadas
a la utilizaci�on del procesamiento paralelo en la soluci�on de problemas que son de
inter�es para la industria el�ectrica.
En el Cap��tulo III se considera la representaci�on del sistema el�ectrico
de potencia. La construcci�on del modelo guarda una relaci�on estrecha con aquella
utilizada por el programa de simulaci�on. Todos los subsistemas se representan en
el espacio estado. El modelo multim�aquinas se obtiene acoplando los submodelos
por unidad generadora e incorporando el modelo del sistema de transmisi�on para
as�� acoplar los modelos de las unidades generadoras.
9
El Cap��tulo IV se disgreg�o en dos secciones. En la primera de �estas se
trata el problema de simular los transitorios electromec�anicos; y en particular, la
obtenci�on de �esta mediante un computador paralelo. Se presentan los esquemas
utilizados para abordar la soluci�on de las ecuaciones y algunos de los m�etodos de in-
tegraci�on sugeridos en la literatura. Posteriormente, en la segunda secci�on, se plantea
la estrategia de paralelizaci�on basada en el m�etodo de Newton-Maclaurin. Se pre-
sentan los fundamentos te�oricos y pr�acticos que determinaron su selecci�on. Adem�as,
se incluye una rese~na con los conceptos fundamentales en torno a la Descomposici�on
� y al algoritmo de balance de carga basado en el M�etodo del Camino m�as Largo,
ambos seleccionados como apropiados para llevar a cabo el desarrollo pr�actico de la
estrategia propuesta.
En el Cap��tulo �nal se presentan los resultados obtenidos de los estudios
de simulaci�on en un modelo simpli�cado del Sistema Interconectado Central chileno
(SIC) y en el sistema de prueba IEEE300. Estos consideran diversidad en el n�umero
de procesadores utilizados para la simulaci�on y en los par�ametros que la de�nen. Este
Cap��tulo se complementa adem�as con comentarios en relaci�on al desempe~no obtenido
con el algoritmo paralelo. Finalmente, se incluyen las conclusiones del trabajo y se
proponen algunos caminos de investigaci�on futura en torno a la utilizaci�on de la
estrategia de paralelizaci�on en otros problemas de inter�es para la industria el�ectrica.
La Tesis incluye una extensa bibliograf��a y diversos anexos que comple-
mentan los t�opicos presentados en la Tesis. Estos incluyen una revisi�on de la teor��a
de grafos, con �enfasis en los conceptos utilizados en el desarrollo de la Tesis, la des-
cripci�on y utilizaci�on del multicomputador Parsytec PowerXplorer, la programaci�on
en Lenguaje C bajo ambiente Parix y los datos utilizados en el estudio del sistema
de prueba IEEE300.
10
II. NOCIONES DE PROCESAMIENTO PARALELO Y APLICA-
CIONES EN SISTEMAS ELECTRICOS DE POTENCIA
La plani�caci�on, el an�alisis de la operaci�on y el dise~no de un sistema
el�ectrico de potencia, entre otras tareas, poseen una complejidad tal que dif��cilmente
podr��an ser realizadas sin la ayuda de computadores. Tanto la viabilidad de estas
tareas como su e�ciencia dependen considerablemente de los recursos computacio-
nales disponibles; por tal motivo, los desarrollos en la tecnolog��a de procesamiento y
los algoritmos de an�alisis juegan un papel preponderante en t�erminos de la calidad
alcanzada en el desempe~no del sistema.
La utilizaci�on de computadores y el dise~no de algoritmos en sistemas
el�ectricos de potencia tiene una larga historia; concretada a trav�es de un sinn�umero de
investigaciones, desarrollos y aplicaciones que han permitido consolidar las bases de
la forma en que actualmente se opera al sistema. La demanda de nuevas tecnolog��as
de procesamiento, como las basadas en las arquitecturas para computaci�on paralela,
y la adecuaci�on de los algoritmos computacionales a estas tecnolog��as, responden
a desaf��os incipientes producto de la complejidad presente hoy en el sistema y a la
imposibilidad de hacer frente a �estos con las herramientas convencionales disponibles.
Los centros de computaci�on e�ciente, las plataformas para la computaci�on paralela o
distribuida, las redes para comunicaci�on local o externa, los sistemas para adquisici�on
de datos y control, las capacidades de procesamiento h��brido basado en tecnolog��as
digitales y an�alogas, las interfaces gr�a�cas y los algoritmos de an�alisis y dise~no son
algunos de los recursos que actualmente concentran la atenci�on por su aplicaci�on
pr�actica en la industria el�ectrica. Por ende, el conocimiento acerca de �estos, as�� como
de su aplicaci�on en las tareas asociadas a un sistema el�ectrico de potencia, es un
aspecto importante que vale la pena tener en consideraci�on.
Este Cap��tulo consta de dos secciones principales, en la primera se tratan
algunos de los conceptos b�asicos asociados al procesamiento paralelo, incluyendo
caracter��sticas, arquitecturas, modelos e ��ndices de desempe~no; posteriormente, en la
secci�on dos, se describen algunas de sus aplicaciones en la soluci�on de los problemas
presentes en un sistema el�ectrico de potencia.
11
2.1 Nociones de Procesamiento Paralelo
Los sistemas de computaci�on paralela y distribuida ofrecen la esperan-
za de dar un salto cuantitativo en la potencialidad computacional, tal que permita
abordar o incrementar la e�ciencia en el estudio de una gran cantidad de proble-
mas. El que tal promesa pueda ser cumplida puede ser objeto de especulaci�on; sin
embargo, la experiencia alcanzada con este tipo de sistemas ha despejado una gran
cantidad de potencialidades y limitaciones cuyo conocimiento puede ser de gran in-
ter�es. El objetivo de est�a secci�on se concentra en proveer las nociones b�asicas acerca
del procesamiento paralelo; se describen par�ametros que permiten caracterizar a una
diversidad de arquitecturas disponibles para procesamiento paralelo, as�� como tam-
bi�en se mencionan algunas de �estas. Adem�as se introducen conceptos b�asicos acerca
de los modelos utilizados para el desarrollo de algoritmos paralelos, y de igual forma
se describen algunos de los ��ndices utilizados para evaluar el desempe~no logrado al
transportar una aplicaci�on a un computador paralelo.
2.1.1 Caracter��sticas de las arquitecturas para procesamiento paralelo
Existe una gran diversidad de arquitecturas que permiten realizar proce-
samiento paralelo. Por lo general, las caracter��sticas entre alg�un par espec���co de
arquitecturas llega a ser tan dis��mil entre s�� que la portabilidad de programas entre
m�aquinas es casi imposible. Sin embargo, la heterogeneidad de arquitecturas ha ju-
gado un papel relevante al momento de buscar un lugar que permita acomodar a la
igualmente diversa gama de problemas presentes en nuestros quehaceres; m�as a�un,
no es dif��cil prever que el �exito en el desempe~no de un algoritmo paralelo depende
de cuan bien se acomoden ambos, arquitectura y algoritmo, al problema. Algunos
par�ametros que podr��an ser de utilidad para reconocer la diversidad de caracter��sticas
presentes en las arquitecturas para procesamiento paralelo son [BT89]:
a) Tipo y n�umero de procesadores. Los sistemas con cientos o miles de pro-
cesadores se denominan \masivamente paralelos". Por el contrario, aquellos
sistemas cuya cantidad de procesadores es relativamente peque~na, pero cada
uno posee una gran capacidad de procesamiento, se denominan \m�aquinas de
12
granularidad gruesa"1. Estas �ultimas caracterizan a los multicomputadores y
multiprocesadores.
b) Presencia o ausencia de un mecanismo de control global. El nivel de con-
trol que tienen los procesadores se caracteriza, por lo general, a trav�es de la
capacidad que �estos tienen o no para ejecutar simult�aneamente operaciones
diferentes. As��, para un instante de tiempo dado, m�aquinas SIMD (Single
Instruction Multiple Data) permiten operar sobre diferentes datos mediante
la misma instrucci�on y m�aquinas MIMD (Multiple Instruction Multiple Data)
permiten operar sobre diferentes datos con diferentes instrucciones.
c) Operaci�on s��ncrona �o as��ncrona. Tal caracter��stica apunta a la presencia o
ausencia de un reloj global com�un utilizado para sincronizar la operaci�on y/o
intercomunicaci�on de los procesadores. Las m�aquinas SIMD son s��ncronas por
de�nici�on. Tal caracter��stica es deseable pese al excesivo trabajo que pueda
requerir tal sincronizaci�on, tanto por las facilidades para el control de los pro-
cesadores como para el dise~no de los algoritmos. Una caracter��stica importante
es que las m�aquinas que operan as��ncronamente tienen la exibilidad de simular
una operaci�on s��ncrona.
d) Interconexi�on de procesadores. En t�erminos del mecanismo por el cual se in-
tercambia la informaci�on entre procesadores, por lo general, suele distinguirse
entre dos alternativas extremas. Estas se conocen como arquitecturas de me-
moria compartida (shared memory) y de intercambio de mensajes (message
passing); adicionalmente, existen dise~nos h��bridos que combinan ambas alter-
nativas.
La primera de estas alternativas utiliza una memoria global compartida accesi-
ble a todos los procesadores. As��, un procesador puede escribir en la memoria
global para que luego otro lea a partir de la misma direcci�on de memoria. El
problema de intercomunicaci�on resuelto de esta manera introduce otro proble-
ma: el acceso simult�aneo de diferentes procesadores a diferentes localizaciones
1Como se sugiere en [Rep92], la granularidad de una arquitectura de procesamiento est�a ca-
racterizada por la raz�on entre una medida de la velocidad de ejecuci�on de instrucciones en cada
procesador (por ejemplo, MIPS: Mega Integers Per Second) y una medida de la velocidad de inter-
comunicaci�on (por ejemplo, baud rate)
13
de memoria. Un sistema basado en interruptores, como el que se muestra a
trav�es de la Figura 2.1, permite resolver tal problema. Naturalmente, la com-
plejidad de tal sistema incrementa con el n�umero de procesadores; situaci�on
que adem�as acarrea tiempos de acceso considerables. Sin embargo, puesto que
el sistema aparece como si todos los procesadores estuviesen directamente co-
nectados entre s��, el dise~no de algoritmos se simpli�ca considerablemente.
ProcesadorProcesador
Procesador
MemoriaMemoria
MemoriaMemoria
Procesador
Interruptor
Figura 2.1: Sistema de intercomunicaci�on de procesadores basado en interruptores
En la segunda alternativa cada procesador cuenta con una memoria local pro-
pia. Tal como se ilustra en la Figura 2.2, el proceso de comunicaci�on se realiza
a trav�es de una red interconectada que consiste en enlaces de comunicaci�on di-
recta entre pares de procesadores. La selecci�on de los procesadores a conectar
es muy importante; la mejor alternativa se presenta si cada procesador pudiese
ser conectado directamente a todos los restantes, pero tal interconexi�on no es
factible. As��, un n�umero excesivo de enlaces incrementa el costo del sistema y
una comunicaci�on mediante un bus compartido presenta un considerable retar-
do cuando el n�umero de procesadores es grande; �esto debido a la necesidad de
contener los mensajes.
Procesador
Procesador
Procesador
Procesador
Memoria
Memoria
Memoria
Memoria
Figura 2.2: Red de interconexi�on para procesadores dotados de su propia memoria
local
14
Procesador
Procesador
Procesador
Procesador
Memoria
(a) Coexistencia de una red punto a punto
con memoria compartida
Procesador ProcesadorProcesadorMemoria Memoria Memoria
Procesador ProcesadorProcesadorMemoria Memoria Memoria
Procesador ProcesadorProcesadorMemoria Memoria Memoria
(b) Grupos de procesadores conectados me-
diante redes intra e intergrupo
Figura 2.3: Arquitecturas de computaci�on paralela basadas en dise~nos h��bridos
Existe un gran n�umero de sistemas que utilizan arquitecturas h��bridas, que
combinan caracter��sticas particulares de cada una de las alternativas anterior-
mente descritas. La Figura 2.3 muestra un par de ejemplos de entre las muchas
combinaciones posibles. A su izquierda se observa una red de conexi�on nodo
a nodo que consta de una memoria compartida; a su vez, a la derecha de la
misma se observan grupos de procesadores donde un bus de comunicaci�on de
alta velocidad sirve de enlace dentro de cada grupo y una red de comunicaci�on
se utiliza para la comunicaci�on entre grupos.
Finalmente, es importante resaltar una diferencia fundamental entre la topo-
log��a de interconexi�on disponible para un sistema de computaci�on paralela y
uno de computaci�on distribuida. Mientras en el primero la red de interconexi�on
est�a bajo control del dise~nador, y por ende es muy regular, en el segundo esta
red est�a predeterminada y usualmente es irregular, como es el caso de las redes
de comunicaci�on de datos habitualmente utilizadas en sistemas de computaci�on
distribuida.
2.1.2 Arquitecturas para procesamiento paralelo
Las capacidades de procesamiento de un monoprocesador, sin desmedro
del incremento substancial alcanzado en los �ultimos a~nos, no son lo su�cientemente
adecuadas para cubrir las demandas que est�an apareciendo en diversos campos de
la ciencia y la ingenier��a. Por tal motivo, la industria computacional ha estado
continuamente desarrollando sistemas que puedan ejecutar las tareas concurrentes de
un programa por medio de computadores paralelos con multiplicidad de tecnolog��as.
15
Habiendo introducido algunos par�ametros generales en torno a la arquitecturas de
procesamiento paralelo, ahora resulta interesante referirse a c�omo se han combinado
estos par�ametros en las arquitecturas disponibles actualmente. Como fue sugerido
en [Fa96], algunas de �estas son:
a) Procesadores superescalares. Son monoprocesadores que permiten la ejecuci�on
simult�anea de m�as de una instrucci�on por ciclo de reloj. Su e�ciencia depende
de la habilidad que tiene el compilador para detectar instrucciones que pue-
den ser ejecutadas en paralelo. Estos procesadores se utilizan en estaciones de
trabajo de desempe~no elevado y en algunos sistemas multiprocesadores. Algu-
nos ejemplos de procesadores escalares son el IBM Power2, DEC Alpha, MIPS
R10000, Intel 80960Hx, etc.
b) Procesadores vectoriales. Son procesadores dise~nados para optimizar la ejecu-
ci�on de las operaciones aritm�eticas en vectores de dimensi�on elevada. Estos
se basan principalmente en arquitecturas que emulan una l��nea de trabajo en
la cual dos o m�as etapas operan en forma simult�anea (pipeline). Muchos de
los tambi�en denominados supercomputadores, como los manufacturados por la
Cray, Fujitsu, IBM, NEC, etc., se basan en procesadores vectoriales poderosos.
c) Multiprocesadores con memoria compartida. Son m�aquinas compuestas de
varios procesadores que se comunican entre s�� a trav�es de una memoria global
compartida por todos los procesadores. Algunas de estas m�aquinas tienen unos
cuantos (2-16) procesadores vectoriales poderosos cuyo acceso a la memoria
se realiza a gran velocidad. Algunos ejemplos de tales arquitecturas son las
familias Cray T90 y J90. Otras, como el SGI Power Challenge, puede tener un
gran n�umero (hasta 32) de procesadores superescalares de menor potencialidad.
d) M�aquinas SIMD masivamente paralelas. Estas m�aquinas est�an compuestas de
cientos o miles de procesadores relativamente simples. Bajo el comando de
una unidad de control central permiten ejecutar, en sincronismo, la misma
instrucci�on sobre conjuntos de datos diferentes (paralelismo a nivel de datos).
e) Multicomputadores con memoria distribuida. Son m�aquinas compuestas por
un conjunto de pares procesador-memoria conectados mediante una red de
comunicaci�on de datos de alta velocidad y cuyo traspaso de informaci�on se
16
realiza mediante intercambio de mensajes. Los procesadores cuentan con una
capacidad de procesamiento relativamente elevada y el n�umero de procesadores
puede llegar a ser grande (2-1024). Debido a la posibilidad de contar con
un n�umero elevado de procesadores, a este tipo de arquitectura tambi�en se
le denomina \masivamente paralelo". Ejemplos de multicomputadores son el
IBM SP-2, Cray T3D/3E, Intel Paragon, Parsytec PowerXplorer, etc.
f) Red heterog�enea de estaciones de trabajo. Esta puede ser utilizada como una
m�aquina paralela virtual que permite resolver problemas concurrentes median-
te el uso de programas, tales como el PVS (Parallel Virtual Machine) y el MPI
(Message Passing Interface), especialmente desarrollados para los efectos de co-
municaci�on y coordinaci�on. En lo que concierne al desarrollo de las aplicacio-
nes, �este sistema computacional es similar a los multicomputadores de memoria
distribuida pero su e�ciencia y con�abilidad es usualmente inferior. Por otro
lado, la oportunidad de utilizar estaciones de trabajos desocupadas como una
m�aquina paralela virtual es atractivo desde el punto de vista econ�omico.
Los desarrollos de aplicaciones sobre las arquitecturas descritas anterior-
mente pueden tener diferentes paradigmas y procedimientos de programaci�on. El
paralelismo puede ser explotado para uno o m�as niveles de granularidad, los cua-
les van desde el nivel de instrucci�on (paralelismo de granularidad �na: �ne grain
parallelism) al nivel de subprograma (paralelismo de granularidad gruesa: coarse
grain parallelism). Los procesadores superescalares y vectoriales, como tambi�en las
m�aquinas SIMD, son m�as adecuados para el paralelismo a nivel de instrucci�on; por
el contrario, las arquitecturas de multiprocesadores y multicomputadores se adaptan
mejor al paralelismo a nivel de subprograma. Este tipo de paralelismo de granula-
ridad gruesa se obtiene al utilizar ya sea la arquitectura de multiprocesadores con
memoria compartida o el paradigma de intercambio de mensajes empleado en multi-
computadores y redes de estaciones de trabajo. El primer modelo se adecua mejor a
programas f�aciles de desarrollar y mantener pero los multiprocesadores de memoria
compartida son generalmente m�as caros y menos escalables que los multicomputa-
dores. Por esta raz�on, los fabricantes de sistemas de computaci�on est�an intentando
desarrollar sistemas operativos inteligentes que permitan emular un ambiente de me-
moria compartida sobre un sistema de memoria f��sicamente distribuida. La detecci�on
17
de paralelismo en el c�odigo se desarrolla principalmente por el programador de la
aplicaci�on; la detecci�on autom�atica de paralelismo a�un es un desaf��o para la compu-
taci�on paralela, excepto en el caso de procesadores superescalares y vectoriales.
2.1.3 Modelos e ��ndices de desempe~no
En muchas �areas de la ciencia se utilizan modelos como un medio de abs-
tracci�on de un sistema particular; igualmente importante resulta ser la de�nici�on de
��ndices que permitan evaluar el desempe~no de tal sistema. El procesamiento paralelo
no es una excepci�on a tales necesidades; aqu�� es posible encontrar una variedad de
modelos para la computaci�on paralela y distribuida, que incorporan diferentes supo-
siciones acerca de la potencialidad individual de cada procesador y del mecanismo
por el cual se trans�ere la informaci�on entre �estos. Considerando que la realizaci�on
pr�actica de la simulaci�on requiere de un modelo para el algoritmo paralelo, al menos
para alguna de las etapas de �esta, a continuaci�on se describen algunos conceptos
b�asicos que permiten caracterizar uno muy simple utilizado para computaci�on para-
lela s��ncrona. De igual manera, se describen los conceptos asociados a los ��ndices de
desempe~no en aplicaciones de tal ��ndole [BT89].
Representaci�on de un algoritmo paralelo mediante un modelo DAG
Las siguientes suposiciones conciernen al modelo en consideraci�on. En lo
que respecta a la funcionalidad de cada procesador, se asume que �estos son capa-
ces de ejecutar ciertas instrucciones elementales, tales como operaciones aritm�eticas
b�asicas, comparaciones, instrucciones anidadas del tipo \if : : : entonces : : : ", etc.; y
que adem�as cuentan con un mecanismo mediante el cual pueden intercambiar infor-
maci�on. En lo que concierne a la potencialidad computacional de cada procesador,
se asume que cada instrucci�on b�asica consume una unidad de tiempo. Finalmente,
en lo que respecta al intercambio de informaci�on, se asume que �esta se trans�ere
instant�aneamente y libre de costo. Bajo tales asunciones, un algoritmo paralelo
puede ser representado mediante un grafo ac��clico dirigido2 (DAG: Directed Acyclic
2Un DAG es un grafo dirigido que no tiene ciclos positivos; es decir, no tiene ciclos que consisten
exclusivamente de arcos hacia adelante.
18
Graph) seg�un se indica a continuaci�on. Los conceptos asociados a la teor��a de grafos,
as�� como la nomenclatura utilizada, se describen en el Anexo A.
Sea G = (N ;A) un DAG, donde N = fn1; : : : ; njNjg es el conjunto
de nodos y A es el conjunto de arcos dirigidos. Cada nodo representa una de las
operaciones realizadas por el algoritmo y los arcos son utilizados para representar la
dependencia de los datos. En particular, un arco (ni; nj) 2 A indica que la operaci�on
correspondiente al nodo nj utiliza el resultado de la operaci�on correspondiente al
nodo ni. Una operaci�on podr��a ser elemental, por ejemplo una operaci�on aritm�etica,
o podr��a ser una operaci�on de alto nivel tal como la ejecuci�on de una subrutina. A
modo de ejemplo, en la Figura 2.4 se muestra el modelo DAG para la operaci�on
matem�atica 2p�x exp(x)
exp( )( ).-
x
( ).
.
2
*
Figura 2.4: Modelo DAG para la operaci�on 2p�x exp(x)
Si xi denota el resultado correspondiente a la operaci�on en el i-�esimo
nodo del DAG, entonces �este puede considerarse como una representaci�on de la
dependencia entre funciones de la forma: xi = fi(f xj = j es un predecesor de i g).
Aqu�� fi es una funci�on que describe la operaci�on correspondiente al nodo ni. Si ni
corresponde a un nodo de entrada, entonces xi no depende de otras variables y es
vista como una variable de entrada externa. As��, la operaci�on correspondiente al
nodo de entrada ni equivale esencialmente a leer la variable de entrada xi y por ende
se asume a consumir un tiempo insigni�cante. S�� N0 denota al conjunto de nodos
que no es de entrada, para alg�un nodo ni 2 N0 se asume que la correspondiente
operaci�on; es decir, la evaluaci�on de la funci�on fi, toma una unidad de tiempo.
19
Tal suposici�on es razonable si cada nodo representa una operaci�on aritm�etica; sin
embargo, en algoritmos m�as complejos los tiempos de ejecuci�on en diferentes nodos
pueden diferir considerablemente.
El DAG es una representaci�on parcial de un algoritmo. Este especi�ca
que operaciones se ejecutar�an, sobre qu�e operandos, e impone ciertas restricciones de
precedencia sobre el orden en que estas operaciones ser�an realizadas. Para describir
completamente un algoritmo paralelo se debe especi�car las operaciones que reali-
zar�a cada procesador y el tiempo en el cual las har�a. Supongamos que se dispone
de un conjunto de p̂ procesadores y que cada procesador es capaz de realizar alguna
de las operaciones deseadas. Para alg�un nodo ni 2 N0, asigne al procesador Pi la
responsabilidad de realizar la tarea correspondiente. Tambi�en, para ni 2 N0, sea ti
una variable entera positiva especi�cando el tiempo para el cual la operaci�on corres-
pondiente al nodo ni se ha completado. No hay procesadores asignados a nodos de
entrada, y por ende ti = 0 para cada nodo de entrada ni. Entonces, se imponen las
siguientes restricciones:
a) Un procesador puede realizar a lo m�as una operaci�on para un tiempo espec���co.
As��, si ni; nj 2 N0, i 6= j, y ti = tj, entonces Pi 6= Pj
b) Si (ni; nj) 2 A, entonces tj � ti +1. Este requerimiento reeja el hecho de que
la operaci�on correspondiente al nodo nj puede comenzar solamente despu�es que
la operaci�on correspondiente al nodo ni ha sido completada.
Una vez que Pi y ti han sido �jados, sujetos a las restricciones anterio-
res, se dice que el DAG ha sido asignado (scheduled) y se denomina al conjunto
f(ni; Pi; ti)jni 2 N0g una asignaci�on (schedule).
Indices de desempe~no
Los siguientes conceptos son �utiles para evaluar el desempe~no que se ob-
tiene al trasladar una aplicaci�on a un computador paralelo [BT89]. En primer lugar
se supone que se ha seleccionado un modelo particular de computaci�on paralela, �este
podr��a ser el DAG previamente considerado u otro modelo. Adem�as, se considera que
20
el problema computacional en cuesti�on puede ser parametrizado por una variable d
que representa el tama~no del problema; por ejemplo, en el modelo DAG, problemas
de diferentes tama~nos corresponden a diferentes n�umeros de variables de entrada.
Supongamos que un algoritmo paralelo utiliza p procesadores (p puede
depender de d, el tama~no del problema) y termina en un tiempo Tp(d). Si T�(d)
denota al tiempo serial �optimo para resolver el mismo problema, es decir, el tiempo
requerido por el mejor posible algoritmo serial (monoprocesador) para este problema,
la raz�on
Sp(d) =T �(d)
Tp(d)(2.1)
se denomina la ganancia de velocidad (speedup) del algoritmo y describe la ventaja
del algoritmo paralelo comparado con el mejor algoritmo serial posible. A su vez, la
raz�on
Ep(d) =Sp(d)
p=
T �(d)
pTp(d)(2.2)
se denomina la e�ciencia del algoritmo y esencialmente mide la fracci�on de tiempo
que un procesador se emplea en forma �util. Idealmente, Sp(d) = p y Ep(d) = 1; en
tal caso, la disponibilidad de p procesadores permite incrementar la velocidad en un
factor igual a p. Para que esta situaci�on se de, el algoritmo paralelo deber��a ser tal
que ning�un procesador se encuentre desocupado o realice trabajos innecesarios, lo
cual es pr�acticamente imposible. Un objetivo m�as realista es aspirar a una e�ciencia
que se mantenga acotada lejos de cero cuando d y p se incrementan.
Las de�niciones anteriores presentan la di�cultad de que el tiempo serial
�optimo T �(d) no es conocido. Por esta raz�on, generalmente T �(d) se de�ne de manera
diferente; algunas de las alternativas son:
a) T �(d) es el tiempo requerido por el mejor algoritmo serial disponible.
b) T �(d) es el tiempo requerido por alg�un algoritmo serial competitivo.
21
c) T �(d) es el tiempo requerido para ejecutar el algoritmo paralelo en cuesti�on en
un procesador. Tal elecci�on de T �(d) permite evaluar e�cientemente cuan bien
se ha paralelizado un algoritmo paralelo particular, pero no provee informa-
ci�on acerca de los m�eritos absolutos del algoritmo, en contraste con la primera
de�nici�on de T �(d).
Puede observarse que si T �(d) se de�ne como en c), y si los algoritmos se
especi�can mediante el modelo DAG, entonces T �(d) coincide con T1(d).
En los inicios de las aplicaciones de la computaci�on paralela, ambos ��ndi-
ces, ganancia de velocidad y e�ciencia, fueron los �unicos utilizados para determinar
la calidad de los algoritmos paralelos. Al aumentar la disponibilidad de m�aquinas
paralelas, y comenzar a desarrollarse las aplicaciones pr�acticas, surgieron otros as-
pectos asociados al problema, como por ejemplo, la raz�on de desempe~no a costo
(Mops/$)3 [Fa96].
2.2 Aplicaciones del Procesamiento Paralelo en Sistemas El�ectricos
de Potencia
El primer objetivo de esta secci�on consiste en describir, en base a una
revisi�on bibliogr�a�ca, algunas de las aplicaciones del procesamiento paralelo en el
an�alisis de los sistemas el�ectricos de potencia. Posteriormente, basado en el trabajo
presentado en [Fa96], se realizar�a una breve rese~na acerca de los problemas en los
que el procesamiento paralelo presenta las mejores perspectivas de utilizaci�on. Fi-
nalmente, con referencia al mismo trabajo, se describen algunos desarrollos llevados
a la industria.
2.2.1 Aplicaciones en el an�alisis de sistemas el�ectricos de potencia
Existe una gran diversidad de aplicaciones concernientes a la utilizaci�on
del procesamiento paralelo en el an�alisis de sistemas el�ectricos de potencia. Las
3Un Mops (Mega oating operations per second) son 106 operaciones en punto otante por
segundo.
22
aplicaciones, por lo general, se motivan m�as por el deseo de incrementar la veloci-
dad de procesamiento que por causas asociadas a la estructura de los problemas.
A excepci�on de los casos en que el estudio implica la obtenci�on de soluciones repe-
tidas, como es el caso del an�alisis de contingencias, no existe un paralelismo obvio
inherente a la estructura matem�atica de los problemas. As��, el recurso usual para
abordarlos requiere de la formulaci�on de un algoritmo en paralelo, cuya e�ciencia
es fuertemente dependiente de cuan bi�en se acomode el algoritmo a la arquitectura
paralela disponible [Rep92].
A continuaci�on se describen algunos de las aplicaciones del procesamiento
paralelo en el an�alisis de sistemas el�ectricos de potencia. El objetivo es dar a conocer
un resumen con los detalles m�as relevantes de estas aplicaciones, principalmente,
en lo que dice relaci�on al objetivo de la aplicaci�on, la estrategia de paralelizaci�on
propuesta y los resultados m�as signi�cativos. El lector que desee profundizar en
�estos y otros detalles, as�� como en otras aplicaciones, puede encontrar referencias a
trabajos de inter�es en la bibliograf��a proporcionada al �nal de esta Tesis.
Soluci�on de ecuaciones algebraicas lineales, cuasivac��as y de gran dimen-
si�on
La soluci�on de ecuaciones algebraicas lineales es un t�opico de inter�es ge-
neral en diversas �areas de la ciencia [GVL89]. En lo que concierne al an�alisis de los
sistemas el�ectricos de potencia, en muchos casos este problema toma caracter��sticas
particulares; siendo la dimensi�on, relativamente elevada, y la representaci�on median-
te matrices cuasivac��as las m�as relevantes.
Considerando que tanto el problema del ujo de potencia como el de
la simulaci�on din�amica, dos de los estudios m�as frecuentemente realizados por la
industria el�ectrica, se formulan generalmente a trav�es de un conjunto de ecuaciones
algebraicas nolineales, y que para su soluci�on el m�etodo com�unmente m�as adoptado
requiere de la soluci�on, entre iteraciones, del problema algebraico lineal4; muchas de
4En el m�etodo de Newton-Raphson, mediante la correcci�on �xk = �(J jxk)�1F (xk), se estima
una soluci�on xk+1 = xk + �xk tal que F (xk+1) t 0. J jxk corresponde a la matriz Jacobiana
evaluada en la soluci�on xk que se conoce a partir de la iteraci�on previa.
23
las investigaciones se concentran en resolver este problema independientemente de
su naturaleza [Com78].
Teniendo en mente las caracter��sticas de dimensi�on elevada y estructura
cuasivac��a mencionadas anteriormente, los esquemas paralelos m�as utilizados para
resolver el problema algebraico lineal, tal como se indica en la Figura 2.5, pueden
dividirse en tres categor��as principales. Adem�as de los m�etodos directos e indirectos,
tambi�en se destacan aquellos que requieren de una etapa previa que reordena y
particiona las matrices envueltas en la soluci�on con el �n de obtener una estructura
especialmente adecuada para su tratamiento en plataformas de computaci�on paralela.
Posterior a esta etapa, se utiliza un m�etodo directo, indirecto o una combinaci�on de
ambos para resolver el problema.
ecuaciones algebraicas linealesAlternativas para la solución paralela de
Gradiente Conjugado
Método de la matriz W
Factorizacionesmultiples
Factorizaciones ysubstitucionesindependientes
Métodos directos
en el borde y la diagonal
en el borde y la diagonal
bloque diagonalAproximadamente
Tipo banda
Con bloques anidados
Con bloques
reordenamiento y particiónMétodos basados en
Métodos indirectos
Gauss Jacobi
Gauss Seidel
Figura 2.5: Alternativas para la soluci�on paralela del problema algebraico lineal
Los m�etodos indirectos de Gauss Seidel y Gauss Jacobi son extreme-
damente paralelizables pero adolecen de problemas de convergencia. Este motivo,
sumado a requerimientos de comunicaci�on extremadamente elevados, los ha mante-
nido pr�acticamente fuera de las perspectivas de aplicaci�on. Como una alternativa
superior, el m�etodo indirecto del Gradiente Conjugado, en combinaci�on con una eta-
pa de pre-condicionamiento de las ecuaciones, presenta caracter��sticas de robustez,
precisi�on y velocidad de computaci�on muy atractivas [GJM94]. Por otro lado, los
24
m�etodos directos, tales como la factorizaci�on LDU5 o la bifactorizaci�on, son apa-
rentemente secuenciales y no sufren de problemas de convergencia. La estrategia
de paralelizaci�on de tales m�etodos no es obvia, siendo los m�etodos de la matriz W
[PM92, WB96, MAK94, LVN94, LC93, HL94] y de las factorizaciones y substitucio-
nes independientes [MGVC96, VGM96, WB95] los m�as utilizados. Adicionalmente,
un gran n�umero de esquemas se ha propuesto para la soluci�on e�ciente de ecuaciones
algebraicas lineales mediante computadores vectoriales; sin embargo, en la mayor��a
de los casos ha sido vectorizada s�olo la etapa de substituci�on de los m�etodos directos.
Los m�etodos basados en el reordenamiento y la partici�on de las matrices
envueltas en el problema algebraico lineal tambi�en han sido utilizados exitosamente;
en �estos destaca la utilizaci�on de una combinaci�on de m�etodos directos e indirectos.
Por ejemplo, un m�etodo h��brido que combina tanto los m�etodos directo LU como
indirecto del Gradiente Conjugado se utiliza en [DFaK96]. A partir de la matriz
BBDF (Block Bordered Diagonal Form), la cual es producto de un reordenamiento
y partici�on que genera una matriz con bloques en la diagonal y en el borde de �esta,
se utiliza el m�etodo del Gradiente Conjugado para resolver la interconecci�on de las
ecuaciones y, posteriormente, la descomposici�on LU para resolver el conjunto de
ecuaciones independientes asociado a cada bloque diagonal de la matriz BBDF. La
Figura 2.6 muestra la estructura particular de �esta y otras matrices, como lo son la
con bloques anidados en la diagonal y en el borde (NBBDF: Nested Block Bordered
Diagonal Form) [Com78], la aproximadamente bloque diagonal (NBDF: Near Block
Diagonal Form) y la tipo banda [OKS90].
Como puede observarse, el n�umero de investigaciones asociadas a la solu-
ci�on de ecuaciones algebraicas lineales mediante computadores paralelos o vectoriales
es considerable. Desde el punto de vista pr�actico, un m�etodo generalizado para la
soluci�on del problema algebraico lineal, sin consideraci�on de la naturaleza de �este,
permitir��a reducir en gran medida el costo de dise~no de alguna estrategia paralela
particular a cada tipo de estudio. Frente a tal bene�cio, la principal desventaja se
concentra en la imposibilidad de incluir en el m�etodo generalizado ciertas poten-
5La factorizaci�on LDU se utiliza como m�etodo de inversi�on de matrices sim�etricas y la factori-
zaci�on LU para matrices asim�etricas.
25
(a) BBDF (b) NBBDF
x
x
x
x
x
x
x
x
(c) NBDF (d) Tipo banda
Figura 2.6: Matrices especialmente reestructuradas para procesamiento paralelo
cialidades que aborden las caracter��sticas particulares a uno u otro problema. Este
aspecto se discute a trav�es de la aplicaci�on considerada a continuaci�on.
Flujo de potencia
El ujo de potencia es una de las herramientas fundamentales para el
an�alisis de un sistema el�ectrico de potencia, siendo lejos el programa m�as utilizado
en tareas como la evaluaci�on de la seguridad del sistema y el an�alisis de la con�-
guraci�on m�as apropiada para �este. Adem�as, puesto que entre otras cosas permite
determinar las condiciones del sistema para una operaci�on en estado estacionario,
sirve como punto de partida para programas tales como el an�alisis de cortocircuitos
y la simulaci�on de transitorios. As��, la e�ciencia en la soluci�on del ujo de potencia
es un requerimiento fundamental para la e�ciencia global de un an�alisis integrado de
problemas.
En lo que respecta a la utilizaci�on del procesamiento paralelo en aplica-
26
ciones de sistemas el�ectricos de potencia, el estudio del ujo de potencia como tal no
ha concentrado un n�umero considerable de investigaciones. Algunas de las razones
son las siguientes [Fa96]:
� La di�cultad en el desarrollo de una estrategia de paralelizaci�on, respecto de
problemas similares, debido a las restricciones que se adhieren a las ecuaciones
algebraicas nolineales b�asicas del problema.
� La disponibilidad de algoritmos e�cientes, que permiten resolver los problemas
de ujo de potencia de sistemas de gran tama~no, con requerimientos computa-
cionales de bajo costo y tiempos de soluci�on muy reducidos.
Sin embargo, tal como se mencion�o anteriormente, el problema del ujo de
potencia, al igual que el de la simulaci�on de los transitorios electromec�anicos, puede
ser visto desde la perspectiva de un problema de soluci�on de ecuaciones algebraicas
lineales, para el cual las investigaciones relativas a la aplicaci�on del procesamiento
paralelo abundan. Dado que la naturaleza de ambos problemas no es la misma, �estos
presentan caracter��sticas particulares que desde el punto de vista de la soluci�on de
ecuaciones algebraicas lineales no necesariamente se consideran; una caracter��stica
relevante y particular al problema del ujo de potencia es que el Jacobiano no posee
elementos constantes. En contraste a �esto, la formulaci�on del problema de simulaci�on
puede resultar en un Jacobiano cuyos coe�cientes en su mayor��a son constantes entre
iteraciones. Con una caracter��stica como �esta, sut��lmente diferente, los esquemas de
soluci�on generalizados no siempre llevan a soluciones e�cientes.
En [Ac96] se plantea un m�etodo de paralelizaci�on del ujo de potencia
basado en la Descomposici�on �; �esta permite aproximar el Jacobiano por una ma-
triz bloque diagonal cuyos bloques se procesan independiente y simult�aneamente en
cada procesador. Tal aproximaci�on resulta en un incremento considerable de las ite-
raciones necesarias para la convergencia del ujo, de�ciencia que se intenta subsanar
mediante un m�etodo de aceleraci�on heur��stico. En lo que respecta a los resultados,
utilizando una m�aquina Intel iPSC/860 con topolog��a hipercubo y 8 procesadores, se
obtuvo una ganancia de velocidad igual a 10,39 en el estudio del sistema de prueba
IEEE 888. El m�etodo tambi�en fue sugerido para la evaluaci�on de contingencias. Por
27
su parte, en [WB95] la estrategia de paralelizaci�on para el ujo de potencia se basa
en el estudio de las tareas independientes que pueden ser encontradas en las etapas
de fatorizaci�on y substituci�on presentes en la soluci�on de ecuaciones algebraicas line-
ales, cuasivac��as y de gran dimensi�on. El desarrollo se llev�o a cabo en un computador
Symetry 81; considerando el estudio de un sistema de 970 barras y 3536 ramas, la
ganancia de velocidad obtenida al utilizar 20 procesadores con memoria compartida
fue 13. Otra alternativa de paralelizaci�on, sugerida en [HO94], considera la soluci�on
del ujo de potencia mediante el m�etodo de Gauss-Seidel; los desarrollos se llevaron a
cabo en dos m�aquinas, una Sequent Balance con memoria distribuida y un nCUBE2
de memoria distribuida.
Otras aplicaciones asociadas al ujo de potencia y su implementaci�on so-
bre computadores paralelos, vistas con mayor inter�es, consideran la paralelizaci�on
de una multiplicidad de problemas de ujo de potencia. Tal es el caso de la eva-
luaci�on de contingencias y los desarrollos basados en arquitecturas con procesadores
superescalares o vectoriales [BCFa96, GMPM92, GMPM93].
Simulaci�on de transitorios electromec�anicos
La simulaci�on de transitorios electromec�anicos concentra un sinn�umero de
investigaciones. Considerando que el trabajo planteado aqu�� se orienta a la aplicaci�on
del procesamiento paralelo en este tipo de estudio, las investigaciones relativas, en
conjunto a otros detalles del problema de simulaci�on, se describir�an en el Cap��tulo
IV de esta Tesis.
Simulaci�on de transitorios electromagn�eticos
El estudio de transitorios en rangos de frecuencia elevada, como los cau-
sados por la operaci�on de interruptores, fallas o descargas atmosf�ericas, es una de
las etapas importantes en la plani�caci�on de un sistema el�ectrico, particularmente,
en lo que dice relaci�on al dise~no de dispositivos aisladores y a la coordinaci�on de
esquemas de protecci�on. Cuando las dimensiones de una l��nea de transmisi�on son
comparables a la longitud de onda de los transitorios de frecuencia elevada, el estudio
debe considerar la din�amica asociada a la propagaci�on de las ondas electromagn�eticas
28
por las l��neas; este fen�omeno se conoce com�unmente con el nombre de transitorios
electromagn�eticos.
En el modelo generalmente utilizado para analizar los transitorios elec-
tromagn�eticos todos los componentes del sistema, excepto las l��neas de transmisi�on,
se modelan mediante circuitos equivalentes con par�ametros concentrados. Estos ele-
mentos se describen mediante ecuaciones diferenciales ordinarias y su soluci�on se
obtiene mediante integraci�on num�erica paso a paso. Por el contrario, las l��neas de
transmisi�on se modelan mediante elementos con par�ametros distribuidos descritos
matem�aticamente por ecuaciones diferenciales parciales (ecuaci�on de onda). En el
caso de considerar p�erdidas en la l��nea, la ecuaci�on de onda no tiene una soluci�on
anal��tica en el dominio del tiempo; sin embargo, tal como se observa en la Figura
2.7, �esta suele representarse adecuadamente por medio de un modelo de onda via-
jera que consiste de dos circuitos equivalentes disgregados, cada uno de los cuales
contiene una fuente de corriente en paralelo con una impedancia ubicada al �n de
ambos extremos de la l��nea.
HA BIA IHB
A B
Figura 2.7: Modelo utilizado para representar una l��nea de transmisi�on en estudios
de simulaci�on de transtorios electromagn�eticos
En [FaKA93], considerando como base los m�etodos num�ericos utilizados
en el Electromagnetic Transients Program (EMTP) [ML94], se propone un algoritmo
paralelo para la simulaci�on de los transitorios electromagn�eticos en redes de gran ta-
ma~no. Tal como puede observarse en el diagrama de ujo de la Figura 2.8, el recurso
principal utilizado para la simulaci�on paralela consiste en explotar el desacoplamien-
to natural introducido por el modelo de onda viajera en las ecuaciones de nodo de
la red.
29
Lea los datos
Determine las condiciones iniciales
optimizando el balance de carga en éstosAsigne subredes a los procesadores
t=h
i=1
en la i-ésima subred asignadaEvalúe las fuentes de corriente
Resuelva las ecuaciones de nodode la i-ésima subred asignada
i=i+1
t=h
i=1
en la i-ésima subred asignadaEvalúe las fuentes de corriente
Resuelva las ecuaciones de nodode la i-ésima subred asignada
i=i+1
Es la últimasubred asignadaal procesador
t=t+h
Envíe las funciones previamente evaluadas
Evalúe la ecuación de onda
Es la últimasubred asignadaal procesador
t=t+h
Envíe las funciones previamente evaluadas
Evalúe la ecuación de onda
integraciónpaso de
Es el último
?integraciónpaso de
Es el último
?SI Procesador B
Escriba la información requerida
Procesador A
Descomponga la red en subredes
que están asociadas a las variables en los extremosEvalúe las funciones de la ecuación de onda
de las líneas que llegan a las subredes asignadasque están asociadas a las variables en los extremos
Evalúe las funciones de la ecuación de onda
de las líneas que llegan a las subredes asignadas
que están asociadas a las variables en los extremosReciba las funciones de la ecuación de onda
opuestos de las líneas que llegan a las subredes asignadasque están asociadas a las variables en los extremos
Reciba las funciones de la ecuación de onda
opuestos de las líneas que llegan a las subredes asignadas
NO
SI
SI
NO
SI
NO
NO
Figura 2.8: Diagrama de ujo para la simulaci�on paralela de transitorios electro-
magn�eticos
El desarrollo de la simulaci�on se realiz�o en Lenguaje C. La plataforma
utilizada para efectos de an�alisis es un multiprocesador prototipo desarrollado pa-
ra la Universidad Federal de Rio de Janeiro. El computador paralelo consta de 8
unidades de procesamiento conectadas a trav�es de una topolog��a hipercubo; cada
unidad de procesamiento posee su propia memoria local y est�a provista de puertas
de comunicaci�on bidireccionales de gran velocidad.
Los resultados obtenidos indican una ganancia de velocidad elevada. Por
ejemplo, en un estudio basado en la simulaci�on del sistema brasile~no, cuya represen-
30
taci�on consisti�o de 1026 nodos, 2457 ramas y 146 l��neas, la ganancia de velocidad
alcanz�o a 6,92. Este resultado, as�� como otros expuestos en la referencia, ponen en
evidencia los bene�cios de utilizar el procesamiento paralelo en la simulaci�on de los
transitorios electromagn�eticos, en especial, si alguna caracter��stica propia, como lo
es el paralelismo natural del problema, puede ser explotado exitosamente mediante
una estrategia de paralelizaci�on adecuada.
Estabilidad transitoria mediante funciones de energ��a
El m�etodo utilizado m�as frecuentemente para evaluar tanto la estabilidad
transitoria como la seguridad din�amica de un sistema el�ectrico de potencia correspon-
de a la simulaci�on din�amica, principalmente la de los transitorios electromec�anicos.
A pesar de su utilidad, y de la gran cantidad de a~nos que respaldan su uso, los
m�etodos directos, tales como el de Lyapunov o