You are currently browsing the category archive for the ‘Informática’ category.

Después de muchísimo tiempo sin escribir, vuelvo con este post que resume todo el trabajo que hemos realizado durante este último año.

En julio del año pasado nos enteramos de un artículo publicado por X. Yang and R. Mittal, de la Johns Hopkins University, en el que aceleraban de manera espectacular el algoritmo de Jacobi y lo utilizaban para resolver ecuaciones en derivadas parciales de tipo elíptico.

A pesar del relativo eco mediático que tuvo, y aunque aceleraba muchísimo Jacobi, seguía sin ser competitivo con los métodos utilizados actualmente para solucionar este tipo de ecuaciones. Sin embargo, como prometía en cuanto a su sencillez desde el punto de vista tanto de implementación como de paralelización, decidimos trabajar un tiempo sobre el mismo.

Finalmente, en junio presentamos unos proceedings en el CEDYA 2015 (pag. 733) y hace tres semanas enviamos un paper a JCP, donde presentamos una serie de mejoras realizadas que permiten, tal y como allí comentamos, que el SRJ sea prácticamente competitivos en ejecución secuencial con los algoritmos utilizados actualmente.

Por un lado, su inmediata implementación (todos tenemos un Jacobi implementado de nuestro curso de métodos numéricos, y es trivial convertirlo en un SRJ 🙂 ) hace pensar que mucha gente que no tenga y necesite un resolvedor elíptico eficiente sin invertir mucho esfuerzo en su implementación quiera utilizarlo. Por otro, su trivial paralelización, por ejemplo en entornos GPU, nos hace pensar en su extraordinario potencial en el ámbito de la supercomputación.

En la página de nuestro grupo de investigación tenemos disponibles todos los esquemas SRJ presentados en el paper.

¡Disfrutenlo!

En el artículo técnico What would a binary black hole merger look like?  se simula, mediante técnicas de ray tracing, como vería un observador externo el merge de dos agujeros negros (del artículo y del sitio web de los autores están sacadas prácticamente todas las imágenes).

Si estamos mirando hacia algún sitio, digamos:

ClockTower-400x300

y pasa un agujero negro frente a nosotros, lo primero que se nos viene a la cabeza es la siguiente imagen:

ClockTower-400x300b

ya que como de un agujero negro no puede escapar nada, ni la luz, pensamos que veríamos una simple esfera negra tapando un trozo de nuestra visión. Sin embargo, una imagen mas realista de lo que veríamos es:

ClockTower_BH-400x300debido a la curvatura que experimentan los rayos de luz por la curvatura del espacio-tiempo que genera el agujero negro: efecto de lente gravitacional.

Colocando una imagen de fondo más métrica, así es como se verían los espacios de Minkowski, Schwarzschild y Kerr.

analyticSpacetimesSi en lugar de un agujero negro tenemos un sistema binario de agujeros negros de igual masa, entonces tendríamos:

bbhSystem

Finalmente, una animación del merge:

Un problema puede ser más o menos difícil de resolver. La complejidad computacional pretende clasificar los problemas computacionales desde el punto de vista de cuanto cuesta resolverlos. Y para cuantificar esta dificultad de una manera teórica y objetiva, lo que se hace es ver como varia el tiempo de resolución con el tamaño de la entrada.

De esta manera, un problema perteneciente a la clase P, un problema resoluble en tiempo polinómico, es un problema cuyo tiempo de resolución es una función polinómica del tamaño de la entrada (si crece poco el tamaño de la entrada, crece poco el tiempo que tardamos en resolverlo, lo cual hace que estos problemas sean tratables).

¿Y qué quiere decir que un problema es de clase NP? Son aquellos problemas para los que es difícil encontrar una solución pero fácil verificarla, es decir, no se conoce ningún algoritmo polinómico que nos encuentre una solución pero si lo existe para comprobar que efectivamente lo es.

Para aclarar la definición anterior, pongamos un ejemplo: el problema del viajante de comercio. Dado un conjunto de ciudades, encontrar una ruta para un comerciante de manera que pase por TODAS las ciudades UNA ÚNICA vez. Este problema se traduce en encontrar un ciclo Hamiltoniano en un grafo. Un crecimiento moderado en el número de ciudades implicadas hace que el problema se vuelva prácticamente intratable. Sin embargo, si nos dan ya una solución, una ruta, es prácticamente trivial comprobar si es un ciclo hamiltoniano o no.

El problema P vs NP pretende demostrar si estos dos conjuntos son o no el mismo.

Dos definiciones complementarias para terminar.

  • Un problema es NP-completo si es un problema NP de los mas difíciles, dejémoslo ahí. El problema anterior es un problema de esta clase. Una propiedad que tienen estos problemas es que son todos equivalentes, desde el punto de vista de complejidad computacional, entre si, es decir, existe un algoritmo que traduce cualquier problema NP-completo en cualquier otro en tiempo polinómico. De manera que, si lográramos un algoritmo en P que resolviera uno de ellos, tendríamos un algoritmo en P para todos ellos (traducimos el otro problema al primero en tiempo polinómico, lo resolvemos en tiempo polinómico y traducimos la solución a una solución del original en tiempo polinómico).
  • Un problema es NP-duro si es, al menos, tan difícil como NP.

 

 

Esta semana he asistido a un curso interesantísimo sobre el estandar C++11, es decir, sobre lo último que nos pueden ofrecer los compiladores de C++, impartido por Jacek Generowicz, del CERN y que controla bastante el tema, en el IFIC.

En palabras del propio Jacek, ésta es brevemente la guía de estilo para el nuevo estandar:

  • utilizar nullptr para punteros nulos,
  • inferencia automática de tipos mediante auto,
  • definición de rangos para los bucles,
  • utilizar funciones begin y end y no las correspondientes funciones miembro,
  • inizializaciones con {},
  • lambda funciones: facilitan los algorimos tipo STL, la inyección remota de código para metaprogramación y en la concurrencia,
  • nueva semantica move como optimización de copy y con la consiguiente implementación del move constructor, el move assignment y el swap, junto con los clásicos copy constructor, copy assignment y destructor,
  • smart pointers unique_ptr y shared_ptr que, de alguna manera, permiten cierto tipo de gestión automatica de la memoria,
  • concurrencia: threads, mutex, etc…

Ya tengo instalado el gcc 4.8, que con -std=c++11 soporta todas estas novedades, y con ganas de aplicar estos potentes mecanismos a mis códigos :–)

A partir de una interesante conversación en el trabajo con el Dr. Petar Mimica, me he visto en la necesidad de repasar algunos conceptos interesantes de las asignaturas que cursé en el área de informática teórica.

El primero de ellos és el de la lógica modal. Las lógicas tradicionales son la proposicional, o de orden cero (CP0), y la lógica de predicados, o de primer orden (CP1). En toda lógica, como en todo lenguaje formal, distinguimos tres aspectos básicos: su léxico, es decir, que “palabras” podemos utilizar en el lenguaje, su sintaxis, es decir, cuales son las reglas para construir “oraciones” con nuestro léxico, y finalmente su semántica, o sea, el significado del que dotamos a estas palabras y oraciones. La lógica proposicional tiene menos poder expresivo que la lógica preposicional pero, en contraposición, es completa.

En la lógica modal, lo que pretendemos es ampliar la capacidad expresiva del CP0 introduciedo dos nuevos símbolos que nos permitiran expresar de que modo se verificaran las fórmulas de esta lógica: necesariamente (\square) o posiblemente (\lozenge), uno primitivo y otro definible a partir de éste, junto con el conjunto de reglas que nos permite operar con ellos.

En esta lógica, el teorema de Löb se escribe, sencillamente:

\square (\square P \rightarrow P) \rightarrow \square P,

y da lugar a paradojas, pues es un enunciado que, a partir de un lenguaje (lo suficientemente expresivo) intenta demostrar cuestiones sobre el propio lenguaje.

La idea es la misma, en otro nivel, a la del teorema de incompletitud de Gödel: para hacer afirmaciones sobre las propiedades de un lenguaje (en términos de consistencia, completitud, etc.) no es suficiente con el propio lenguaje: necesitamos un metalenguaje. Se ha hablar mucho al respecto, pero desde mi humilde punto de vista, lo único que nos está diciendo es que, si nos imaginamos en algún lugar toda la matemática (el Libro al que hacia referencia Erdös :-), nunca podremos tener un sistema de axiomas y reglas que nos permite generarlo de manera completa, pero si parcial. Además, cambiando este sistema, posiblemente podamos generar nuevas demostraciones  imposibles en el anterior (a cambio de perder otras si generables en el primero) y sin inconsistencias entre las generables en ambos.

Haciendo un simil con las variedades diferenciables (y salvando la enorme cantidad de defectos obvios que tiene esta comparación), nunca tendremos una carta para cubrir toda la variedad, necesitaremos varias, pero serán compatibles entre ellas en los solapes.

A mi casi-código SPH le he añadido la libreria Voro++ de Chris Rycroft y ésta va calculando las correspondientes teselaciones de Voronoi tridimensionales correspondientes a las partículas siguiendo movimientos pendulares (sobre planos z=cte) .

Pulsar sobre la imagen para empezar la animación.animate_1

El blog, que empezó para servir de mero canal de comunicación asíncrono entre dos o tres personas, acaba de superar las mil visitas mensuales. Aunque no conozco a casi ninguno de mis lectores,

¡GRACIAS A TODOS! 🙂

blogStats   blogMap

El software Chombo, del Berkeley Lab, combina los métodos en diferencias finitas con las mallas adaptativas (AMR) para resolver, entre otras, PDEs elípticas.

Las siguientes imágenes, en 2D y 3D, se han obtenido a partir de su AMRPoisson:

schSolSouschSol

De momento unas cuantas imágenes:

CA7

Ya las comentaremos en otro post y colocaremos el código utilizado para generarlas.

Una nueva imagen curiosa del error en la resolución numérica de una Poisson 2d utilizando multigrid…

caraError2d

Una presentación con parámetros tweeter:

tweetPres

Simplemente enlazo esta página donde habla de como realizar flujos de trabajo aprovechando el poco coste del branching en Git.

También puede servir como punto de entrada al libro Pro Git de Scott Chacon. Ayuda mucho a entender el funcionamiento de Git sus explicaciones de como están implementadas internamente estas funcionalidades.

Algunas notas interesantes:

  • Git no guarda cambios incrementales sino que guarda instantaneas completas del estado del código en el momento del commit.
  • La rama principal y las demás ramas son apuntadores a estas instantaneas.
  • En el momento de crear una nueva rama, se crea un apuntador a la instantánea del último commit.
  • Esta política hace que el coste del branching sea bajo en comparación a otros
  • Permite, por tanto, la existencia y utilización con ramas temporales para los flujos de trabajo.

En la siguiente imagen del libro podemos ver reflejadas todas estas ideas:

gitBranching

Diagrama de clases en UML2 que hicimos de la aplicación ParaMul con VP-UML y que utilizaremos desde Kunagi para diferentes elementos de Scrum y GitX para el control de versiones:

UML_CD_ParaMul

Roles

  • Product Owner: es el que sabe como debe ser el producto, por lo que escribe historias de usuario (requisitos funcionales), las ordena por prioridad, las coloca en el product backlog, pone fechas y se encarga de aceptar o rechazar los entregables. Por ejemplo, en kunagi:

scrum_PO

  • ScrumMaster: es el encargado de asegurar que los procesos Scrum se cumplan, que se cumplan las reglas, que los equipos trabajen como es debido, eliminando obstáculos y aislándolos de distracciones. Por ejemplo, en kunagi:

scrum_SM

  • Development Team: es el equipo multidisciplinar de entre 5 y 9 personas con habilidades transversales (diseño, implementación, documentación…) que se autoorganiza para tener los entregables en los plazos.

scrum_T

Reuniones

  • Daily Scrum (15m): cada dia a la misma hora y en el mismo sitio de pie para que cada miembro del equipo diga que hizo ayer, que ara hoy y que impedimentos está encontrando.
  • Scrum de Scrum (15m):  después del daily scrum y a nivel de equipos cuando existen varios. Un representate por equipo para explicar que hizo su equipo ayer, que ará hoy, que problemas tiene y si va a subir algo que se encontraran el resto de equipos.
  • Sprint Planning Meeting (8h): al empezar un sprint para prepararlo. Seleccionar que es lo que se hará, construir el sprint backlog y asignar plazos.
  • Sprint Review Meeting (4h): revisar que se ha conseguido y que no. Demo únicamente de lo entregable.
  • Sprint Retrospetive Meeting (4h): opinión de todos sobre las demos.

Documentos

  • Product Backlog: que se tiene que hacer en el producto.
  • Sprint Backlog: que se tiene que hacer en el sprint actual.

En la web de ScrumAlliance encontramos el siguiente resumen:

scrumFramework

En el siguiente post de Henrik Kniberg comenta como llevar a la práctica los conceptos tratados en los posts sobre Software Configuration Management y Agile Software Development.

El siguiente gráfico, del mismo post, resume todo lo tratado en el artículo:

gitScrum

A continuación sencillos comentarios interesantes que aparecen en el post:

  • Cada branch (rama), incluso la mainline (tronco), tiene un owner (propietario) y una policy (política).
  • Tenemos to do, in progress y done como estados para cada user story.
  • Done (hecho) significa releasable (entregable), es decir, que si en ese momento el cliente quisiera entrar y empezar a probarlo, nadie tuviera que decirle que no puede, que tiene que esperar.
  • El tronco es la rama hecho, es decir, la que entrará en producción llegado el momento.
  • La política del tronco puede ser o (exclusivo) entregable at any time (en cualquier momento) o lo antes posible (asap).
  • Crear ramas cuantas menos mejor. Solo crearemos una cuando queramos probar algo y no lo podamos hacer con ninguna de las existentes sin violar sus políticas.
  • Como entegrable incluye las pruebas de integración y no podemos hacerlo sobre la mainline, necesitamos una nueva rama: work branch (rama de trabajo) o development branch (rama de desarrollo).

El Agile Software Development (desarrollo ágil de software) es un paradigma de la ingenieria del software cuyas principales características son:

  • la idea general es el desarrollo iterativo e incremental minimizando costes.
  • una iteración es el software desarrollado en una unidad de tiempo, entre una y cuatro semanas.
  • cada iteración no agrega mucha funcionalidad pero debe estar libre de errores y funcionar.
  • en cada iteración: planificación, analisis, diseño, implementación, prueba y documentación.
  • al final de cada iteración se reevaluan las prioridades del proyecto.
  • se enfatiza la comunicación cara a cara.

Scrum es un ejemplo concreto de metodología ágil. El diagrama de la empresa Mountain Goat Software de Mike Cohn es bastante autoexplicativo:

scrum

aquí una introducción de ellos mismos a estos temas.

¿Alguna herramienta libre para llevar ésto a la práctica? Pués, por ejemplo, PangoScrum o Kunagi. Según ellos mismos, “PangoScrum is a agile project management tool for Scrum.Keeping it simple, it focus on the continuously efficiency improvement of software development”, “Kunagi is a free web-based tool for integrated project management and collaboration based on Scrum“.

Finalmente, en esta página de Scrum Manager, los princípios de la Orientación a Objetos.

Seguimos con SCM, con el libro Software Configuration Management Patterns: Effective Teamwork, Practical Integration, desde donde lo dejamos en el último post sobre el tema.

Private Workspace

¿Cómo lo hacemos, con una codeline que cambia contínuamente, para realizar progresos sin que nos distraiga este entorno cambiante debido a los que están por debajo de nosotros?

Realiza tu trabajo en un workspace privado donde controlemos las versiones del código y los componentes que estamos utilizando. Debemos tener control total sobre cuando y como cambia nuestro entorno.

Repository

¿Cómo obtener las versiones correctas de los componentes correctos en un nuevo workspace?

Private System Build

¿Cómo verificas que tus cambios no rompen la construcción o el sistema antes de colocarselos?

Antes de hacer un submit al control de fuente, construir el sistema de manera privada de manera similar a como será.

SCM_psb

Integration Build

¿Cómo asegurarse de que el código base siempre se construye de manera fiable?

Asegurate de que todos los cambios (y sus dependencias) se construyen utilizando un proceso para la construcción de la integración centralizado.

SCM_ib

Third Party Codeline

¿Cúal es la estrategia mas efectiva para coordinar las versiones de vendedores de código con las versiones de productores de código?

SCM_tpc

Task Level Commit

¿Cuanto trabajo debemos realizar entre submits al sistema de control de versiones? ¿Cuando tiempo deberíamos esperar antes de colocarlos?

Realizar un commit por cada pequeña tarea de grano fino consistente.

Codeline Policy

¿Como saben los desarrolladores en que codeline deben comprobar su código y que tests deben realizar antes de hacerlo?

Para cada rama o codeline define una política que determine cómo y cúando los desarrolladores realizarán cambios. La política debe ser concisa y auditable.

Smoke Test

¿Cómo saber que el sistema seguirá funcionando después de que realizemos un cambio?

Somete cada construcción a una prueba de humo que verifique que la aplicación no se rompe de una manera evidente.

Unit Test

¿Cómo comprobar si un módulo continua funcionando tras realizar un cambio?

Desarrolla y realiza pruebas unitarias.

Regression Test

¿Cómo asegurarse de que el código existente no empeora con las nuevas mejoras?

Ejecutar pruebas de regresión en el sistema siempre que lo desee para asegurar la estabilidad de la codeline, como antes de liberar una construcción, o antes de un cambio especialmente arriesgado.
Crea las pruebas de regresión a partir de los casos de prueba que hicieron fallar al sistema en el pasado.

Private Versions

¿Cómo puedes experimentar con un cambio complejo y beneficiarse del sistema de control de versiones sin hacer el cambio público?

Provee a los desarrolladores de un mecanismo de checkpoints de cambios en una granularidad que se sienta cómodo. Esto puede hacerse mediante un área de control para versiones locales. Sólo los conjuntos de código estables se registrarán en el repositorio del proyecto.

Release Line

¿Cómo mantener versiones publicadas sin interferir en el trabajo actual de desarrollo?

SCM_rl

Release-Prep Codeline

¿Cómo se puede estabilizar una codeline para un lanzamiento inminente, además de facilitar el continuar trabajando en la codeline activa?

SCM_rpc

Task Branch

¿Cómo puede nuestro equimo hacer a una codeline múltiples cambios a largo plazo superpuestos sin comprometer su consistencia e integridad?

SCM_tb

Alguna definicion previa (mantendremos la nomenclatura inglesa):

Un workspace es un lugar donde el desarrollador tiene todos las entidades que necesita para realizar su tarea. En concreto, puede ser un arbol de directorios en disco en el area de trabajo del desarrollador o una colección de ficheros mantenidad en un espacio abstracto por una herramienta. Está asociado con versiones particulares de las entidades. Debe disponer de un mecanismo para construir ejecutables a partir de su contenido.

Una codeline es un conjunto de fichero fuente y otras entidades que forman parte y que cambia a lo largo del tiempo. Cada vez que modificamos un fichero u otra entidad en el sistema de control de versiones, creamos una revisión de los mismos. Una codeline contiene cada versión de cada entidad a lo largo de un camino de evolución.

Dado que las ramas en las que se trabaja en paralelo no constituyen conjuntos disjuntos, el merge siempre tiene un overhead debido a posibles conflictos.

En cada uno de los patrones aparecen los problemas que intenta resolver y el esquema de solución.

Mainline
¿Cómo mantener el numero de codelines activas de manera que sea un conjunto manejable, y evitar que el crecimiento del arbol de versiones deproyecto lo lleve a ser demasiado amplio o demasiado denso? ¿Como evitar el overhead del merging?

mainlineDevelopment

Active Development Line
¿Cómo conseguir una codeline rapidamente evolucionable pero lo suficientemente estable para poder utilizarse?

labelingNamedStableBases

Private Workspace

Acabo de conseguir el libro Software Configuration Management Patterns: Effective Teamwork, Practical Integration de Stephen P. Berczuk, Brad Appleton y Kyle Brown en el que se abordan diferentes patrones para la Gestión de Configuración de Software. Además, encontre una presentación de G. Serrano basada en el libro que cubre sobradamente nuestros intereses.

En la práctica, la SCM se preocupa de como construir y lanzar un producto, así como de la identificación y el seguimiento de sus modificaciones.

Para empezar, ¿qué entendemos por patrón? La idea de patrón tal y como la utilizaremos aparece originalmente en el trabajo que el arquitecto Christopher Alexander hizo en construcción arquitectónica para describir las cualidades de un buen diseño arquitectónico. Define patrón como una “solución a un problema en un contexto”, como algo que “describe un problema que ocurre una y otra vez en nuestro entorno, y describe la esencia de la solución a dicho problema, de manera que puedes utilizar esa solución millones de veces sin tenerlo que hacer dos veces de la misma manera”.

El esquema de patrones que seguiremos es:

SCMPatternLanguage

Acabo de descubrir Prezi, un programa que nos permite crear presentaciones online.

Por una parte, como acabamos de decir, permite tanto su creación como su exposición sin necesidad de ninguna instalación local. Por otra, el punto mas original, es que nos permite crearla a partir de un único esquema por el que podremos navegar líbremente, un complejo gráfico por el que nos iremos desplazando, acercando y alejando a lo largo de nuestra exposición.

Existen tres modalidades, una de ellas gratuita, para darnos de alta en el sistema. A partir de ahí, podemos crear tantas presentaciones como queramos (tenemos un límite de almacenamiento) y disponemos de unas cuantas plantillas, que parecen meditadas, que nos facilitarán la iniciación en el sistema.

Las presentaciones, la verdad, quedan resultonas.

Para los que utilizamos latex, tenemos que añadirlo como imagen (generada, por ejemplo, mediante LatexIt).

agosto 2017
L M X J V S D
« Jul    
 123456
78910111213
14151617181920
21222324252627
28293031