Practica 02 Clustering de Datos Con Hilos Bajo UNIX

ESCOM-IPN (Sistemas Operativos II - Practica 02)
Prof. Edgardo Adrián Franco Martínez

Página 1 de 6
INSTITUTO POLITÉCNICO NACIONAL

ESCUELA SUPERIOR DE CÓMPUTO
Practica 02 de Sistemas Operativos II
Profr. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco
Septiembre 2010
Practica 02 “Clustering de datos con hilos bajo UNIX”
Objetivo
Construir una aplicación paralela basada en procesos ligeros (hilos), capaz de agrupar un conjunto
cuantioso de datos de manera eficiente. Para lograrlo se deberá dominar el concepto y manejo de
los llamados procesos ligeros (hilos) en UNIX, logrando con ello comprender la importancia de
utilizarlos para problemas donde es necesario reducir el tiempo de cómputo significativamente,
aprovechando las capacidades multinúcleo de los equipos de computo modernos.
Introducción
Un algoritmo de agrupamiento (clustering) es un procedimiento de agrupación de una serie de
vectores de acuerdo con un criterio de cercanía. Esta cercanía se define en términos de una
determinada función de distancia, como la euclídea, aunque existen otras más robustas o que
permiten extenderla a variables discretas.
Generalmente, los vectores de un mismo grupo (o clústers) comparten propiedades comunes. El

conocimiento de los grupos puede permitir una descripción sintética de un conjunto de datos
multidimensional complejo. De ahí el uso de algoritmos de agrupamiento en minería de datos. Esta
descripción sintética se consigue sustituyendo la descripción de todos los elementos de un grupo por
la de un representante característico del mismo.
Existen diversas técnicas de agrupamiento. Se dividen en dos grandes categorías:
 Jerárquicas, que construyen una jerarquía de grupos escindiéndolos iterativamente.

 De particionamiento, en los que el número de grupos se determina de antemano y las
observaciones se van asignando a los grupos en función de su cercanía.
Existen diversas implementaciones de algoritmos concretos. Por ejemplo, el de las k-medias, de

particionamiento. Es uno de los más antiguos pero uso extendido a pesar de sus carencias y falta de
robustez.
Agrupación con k-medias

El algoritmo de k-medias en clustering es el referente principal entre los diversos métodos para
seleccionar grupos representativos entre los datos.
Dado un conjunto finito de patrones X, el problema de agrupamiento en X consiste en asignar

etiquetas a los patrones que identifiquen subgrupos naturales en el conjunto. Debido a que los
Página 2 de 6
patrones no están inicialmente etiquetados, este problema es frecuentemente conocido como

aprendizaje no supervisado, con la palabra aprendizaje significando la búsqueda de etiquetas que
formen “buenos” clusters. El objetivo es partir X en un cierto número K de subconjuntos naturales y
homogéneos, donde los elementos de cada conjunto son tan similares como sea posible entre ellos y
que, al mismo tiempo, sean lo más distintos posibles a los demás integrantes de X. El número K
puede ser fijado de antemano o puede ser obtenido por medio de restricciones físicas o
matemáticas.
El algoritmo de k-medias es sencillo, pero muy eficiente, siempre que el número de clases se
conozca a priori con exactitud.
Existen una serie matrices que constituyen el fundamento para la implementación de este algoritmo.
- Matriz de datos de entrenamiento : ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗

- Matriz de distancias
- Matriz de centros: ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗
- Matriz de pertenencias
Partiendo de la matriz de datos a clasificar ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗ y del conjunto de elementos de la
clase j {⃗| ⃗ ⃗⃗⃗⃗ } el algoritmo de k-medias, realiza las siguientes operaciones.
1.- Inicialización: En el tiempo t=0, elija el número de clases K y sus respectivos centros ⃗⃗⃗⃗ .
2.- Distribución de los datos de entrenamiento: ⃗⃗⃗⃗ si ⃗⃗⃗⃗ ⃗⃗⃗⃗

⃗⃗⃗⃗ ⃗⃗⃗
3.- Cálculo de nuevos centros: ⃗⃗⃗⃗ ∑ ⃗⃗⃗⃗ con
4.- Verificación de convergencia: si ⃗⃗⃗⃗ ⃗⃗⃗⃗ parar, de lo contrario regresar al paso 2.
Figura 1 "Datos de ejemplo"

Página 3 de 6
Al aplicar el algoritmo de k-medias, sobre los datos de la figura con K=2, se encuentra que el valor de
los centros es C1(1,1) y C2(7,5.5).
Los procesos ligeros (hilos)

Un hilo tiene muchas similitudes con un proceso, aunque conceptualmente es un subconjunto de un
proceso. Así, un proceso puede contener varios hilos pero un hilo no puede contener varios
procesos. La diferencia más importante entre ambos reside en que un proceso tiene un espacio de
memoria único que no puede ser accedido por otro proceso, a menos que se implemente un
mecanismo de IPC (comunicación entre procesos). En el caso de los hilos, de manera intrínseca se
tiene una región de memoria común a todos ellos (sección de datos, código y montículo). Así dentro
de un proceso puede haber varios hilos de ejecución modificando la misma variable, sin necesidad
de un programa adicional.
Figura 2: Los hilos comparten la sección de variables globales (global data), código (code) y montículo (heap)
Manejos de hilos POSIX

Librería de hilos POSIX
#include <pthread.h>
Los hilos POSIX son referenciados por un ID de tipo pthread_t. Cualquier hilo puede conocer su
ID invocando a:
pthread_t pthread_self(void);
Esta función retorna el ID del hilo que la invoca, no tiene errores definidos.
Creando un hilo (create)
La función pthread_create crea un hilo. Esta función automáticamente pone en ejecución el hilo
que crea.
int pthread_create( pthread_t *thread, const pthread_attr_t *attr, void

*(*start_routine)(void *), void *arg);
Página 4 de 6
El parámetro thread apunta al ID del hilo recientemente creado. El parámetro attr representa un
objeto atributo que encapsula los atributos de un hilo. Si attr es NULL, el hilo nuevo tendrá los
atributos asignados por defecto. El tercer parámetro, start_routine, es el nombre de la función
que es invocada por el hilo cuando comienza su ejecución. La función start_routine recibe solo
un parámetro el cual es especificado por el parámetro arg.
Si pthread_create se ejecuta satisfactoriamente retorna 0. Si la rutina no se ejecuta

satisfactoriamente retorna un código de error diferente de cero. A continuación se muestra una tabla
con los errores que puede generar una invocación a pthread.
Error Causa
EAGAIN El sistema no posee los recursos necesarios para crear el nuevo
hilo, o se excede el límite total del número de hilos permitidos por
el sistema.
EINVAL El parámetro attr es inválido
EPERM No se tienen los permisos suficientes para cambiar la política de
planificación o cualquier otro parámetro especificado en attr
Unir (join)
Esta función espera por la culminación de algún hilo. La función pthread_join suspende la ejecución del
hilo que la invoca hasta que el hilo objetivo , especificado por el primer parámetro, termine. El parámetro
valor_ptr es un apuntador al valor de retorno que el hilo objetivo pasa a la función pthread_exit o a
return. Si value_ptr es NULL, el hilo que invoca join no se recibe el valor de retorno del hilo objetivo.
int pthread_join( pthread_t, void **value_ptr );
Si la función termina exitosamente retorna 0. Si no termina exitosamente retorna un valor de error

diferente de cero.
Error Causa
EINVAL El hilo no corresponde a un hilo disponible para la unión
ESRCH No existe un hilo identificado por ID
Planteamiento del problema

Paralelizar el algoritmo de k-medias en datos, i.e. se deberá de buscar las partes del algoritmo donde
se realiza un procesamiento del mismo tipo sobre todos los datos de entrada.
 Cálculo de las distancias a los centros de cada dato y cálculo de las pertenencias
En una segunda etapa busque también paralelizar el cálculo de los nuevos centros.
Revisar el código que se proporciona y muestre los resultados con el conjunto de datos de prueba
del iris_data (también se proporciona), buscado 3 y 5 clases sobre los datos.
Página 5 de 6
Versión Secuencial Versión con Hilos

Inicio Inicio
Leer el número Leer el número

de centros, los de centros, los
datos e datos e
inicializar la inicializar la
matriz de matriz de
centros. centros.
Calcula Calcula Paralelizar la operación de

distancias distancias cálculo de distancias
Calcula Calcula Paralelizar la operación de

pertenencias pertenencias cálculo de pertenencias
Paralelizar la operación de
Calcula centros Calcula centros
cálculo de nuevos centros.
Si Los centros han

Si
Los centros han
cambiado cambiado
No No
Fin Fin
Figura 3: Proceso a realizar k-medias (Secuencial y con Hilos)
Requerimientos
• Portada
• Introducción
• Planteamiento del problema
• Diseño y funcionamiento de la solución (Descripción de la abstracción del problema y su

solución, apoyándose de diagramas y figuras en un lenguaje claro). *Explicando a detalle
cómo se paralelizo el tratamiento de los datos más que en que consiste el algoritmo de k-
medias (No es tema de la materia).
Página 6 de 6
• Implementación de la solución (Según la solución diseñada como se implementó en el

lenguaje de programación)
• Funcionamiento (Verificación de la solución, pruebas y resultados de salida *Pantallazos)
• Gráfica de tiempos secuencial contra versión con 1 hilo (Tiempo vs Versiones).
• Grafica de rendimiento según el número de hilos (Tiempo vs Hilos).
• Interpretación y explicación del porqué de los tiempos recabados.
• Errores detectados (Si existe algún error detectado, el cuál no fue posible resolver o se
desconoce el motivo y solo ocurre con ciertas condiciones es necesario describirlo)
• Posibles mejoras (Describir posibles disminuciones de código en la implementación u otras

posibles soluciones)
• Conclusiones (Por cada integrante del equipo)
• Anexo (Códigos fuente *con colores e instrucciones de compilación)
• Bibliografía (En formato IEEE)
Observaciones
 El reporte deberá de dar énfasis a los resultados de tiempo, por lo que es importante reportar
las características del equipo donde fue probado.
 Reportar graficas de rendimiento para el conjunto de datos iris_data, probando con 3 y 5
centros.
Fechas de entrega del programa

 Miércoles 08 de Septiembre en laboratorio (Grupo 5CV3)
 Viernes 10 de Septiembre en laboratorio (Grupo 5CV2)
Fechas de entrega del reporte

A más tardar el lunes 13 de septiembre de 2010 a las 23:59:59 horas a través de la página web.
(Enviar en un archivo comprimido código fuente y reporte únicamente).
*No hay prorrogas, ya que se cerrará la calificación del 1er Parcial el día Martes 14 de Septiembre.
http://computacion.cs.cinvestav.mx/~efranco/?p=recepcion_trabajos/index.php
Grupo Usuario Contraseña
5CV2 5cv2so2 2sistemasop2010
5CV3 5cv3so2 3sistemasop2010

Practica 02 Clustering de Datos Con Hilos Bajo UNIX

Cargado por

Copyright:

Formatos disponibles

Practica 02 Clustering de Datos Con Hilos Bajo UNIX

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Practica 02 Clustering de Datos Con Hilos Bajo UNIX

Cargado por

Copyright:

Formatos disponibles

ESCOM-IPN (Sistemas Operativos II - Practica 02)

Prof. Edgardo Adrián Franco Martínez

INSTITUTO POLITÉCNICO NACIONAL

Generalmente, los vectores de un mismo grupo (o clústers) comparten propiedades comunes. El

Existen diversas técnicas de agrupamiento. Se dividen en dos grandes categorías:

 Jerárquicas, que construyen una jerarquía de grupos escindiéndolos iterativamente.

Existen diversas implementaciones de algoritmos concretos. Por ejemplo, el de las k-medias, de

Agrupación con k-medias

Dado un conjunto finito de patrones X, el problema de agrupamiento en X consiste en asignar

patrones no están inicialmente etiquetados, este problema es frecuentemente conocido como

- Matriz de datos de entrenamiento : ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗

2.- Distribución de los datos de entrenamiento: ⃗⃗⃗⃗ si ⃗⃗⃗⃗ ⃗⃗⃗⃗

3.- Cálculo de nuevos centros: ⃗⃗⃗⃗ ∑ ⃗⃗⃗⃗ con

4.- Verificación de convergencia: si ⃗⃗⃗⃗ ⃗⃗⃗⃗ parar, de lo contrario regresar al paso 2.

Figura 1 "Datos de ejemplo"

Los procesos ligeros (hilos)

Manejos de hilos POSIX

Creando un hilo (create)

int pthread_create( pthread_t *thread, const pthread_attr_t *attr, void

Si pthread_create se ejecuta satisfactoriamente retorna 0. Si la rutina no se ejecuta

int pthread_join( pthread_t, void **value_ptr );

Si la función termina exitosamente retorna 0. Si no termina exitosamente retorna un valor de error

Planteamiento del problema

Versión Secuencial Versión con Hilos

Leer el número Leer el número

Calcula Calcula Paralelizar la operación de

Calcula Calcula Paralelizar la operación de

Si Los centros han

Figura 3: Proceso a realizar k-medias (Secuencial y con Hilos)

• Planteamiento del problema

• Diseño y funcionamiento de la solución (Descripción de la abstracción del problema y su

• Implementación de la solución (Según la solución diseñada como se implementó en el

• Funcionamiento (Verificación de la solución, pruebas y resultados de salida *Pantallazos)

• Gráfica de tiempos secuencial contra versión con 1 hilo (Tiempo vs Versiones).

• Grafica de rendimiento según el número de hilos (Tiempo vs Hilos).

• Interpretación y explicación del porqué de los tiempos recabados.

• Posibles mejoras (Describir posibles disminuciones de código en la implementación u otras

• Conclusiones (Por cada integrante del equipo)

• Anexo (Códigos fuente *con colores e instrucciones de compilación)

• Bibliografía (En formato IEEE)

Fechas de entrega del programa

Fechas de entrega del reporte

Grupo Usuario Contraseña

5CV2 5cv2so2 2sistemasop2010

5CV3 5cv3so2 3sistemasop2010

También podría gustarte

int pthread_create( pthread_t thread, const pthread_attr_t attr, void