8 de abril de 2012

Extra Points 2

Distributed and Parallel Systems
Extra Points 2
  • Equal: Identical in size, quantity, degree, intensity. The same.
  • Complexity: Expresses a condition of numerous elements in a system and numerous forms of relationships among the elements.
  • Output: Is the term denoting either an exit or changes which exit a system and which modify a process.
  • Atomic: A part or particle considered to be an irreducible constituent of a specified system.
  • Group: Any collection or assemblage of persons or things.

7 de abril de 2012

Week 11

Distributed and Parallel Systems
Contribution: Week 11
Continuando con lo que estuve investigando la semana pasada acerca del modelo WRF para predicción del tiempo atmosférico y el clima, y cuya información se encuentra en la misma publicación pasada, ahora complemento directamente en el wiki la página donde ya había mencionado anteriormente la idea para proyecto de grupo. Anteriormente solo había escrito algo de información, algunas herramientas e instituciones que se encargan de este tipo de cosas, y ahora incluye ahí mismo un apartado para esta herramienta que encontré.

Ahí mismo están los enlaces a la página oficial y la parte del tutorial que encontré, que espero seguir poco a poco y ver si logro instalar bien todas las herramientas.

Enlace al wiki: Clima (Modified)

6 de abril de 2012

Extra Points

Distributed and Parallel Systems
Extra Points
Questions and answers of the midterm exam.

The questions 1 to 5 are in Cecilia Urbina's blog.

6. How do the computers that form a cluster communicate with one another?
A cluster is communicated by a network connection. There are some types, for example the Ethernet is very common to communicate computers in a cluster, and can use protocols like TCP/IP or sometimes UDP. Another connection used in supercomputers is the Myrinet that use optical fiber cables.

7. What difficulties may arise if the machines that form a cluster are not all identical?
The difference in the architecture and also the resource that are available in the computer, because the execution of one thread can be different if the processor is slower than another, and delay all the execution.

8. What factors affect the number of threads that can be efficiently executed on a GPU?
The number of the processors and how many cores they have, and the memory that can be accessed.

9. Will a cluster always improve its performance if more machines are included into it?
No, because there is a point when you add more hardware and the performance stays equal.

10. Give an example of a critical section in a parallel algorithm.
When access a part of the memory that is used by another thread.

11. Why is deadlock harder to detect in a distributed system than in a single-machine system.
Because is difficult to know in what computer and which processor is the thread doing a deadlock.

12. Give an example of how, in general terms, to distribute sorting.
Break in parts the array to be sorting. MergeSort an QuickSort are good examples because we break in two parts and then break again, and each part is sorting independently and when they finish return the array sorted and mix with the result of the previous thread and sort this.

13. Give an example of how, specifically, to distribute matrix multiplication.
When the matrix is big for example 10x10, we can cut in 4 matrices of 5x5 and each thread make a multiplication.

14. Name some of the difficulties in detecting faces in a single photograph using a computing cluster.
For detect a face in an image using a cluster, we need to send a part of the simple image in each thread, and then returns if the particular region of the image is a face or not. The difficulty is that all the computers in the cluster needs the same classifier trained on example faces, and the image database is only in the server and all the threads wants to access at the same time.

15. Describe in pseudocode how to implement the dining philosophers in a distributed system.
I don't write a pseudocode but I write some ideas about how the dining philosophers can be distributed.
First of all, the server says what philosophers can eat, because it have the counting of forks.
Each processor can be a philosopher waiting for the forks.
When a philosopher have two forks can eat, or execute a program. If take too much time, the server request the forks.
The server provide the fork to a different processor.
The server needs to know how much time one processor has been waiting, for avoid starvation.

I would do questions 6 to 10, but the following 5 questions I didn't see in another blog, so I add questions 11-15.

5 de abril de 2012

Week 10

Distributed and Parallel Systems
Contribution: Week 10
Ya había mencionado la sugerencia de la predicción del tiempo para el proyecto de grupo para esta clase de sistemas distribuidos y paralelos, pero no había encontrado gran cosa además de datos técnicos y puramente informativos.

Antes de entrar en el tema del proyecto me gustaría mencionar el como llegue a una herramienta que nos podrá ser de gran ayuda, si es que el grupo se decide ir por esta idea.

Ya que nosotros como proyecto mostraremos algún programa que corra en nuestro propio cluster, haciendo uso de las herramientas y conocimiento adquirido de cómputo paralelo, me puse a investigar que es lo que algunos centros de supercómputo en el país hacen. Encontrar centros de supercómputo fue fácil ya que en México hay varias universidades que tienen su propio centro, y que inclusive varias de ellas trabajan en conjunto para crear un complejo de computadoras, a pesar de que no estén en una misma área, pero bueno algo que me intereso fue información que encontré en la página de la universidad de Guadalajara.

CGTI - Universidad de Guadalajara

De esta página cito la definición que nos dan en la página de inicio del supercómputo:
"El supercómputo es la tecnología informática más avanzada de cálculo numérico que existe actualmente para desarrollar investigaciones complejas de alto nivel de especialización; es la única herramienta que le permite al investigador llevar a cabo, con certeza y velocidad, billones de cálculos matemáticos para estudiar problemas de gran magnitud."

La sección que nos interesa es la parte de infraestructura, donde primeramente podemos ver el equipo o hardware con el que ellos cuentan y que no es cualquier cosa.

La sección que me lleva un paso más al punto que quiero llegar en esta publicación es la parte del Software.

Entre las aplicaciones que se encuentran instaladas en sus clusters son:

Gaussian: Proporciona el estado de las capacidades de última generación para el modelado de la estructura electrónica.
Espresso: Es una suite integrada de códigos de computadora para cálculos de estructura electrónica de materiales y el modelado a nanoescala.
Siesta: Simulación electrónica con cúmulos de átomos.
PWscf (versión espresso-4.0.4): Simulación computacional de dinámica molecular.
WRF: Weather Research and Forecasting Model.
Amon: Herramientas de monitoreo para Wrf.
Aprof: Herramientas de monitoreo para Wrf.
Bechmark: Herramientas de monitoreo para Wrf.

Los modelos de paralelismo que usan son:
  • MPI
  • OpenMPI
  • Hdf5-Netcdf
  • Mpich2
También usan varios compiladores, entre los que se encuentran Gfortran, g++, PGI, Ncarg y Zlib.

Ahora pongamos atención a las aplicaciones que ellos utilizan, podemos notar que la mitad de ellas son para la predicción del clima.

Y es ahora donde llego a la parte de la predicción del clima, ellos usan el modelo "Weather Research and Forecasting" (WRF), y al investigar de que se trataba este modelo resulto que el modelo es un programa de computadora creado para facilitar la investigación y pronóstico del clima.

El WRF es posible instalarse en nuestras computadoras ya que es posible descargar el código fuente de la página oficial, y cabe mencionar que este programa es usado por muchas dependencias en los estados unidos, inclusive por estaciones militares. En realidad es una de las herramientas de pronóstico de clima más usado en el mundo, y es de alguna forma "libre".

La siguiente imagen es una muestra de lo que se puede obtener con esta herramienta y unas cuantas más que se tienen que instalar.


La animación proviende de wikipedia, donde podrán ver más información del WRF.

WRF - Wikipedia

Y la misma página de la universidad de Guadalajara tiene el sistema funcionando y podemos ver las animaciones que se están produciendo. Por lo menos desde hoy en pronóstico de precipitaciones llega hasta dos días adelante, por lo que podemos cerciorarnos de que no es solo una simple animación.

Clic para ver en vivo el pronóstico


Entonces ahora sabemos que existe una herramienta para el pronóstico del tiempo, ya que evidentemente no vamos a crear algo nuevo en esa área ya que involucra muchos años de investigación, acerca de los patrones del clima, nosotros solo haremos el uso de la herramienta, y la acoplaremos a nuestro conjunto de computadoras para que los resultados estén disponibles en tiempo real.

Además como todo buen paquete de código, la página oficial de WRF tiene su propio tutorial para poner a andar el programa y vienen con algunos ejemplos de datos para pronósticos de algunos fenómenos naturales sucedidos hace algunos años, los cuáles podemos probar.

Ya le di una revisada a todo el tutorial, es un poco extenso, debido a que hay varias cosas que instalar y otras cosas a configurar, pero de eso hablaré en la próxima entrada.

4 de abril de 2012

Week 9

Distributed and Parallel Systems
Contribution: Week 9
Mientras buscaba algo de implementaciones al computo paralelo, encontré un caso de estudio llamado "Tuple Space", del cual me disponía a hablar, pero al estar leyendo acerca de él, vi un ejemplo de este caso en un lenguaje llamado Linda, y como me causó curiosidad investigué y encontré que fue creado especialmente para el computo distribuido. De este existe una versión para Python llamado PyLinda, y es de lo que hablo esta semana en el wiki.

Enlace al wiki: PyLinda


Para complementar la aportación aquí hay un resumen de lo que es el lenguaje Linda y las acciones que se hacen con el, y su caso representativo el del espacio de tuplas.

Linda tiene varias extensiones o versiones para diferentes lenguajes entre ellos tenemos a Python, C y Java, que suelen ser comunes en el ámbito de la programación.

El concepto sobresaliente de Linda es el espacio de tuplas, que sin entrar en definiciones exactas, es el espacio por el cual los procesos se comunican, y es de ahí de donde comparten información la cual todos los procesos están usando en algún momento.

Una tupla puede ser un campo de variables de un mismo tipo donde los procesos mandan la información obtenida.

Linda tiene 4 primicias que son:
out - para añadir datos al espacio de tuplas
eval - evaluar una cierta instancia y luego se agrega
rd - leer u obtener elementos
inn - elimina un elemento


Los círculos son los procesos y la mancha del centro es la tupla donde están almacenados los datos obtenidos.

Y como no podía faltar un vídeo que nos de una mejor idea de lo del espacio de tuplas.


Bibliografía
Linda en PDF

3 de abril de 2012

Sistemas Caóticos

Modelado y Simulación de Sistemas Dinámicos
Reporte 4
Reporte que explica en qué sentido el fenómeno que estás estudiando tiene características de un sistema caótico y qué implicaciones tiene esto en su modelado.

Programa que contiene uno o los dos de los elementos siguientes: (a) análisis de datos reales que indica que se trata de un señal caótico (típicamente una serie de tiempo, pero podría ser otra cosa) y (b) sistema de ecuaciones u otro modelo "artificial" para el fenómeno que da lugar a cáos - ambos (a) y (b) incluyendo código fuente y alguna ilustración de lo que se obtuvo.

Introducción


De lo que trata en pocas palabras la teoría del caos, es que ciertos tipos de sistemas dinámicos son muy sensibles a las variaciones en las condiciones o variables iniciales de un modelo.

Estas pequeñas modificaciones al inicio, provocan diferencias muy significativas y totalmente distintas en un comportamiento futuro, lo que complica la predicción a largo plazo.

Y para no empezar solamente a copiar texto de otras fuentes, y como siempre ayudan de mucho, encontré un vídeo excelente donde explican qué es el caos, y dónde lo podemos encontrar.


Algo de lo que puedo resumir con mis palabras acerca de este vídeo y el concepto de teoría del caos, es que en la naturaleza existen muchos modelos cuantitativos, donde la medición del tiempo, o el momento en el que pasa cierto evento, es muy importante y fundamental para todo el sistema.

Los sistemas en los que el tiempo es fundamental, son los que llamamos sistemas dinámicos, por ejemplo el clima o predicción del tiempo es un modelo donde interviene el tiempo, y es completamente caótico, porque solo unos pequeños cambios en condiciones iniciales de un sistema de pronóstico del tiempo, pueden hacer surgir condiciones atmosféricas totalmente distintas.

Un modelo matemático es muy complicado porque las mediciones que el investigador hace acerca del estado inicial de un modelo, nunca tiene una medición perfecta, y cambios completamente insignificantes pueden producir un resultado totalmente distintos, a esto le llamamos caos.

Hablar de ejemplos no caóticos son también muy buenos para entender que sí lo es.

Por ejemplos tenemos el péndulo o el lanzamiento de un proyectil. Lo que nos hace decir con seguridad que estos no son sistemas caóticos, mencionando el ejemplo del proyectil, es porque si una de las variables que están involucradas, como el ángulo de lanzamiento, es alterado muy poco, el proyectil aun caería en una zona totalmente cercana al punto al que se quisiera lanzar. En cambio en el sistema caótico esto no pasaría.

Hay algo llamado Familia Logística, que sirve para evaluar un modelo a lo largo del tiempo, como el crecimiento de población, y algo de ello también es aplicado al tema de la economía. En una entrada anterior hice algo acerca de la familia logística para el crecimiento de población.

Análisis de cambio monetario


La siguiente imagen puede ser un tanto cómica, por la relación que hacemos del concepto del caos y el tan conocido efecto mariposa, pero nos da una idea de la realidad del problema, porque a lo que se refiere en el aleteo de la mariposa puede ser cambiado por algún evento simple que este involucrado con los cambios de la economía, como el de la venta de algún producto en un país, lo cual provoque que en otro resulte la caída de la bolsa, cosas que podrían parecer no asociarse, pero sin tal vez puede ser verdadero.

En la siguiente página encontré algunos datos que me sirvieron de base para analizar este caso. Los datos dan como resultado una gráfica de Dolar contra Euro, y aquí esta tal y como en la página.

Economic Time Series


Cuando un sistema es caótico su comportamiento es altamente complejo e impredecible a largo plazo debido a que cualquier pequeña modificación se amplifica por el propio sistema. Sin embargo, a corto plazo, se puede predecir.

Para demostrar que a corto plazo un sistema como el presentado puede ser predecible, tome un modelo cualquiera para analizar los datos.

La función dada para este modelo es f(x) = 4x^3 - 3x, y lo que hice para demostrar que es un ejemplo de modelo caótico fue crear un programa que me diera los valores obtenidos para ochenta iteraciones y después poder graficar con dos diferentes valores iniciales de x.

El programa usado fue el siguiente:


El resultado para a = 2 es:


Y el resultado para a = 2.00001 es:


Lo que se puede decir de las dos gráficas es que después de cierta iteración empiezan a haber cambios muy drásticos en comparación de una con otra, sin embargo en un inicio parecían ser iguales.

Para ver mucho mejor el cambio de una con otra, hice un programa que me devolviera en un archivo la diferencia de los valores dados por las dos gráficas y luego grafique para analizar.

Este fue el programa para comparar:


Y obtuve lo siguiente:


Como se puede notar, en las primeras iteraciones no hay cambio significativo en los valores, pero llega al punto donde se disparan valores muy diferentes.

Con esto llego a la conclusión de que es posible predecir a corto plazo los valores para un modelo. Es decir, que para el caso concreto de una serie de datos en economía, si se logra saber a que modelo se acerca más, sería posible estimar los valores siguientes, pero resultaría malo para cuando se desea saber más a futuro.

Modelo no lineal


En economía, para caracterizar y predecir el comportamiento de las series temporales, tradicionalmente se utilizan modelos lineales, pero suelen producir comportamientos muy simples que obligan a introducir perturbaciones aleatorias para que resulten más reales. Este es el motivo que ha llevado al equipo a optar por modelos no lineales y, en particular, por los caóticos.

Estas técnicas matemáticas tienen la propiedad de mostrar comportamientos muy diferentes a lo largo del tiempo ante variaciones muy pequeñas de las condiciones iniciales.

Para este caso observe trabajos parecidos como el de el siguiente pdf, donde usan una función logística.

Chaos Models in Economics

Una función logística como se menciona en el vídeo del inicio, es muy utilizada para comprender los cambios caóticos en economía, por eso basado en lo que ya había probado en el caso de población, hice otro pequeño programa para obtener los datos con la función y después graficar con gnuplot.


Resultado para a = 0.018


Resultado para a = 0.019


Entonces la mayoría de los casos que se presentan en vida real en la economía suelen ser de tipo caótico, ya que aunque se conocen los parámetros iniciales cercanos al real para un cierto modelo, es difícil conocer el comportamiento a largo plazo, y solo como ya mencione, se podría conocer a un corto plazo, pero esto no es de gran ayuda en economía, porque lo que realmente se necesita es conocer que pasará en meses y no días.

Bibliografía
Teoría del Caos
Caos en el mercado
Caos en series de tiempo

2 de abril de 2012

Pruebas Estadísticas para Números Pseudoaleatorios

Modelado y Simulación de Sistemas Dinámicos
Reporte 3
A través de investigación en línea, elige una librería de generación de números pseudoaleatorios y pruebas estadísticas. Implementa a base de esto un programa para determinar: a) si los números generados de acoplan a la distribución indicada y b) si se puede considerar que los números generados presentan características deseables de "números aleatorios". Reporta los resultados junto con los mecanismos que seleccionaste.

Herramientas utilizadas
  • Octave - Lenguaje de programación utilizado
  • Gnuplot - Para creación de gráficas
Generación de números pseudoaleatorios

Dado a que use Octave para hacer mi tarea, y además de que trate de no repetir generadores de números pseudoaleatorios con distribuciones que mis compañeros ya habían usado en su tarea, tome la función para generar números pseudoaleatorios con la Distribución Beta.

La función es llamada de la siguiente forma.
betarnd(alpha, beta)
La cual nos regresa un número aleatorio de punto flotante entre 0 y 1.

Y cuya función de densidad esta dada por la siguiente forma.


¿Los números generados de acoplan a la distribución indicada?

Para saber si los números generados en verdad se acoplan a la distribución dada, lo que hice fue crear un pequeño programa en octave que genera una cantidad N de números aleatorios en la distribución beta, dándole como parámetros el valor de alfa = 2 y beta = 2.

Estos valores generados los iba ubicando en "canastas", para después graficar y saber si se parecía a la función.

En un principio lidie un poco con la parte de cual función era la correcta, pero en la página de la Wikipedia vienen unas gráficas y sus respectivos valores de alfa y beta dados, y en primera instancia compare directamente con esa gráfica que es la siguiente.


Y que para los valores que yo di, debería de parecerse a la de la línea color aqua.

Mi programa fue el siguiente.


Y con los datos recabados desde el anterior grafique directo con gnuplot para obtener lo siguiente.

betadis(1000, 100)

betadis(10000, 100)

Hasta ese momento fue un suspiro ver que mientras más aumentaba la cantidad de repeticiones, que son la cantidad de números generados, para un total de 100 canastas, los puntos marcados se acercaban más a la gráfica de la función.

Luego hice algo diferente, gracias a la idea de Juan Carlos para graficar y comparar directamente con la gráfica de la función, que por cierto es la de Función de Densidad. Primero cree un archivo con 10mil números aleatorios con la distribución.


Para después con Gnuplot crear un histograma y ahí mismo colocar la función de densidad para la distribución beta.


El resultado en imagen fue el siguiente.


Y con la imagen anterior, llegué a la conclusión de que el generador de números pseudoaleatorios, si se acopla a la distribución beta.


¿Los números generados presentan características deseables de números aleatorios?

Ahora faltaba hacer alguna prueba para verificar que los números generados tienen la característica de números aleatorios.

Al final esta el enlace a la página donde se encuentran todos las pruebas que se consideran como excelentes para verificar esto, también en el PDF de Statistical Test Suite, ahi vienen explicados todos las pruebas, así como en la página de random.org.

Hice la prueba de frecuencia por bloques, que trata de verificar que la cantidad de ceros y unos por bloque de un arreglo total de números sea pareja.

Donde la cantidad de bloques N esta dado por n/m, donde n es el número de elementos, y m la cantidad de elementos por bloque.


Al correr esta prueba, obtuve que el generador paso por lo menos esta de las tantas pruebas que hay, y probé con esa cantidad en los parámetros, intente con más pero tardo mucho y cancele.


Y esto fue todo, pero por último menciono como dato, que en Gnuplot y Octave la función log, es tomada como logaritmo natural, y para el logaritmo base 10 la función es log10, cosa que casi me mete en problemas, pero en los tutoriales encontré esa información.

Recursos consultados
Tutorial Gnuplot
Tutorial Octave
Statistical Test Suite
Distribución Beta
Pruebas estadísticas