PDF de programación - Tesis: Carlos Hernandez - Algoritmos de ordenamiento y teoria de graficas en una computadora paralela de tipo hipercubo

CUUI DE INVESTIUCIIM Y 6l

EST UDtes A. HNZ . &8 ' '•H

I. P. N .

/lii LI O T EOA
•
1'-lGENIER! ... ELECTRIC~

Centro de Investigaci6n y de Estudios Avanzados del

Instituto Politecnico Nacional

Departamento de Ingenieria El9ctrica

Secci6n Computaci6n

Titulo

Algoritmos de ordenamiento y teoria de graficas en

una computadora para lela de tipo hipercubo.

Trabajo realizado para obtener el grado de Maestro en Ciencias,

en Ia especialidad de lngenieria Eh~ctrica

Par el Alumno

Carlos Alberto Hernandez Hernandez

Trabajo dirigido par:

Dr. Sergio V. Chapa Vergara.

Ml!xico, O.F.

septiembre de 1995

10111"[11 tl INYESP ACIU Y 0!

UT U8!" S AV~~I H".<, /Jf(

I. P . N .

ISI LlOT€:__C,A.

•
''II;ENIER!A ELECTRIC'

CINVESTAY

I P N

ADQUJSICION
DE LIBROS

. q_s.:.-!3:_. _ _
: (..-L. _;_::..oi...2.-
' .
.
FECH A -·...f..-. ,.:_ ,~._._._,
P~OCIL a. .. .• .".i.....: _ _ _

....

~

•--

A mis Padres.

A mis Hermanos.

;&llltt II£ I~VEST I6AC' !U Y ll

H :

• VA.' .~ ~ IS Ofl

I. P. N .

• III L IOT E CA
'"'r;ENIERIA ElE C TRIC~

Introducci6n

Esta tesis tuvo su motivaci6n del curso de AutOmat as Celulares {AC), impartido por el Dr
Harold V. Mcintosh, ya que los AC' presentan un magnifico paradigrna para Ia computaci6n
paralela. Los AC fueron propuestos por Von Neumann, como un modele el cual opera en una
manera altarnente paralela., mediante capias o variantes de si mismas y en modelos para
reproducci6n biol6gicas. Esta propuesta consisti6 en una nueva altemativa de enfoque paralelo
para Ia soluci6n de problemas. En los AC se presentan los problemas tipicos de computaci6n
paralela, donde una de las preguntas mcis importantes es encontrar metodos generales para
realizar aplicaciones Utiles. Por otra parte una de las mayores problemil.ticas de las computadoras
paralelas de prop6sito gñcrc;l •?S el pobre desempeno que se tiene por lo que uno de los cuellos de
botella es el uso eficientc: del hardware que depende del software. Por Jo que tomando en cuenta
estos dos antecedentes se
induce a\ planteam.iento de Ia pregunta £,C6mo utilizar (prograrnar)
eficientemente las computadoras paralelas con metodos generales, para resolver problemas
comunes?, que es el centro de motivaci6n de este trabajo.

Aunque Ia aplicaci6n de Ia tecnologia en computaci6n masivamente paralela se tiene
disponible desde varies ai'ios atrcis; bil.sicamente, Ia mayoria de los algoritrnos y sus aplicaciones
mil.s populares han sido disefiados bajo un esquema secuencial. La generaci6n de c6digo para un
maquina masivamente paralela es un tarea no trivial y requiere de: a) una nueva forma de pensar
los problemas, b) del desarrollo de los algoritmos en forma paralela y c) de su adecuada
implantaci6n de los modelos paralelos propuestos. Los anteriores son pasos que se daril.n para
obtener un mayor rendimiento en Ia reso\uci6n de problemas. En esta direcci6n es necesario
disei'iar nuevas algoritmos los cuales se apliquen a un modele de paralelismo (arquitectura) con el
fin de resolver problemas generales. El trabajo y Ia dificultad que implican el desarrollo de dichos
algoritmos requiere que el problema sea interesante, lo suficientemente general y regular para
compensar el esfuerzo realizado.

Por lo que el objetivo de esta tesis es mostrar las ventajas en el estilo de programaci6n
paralela de datos mUltiples para c6digo similar (SCMD, del ingles same-code/multiple-data), en Ia
programaci6n eficiente de computadoras paraJelas, por lo que se eligieron problemas tipicos de
computaci6n como el ordenam.iento y dos problemas de teoria de gril.ficas. Ademas se tome como
base Ia arquitectura hipercubo. Por lo que otro punta importante en esta tesis es el estudio de las
caracteristicas de Ia arquitectura hipercubo ya que de esta fonna es posible mapear eficientemente
tanto los algoritmos presentados como ademas en un futuro poder mapear otros aJgoritmos. Es
conveniente hacer tnfasis en que el modele SCMD es aplicable a otras arquitecturas.

1Una buena rcvisi6n de aut6matas celulares se puede encontrar en (Wolfram 86).,..:£fe 1 '~-•'

Esta tesis consta de tres capitulos como se muestra en Ia figura F I, el capitulo uno
present a un marco tt!orico, orienta allector en el contenido de esta tesis adem<is , el capitulo dos
abarca los algoritmos de ordenamiento y ademis plantea una clasificaciOn de algoritmos paralelos
de o rdenamiento, el capitulo tres es acerca de dos de los algoritmos de teoria de grificas mis
estudiados, el irbol de extensiOn minimal y el problema del vendedor viajero y pa r Ultimo se dan
conclusiones generales de los planteamientos iniciales asi como perspectivas futuras. Los
algoritmos que se tratan se eligieron ya que una gran cantidad de problemas pueden ser reducidos
a estos algoritmos. Contando en Ia secciOn de computaci6n con una computadora paralela del tipo
red de interconex.i6n con arquitectura hipercubo NCUBE 2, se plante6 Ia programaci6n paralela
SCMD en particular para las computadoras de red de interconexi6n de tipo hipercubo.

Figura Fl Estructura del trabajo

Agradecimientos

Varios amigos, compafieros y profesores han contribuido en Ia realizaciOn de este trabajo

Agradezco a todos Ia ayuda asi como las criticas recibidas.

Quiero decir que Ia secciOn de computaciOn del CTNVESTAV, me proporcionO un

ambiente de trabajo ideal para Ia realizaciOn de est a tesis.

Agradezco en particular (con riesgo de omitir a alguien 0 a muchos) a mi maestra de
primaria Adela por ensefiarme el inicio del camino, a! profesor de secundaria Jose Parada por su
apoyo, al Dr. JesUs Figueroa por sus consejos, a! Dr. Ibarra Zanatha y a Ia M. en C: Carlota
Tamayo por su confianza en mi, a! Dr. Sergio Chapa por su paciencia y guia en esta tesis, a! M. en
C. Alejandro Tinoco por sus valiosos comentarios, al M. en C. Oscar Olmedo por su tiempo en Ia
revisiOn de esta tesis, a! Lie. Ignacio Vega y a Felipa Rosas por su ayuda en Ia elaboraci6n de este
escrito.

Quiero agradecer a mis compafieros Alfredo, Efren, Manuel, Nacho, RaUl, Tanit, a los
demcis compafieros del CINVESTAV y a los MUPPETS, par su amistad y los buenos mementos
que pasamos juntos

Tambien agradezco a! CINVESTA V por darme Ia oportunidad de superarme, a mi pais y

al CONACyT por los recursos brindados para realizar Ia maestria.

Contenido

Dedicatoria

lntroducci6n

Agradecimientos

Capitulo 1 Computaci6n para lela

................... ............ ...... .............................. a

1.1
1.2
1.2.1
1.2.1.1
1.2.1.2
1.2.2
1.3.
1.3.1
1.3.1.1

12
13
14
15
17
21
...... .. .... ...... .. .... ... .. ....... .. . .. .. ... .. .... .... .... .. .. ... ... ..... : .. 22

Capitulo 2 Ordenamiento en paralelo

25

Ordenamiento paralelo
Ordenamiento paralelo con quicksort y mergesort (OPQM)

25
............ 26
... ................... ...... ...... ................................... 21

2. I
2.2
2.2.1 Algoritmo OPQM
2.2.2 Complejidad
2.2.3 Resultados experimentales
2.2
2.3.1 Algoritmo OPMR.
2.3.2 Comp1ejidad
D 3
2.4

Ordenamiento paraJelo pvr r!IUestreo ~~gular (OPMR)

32
. ....... 34
34

38
~
41

Capitulo 3 Algoritmos de teo ria de gratjcas en paralelo

3.1
3.2
3.2.1
3.2.2
3.2.3
3.3
3.3.1
3.3 .2
3.3 .3
3.3.4

Conclusiones

Trabajos futuros

Referencias

43

4 3

44

45 ••

51
.............. 52
54
57
58
59

61

62

64

CENTRO DE INVEST!GACION Y DE ESTUOIOS AVANZAOOS DEL I.P.N

Capitulo 1

Computaci6n paralela

las caracteristicas de

El principal objetivo de este capitulo es de presentar un marco te6rico de los
modelos de paralelismo y programaci6n, tambien se definen algunos conceptos y notaciones
que se utilizaran en el resto de este trabajo. Primero en 1.1 Computaci6n paralela, se
mencionan algunas caracteristicas generales de Ia computaci6n paralela, tanto a n.ivel
software como a nivel hardware; en 1.2 Clasificaci6n de arquitecturas, se revisa Ia
clasificaci6n proporcionada por Michael S. Flynn en [Flynn 72], que divide a las
computadoras en base a el nUmero de instrucciones y datos utilizados simultilneamente en
cuatro categorias, estas categorias nos pennite analizar
las
computadoras paralelas; en 1.2.1 Computadoras MTh1D se revisan los dos principales
modelos de computadoras MIMD, el modele de memoria compartida y el modele de red
tambien conocido como de paso de mensajes; en I .2.1.1 Arquitectura hipercubo se define en
que consiste un hipercubo asi como algunas propiedades importantes de los hipercubos; en
1.2.1.2 Computadora NCUBE 2 se describen las caracteristicas principales de Ia
computadora NCUBE 2, tales como los procesadores, canales de comunicaci6n, asi como el
algoritmo de ruteo que utiliza Ia computadora NCUBE 2; en 1.2.2 Desempeiio de
arquitecturas paralelas se definen algunos criterios para medir el desempeiio de
computadoras paralelas tales como: Ia aceleraci6n y eficiencia de los algoritmos paralelos,
ademils se revisa el efecto de Ia ley de Amdahl en el desempeii.o de las computadoras
paralelas; en I . 3 Programaci6n de sistemas paralelos se revisa el modele tradicional que
consiste en realizar compiladores que detecten el paralelismo en c6digo secuencial; asi como
los cinco principales estilos de programaci6n: procedural, orientada a objetos, funcional,
!Ogica y basada en conocimiento y par ultimo se explica Ia metodologia s