Project progress

In this post, I will publish links of different things that I have been doing during the semester for the project group of distributed and parallel systems.

Week 16: Presentation.


I made a presentation, is the topics that we made during the semester, also I  put a different graphics about why is important parallel and distributed systems using parallel python and gnuplot.





Week 15: Grid computacional con jcGrid


Mi aportación para esta semana, es como configurar el midleware de Java Grid Computing, para poder ser servidor, expongo los pasos en el apartado del wiki de Grid, al igual que tambien pongo informacion de las consideraciones del diseño de un Grid computacional.


Aqui una captura de pantalla con el jcGrid server ya configurado.

Week 14: Math Kernel Library LINPACK Intel



Linpack es elegido por la pagina top 500 para obtener cifras de rendimiento en gigaflops, lo que hace es resolver un sistema de ecuaciones lineales denso, por lo que al medir este rendimiento real de diferentes tamaños del problema, podemos obtener los numeros que figuran en esta página, pongo las instrucciones en el wiki de como poder correr esta herramienta para ponerlo en el cluster.




Week 13: Phoronix Test Suite


Para esta semana, estuve investigando como podemos medir el rendimiento de manera óptima para nuestro cluster, por lo que encontré una herramienta interesante en el cual tiene numerosas pruebas de diferentes usos, por lo que la usé en mi computadora e hice algunos test para ver el comportamiento, al igual que puse como utilizarla e instalarla.


Más información en el wiki.


Nominaciones
Cecy.


Week 12: Comunicación de Sistemas Distribuidos


Para esta semana, hice un apartado en el wiki en donde puse información de los diversos protocolos que se utilizan en la comunicación de sistemas distribuidos, como las Redes ATM, Llamadas a procedimientos remotos y cliente-servidor, al igual que puse unos ejemplos de los cuales ya habia realizado.

Nominaciones: Cecilia, JC, Carmen




Week 11: Petri Net


I made a contribution in the wiki about Petri Net, I put important information and describe a Petri Net, and also I made a simulation use a tool call it tapaal in ubuntu.


Please check the wiki for more details.

Nominaciones:
Juan
Cecy




Week 10: Ruby paralelo
           For this week, I made how to use ruby with a gems, for make programs with       parallelism, also, I put two examples and check a benchmark with different uses.


Week 9: Comportamiento paralelo
           Realicé graficas checando el comportamiento paralelo y secuencial utilizando    gnuplot y parallel python, hice un pequeño cluster en mi casa y obtuve algunos resultados, luego los grafiqué y realicé algunas conclusiones en el wiki.


Para más información verifiquen el wiki


Nominaciones: Cecy


Week 8: Propuesta de aplicación : Blender
            Estuve trabajando con Blender un renderizador de graficos 3D
            Para mas información verifiquen el wiki


            Nominaciones: Juan Carlos & Cecy


Week 7: [Exam] - Make a custom distribution

For this week, I made a tutorial for make a custom distribution, I hope this tutorial help to people that work in cluster.

        Also, I went to the meeting with the cluster group for make a plan about the    
        project.


Week 6: Pyro
       
       Programa sencillo utiizando la herramienta Pyro para python, de manera remota poder 
       calcular las funciones trigonométricas.


      Nominaciones: Rafita, juan y cecy


Week 5: Chat multithread

I put a code that is a Chat using threads in python in socket section.

Week 4: Sockets in python (Wiki) [Feb 23] (in Spanish)

I have been working on make an Chat application for supercomputer, so for this week I made a code in python using sockets, it is the first part of the code that I going to make for the next week. Also I put some comments and important information about sockets that my classmates who wants to make something in sockets they can use it.

Also Cecy Urbina, Saul Gaussin and me try Parallel Python at school, we use the example code and see the differences between running parallel and sequence in sum_prime.py, so, we show in class and we can use it for our project, here some screenshots from Saul's computer that have i5 core and Cecy and me use Atom.

Week 3: Matrix Multiplication (Wiki) [Feb 14, 2012]

I made a code in python using threads for make a matrix multiplication, in the example make a two matrix 3x3 using integer random numbers (0-9), we can change those numbers and use this code to check cluster

          Nominations: Gaby, Cecy


Week 2: Principles of Parallel Algorithm Design (Wiki) [Feb 7, 2012]

I publish an different concepts about principles of parallel algorithm, that i think it is important for make a good reports for next weeks.
I talk about that we have two key steps in the design of parallel algorithms, splitting a computation into littler computations and designating them to different processors for make parallel executions, differences between parallel Algorithm vs parallel Formulation and Elements of a Parallel Algorithm/Formulation also concepts like Decomposition, Tasks, Granualarity, Fine-grained & Coarse-grained, Task-Dependecy Graph, Task-Iteraction Graph and different examples for explain better those concepts.

           Parallel Computer Memory Architectures  (Blog) (Lab) [Feb 7, 2012]

Concept map

Week 1: Merge sort (in Spanish) (Blog) [Jan 31, 2012]

Extra Points

• Security
• The objective of computer security includes protection of information and property from theft, corruption, or natural disaster, while allowing the information and property to remain accessible and productive to its intended users.
• Source
• Any thing of place from which something comes or is obtained, origin.
• Broadcast
• Refers to a method of transferring a message to all recipients simultaneously.
• Frame
• Is a digital data transmission unit or data packet that includes frame synchronization, for example, a sequence of bits or symbols making it possible for the receiver to dectect the beginning and end of the packet in the stream of symbols or bits.
• Update
• To bring up to date information.

Ruby en paralelo

Para la aportación de esta semana, hablaré acerca de un lenguaje de programación, llamado Ruby, algunos de mis compañeros tal vez ya lo conozcan ya que recuerdo que vimos algo de ello en lenguajes de programación hace algunos semestres.

Ruby es un lenguaje de programación que abarca diferentes paradigmas entre ellos podemos decir, que Ruby es un lenguaje interpretado, reflexivo y también orientado a objetos, inspirado en Python y Perl, para esta entrada hablaré de como poder utilizar este lenguaje en forma paralela.

Ruby por default viene instalado en sistemas operativos de Mac OS a diferencia de Ubuntu, en donde para instarlo debemos de seguir el tipico comando.

Luego de instalarlo, existe un gestor de paquetes para el lenguaje de programación Ruby, llamado RubyGems, en donde podemos portar librerías para Ruby, por lo que necesitamos instalarlo para poder tener la extensión paralela, por lo que pondremos en el terminal.

Ahora con todo esto, lo que necesitamos es la estensión paralela de ruby, para eso simplemente vamos a utilizar el siguiente comando (Ahora lo pondré en Mac OS, pero es lo mismo que en Ubuntu).

Ahora que tenemos todo instalado, vamos a probar si esto funciona correctamente, la extensión parallel para ruby es poderosa, ya que podemos correr cualquier código en procesos paralelos, para utilizar los recursos del CPU o tambien utilizar hilos, así generando código más eficiente.

Para este caso, modifiqué un código realizado aquí en donde se realiza un benchmark entre como de una forma secuencial, mandamos ping host a diferentes páginas web, luego por medio de hilos, luego por medio de bifuración, como lo hemos visto en la materia, teniendo los siguientes resultados.

Obteniendo resultados favorables al utilizar Hilos y Forks, por lo que podemos ver considerablemente el cambio en tiempo.

PD: ara poder hacer funcionar el código pongan cambien las páginas hosts, pongan otras, las que ustedes quieran, porque las que vienen en el ejemplo, hay 2 que ya no existen.

Expongo el código.

require 'rubygems'
require 'parallel'
require 'net/http'
require 'benchmark'


hacer_ping = lambda { |host| 10.times { Net::HTTP.new(host).head('/') } }
puts "#{Parallel.processor_count} procesador(es)"
hosts = ['www.facebook.com', 'www.google.com', 'www.yahoo.com', 'www.uanl.mx', 'www.wikipedia.org', 'www.ruby-lang.org']

Benchmark.bm do |x|
  x.report('Normal') { 
    hosts.each &hacer_ping
  }
  x.report('Hilos') { 
    Parallel.each(hosts, :in_threads => Parallel.processor_count, &hacer_ping)
  }
  x.report('Forks') { 
    Parallel.each(hosts, &hacer_ping)
  }
end 

Ahora modifiqué el código para que hiciera una simple división 100 millones de veces
Expongo el código.

require 'rubygems'
require 'parallel'
require 'benchmark'

div = lambda { 100000000.times { 4.0/2.0 } }
puts "#{Parallel.processor_count} procesador(es)"
 
Benchmark.bm do |x|
  x.report('Normal') { 
    hosts.each &div
  }
  x.report('Hilos') { 
    Parallel.each(hosts, :in_threads => Parallel.processor_count, &div)
  }
  x.report('Forks') { 
    Parallel.each(hosts, &div)
  }
end

Y aquí los resultados.

Computación distribuida en Python usando Pyro

¿Que es Pyro?
Pyro es una librería de python que podemos utilizar para nuestro proyecto de la materia de paralelos y distribuidos, ya que nos permite construir aplicaciones en donde podemos crear objetos que se comuniquen entre ellos mismos atraves de la red, de una manera relativamente fácil.


Podemos hacer llamadas de métodos normales de Python, con casi cualquier parámetro posible y obtendremos una respuesta, con Pyro lo que hace es localizar el objeto para poder ejecutar el método, por lo que tendremos un conjunto de herramientas permitiendonos construir aplicaciones distribuidas muy fácilmente.


Pyro está escrito 100% en python.


Para instalar Pyro simplemente lo puedes descargar desde su pagina (aquí)
Ahí mismo pueden encontrar la documentación la cual viene muy completa.


Según la documentación de Pyro tienen algunos benchmark usando su código.

"2000 connections in 1.139 sec = 1756 conn/sec
2000 new proxy calls in 1.451 sec = 1378 calls/sec
10000 calls in 1.058 sec = 9452 calls/sec" [Aquí has info] 

 Por lo que podemos ver que es relativamente rápido.


Mi aportación de esta semana consiste en realizar un programa utilizando esta librería, para ello hice un código en el cual se hacen llamadas para obtener las funciones trigonométricas.


Para eso, primero que nada realicé un código que me devolviera dichos valores.






Luego necesitamos un servidor, para el cual utilizo las librerías de Pyro.





Y por ultimo el cliente





Por lo que, necesitamos para correrlo, primeramente nombrar el servidor, por lo que vamos a poner en el terminar, en la carpeta donde tengas el código "pyro-ns"

Luego en otra terminal vamos a ejecutar el servidor.

Y en otra terminal vamos a ejecutar el cliente el cual llama a las funciones trigonométricas.

Aquí podemos ver las tres terminales, para que también puedan ejecutarlo.

Como ven es muy sencillo, con esto podemos hacer lo que vimos en clase de RMI, al igual que hacer el computo PI o mandar mensajes.


Esto es todo por mi parte.

Semana 1: Reporte - Ordenamiento por mezcla

Introducción.

Anteriormente, los diseñadores que hacían algoritmos asumían que una computadora solamente tenía un elemento a procesar, este tipo de algoritmos que se diseñan con este propósito son llamados secuenciales, ya que hacen una secuencia particular siguiendo ciertos pasos. 

Pero ahora, una computadora sencilla o incluso laptops, actualmente tienen múltiples procesadores, también existen clusters de computadoras los cuales por ejemplo, en el departamento de defensa de los Estados Unidos simulan una explosión nuclear y Google procesa sus búsquedas en ese tipo de computadoras. Por ejemplo, para el año pasado (2011), la Fujitsu K es considerada la supercomputadora más rápida del mundo con 68544 CPUs.

Supongamos, que cuando estemos graduados y trabajemos en el mundo real, nos encontraremos con problemas que necesitamos resolver con un sistema multiprocesador, por ejemplo, si tuviéramos una matriz de enteros y queremos poner todos los números enteros negativos en la matriz, podemos dividir la matriz en segmentos de igual tamaño, un segmento por cada procesador y el procesador de cada uno puede mostrar todos los números enteros negativos de su segmento, el algoritmo que utilizaríamos secuencialmente tomaría Θ(n), si utilizáramos el algoritmo multiprocesador cada procesador se encarga de un segmento de la matriz con un máximo de n / p elementos, por lo que el procesamiento de toda la matriz toma Θ(n/p).

Pero existen problemas de los cuales es difícil imaginar y diseñar el uso de múltiples procesadores para acelerar el tiempo de procesamiento, un ejemplo de esto es el orden de búsqueda a profundidad de un grafo: cualquier algoritmo se verá obligado a procesar a un nodo hijo sólo después de su nodo padre, así que, si la altura de la grafo fuera como n / 2,  es necesariamente Θ(n), En esta liga puedes ver dónde se demuestra que este problema es intrínsecamente secuencial. 

Modelos paralelos y distribuidos.

Existen diferentes sistemas con múltiples procesadores, pero hay dos categorías básicas: las computadoras paralelas y las computadoras distribuidas, de las cuales estaremos hablando durante todo el curso y en mi caso profundizar conceptos algorítmicos para los sistemas y como pueden ayudarnos para resolver problemas en el futuro laborar, éstos dos términos se utilizan con algunas coincidencias, pero por lo general un sistema paralelo, es aquél en el que los procesadores están estrechamente relacionados, mientras  que un sistema distribuido tiene procesadores que son más independientes el uno del otro.

Análisis de un algoritmo de multiproceso.

Ahora, para mi aportación de esta semana haré un análisis de un algoritmo multiproceso, lo cual escogí el que se me facilitara en entender para en semanas mas adelantes, ir viendo algoritmos mas complejos.

Un algoritmo de divide y vencerás, divide el problema a resolver en subproblemas, que son más fáciles de resolver que el problema original, resuelve los subproblemas y se combina las soluciones a los subproblemas para construir una solución al problema original.

El paradigma de divide y vencerás mejora la modularidad del programa y lleva a menudo a algoritmos simples y eficientes, por ello se ha demostrado ser una poderosa herramienta para los diseñadores de algoritmos secuenciales.

Divide y vencerás juega un papel aún más importante en el diseño de algoritmos paralelos, debido a que los subproblemas creados en el primer paso son regularmente independientes, pueden ser resueltos de forma paralela, a menudo los subproblemas se resuelven de forma recursiva, a consecuencia de esto, incluso los algoritmos de dividir y vencerás que se han diseñado para las computadoras secuenciales suelen tener algún paralelismo inherente. 

Como ejemplo de algoritmo utilizando divide y vencerás, haré un análisis del algoritmo de ordenamiento por mezcla de forma secuencial, para luego verlo de una perspectiva paralela.

El ordenamiento por mezcla, produce una secuencia ordenada por la clasificación de sus dos mitades y su mezcla. 

Tiene un tiempo de complejidad de Θ(n log(n)) y la complejidad en el espacio es Θ(n).

En primer lugar, la secuencia a ordenar se descompone en dos partes (divide), cada mitad esta ordenada de forma independiente (conquista o vence), a continuación, las dos mitades se arreglan ordenadamente (mezcla).

Podemos ver que este algoritmo resalta la importancia de la operación de intercalación:

Mergesort(A[1, n])
Merge( MergeSort(A[1, ⌊n/2⌋]), MergeSort(A[⌊n/2⌋ + 1, n]) )

El caso base de la recursión, es cuando consta en ordenar a un solo elemento, por lo tanto no es posible la reorganización. 

Un seguimiento de la ejecución de la ordenación por mezcla.

Primero, se determina un índice intermedio entre alto y bajo, después va de bajo a medio, de medio más uno a alto recursivamente, luego las dos mitades se mezclan ordenados por un procedimiento de mezcla, la recursión termina, cuando bajo es igual a alto, esto quiere decir que solo hay un elemento.

ordenMezcla(int bajo, int alto){
    if (bajo<alto) {

        int medio = (bajo+alto) / 2;
        ordenMezcla(bajo, medio);
        ordenMezcla(medio+1, alto);
        mezcla(bajo, medio alto);
    }
}

La eficiencia de este algoritmo, depende de la eficiencia con que se mezclan las dos mitades ordenadas, en una sola lista ordenada, para esto existen diferentes métodos, el cual yo escribiré es el más óptimo.

La variante mas óptima de mezcla, no copia todo el arreglo a otro, por lo tanto solo utiliza la mitad de espacio de memoria y también solo la mitad del tiempo, para copiar elementos de un arreglo auxiliar, entonces cuando todos los elementos de la primera mitad se han copiado de nuevo a una, los elementos restantes ya no se necesitan mover porque están en sus lugares adecuados, esto es como si se creara un espacio auxiliar para realizar las operaciones.

mezcla(int bajo, int medio, int alto) {
    int i, j, k;
    i=0;    
    j=bajo;
    
   //Primero la primera mitad se copia en un array auxiliar 
    while (j<=medio)
        auxiliar[i++]=arreglo[j++];
    i=0; 
    k=bajo;
    
    // Se copia el próximo elemento a cada rato.
    while (k < j && j <= alto)
        if (auxiliar[i]<=arreglo[j])
            arreglo[k++] = auxiliar[i++];
        else
            arreglo[k++] = arreglo[j++];
    // copia los elementos de la primera mitad (si es que hay)
    while (k<j)
        arreglo[k++] = auxiliar[i++];
}

En esta variante eficiente, la función mezcla 1.5n pasos, o sea, n / 2 pasos para copiar la primera mitad al array auxiliar, n / 2 pasos para copiar de nuevo al arreglo y n / 2 pasos para la segunda mitad, esto produce un tiempo de ejecución de ordenación por mezcla de 1.5n log(n) pasos.

Un inconveniente es que necesita un espacio adicional de Θ(n) para el array auxiliar, pero como utilizamos el más eficiente, solo se necesita la mitad de este espacio, siendo más rápido y estable que otras variantes.

Por lo tanto el tiempo de ejecución puede ser especificado por la recurrencia:

Cuya solución es que el algoritmo tiene una complejidad en tiempo de Θ(n log(n)) es óptimo.

Ordenamiento mezcla en paralelo.

Ahora explicaré como paralelizar el algoritmo de ordenamiento por mezcla, como podemos ver por obvias razones, el paralelismo de este algoritmo depende directamente de como es la rutina de mezcla, la cual también puede ser paralela, aunque sea el algoritmo secuencial, este ya tiene un paralelismo inherente ya que permite realizar dos llamadas recursivas independientes.

La forma mas sencilla de poner en paralelo el algoritmo es como se muestra en el siguiente pseudocodigo:

ordenMezcla(int bajo, int alto){
    if (bajo<alto) {
        int medio = (bajo+alto) / 2;
        spawn ordenMezcla(bajo, medio);
        spawn ordenMezcla(medio+1, alto);
        sync;
        mezcla(bajo, medio, alto);
    }
}

Suponiendo, que la función mezcla es secuencial para que el trabajo y la profundidad de mezclar dos elementos ordenados de n / 2 sea Θ(n),  así que en ordenMezcla el trabajo y su profundidad esta dado por:

Obtuvimos como solución el mismo que el tiempo para el algoritmo secuencial Θ(n log(n)) para el trabajo, pero por el lado de la profundidad, la solución es D(n) = Θ(n) que es menor que el trabajo, por lo tanto el paralelismo de este algoritmo es Θ(log n), el problema aquí es que la etapa de mezcla sigue siendo secuencial.

Usando una combinación en paralelo de las dos secuencias ordenadas, se puede combinar con el trabajo Θ(n) y la profundidad Θ(log log n)

Para el uso de este algoritmo de mezcla, la recurrencia de profundidad sería:

cuya solución es D(n) = Θ(log n log log n), usando una técnica llamada "pipelined divde-and-conquer", la profundidad del ordenMezcla puede reducirse hasta Θ(log n).

Divide y vencerás ha demostrado ser, una de las técnicas más poderosas para la solución de problemas en paralelo, se pueden resolver problemas de geometría computacional, la clasificación de elementos, la realización rápida de las transformadas de Fourier, resolución de sistemas lineales para factorizar grandes números, etc...

Espero que haya quedado entendible, tardé en entender cada una de las cosas, espero y verifiquen lo que investigué y si algo no queda muy claro, les pongo los recursos de donde obtuve esta información.

The Algorithm Design Manual - Steven S. Skiena - Springer
Parallel Algorithms - Guy E. Blelloch - Carnegie Mellon University
Sequential and parallel sorting algorithms - Hans wener Lang - FH flensburg
A Minicourse on Dynamic Multithreaded Algorithms - Charles E. Leiserson - MIT

Animaciones aqui.

Videos del MIT "Introduction to Algorithms" Lecturas 20 y 21 hablan sobre algoritmos paralelos y hablan sobre el ordenamiento de mezcla en paralelo en el minuto 43:30 de la lectura 21.

 

Nominaciones: 

Esteban.

Aveldaño

Cecy