View
345
Download
3
Category
Preview:
Citation preview
Súper cómputo a bajo costo utilizando JavaScript
Mario García Valdez @mariogarciav
Súper ComputoEs la utilización de computadoras con capacidades extraordinarias para la realización de investigación en diversas áreas del conocimiento.
Worldwide LHC Computing Grid
➤ El Gran Colisionador de Hadrones (LHC) se construyó para probar la existencia del Bosón de Higgs.
➤ Los experimentos arrojan datos en cantidades sin precedentes.
➤ Los sensores arrojan 300 GByte/s.
➤ Después del filtrado quedan al rededor de 300 MByte/s.
➤ El proyecto genera 27 TB de datos al día.
➤ En 2012 consistía en 170 centros de computo en 36 países.
➤ En 2010 eran 200,000 núcleos y 150 petabytes de disco duro.
➤ Es una aplicación que simula 60 partículas viajando alrededor del aro del LHC.
➤ Esta simulación se realiza para 100,000 vueltas.
➤ Ayuda a ajustar los componentes para mantener las órbitas en curso.
http://lhcathome.web.cern.ch/
Berkeley Open Infrastructure for Network Computing (BOINC)
➤ Es un sistema an open-source para computación voluntaria y grid.
➤ La intención de este proyecto es obtener una capacidad de computación enorme utilizando computadores personales alrededor del mundo.
http://boinc.berkeley.edu/
¿Súper Computadoras?
¿Súper Computadoras de bajo costo?
http://www.nvidia.com/object/why-choose-tesla.html#sthash.5yLozfYP.dpuf
Tesla K80 GPU
➤ Desempeño de hasta 2.91 TFlops en doble precisión.
➤ Hasta 8.74 TFlops en precisión simple.
➤ Memoria interna de 24 GB.
➤ Aprox. $4000.00
➤ Con 10 tenemos medio Miztli
¿Súper Computadoras de bajo costo? Un Cluster
¿Súper Computadoras de bajo costo? Un Cluster
Servicios Cloud - Free Tier
Servicios Cloud - Free Tier / Low Cost
Servicios Cloud - Free Tier
Volunteer Computing
Un conjunto de herramientas que permiten a los ciudadanos donar ciclos de sus CPUs a aplicaciones que permiten la ejecución de algún experimento.
Volunteer Computing
Computación Voluntaria
➤ Los Voluntarios son anónimos.
➤ Como entidades anónimas no podemos reprenderlos o hacerlos responsables.
➤ Los voluntarios deben confiar en los proveedores de las aplicaciones.
➤ Después de todo bajaremos un programa que actuará como un malware.
Es una heurística de búsqueda la cual imita el proceso de selección natural
COMPUTACIÓN EVOLUTIVA (PROBLEMA)
Útiles cuando buscamos posibles soluciones en un espacio de búsqueda.
Cuando optimizamos.
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]ONEMAX ( ) 15
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]ONEMAX ( ) 15
ONEMAX ( )[ 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 10 10 ] 20
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]ONEMAX ( ) 15
ONEMAX ( )[ 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 10 10 ] 20
ONEMAX ( )[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ] 11
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]ONEMAX ( ) 15
ONEMAX ( )[ 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 10 10 ] 20
ONEMAX ( )[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ] 11 262 = 67,108,864
ONEMAX
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]ONEMAX ( ) 15
ONEMAX ( )[ 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 10 10 ] 20
ONEMAX ( )[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ] 11
ONEMAX ( )[ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ] 26
262 = 67,108,864
POBLACIÓN
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 10 10 ]
[ 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 10 10 ]
[ 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
EVALUACIÓN FUNCIÓN DE APTITUD = ONEMAX( )
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 ]
[ 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 10 ]
[ 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
9
13
18
11
10
7
17
10
SELECCIÓN
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 10 10 ]
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 ]
[ 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 0 10 ]
[ 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
9 13
18
11
10
7
17
10
CRUCE
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 10 10 ] 18
17[ 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 0 0 0 0 10 ]
19
16
[1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 10 10]
[1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 10]
MUTACIÓN
[1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 10 10]
[1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 10 10]
NUEVA POBLACIÓN - GEN 2
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 10 0 0 ]
[ 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 10 11 ]
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 10 10 ]
[ 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 0 10 0 0 ]
[ 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 10 10 ]
[1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 10 10]
[ 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 10 ]
NUEVA POBLACIÓN - GEN N
[ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ]
[ 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 10 11 ]
[ 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 10 10 ]
[ 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 10 10 ]
[1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 10 10]
[ 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 10 ]
[ 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 10 10 ]
[ 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 10 10 ]
¿SÚPER CÓMPUTO EVOLUTIVO?
➤ Los algoritmos evolutivos son bochornosamente paralelizables.
➤ El costo de computo más elevado está en la función de aptitud.
➤ Algunos problemas requieren alto poder de procesamiento, incluso para problemas académicos.
➤ Por ejemplo: OneMax de 106 bits.
➤ Existen muchas variantes distribuidas del algoritmo:
➤ Multi-Islas
➤ Basados en Pool
¿Y SI USAMOS EL NAVEGADOR?
➤ JAVA Applets
➤ Flash, ActionScript
➤ VBScript
➤ ActiveX
PROPUESTA
➤ Una solución basada completamente en JavaScript, para implementar experimentos de cómputo evolutivo voluntario.
JAVASCRIPT¿ ?
PROPUESTA
JAVA C++
FORTRANMATLAB
C
JAVASCRIPT
➤ En todos lados.
➤ No requiere instalación de alguna VM, Plugin o software.
➤ Relativamente rápido.
➤ Compilador JIT para V8.
➤ En todo el stack, gracias a node.js.
➤ Buenas herramientas de desarrollo, depuradores, editores, gestores de bibliotecas, una comunidad activa.
➤ Los Web Workers de HTML 5 permiten explotar los hilos del CPU.
➤ Ciudadano de primera en Heroku, Azure, Openshift, etc.
JAVASCRIPT
➤ Inmaduro para cómputo científico, no hay muchas bibliotecas.
➤ El método de generación de números Random varía según el navegador.
➤ La precisión y los cálculos también pueden variar.
➤ Poca aceptación por parte de la comunidad, se piensa en el lenguaje solo para validar páginas Web.
➤ No es Java, C, Fortran, Python, R o Matlab.
A PROBAR
➤ Escalabilidad
➤ Heterogéneo
➤ Tolerancia a fallos
➤ Adaptativo
➤ Desempeño
➤ Comportamiento de los Voluntarios
NodEO
NodEO
function Chromosome(string,fitness){ this.string = string; this.fitness = fitness; // functions this.invert = invert; this.mutate = mutate; this.crossover=crossover; this.reproduction=reproduction; }
NodEO
eo = new Nodeo( { population_size: population_size, chromosome_size: chromosome_size, fitness_func: trap_fitness } );
NodEO
(function do_ea() {
eo.generation();
generation_count++;
if ( (generation_count % 100 === 0) ) {
do_periodic_stuff()
}
if( (eo.fitness_of[eo.population[0]] < traps*conf.fitness.b )
&& ( generation_count*conf.population_size < conf.max_evaluations)) {
setTimeout(do_ea, 5);
} else {
we_are_done();
}
})();
NodIO: Computación Voluntaria utilizando NodEO
➤ Un servidor REST
➤ Varias rutas para almacenar y recuperar información.
➤ Utiliza JSON como formato de comunicación cliente-servidor.
➤ Sobre el EA:
PUT, GET chromosome, GET random
➤ Sobre el experimento:
Generación Actual, Mejor cromosoma
➤ Bitácora
➤ Ejecuta varios experimentos.
NodIO: Computación Voluntaria utilizando NodEO
➤ Muchos Clientes, cada uno:
➤ Incluye un algoritmo en NodEO
➤ Despliega gráficas e información del experimento.
➤ El algoritmo puede considerarse una isla, que crea su propia población.
➤ Cada 100 generaciones envía al mejor cromosoma al server.
➤ Después del envío, solicita un cromosoma aleatorio.
➤ Si se encuentra el cromosoma óptimo el experimento termina.
NodIO-W2
➤ Los clientes utilizan HTML Web Workers.
➤ Re-inician el experimento al encontrar un óptimo.
NodEO
NodEO-W2
IPS VS TIEMPO ONEMAX
FUNCIÓN RASTRIGIN
FUNCIÓN RASTRIGIN
WEIBULL FIT GEV FIT
DETALLES DE LA IMPLEMANTACIÓN RASTRIGIN PESADA➤ Randomize
➤ Matlab y Java utilizan la biblioteca Java Randomizer para generar Gausianas pseudo aleatorias de precisión double.
➤ Se utilizó random-js ya que la implementación de Math.random() tiene inconsistencias y es no determinista.
➤ Funciones de timing.
➤ Para evaluar el tiempo de ejecución a veces se utiliza la clase Date pero su resolución llega a los milisegundos.
➤ Para las medidas se utilizaron dos funciones, para node.js la función nativa process.hrtime() nanosegundos y Performance.now() con microsegundos. (Firefox y Chrome).
➤ Herramientas Disponibles:
➤ npm, debupuradores, log (winston), monitores de red, monitoreo de Web Workers.
➤ Tipos de datos:
➤ Números flotantes con una precisión de 64 bits que implementan parcialmente la biblioteca StrictMath de Java.
➤ Si se requiere de mayor precisión se puede utilizar math.js para matrices y big numbers.
LINKS
CÓDIGO FUENTE Y ARTICULOS https://github.com/JJ/modeling-volunteer-computing.https://github.com/JJ/splash-volunteer
Implementación temporal (fork) con Web Workershttps://github.com/mariosky/splash-volunteer
Comunidad JavaScript Tijuana:http://tijuanajs.org/
mariosky@gmail.com @mariogarciav
GRACIAS POR SU ATENCIÓN
Recommended