A framework for scientific computing with GPUs

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Heterogeneous computing with an algorithmic skeleton framework

The Graphics Processing Unit (GPU) is present in almost every modern day personal computer. Despite its specific purpose design, they have been increasingly used for general computations with very good results. Hence, there is a growing effort from the community to seamlessly integrate this kind of devices in everyday computing. However, to fully exploit the potential of a system comprising GPUs and CPUs, these devices should be presented to the programmer as a single platform. The efficient combination of the power of CPU and GPU devices is highly dependent on each device’s characteristics, resulting in platform specific applications that cannot be ported to different systems. Also, the most efficient work balance among devices is highly dependable on the computations to be performed and respective data sizes. In this work, we propose a solution for heterogeneous environments based on the abstraction level provided by algorithmic skeletons. Our goal is to take full advantage of the power of all CPU and GPU devices present in a system, without the need for different kernel implementations nor explicit work-distribution.To that end, we extended Marrow, an algorithmic skeleton framework for multi-GPUs, to support CPU computations and efficiently balance the work-load between devices. Our approach is based on an offline training execution that identifies the ideal work balance and platform configurations for a given application and input data size. The evaluation of this work shows that the combination of CPU and GPU devices can significantly boost the performance of our benchmarks in the tested environments, when compared to GPU-only executions.

Combining non-dominance, objective-order and spread metric to extend firefly algorithm to multi-objective optimization

In this paper, we propose an extension of the firefly algorithm (FA) to multi-objective optimization. FA is a swarm intelligence optimization algorithm inspired by the flashing behavior of fireflies at night that is capable of computing global solutions to continuous optimization problems. Our proposal relies on a fitness assignment scheme that gives lower fitness values to the positions of fireflies that correspond to non-dominated points with smaller aggregation of objective function distances to the minimum values. Furthermore, FA randomness is based on the spread metric to reduce the gaps between consecutive non-dominated solutions. The obtained results from the preliminary computational experiments show that our proposal gives a dense and well distributed approximated Pareto front with a large number of points.

Multi-phase post-mortem CT angiography: development of a standardized protocol.

The objective of this work was to develop an easily applicable technique and a standardized protocol for high-quality post-mortem angiography. This protocol should (1) increase the radiological interpretation by decreasing artifacts due to the perfusion and by reaching a complete filling of the vascular system and (2) ease and standardize the execution of the examination. To this aim, 45 human corpses were investigated by post-mortem computed tomography (CT) angiography using different perfusion protocols, a modified heart-lung machine and a new contrast agent mixture, specifically developed for post-mortem investigations. The quality of the CT angiographies was evaluated radiologically by observing the filling of the vascular system and assessing the interpretability of the resulting images and by comparing radiological diagnoses to conventional autopsy conclusions. Post-mortem angiography yielded satisfactory results provided that the volumes of the injected contrast agent mixture were high enough to completely fill the vascular system. In order to avoid artifacts due to the post-mortem perfusion, a minimum of three angiographic phases and one native scan had to be performed. These findings were taken into account to develop a protocol for quality post-mortem CT angiography that minimizes the risk of radiological misinterpretation. The proposed protocol is easy applicable in a standardized way and yields high-quality radiologically interpretable visualization of the vascular system in post-mortem investigations.

Fusion of Multi-Atlas Segmentations with Spatial Distribution Modeling

In recent years, multi-atlas fusion methods have gainedsignificant attention in medical image segmentation. Inthis paper, we propose a general Markov Random Field(MRF) based framework that can perform edge-preservingsmoothing of the labels at the time of fusing the labelsitself. More specifically, we formulate the label fusionproblem with MRF-based neighborhood priors, as an energyminimization problem containing a unary data term and apairwise smoothness term. We present how the existingfusion methods like majority voting, global weightedvoting and local weighted voting methods can be reframedto profit from the proposed framework, for generatingmore accurate segmentations as well as more contiguoussegmentations by getting rid of holes and islands. Theproposed framework is evaluated for segmenting lymphnodes in 3D head and neck CT images. A comparison ofvarious fusion algorithms is also presented.

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.

Anàlisis, disseny i implementació d'una aplicació de gestió d'històries mèdiques per un sistema multi centres mitjançant tecnologia J2EE, i tecnologia de xarxes de bases de dades

El treball final de carrera 'HISMED', es basa en l'anàlisi, disseny, investigació e implementació d'una aplicació dins l'àmbit assistencial sanitari amb la premissa de voler ser un sistema per oferir un servei sanitari de millor qualitat, i crear un entorn en el qual investigadors, laboratoris, metges i personal docent comparteixen dades amb una rellevància cabdal per les seves professions. Oferint-los una eina de consulta molt potent en quant a l'obtenció de dades clíniques, que els permet explotar la informació segons convingui el cas.

Asymptotic robustness in multi-sample analysis of multivariate linear relations

Standard methods for the analysis of linear latent variable models oftenrely on the assumption that the vector of observed variables is normallydistributed. This normality assumption (NA) plays a crucial role inassessingoptimality of estimates, in computing standard errors, and in designinganasymptotic chi-square goodness-of-fit test. The asymptotic validity of NAinferences when the data deviates from normality has been calledasymptoticrobustness. In the present paper we extend previous work on asymptoticrobustnessto a general context of multi-sample analysis of linear latent variablemodels,with a latent component of the model allowed to be fixed across(hypothetical)sample replications, and with the asymptotic covariance matrix of thesamplemoments not necessarily finite. We will show that, under certainconditions,the matrix $\Gamma$ of asymptotic variances of the analyzed samplemomentscan be substituted by a matrix $\Omega$ that is a function only of thecross-product moments of the observed variables. The main advantage of thisis thatinferences based on $\Omega$ are readily available in standard softwareforcovariance structure analysis, and do not require to compute samplefourth-order moments. An illustration with simulated data in the context ofregressionwith errors in variables will be presented.

Multi-phase postmortem CT angiography: recognizing technique-related artefacts and pitfalls.

BACKGROUND AND PURPOSE: Multi-phase postmortem CT angiography (MPMCTA) is increasingly being recognized as a valuable adjunct medicolegal tool to explore the vascular system. Adequate interpretation, however, requires knowledge about the most common technique-related artefacts. The purpose of this study was to identify and index the possible artefacts related to MPMCTA. MATERIAL AND METHODS: An experienced radiologist blinded to all clinical and forensic data retrospectively reviewed 49 MPMCTAs. Each angiographic phase, i.e. arterial, venous and dynamic, was analysed separately to identify phase-specific artefacts based on location and aspect. RESULTS: Incomplete contrast filling of the cerebral venous system was the most commonly encountered artefact, followed by contrast agent layering in the lumen of the thoracic aorta. Enhancement or so-called oedematization of the digestive system mucosa was also frequently observed. CONCLUSION: All MPMCTA artefacts observed and described here are reproducible and easily identifiable. Knowledge about these artefacts is important to avoid misinterpreting them as pathological findings.

Multi-modal assessment of long-term erythropoietin treatment after neonatal hypoxic-ischemic injury in rat brain.

Erythropoietin (EPO) has been recognized as a neuroprotective agent. In animal models of neonatal brain injury, exogenous EPO has been shown to reduce lesion size, improve structure and function. Experimental studies have focused on short course treatment after injury. Timing, dose and length of treatment in preterm brain damage remain to be defined. We have evaluated the effects of high dose and long-term EPO treatment in hypoxic-ischemic (HI) injury in 3 days old (P3) rat pups using histopathology, magnetic resonance imaging (MRI) and spectroscopy (MRS) as well as functional assessment with somatosensory-evoked potentials (SEP). After HI, rat pups were assessed by MRI for initial damage and were randomized to receive EPO or vehicle. At the end of treatment period (P25) the size of resulting cortical damage and white matter (WM) microstructure integrity were assessed by MRI and cortical metabolism by MRS. Whisker elicited SEP were recorded to evaluate somatosensory function. Brains were collected for neuropathological assessment. The EPO treated animals did not show significant decrease of the HI induced cortical loss at P25. WM microstructure measured by diffusion tensor imaging was improved and SEP response in the injured cortex was recovered in the EPO treated animals compared to vehicle treated animals. In addition, the metabolic profile was less altered in the EPO group. Long-term treatment with high dose EPO after HI injury in the very immature rat brain induced recovery of WM microstructure and connectivity as well as somatosensory cortical function despite no effects on volume of cortical damage. This indicates that long-term high-dose EPO induces recovery of structural and functional connectivity despite persisting gross anatomical cortical alteration resulting from HI.

Symmetrically multilateral-bargained allocations in multi-sided assignment markets

[cat] Aquest treball tracta d’extendre la noció d’equilibri simètric de negociació bilateral introduït per Rochford (1983) a jocs d’assignació multilateral. Un pagament corresponent a un equilibri simètric de negociación multilateral (SMB) és una imputación del core que garanteix que qualsevol agent es troba en equilibri respecte a un procés de negociación entre tots els agents basat en allò que cadascun d’ells podria rebre -i fer servir com a amenaça- en un ’matching’ òptim diferent al que s’ha format. Es prova que, en el cas de jocs d’assignació multilaterals, el conjunt de SMB és sempre no buit i que, a diferència del cas bilateral, no sempre coincideix amb el kernel (Davis and Maschler, 1965). Finalment, responem una pregunta oberta per Rochford (1982) tot introduïnt un conjunt basat en la idea de kernel, que, conjuntament amb el core, ens permet caracteritzar el conjunt de SMB.

Multi-Atlas based Segmentation of Head and Neck CT Images using Active Contour

This paper presents the segmentation of bilateral parotid glands in the Head and Neck (H&N) CT images using an active contour based atlas registration. We compare segmentation results from three atlas selection strategies: (i) selection of "single-most-similar" atlas for each image to be segmented, (ii) fusion of segmentation results from multiple atlases using STAPLE, and (iii) fusion of segmentation results using majority voting. Among these three approaches, fusion using majority voting provided the best results. Finally, we present a detailed evaluation on a dataset of eight images (provided as a part of H&N auto segmentation challenge conducted in conjunction with MICCAI-2010 conference) using majority voting strategy.

Symmetrically multilateral-bargained allocations in multi-sided assignment markets

[cat] Aquest treball tracta d’extendre la noció d’equilibri simètric de negociació bilateral introduït per Rochford (1983) a jocs d’assignació multilateral. Un pagament corresponent a un equilibri simètric de negociación multilateral (SMB) és una imputación del core que garanteix que qualsevol agent es troba en equilibri respecte a un procés de negociación entre tots els agents basat en allò que cadascun d’ells podria rebre -i fer servir com a amenaça- en un ’matching’ òptim diferent al que s’ha format. Es prova que, en el cas de jocs d’assignació multilaterals, el conjunt de SMB és sempre no buit i que, a diferència del cas bilateral, no sempre coincideix amb el kernel (Davis and Maschler, 1965). Finalment, responem una pregunta oberta per Rochford (1982) tot introduïnt un conjunt basat en la idea de kernel, que, conjuntament amb el core, ens permet caracteritzar el conjunt de SMB.

A bio-inspired agent-based programming environment for pervasive platforms

Abstract in English : Ubiquitous Computing is the emerging trend in computing systems. Based on this observation this thesis proposes an analysis of the hardware and environmental constraints that rule pervasive platforms. These constraints have a strong impact on the programming of such platforms. Therefore solutions are proposed to facilitate this programming both at the platform and node levels. The first contribution presented in this document proposes a combination of agentoriented programming with the principles of bio-inspiration (Phylogenesys, Ontogenesys and Epigenesys) to program pervasive platforms such as the PERvasive computing framework for modeling comPLEX virtually Unbounded Systems platform. The second contribution proposes a method to program efficiently parallelizable applications on each computing node of this platform. Résumé en Français : Basée sur le constat que les calculs ubiquitaires vont devenir le paradigme de programmation dans les années à venir, cette thèse propose une analyse des contraintes matérielles et environnementale auxquelles sont soumises les plateformes pervasives. Ces contraintes ayant un impact fort sur la programmation des plateformes. Des solutions sont donc proposées pour faciliter cette programmation tant au niveau de l'ensemble des noeuds qu'au niveau de chacun des noeuds de la plateforme. La première contribution présentée dans ce document propose d'utiliser une alliance de programmation orientée agent avec les grands principes de la bio-inspiration (Phylogénèse, Ontogénèse et Épigénèse). Ceci pour répondres aux contraintes de programmation de plateformes pervasives comme la plateforme PERvasive computing framework for modeling comPLEX virtually Unbounded Systems . La seconde contribution propose quant à elle une méthode permettant de programmer efficacement des applications parallélisable sur chaque noeud de calcul de la plateforme

Statistical mechanics of multi-edge networks

Statistical properties of binary complex networks are well understood and recently many attempts have been made to extend this knowledge to weighted ones. There are, however, subtle yet important considerations to be made regarding the nature of the weights used in this generalization. Weights can be either continuous or discrete magnitudes, and in the latter case, they can additionally have undistinguishable or distinguishable nature. This fact has not been addressed in the literature insofar and has deep implications on the network statistics. In this work we face this problem introducing multiedge networks as graphs where multiple (distinguishable) connections between nodes are considered. We develop a statistical mechanics framework where it is possible to get information about the most relevant observables given a large spectrum of linear and nonlinear constraints including those depending both on the number of multiedges per link and their binary projection. The latter case is particularly interesting as we show that binary projections can be understood from multiedge processes. The implications of these results are important as many real-agent-based problems mapped onto graphs require this treatment for a proper characterization of their collective behavior.