Aceleración de Algoritmos en Procesadores Multicore, GPGPU y FPGA. Algorithm Acceleration with Multicore, GPGPU and FPGA Processors.

El avance en la potencia de cómputo en nuestros días viene dado por la paralelización del procesamiento, dadas las características que disponen las nuevas arquitecturas de hardware. Utilizar convenientemente este hardware impacta en la aceleración de los algoritmos en ejecución (programas). Sin embargo, convertir de forma adecuada el algoritmo en su forma paralela es complejo, y a su vez, esta forma, es específica para cada tipo de hardware paralelo. En la actualidad los procesadores de uso general más comunes son los multicore, procesadores paralelos, también denominados Symmetric Multi-Processors (SMP). Hoy en día es difícil hallar un procesador para computadoras de escritorio que no tengan algún tipo de paralelismo del caracterizado por los SMP, siendo la tendencia de desarrollo, que cada día nos encontremos con procesadores con mayor numero de cores disponibles. Por otro lado, los dispositivos de procesamiento de video (Graphics Processor Units - GPU), a su vez, han ido desarrollando su potencia de cómputo por medio de disponer de múltiples unidades de procesamiento dentro de su composición electrónica, a tal punto que en la actualidad no es difícil encontrar placas de GPU con capacidad de 200 a 400 hilos de procesamiento paralelo. Estos procesadores son muy veloces y específicos para la tarea que fueron desarrollados, principalmente el procesamiento de video. Sin embargo, como este tipo de procesadores tiene muchos puntos en común con el procesamiento científico, estos dispositivos han ido reorientándose con el nombre de General Processing Graphics Processor Unit (GPGPU). A diferencia de los procesadores SMP señalados anteriormente, las GPGPU no son de propósito general y tienen sus complicaciones para uso general debido al límite en la cantidad de memoria que cada placa puede disponer y al tipo de procesamiento paralelo que debe realizar para poder ser productiva su utilización. Los dispositivos de lógica programable, FPGA, son dispositivos capaces de realizar grandes cantidades de operaciones en paralelo, por lo que pueden ser usados para la implementación de algoritmos específicos, aprovechando el paralelismo que estas ofrecen. Su inconveniente viene derivado de la complejidad para la programación y el testing del algoritmo instanciado en el dispositivo. Ante esta diversidad de procesadores paralelos, el objetivo de nuestro trabajo está enfocado en analizar las características especificas que cada uno de estos tienen, y su impacto en la estructura de los algoritmos para que su utilización pueda obtener rendimientos de procesamiento acordes al número de recursos utilizados y combinarlos de forma tal que su complementación sea benéfica. Específicamente, partiendo desde las características del hardware, determinar las propiedades que el algoritmo paralelo debe tener para poder ser acelerado. Las características de los algoritmos paralelos determinará a su vez cuál de estos nuevos tipos de hardware son los mas adecuados para su instanciación. En particular serán tenidos en cuenta el nivel de dependencia de datos, la necesidad de realizar sincronizaciones durante el procesamiento paralelo, el tamaño de datos a procesar y la complejidad de la programación paralela en cada tipo de hardware. Today´s advances in high-performance computing are driven by parallel processing capabilities of available hardware architectures. These architectures enable the acceleration of algorithms when thes ealgorithms are properly parallelized and exploit the specific processing power of the underneath architecture. Most current processors are targeted for general pruposes and integrate several processor cores on a single chip, resulting in what is known as a Symmetric Multiprocessing (SMP) unit. Nowadays even desktop computers make use of multicore processors. Meanwhile, the industry trend is to increase the number of integrated rocessor cores as technology matures. On the other hand, Graphics Processor Units (GPU), originally designed to handle only video processing, have emerged as interesting alternatives to implement algorithm acceleration. Current available GPUs are able to implement from 200 to 400 threads for parallel processing. Scientific computing can be implemented in these hardware thanks to the programability of new GPUs that have been denoted as General Processing Graphics Processor Units (GPGPU).However, GPGPU offer little memory with respect to that available for general-prupose processors; thus, the implementation of algorithms need to be addressed carefully. Finally, Field Programmable Gate Arrays (FPGA) are programmable devices which can implement hardware logic with low latency, high parallelism and deep pipelines. Thes devices can be used to implement specific algorithms that need to run at very high speeds. However, their programmability is harder that software approaches and debugging is typically time-consuming. In this context where several alternatives for speeding up algorithms are available, our work aims at determining the main features of thes architectures and developing the required know-how to accelerate algorithm execution on them. We look at identifying those algorithms that may fit better on a given architecture as well as compleme

Verificación de Sistemas Basada en Teoría de Tipos. System verification in type theory

Este proyecto se enmarca en la utlización de métodos formales (más precisamente, en la utilización de teoría de tipos) para garantizar la ausencia de errores en programas. Por un lado se plantea el diseño de nuevos algoritmos de chequeo de tipos. Para ello, se proponen nuevos algoritmos basados en la idea de normalización por evaluación que sean extensibles a otros sistemas de tipos. En el futuro próximo extenderemos resultados que hemos conseguido recientemente [16,17] para obtener: una simplificación de los trabajos realizados para sistemas sin regla eta (acá se estudiarán dos sistemas: a la Martin Löf y a la PTS), la formulación de estos chequeadores para sistemas con variables, generalizar la noción de categoría con familia utilizada para dar semántica a teoría de tipos, obtener una formulación categórica de la noción de normalización por evaluación y finalmente, aplicar estos algoritmos a sistemas con reescrituras. Para los primeros resultados esperados mencionados, nos proponemos como método adaptar las pruebas de [16,17] a los nuevos sistemas. La importancia radica en que permitirán tornar más automatizables (y por ello, más fácilmente utilizables) los asistentes de demostración basados en teoría de tipos. Por otro lado, se utilizará la teoría de tipos para certificar compiladores, intentando llevar adelante la propuesta nunca explorada de [22] de utilizar un enfoque abstracto basado en categorías funtoriales. El método consistirá en certificar el lenguaje "Peal" [29] y luego agregar sucesivamente funcionalidad hasta obtener Forsythe [23]. En este período esperamos poder agregar varias extensiones. La importancia de este proyecto radica en que sólo un compilador certificado garantiza que un programa fuente correcto se compile a un programa objeto correcto. Es por ello, crucial para todo proceso de verificación que se base en verificar código fuente. Finalmente, se abordará la formalización de sistemas con session types. Los mismos han demostrado tener fallas en sus formulaciones [30], por lo que parece conveniente su formalización. Durante la marcha de este proyecto, esperamos tener alguna formalización que dé lugar a un algoritmo de chequeo de tipos y a demostrar las propiedades usuales de los sistemas. La contribución es arrojar un poco de luz sobre estas formulaciones cuyos errores revelan que el tema no ha adquirido aún suficiente madurez o comprensión por parte de la comunidad. This project is about using type theory to garantee program correctness. It follows three different directions: 1) Finding new type-checking algorithms based on normalization by evaluation. First, we would show that recent results like [16,17] extend to other type systems like: Martin-Löf´s type theory without eta rule, PTSs, type systems with variables (in addition to systems in [16,17] which are a la de Bruijn), systems with rewrite rules. This will be done by adjusting the proofs in [16,17] so that they apply to such systems as well. We will also try to obtain a more general definition of categories with families and normalization by evaluation, formulated in categorical terms. We expect this may turn proof-assistants more automatic and useful. 2) Exploring the proposal in [22] to compiler construction for Algol-like languages using functorial categories. According to [22] such approach is suitable for verifying compiler correctness, claim which was never explored. First, the language Peal [29] will be certified in type theory and we will gradually add funtionality to it until a correct compiler for the language Forsythe [23] is obtained. 3) Formilizing systems for session types. Several proposals have shown to be faulty [30]. This means that a formalization of it may contribute to the general understanding of session types.

Abordagem otimizada na ressuscitação cardiocerebral

A ressuscitação cardiocerebral (RCC) é uma nova abordagem à ressuscitação de pacientes com parada cardíaca fora do hospital (PCFH). O primeiro componente principal da RCC são as compressões torácicas contínuas (CTC), também chamadas de RCP com compressões torácicas isoladas ou "RCP somente com compressões torácicas" ("Hands-only" CPR), recomendadas como parte da RCC por todos os observadores que testemunhem um colapso súbito de origem presumidamente cardíaco. O segundo componente é um novo algoritmo de tratamento de Suporte Avançado de Vida em Cardiologia (ACLS) para Serviços Médicos de Emergência (SME). Esse algoritmo enfatiza compressões torácicas ininterruptas a despeito de outros procedimentos contínuos como parte do esforço de resgate. Um terceiro componente foi recentemente adicionado à RCC, e é o cuidado agressivo pós-ressuscitação. A RCC tem aumentado a participação de testemunhas e tem melhorado as taxas de sobrevivência em varias comunidades. Essa é a hora para outras comunidades re-examinarem seus próprios desfechos com parada cardíaca e considerar a possibilidade de se juntar a essas cidades e comunidades que dobraram e até mesmo triplicaram as suas taxas de sobrevivência de PCFH.

Quantificação da área de infarto usando-se SPECT de perfusão miocárdica de alta resolução em ratos

FUNDAMENTO: Técnicas de imageamento in vivo permitem avaliar sequencialmente a morfologia e a função dos órgãos em diversos modelos experimentais. Desenvolvemos um dispositivo de adaptação de uma gama-câmara clínica para obter imagens tomográficas por emissão de fótons singulares (SPECT) de alta resolução, baseado em colimador pinhole. OBJETIVO: Determinar a acurácia desse sistema na quantificação da área de infarto miocárdico em ratos. MÉTODOS: Treze ratos Wistar machos (250 g) foram submetidos a infarto do miocárdio por oclusão da artéria coronária esquerda. Após 4 semanas, foram adquiridas imagens tomográficas com o sistema desenvolvido, 1,5 hora após a injeção endovenosa de 555MBq de 99mTc-Sestamibi. Na reconstrução tomográfica, utilizamos software especialmente desenvolvido baseado no algoritmo de Máxima Verossimilhança. Comparamos as médias e analisamos a correlação entre a extensão dos defeitos perfusionais detectados pela cintilografia e a extensão da fibrose miocárdica avaliada pela histologia. RESULTADOS: As imagens apresentaram ótima relação órgão-alvo/fundo, com apropriada visualização das paredes e da cavidade do ventrículo esquerdo. Todos os animais exibindo áreas de infarto foram corretamente identificados pelas imagens de perfusão. Não houve diferença entre a área do infarto medida pelo SPECT (21,1 ± 21,2%) e pela histologia (21,7 ± 22,0%; p = 0,45), obtendo forte correlação entre os valores da área de infarto mensurada pelos dois métodos (r = 0,99; p < 0,0001). CONCLUSÃO: O sistema desenvolvido apresentou resolução espacial adequada e elevada acurácia para detecção e quantificação das áreas de infarto miocárdico, sendo uma opção de baixo custo e grande versatilidade na obtenção de imagens em SPECT de alta resolução de órgãos de pequenos roedores.

Expressao genica associada ao estresse oxidativo no coracao de camundongo apos isquemia intestinal

FUNDAMENTO: O fenômeno da isquemia e reperfusão intestinal é um evento frequente na clínica e está associado a repercussões deletérias em órgãos a distância, em especial ao coração. OBJETIVO: Investigar a expressão gênica do estresse oxidativo e defesa antioxidante no coração de camundongos isogênicos, submetidos a isquemia e reperfusão intestinal (IR). MÉTODOS: Doze camundongos (C57BL/6) foram distribuídos em dois grupos: Grupo IR (GIR) com 60 min de oclusão da artéria mesentérica superior, seguidos de 60 min de reperfusão. Grupo Controle (GC) submetidos a anestesia e a laparotomia sem o procedimento de IR observados por 120 min. As amostras de intestino e coração foram processadas pelo método (RT-qPCR / Reverse transcriptase - quantitative Polymerase Chain Reaction) para determinar a expressão gênica de 84 genes relacionados ao estresse oxidativo ("t" de Student, p < 0,05). RESULTADOS: Observou-se no tecido intestinal (GIR) uma expressão significantemente aumentada em 65 (74,71%) genes em relação ao tecido normal (GC), e 37 (44,04%) genes estiveram hiperexpressos (maior que três vezes o limiar permitido pelo algoritmo). No tocante aos efeitos da I/R intestinal a distância no tecido cardíaco verificou-se a expressão significantemente aumentada de 28 genes (33,33%), mas somente oito genes (9,52%) se hiperexpressaram três vezes acima do limiar. Quatro (7,14%) desses oito genes se expressaram simultaneamente nos tecidos intestinal e cardíaco. No GIR notaram-se cardiomiócitos com núcleos de menor tamanho, picnóticos, ricos em heterocromatina e raros nucléolos, indicando sofrimento cardíaco. CONCLUSÃO: A I/R intestinal promoveu a hiperexpressão estatisticamente significante de oito genes associados ao estresse oxidativo a distância no tecido miocárdico.

Escolha de áreas prioritárias de conservação de anfíbios anuros do Cerrado através de um modelo de populações centrais-periféricas

Uma das maiores ameaças à diversidade biológica é a perda de hábitat, de modo que uma das alternativas para proteção da biodiversidade é a seleção de reservas pela utilização de procedimentos de otimização para estabelecer áreas prioritárias para conservação. Neste estudo, um algoritmo simulated annealing foi usado para verificar como a periferia das distribuições das espécies influencia na seleção de áreas no Cerrado para conservação de 131 espécies de anfíbios anuros. Dois conjuntos de dados foram analisados, um contendo a distribuição original das espécies e outro excluindo a periferia das distribuições. As redes ótimas encontradas a partir das distribuições originais contiveram 17 quadrículas enquanto aquelas encontradas a partir das distribuições restritas foram maiores, com 22 células. As células com alto grau de insubstituibilidade foram mantidas em todas as redes e novas regiões de células substituíveis, localizadas na margem do bioma, surgiram quando apenas as distribuições reduzidas foram usadas.

Simulación Monte Carlo de las dosis en tumores de pulmón en tratamientos de radioterapia estereotáxica extracraneal

Estudio elaborado a partir de una estancia en el Karolinska University Hospital, Suecia, entre marzo y junio del 2006. En la radioterapia estereotáxica extracraneal (SBRT) de tumores de pulmón existen principalmente dos problemas en el cálculo de la dosis con los sistemas de planificación disponibles: la precisión limitada de los algoritmos de cálculo en presencia de tejidos con densidades muy diferentes y los movimientos debidos a la respiración del paciente durante el tratamiento. El objetivo de este trabajo ha sido llevar a cabo la simulación con el código Monte Carlo PENELOPE de la distribución de dosis en tumores de pulmón en casos representativos de tratamientos con SBRT teniendo en cuenta los movimientos respiratorios y su comparación con los resultados de varios planificadores. Se han estudiado casos representativos de tratamientos de SBRT en el Karolinska University Hospital. Los haces de radiación se han simulado mediante el código PENELOPE y se han usado para la obtención de los resultados MC de perfiles de dosis. Los resultados obtenidos para el caso estático (sin movimiento respiratorio ) ponen de manifiesto que, en comparación con la MC, la dosis (Gy/MU) calculada por los planificadores en el tumor tiene una precisión del 2-3%. En la zona de interfase entre tumor y tejido pulmonar los planificadores basados en el algoritmo PB sobrestiman la dosis en un 10%, mientras que el algoritmo CC la subestima en un 3-4%. Los resultados de la simulación mediante MC de los movimientos respiratorios indican que los resultados de los planificadores son suficientemente precisos en el tumor, aunque en la interfase hay una mayor subestimación de la dosis en comparación con el caso estático. Estos resultados son compatibles con la experiencia clínica adquirida durante 15 años en el Karolinska University Hospital. Los resultados se han publicado en la revista Acta Oncologica.

Sistema adaptativo para la predicción de incendios forestales basado en estrategias estadístico-evolutivas

Es proposa mètodes per a millorar la qualitat de predicció d'Incendis forestals per mitjà de combinació d'estratègies basades en guia de dades. Els simuladors de foc són implementacions de models físics i matemàtics que són abstraccions de la realitat i per a funcionar necessiten paràmetres difícils de mesurar i/o amb un comportament dinàmic en el temps. Utilitzant Còmput d'Altes Prestacions apliquem algorismes evolutius reduint l'espai de cerca dels valors que posteriorment s'integren en un conjunt de possibilitats. Els resultats presenten adaptació al canvi de condicions de l'incendi que serveix de base per a generar una aplicación de temps real.

Predicción de incendios forestales basada en algoritmos evolutivos guiados por los datos

En este trabajo se propone un método para mejorar la predicción de la propagación de incendios forestales. En la actualidad existen diversos simuladores de comportamiento del fuego los cuales utilizan diversos parámetros de entrada. Estos parámetros de entrada suelen ser una fuente de imprecisión dada la dificultad que resulta disponer de sus valores reales. Este trabajo intenta mejorar las predicciones mediante la mejora de la precisión de los parámetros de entrada. Se utiliza un algoritmo genético guiado utilizando conocimiento disponible. Los resultados observados demuestran que utilizar conocimiento mejora la precisión de las predicciones y acelera dicho proceso.

Calibración TLR y LRM en MATLAB para medidas con guías de onda

En este proyecto, lo primero que hemos hecho ha sido desarrollar un algoritmo en Matlab que implementara el método de calibración TRL, el funcionamiento del cual hemos comprobado en primera instancia mediante simulaciones y, posteriormente, mediante un ejemplo real. Posteriormente, hemos desarrollado otro algoritmo en Matlab para implementar el método de calibración LRM. Este algoritmo sólo lo hemos podido comprobar a nivel de simulación. A continuación, mediante los dos algoritmos, hemos realizado una comparación entre ambos sistemas de calibración a través de simulaciones. Finalmente, analizando los resultados de varias simulaciones calibradas con nuestro programa del método TRL, hemos buscado cuáles pueden ser los motivos para la aparición de picos indeseados y hemos encontrado uno de ellos.

Preliminary study of cooperation in hybrid ad-hoc networks

In this paper, we present a first approach to evolve a cooperative behavior in ad hoc networks. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios are unfavorable to the interests of a user. In this paper we deal with the issue of user cooperation in ad hoc networks by developing the algorithm called Generous Tit-For-Tat. We assume that nodes are rational, i.e., their actions are strictly determined by self-interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we study the added behavior of the network.

Extracción de parámetros de un resonador FBAR por optimización

L’objectiu d’aquest projecte que consisteix a elaborar un algoritme d’optimització que permeti, mitjançant un ajust de dades per mínims quadrats, la extracció dels paràmetres del circuit equivalent que composen el model teòric d’un ressonador FBAR, a partir de les mesures dels paràmetres S. Per a dur a terme aquest treball, es desenvolupa en primer lloc tota la teoria necessària de ressonadors FBAR. Començant pel funcionament i l’estructura, i mostrant especial interès en el modelat d’aquests ressonadors mitjançant els models de Mason, Butterworth Van-Dyke i BVD Modificat. En segon terme, s’estudia la teoria sobre optimització i programació No-Lineal. Un cop s’ha exposat la teoria, es procedeix a la descripció de l’algoritme implementat. Aquest algoritme utilitza una estratègia de múltiples passos que agilitzen l'extracció dels paràmetres del ressonador.

Dispositius nanoelectrònics a freqüències de THz : estudi de la propagació electromagnètica en les connexions

Per a altes freqüències, les connexions poden tenir un paper rellevant. Atès que la velocitat de propagació dels senyals electromagnètics, c, en el cable no és infinita, el voltatge i el corrent al llarg del cable varien amb el temps. Per tant, amb l’objectiu de reproduir el comportament elèctric de dispositius nanoelectrònics a freqüències de THz, en aquest treball hem estudiat la regió activa del dispositiu nanoelectrònic i les seves connexions, en un sistema global complex. Per a aquest estudi hem utilitzat un nou concepte de dispositiu anomenat Driven Tunneling Device (DTD). Per a les connexions, hem plantejat el problema a partir de tot el conjunt de les equacions de Maxwell, ja que per a les freqüències i longituds de cable considerats, la contribució del camp magnètic és també important. En particular, hem suposat que la propagació que és dóna en el cable és una propagació transversal electromagnètica (TEM). Un cop definit el problema hem desenvolupat un programa en llenguatge FORTRAN que amb l'algoritme de diferències finites soluciona el sistema global. La solució del sistema global s'ha aplicat a una configuració particular de DTD com a multiplicador de freqüència per tal de discutir quins paràmetres de les connexions permet maximitzar la potència real que pot donar el DTD.

Avaluació dels algorismes d'encaminament per a una NoC amb topologia Mesh 2D

Aquest projecte presenta una avaluació de les diferents alternatives d'encaminament per a una NoC amb una topologia mesh 2D. Per tal d'exposar aquestes alternatives s'ha estudiat la composició d'un router implementat amb l'algorisme determinista XY i s'ha adaptat per tal que aquest suportés els algorismes parcialment adaptatius West First, North Last i Negative First. Un cop tenim els routers implementats es disposa un estudi dels diferents algorismes i com cadascun d'aquests actuen en front uns mateixos estímuls per tal de crear una comparativa entre ells que ens faciliti una elecció a priori.

Modelo de un grupo de robots colaboradores cazadores

El nombre d'aplicacions dels microrobots en biomedicina creix a mesura que el seu desenvolupament avança. Entre elles hi ha les consistents a examinar cèl·lules amb microrobots cooperants. En aquest treball es presenta un prototip a escala d'aquest problema, convenientment simplificat: dos robots tracten d'agafar una pilota que representa la cèl·lula que s'examina. Com a resultat, s'ha obtingut un algorisme deliberatiu per a la resolució d'aquest problema amb robots homogenis.