Cruz Pillancari 2010

UNIVERSIDAD DE MAGALLANES
FACULTAD DE INGENIER´IA
´
DEPARTAMENTO DE INGENIER´IA EN COMPUTACION

C´
alculo de ´Indice de Similidud
Estructural

Manuel Cruz Pillancari
2010

La presente Memoria de Titulaci´on ha sido aprobada con la siguiente calificaci´on:
Manuel Cruz Pillancari
Memoria :
Ex´amen de T´ıtulo :
Nota Final :

Sr. Eduardo Pe˜
na Jaramillo
Director Departamento
De Ingenier´ıa enComputaci´on

21 de diciembre de 2010.

UNIVERSIDAD DE MAGALLANES
FACULTAD DE INGENIER´IA
´
DEPARTAMENTO DE INGENIER´IA EN COMPUTACION

C´
alculo de ´Indice de Similidud
Estructural

Trabajo de titulaci´
on presentado en conformidad
a los requisitos para obtener el t´ıtulo de Ingeniero
Civil en Computaci´on e Inform´atica.
Profesor Gu´ıa: Sr. Dr. Pedro Alberti Villalobos.
Profesor Co-Gu´ıa: Sr. Dr.Sergio Soza Amigo.

Manuel Cruz Pillancari
2010

A mis padres, Manuel y Ana

Resumen

Este trabajo tiene como finalidad la de resolver el problema del C´alculo de ´Indice de
Similitud Estructural, el cual tiene relaci´on con el ´area econ´omica, por medio del dise˜
no e
implementaci´on de un algoritmo paralelo que permita la optimizaci´on del tiempo de ejecuci´on
del problema a resolver.
Para darsoluci´on al problema antes mencionado se opt´o por utilizar un modelo de
memoria compartida y para trabajar en esta arquitectura de computaci´on paralela, se
utiliz´o la tecnolog´ıa multi-n´
ucleo utilizando la librer´ıa de programaci´on OpenMP, con lo que
en el fondo se logra distribuir las operaciones necesarias para resolver el problema de ´ındice
de similitud estructural, entre los distintosn´
ucleos disponibles de la m´aquina utilizada y de
esta manera que estos c´alculos puedan ser realizados de manera simult´anea.
Tambi´en se puede mencionar que la aplicaci´on desarrollada permitir´a presentar los resultados obtenidos sobre la similitud estructural encontrada, para su posterior interpretaci´on y
an´alisis en lo relativo a esta tem´atica.

i

´Indice general

I. Introducci´
on

11.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.1. Objetivo General . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.2. Objetivos Espec´ıficos . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2. Descripci´on de los Cap´ıtulos . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

II. Marco Te´
orico

4

2.1.Computaci´on Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1.1. Clasificaci´on de Arquitecturas Paralelas . . . . . . . . . . . . . . . . .

5

2.1.2. Modelos de Comunicaci´on . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.3. Aplicaciones de la Computaci´on Paralela . . . . . . . . . . . . . . . .

7

2.1.4. Librer´ıas para Computaci´on Paralela . . . . . . . . . . . .. . . . . .

8

2.1.5. Teor´ıa de Algoritmos Paralelos . . . . . . . . . . . . . . . . . . . . . .

10

2.1.6. Factores que Afectan a la Computaci´on en Paralelo . . . . . . . . . .

12

ii

2.1.7. Cluster de Computadores . . . . . . . . . . . . . . . . . . . . . . . .

13

2.2. An´alisis Input-Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.2.1. Modelo de Input-Output .. . . . . . . . . . . . . . . . . . . . . . . .

17

2.2.2. Matrices de Coeficientes T´ecnicos . . . . . . . . . . . . . . . . . . . .

19

2.2.3. Indicador de Lemasne . . . . . . . . . . . . . . . . . . . . . . . . . .

20

III. Desarrollo

22

3.1. Comparativa entre Memoria Distribuida y
Compartida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.2. Librer´ıaOpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.2.1. Directivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.2.2. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.3. Herramientas de Programaci´on . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.3.1. Lenguajes de Programaci´on . . . . . . . . . . . ....