Paralelizacindelalgoritmodelmtododebareisslibrededivisinparasolucindesistemasdeecuacioneslinealesdeingenieraelctrica

Vista previa del material en texto

4to Congreso Internacional, 2do Congreso Nacional de Métodos Numéricos en Ingeniería y Ciencias Aplicadas 
M.C. Súarez, S. Gallegos, F. Zárate, S. Botello, M. Moreles, J. Pérez, M. Rodríguez y F. Domínguez (Editores) 
© UMSNH – aSMMNI - CIMNE, México 2007 
 
PARALELIZACIÓN DEL ALGORITMO DEL MÉTODO DE 
BAREISS LIBRE DE DIVISIÓN PARA SOLUCIÓN DE SISTEMAS 
DE ECUACIONES LINEALES DE INGENIERÍA ELÉCTRICA 
 
Rubén Martínez Alonso y Domingo 
Torres Lucio 
Instituto Tecnológico de Morelia 
Programa de Graduados e Investigación en Ingeniería Eléctrica 
(PGIEE) 
Av. Tecnológico 1500, C.P. 58120, Morelia, Michoacán 
México 
Email: rmaalo@mexico.com, dtorres@elec.itmorelia.edu.mx) 
 
 
Resumen. Este trabajo presenta la propuesta de paralelización del método de Bareiss libre de división de un 
paso para eliminación gaussiana en un sistema de ecuaciones lineales generadas de problemas de aplicaciones 
en ingeniería eléctrica, tales como sistemas eléctricos de potencia y circuitos eléctricos. Este algoritmo será 
implementado en procesadores integrados en un dispositivo electrónico programable; conocido como, 
FPGA “Field Programmable Gate Array”. Se obtuvo una complejidad algorítmica de O(n2) bajo un esquema 
de n2 procesadores que resolverán el sistema de ecuaciones lineales. Se presenta la propuesta de distribución 
de datos en la arquitectura y el algoritmo paralelo de procesamiento que realizarán los procesadores una vez 
cargados los datos para resolver el sistema de ecuaciones. Cada uno de los procesadores ejecuta en paralelo el 
determinante propuesto por Bareiss. 
 
Palabras clave: Algoritmo paralelo, Procesamiento paralelo, Sistemas de ecuaciones lineales, FPGA´s, 
Ingeniería eléctrica. 
1 INTRODUCCIÓN 
El método libre de división de un paso aplicado a eliminación Gaussiana se paraleliza para ser 
implementado en un FPGA, ya que es un método totalmente paralelizable1. Dadas sus ecuaciones 
matemáticas se realiza un ejemplo con un sistema de ecuaciones para observar su comportamiento 
matemático y posteriormente desarrollar una arquitectura que pueda ejecutar dicho algoritmo. Los 
procesadores contienen solo operadores aritméticos de suma y multiplicación y registros para 
almacenamiento de datos, con los que puede resolver un problema. 
El procesamiento paralelo ayuda a la ingeniería eléctrica a resolver grandes sistemas de ecuaciones 
obtenidos de sistemas eléctricos de potencia, elemento finito, control eléctrico, entre otros. Algunos de los 
problemas que se presentan en ingeniería eléctrica están relacionados con un gran número de variables que se 
tienen que resolver para encontrar la solución a un problema. Una arquitectura paralela para resolver estos 
sistemas es de gran utilidad, ya que disminuye el tiempo de la solución en dichos sistemas de ecuaciones1. 
Para implementar esta arquitectura en hardware se propone utilizar los dispositivos programables FPGA, 
ya que tienen Arreglos bidimensionales de módulos digitales reprogramables con interconexiones 
programables. Cuentan con millones de compuertas lógicas, buena relación costo rendimiento, y son 
dispositivos en los que se pueden realizar circuitos paralelos, por la facilidad que presenta su diseño. 
Este trabajo menciona en la sección dos el método libre de división de un paso aplicado a eliminación 
gaussiana con cada una de sus ecuaciones; en la sección tres se presenta la paralelización planteada para una 
arquitectura implementada sobre el método mencionado en la sección dos; en la sección cuatro se describe la 
distribución general de los datos en los procesadores una vez que se ha revisado la arquitectura propuesta; en 
la sección cinco se menciona la etapa de procesamiento que ejecutará el algoritmo, donde se describe la 
unidad de procesamiento FPGA; en la sección seis se presentan las conclusiones y finalmente en la sección 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
 
siete se muestran las referencias. 
2 METODO LIBRE DE DIVISIÓN DE UN PASO1 
En el área de alto desempeño computacional, el diseño de un arreglo de procesadores que utiliza el 
método de libre división, ha sido muy atractivo y de mucha atención recientemente. Las razones principales 
son que la división necesita un alto desempeño y un procesador de propósito especial, por lo que estas 
razones son un incremento de tiempo y espacio, dentro del procesador y para el cálculo. Además, hasta la 
estabilidad numérica es importante, el efecto acumulativo del error de redondeo realizado por las operaciones 
de división, también hace mucho más eficiente al método libre de división. 
El método de eliminación gaussiana de un paso libre de división se utiliza como un método optimo para 
realizar un arreglo con procesadores. 
Método de eliminación gaussiana de un paso libre de división1. 
Este permite generalizar un sistema lineal de ecuaciones dado por: 
Ax = B donde , )( ijaA =
mjnniaiBnji j ≤≤+≤≤=≤≤ 1,1),(,,1 
y nmjniaiX j −≤≤≤≤= 1,1),( . 
Para resolver Ax = B, la matriz A sería reducida a la forma diagonal o a la forma triangular pudiéndose 
realizar una sustitución hacia atrás. En general el algoritmo de sistolización que reduce A a su forma diagonal 
es más difícil que reducirla a su forma triangular. En este documento se considera el algoritmo para reducir la 
matriz A a su forma diagonal utilizando el método de un paso libre de división para eliminación gaussiana. 
Simplemente el algoritmo de un paso libre de división para diagonalización esta dado por la ecuación (1). 
⎪
⎪
⎩
⎪
⎪
⎨
⎧ =
=
≤≤≤≤≤≤
≤≤≤≤=
−−
−−
−
maneraotrade
aa
aa
kisia
a
mjknink
mjniaa
k
ij
k
ik
k
kj
k
kk
k
ij
k
ij
ijij
,
,
;,1,1
;1,1,
)1()1(
)1()1(
)1(
)(
)0(
 (1) 
donde A , es el determinante de la matriz A. 
3 PARALELIZACIÓN Y ARQUITECTURA DEL METODO DE PASO LIBRE DE 
DIVISIÓN 
A continuación se desarrollará un ejemplo de un sistema de ecuaciones de 3 x 3 con su vector 
independiente, para observar el comportamiento de este método y posteriormente desarrollar un 
planteamiento paralelo para la solución de este sistema y para n número de ecuaciones. Dada la matriz de la 
ecuación (2) aplicar el método libre de división de un paso para la solución de dicho sistema. 
Matriz Original 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
3
)0(
2
)0(
1
)0(
33
)0(
32
)0(
31
)0(
23
)0(
22
)0(
21
)0(
13
)0(
12
)0(
11
)0(
b
b
b
aaa
aaa
aaa
 (2) 
La matriz anterior se tiene que expresar de la forma: 
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
34
)0(
33
)0(
32
)0(
31
)0(
24
)0(
23
)0(
22
)0(
21
)0(
14
)0(
13
)0(
12
)0(
11
)0(
aaaa
aaaa
aaaa
 (3) 
Donde el vector independiente se incluye dejando una sola matriz de 3 x 4 para así aplicar el método libre 
de división de un paso. De manera que el vector bn se cambia por el vector an,n+1. 
A continuación se ejemplifican las iteraciones correspondientes para la solución de un sistema de ecuaciones 
con el número de elementos de la matriz anterior. 
A. Iteración 1. 
1414131312121111
)0()1()0()1()0()1()0()1(
4,3,2,1,1,1
aaaaaaaa
kijiksi
====
====
 
2421
1411
24
2321
1311
23
2221
1211
22
2121
1111
21 )0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
4,3,2,1,2,1
aa
aa
a
aa
aa
a
aa
aa
a
aa
aa
a
jiksi
====
===
 
3431
1411
34
3331
1311
33
3231
1211
32
3131
1111
31 )0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
)0()0(
)0()0(
)1(
4,3,2,1,3,1
aa
aa
a
aa
aa
a
aa
aa
a
aa
aa
a
jiksi
====
===
 
B. Iteración 2. 
1412
2422
14
1312
2322
13
1212
2222
12
1112
2122
11 )1()1(
)1()1(
)2(
)1()1(
)1()1(
)2(
)1()1(
)1()1(
)2()1()1(
)1()1(
)2(
4,3,2,1,1,2
aa
aa
a
aa
aa
a
aa
aa
a
aa
aa
a
jiksi
====
===
 
2424232322222121
)1()2()1()2()1()2()1()2(
4,3,2,1,2,2
aaaaaaaa
kijiksi
====
====
 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
 
34
2422
33
23222222
31
2122
31 )1(
32
)1(
)1()1(
34
)2(
)1(
32
)1(
)1()1(
33
)2(
32
)1(
32
)1(
)1()1(
32
)2(
)1(
32
)1(
)1()1(
)2(
4,3,2,1,3,2
aa
aa
a
aa
aa
a
aa
aaa
aa
aa
a
jiksi
====
===
 
C. Iteración 3. 
1413
3433
14
1313
33
13
1213
3233
12
11
3133
11 )2()2(
)2()2(
)2(
)2()2(
33
)2()2(
)2(
)2()2(
)2()2(
)2(
)2(
13
)2(
)2()2(
)3(
4,3,2,1,1,3
aa
aa
a
aa
aa
a
aa
aa
a
aa
aa
a
jiksi
====
===
 
24
)2()2(
)2()2(
)2(
23
)2()2(
33
)2()2(
23
)2(
)2()2(
)2()2(
22
)2(
)2(
23
)2(
)2()2(
)3(
23
3433
24
23
33
2223
3233
21
3133
21
4,3,2,1,2,3
aa
aa
a
aa
aa
a
aa
aa
a
aa
aa
a
jiksi
====
===
 
3434333332323131
)2()3()2()3()2()3()2()3(
4,3,2,13,3
aaaaaaaa
kijiksi
====
====
 
En la Ecuación (1) se describe el método de un paso libre de división aplicado al método de eliminación 
gaussiana, con lo anterior se observan las siguientes características del algoritmo que ayudarán a paralelizar 
dicho método. 
 Se aprecia que en cada iteración se pueden ejecutar todos los determinantes de 2 x 2 al mismo tiempo, 
por lo tanto la complejidad del algoritmo para la ejecución de los determinantes será: 
Ned =nxm, 
donde: 
Ned = número de determinates a ejecutar en una iteración 
n = número de renglones 
m = número de columnas 
donde: , entonces: 1+=nm
nnnnNed +=+= 2)1( 
 Se considera que el algoritmo tiene complejidad de O(n2) dado que es el que tiene el mayor exponente. 
 Existe una dependencia de datos para cada una de las iteraciones, se inicia con una iteración k y para 
realizar la iteración k + 1 se tiene que haber ejecutado la anterior, porque los datos de la iteración 
siguiente son dependientes del cálculo de la iteración anterior. 
Debido a las tres características mencionadas anteriormente se propone realizar una arquitectura paralela 
de procesadores que puedan desarrollar dicho algoritmo en un tiempo poco considerable, para desarrollo de 
aplicaciones en ingeniería eléctrica. 
Se propone realizar una red de procesadores con una distribución en malla, en forma matricial, donde el 
número de procesadores será igual a , existe un procesador central que es el que se encarga de repartir cada 
uno de los datos que serán procesados por cada uno de los procesadores. Las operaciones que realizan los 
procesadores son dos multiplicaciones y una suma, que corresponde al cálculo de un determinante de 2 x 2. 
Estos procesadores tienen 5 localidades de memoria, ya que los determinantes que calculan son de 2 x 2, y 
2n
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
solo tienen 4 valores constantes y el resultado se almacenará en la quinta posición. 
Desarrollo del algoritmo para cargar los datos en los procesadores. 
Lo primero que se tiene que realizar es la carga de los datos en cada uno de los procesadores, para que 
puedan empezarse a realizar las operaciones en cada uno de estos. El procesador central enviará cada uno de 
los datos secuencialmente hasta llegar a n. 
En la paralelización del método de un paso libre de división se tiene que considerar el número de la 
iteración que se este ejecutando ya que los procesadores tienen una posición porque están dispuestos en 
forma matricial y se considerarán de la siguiente manera dada su posición: 
14321
1334333231
1224232221
1114131211
...
...
...
...
+
+
+
+
nnnnnn
n
n
n
PPPPP
PPPPP
PPPPP
PPPPP
 
cada procesador ejecutará el cálculo del dato según sea su posición por ejemplo el P11 calculará el elemento 
a11,, el P12 calculará el elemento a12, y así cada uno de los procesadores se encarga de realizar su tarea. 
Distribución de datos en un sistema de ecuaciones. 
Al principio se toman los datos de la matriz inicial que se llamarán datos de la iteración (0). Donde: k = 
Iteración, i = Renglón, j = Columna. 
Como se ha mencionado anteriormente los procesadores están dispuestos en forma matricial como se 
muestra en la Figura 5. 
Procesador
Maestro
P1,1
P1,2
P1,3
P1,4
P1,m
P2,1
P2,2
P2,3
P2,4
P2,m
P3,1
P3,2
P3,3
P3,4
P3,m
Pn,1
Pn,2
Pn,3
Pn,4
Pn,m
Arquitectura 
Paralela
 
Figura 5. Distribución de los procesadores en forma matricial 
Primeramente en cada procesador se cargan cada unos de los datos correspondientes a su poción por 
ejemplo en el procesador P11 se carga el elemento a11, en el P12 se cargará el elemento a12, y así sucesivamente, 
como se muestra en la Figura 6. El origen de los datos parte del procesador maestro que reparte cada uno de 
los datos a todos lo procesadores. 
Los datos para la primera iteración serán exactamente los mismos que los de la iteración 
(0), esto quiere decir que el primer renglón de la nueva matriz correspondiente a la iteración (1) será igual al 
renglón de la matriz inicial, para este renglón no es necesario realizar ningún cálculo. Estos datos se cargan a 
naaaa 1131211 ...,.,
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
 
partir de un procesador central uno por uno, hasta llegar a n. Se necesita también cargar el dato a los 
procesadores Pij cuando 
11a
ik ≠ , si todos estos procesadores necesitan este dato ya que se presenta en cada 
uno de los determinantes con los que se calcula el nuevo valor, además este puede ser cargado en un ciclo de 
reloj en todos los procesadores. En la Figura 7 se muestra esta distribución. Para los renglones existe una 
condición especial, ya que cada procesador necesita un dato que corresponde al número del renglón en que 
este se encuentra y la iteración que se esta ejecutando, por ejemplo, para el renglón 2 y la iteración 1 se 
deberá cargar en dato a21 en todos los procesadores del renglón 2, como se muestra en la Figura 8. 
1=k
 
Procesador
Maestro
a1,2
a1,3
a1,4
a1,m
a2,2
a2,3
a2,4
a2,m
a3,2
a3,3
a3,4
a3,m
a1,1
a2,1
a3,1
an,1
an,2
an,3
an,4
an,m
Distribución de datos a i j 
en los proc esadores Pi j
 
Figura 6. Distribución de los datos en los procesadores 
ija ijP
Procesador
Maestro
Distribución de datos a i i 
en los proc esadores Pi ja1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
a1,1
Origen
 
Figura 7. Distribución del Dato en los procesadores kka ijP
También las columnas tienen un dato en común que se cargará en todos los procesadores pertenecientes a 
una misma columna, por ejemplo, para la columna 2 y la iteración 1 en toda la columna 2 se deberá cargar el 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
elemento a12 para todos los procesadores de esa columna, y así será el comportamiento para cada una de las 
demás columnas de procesadores. En la Figura 9, se muestra esta distribución. 
Procesador
Maestro
Distribuc ión de datos ai 1 
en los proc esadores Pi j
a2,1
a2,1
a2,1
a2,1
a2,1
a3,1
an,1
a3,1
an,1 a3,1
an,1
a3,1
an,1
a3,1
an,1
Origen
Origen
Origen
 
Figura. 8. Distribución de datos en los renglones de la arquitectura. 
Procesador
Maestro
Distribución de datos a 1 j 
en los proc esadores Pi jOrigena1,1
a1,2
a1,3
a1,4
a1,m
a1,1
a1,2
a1,3
a1,4
a1,m
a1,1
a1,2
a1,3
a1,4
a1,m
a1,1
a1,2
a1,3
a1,4
a1,m
Origen
Origen
Origen
Origen
 
Figura 9. Distribución de datos en las columnas de la arquitectura. 
Presentada la distribución de datos anterior se procede a realizar el cálculo de la primeraiteración puesto 
que son todos los datos que se necesitan para calcular los determinantes que darán el resultado de los nuevos 
datos que se necesitarán para iteración k+1. 
4 DISTRIBUCIÓN GENERAL DE LOS DATOS EN LOS PROCESADORES 
Dado el ejemplo anterior se observa que para realizar la carga de los datos se pueden proponer una serie 
de condiciones en forma general. 
En cada procesador se cargarán cada unos de los datos correspondientes a su poción dada por los 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
 
renglones i y las columnas j, es decir a cada procesador Pij se le cargará el dato aij. y así sucesivamente para 
todos lo procesadores. Los datos del renglón cuando kna. 1=k que se cargarán en cada procesador para la 
primera iteración serán exactamente los mismos que los de la iteración 0, ya que el primer renglón (cuando i 
= 1), de la nueva matriz correspondiente a la iteración k = 1 será igual al renglón de la matriz inicial, para 
este renglón no es necesario realizar ningún cálculo. Se necesita también cargar el dato a los procesadores 
que sean puesto que todos estos necesitan este dato ya que se presenta en cada uno de los determinantes 
con los que se calculará el nuevo valor, además este puede ser cargado en un ciclo de reloj en todos los 
procesadores. Para los renglones i existe una condición especial, ya que cada procesador necesita un dato que 
corresponde al número del renglón i en que este se encuentra y la iteración k que se esta ejecutando, por 
ejemplo, para el renglón i y la iteración k se deberá cargar en dato aik en todos los procesadores del renglón i 
donde k no cambia por ser la iteración que se esta ejecutando e i va desde 2 a n, y cuando i = 1 estos datos ya 
han sido cargados con otra condición. También las columnas j tienen un dato en común que se cargará en 
todos los procesadores Pkj pertenecientes a una misma columna, por ejemplo, para la columna j y la iteración 
k en toda la columna j se deberá cargar el elemento akj donde k no cambia por ser la iteración que se esta 
ejecutando y j va desde 1 a n, para todos los procesadores de esa columna, y así será el comportamiento para 
cada una de las demás columnas de procesadores. Una vez cargados los datos en cada uno de lo procesadores 
se realiza el cálculo para la primera iteración, y los resultados se utilizarán en la segunda iteración hasta llegar a 
las n-esima iteración. 
kka
k>
Iteración n 
En esta iteración es donde todos los procesadores empiezan a repartir datos en forma paralela a todos los 
demás procesadores para efectuar la solución de un sistema de ecuaciones donde los procesadores ejecutan 
simultáneamente los determinantes de 2 x 2 lo que representa una independencia del proceso en el algoritmo 
de Bareiss y una tarea más rápida en el cálculo. 
Para realizar el cálculo del determinante propuesto por Bareiss que es de 2 x 2 en cualquier iteración, se 
necesitan los valores de la iteración anterior; ya se vio que cada procesador Pij calcula su dato por lo que 
para cualquier iteración cada procesador ya cuenta con este dato y no será necesario realizar ninguna carga 
sobre el. En todas las iteraciones se necesitan los mismos datos descritos en el apartado de distribución 
general de los datos. Ya propuesto esto se inicia con el paralelismo de los datos y el cálculo matemático en 
cada uno de los procesadores. Dependiendo del número de la iteración en que se encuentre realizando el 
procesamiento los datos del renglón cuando 
ija
ki = no se necesitan calcular puesto que son los mismos que ya 
fueron calculados en la iteración ; y para todas las iteraciones se presenta siempre el mismo caso. Esto 
quiere decir que los procesadores cuando 
1−k
kjP ki = no necesitan realizar ningún cálculo. Los procesadores Pij 
cuando para calcular la iteración k necesitan el dato por lo que se deberá de distribuir en forma 
paralela a cada uno de los procesadores, puestos que todos estos procesadores necesitan este dato, ya que se 
presenta en cada uno de los determinantes con los que se calculará el nuevo valor, además este puede ser 
cargado en un ciclo de reloj en todos los procesadores. Para los renglones i existe una condición especial, ya 
que cada procesador necesita un dato que corresponde al número del renglón i en que este se encuentra y la 
iteración k que se esta ejecutando, por ejemplo, para el renglón i y la iteración k se deberá cargar en dato aik 
en todos los procesadores del renglón i donde k no cambia por ser la iteración que se esta ejecutando. 
También las columnas j tienen un dato en común que se cargará en todos los procesadores Pkj pertenecientes 
a una misma columna, por ejemplo, para la columna j y la iteración k en toda la columna j se deberá cargar el 
elemento akj donde k no cambia por ser la iteración que se esta ejecutando y j va desde 1 a n, para todos los 
procesadores de esa columna. 
ik ≠ kka
5 PROCESAMIENTO 
Para esta etapa se cuenta con un dispositivo FPGA, (Field Programmable Gate Array), También se 
denominan LCA (Logic Cell Array). Consisten en una matriz bidimensional de bloques configurables que se 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
pueden conectar mediante recursos generales de interconexión10. La arquitectura propuesta se implementará 
en un FPGA , ya que contiene millones de compuertas, y con esto es posible diseñar varios procesadores, 
que ejecutarán el algoritmo descrito en la sección cuatro. En la Figura 10 se muestra la estructura de un 
FPGA. 
 
Fig. 10 Estructura general de un FPGA 
En la Figura 11, se muestra el módulo de desarrollo con un FPGA. Para la programación de este dispositivo 
electrónico se cuenta con un lenguaje de programación llamado VHDL “Very High Description Lenguaje”. 
 
Fig. 11 Modulo de diseño con FPGA 
A .Características de los FPGAs10: 
• Arreglo bidimensional de módulos digitales reprogramables con interconexiones programables. 
• Capacidad de 5000 a 10 millones de compuertas en un solo chip. 
• Tiempos de retardo dependientes de la arquitectura. 
• Sustituyen a ASIC de mediano tamaño. 
• Buena relación costo/rendimiento para producciones relativamente pequeñas. 
B. VLSI y Lógica Programable10. 
• El uso de un FPGA permite el diseño de sistemas tan complejos como microprocesadores o sistemas 
en un solo chip. 
• El costo de desarrollo es relativamente bajo. 
• No se depende de una fábrica de circuitos integrados. 
R. MARTINEZ Y D. TORRES / Paralelización del algoritmo del método de bareiss libre de div. para sol. de sist. de ecuaciones lineales 
de ingeniería eléctrica 
 
 
 
 
• Ciclo de diseño con FPGA corto, el diseño se puede portar a un ASIC si la demanda lo requiere. 
• Los FPGAs están sustituyendo a los arreglos de compuertas y a algunos ASIC debido a sus ventajas. 
• Potencial grande de desarrollo tecnológico en México con los FPGAs. 
 
C. Plataforma de desarrollo con FPGA10. 
• Computadora PC. 
• Herramienta CAD. 
• Tarjetas de desarrollo. 
• Tarjetas PCI. 
• Sistemas Multimódulos y sistemas dedicados. 
6 CONCLUSIONES 
El método de Bareiss de un paso libre de división para eliminación gaussiana presenta grandes ventajas de 
paralelización puesto que en cada una de las iteraciones necesarias para la solución de un sistema de 
ecuaciones los procesadores ejecutan simultáneamente los determinantes de 2 x 2 lo que representa una 
independencia del proceso en el algoritmo de Bareiss. Y por lo tanto se ahorra tiempo en la ejecución de un 
problema. Repartir los datos en paralelo desde un procesador a otro también se puede ejecutar aprovechando 
la disposición de cada uno de los procesadores para la solución de un problema. 
Conforme se van presentando los avances tecnológicos surgen aplicaciones que ayudan a resolver 
problemasen aplicaciones de la ingeniería eléctrica, los FPGA son una herramienta electrónica programable 
que ayudan al procesamiento de información e implementación de diferentes tipos de arquitecturas paralelas. 
Es posible la solución de sistemas de ecuaciones lineales originadas de un sistema eléctrico, mediante la 
aplicación del método de un paso libre de división para eliminación gaussiana a través del procesamiento de 
una arquitectura paralela en un FPGA. 
7 REFERENCIAS 
[1] Shietung Peng, Stanislav Sedukhin, “Parallel Algorithm and Architectures for Two-step Division-free Gaussian Elimination”, 
(0-7803-4229-1/97 1997 IEEE). 
[2] M.C. Rubén Martínez Alonso, Dr. Domingo Torres Lucio, “Propuesta para la Solución de Sistemas de Ecuaciones Lineales 
por el Método libre de división para Aplicaciones en Ingeniería Eléctrica con un FPGA”. XVI Reunión de Otoño de 
Comunicaciones, Computación, Electrónica y Exposición Industrial, IEEE ROC&C’2005. Acapulco, Gro. Del 
29 de Noviembre al 4 de Diciembre del 2005. 
[3] Fernando Prado Carpio, “Arquitecturas Avanzadas”, Universidad de Valencia, Valencia España, 30, Enero 2002. 
[4] Felipe Morales S. Hugo Rudnick V.D.W. Aldo Cipriano Z., “Descomposición ε Balanceada para Analisis de Sistemas de 
Potencia Mediante procesamiento Paralelo”, IEEE trans on power systems, 1995. 
[5] A. P. Vazhenin “ Parallel Algorithm for Solving Systems of Linear Equations with Dynamically changed Length of Operands”, 0-
8186-7038-X/95 1995 IEEE. 
[6] George C. Nakos, Peter R. Turner, Robert M Williams. “Fraction-Free Algorithms for linear and Polynomial Equations”, 
ACM, Mathematics Departament. 
[7] Tateaki Sasaki, Hirokazu Murao, “Efficient Gaussian Elimnination Method for Symbolic Determinats and Linear Systems”, 
ACM, Proceedings of the 1981 Symposium on Symbolic and Algebraic Computation. 
[8] Alkiviadis G. Akritas, Evgenia K. Akritas, “Varius Proofs os Sylvester´s (Determinant) Identity”, IMACS Symposium SC-
1993, Partially supported by GRF grant 3089-xx-0038 (1993) of the University of Kansas. 
[9] Glenn W. Stagg, Ahmed H. El-Abiad, “Computer Methods in Power System Analysis”, Mc Graw Hill Series in Electronic 
Systems, Copyright 1968. ISBN 0-07-Y85764-4. 
[10] Virtex-II Pro Development System, with FPGA, Disponible: http://www.digilentic.com. 
 
	1 INTRODUCCIÓN 
	2 METODO LIBRE DE DIVISIÓN DE UN PASO1 
	Método de eliminación gaussiana de un paso libre de división1.
	3 PARALELIZACIÓN Y ARQUITECTURA DEL METODO DE PASO LIBRE DE DIVISIÓN
	Desarrollo del algoritmo para cargar los datos en los procesadores.
	Distribución de datos en un sistema de ecuaciones.
	4 DISTRIBUCIÓN GENERAL DE LOS DATOS EN LOS PROCESADORES
	Iteración n
	5 PROCESAMIENTO
	6 CONCLUSIONES
	7 REFERENCIAS