PDF de programación - Tesis: Julio Cesar - Aplicaciones de Procesamiento en Paralelo Usando Transputers

11N5'-1- [)/
!€5;v;'797

"'Tit IJ£ IIIVtSTI&ACtt• Y I~

ISTUIII$ AVANZAttS IH

I. P. N .

• I.LIOTEOA
'"'l;ENtEitiA ELECTRIC,

Centro de Investigaci6n y Estudios

Avanzados del I.P.N.

Depto. Ing. El<§ctrica
Seccion Computacion

Tesis de .Maestria: " Aplicaciones de

Procesamiento en Paralelo

Usando Transputers "

Que para Obtener el Grado de

:t\llae~tro en Ciencia~

Especialidad en Ingenieria Electrica

Pre~enta:

J uliu Ce~ar Gallardo1

Codirigida pur:

Dr. J o~e Lui~ Marruqufn Zaleta ( CIMAT)

M. en C. Felitl D. Sagols Tronco~o (CINVESTAV)

Mexico, D.F. Octubre de 1996

1 Bewrio de CONACYT

CHTit IE IIYiSTIUCtt• Y ' '

UTUIJiiS AVANZUU IH

I. P. N .

• II'IL.IOTEOA
l"' 8ENIERIA ELECTRIC.'

CLABIF. o- _ •.. JG_ o .~ .q · ···- -
A~QUIS ., Q /._~ /1_7J~_<(_ __ _
.. ECHA , •• • :;<,/.. ~ l] 'f :. :71.._ •.
PROC:IID-•~~.J~3L..:

. -·-

'

Agradecimientos:

A mi familia, por sn enorme apoyo moral y economico.

A CONACYT y a todos los m e xicanos, qnienes a t.raves de sus impuest.os
y la canalizacion de est.os por dicha inst.it.ncion , me han proporcionado el
medio economico apropiado para realizar mis est.udios de posgrado.

A mi a sesor d e t esis Jose Luis Marroquin Z. , por su valiosa asesoria y su

gran apoyo economico.

AI profesor Feliu Sagols T ., por la mot.ivacion academica que recibi de el a

traves de la impar t.icion de sus cursos.

A los sinodales M. e n. C . Feliu Sagols T ., Dr. Guillermo Morale s L .,
Dr . Jose Luis Marroquin z. y Dr. Salvador Bote llo R ., por acept.ar
fo rmar parte del jurado y asumir lo que est.o implica.

CIIITit II IIIVE ~ TISA C tell Y ••

UTUIIIS AVAIIIZAUS IH

I. P. N.

•laLIOTEOA
1111 1:;ENIEftiA ELECTRIC~

'

Dedicada:

A mi familia con mucho cariiio y todo con todo mi ser ,

A mts padres. Guillermo y Cholita .
.4. mis hermanos. Elias. Paty, Diana, Marco , Charly, Memo .
.4. mts sobrinos, Cristian y Niky.

A mi otra familia, Ia formada por los grandes amigos y cuates, a quienes

no hace falta t.ener sn sangre en com(m para llama rlos y considerarlos her
manos. A cada una d e esas familias que me encuet.ro en cada ciudad qne
voy.

A mi hermoso y Iindo Guanajuato encantado y a mi ranchito en el

que vivi mi enfancia: San Diego Quiriceo.

A " Jesus", quien es y segnini siendo para mi el ideal m is grande. a! qne t.odos
los seres hnmanos debemos aspirar. Por ser "nna incognita" y Ia t'mica razon
para cambia r Ia direccion de mi vida. A el, aunqne su hist.oria no sea real y
solo exist.a en Ia imaginacion , y aunqne desee profundament.e sn exist.encia.

A t.odas aquellas personas qne se han encont.rado asi mism as y han descubiert.o
q ue es necesario cambiar para ser mejores. A todas es t.as personas qne se
esfuerzan por encontrar Ia verdad y tratan de vivi r con ella. A aqn ellas per
sonas qne se han dado cnent.a que es necesario vivir mis alia de lo individual
y qne bnscan tma vida social mis justa y sin conveniencias personates.

A Ia mujer, Ia flor con aroma mis hermoso de este planet.a, pero a Ia vez. Ia de

mayor cuida do.

CMTit DE IIIY[STIUCtt• Y et

ISTUIIItS AVANUUS IH

I. P. N.

•t&LIOTEOA
'""~ENIERIA ELECTRIC.&.

Aplicaciones de Procesamien to en Paralelo

U san do Transputers

Julio Cesar Galla rdo

Octubr e de 1996

Resumen

En este t rabajo se presenta Ia paralelizacion de dos aplicaciones usando
una red de transputers que act ua n como nodos de procesamiento, lenguaje C
para su codificacion y una computadora PC 486 con Windows95 actuando
como ·'host ''. La primer aplicacion consiste en optimizar una estructu ra de
acero para una nave industria l suj eta a cargas laterales y utilizando como
informacion un catalogo de secciones transversales; esto es consegu ido medi
a nte el usa de una familia de algoritmos parametricos que permiten realizar
busquedas estocasticas. Esta familia de a lgoritmos es una generalizacion de
los algorit mos geneticos , las estrategias evolut ivas y el recocido simulado.
La segunda aplicacion consiste en construir un filtro para Ia eliminacion
de ruido en imagenes, usando un automata celular sfncrono determinfstico.
Ademas. en este trabajo se incluyen las experiencias adquiridas en el usa
de sistemas paralelos basados en transputers.

Palabras Clave:
algoritmos geneticos, automata celular , estrategias evolut ivas . modelo CSP,
occam, paralelismo , proceso, procesamiento de imagenes, tarjeta IMS 8008,
transputers, recocido simulado.

CUITII I[ lllfVESTIUCIH Y K
UTUIICS AVA~ZAUS Ill

l. P. N.

I!IIDLIOTEOA
L·)~ fN IERIA ELECTRIC,.

Contenido

Ohjet.ivos
lnt.rod uccion .
2.1 Tendencia de la Comput.acion
i>Que es la Comput.acion en Paralelo?
2.2
2.3 Dificultades en el Area del Paralelismo
2.4 Aplicaciones del Paralelismo
2.5 Contenido y Organizacion de este Tra bajo de Tesis
Present.acion de los Transputers
3. 1 Los Tra nsputers y la Tarj eta IMS 8008
3.2 Modelo de Programacion
3.3
3.4 Not.a.S Importantes Acerca de la Instalacion .
3.5 Herra mientas para Desarrollar Aplicaciones en una Red de Trans-

Inst.alacion del Software

puters

3.6 Caracteristicas Generales de Occam
3.7 Caracteristicas Generales de C
3.8 Descripcion de la Confignracion Adherida a toda Aplicacion
3.9 Combinando Varios Lenguajes en una Aplicacion

..1 Desarrollando Software en Paralelo

4. 1

Fases de Diseiio

Int.roduccion a la Computacion en Paralelo
4 .1.1
4. 1. 2 Estrategias para Explotar el Paralelismo
4. 1. 3 Fase de Prueha
4. 1. 4 Amilisis de Rendimiento

4.2 Configm acion de la Tarjeta IMS BOOB

4.2.1 Hardwire .
4.2 .2 Softwire

4.3 Desarrolla ndo una Aplicacion-Ejemplo en Occam
4.4 Desarrollando tma Aplicacion-Ejemplo en C
Pa ralelizacion de las Aplicaciones de Interes
5. 1 Optimizacion de Est.ructnras de Acero, Utilizando una Familia de

Algoritmos Estocast.icos en Paralelo
5. 1.1 Planteamient.o del Problema

12
13
16

19
24
25
26
26
30
30
30
31
33
34
37
38
42
47
57
66

66
66

5. 1.2 Fase de Diseiio
5. 1.3 Descripci6n General de los Procesos
5. 1.-1 Resultados .

5.2 Un Filtro para Ia Eliminari6n de Ruido en Proreso de lmagenes .

Usando un Automa ta Celula r Sincrono Deterministico.
5.2. 1 Pla nteamiento del Problema
5.2 .2 Fase de Diseiio
5.2.3 Descripci6n General de los Procesos
5. 2.4 Resultados .

6 Conrlusiones .
A Programando en Occam

A.1 Procesos Primitivos .
A.2 Uso de Canales
A .3 Construcciones

A.3.1 Secuenciales
A.3.2 Condicionales
A.3.3 Selerriones .
A.3.-l Cidos
A.3.5 Construcciones de concnrrencia
A.3.6 Alternativas

A.-I Temporizadores (timers)

8 P rogramando en C

8.1 Crea ndo y Manejando Procesos (process.h)

8 .1. 1 Procesos Asincronos
8.1.2 Procesos Sincronos
8.1.3 Sincronizaci6n entre Procesos
8.2 Canales de Comunicaci6n (channel.h)

lnicializaci6n de Canales

8.2.1
8.2.2 Canales de Salida .
8.2.3 Canales de Entrada
8.2.4 Recibiendo Datos de Varios Canales .

8 .3 Semaforos (semap hor.h)
8.4 Usando el Reloj

8.4.1 Control de Procesos Usando el Reloj

8.5 Otras Funciones .

C Descripci6n de los Operadores Geneticos: selecci6n,

cruzamzento, mutaci6n y aceptaci6n .

68
69
/ 5

77
77
79
80
85
87
89
89
90
90
90
91
91
92
92
93
95
99
99
102
103
105
105
105
106
107
109
110
111
11 2
112

114

l\.lntaci6n

C 1 Selecci6n .
C.2
C.3 Cruzamiento
C . ..l Aceptaci6n .

0 C6digo Principal de las Aplicaciones .

0 .1 Codificaci6n del Problema de Optimizaci6n de Estrnct.nras

0 .1.1 Proceso CONTROL
0 .1.2 Proceso C FC RUOA.

0.2 Codificaci6n del Filt.ro pa ra Procesamient.o de lmagenes

0 .2. 1 Proceso CONTROL
0 .2.2 Proceso AC

114
115
11 6
11 7
117
118
118
120
122
122
124

1. Objetivos

• lmplementar nna familia de a lgoritmos de b1'1sqneda estoc.astica qne indnye
a los algoritmos gem\ticos, estra t egias evolntivas y rec.oc.ido simnlado como
casos particnla res; d ebiendo resolver el signiente problema: "Optimizacion
d e estrnctnras de acero para nna nave indnstrial snjeta a cargas latera les"
Esta a plicacion se realizara mediante nna red de transputers qne act1\an
como nodos de procesamiento, lengnaje C para sn codificacion y nna com
p ntadora PC 486 con Windows95 actnando como compntadora sede (host).

• Constrnir e implementar nn filtro para la eliminacion de rnido en imagenes
nsando nn antomata celnlar sfncrono determinfstico. Tambien se realizara
en el mismo eqnipo de compnto y nsando el mismo lengnaje qne la aplicacion
ant erior.

• Prodncir nn texto qne transmita las experiencias adqniridas en el nso de

sistemas paralelos basados en transputers.

2. lntroduccion

En este rapitulo se present.a una idea general de lo que es Ia romput.ar ion en
paralelo y sus prinripales a plicariones. Ademas , se muest.ra una descripcion del
contenido ,. Ia organizarion de este trabajo.

2.1. Te ndencia de Ia Computacion

:\lur hos problemas de gran interes pnictico requieren de un alto grado de proce
samiento de comput.o. y frecuem.emem.e no pueden ser resuelt.os en el lapso de
t.iempo que Ia aplicacion ex.ige, en \illa computadora com1in (secuencial). a1in
cuando mejore su rendirnien