Análisis de rendimiento de aplicaciones paralelas de memoria compartida: problema N-body

Este trabajo analiza el rendimiento de cuatro nodos de cómputo multiprocesador de memoria compartida para resolver el problema N-body. Se paraleliza el algoritmo serie, y se codifica usando el lenguaje C extendido con OpenMP. El resultado son dos variantes que obedecen a dos criterios de optimización diferentes: minimizar los requisitos de memoria y minimizar el volumen de cómputo. Posteriormente, se realiza un proceso de análisis de las prestaciones del programa sobre los nodos de cómputo. Se modela el rendimiento de las variantes secuenciales y paralelas de la aplicación, y de los nodos de cómputo; se instrumentan y ejecutan los programas para obtener resultados en forma de varias métricas; finalmente se muestran e interpretan los resultados, proporcionando claves que explican ineficiencias y cuellos de botella en el rendimiento y posibles líneas de mejora. La experiencia de este estudio concreto ha permitido esbozar una incipiente metodología de análisis de rendimiento, identificación de problemas y sintonización de algoritmos a nodos de cómputo multiprocesador de memoria compartida.

A Modulated Closed Form solution for Quantitative Susceptibility Mapping - A thorough evaluation and comparison to iterative methods based on edge prior knowledge.

The aim of this study is to perform a thorough comparison of quantitative susceptibility mapping (QSM) techniques and their dependence on the assumptions made. The compared methodologies were: two iterative single orientation methodologies minimizing the l2, l1TV norm of the prior knowledge of the edges of the object, one over-determined multiple orientation method (COSMOS) and anewly proposed modulated closed-form solution (MCF). The performance of these methods was compared using a numerical phantom and in-vivo high resolution (0.65mm isotropic) brain data acquired at 7T using a new coil combination method. For all QSM methods, the relevant regularization and prior-knowledge parameters were systematically changed in order to evaluate the optimal reconstruction in the presence and absence of a ground truth. Additionally, the QSM contrast was compared to conventional gradient recalled echo (GRE) magnitude and R2* maps obtained from the same dataset. The QSM reconstruction results of the single orientation methods show comparable performance. The MCF method has the highest correlation (corrMCF=0.95, r(2)MCF =0.97) with the state of the art method (COSMOS) with additional advantage of extreme fast computation time. The l-curve method gave the visually most satisfactory balance between reduction of streaking artifacts and over-regularization with the latter being overemphasized when the using the COSMOS susceptibility maps as ground-truth. R2* and susceptibility maps, when calculated from the same datasets, although based on distinct features of the data, have a comparable ability to distinguish deep gray matter structures.

Optimització i implementació en Simulink de l'adquisició d'un senyal GPS amb blocs FFT

Aquest projecte es tracta de la optimització i la implementació de l’etapa d’adquisició d’un receptor GPS. També inclou una revisió breu del sistema GPS i els seus principis de funcionament. El procés d’adquisició s’ha estudiat amb detall i programat en els entorns de treball Matlab i Simulink. El fet d’implementar aquesta etapa en dos entorns diferents ha estat molt útil tant de cara a l’aprenentatge com també per la comprovació dels resultats obtinguts. El principal objectiu del treball és el disseny d’un model Simulink que es capaç d’adquirir una senyal capturada amb hardware real. En realitat, s’han fet dues implementacions: una que utilitza blocs propis de Simulink i l’altra que utilitza blocs de la llibreria Xilinx. D’aquesta manera, posteriorment, es facilitaria la transició del model a la FPGA utilitzant l’entorn ISE de Xilinx. La implementació de l’etapa d’adquisició es basa en el mètode de cerca de fase de codi en paral·lel, el qual empra la operació correlació creuada mitjançant la transformada ràpida de Fourier (FFT). Per aquest procés es necessari realitzar dues transformades (per a la senyal entrant i el codi de referència) i una antitransformada de Fourier (per al resultat de la correlació). Per tal d’optimitzar el disseny s’utilitza un bloc FFT, ja que tres blocs consumeixen gran part dels recursos d’una FPGA. En lloc de replicar el bloc FFT, en el model el bloc és compartit en el temps gràcies a l’ús de buffers i commutadors, com a resultat la quantitat de recursos requerits per una implementació en una FPGA es podria reduir considerablement.

A numerical solver for a nonlinear Fokker-Planck equation representation of neuronal network dynamics

To describe the collective behavior of large ensembles of neurons in neuronal network, a kinetic theory description was developed in [13, 12], where a macroscopic representation of the network dynamics was directly derived from the microscopic dynamics of individual neurons, which are modeled by conductance-based, linear, integrate-and-fire point neurons. A diffusion approximation then led to a nonlinear Fokker-Planck equation for the probability density function of neuronal membrane potentials and synaptic conductances. In this work, we propose a deterministic numerical scheme for a Fokker-Planck model of an excitatory-only network. Our numerical solver allows us to obtain the time evolution of probability distribution functions, and thus, the evolution of all possible macroscopic quantities that are given by suitable moments of the probability density function. We show that this deterministic scheme is capable of capturing the bistability of stationary states observed in Monte Carlo simulations. Moreover, the transient behavior of the firing rates computed from the Fokker-Planck equation is analyzed in this bistable situation, where a bifurcation scenario, of asynchronous convergence towards stationary states, periodic synchronous solutions or damped oscillatory convergence towards stationary states, can be uncovered by increasing the strength of the excitatory coupling. Finally, the computation of moments of the probability distribution allows us to validate the applicability of a moment closure assumption used in [13] to further simplify the kinetic theory.

Gestión de recursos en nodos multi-core de memoria compartida

La gestión de recursos en los procesadores multi-core ha ganado importancia con la evolución de las aplicaciones y arquitecturas. Pero esta gestión es muy compleja. Por ejemplo, una misma aplicación paralela ejecutada múltiples veces con los mismos datos de entrada, en un único nodo multi-core, puede tener tiempos de ejecución muy variables. Hay múltiples factores hardware y software que afectan al rendimiento. La forma en que los recursos hardware (cómputo y memoria) se asignan a los procesos o threads, posiblemente de varias aplicaciones que compiten entre sí, es fundamental para determinar este rendimiento. La diferencia entre hacer la asignación de recursos sin conocer la verdadera necesidad de la aplicación, frente a asignación con una meta específica es cada vez mayor. La mejor manera de realizar esta asignación és automáticamente, con una mínima intervención del programador. Es importante destacar, que la forma en que la aplicación se ejecuta en una arquitectura no necesariamente es la más adecuada, y esta situación puede mejorarse a través de la gestión adecuada de los recursos disponibles. Una apropiada gestión de recursos puede ofrecer ventajas tanto al desarrollador de las aplicaciones, como al entorno informático donde ésta se ejecuta, permitiendo un mayor número de aplicaciones en ejecución con la misma cantidad de recursos. Así mismo, esta gestión de recursos no requeriría introducir cambios a la aplicación, o a su estrategia operativa. A fin de proponer políticas para la gestión de los recursos, se analizó el comportamiento de aplicaciones intensivas de cómputo e intensivas de memoria. Este análisis se llevó a cabo a través del estudio de los parámetros de ubicación entre los cores, la necesidad de usar la memoria compartida, el tamaño de la carga de entrada, la distribución de los datos dentro del procesador y la granularidad de trabajo. Nuestro objetivo es identificar cómo estos parámetros influyen en la eficiencia de la ejecución, identificar cuellos de botella y proponer posibles mejoras. Otra propuesta es adaptar las estrategias ya utilizadas por el Scheduler con el fin de obtener mejores resultados.

Underwater Gigamosaicing

El procés de fusió de dues o més imatges de la mateixa escena en una d'única i més gran és conegut com a Image Mosaicing. Un cop finalitzat el procés de construcció d'un mosaic, els límits entre les imatges són habitualment visibles, degut a imprecisions en els registres fotomètric i geomètric. L'Image Blending és l'etapa del procediment de mosaicing a la que aquests artefactes són minimitzats o suprimits. Existeixen diverses metodologies a la literatura que tracten aquests problemes, però la majoria es troben orientades a la creació de panorames terrestres, imatges artístiques d'alta resolució o altres aplicacions a les quals el posicionament de la càmera o l'adquisició de les imatges no són etapes rellevants. El treball amb imatges subaquàtiques presenta desafiaments importants, degut a la presència d'scattering (reflexions de partícules en suspensió) i atenuació de la llum i a condicions físiques extremes a milers de metres de profunditat, amb control limitat dels sistemes d'adquisició i la utilització de tecnologia d'alt cost. Imatges amb il·luminació artificial similar, sense llum global com la oferta pel sol, han de ser unides sense mostrar una unió perceptible. Les imatges adquirides a gran profunditat presenten una qualitat altament depenent de la profunditat, i la seva degradació amb aquest factor és molt rellevant. El principal objectiu del treball és presentar dels principals problemes de la imatge subaquàtica, seleccionar les estratègies més adequades i tractar tota la seqüència adquisició-procesament-visualització del procés. Els resultats obtinguts demostren que la solució desenvolupada, basada en una Estratègia de Selecció de Límit Òptim, Fusió en el Domini del Gradient a les regions comunes i Emfatització Adaptativa d'Imatges amb baix nivell de detall permet obtenir uns resultats amb una alta qualitat. També s'ha proposat una estratègia, amb possibilitat d'implementació paral·lela, que permet processar mosaics de kilòmetres d'extensió amb resolució de centímetres per píxel.

Aprendre a Ensenyar a Resoldre Problemes

La finalitat general del projecte és la millora de la formació dels estudiants de magisteri i de professorat, pel que fa a la seva visió i els seus coneixements sobre l'ensenyament i aprenentatge de les matemàtiques, a partir d'una redefinició de les diferents assignatures de didàctica de les matemàtiques. Es pren l'aprenentatge de l'ensenyament de la resolució de problemes com a eix vertebrador de les assignatures, introduint la realitat de l'aula per mitjà de la interpretació de casos professionals gravats en videoclips. El projecte pretén elaborar materials docents així com dissenyar i experimentar noves metodologies, tant en l'àmbit presencial com virtual, i al mateix temps fomentar la coordinació del professorat que imparteix les assignatures de didàctica. Tot el material es recollirà en una base de dades en l'ADRE, que permetrà la consulta tant presencial com virtual dels materials docents i casos professionals recollits per parts de l'alumnat i professorat. Els objectius a assolits responen a la finalitat del projecte i estan relacionats amb moltes de les prioritats de la convocatòria, ja que impliquen, entre altres coses, la producció de material docent, l’experimentació de noves metodologies i la interrelació entre teoria i pràctica professional.

Aula matemàtica, 2a. part. : un projecte per a la millora de l'aprenentatge de les matemàtiques a la UAB

El projecte Aula Matemàtica consta de dues parts. 1. Elaborar un material d'autoaprenentatge en suport digital que cobreixi tots els temes de Matemàtiques de 1r. curs de les carreres de Ciències (Biologia, Química, etc.) i les Enginyeries. Aquest material, accessible des de qualsevol ordinador connectat a Internet, és una base de dades de problemes que els alumnes poden utilitzar per a treballar el temes explicats a classe, o be per cobrir deficiències a la seva formació pre-universitària. Al mateix temps, es poden realitzar exàmens, i els alumnes poden practicar amb els problemes d'examen. 2. Durant unes hores cada dia, oferir una (o diverses) aules d'informàtica al campus de la UAB amb presència de personal de suport (professors, o becaris de darrers cursos de matemàtiques o doctorat) per tal que els alumnes que vulguin (o necessitin) puguin practicar amb ajuda, i consultat els dubtes que tinguin. En la fase actual del projecte s’han fet les següents actuacions: 1. S’ha obert una aula d’informàtica amb suport de becaris a la facultat de Ciències, on a més de practicar els alumnes, s’han efectuat exàmens. 2. S’ha treballat en el programa per tal de fer-lo més amigable. 3. S’ha ampliat la base de problemes fins a 1450, i cobrir totes les assignatures de Matemàtiques i Estadística de 1r. curs de la facultat de Ciències i l’Escola Tècnica Superior d’Enginyeries. 4. S’ha començat a treballar per a la utilització del programa a Secundària. 5. S’han fet avanços molt importants per tal d’incorporar problemes amb resposta oberta. 6. El programa és accessible des de qualsevol ordenador amb Internet.

Alineamiento de secuencias genéticas en procesadores multicore

Este trabajo analiza el rendimiento del algoritmo de alineamiento de secuencias conocido como Needleman-Wunsch, sobre 3 sistemas de cómputo multiprocesador diferentes. Se analiza y se codifica el algoritmo serie usando el lenguaje de programación C y se plantean una serie de optimizaciones con la finalidad de minimizar el volumen y el tiempo de cómputo. Posteriormente, se realiza un análisis de las prestaciones del programa sobre los diferentes sistemas de cómputo. En la segunda parte del trabajo, se paraleliza el algoritmo serie y se codifica ayudándonos de OpenMP. El resultado son dos variantes del programa que difieren en la relación entre la cantidad de cómputo y la de comunicación. En la primera variante, la comunicación entre procesadores es poco frecuente y se realiza tras largos periodos de ejecución (granularidad gruesa). En cambio, en la segunda variante las tareas individuales son relativamente pequeñas en término de tiempo de ejecución y la comunicación entre los procesadores es frecuente (granularidad fina). Ambas variantes se ejecutan y analizan en arquitecturas multicore que explotan el paralelismo a nivel de thread. Los resultados obtenidos muestran la importancia de entender y saber analizar el efecto del multicore y multithreading en el rendimiento.

A geometric mechanism of diffusion: Rigorous verification in a priori unstable Hamiltonian systems

In this paper we consider a representative a priori unstable Hamiltonian system with 2+1/2 degrees of freedom, to which we apply the geometric mechanism for diffusion introduced in the paper Delshams et al., Mem.Amer.Math. Soc. 2006, and generalized in Delshams and Huguet, Nonlinearity 2009, and provide explicit, concrete and easily verifiable conditions for the existence of diffusing orbits. The simplification of the hypotheses allows us to perform explicitly the computations along the proof, which contribute to present in an easily understandable way the geometric mechanism of diffusion. In particular, we fully describe the construction of the scattering map and the combination of two types of dynamics on a normally hyperbolic invariant manifold.

3D gait assessment in young and elderly subjects using foot-worn inertial sensors.

This study describes the validation of a new wearable system for assessment of 3D spatial parameters of gait. The new method is based on the detection of temporal parameters, coupled to optimized fusion and de-drifted integration of inertial signals. Composed of two wirelesses inertial modules attached on feet, the system provides stride length, stride velocity, foot clearance, and turning angle parameters at each gait cycle, based on the computation of 3D foot kinematics. Accuracy and precision of the proposed system were compared to an optical motion capture system as reference. Its repeatability across measurements (test-retest reliability) was also evaluated. Measurements were performed in 10 young (mean age 26.1±2.8 years) and 10 elderly volunteers (mean age 71.6±4.6 years) who were asked to perform U-shaped and 8-shaped walking trials, and then a 6-min walking test (6MWT). A total of 974 gait cycles were used to compare gait parameters with the reference system. Mean accuracy±precision was 1.5±6.8cm for stride length, 1.4±5.6cm/s for stride velocity, 1.9±2.0cm for foot clearance, and 1.6±6.1° for turning angle. Difference in gait performance was observed between young and elderly volunteers during the 6MWT particularly in foot clearance. The proposed method allows to analyze various aspects of gait, including turns, gait initiation and termination, or inter-cycle variability. The system is lightweight, easy to wear and use, and suitable for clinical application requiring objective evaluation of gait outside of the lab environment.

Line search multilevel optimization as computational methods for dense optical flow

We evaluate the performance of different optimization techniques developed in the context of optical flowcomputation with different variational models. In particular, based on truncated Newton methods (TN) that have been an effective approach for large-scale unconstrained optimization, we develop the use of efficient multilevel schemes for computing the optical flow. More precisely, we evaluate the performance of a standard unidirectional multilevel algorithm - called multiresolution optimization (MR/OPT), to a bidrectional multilevel algorithm - called full multigrid optimization (FMG/OPT). The FMG/OPT algorithm treats the coarse grid correction as an optimization search direction and eventually scales it using a line search. Experimental results on different image sequences using four models of optical flow computation show that the FMG/OPT algorithm outperforms both the TN and MR/OPT algorithms in terms of the computational work and the quality of the optical flow estimation.

THE USE OF SIMULATIONS IN EVOLUTIONARY POPULATION GENETICS: APPLICATIONS ON HUMANS, OWLS AND VIRTUAL ORGANISMS

Summary (in English) Computer simulations provide a practical way to address scientific questions that would be otherwise intractable. In evolutionary biology, and in population genetics in particular, the investigation of evolutionary processes frequently involves the implementation of complex models, making simulations a particularly valuable tool in the area. In this thesis work, I explored three questions involving the geographical range expansion of populations, taking advantage of spatially explicit simulations coupled with approximate Bayesian computation. First, the neutral evolutionary history of the human spread around the world was investigated, leading to a surprisingly simple model: A straightforward diffusion process of migrations from east Africa throughout a world map with homogeneous landmasses replicated to very large extent the complex patterns observed in real human populations, suggesting a more continuous (as opposed to structured) view of the distribution of modern human genetic diversity, which may play a better role as a base model for further studies. Second, the postglacial evolution of the European barn owl, with the formation of a remarkable coat-color cline, was inspected with two rounds of simulations: (i) determine the demographic background history and (ii) test the probability of a phenotypic cline, like the one observed in the natural populations, to appear without natural selection. We verified that the modern barn owl population originated from a single Iberian refugium and that they formed their color cline, not due to neutral evolution, but with the necessary participation of selection. The third and last part of this thesis refers to a simulation-only study inspired by the barn owl case above. In this chapter, we showed that selection is, indeed, effective during range expansions and that it leaves a distinguished signature, which can then be used to detect and measure natural selection in range-expanding populations. Résumé (en français) Les simulations fournissent un moyen pratique pour répondre à des questions scientifiques qui seraient inabordable autrement. En génétique des populations, l'étude des processus évolutifs implique souvent la mise en oeuvre de modèles complexes, et les simulations sont un outil particulièrement précieux dans ce domaine. Dans cette thèse, j'ai exploré trois questions en utilisant des simulations spatialement explicites dans un cadre de calculs Bayésiens approximés (approximate Bayesian computation : ABC). Tout d'abord, l'histoire de la colonisation humaine mondiale et de l'évolution de parties neutres du génome a été étudiée grâce à un modèle étonnement simple. Un processus de diffusion des migrants de l'Afrique orientale à travers un monde avec des masses terrestres homogènes a reproduit, dans une très large mesure, les signatures génétiques complexes observées dans les populations humaines réelles. Un tel modèle continu (opposé à un modèle structuré en populations) pourrait être très utile comme modèle de base dans l'étude de génétique humaine à l'avenir. Deuxièmement, l'évolution postglaciaire d'un gradient de couleur chez l'Effraie des clocher (Tyto alba) Européenne, a été examiné avec deux séries de simulations pour : (i) déterminer l'histoire démographique de base et (ii) tester la probabilité qu'un gradient phénotypique, tel qu'observé dans les populations naturelles puisse apparaître sans sélection naturelle. Nous avons montré que la population actuelle des chouettes est sortie d'un unique refuge ibérique et que le gradient de couleur ne peux pas s'être formé de manière neutre (sans l'action de la sélection naturelle). La troisième partie de cette thèse se réfère à une étude par simulations inspirée par l'étude de l'Effraie. Dans ce dernier chapitre, nous avons montré que la sélection est, en effet, aussi efficace dans les cas d'expansion d'aire de distribution et qu'elle laisse une signature unique, qui peut être utilisée pour la détecter et estimer sa force.

Credit risk contributions under the Vasicek one-factor model: a fast wavelet expansion approximation

To measure the contribution of individual transactions inside the total risk of a credit portfolio is a major issue in financial institutions. VaR Contributions (VaRC) and Expected Shortfall Contributions (ESC) have become two popular ways of quantifying the risks. However, the usual Monte Carlo (MC) approach is known to be a very time consuming method for computing these risk contributions. In this paper we consider the Wavelet Approximation (WA) method for Value at Risk (VaR) computation presented in [Mas10] in order to calculate the Expected Shortfall (ES) and the risk contributions under the Vasicek one-factor model framework. We decompose the VaR and the ES as a sum of sensitivities representing the marginal impact on the total portfolio risk. Moreover, we present technical improvements in the Wavelet Approximation (WA) that considerably reduce the computational effort in the approximation while, at the same time, the accuracy increases.