Estado Del Arte

5/22/2018 Estado Del Arte

1/32

3

Captulo I

1.1 INTRODUCCIN

El objetivo de la presente investigacin la cual realizamos en el InstitutoTecnolgico de Huatabampo con apoyo del M.C Eleazar Ros Valdez, es verificarsi realmente un mtodo de ordenamiento es ms veloz que otro en la solucin deun problema de ordenacin dado.

Normalmente la ejecucin de estos algoritmos se hace de forma individual en unasola computadora, esta vez trataremos de ponerlos a prueba en un ambienteparalelo es decir en un cluster computacional, para ello se utilizara CentOS que esuna distribucin Linux como sistema operativo y Rocks Cluster el cual es unsistema que permite instalar, configurar y administrar un cluster.

En este documento se menciona software que se puede utilizar para generar un

ambiente cluster as como los sistemas operativos que soportan dichos software.

Para la realizacin de la investigacin fue necesario recabar mucha informacinacerca de software disponible para llevar a cabo esta tarea, utilizamos algunosscripts y programas para la etapa de pruebas las cuales se mencionan de maneradetallada y comprensible.

Tambin se detalla el hardware que se utilizara para ensamblar el cluster en elcual se ejecutaran los algoritmos de manera distribuida, es decir, una ejecucinparalela.

Sin ms que decir a continuacin los dejamos con el desarrollo de la investigacin.


2/32

4

CAPITULO ll ESTADO DEL ARTE

2.1 SOFTWARE PARA CLSTER

2.1.1 ROCKS CLSTER

Rocks es una distribucin para clsters Linux de cdigo abierto, que permite a losusuarios finales crear fcilmente grupos computacionales, puntos finales de la redy visualizacin de paredes de azulejos de visualizacin. Cientos de investigadoresde todo el mundo han utilizado Rocks clster para implementar su propio clster

Versiones de rocks cluster

Rocks 1.0 Released: November, 2000 Kickstart files generated with 'sed' eKV (ethernet Keyboard and Video) - monitor compute node installs over the

ethernet FRONTED's built with a kickstart file on a floppy

The kickstart file was generated by a web form RedHat 6.2 Compute nodes downloaded packages via NFS

Rocks 2.0 Released: February, 2001 Kickstart files generated with 'sed' and 'cpp'

sed used for variable substitution cpp used for module inclusion

RedHat 7.0 Compute nodes downloaded packages with HTTP

Rocks 2.0.1 Released: April, 2001

Rocks 2.1 Released: April, 2001

Rocks 2.1.1 Released: November, 2001

Rocks 2.1.2 Released: December, 2001Rocks 4.2.1 (Cydonia) Released: September 2006 Maintenance release to 4.2 CentOS 4 update 4


3/32

5

Rocks 2.2 Released: March, 2002

Rocks 2.2.1

Released: March, 2002Rocks 2.3 (El Cap) Released: November, 2002

Rocks 2.3.1 (Denail) Released: February, 2003

Rocks 2.3.2 (Annapurna) Released: April, 2003

Rocks 3.0.0 (Lhotse) Released: September, 2003 "Rolls" are introduced

Rocks 3.1.0 (Matterhorn) Released: December, 2003

Rocks 3.2.0 (Shasta) Released: May, 2004

Rocks 3.3.0 (Makalu)

Released: October, 2004 Based on RedHat Enterprise Linux 3.0 rebuilt by the Rocks team from freely-available source RPMS

kernel 2.4.x SGE 5.3p6

Rocks 4.0.0 (Whitney) Released: June, 2005 based on CentOS 4.0

Rocks 4.1 (Fuji) Released: September, 2005 based on CentOS 4.2 kernel 2.6.x SGE 6.0u6

Rocks 4.2 (Hallasan) Released: August, 2006 based on CentOS 4.3 kernel 2.6.x


4/32

6

SGE 6.0u8 introduction of the Bio Roll and Restore Roll Moved to graphical installer

Rocks 4.3 (Mars Hill)

Released: June 2007 CentOS 4 update 5 Initial release of Rocks command line and PXE-first boot order

Rocks 5.0 (V) Released: April 2008 CentOS 5, update 1 Initial release of Xen support, fully-programmable partitioning, and flashing

BIOS on compute nodes using PXE

Rocks 5.1 (V.I)

Released: November 2008 CentOS 5, update 2 Initial release of virtual clusters support

Rocks 5.2 (Chimichanga) Released: June 2009 CentOS 5, update 3 Initial release of Solaris support for client nodes and ability to assign attributes

to nodes

Rocks 5.3 (Rolled Tacos)

Released: December 2009 CentOS 5, update 4 Core software maintenance release

Rocks 5.4 (Maverick)

Released: November 2010 CentOS 5, update 5 Redesign of the Avalanche Installer (written in C, stage2.img files are now in

the peer-to-peer network, predictions, ability to group nodes during install) Channel bonding and firewall settings controlled by the Rocks command line

Introduction of "Air Traffic Control" "channeld" replaces "greceptor" DNS resolution for multiple domains


5/32

7

Rocks 5.5/6.0 (mamba)

Released: may 2012

Rocks 6.1 (emerald boa)

Released: October 2012 Two-factor authentication is supported usinggoogle authenticator Internal ssh authentication is now host-based A frontend can be installed using a single partition ZFS on Linux roll now available. Based upon theZFS on Linux rc11. Note

ZFS on linux is a source roll. Support GPT partition tables for drives > 2TB Improved IPMI documentation rocks create distro speed improved by removing redundant checksum

calculation Infiniband (Mellanox) configured in the HPC roll with subnet manager

running on frontend SGE roll updates to GE-2011p1 Condor roll updated to 7.8.5

2.1.2 OPEN MOSIX

OpenMosix es un sistema decluster paraLinux que permite a varias mquinas

actuar como un nico sistema multiprocesador (denominado en ingls SSI). Estopermite que no tengamos que reprogramar nuestras aplicaciones para queaprovechen el cluster. Los procesos no saben en qu nodo del cluster se ejecutan,y es el propio openMosix el responsable de "engaarlos", y redirigir las llamadas alsistema al nodo del cluster en el que se lanz el proceso. openMosix implementaun algoritmo balanceador que permite repartir de forma ptima la carga, si est elcluster bien calibrado.

Se compone de un parche al kernel, responsable de las migraciones transparentesde procesos, y unas herramientas de rea de usuario, necesarias para calibrar yadministrar el cluster.

openMosix puede migrar cualquier proceso mientras que no haga uso de lossegmentos de memoria compartida. Segn la calibracin, migrarn procesos msligeros, o ms pesados.

Actualmente el desarrollo de openMosix est parado. Sigue funcionando bien paralos kernels 2.4; y para el kernel 2.6 an no funcionaba completamente.
http://code.google.com/p/google-authenticator/http://zfsonlinux.org/http://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Linuxhttp://es.wikipedia.org/wiki/Linuxhttp://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://zfsonlinux.org/http://code.google.com/p/google-authenticator/


6/32

8

Sin embargo, por su estabilidad y robustez an hay gente que lo emplea, y sigueinstalndolo. El nico problema real es con las mquinas que tienen hardware nosoportado por el kernel 2.4.

Caractersticas: No se requieren paquetes extra No son necesarias las modificaciones en el cdigo Es dependiente del kernel No migra todos los procesos siempre, tiene limitaciones de funcionamiento Problemas con memoria compartida


7/32

9

2.1.3 PELICANHPC

PelicanHPC es una distribucin de GNU / Linux que se ejecuta como una imagende arranque USB " live CD " o (tambin se puede arrancar desde una particin deldisco duro, o puede ser utilizado como un sistema operativo virtualizado). Si el

archivo de imagen ISO se pone en un CD o USB, a continuacin, se puede utilizarpara arrancar el ordenador. El equipo en el que se inicia PelicanHPC se conocecomo el "nodo FRONTED. Es el equipo con el que interacta el usuario. Una vezPelicanHPC est en marcha, un guin - " pelican_setup " - se puede ejecutar. Estescript configura el nodo FRONTED como servidor netboot . Despus de esto se hahecho, otros equipos pueden arrancar copias de PelicanHPC travs de la red.Estos otros ordenadores se denominan " nodos de cmputo". PelicanHPCconfigura el grupo formado por el nodo FRONTED y los nodos de cmputo paraque la computacin paralela basada en MPI se pueda hacer.

PelicanHPC se hace usando Debian GNU / Linux como base, a travs del sistemaDebian Live. Est hecho mediante la ejecucin de una nica secuencia decomandos con el comando "sh make_pelican - v *". Versiones personalizadas dePelicanHPC, por ejemplo, que contiene paquetes adicionales, pueden fcilmentehacerse modificando el guin make_pelican. El guin make_pelican y los paquetesnecesarios se proporcionan en PelicanHPC, para que pueda construir una imagenpersonalizada con las imgenes proporcionadas. Tambin puede ejecutarmake_pelican de cualquier distro GNU / Linux si instala live-build y algunos otrospaquetes.

Caractersticas

El nodo FRONTED puede ser un ordenador de verdad fue iniciada utilizando unCD o un dispositivo USB, o en una mquina virtual que se inicia con el archivo deimagen de CD. Con esta ltima opcin, PelicanHPC se puede utilizar al mismotiempo que el entorno de trabajo normal, que puede ser cualquiera de los sistemasoperativos comunes.

Los nodos de cmputo son normalmente los equipos reales, para obtener elmximo rendimiento, pero tambin pueden ser virtuales.

Soporta la computacin paralela basada en MPI utilizando Fortran (77, 90 ), C,C++ , GNU Octave y Python.


8/32

10

Ofrece la aplicacin Abrir MPI de MPI.

El clster puede ser redimensionado a agregar o quitar nodos con el comando "pelican_restarthpc.

Fcilmente extensible para agregar paquetes. Tambin fcilmente modificable, yaque se crea la imagen PelicanHPC CD / USB utilizando un nico guin que sebasa en el sistema Debian Live. Por esta razn, la versin distribuida es bastantebsica y ligera.

Contiene software de ejemplo: HPL Linpack (ahora en versin 2.0) de referencia yextensos ejemplos que utilizan GNU Octave. Tambin tiene mpi4py.

Limitaciones y exigencias

Los nodos de cmputo que se deben iniciar por la red. Esta es una opcin que

ofrece todos los dispositivos de red modernos suministrados con las placas base,pero a menudo se debe habilitar en la configuracin del BIOS. Permitirle que, ydarle ms prioridad que el arranque desde el disco duro u otras fuentes. Si ustedtiene una tarjeta de red que no va a hacer el arranque en red, es posible evitaresto usando rom -o- matic. Otra cosa a tener en cuenta es que el FRONTEDPelicanHPC funciona como un servidor DHCP. No debe utilizarlo en una redabierta, o te vas a causar conflictos dhcp. Esto te llevar a un mundo deproblemas con los administradores de red. Adems, sus nodos de cmputo no seiniciarn correctamente.

Un clster PelicanHPC est diseado para ser utilizado por una sola persona -slo hay un usuario, con el "usuario" nombre de usuario.

Versiones publicadas son para CPUs de 64 bits solamente (Opteron, Turion, Core2, etc.) make_pelican puede ser fcilmente utilizado para hacer una versin de 32bits, si es necesario.

La pgina web PelicanHPC enumera algunas otras distribuciones similares quepueden ser ms apropiados para determinados usos.

PelicanHPC es una imagen de CD producido mediante la ejecucin de un script

(vea a continuacin). El guin tiene licencia GPL v3. La imagen resultante CDcontiene software de la distribucin Debian GNU / Linux, y varias otras fuentes, loque est sujeto a las licencias escogidas por los autores de ese software.

PelicanHPC CD se distribuye con la esperanza de que ser til, pero SINNINGUNA GARANTA, incluso sin la garanta implcita de COMERCIALIZACIN oIDONEIDAD PARA UN PROPSITO PARTICULAR


9/32

11

2.1.4 ATIPA

Atipa ha logrado tanto con el lanzamiento de la Phoenix Cluster ManagementSuite. Herramienta de gestin de sistemas, tales como aadir nuevos nodos alclster con slo conectarlos a la red, encenderlo, y el nodo principal se configurar

automticamente el nuevo nodo y agregarlo en el fondo de recursos.

En un entorno de clculo equilibrado, las mejoras de hardware y de software hancontribuido igualmente al aumento de rendimiento de la aplicacin. Lo que msimporta es el tiempo ms corto para una solucin. El cluster Atipa est diseadopara proporcionar una manera integral y comparativo de lograr el rendimiento delclster. Ingenieros Atipa utilizan programas de benchmarking reconocidos paraasegurar el funcionamiento del clster. Estas herramientas analticas midendiferencias debidas a los cambios de hardware o software en el mismoclster. Hemos descubierto que la ejecucin con xito todas las pruebas de una

garanta de que el clster est configurado correctamente.

Caractersticas:

Completamente adaptable a sus necesidades exactas, incluyendo lainstalacin de bibliotecas complejas y su pre-requisitos.

Configuracin, sintonizacin y optimizacin del entorno de funcionamientoidntico en todos los nodos.

La administracin y gestin del Sistema suite inclua, Phoenix suite degestin de clusters de Atipa.

Integracin de los ganglios para el monitoreo muertos-clster simple. Soporte completo IPMI para un fcil y potente sistema de administracin de

la salud. Consultora, transferencia de conocimientos y asistencia tcnica durante

todo el ciclo de vida de la agrupacin.


10/32

12

2.1.5 SCYLD CLUSTERWARE

Scyld de clster es una solucin completa de administracin de clsteres HPC quees escalable, flexible y fcil de usar. Es totalmente compatible con RedHatEnterprise Linux y CentOS. Ofertas Scyld Clusterware.

Caractersticas:

Aprovisionamiento Super-rpido de clster Sistema nico de Arquitectura de imagen que garantiza la coherencia de la

configuracin El apoyo a las nubes internas y explosin de nubes Arquitectura basada en servicios web para la gestin de flujo de trabajo y la

presentacin desde cualquier lugar Calificacin y optimizacin de hardware pingino para una experiencia de

usuario ptima La certificacin como arquitectura de referencia Intel Cluster Ready para

clusters SSI

2.1.6 OSCAR

Cluster OSCAR. (Open Source Cluster Application Resources) es una coleccinde software de cdigo abierto para crear un cluster sobre Linux desarrollada por elGrupo de Clusters Abiertos (OCGOpen Cluster Group).

Los computadores que conforman el cluster se denominan nodos, existen dostipos denodos: unnodo principal (nodo servidor) y varios nodos de cmputo

(nodos clientes).Elnodo principal provee respuestas a los pedidos de servicio y asigna las tareasapropiadas a cada nodo cliente. Los nodos clientes se dedican a realizar tareas decmputo, poseen hardware homogneo y disponen de una copia completadelsistema operativo y de otros programas. Los nodos se comunican a travs deunaredEthernet que no est expuesta al mundo exterior; el nodo servidor poseedos interfaces de red: una interfaz de red conectada al mundo externo y unainterfaz conectada a la red interna.

OSCAR se instala sobre un computador con una distribucin Linux previamente,realiza la instalacin y/o configuracin de los paquetes necesarios para el clusterde forma automtica.
http://www.ecured.cu/index.php/Nodohttp://www.ecured.cu/index.php/Nodohttp://www.ecured.cu/index.php/Nodohttp://www.ecured.cu/index.php/Sistema_operativohttp://www.ecured.cu/index.php/Red_de_computadorashttp://www.ecured.cu/index.php/Ethernethttp://www.ecured.cu/index.php/Ethernethttp://www.ecured.cu/index.php/Red_de_computadorashttp://www.ecured.cu/index.php/Sistema_operativohttp://www.ecured.cu/index.php/Nodohttp://www.ecured.cu/index.php/Nodohttp://www.ecured.cu/index.php/Nodo


11/32

13

2.2 LENGUAJES DE PROGRAMACIN PARALELA

La computacin paralela es una forma de cmputo en la quemuchasinstrucciones se ejecutan simultneamente, operando sobre el principiode que problemas grandes, a menudo se pueden dividir en unos ms pequeos,

que luego son resueltos simultneamente (en paralelo). Hay varias formasdiferentes de computacin paralela: paralelismo a nivel de bit, paralelismo a nivelde instruccin,paralelismo de datos yparalelismo de tareas.El paralelismo se haempleado durante muchos aos, sobre todo en la computacin de altasprestaciones, pero el inters en ella ha crecido ltimamente debido a laslimitaciones fsicas que impiden el aumento de la frecuencia. Como el consumo deenerga y por consiguiente la generacin de calor de las computadorasconstituye una preocupacin en los ltimos aos, la computacin en paralelo se haconvertido en el paradigma dominante en laarquitectura de computadores,principalmente en forma deprocesadores multincleo.

2.2.1 MPI

MPI (Message Passing Interface) es un Interfaz estandarizado para la realizacinde aplicaciones paralelas basadas en paso de mensajes. El modelo deprogramacin que subyace tras MPI es MIMD (Multiple Instruction streams,Multiple Data streams) aunque se dan especiales facilidades para la utilizacin delmodelo SPMD (Single Program Multiple Data), un caso particular de MIMD en elque todos los procesos ejecutan el mismo programa, aunque no necesariamentela misma instruccin al mismo tiempo.

MPI es, como su nombre indica, un interfaz, lo que quiere decir que el estndar noexige una determinada implementacin del mismo. Lo importante es dar alprogramador una coleccin de funciones para que ste disee su aplicacin, sinque tenga necesariamente que conocer el hardware concreto sobre el que se va aejecutar, ni la forma en la que se han implementado las funciones que emplea.

Figura 2.1.Ubicacin de MPI en el proceso

de programacin de aplicaciones paralelas
http://es.wikipedia.org/wiki/Instrucci%C3%B3n_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Paralelismo_de_datoshttp://es.wikipedia.org/wiki/Paralelismo_de_tareashttp://es.wikipedia.org/wiki/Arquitectura_de_computadoreshttp://es.wikipedia.org/wiki/Microprocesadorhttp://es.wikipedia.org/wiki/Microprocesadorhttp://es.wikipedia.org/wiki/Arquitectura_de_computadoreshttp://es.wikipedia.org/wiki/Paralelismo_de_tareashttp://es.wikipedia.org/wiki/Paralelismo_de_datoshttp://es.wikipedia.org/wiki/Instrucci%C3%B3n_(inform%C3%A1tica)


12/32

14

MPI ha sido desarrollado por el MPI Forum, un grupo formado por investigadoresde universidades, laboratorios y empresas involucrados en la computacin dealtas prestaciones. Los objetivos fundamentales del MPI Forum son los siguientes:

Definir un entorno de programacin nico que garantice la portabilidad delas aplicaciones paralelas.

Definir totalmente el interfaz de programacin, sin especificar cmo debeser la implementacin del mismo. Ofrecer implementaciones de calidad, de dominio pblico, para favorecer la

extensin del estndar. Convencer a los fabricantes de computadores paralelos para que ofrezcan

versiones de MPI optimizadas para sus mquinas (lo que ya han hechofabricantes como IBM y Silicon Graphics).

Los elementos bsicos de MPI son una definicin de un interfaz de programacinindependiente de lenguajes, ms una coleccin de bindings o concreciones de eseinterfaz para los lenguajes de programacin ms extendidos en la comunidadusuaria de computadores paralelos: C y FORTRAN.

2.2.2 OpenMP

OpenMP es unainterfaz de programacin de aplicaciones (API) para laprogramacinmultiproceso dememoria compartida en mltiples plataformas.Permite aadirconcurrencia a los programas escritos en C, C++ y Fortran sobre labase del modelo de ejecucinfork-join.

Est disponible en muchasarquitecturas, incluidas las plataformas de Unix y deMicrosoft Windows. Se compone de un conjunto de directivas de compilador,rutinas de biblioteca, y variables de entorno que influyen el comportamiento entiempo de ejecucin.

Definido juntamente por un grupo de proveedores de hardware y de softwaremayores, OpenMP es un modelo de programacinportable yescalable queproporciona a los programadores una interfaz simple y flexible para el desarrollode aplicaciones paralelas para las plataformas que van desde las computadorasde escritorio hasta lassupercomputadoras. Una aplicacin construida con unmodelo deprogramacin paralela hbrido se puede ejecutar en uncluster decomputadoras utilizando ambos OpenMP yMPI, o ms transparentemente atravs de las extensiones de OpenMP para los sistemas dememoria distribuida.

OpenMPse basa en el modelo fork-join, paradigma que proviene de lossistemasUnix,donde una tarea muy pesada se divide en Khilos (fork) con menorpeso, para luego "recolectar" sus resultados al final y unirlos en un solo resultado(join).
http://es.wikipedia.org/wiki/Interfaz_de_programaci%C3%B3n_de_aplicacioneshttp://es.wikipedia.org/wiki/Multiprocesohttp://es.wikipedia.org/wiki/Memoria_compartidahttp://es.wikipedia.org/wiki/Computaci%C3%B3n_concurrentehttp://es.wikipedia.org/wiki/Bifurcaci%C3%B3n_(sistema_operativo)http://es.wikipedia.org/wiki/Arquitectura_de_computadorashttp://es.wikipedia.org/wiki/Pragma#Programaci.C3.B3nhttp://es.wikipedia.org/wiki/Variable_de_entornohttp://es.wikipedia.org/wiki/Portabilidadhttp://es.wikipedia.org/wiki/Escalabilidadhttp://es.wikipedia.org/wiki/Supercomputadorahttp://es.wikipedia.org/wiki/Computaci%C3%B3n_paralelahttp://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Interfaz_de_Paso_de_Mensajeshttp://es.wikipedia.org/w/index.php?title=Memoria_distribuida&action=edit&redlink=1http://es.wikipedia.org/wiki/Unixhttp://es.wikipedia.org/wiki/Unixhttp://es.wikipedia.org/w/index.php?title=Memoria_distribuida&action=edit&redlink=1http://es.wikipedia.org/wiki/Interfaz_de_Paso_de_Mensajeshttp://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Cluster_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Computaci%C3%B3n_paralelahttp://es.wikipedia.org/wiki/Supercomputadorahttp://es.wikipedia.org/wiki/Escalabilidadhttp://es.wikipedia.org/wiki/Portabilidadhttp://es.wikipedia.org/wiki/Variable_de_entornohttp://es.wikipedia.org/wiki/Pragma#Programaci.C3.B3nhttp://es.wikipedia.org/wiki/Arquitectura_de_computadorashttp://es.wikipedia.org/wiki/Bifurcaci%C3%B3n_(sistema_operativo)http://es.wikipedia.org/wiki/Computaci%C3%B3n_concurrentehttp://es.wikipedia.org/wiki/Memoria_compartidahttp://es.wikipedia.org/wiki/Multiprocesohttp://es.wikipedia.org/wiki/Interfaz_de_programaci%C3%B3n_de_aplicaciones


13/32

15

Cuando se incluye unadirectiva OpenMPesto implica que se incluyeunasincronizacin obligatoria en todo el bloque. Es decir, el bloque de cdigo semarcar comoparalelo y se lanzarn hilos segn las caractersticas que nos d ladirectiva, y al final de ella habr unabarrera para la sincronizacin de losdiferentes hilos (salvo que implcitamente se indique lo contrario con la

directiva nowait). Este tipo de ejecucin se denomina fork-join.

2.3 MTODOS DE ORDENAMIENTO.

Qu es ordenamiento?

Es la operacin de arreglar los elementos en algn orden secuencial de acuerdo aun criterio de ordenamiento.

El propsito principal de un ordenamiento es el de facilitar las bsquedas de losmiembros del conjunto de ordenamiento.

Cundo conviene usar un mtodo de ordenamiento?

Cuando se requiere hacer una cantidad considerable de bsquedas y esimportante el factor tiempo.

Por qu se requiere utilizar la programacin paralela para evaluar los mtodos deordenamiento?

Para nuestro caso de estudio es muy importante porque crear una rutina queevalu los mtodos de ordenamiento en forma simultnea ayudara a despejar la

duda acerca de cul es el mtodo de ordenamiento que mejor se desempee esesta tarea, lo que nos ayudara a entender el comportamiento y rendimiento quecada uno de ellos tiene al ser ejecutado.

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar.En este caso, nos servirn para ordenar vectores o matrices con valoresasignados aleatoriamente. Nos centraremos en los mtodos ms populares,analizando la cantidad de comparaciones que suceden, el tiempo que demora yrevisando el cdigo, escrito en Java, de cada algoritmo.
http://es.wikipedia.org/wiki/Directivahttp://es.wikipedia.org/wiki/Sincronizaci%C3%B3nhttp://es.wikipedia.org/wiki/Paralelohttp://es.wikipedia.org/wiki/Barrera_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Barrera_(inform%C3%A1tica)http://es.wikipedia.org/wiki/Paralelohttp://es.wikipedia.org/wiki/Sincronizaci%C3%B3nhttp://es.wikipedia.org/wiki/Directiva


14/32

16

2.3.1 MTODO BURBUJA

El mtodo de la burbuja es uno de los ms simples, es tan fcil como comparartodos los elementos de una lista contra todos, si se cumple que uno es mayor omenor a otro, entonces los intercambia de posicin.

Se denomina burbuja debido a que los valores ms pequeos burbujeangradualmente (suben) hacia la cima o parte superior del array de modo similar acomo suben las burbujas en el agua, mientras que los valores mayores se hundenen la parte inferior del array.

La burbuja ms simple de todas es la que compara todos con todos, generandocomparaciones extras, por ejemplo, no tiene sentido que se compare con sigomismo o que se compare con los valores anteriores a l, ya que supuestamente,ya estn ordenados.

Por ejemplo, imaginemos que tenemos los siguientes valores:

Lo que hara una burbuja simple, seria comenzar recorriendo los valores de izq. Aderecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3,si es mayor o menor (dependiendo si el orden es ascendiente o descendiente) seintercambian de posicin. Luego continua con el siguiente, con el 6, y lo comparacon todos los elementos de la lista, esperando ver si se cumple o no la mismacondicin que con el primer elemento. As, sucesivamente, hasta el ltimoelemento de la lista.

2.3.2 MTODO SHELL

El nombre se debe a su inventor, D. L. Shell. Se suele denominar tambinordenacin por insercin con incrementos decrecientes. Se considera que elmtodo Shell es una mejora de los mtodos de insercin directa.

Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de

mayor tamao y con ello se consigue que la ordenacin sea ms rpida.Generalmente se toma como salto inicial n/2 (siendo n el nmero de elementos),luego se reduce el salto a la mitad en cada repeticin hasta que el salto es detamao 1.

5 6 1 0 3


15/32

17

2.3.3 MTODO QUICK SORT

El algoritmo trabaja de la siguiente forma:

Elegir un elemento de la lista de elementos a ordenar, al que

llamaremos pivote. Resituar los dems elementos de la lista a cada lado del pivote, de manera

que a un lado queden todos los menores que l, y al otro los mayores. Loselementos iguales al pivote pueden ser colocados tanto a su derecha comoa su izquierda, dependiendo de la implementacin deseada. En estemomento, el pivote ocupa exactamente el lugar que le corresponder en lalista ordenada.

La lista queda separada en dos sublistas, una formada por los elementos ala izquierda del pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sublista mientras stas

contengan ms de un elemento. Una vez terminado este proceso todos loselementos estarn ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posicin en laque termine el pivote elegido.

En el mejor caso, el pivote termina en el centro de la lista, dividindola endos sub-listas de igual tamao. En este caso, el orden de complejidad delalgoritmo es O(nlog n).

En el peor caso, el pivote termina en un extremo de la lista. El orden de

complejidad del algoritmo es entonces de O(n). El peor caso depender dela implementacin del algoritmo, aunque habitualmente ocurre en listas quese encuentran ordenadas, o casi ordenadas. Pero principalmente dependedel pivote, si por ejemplo el algoritmo implementado toma como pivotesiempre el primer elemento del array, y el array que le pasamos estordenado, siempre va a generar a su izquierda un array vaco, lo que esineficiente.

En el caso promedio, el orden es O(nlog n).

No es extrao, pues, que la mayora de optimizaciones que se aplican al algoritmo

se centren en la eleccin del pivote.


16/32

18

2.4 SISTEMAS OPERATIVOS PARA CLUSTERS

2.4.1 HP-UXEs la versin deUnix desarrollada y mantenida por Hewlett-Packard desde 1983,ejecutable tpicamente sobre procesadores HP PA RISC y en sus ltimas

versiones sobre Intel Itanium (arquitectura Intel de 64 bits); a pesar de estarbasada ampliamente en System V incorpora importantes caractersticas BSD. Enla actualidad la ltima versin de este sistema operativo es la 11.23, tambinconocido como 11iv2 (2003), aunque existen numerosas instalaciones de sistemasms antiguos, especialmente HP-UX 10.x (1995-97) o incluso 9.x. (1992-95).

Apartir de la versin 11.11 (2000) se usa un sistema de numeracin doble, as la11.11 es tambin conocida como 11i, la 11.20 es 11iv1.5 y as sucesivamente.Est previsto el lanzamiento de 11.31 (11iv3) a finales de 2006.

2.4.2 AIX

Es un sistema operativo UNIX System V propietario de IBM. Inicialmentesignificaba "Advanced IBM Unix" pero probablemente el nombre no fue aprobadopor el departamento legal y fue cambiado a "Advanced Interactive eXecutive"

AIX corre en los servidores IBM eServers pSeries, utilizando procesadores de lafamilia IBM POWER de 32 y 64bits.

2.4.3 Windows Server 2008Es el nombre del sistema operativo para servidores de Microsoft. Es el sucesor deWindows Server 2003 puesto en libertad casi cinco aos antes. Al igual queWindows Vista, Windows Server 2008 se basa en el ncleo Windows NT 6.0.Desarrollo

Fue conocido como Windows Server "Longhorn" hasta el 16 de mayo de 2007,cuando Bill Gates, el presidente de Microsoft anunci su ttulo oficial (WindowsServer 2008) durante su discurso de apertura en WinHEC.

2.4.4 Mac OS XEs la versin actual del sistema operativo Macintosh de Apple. Se basa en UNIX yusa una interfaz grfica desarrollada por Apple llamada Aqua, que se inspira

libremente en la interfaz de Mac OS Classic. El gestor de ventanas X11,caracterstico en la familia de sistemas Unix, y Java se usan solo paracompatibilidad con software no nativo de Mac.Mac OS X v10.6 (Snow Leopard):

Anunciada en una conferencia privada en la Worldwide Developers Conference2008, esta nueva versin no incluye nuevas funciones, sino que est pensada
http://es.wikipedia.org/wiki/Unixhttp://es.wikipedia.org/wiki/Unix


17/32

19

principalmente para aumentar la estabilidad y seguridad de Leopard. Incluyesoporte para el sistema de archivos ZFS, que permite utilizar hasta 16 TB dedisco. Tambin tendr soporte para Microsoft Exchange Server 2007 en Mail(software), iCal y Adress Book (software). Mac OS X usa el protocolo ExchangeWeb Services para tener acceso a Exchange Server 2007.

2.4.5 SOLARISSolaris es un sistema operativo de tipo Unix desarrollado por Sun Microsystemsdesde 1992 como sucesor de SunOS. Es un sistema certificado oficialmente comoversin de Unix. Funciona en arquitecturas SPARC y x86 para servidores yestaciones de trabajo.

Aunque Solaris fue desarrollado como software privativo, la mayor parte de sucdigo se ha liberado como proyecto de software libre denominado OpenSolaris.Solaris es conocido por su escalabilidad, especialmente en sistemas SPARC, y

por ser origen de innovadoras tecnologas, como DTRace y ZFS.

2.4.6 FreeBSDEs un sistema operativo multiusuario, capaz de efectuar multitarea conapropiacin y multiproceso en plataformas compatibles con mltiplesprocesadores; el funcionamiento de FreeBSD est inspirado, como ya se dijo, enla variante 4.4 BSD-Lite de UNIX. Aunque FreeBSD no puede ser propiamentellamado UNIX, al no haber adquirido la debida licencia de The Open Group,FreeBSD s est hecho para ser compatible con la norma POSIX, al igual que

varios otros sistemas "clones de UNIX". El sistema FreeBSD incluye el ncleo, laestructura de ficheros del sistema, bibliotecas de la API de C, y algunas utilerasbsicas. La versin 6.1[3] trajo importantes mejoras como mayor apoyo paradispositivos Bluetooth y controladores para tarjetas de sonido y red.

La ltima versin estable es la 7.0 lanzada el 27 de febrero del ao 2008, queincluye compatibilidad con el sistema de archivos ZFS de Sun y a la arquitectura

ARM, entre otras novedades.

2.4.7 CentOS

CentOSes una distribucin de Linux la cual fue compilada por voluntarios a partirdel cdigo liberado por Red Hat, en resumen, CentOS es un sistema basado enRed Hat. A diferencia de las distribuciones de Linux ms conocidas como Debian,Fedora o Ubuntu, este sistema es robusto, es decir, es un sistema por demsestable y confiable lo que lo hace ideal para crear servidores especializados.


18/32

20

Este sistema es por mucho una de las mejores opciones debido a que sudesarrollo no fue enfocado a innovacin, sino a estabilidad eso aunado a susraces de Red Hat dan seguridad y confianza, adems de contar condocumentacin y soporte masivos en la red.

Dicho lo anterior, CentOS es la distribucin ideal para la creacin de un cluster yaque es uno de los sistemas Linux ms estables y robustos que se puedenencontrar con una gran capacidad y confiabilidad para la gestin de redes y/oservidores.


19/32

21

CAPTULO III IMPLEMENTACION

3.1 UbicacinEl presente proyecto fue realizado en el Laboratorio de Computo del InstitutoTecnolgico de Huatabampo, avenida tecnolgico s/n colonia unin, Huat, Son.

Figura 3.1. Ubicacin del lugar donde se realizo en proyecto


20/32

22

3.2 Software necesario

Para la realizacin de este proyecto se eligi el sistema operativo CentOS versin6.3 porque es un sistema muy estable y robusto lo cual permite eliminar errores decompatibilidad de hardware haciendo de la creacin del clster una tarea sencilla y

rpida.

Las razones por la cual empleamos este sistema son las siguientes:

Fcil mantenimiento Idneo para el uso a largo plazo Entorno favorable para los usuarios Desarrollo activo Soporta todo el hardware y software que soporta Red Hat.

Es gratuito, muy estable, porque contiene paquetes que estn muyprobados de bugs. Especial para servidores

Como software para cluster escogimos rocks cluster por ser una distribucin paraclusters de alto rendimiento, el cual facilita la configuracin de las computadorasque fungirn el papel de nodos del cluster, debido a que la adicin de un nuevonodo se hace de manera automtica por medio de la red del cluster.

La instalacin de rocks cluster puede ser modificada lo que hace que el clster sea

ms personalizado en cuanto a la tarea que este vaya a desempear, e sto pormedio de Rolls (paquetes de instalacin) como por ejemplo el roll de Ganglia elcual nos ayudara a ver y monitorear de manera grafica el rendimiento del cluster.

Aparte de ser una de las distribuciones mas empledas en el mbito de clusters porlo cual existe mucha documentacin que puede ser de ayuda en el desarrollo delos mismos.


21/32

23

3.3 Hardware utilizado

PC1 Procesador intel Pentium IV a 2.8 Ghz Memoria ram 256 mb Disco duro 40 Gb Tarjeta de red integrada Fast Ethernet 10/100 mb/s



PC4 Procesador intel core2duo a 2.83 Ghz Memoria ram 2 Gb Disco duro 200 Gb Tarjeta de red integrada Fast Ethernet 10/100 mb/s

Switch Baseline 2824 de 24 puertos

.


22/32

24

3.4 Pruebas

3.4.1 FUNCIONABILIDAD DEL CLUSTER

Antes de comenzar con la ejecucin de programas en el cluster veremos que

todas las computadoras se encuentran incluidas dentro de nuestro cluster paraellos se agregaron tres computadoras. Al agregar los nodos (computadoras) alcluster cada nodo recibe un nombre de forma automtica para poder identificarlasen el cluster como se muestra en las siguientes imgenes:

Como se puede observar en las imgenes cada una de los nodos reciben unnombre el cual los identifica en el cluster recibiendo los nombres de compute-0-0,compute-0-1, y compute-0-2 respectivamente.

Figura 3.2. Nodo 0

Figura 3.3. Nodo 1

Figura 3.4.Nodo 2


23/32

25

Ahora desde el FRONTED (servidor) accederemos a la lista de nodos mediante elcomando rockslist host el cual nos mostraruna lista como la siguiente:

Otra manera muy til para monitorear la conexin y correcto funcionamiento delcluster es mediante el Roll llamado Ganglia el cual muestra de manera grafica eluso que se le da al cluster y el rendimiento de este, ahora bien este Roll nosmuestra que todos los nodos se encuentran conectados al cluster y enfuncionamiento solo a la espera de recibir la carga que les sea asignada y de esaforma empezar a trabajar.

Las siguientes imgenes tomadas de Ganglia en el FRONTED muestran quetodos los nodos estn en lnea y el trabajo o la carga de cada uno de ellos tanto en

grupo como de forma individual

Figura 3.6. Grafica del Frontend en Ganglia

Figura 3.5. Nodos registrados en Rocks Cluster


24/32

26

Figura 3.7. Grafica del nodo 2 en Ganglia




25/32

27

Figura 3.10. Grafica global del cluter

Como se puede apreciar en las imgenes anteriores el cluster ya esta ensambladoy listo para nuestras pruebas.

Figura 3.11. Fotografa del cluster encendido y operando


26/32

28

3.4.2 FUNCIONABILIDAD DE LA PROGRAMACION PARALELA (MPI)

Las pruebas de paralelizacion sern realizadas con el siguiente cdigo:

#include

#include #include #define BUFSIZE 128#define TAG 0

int main(int argc, char *argv[]){char idstr[32];char buff[BUFSIZE];

int numprocs;int myid;int i;MPI_Status stat;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);MPI_Comm_rank(MPI_COMM_WORLD,&myid);If (myid == 0){

Printf ("%d: We have %d processors\n", myid, numprocs);

For (i=1;i


27/32

29

Sprint (idstr, "Processor %d ", myid);Strncat (buff, idstr, BUFSIZE-1);Strncat (buff, "reporting for duty\n", BUFSIZE-1);/* send to rank 0: */MPI_Send (buff, BUFSIZE, MPI_CHAR, 0, TAG, MPI_COMM_WORLD);

}MPI_Finalize();return 0;

}

El cual una vez compilado recibir el nombre de ejemplo.

Y un script sencillo el cual indica al servidor en cuales nodos se ejecutaran losprocesos que sern ejecutados llamado nodos el cual contiene el siguiente

contenido:

Compute-0-0Compute-0-1Compute-0-2

Este script tan sencillo es muy til para la ejecucin de programas de carcterparalelo en rocks cluster en esta ocasin lo nombraremos como nodos para suuso posterior en la ejecucin de nuestra prueba.


28/32

30

CAPITULO IV ANLISIS DE RESULTADOS

Los resultados de la prueba de paralelizacion no fueron los deseados debido aque el cluster no logra hacer el trabajo que se le indica que haga como se muestraen la siguiente imagen:

Figura 4.1. Error al ejecutar el cdigo Prueba

Al revisar la grafica de procesos en ganglia se encontr que los nodos a los que semandado el trabajo de procesamiento no lo recibieron en ningn momento.


29/32

31

Figura 4.2. Distribucin de carga durante la ejecucin

Como se puede ver todos los procesos se llevan a cabo solo en el servidor y lasotras computadoras no hacen ningn trabajo a pesar de que se les dio la orden enel script nodos de que fueran solo los nodos y no el servidor el que hiciera el

trabajo.

Se realizo una segunda prueba con un cdigo ms sencillo para evitar errores en

la programacin que pudieran afectar la ejecucin paralelizada del mismo siendoel cdigo siguiente el empleado para esta prueba:

#include #include int main (int argc, char *argv[]){int lnom;char nombrepr [MPI_MAX_PROCESSOR_NAME];cat circuint pid, npr;

int A = 2; // identificador y numero de proc.MPI_Init (&argc, &argv);MPI_Comm_size (MPI_COMM_WORLD, &npr);MPI_Comm_rank (MPI_COMM_WORLD, &pid);MPI_Get_processor_name (nombrepr, &lnom);

A = A + 1;


30/32

32

Printf (" >> Proceso %2d de %2d activado en %s, A = %d\n", pid, npr, nombrepr,A);MPI_Finalize ();return 0;}

En este caso el programa ser compilado y nombrado prog.exeY los resultados arrojados fueron los siguientes:

Figura 4.3. Resultado de la ejecucin de prog.exe

Exactamente el mismo error que arrojo la prueba anterior lo que despeja la dudaacerca de errores en la codificacin.

Y nuevamente en ganglia se muestra que las pruebas no hacen ningn intento pormandar datos a los nodos lo cual es curioso considerando que se puede acceder alos nodos lo cual se hace con el comando SSH como se muestra a continuacin.

Como se observa la imagen muestra que se tiene acceso al nodo -0-0directamente desde el servidor principal del cluster y de la misma manera sepuede accesar a los otros nodos lo que hace que el error en la ejecucin de losprogramas sea algo extrao puesto que inclusive en ganglia se muestra que todoslos nodos estn en lnea y funcionales.


31/32

33

Figura 4.4. Acceso al nodo -0-0

Luego de varias pruebas para lograr que el cluster paralelizara los datos, se optopor parchear el kernel de CentOS con Mosix el cual es un parche que permite a uncluster distribuir la carga de trabajo de forma equilibrada para su ejecucinparalela.

Se procedi a instalar el parche pero una vez instalado nos encontramos con unerror, debido a que el parche no se instala correctamente y solo cicla nuestrosistema al inicio impidindole arrancar y mostrando solo una imagen negra en elmonitor.


32/32

34

CAPITULO V CONCLUSIONES Y RECOMENDACIONES

Conclusin

En conclusin la presente investigacin no obtuvo los resultados esperados,debido a ciertos errores generados en la etapa de pruebas del cluster.

Debido a que el cluster fue ineficiente en su funcin de balanceo de carga en losnodos, la investigacin no llego a hacer uso de los mtodos de ordenamiento,puesto que, el cluster no tuvo buenos resultados en la etapa de pruebasmostrando resultados inesperados a la hora de la ejecucin de programas yscripts.

Los resultados obtenidos muestran que el cluster a pesar de estar configuradocorrectamente, no responde a las necesidades de forma adecuada y a pesar dehaber optado por otras opciones de paralelizacion los resultados siguieronarrojando que la carga no se distribuye de manera adecuada, haciendo que laejecucin solo se realice en el servidor y no en los nodos.

Debido a la falta de tiempo y recursos para dar solucin a los errores presentadosen esta investigacin dejamos la presente documentacin a futuros interesadospara la posible culminacin de este proyecto.

Recomendaciones

Utilizar un sistema operativo y un software para cluster que sean altamentecompatibles y de los cuales se haya tenido xito en su implementacin para podertener una referencia mucho ms fiable si se presentan inconvenientes en laimplementacin

Documents

Estado Del Arte