jueves, 29 de marzo de 2012

Pruebas estadísticas para los números pseudoaleatorios

Lenguaje  a utilizar 


Python


Librería de generación de números pseudoaleatorios


La librería que seleccioné es random de Python, la función random.expovariate(lambd), que el parámetro lambd es un número diferente de 0.


Pruebas 
estadísticas


La prueba estadistica que elegí es: Anderson-Darling
Esta prueba se sefine como:
  • H0: Los datos siguen la distribución especifica(en mi caso exponencial)
  • Ha: Los datos no siguen la solución especifica(en mi caso exponencial)
Esta prueba la apliqué en Python con la librería scipy, módulo stats, función anderson(x, dist='norm'), los parámetros que entran son x = es el arreglo, dist, que es el nombre de la distribución en mi caso 'expon'.

Y los valores que regresa son A2 que es un float , es el valor de la prueba Anderson Darling, critical que es una lista de valores críticos de la distribución, y sig que es el nivel de significancia para el valor crítico correspondiente. La función regresa un valor crítico para diferentes niveles de significancia dependiendo del test.

Esta prueba estadística nos dará el valor de A2 y los valores críticos, estos son los que vamos a comparar para saber si se rechaza o no la hipótesis
Y en la misma librería viene una nota muy importante, que se relaciona con la definición de la prueba Aderson que dice, "Si A2 es más grande que los valores criticos de cada correspondiente nivel de significancia, la hipotesis nula de que los datos provienen de la distrubución elegida puede ser rechazada "


Generar números con python




Ahora vemos el resultado de una ejecución:


Con este resultado podemos ver que en esta prueba no se rechazaron las Hipótesis nulas, entonces los datos están siguiendo  la distribución exponencial.

Características deseables de números aleatorios


He leído algunas sobre las características que se espera que cumplan los números aleatorios, y hay una de ellas que me a llamado la atención, la leí en un documento propuesto por la Doctora, para la solución de esta misma tarea. Esto dice algo así: "a good random number generator will also produce sequences that look nonrandom to the human eye (e.g., a series of ten rolls of six on our die) and which also fail any statistical tests that we might expose it to. ", es decir un buen generador de números aleatorios también producirá secuencias que parecen no aleatorias para el ojo humano y que tampoco sigue pruebas estadísticas.

Entonces para poder concluir si la distribución exponencial es un buen generador de números aleatorios, decidí correr varias veces el programa anterior, para ver si el test siempre dice que sigue la distribución exponencial, o sí hay veces que dice que no la sigue, si es así para mi es suficiente para decir que generar números aleatorios con distribución exponencial es una buena opción. Veamos el programa:



Y lo que vemos es lo siguiente:



Podemos ver que aveces se rechaza la hipótesis nula, pero aveces no, entonces puedo decir que si cumple con características de números aleatorios


Referencias


Scipy, Scipy2
Aleatorios
Teoría Anderson Darling Test




viernes, 23 de marzo de 2012

Embarazosamente paralelos

En los llamados problemas embarazosamente paralelos, un cálculo consiste en una serie de tareas que pueden ejecutar más o menos independiente, sin la comunicación. Estos problemas suelen ser fáciles de adaptar para la ejecución en paralelo. Un ejemplo es un estudio de parámetros, en la que el mismo cálculo debe llevarse a cabo utilizando una gama de parámetros de entrada diferentes. Los valores de los parámetros se leen de un archivo de entrada, y los resultados de los cálculos diferentes se escriben en un fichero de salida.


Trabajadores (W) parámetros de la petición de la tarea de entrada (I) y enviar los resultados a la tarea de salida (O). Tenga en cuenta las conexiones de muchos a uno: este programa no es determinista en el que las tareas de entrada y salida de recibir los datos de los trabajadores en el orden que los datos que se generan. Canales de respuesta, representadas como líneas discontinuas, se utilizan para comunicar los parámetros de la tarea de entrada para los trabajadores.
Si el tiempo de ejecución por problema es constante y cada procesador tiene la misma potencia de cálculo, a continuación, basta con problemas de partición disponibles en conjuntos de igual tamaño y asignar un conjunto tal que cada procesador.  Las tareas de entrada y salida son responsables de la lectura y escritura de los archivos de entrada y salida, respectivamente. Cada tarea de los trabajadores (por lo general una por procesador) varias veces pide valores de los parámetros de la tarea de entrada, calcula el uso de estos valores, y envía los resultados a la tarea de salida. Debido a los tiempos de ejecución varían, las tareas de entrada y salida no se puede esperar para recibir los mensajes de los distintos trabajadores en ningún orden en particular. En su lugar, una estructura de comunicación de muchos a uno se utiliza que les permite recibir mensajes de los diversos trabajadores en orden de llegada.

La tarea de entrada responde a una petición de los trabajadores mediante el envío de un parámetro con el trabajador. Por lo tanto, un trabajador que ha enviado una solicitud a la tarea de entrada, simplemente espera a que el parámetro para llegar a su canal de respuesta. En algunos casos, la eficiencia puede ser mejorada por prebúsqueda, es decir, que solicita el parámetro siguiente, antes de que sea necesario. El trabajador puede realizar el cálculo, mientras que su petición está siendo procesada por la tarea de entrada.

Debido a que este programa utiliza muchos-a-uno las estructuras de comunicación, el orden en que los cálculos se realizan no se determina necesariamente. Sin embargo, esto no determinismo sólo afecta a la asignación de los problemas a los trabajadores y la clasificación de los resultados en el archivo de salida no, los resultados reales calculadas.

Programar !! Python secuencial:

#!/usr/bin/python                                                                                                                                      
contador = 1
lista = []
resultados = []
f = open("entradas.txt")

#este rollo para sacar del archivo de entrada los numeritos                                                                                            
while True:
      linea = f.readline()
      if not linea: break
      print linea
      if contador % 2 != 0:
            lista.append(int(linea)) #amo python                                                                                                       

f.close()

print linea
f = open("salida.txt", "w")
for m in range(len(lista)):
      res = (lista[m])**2 #variable auxiliar que me ayuda a escribir en el array                                                                       
      resultados.append(res) #guardo en un arreglo, solo para debug                                                                                    
      cadena = str(res) + "\n" #lo que voy a poner en el archivo                                                                                       
      f.write(cadena) # escribo en el archivo                                                                                                          
f.close #lo cierro                                                                                                                                     

print lista
print resultados

Resultado :

Teminal


Archivo Salida.txt que se creo:

Python paralelo:
#!/usr/bin/python                                                                                                                                                                                                                                                               
import threading, time
import Queue

q = Queue.Queue()
o = Queue.Queue()
contador = 1

class cuadrado(threading.Thread):
      def __init__(self, num):
            threading.Thread.__init__(self)
            self.num = num
            self.res = 0

      def run(self):
            print "Calculando paralelamente los cuadrados"
            self.res = self.num ** 2
            o.put(self.res)



f = open("entradas.txt")

#este rollo para sacar del archivo de entrada los numeritos                                                                                                                                                                                                                     
while True:
      linea = f.readline()
      if not linea: break
      print linea
      if contador % 2 != 0:
            q.put(int(linea)) #ponemos en la cola                                                                                                                                                                                                                               
            print("Mando a llamar al hilo para que ejecute el cuadrado")
            h = cuadrado(int(linea))
            h.start()
            h.join()
f.close()


f = open("SALIDA.txt", "w")
print "Empiezo a escribir en el archivo"
for i in range(o.qsize()):
      cadena = str(o.get(i)) + "\n" #lo que voy a poner en el archivo                                                                                                                                                                                                           
      f.write(cadena) # escribo en el archivo                                                                                                                                                                                                                                   
f.close #lo cierro                                                                                                                                                                                                                                                              

Resultados:

Terminal



Archivo SALIDAS.txt







Más ejemplos

Algunos ejemplos de los problemas embarazosamente paralelos incluyen:


  • Consultas distribuidas de bases de datos relacionales utilizando el procesamiento distribuido conjunto
  • Servir archivos estáticos en un servidor web.
  • El conjunto de Mandelbrot y otros cálculos fractales, donde cada punto se puede calcular de forma independiente.
  • Representación de los gráficos por ordenador . En el trazado de rayos , cada píxel puede ser prestado de manera independiente. En la animación por ordenador , cada fotograma pueden ser prestados de manera independiente (véase la representación en paralelo )
  • Fuerza bruta búsquedas en la criptografía . Un notable ejemplo del mundo real es distributed.net .
  • BLAST búsquedas en bioinformática para las consultas de varios (pero no para consultas individuales de gran tamaño)
  • A gran escala de reconocimiento facial que consiste en la comparación de miles de entradas se enfrenta con el número igualmente grande de caras.
  • Las simulaciones por ordenador comparación de numerosos escenarios independientes, como los modelos climáticos.
  • Los algoritmos genéticos y otros de computación evolutiva metaheurísticas .
  • Ensemble cálculos de predicción numérica del tiempo .
  • Evento de simulación y reconstrucción de la física de partículas .
  • Tamizado paso de la criba cuadrática y el tamiz de número de campo .
  • Árbol de paso el crecimiento del bosque al azar técnica de aprendizaje automático.

Referencias

jueves, 22 de marzo de 2012

Java multitarea

Me ha parecido importante empezar a checar como sería hacer algunas cosas que puedo hacer  en Python, en Java, este post lo dedico a explicar como se crean y funcionan los hilos en Java, así como sincronizarlos, etcétera.

Los programas multihilo tienen dos o más partes que pueden ejecutarse de manera simultanea o concurrente. Cada parte del programa se llama hilo y cada hilo sigue un camino diferente. La programación multihilo es una manera especializada de multitarea.

Hay dos tipos de multitarea, a travez de procesos y atravez de hilos. Ambas son diferentes un proceso es un programa que se esta ejecutando, entonces la multitarea que se basa en procesos es la capacidad de las computadoras de ejecutar varios programas a la vez, el programa es la unidad más pequeña que el sistema de computo puede manejar.

La multitarea que se basa en hilos, el hilo es la unidad de código mas pequeño que se puede gestionar. Es decir un programa es capaz de ejecutar dos o más tareas en simultáneo. 

La multitarea que se basa en hilos tiene un menor costo de operación que las basadas en procesos. Los procesos requieren de más recursos  y necesitan espacio de direccionamieto propio. La comunicacion con procesos es costosa y limitada. Intercambiar contextos de procesos tambien es costoso. Mientras que los hilos son ligeros, comparten el mismo espacio de direccionamiento y el mismo proceso.

Los programas de Java usan entornos multitarea basados en procesos, pero esto no esta bajo control de Java. La multitarea de hilos si esta al control de Java. La multitarea que se basa en hilos permiten escribir programas eficientes que usan optimamente el CPU.

Clase Thread y la interfaz Runnable

El sistema multihilo de Java se crean en torno a la clase Thread, sus métodos y su interfaz Runnable. La clase Thread encapsula a un hilo de ejecución. Como no se puede hacer referencia directamente al estado de un hilo que se esta ejecutando es necesario usar la instancia a la clase Thread que representa a dicho hilo. Para hacer un hilo nuevo el programa debe extender a la clase Thread o implementar la interfaz Runnable.
La clase Thread define métodos que ayudan a manejar los hilos. Estos son algunos:
  • getName: Obtiene el nombre del hilo.
  • getPriority: Obtiene la prioridad del hilo.
  • isAlive: Determina si un hilo aún se esta ejecutando.
  • join: Espera a que termine un hilo.
  • run: Punto de entrada de un hilo.
  • sleep: Suspende a un hilo durante cierto tiempo.
  • start: Empieza al hilo llamando a run.
Hilo principal

Cuando los programas comienzan su ejecución, hay un hilo que se ejecuta automáticamenre, este es el hilo principal ya que es el único que se ejecuta al iniciar el programa. Este hilo es importante por dos razones:
  • A partir de este hilo será posible crear el resto de los hilos del programa.
  • Este es el último que finaliza su ejecución ya que debe de realizar ciertas acciones para terminar correctamente el programa.
Para controlar este hilo, hay que crear un objeto Thread, entonces se crea una referencia al mismo con el método currentThread(), que es un miembro public static de la clase Thread, su forma general es la siguiente:
static Thread currentThread()

Ese método devuelve una referencia al mismo hilo del que fué llamado. Una vez que se obtuvo la referencia al hilo principal es posible controlarlo como a cualquier otro hilo.

Ejemplo de Control de hilo principal

//controlamos el hilo principal                                                                                                                        

class hiloPrincipal{
    public static void main(String args[]){
        Thread t = Thread.currentThread();
        System.out.println("Hilo actual:" + t);
        //cambio del nombre del hilo                                                                                                                   
        t.setName("Hilo principal");
 System.out.println("Ahora se llama: " + t);
        try{
            for(int n = 5; n > 0; n--){
                System.out.println(n);
  Thread.sleep(1000);
            }

 }
        catch (InterruptedException e){
            System.out.println("Se interrumpio al hilo principal");
 }

    }

}

Con este programa obtenemos una referencia al hilo actual, llamando al método currentThread(), esta referencia la almacené en la variable local t. Llamamos al método setName() para poder cambiar el nombre interno del hilo.
El ciclo cuenta del 5 al 1 pausandose entre cada número 1 segundo, con el método sleep.

Creación de un hilo

Los hilos en Java se crean con el objeto del tipo Thread.java y hay dos maneras de hacer esto:
  • Implementando la interfaz Runnable.
  • Extendiendo la clase thread. 

Interfaz Runnable

La manera más facil de crear un hilo es creando una clase que implemente la interfaz Runnable, se puede construir un hilo desde cualquier objeto que implementa esta interfaz. La clase necesita implementar el método run(), que se declara asi:
public void run()
Dentro del método run(), se escribe el código que definirá un nuevo hilo.

Después de crear la clase, se crea el objeto de tipo Thread:
Thread(Runnable objeto Hilo, String nombreHilo)

El nuevo hilo que se creo no empezará su interfaz hasta que se llame al metodo start(), start() ejecuta una llamada al método run():
void start()

Ejemplo de creación de un hilo con Runnable:

//creacion de un segundo hilo                                                                                                                          
class HiloNuevo implements Runnable{
    Thread t;
    HiloNuevo(){
        t = new Thread(this, "HiloDemo");
        System.out.println("Hilo hijo: " + t);
        t.start(); //comienza el hilo                                                                                                                  
    }

    public void run(){
        try{
            for(int i = 5; i > 0; i--){
                System.out.println("Hilo hijo :" + i);
                Thread.sleep(500);
            }
        }catch(InterruptedException e){
            System.out.println("Salida del hilo hijo");
        }
    }
}
    class Hilo{
        public static void main(String args[]){
            new HiloNuevo();
            try{
                for(int i = 5; i > 0; i--){
                    System.out.println("Hilo principal: "+i);
                    Thread.sleep(1000);
                }
            }catch(InterruptedException e){
                System.out.println("Se interrumpe el hilo principal");
            }
            System.out.println("Salida del hilo principal");
        }

}

Resultado:



En este programa vemos que termina en último lugar el hilo principal, esto es porque lo altere para que así pasara, el hilo principal duerme más tiempo que el hilo hijo. En lo personal yo prefiero crear hilos implementando la interfaz Runnable me parece más fácil.

Creación de múltiples hilos

En los ejemplos anteriores solo había creado un hilo, sin embargo podemos crear tantos hijos como queramos. En el siguiente programa creo 3 hijos.

//creo 3 hijos                                                                                                                                                                                                                     

class HiloNuevo implements Runnable{
String nombre;
Thread t;

HiloNuevo(String nombreHilo){
nombre = nombreHilo;
t = new Thread(this, nombre);
System.out.println("Hilo nuevo "+ t);
t.start();
}

public void run(){
try{
for(int i=5; i>0;i--){
System.out.println(nombre +":" + i);
Thread.sleep(500);
}
}catch(InterruptedException e){
System.out.println("Interrupción del hilo" + nombre);
}
System.out.println("salida del hilo" + nombre);
}
}

class Hilos{
public static void main(String args[]){
new HiloNuevo("uno");
new HiloNuevo("dos");
new HiloNuevo("tres");
try{
//ESPERAMOS A QUE LOS OTROS HILOS TERMINEN                                                                                                                                                                             
Thread.sleep(10000);
}catch(InterruptedException e){
System.out.println("Interrupcion del hilo principal");
}
System.out.println("Salida del hilo principal");

}
}

Resultado:


Uso de isAlive() y join()

Como hemos visto en nuestros programas le decimos al hilo principal que duerma más tiempo que los demás para que no termine antes, pero esto no es muy conveniente ya que nosotros suponemos que en ese lapso de tiempo terminaran los demás, pero y si no es así?, para eso tenemos el método isAlive() que es un método definido por la clase Thread y su forma general es la siguiente:
final boolean isAlive().
Este método devuelve el valor True si el hilo al que se hace referencia aún se esta ejecutando, y devuelve false en caso contrario.
Ese método es útil en algunos casos, pero hay otro método más común join(), que se utiliza para esperar a que un hilo termine. Su forma general es:
final void join() throws InterruptedException
Ese método espera a que termine el hilo sobre el que se realizo la llamada. Su nombre viene de que el hilo llamante espera a que el hilo especificado se reuna con el. Otras formas de join permiten especificar el máximo tiempo de espera para que termine el hilo.

Ejemplo de isAlive y join()

//usamos jin para esperar a que terminen                                                                                                                                                                                                                                                                                                                                                                                                                              

class NuevoHilo implements Runnable{
    String nombre;
    Thread t;
    NuevoHilo(String nom){
        nombre = nom;
        t = new Thread(this, nombre);
        System.out.println("Nuevo hilo: "+ t);
        t.start();
    }
    //aqui entra el hilo                                                                                                                                                                                                                                                                                                                                                                                                                                              
    public void run(){
        try{
            for(int i=5; i>0; i--){
                System.out.println(nombre + ": " +i);
                Thread.sleep(1000);
            }
        }catch(InterruptedException e){
            System.out.println("Interrupcion del hilo " + nombre);
        }
        System.out.println("Sale el hilo "+ nombre);
    }
}
class DemoJoin{
    public static void main (String args[]){
        NuevoHilo ob1 = new NuevoHilo("uno");
        NuevoHilo ob2 = new NuevoHilo("dos");
        NuevoHilo ob3 = new NuevoHilo("tres");
        System.out.println("El hilo uno esta vivo " + ob1.t.isAlive());
        System.out.println("El hilo dos esta vivo " + ob2.t.isAlive());
        System.out.println("El hilo tres esta vivo " + ob3.t.isAlive());
        //espera a que los otros hilos terminen                                                                                                                                                                                                                                                                                                                                                                                                                       
        try{
            System.out.println("Espera a que finalizen los otros hilos");
            ob1.t.join();
            ob2.t.join();
            ob3.t.join();

        }catch(InterruptedException e){
        System.out.println("El hilo uno esta vivo " + ob1.t.isAlive());
        System.out.println("El hilo dos esta vivo " + ob2.t.isAlive());
        System.out.println("El hilo tres esta vivo " + ob3.t.isAlive());
        System.out.println("El hilo principal termina");
        }


}



}

Resultado



Prioridades de los hilos

El planificador de hilos usa las prioridades de los hilos para poder decidir cuando se va a permitir la ejecución de cada hilo. Los hilos que tienen prioridad más alta tienen mayor tiempo del CPU que los de prioridad baja. Un hilo de prioridad alta puede desalojar a uno de prioridad más baja. Por ejemplo, cuando un hilo de prioridad mas baja se esta ejecutando y otro  de prioridad más alta reanuda su ejecución, este segundo desalojará al de prioridad más baja.
Los hilos con la misma prioridad tienen el mismo acceso al CPU.
Para establecer la prioridad de un  hilo se utiliza setPriority(), que es miembro de la clase Thread,. Su forma general es:
final void setPriority(int nivel)
En donde nivel es la nueva prioridad del hilo. El valor del nivel debe de estar entre MIN_PRIORITY y MAX_PRIORITY. Actualmente estos valores son 1 y 10. Para establecer la prioridad por default que tienen los hilos de nuevo se usa NORM_PRIORITY, es  5.
Para obtener la prioridad de un hilo usamos getPriority() de Thread:
final int getPriority

Sincronización

En Java la sincronización parece sencilla ya que cada hilo tiene su propio monitor implícito asociado. Para entrar al monitor basta con llamar a un método modificado con la palabra clave synchronized. Mientras hay un hilo dentro de un método sincronizado, todos los demás hilos que tratan de llamar a ese método, o a otro método sincronizado sobre la misma instancia, tienen que esperar. Para salir del monitor simplemente hay que salir del método sincronizado.
La palabra clave synchronized, permite que un hilo acceda a un método sin interrupciones, aunque otros hilos quieran usarlo.

Comunicación entre hilos
  • wait() Indica al hilo que realiza la llamada que debe abandonar al monitor y quedar suspendido hasta que algún otro hilo llame al método notify()
  • notify() Activa a un hilo que previamente llamo a while en el mismo objeto.
  • notify all() Activa todos los hilos que llamaron previamente a wait() en el mismo objeto. Uno de esos hilos empezar a ejecutarse.
Los métodos se llaman asi:
final void wait()
final void notify()
final void notifyAll()

Productor consumidor en Java

class Q{
    int n;
    synchronized int get(){
        System.out.println("Consume: "+ n);
        return n;
    }
    synchronized void put(int n){
        this.n = n;
        System.out.println("Produce: "+ n);
    }
}

class Productor implements Runnable{
    Q q;
    Productor(Q q){
        this.q = q;
        new Thread(this, "Productor").start();
    }
    public void run(){
        int i = 0;
        while(true){
            q.put(i++);
        }
    }

}

class Consumidor implements Runnable{
    Q q;
    Consumidor(Q q){
        this.q = q;
        new Thread(this, "Consumidor").start();

    }

    public void run(){
        while(true){
            q.get();
        }
    }

}

class PC{
    public static void main(String args[]){
        Q q = new Q();
        new Productor(q);
        new Consumidor(q);
        System.out.println("control c para finalizar");

    }

}

En ese programa aunque se sincronizan los métodos put y get nada impide que el productor vaya más rápido que el consumidor, ni que el consumidor recolecte el mismo valor de la cola dos veces. Entonces la implementación correcta del productor consumidor es usando wait() y notify().
En el siguiente código muestro como hacerlo:

//productor consumidor simple                                                                                                                                                                                                                                                                                                                                                                                                                                         

class Q{
    int n;
    boolean valueSet = false;

    synchronized int get(){
        while(!valueSet)
            try{
                wait();
            }catch(InterruptedException e){
                System.out.println("captura de la excepcion");
            }
            System.out.println("Consume: " + n);
            valueSet = false;
            notify();
            return n;

    }
    synchronized void put(int n){
        while(valueSet)
            try{
                wait();
            }catch(InterruptedException e){
                System.out.println("Captura de la excepcion");
            }
        this.n = n;
        valueSet = true;
        System.out.println("Produce: "+ n);
        notify();
    }
}

class Productor implements Runnable{
    Q q;
    Productor(Q q){
        this.q = q;
        new Thread(this, "Productor").start();
    }
    public void run(){
        int i = 0;
        while(true){
            q.put(i++);
        }
    }

}

class Consumidor implements Runnable{
    Q q;
    Consumidor(Q q){
        this.q = q;
        new Thread(this, "Consumidor").start();

    }

    public void run(){
        while(true){
            q.get();
        }
    }

}

class PC{
    public static void main(String args[]){
        Q q = new Q();
        new Productor(q);
        new Consumidor(q);
        System.out.println("control c para finalizar");

    }

}

Resultado:


Finalmente, he aprendido a hacer programas multitarea en Java ahora podré aportar al equipo, si así se requiere programación en Java también  :) .

Semana 8

Proyecto grupal final Ideas

Platiqué con algunos de mis compañeros que si fueron a la junta y me hablaron tentativamente del proyecto que estaremos realizando como entrega final, basandonos en las funcionalidades que hace esta página http://www.leetcode.com/ y distribuyendo el trabajo en varias computadoras para mandar las respuesta necesaria.


Y propongo algunas buenas herramientas y lenguajes que debemos usar para esto:

Parallel Python: Me parece una herramienta excelente para que haga el trabajo de distribuir y paralelizar el código en un cluster, así nosotros no nos preocuparíamos de muchas cosas, además de que ya gente en el grupo hemos estado trabajando con la herramienta y estamos familiarizados con ella.

Javascript: Usar JS + HTML5 + CSS , será posible crear el aspecto de estar verdaderamente en alguna terminal ejecutando código, creo que debemos empezar a ver este aspecto ya que aparentemente será el más fácil pero no lo debemos dejar para el último momento.

Dispy: es un marco, desarrollado en Python, para la ejecución en paralelo de los cálculos mediante la distribución de ellos a través de múltiples procesadores en una sola máquina (SMP), entre muchas máquinas en un clúster, la red o las nubes. Dispy es muy adecuado para los datos de paralelismo (SIMD paradigma) cuando se evalúa un cálculo con diferentes (grande) conjuntos de datos de forma independiente.  

Nominaciones:

Solamente a Roberto Carlos y Gabriela Martínez(entrada sobre junta)por ponerme al tanto con la junta.

(si esque esto deba de ir en el wiki, estoy tratando aún de recordar mi contraseña)


miércoles, 21 de marzo de 2012

Semana 7

Esta semana me dí a la tarea de investigar cuando es correcto paralelizar código, esto debido a que como estoy en el equipo que debe programar es importante saber cuando si se puede hacer y cuando no.
Y las cosas que debemos saber para cuando este listo el cluster y poder pasar los programas que simulan procesos en hilos a programas que se ejecuten en procesos de diferentes máquinas.

Se tiene que analizar si se cuenta con el hardware y software necesario para determinar se si vale la pena paralelizar el programa o viceversa.

En cuestiones de equipamiento el proceso de paralelizar un programa nos exigira conocer un poco más de la arquitectura de la supercomputadora o "cluster" sobre el cual pretende paralelizar su código, conocer con cuantos procesadores se cuenta, la cantidad de memoria, espacio en disco, los niveles de memoria disponible, el medio de interconexión, etc.

En términos de software debemos conocer qué sistema operativo se manejará, si los compiladores instalados permiten realizar aplicaciones con paralelismo, si se cuenta con herramientas como PVM o MPI en sistemas distribuidos.



Para saber si vale la pena el paralelismo en un programa, podemos identificar nuestra situación con las siguientes justificaciones:


1.Necesidad de respuesta inmediata de resultados.

Si el usuario está usando un programa en una máquina secuencial, y necesita ejecutarlo en varias ocasiones con datos de entrada diferentes, y el tiempo de ejecución es considerable (consume horas o días) le es molesto esperar tanto tiempo para volver a realizar otro experimento o someterlos secuencialmente que al final disminuirá notablemente el desempeño de su máquina. Esto sin considerar las modificaciones al código o fallas en la ejecución del modelo. La paralelización y la ejecución del programa en una máquina paralela permitirá realizar más análisis o experimentos en menos tiempo.

2.Es un problema de Gran Reto.

Un programa puede presentar algoritmos de cálculo científico intensivo que demanden grandes recursos de cómputo (CPU, memoria, disco), en estos casos el dicho de "divide y vencerás" bien se puede aplicar, las tareas se dividen entre varios procesadores, se ejecutan en paralelo y se obtiene una mejora en la relación costo y desempeño. Hoy en día las arquitecturas de cómputo estan incorporando paralelismo en los más altos niveles de sus sistemas, para satisfacer las exigencias de los problemas de grandes retos.

3.Simplemente elegancia de programación.

Es completamente válido.

Para implementar paralelismo a un programa es muy importante que el código presente:

Independencia de datos. Como programadores  debemos saber  identificar tareas independientes dentro del código, por ejemplo, revisar que existan ciclos for o do independientes, y rutinas o módulos independientes. De tal forma que no exista dependencias de datos que puedan obstruir la paralelización.
Que el programador identifique las zonas donde se efectúa la mayor carga de trabajo y que le consuma la mayor parte de tiempo de ejecución.

Es todo por esta semana espero, mis compañeros se den la oportunidad de leerlo, ya que menciono algunos puntos que debemos tener en cuenta para empezar a hacer que nuestro código corra en clústers y saber cuando vale la pena paralelizar.


Referencias

Paralelización

martes, 20 de marzo de 2012

Configuración Arduino BT

Arduino IDE

Lo primero que tenemos que hacer es descargar el software necesario para programar en Arduino que hace que sea más sencillos escribir código y subirlo.
Como yo lo estoy instalando en Linux lo que voy a hacer es buscar el IDE Arduino en el Centro de Software:


Instalamos y podremos ver algo como esto: 


Ahora cerramos esto, y empezemos a configurar si no, no será posible pasar el programa al Arduino. 


Configuración Conexión PC (Ubuntu 11.10 ) - Arduino Bluetooth

Para comenzar a usar el Arduino Bluetooth tenemos que eliminar la librería brltty, esto lo hice entrando al Centro de Software Ubuntu.


Ahora hay que identificar desde nuestra computadora en Arduino, y escribir la clave por default del Arduino en la computadora que es "12345", para así poder enviar los programas al Arduino.

Es importante resaltar que me pareció bastante extraño que la computadora solo detectaba el dispositivo cuando lo acababa de conectar, después de tiempo conectado dejaba de detectarlo y tenía que aplanar al botón Reset, esto lo hice muchas veces ya que batallaba para detectarlo.

En la página principal de Arduino recomiendan conectar el Arduino con la PC por medio del botón que podemos ver en la parte superior derecha de nuestra pantalla:



Sin embargo a través de esta aplicación es imposible agregarlo, ya que al querer agregar un nuevo dispositivo BT te pide meter una clave para el Arduino y una vez que la introdujiste espera a que ahora desde el Arduino escribamos la clave que esta en pantalla lo cual es imposible. Y lo que siguieren en la página oficial es irte a explorar archivos y de ahi escoger el Arduino BT y introducir la clave, sin embargo esta opción ya no esta en Ubuntu 11.10, eso funcionaba para Ubuntu 9.XX, entonces lo que hice fue instalar otra aplicación que manejara también conexiones BT.

                                    


Bien, ahora desde ahí buscaremos los dispositivos BT disponibles:


Damos click derecho, y apareceran varias opciones, damos click en Pair y nos aparece un cuadro de texto para meter la contraseña del Arduino, ahí solo introducimos 12345.

Ahora podemos ver en la aplicación Bluetooth que ya estan relacionados los dispositvios.



Ahora nos vamos a un terminal y checamos los dispositivos BT que detecta la computadora, con el siguiente comando "hcitool scan":



En la imagen podemos ver que nos da la dirección de nuestro dispositivo con este dato ahora podemos modificar el archivo "rfcomm.conf", que se encuentra en "/etc/bluetooth/", yo accedo desde un emacs de la siguiente manera: "sudo emacs -nw /etc/bluetooth/rfcomm.conf", y en el archivo vemos algunas líneas comentarizadas con # quitamos los # de manera que quede algo así(además fijate que cambie la dirección a la de mi arduino que me mostró el paso anterior, también cambié el comentario) y bin cambia a "yes":




Ahora guardas cambios, y lo que se tiene que hacer es ir a un archivo en donde podemos configurar diferentes aspectos de nuestro Arduino, es primordial que modifiques lo siguiente,  este archivo se llama "preferences.txt"  que se encuentra en "~/.arduino/preferences.txt", en mi caso yo accedo de esta manera: "cecy@cecy-Inspiron-N4020:~/.arduino$ sudo emacs -nw preferences.txt"

Ahora vemos un emacs, ese emacs nos muestra preferences.txt, ahi buscaremos el renglon 34 donde dice: serial.port= COMM1, cambiamos COMM1 por "/dev/rfcomm0", y guardamos cambios.



Ahora puedes conectar el Arduino a la PC con este comando(obviamente la direccion la cambias a la tuya) "rfcomm connect 0 00:07:80:42:05:51" y así podemos iniciar la conexión y poder pasar los archivos al Arduino:


Si a ti también te aparece ese mensaje entonces todo esta bien.


Programación

Ahora para empezar a probar el Arduino BT, usaré el siguiente código que lo que hace es prender y apagar un led:






Ahora compilamos el archivo, y para enviar el programa al Arduino y poder ver que de verdad funciona, debemos colocar el led en el pin 13, de la siguiente manera:


Y porfín podemos enviar el programa al Arduino, primero checamos en el terminal que la conexión aun este corriendo:


Si es así, desde el programa Arduino, ahora presionamos el botón Upload, y subirá el arcivo al Arduino y podremos ver el led parpadeando:



Resultado




Referencias

Código
Arduino BT

lunes, 19 de marzo de 2012

Arduino BT para proyecto

Como ya lo había mencionado antes mi proyecto para la materia de Cómputo Integrado usando Arduino es un Cubo de leds de 10x10x10, pero este proyecto lo voy a combinar con Dispositivos Móviles en dónde lo que quiero hacer es controlar desde el celular los leds de la matriz(Proyecto móviles), para esto es necesario tener un Arduino BT, en esta entrada hablare sobre las especificaciones y algunos ejemplos de proyectos hechos con Arduino Bluetooth.


Arduino BT

  • La principal y obvia diferencia a los demás Arduinos es su comuicación BT en vez de USB.
  • El arduino BT es más delicado que los Arduinos normales, es más frágil y fácil de romper.
  • Es importante tomar en cuenta que el se debe de alimentar con un voltaje no mayor a los 5.5V y la polaridad no se debe de invertir si se hace alguna de estas dos cosas la placa se dañará. La mínima de voltaje que ocupa es 1.2 V.
  • Tiene un microcontrolador ATmega168 que no se debe intentar quitar.
  • Tiene 8 entradas analógicas adicionales.
  • El pin7 esta conectado al modulo RESET de manera que solo se debe usar para eso.

Caracteristicas generales:
  • Microcontrolador: ATmega328
  • Volaje de Operación: 5V
  • Voltaje de entrada: 1.2 -5.5V
  • I/O Pines digitales: 14 (y 6 se pueden usar como salidas PWM)
  • Entradas analógas: 6
  • DC I/O Pines: 40 mA
  • DC Current for 3.3V Pin: 50 mA
  • Flash memory: 32 KB
  • SRAM: 2KB
  • EEPROM: 1 KB
  • Velocidad de reloj: 16 MHz


Alimentación
  • 9V. Es una entrada de voltaje, podemos suplir la entrada de voltaje atravez de este pin, pero debemos tener cuidado ya que se puede dañar con los 9V.
  • 5V. Es usado para dar poder al microcontrolador y los otros componentes.
  • Gnd. Es la coneción a tierra.

Memoria

El ATmega328 tiene 32 KB de memoria flash para almacenar el código, y 2 KB se usan para el gestor de arranque. Tiene 1 KB de SRAM y 512 bytes de EEPROM.


Salidas y Entradas

Los 14 pines digitales pueden ser usados como entradas o salidas, ellos operan con 5V y pueden dar o recibir 40 mA y tienen un resistor interno de 20 a 50 kOhms. Además cada pin tiene alguna función especifica:

  • Serie: 0(RX) y 1(TX), se usa para recibir(RX) y transmitir (TX) datos en serie TTL.
  • Interrupciones externas: 2 y 3, se usan para crar una interrupción en un valor bajo, un borde ascendente o descendente, o en el cambio de valor.
  • PWM: 3, 5, 6, 7, 8, 9, 10 y 11. Se proporcionan 8 bits de salida PWM con la función analogWrite().
  • SPI: 10(SS), 11(MOSI), 12(MISO), 13(SCK), esos pines apoyan la comunicación SPI, que no esta invluido en el lenguaje de Arduino.
  • BT Reset: 7. Esta conectado a la línea de reposición.
  • LED: 13, cuando este pin es de alto valor el led esta encendido, cuando esta en bajo esta apagado.
  • Entradas analógicas: son 6 entradas, cada una puede proporcionar 10 bits de resolución, esto quiere decir 1024 valores distintos.


Comunicación BT

El modulo blueGiga W711, permite la conexión entre Arduinos, Teléfonos o PC's u otros dispositivos con bluetooth. Se comunica con el microprocesador ATmega328 a través de serie.


Características físicas

Mide aproximadamente 8 cms por 5 cms. Tiene 3 orificios para poder atornillarlo a alguna superficie, dependiendo el proyecto.



Referencias

Imágenes propias
 


Arduino

¿Qué es un Arduino?



Es una plataforma de hardware que tiene un entorno para su desarrollo, que ayuda a desarrollar proyectos multidisciplinarios de electrónica. La manera de programar el software provee muchas ventajas para el desarrollador.  Su hardware consite básicamente en un microcontrolador Atmel AVR y puertos de entrada y salida. El arduino puede ser usado para desarrollar cualquier tipo de proyecto sin haber adquirido alguna licencia.

Componentes del Arduino






USB
Se utiliza para subir los programas al arduino, para comunicar el arduino y la computadora y algunas veces como alimentacion del arduino.

Selector de alimentación externa o por USB
Se coloca un jumper en los pines cercanos a la alimentacion. En los arduinos más actuales la selección de alimentación es automática.

Entrada de alimentación externa
VIN aveces es marcada como 9V, este voltaje se usa cuuando hay una fuente de alimentación externa. Las diferentes placas aceptan diferentes tipos de voltaje, poreso es importante btener en cuenta la documentación de cada arduino.
5V, es la alimentacion regulada usada para alimentar al microcontrolador y los demás componentes de la placa. Esta fuente puede venir del VIN o del USB u otra fuente regulada de 5V.

Terminal de referencia analógica
Es una referencia de voltaje para las entradas analógicas.

Terminales digitales
Las terminales digitales pueden ser usadas como entradas o salidas de propósito general, atravez de comandos como pinMode(), digitalRead(), y digitalWrite(). Cuando el pin se usa como entrada tiene una resistencia pull-up que puede activarse o desactivarse. Y cuando se usa como salida produce una salida máxima de 40 mA.

  • Terminales digitales de entrada y salida(Serial: 0 (RX) y 1(TX)). Se usa para recibir(RX) y transmitir(TX) datos serie TTL.
  • Interrupciones externas, son la 2 y 3 son configuradas para disparar una interrupción con un valor bajo, con pulso de subida o de bajada o con un cambio de valor.
  • PWM algunos pines tienen esta marca que significa que porporcionan salidas de 8 bit con la función analogWrite().

Microcontrolador
Los microcontroladores mas comunes que tienen estas placas son el ATmega168 (en la mayoría) y el ATmega8 (más antiguo). Algunas caracteristicas generales son:
Terminales de E/S digitales: en el 168 tienen 14 y 6 que pueden proporcionar salidas PWM y en el 8 tienen 14 salidas y 3 que se pueden usar como PWM.
Terminales de entrada analógicos: 6(DIP) o 8(SMD) para el arduino 168 y el arduino 8 cuenta con 6 pines de entrada analógica, ambos tienen una corriente de 40 mA en sus pines de E/S, el arduino 168 tiene una memoria flash de 16 KB y el arduino 8 de KB, ambos tienen una SRAM de 1KB y memoria EEPROM de 512 bytes.

Botón de reinicio
Se usa para reiniciar la placa.


Tipos de Ardinos
  • Duemilanove: Esta es la versión más nueva de Arduino USB básica, se puede conectar al ordenador con un cable USB estándar y tiene todo lo necesario para la programación. Pueden añadirsele multiples accesorios para expandir algunas funcionalidades.
Duemilanove
  • Diecimila: Es la versión inmediata anterior del Duemilanove.
Diecimila
  • Nano: Es una placa compacta para usarla en placas de desarrollo directamente, se puede conectar al ordenador con un cabke Mini-B USB.
Nano
  • Mega: Es un Arduino grande y potente, compatible con mulitples accesorios de las placas Duemilanove y Diecimilla.
Mega
  • Bluetooth: Este cuenta con modulo bluetooth y puede programarse y comunicarse sin cables. 
Arduino BT
  • LilyPad: Se usa para aplicaciones sobre ropa, ya que puede ser cosida, tiene un diseño con estilo y es color purpura.
LilyPad
  • Mini: Es la placa más pequeña, funciona en una placa de desarrollo o en donde se requiere minimizar el uso de espacio. Se conecta a la computadora con un adaptador Mini USB.
Arduino mini
  • Adaptador Mini USB: Esta placa convierte una conexión USB a 5V, toma tierras, líneas TX y RX que se pueden conectar al Arduino MIni o a otro microcontrolador.
Arduino Mini USB
  • Pro: Es diseñada para los proyectos en los que es necesario dejar la placa incrustada en el proyecto, es más economica que la Diecimila y es facil alimentarla con baterías, pero necesita componentes extra y montaje.
Arduino Pro
  • Pro Mini: Al igual que la Pro, la Pro Mini esta diseñada para usuarios avanzados que requieren de bajo costo, menor tamaño y soporte de un poco de trabajo extra.
Arduino Pro mini

  • Serial: Esta placa usa una interfaz RS232 como una comunicación con el ordenador para programación o intercambio de datos. 
Arduino Serial
  • Serial a una cara: Esta placa es diseñada para ser trazada y armada a mano, es más grande que la Diecimila y compatible con los shields.
  • Shields: Esta no es un tipo de Arduino, más bien son placas que se pueden agregar a los arduinos para ampliar alguna caracteristica, son controladas desde el arduino. Un ejemplo de esto es Shield Ethernet que permite a una placa Arduino conectarse a una red Ethernet y acceder a Internet.
Ethernet Shield


Aplicaciones
Las aplicaciones del Arduino son multiples, se pueden usar en proyectos escolares o en proyectos más elaborados aplicados a la industria, eso se debe a su facilidad de programación. También se puede usar en proyectos personales, dependiendo de la imaginación de cada quien.




domingo, 11 de marzo de 2012

Cálculo del pi en paralelo

En esta semana quise complementar lo de algoritmos paralelos haciendo un algoritmo que calcula el número Pi primero en paralelo y después en secuencial.

Metodo de Montecarlo

Este algoritmo consiste en generar experimentos aleatorios independientes consistentes en generar N puntos x, y que pertenezcan de 0 a 1 y contabilizar C los números que caen dentro del cuadrante de un circulo de radio 1.


El área del circulo es igual a pi*radio **2, el área del cuadrante es pi/4, y la probabilidad es C/N = pi/4 osea pi = 4C/N.

La aproximación más precisa es cuando N tiende al infinito.
Este es el algoritmo secuencial que desarrolle:


Ejecución:



Paralelización

Este reparto consiste en la generacion de N experimentos en un conjunto de P procesadores. Cada procesador puede generar puntos y contar cuales C caen en el rango del círculo con 1 de radio.
Al iniciar solo el proceso principal conoce cuales son los valores de N, osea el número de pruebas que se quiere hacer, y cuantos procesadores se van a tener.
Después se envian a los procesos esclavos la N, para que empiezen a calcular.

Cada proceso realiza el trabajo que le corresponde


Y por último los procesos esclavos envían sus resultados al proceso maestro, para que el maestro calcule el numero de aciertos y lo multiplique por 4 (por la formula que acabamos de ver) y lo divida entre el total de experimentos N.

Mi programa en python emula este comportamiento con hilos, y queue de python para poder mandar cada suma al proceso maestro, este es el programa:


En donde señale que sean 5 procesadores, osea 5 hilos que realicen la tarea indicada.
Y la ejecución se ve así:



El algoritmo lo desarrolle tomando la lo propuesto en este pdf, donde proponen la realización de él más no códigos ni pseudocódigos.

Semana 6

Paralelizando algoritmos

Criba de Eratóstenes

Es un aloritmo que encuentra numeros primos de 2 a N, empieza con el número 2 y tacha todos los elementos que son multiplos del 2, una vez que tacho todos estos sigue el elemento que no ha sido tachado despues de dos y así sucesivamente.




Primero desarrollé la versión en secuencial del algoritmo en Python:




Ejecución:


Para paralelizarla lo que intenté hacer fué que cada hilo buscara los múltiples de ciertos números en paralelo. Es decir mientras uno buscaba los múltiplos de 2 otro buscara los múltiplos de 3 y así sucesivamente.



En el ejemplo lo hice con solo un hilo, con esta manera de implementación podemos crear tantos hilos como queramos y que empiecen a checar si es primo o no desde algún número, y así trabajar en paralelo, subiré la parte en donde muestro como se hace de esta forma que explico en otra entrada, esto es todo por ahora.

Nominaciones:
Por ahora solo, Roberto Martínez por la propuesta al uso de una herramienta útil para hacer sistemas distribuidos y Emmanuel por la explicación del uso de mpi4 de python ya que yo tenía pensado hablar de eso.