The present document exposes a different approach for haptic rendering, defined as the simulation of force interactions to reproduce the sensation of surface relief in dense models. Current research shows open issues in timely haptic interaction involving large meshes, with several problems affecting performance and fidelity, and without a dominant technique to treat these issues properly. Relying in pure geometric collisions when rendering highly dense mesh models (hundreds of thousands of triangles) sensibly degrades haptic rates due to the sheer number of collisions that must be tracked between the mesh's faces and a haptic probe. Several bottlenecks were identified in order to enhance haptic performance: software architecture and data structures, collision detection, and accurate rendering of surface relief. To account for overall software architecture and data structures, it was derived a complete component framework for transforming standalone VR applications into full-fledged multi-threaded Collaborative Virtual Reality Environments (CVREs), after characterizing existing implementations into a feature-rich superset. Enhancements include: a scalable arbitrated peer-to-peer topology for scene sharing; multi-threaded components for graphics rendering, user interaction and network communications; a collaborative user interface model for session handling; and interchangeable user roles with multi-camera perspectives, avatar awareness and shared annotations. We validate the framework by converting the existing ALICE VR Navigator into a complete CVRE, showing good performance in collaborative manipulation of complex models. To specifically address collision detection computation, we derive a conformal algebra treatment for collisions among points, segments, areas, and volumes, based on collision detection in conformal R{4,1} (5D) space, and implemented in GPU for faster parallel queries. Results show orders of magnitude time reductions in collisions computations, allowing interactive rates. Finally, the main core of the research is the haptic rendering of surface mesostructure in large meshes. Initially, a method for surface haptic rendering was proposed, using image-based Hybrid Rugosity Mesostructures (HRMs) of per-face heightfield displacements and normalmaps layered on top of a simpler mesh, adding greater surface detail than actually present. Haptic perception is achieved modulating the haptic probe's force response using the HRM coat. A usability testbed framework was built to measure experimental performance with a common set tests, meshes and HRMs. Trial results show the goodness of the proposed technique, rendering accurate 3D surface detail at high sampling rates. This local per-face method is extended into a fast global approach for haptic rendering, building a mesostructure-based atlas of depth/normal textures (HyRMA), computed out of surface differences of the same mesh object at two different resolutions: original and simplified. For each triangle in the simplified mesh, an irregular prism is considered defined by the triangle's vertices and their normals. This prism completely covers the original mesh relief over the triangle. Depth distances and surfaces normals within each prism are warped from object volume space to orthogonal tangent space, by means of a novel and fast method for computing barycentric coordinates at the prism, and storing normals and relief in a sorted atlas. Haptic rendering is effected by colliding the probe against the atlas, and effecting a modulated force response at the haptic probe. The method is validated numerically, statistically and perceptually in user testing controlled trials, achieving accurate haptic sensation of large meshes' fine features at interactive rendering rates, with some minute loss of mesostructure detail. / En aquesta tesi es presenta un novedós enfocament per a la percepció hàptica del relleu de models virtuals complexes mitjançant la simulació de les forces d'interacció entre la superfície i un element de contacte. La proposta contribueix a l'estat de l'art de la recerca en aquesta àrea incrementant l'eficiència i la fidelitat de la interacció hàptica amb grans malles de triangles. La detecció de col·lisions amb malles denses (centenars de milers de triangles) limita la velocitat de resposta hàptica degut al gran nombre d'avaluacions d'intersecció cara-dispositiu hàptic que s'han de realitzar. Es van identificar diferents alternatives per a incrementar el rendiment hàptic: arquitectures de software i estructures de dades específiques, algorismes de detecció de col·lisions i reproducció hàptica de relleu superficial. En aquesta tesi es presenten contribucions en alguns d'aquests aspectes. S'ha proposat una estructura completa de components per a transformar aplicacions de Realitat Virtual en Ambients Col·laboratius de Realitat Virtual (CRVEs) multithread en xarxa. L'arquitectura proposada inclou: una topologia escalable punt a punt per a compartir escenes; components multithread per a visualització gràfica, interacció amb usuaris i comunicació en xarxa; un model d'interfície d'usuari col·laboratiu per a la gestió de sessions; i rols intercanviables de l'usuari amb perspectives de múltiples càmeres, presència d'avatars i anotacions compartides. L'estructura s'ha validat convertint el navegador ALICE en un CVRE completament funcional, mostrant un bon rendiment en la manipulació col·laborativa de models complexes. Per a incrementar l'eficiència del càlcul de col·lisions, s'ha proposat un algorisme que treballa en un espai conforme R{4,1} (5D) que permet detectar col·lisions entre punts, segments, triangles i volums. Aquest algorisme s'ha implementat en GPU per obtenir una execució paral·lela més ràpida. Els resultats mostren reduccions en el temps de càlcul de col·lisions permetent interactivitat. Per a la percepció hàptica de malles complexes que modelen objectes rugosos, s'han proposat diferents algorismes i estructures de dades. Les denominades Mesoestructures Híbrides de Rugositat (HRM) permeten substituir els detalls geomètrics d'una cara (rugositats) per dues textures: de normals i d'alçades. La percepció hàptica s'aconsegueix modulant la força de resposta entre el dispositiu hàptic i la HRM. Els tests per avaluar experimentalment l'eficiència del càlcul de col·lisions i la percepció hàptica utilitzant HRM respecte a modelar les rugositats amb geometria, van mostrar que la tècnica proposada va ser encertada, permetent percebre detalls 3D correctes a altes tases de mostreig. El mètode es va estendre per a representar rugositats d'objectes. Es proposa substituir l'objecte per un model simplificat i un atles de mesoestructures en el que s'usen textures de normals i de relleus (HyRMA). Aquest atles s'obté a partir de la diferència en el detall de la superfície entre dos malles del mateix objecte: l'original i la simplificada. A partir d'un triangle de la malla simplificada es construeix un prisma, definit pels vèrtexs del triangle i les seves normals, que engloba el relleu de la malla original sobre el triangle. Les alçades i normals dins del prisma es transformen des de l'espai de volum a l'espai ortogonal tangent, amb mètode novedós i eficient que calcula les coordenades baricèntriques relatives al prisma, per a guardar el mapa de textures transformat en un atles ordenat. La percepció hàptica s'assoleix detectant les col·lisions entre el dispositiu hàptic i l'atles, i modulant la força de resposta d'acord al resultat de la col·lisió. El mètode s'ha validat numèricament, estadística i perceptual en tests amb usuaris, aconseguint una correcta i interactiva sensació tàctil dels objectes simulats mitjançant la mesoestructura de les malles / En esta tesis se presenta un enfoque novedoso para la percepción háptica del relieve de modelos virtuales complejos mediante la simulación de las fuerzas de interacción entre la superficie y un elemento de contacto. La propuesta contribuye al estado del arte de investigación en este área incrementando la eficiencia y fidelidad de interacción háptica con grandes mallas de triángulos. La detección de colisiones con mallas geométricas densas (cientos de miles de triángulos) limita la velocidad de respuesta háptica debido al elevado número de evaluaciones de intersección cara-dispositivo háptico que deben realizarse. Se identificaron diferentes alternativas para incrementar el rendimiento háptico: arquitecturas de software y estructuras de datos específicas, algoritmos de detección de colisiones y reproducción háptica de relieve superficial. En esta tesis se presentan contribuciones en algunos de estos aspectos. Se ha propuesto una estructura completa de componentes para transformar aplicaciones aisladas de Realidad Virtual en Ambientes Colaborativos de Realidad Virtual (CRVEs) multithread en red. La arquitectura propuesta incluye: una topología escalable punto a punto para compartir escenas; componentes multithread para visualización gráfica, interacción con usuarios y comunicación en red; un modelo de interfaz de usuario colaborativo para la gestión de sesiones; y roles intercambiables del usuario con perspectivas de múltiples cámaras, presencia de avatares y anotaciones compartidas. La estructura se ha validado convirtiendo el navegador ALICE en un CVRE completamente funcional, mostrando un buen rendimiento en la manipulación colaborativa de modelos complejos. Para incrementar la eficiencia del cálculo de colisiones, se ha propuesto un algoritmo que trabaja en un espacio conforme R4,1 (5D) que permite detectar colisiones entre puntos, segmentos, triángulos y volúmenes. Este algoritmo se ha implementado en GPU a efectos de obtener una ejecución paralelamás rápida. Los resultadosmuestran reducciones en el tiempo de cálculo de colisiones permitiendo respuesta interactiva. Para la percepción háptica de mallas complejas que modelan objetos rugosos, se han propuesto diferentes algoritmos y estructuras de datos. Las denominadasMesoestructuras Híbridas de Rugosidad (HRM) permiten substituir los detalles geométricos de una cara (rugosidades) por una textura de normales y otra de alturas. La percepción háptica se consigue modulando la fuerza de respuesta entre el dispositivo háptico y la HRM. Los tests realizados para evaluar experimentalmente la eficiencia del cálculo de colisiones y la percepción háptica utilizando HRM respecto a modelar las rugosidades con geometría, mostraron que la técnica propuesta fue acertada, permitiendo percibir detalles 3D correctos a altas tasas de muestreo. Este método anterior es extendido a un procedimiento global para representar rugosidades de objetos. Para hacerlo se propone sustituir el objeto por un modelo simplificado y un atlas de mesostructuras usando texturas de normales y relieves (HyRMA). Este atlas se obtiene de la diferencia en detalle de superficie entre dos mallas del mismo objeto: la original y la simplificada. A partir de un triángulo de la malla simplificada se construye un prisma definido por los vértices del triángulo a lo largo de sus normales, que engloba completamente el relieve de la malla original sobre este triángulo. Las alturas y normales dentro de cada prisma se transforman del espacio de volumen al espacio ortoganal tangente, usando un método novedoso y eficiente que calcula las coordenadas baricéntricas relativas a cada prisma para guardar el mapa de texturas transformado en un atlas ordenado. La percepción háptica se consigue detectando directamente las colisiones entre el dispositivo háptico y el atlas, y modulando la fuerza de respuesta de acuerdo al resultado de la colisión. El procedmiento se ha validado numérica, estadística y perceptualmente en ensayos con usuarios, consiguiendo a tasas interactivas la correcta sensación táctil de los objetos simulados mediante la mesoestructura de las mallas, con alguna pérdida muy puntual de detalle

Els workflows han esdevingut un esquema d’organització de les tasques àmpliament utilitzat per al processament de dades científiques. Aquesta tesis presenta varies tècniques de planificació i de gestió de recursos per a l'execució de workflows científics en entorns de computació híbrids. En els darrers anys, els processadors de les targetes gràfiques (GPUs) han esdevingut un recurs programable que s'ha introduït en els sistemes de còmput com a acceleradors per a executar, a un cost econòmic baix, altres tasques que no sigui el processament gràfic. Un àmbit on s'han introduït ha estat el camp del processament d'imatges mèdiques, degut a que l'alta ressolució i tamany de les imatges suposen un alt cost en recursos i temps de computació. Aquest cas es dóna amb FreeSurfer, que és un conjunt d'eines que defineixen workflows de processament de ressonàncies magnètiques. La introducció d'algunes implementacions en GPU en les etapes del workflow de processament de ressonàncies estructurals des de les versions 5 i 5.3, ha suposat una important reducció del temps d'execució per una sola instància (execució serial) del workflow, al voltant d'un 60-70% en funció de la ressonància d'entrada. Quan volem executar múltiples instàncies del workflow en un mateix node de còmput ens trobem que les GPUs resulten ser coll d'ampolla per la saturació de la memòria de la targeta. Per superar aquestes limitacions s'introdueixen al llarg d'aquest treball vàries tècniques de planificació i gestió dels recursos compartits, en especial la GPU. En el primer estudi es presenta la proposta de planificació que denominem inter-workflow, amb una taula de restriccions que defineix un percentatge d’utilització de recursos per cada etapa i que serveix per prendre les decisions de planificació. Aquesta planificació s’aplica en la gestió de les dependències de dades i d’accés als recursos per al cas d’us definit pel workflow complet d’anàlisi estructural de FreeSurfer. En l’execució de múltiples instancies, aplicant aquesta planificació obtenim una millora de 6,79x respecte l'execució serial. Per altra banda, en el segon estudi realitzat, el cas d’us és el subflow de FreeSurfer per a la reconstrucció volumètrica. Amb la planificació que denominem per lots s'introdueixen mecanismes de control de combinacions de les tasques de les diferents instàncies a executar, i obtenim un guany de 10,48x respecte l'execució serial. Aquesta millora suposa un 27% respecte la planificació inter-workflow aplicada en el mateix workflow i les mateixes dades d’entrada. / Scientific workflows have become a framework of working arrangements, widely used for scientific data processing. This thesis presents several scheduling and resource management techniques for the execution of scientific workflows on hybrid computing environments. In recent years, the processors of the graphics cards (GPU) have become a programmable resource that has been introduced into computer systems as accelerators to run, in a low cost way, other tasks than graphics processing. One area where they have been introduced is the medical imaging field, because the high resolution and image size represent a high cost in terms of resources and computation time. This is the case of FreeSurfer, which is a set of tools which define Magnetic Resonance (MRIs) processing workflows. The introduction of some implementations on the GPU in stages the of the processing workflow from structural resonances from versions 5 and 5.3, has resulted in a major reduction of the execution time in one workflow instance (serial execution), representing about 60-70% based on the input resonance. When we run multiple instances of the FreeSurfer workflow in the same computing node we find that GPUs become a bottleneck for the saturation of the GPU memory. To overcome these limitations several techniques are introduced throughout this work for planning and management of shared resources, especially the GPU. We call the first proposal inter-workflow scheduling. It uses a list of restrictions that define the utilization rate of resources for each stage and is used to make planning decisions. This planning is applied in the management of data dependencies and resource access for the use case defined by the full FreeSurfer structural analysis workflow . In the execution of multiple instances, applying this planning achieves 6,79x speedup with respect to the serial execution. Moreover, in the second study, the use case is the FreeSurfer volumetric reconstruction workflow. The batch scheduling that we propose, introduce control mechanisms for combining the execution of tasks from different instances. It obtains a speedup of 10,48x versus the serial exeuction This represents a 27% improvement compared to the inter-worklfow planning applied in the same workflow and to the same input data.

Aquesta tesi s'ha desenvolupat entorn les repercussions i oportunitats creades per la digitalització, accessibilitat en línia al patrimoni cultural i la preservació digital, doncs el llenguatge hipermèdia i els nous fluxos de comunicació han atorgat una nova dimensió als sistemes de comunicació i documentació i a les estratègies i programes de gestió, preservació, estudi, difusió i accés als béns culturals. L'estudi de cas són les col•leccions europees d'instruments musicals en línia. Hem pogut determinar les tendències de futur en relació a finalitats i objectius de la documentació i digitalització del patrimoni cultural, en l'àmbit de la Unió Europea, amb l'anàlisi de llocs web de les col•leccions europees d'instruments musicals en línia i amb l'anàlisi de les polítiques de digitalització. L'estudi de cas ens ha permès aportar una visió innovadora i multidisciplinària, de confluència entre els drets culturals, les Ciències de la Documentació i les metodologies i conceptes de la Museologia. Amb aquesta tesi defensem que l'accessibilitat d'estructures del coneixement, com les col•leccions en línia, és una de les garanties per a l'autonomia de les persones i el progrés de les societats. / This thesis has been developed around the impacts and opportunities created from the digitisation and online accessibility of cultural heritage and digital preservation, seeing how the language hypermedia and new communication flows have given a new dimension to communication systems and documentation strategies as well as programs management, preservation, study, dissemination and access to cultural heritage. The case study is the european online musical instruments collections. We have been able to determine future trends regarding aims and objectives of the documentation and digitisation of cultural heritage in the European Union, with the analysis of the wesites of the european online musical instruments collections and the analysis of the digitisation policies. The case study has allowed us to provided an innovative and multidisciplinary vision of convergence between the cultural rights, Information and Communication Sciences and Museology methodologies and concepts. This thesis is to defend the accessibility of knowledge structures, such as collective Collections Online, which is one of the guarantees for the independence of the people and the progress of societies.

Les xarxes socials en línia (en anglès, Online Social Networks o OSNs) són avui en dia un dels serveis més populars a Internet. En el moment d’escriure aquestes línies, quatre de les deu primeres pàgines del rànquing global Alexa corresponien a xarxes socials i les xarxes més utilitzades tenien centenars de milions d’usuaris actius cada dia. Les persones fem servir xarxes socials per compartir tot tipus de continguts: des d’atributs personals (com noms, edat o sexe), a ubicacions, fotos o comentaris. D’altra banda, les xarxes socials es caracteritzen per permetre que els usuaris puguin crear relacions de manera explícita (per exemple, relacions d’amistat). A més, les xarxes socials inclouen no només la informació que els usuaris publiquen conscientment sobre si mateixos, sinó també la informació que es genera a partir de la interacció dels usuaris de la plataforma. Tant el nombre d’usuaris com el volum de dades compartides fan que la privacitat en xarxes socials sigui crítica. Aquesta tesi se centra en l’estudi de la privacitat en xarxes socials en dos contextos diferents: l’adquisició de dades de manera automatitzada (crawling) i l’aprenentatge. En primer lloc, s’estudia la relació entre crawling i privacitat, un tema que fins al moment ha rebut una atenció limitada. Aquest escenari és interessant ja que és assequible fins i tot per a un atacant de baix pressupost. En segon lloc, s’estudia com extreure informació de les relacions que formen els usuaris de xarxes socials. Les tècniques desenvolupades s’estenen després al tractament d’altres problemes que, com les xarxes socials, es poden modelar en forma de grafs. / Online Social Networks (OSNs) are now one of the most popular services on the Internet. When these lines were written, there were four OSN sites in the Alexa's top ten global ranking and the most used OSNs were having hundreds of millions of daily active users. People use OSNs to share all kinds of contents: from personal attributes (like names, age, or gender), to location data, photos, or comments. Moreover, OSNs are characterized by allowing its users to explictly form relationships (e.g. friendship). Additionally, OSNs include not only information the users conscientiously post about themselves, but also information that is generated from the interaction of users in the platform. Both the number of users and the volume of data shared make privacy in OSNs critical. This thesis is focused on studying privacy related to OSNs in two different contexts: crawling and learning. First, we study the relation between OSN crawling and privacy, a topic that so far received limited attention. We find this scenario interesting because it is affordable for even a low-budget attacker. Second, we study how to extract information from the relationships OSN users form. We then expand our findings to other graph-modeled problems.

Los dispositivos FPGA persisten como componentes fundamentales para el diseño y evaluación de sistemas electrónicos. En el caso de las FPGAs basadas en memoria SRAM de Xilinx, éstas soportan Reconfigurabilidad Parcial Dinámica (DPR) por medio del Internal Configuration Access Port (ICAP). Este componente físico permite acceder a la memoria de configuración mientras el sistema está operando y por lo tanto la DPR puede ser usada para modificar partes específicas del sistema mientras que el resto sigue funcionando sin ser afectado. La arquitectura del sistema pude ser modificada a nivel de componentes lógicos básicos como Look-Up-Tables (LUTs), o a nivel de bloques más grandes como IPs con lo cual la flexibilidad de los sistemas puede mejorar. Ésta es una gran ventaja especialmente en sistemas críticos, como los aeroespaciales, donde el acceso al sistema para modificar su hardware no es una tarea sencilla. Pero el principal problema que estas FPGAs presentan cuando son utilizadas para aplicaciones críticas es su susceptibilidad a Single Event Upset (SEU) y Multi-bit Upset (MBU) en la memoria de configuración. Éste es un factor limitante que debe ser considerado para evitar malfuncionamiento del hardware implementado. Esta tesis está enfocada en usar DPR como un mecanismo para: i) mejorar la flexibilidad del hardware, ii) emular fallos de forma precisa en diseños ASIC mapeados en FPGAs y iii) mejorar la tolerancia a fallos acumulados o múltiples en la memoria de configuración de circuitos con Triple Redundancia Modular (TMR). Este trabajo aborda estos aspectos considerando como figura de mérito fundamental la velocidad de ejecución de las tareas. Por lo tanto uno de los principales objetivos es acelerar las tareas relacionadas con DPR. En primer lugar un controlador hardware para el ICAP fue diseñado: AC_ICAP. Éste además de soportar lectura y escritura de frames, manejo de bitstreams parciales desde memoria flash y memoria interna de la FPGA, también permite DPR de alta velocidad a nivel de LUTs sin necesidad de bitstreams parciales previamente generados. Esta última característica es posible gracias a ingeniería inversa en el bitstream con la cual se puede ejecutar DPR de LUTs individuales en menos de 5 μs. Ésto representa una mejora en tiempo de reconfiguración de más de 380 veces comparado con el controlador XPS_HWICAP de Xilinx En segundo lugar, la DPR a nivel de LUTs es utilizada en la emulación de fallos para evaluar circuitos ASIC mapeados en FPGAs. Para ello se diseña un CAD que incluye un traductor de la descripción ASIC a una descripción basada en LUTs para ser implementada en FPGAs, generación de diccionarios de fallos y extracción de patrones de prueba. Una plataforma hardware usa el listado de fallos y aprovecha la DPR de la FPGA para la inyección precisa de fallos seguida de la aplicación de los patrones de test para analizar los efectos de los fallos en el circuito. Finalmente la DPR es utilizada para mejorar la tolerancia a fallos de circuitos TMR implementados en FPGAs basados en memoria SRAM. En estos dispositivos la acumulación de fallos en la memoria de configuración puede generar fallos en las réplicas TMR. Por lo tanto la rápida detección y corrección de fallos sin detener el sistema es un requerimiento que se debe cumplir cuando se usan estas FPGAs en la implementación de sistemas críticos. Para ello se insertan detectores de errores de tipo XNOR que convergen en componentes carry-chain de la FPGA y además cada dominio es aislado en áreas diferentes del dispositivo para los cuales se extraen bitstreams parciales. Éstos son utilizados para corregir los fallos cuando los detectores son activados. / Field Programmable Gate Array (FPGA) devices persist as fundamental components in the design and evaluation of electronic systems. They are continuously reported as final implementation platforms rather than only prototype elements. The inherent reconfigurable characteristics that FPGAs offer are one of the most important advantages in the actual hardware implementation and redesign of systems. In the case of Xilinx SRAM-based FPGAs they support Dynamic Partial Reconfiguration (DPR) by means of the Internal Configuration Access Port (ICAP). This hardwired element allows the configuration memory to be accessed at run time. DPR can then be used to change specific parts of the system while the rest continues to operate with no affection in its computations. Therefore the architecture of the system can be modified at the level of basic logic components such as Look-Up-Tables (LUTs), or bigger blocks such as IP cores, and in this way more flexible systems can be designed. It is a great advantage especially in critical and aerospace applications where the access to the system to re-design the hardware is not a trivial task. But on the other hand, the main problem these FPGAs present when used for critical applications is their sensitivity to Single Event Upset (SEU) and Multi-bit Upset (MBU) in the configuration memory. It is a limiting factor that must be considered to avoid misbehavior of the implemented hardware. This thesis is focused on using DPR as a mechanism to: i) improve hardware flexibility, ii) emulate faults on ASIC designs mapped in FPGAs and iii) improve tolerance to accumulated or multiple faults in the configuration memory of Triple Modular Redundancy (TMR) circuits. This work addresses the three challenges considering as one of the most relevant figures of merit the speed at which the tasks can be performed. It is therefore one of the main objectives we consider: the speed-up of DPR related tasks. In the first place we developed a new high speed ICAP controller, named AC_ICAP, completely implemented in hardware. In addition to similar solutions to accelerate the management of partial bitstreams and frames, AC_ICAP also supports DPR of LUTs without requiring pre-computed partial bitstreams. This last characteristic was possible by performing reverse engineering on the bitstream. This allows DPR of single LUTs in Virtex-5 devices to be performed in less than 5 μs which implies a speed-up of more than 380x compared to the Xilinx XPS_HWICAP controller. In the second place, the fine grain DPR obtained with the utilization of the AC_ICAP is used in the emulation of faults to test ASIC circuits implemented in FPGAs. It is achieved by designing a CAD flow that includes a custom technology mapping of the ASIC net-list to LUT-level FPGA net-list, the creation of fault dictionaries and the extraction of test patterns. A hardware platform takes the fault list and leverages the partial reconfiguration capabilities of the FPGA for fault injection followed by application of test patterns for fault analysis purposes. Finally, we use DPR to improve the fault tolerance of TMR circuits implemented in SRAM-based FPGAs. In these devices the accumulation of faults in the configuration memory can cause the TMR replicas to fail. Therefore fast detection and correction of faults without stopping the system is a required constraint when these FPGAs in the implementation of critical systems. This is carried out by inserting flag error detector based on XNOR and carry-chain components, isolating and constraining the three domains to known areas and extracting partial bitstreams for each domain. The latter are used to correct faults when the flags are activated.

Hoy en día, muchos problemas del mundo real son codificados en instancias SAT y resueltos eficientemente por modernos SAT solvers. Estos solvers, usualmente conocidos como Conflict-Driven Clause Learning (CDCL: Aprendizaje de cláusulas guiado por conflictos) SAT solvers, incluyen una variedad de sofisticadas técnicas, como el aprendizaje de cláusulas, estructuras de datos perezosas, heurísticas de ramificación adaptativas basadas en los conflictos, o reinicios aleatorios, entre otros. Sin embargo, las razones de su eficiencia resolviendo problemas SAT del mundo real, o industriales, son todavía desconocidas. La creencia común en la comunidad SAT es que estas técnicas explotan alguna estructura oculta de los problemas del mundo real. En esta tesis, primeramente se caracteriza algunas importantes características de la estructura subyacente de las instancias SAT industriales. Específicamente, estas son la estructura de comunidades y la estructura auto-similar. Se observa que la mayoría de las fórmulas SAT industriales, vistas como grafos, tienen estas dos propiedades. Esto significa que (i) en un grafo con una estructura de comunidades clara; es decir, alta modularidad, se puede encontrar una partición de sus nodos en comunidades de tal forma que la mayoría de las aristas conectan nodos de la misma comunidad; y (ii) en un grafo con el patrón de auto-similitud; es decir, siendo fractal, su forma se mantiene después de re-escalados (agrupando conjuntos de nodos en uno). Se analiza también cómo estas estructuras están afectadas por los efectos de las técnicas CDCL durante la búsqueda. Usando los estudios estructurales previos, se proponen tres aplicaciones. Primero, se aborda el problema de la generación aleatoria de instancias SAT pseudo-industriales usando la noción de modularidad. Nuestro modelo genera instancias similares a las (clásicas) fórmulas SAT aleatorias cuando la modularidad es baja, pero cuando este valor es alto, nuestro modelo también es adecuado para modelar problemas pseudo-industriales realísticamente. Segundo, se propone un método basado en la estructura en comunidades de la instancia para detectar cláusulas aprendidas relevantes. Nuestra técnica aumenta la instancia original con un conjunto de cláusulas relevantes, y esto resulta en una mejora general de la eficiencia de varios CDCL SAT solvers. Finalmente, se analiza la clasificación de instancias SAT industrial en familias usando las características estructurales previamente analizadas, y se comparan con otros clasificadores comúnmente usados en aproximaciones SAT portfolio. En resumen, esta disertación extiende nuestro conocimiento sobre la estructura de las instancias SAT, con el objetivo de explicar mejor el éxito de las técnicas CDCL, con la posibilidad de mejorarlas; y propone una serie de aplicaciones basadas en este análisis de la estructura subyacente de las fórmulas SAT. / Nowadays, many real-world problems are encoded into SAT instances and efficiently solved by modern SAT solvers. These solvers, usually known as Conflict-Driven Clause Learning (CDCL) SAT solvers, include a variety of sophisticated techniques, such as clause learning, lazy data structures, conflict-based adaptive branching heuristics, or random restarts, among others. However, the reasons of their efficiency in solving real-world, or industrial, SAT instances are still unknown. The common wisdom in the SAT community is that these technique exploit some hidden structure of real-world problems. In this thesis, we characterize some important features of the underlying structure of industrial SAT instances. Namely, they are the community structure and the self-similar structure. We observe that most industrial SAT formulas, viewed as graphs, have these two properties. This means that~(i) in a graph with a clear community structure, i.e. having high modularity, we can find a partition of its nodes into communities such that most edges connect nodes of the same community; and~(ii) in a graph with a self-similar pattern, i.e. being fractal, its shape is kept after re-scalings, i.e., grouping sets of nodes into a single node. We also analyze how these structures are affected by the effects of CDCL techniques during the search. Using the previous structural studies, we propose three applications. First, we face the problem of generating pseudo-industrial random SAT instances using the notion of modularity. Our model generates instances similar to (classical) random SAT formulas when the modularity is low, but when this value is high, our model is also adequate to model realistic pseudo-industrial problems. Second, we propose a method based on the community structure of the instance to detect relevant learnt clauses. Our technique augments the original instance with this set of relevant clauses, and this results into an overall improvement of the efficiency of several state-of-the-art CDCL SAT solvers. Finally, we analyze the classification of industrial SAT instances into families using the previously analyzed structure features, and we compare them to other classifiers commonly used in portfolio SAT approaches. In summary, this \dissertation extends the understandings of the structure of SAT instances, with the aim of better explaining the success of CDCL techniques and possibly improve them, and propose a number of applications based on this analysis of the underlying structure of SAT formulas.

En aquesta tesi s'aborda el problema de la comprensió de text automàtic en condicions sense restriccions. En particular, abordem les tasques de detecció, el seguiment, i el reconeixement de text multi-idioma amb orientació arbitrària en imatges i vídeos d'escena natural. Per a això s'ha desenvolupat un conjunt de mètodes genèrics que es basen de la premissa bàsica que el text té sempre algunes característiques claus visuals que són independents de la llengua o escriptura en el qual està escrit. Les metodologies d'extracció de text en escena es basen generalment en la classificació de regions o regions individuals, utilitzant el coneixement a priori d'un script o llenguatge determinat. La percepció humana de text, per contra, es basa en l'organització perceptiva a través del qual el text apareix com un grup perceptualment rellevant d'objectes atòmics. En aquesta tesi, s'argumenta que el problema de l'extracció de text pot ser plantejat com a detecció de grups significatius de regions de la imatge. Ens ocupem del problema de la segmentació del text en escenes naturals des d'una perspectiva jeràrquica, fent ús explícit de l'estructura del text, enfocant directament la detecció d'agrupacions de regions que corresponen a elements de text dins d'una jerarquia produïda per un procés d'aglomeració per similitud sobre les regions individuals. Proposem una manera òptima per construir aquesta jerarquia de manera que s'estableix un espai de característiques dissenyat per produir hipòtesis de grup de text, i una regla de detenció que combina un classificador discriminatiu i una mesura probabilística de rellevancia dels grups amb base en l'organització perceptiva. Proposem un nou algoritme de propostes d'objecte que està dissenyat específicament per a detectar text, i el comparem amb altres mètodes genèrics en l'estat de la tècnica. Alhora, s'estudia en quina mesura els mètodes existents de propostes d'objectes genèrics poden ser útils per a la detecció de text d'escena. A continuació, presentem un algoritme híbrid per a la detecció i seguiment de text d'escena en el qual la noció de groups de regions també juga paper central. Un mòdul d'extracció de text escena basada en MSER ​​s'utilitza per detectar el text de forma asíncrona, mentre que paral·lelament els objectes de text detectates són seguits per propagació de MSER. La cooperació d'aquests dos mòduls va més enllà del seguiment per detecció en termes d'optimització de temps, i pot oferir processament de vídeo en temps real fins i tot en dispositius de baixos recursos. Finalment, ens centrem en el problema de la identificació de l'escriptura en imatges de text d'escena per tal de construir un sistema de lectura d'extrem a extrem en escenris multi-idioma. Afrontar aquest problema amb classificadors CNN no és una tasca senzilla, ja que aquests no tenen en compte una característica clau de les instàncies de text d'escena: la seva relació d'aspecte es extremadament variable. En lloc de canviar la mida d'imatges d'entrada a una mida fixa, com en l'ús típic dels classificadors CNN holístics, proposem un marc de classificació basat en caracteristiques locals amb la finalitat de preservar les parts discriminatives de la imatge que són característiques de la seva classe. Es descriu un nou mètode basat en l'ús de conjunts de xarxes unides per aprendre conjuntament representacions discriminatives de regions locals de la imatge i alhora la seva importància relativa en un esquema de classificació global. Els nostres experiments amb aquest procediment d'aprenentatge demostren la viabilitat d'identificació d'alfabet en imatges d'escena natural, aplanant el camí cap als sistemes de comprensió de text d'escena d'extrem a extrem en diversos idiomes. / En esta tesis se aborda el problema de la comprensión de texto automático en condiciones sin restricciones. En particular, abordamos las tareas de detección, seguimiento, y el reconocimiento de texto multi-idioma con orientación arbitraria en imágenes y vídeos de escena natural. Para ello se ha desarrollado un conjunto de métodos genéricos que se basan de la premisa básica de que el texto tiene siempre algunas características claves visuales que son independientes de la lengua o escritura en el que está escrito. Las metodologías de extracción de texto en escena se basan generalmente en la clasificación de regiones o regiones individuales, utilizando el conocimiento a priori de un script o lenguaje determinado. La percepción humana de texto, por el contrario, se basa en la organización perceptiva a través del cual el texto aparece como un grupo perceptualmente relevante de objetos atómicos. En esta tesis, se argumenta que el problema de la extracción de texto puede ser planteado como detección grupos significativos de regiones de la imagen. Nos ocupamos del problema de la segmentación del texto en escenas naturales desde una perspectiva jerárquica, haciendo uso explícito de la estructura del texto, enfocando directamente la detección de agrupaciones de regiones que corresponden a elementos de texto dentro de una jerarquía producida por un proceso de aglomeración por similitud sobre las regiones individuales. Proponemos una manera óptima para construir esta jerarquía de modo que se establece un espacio de características diseñado para producir hipótesis de grupo de texto, y una regla de detención que combina un clasificador discriminativo y una medida probabilística de relevancia de los grupos con base en el organización perceptiva. Proponemos un nuevo algoritmo de propuestas de objeto que está diseñado específicamente para detectar texto, y lo comparamos con otros métodos genéricos en el estado de la técnica. Asimismo, se estudia en qué medida los métodos existentes de propuestas de objetos genéricos pueden ser útiles para la detección de texto de escena. A continuación, presentamos un algoritmo híbrido para la detección y seguimiento de texto de escena en el que la noción de groups de regiones también juega papel central. Un módulo de extracción de texto escena basada en MSER utiliza para detectar el texto de forma asíncrona, mientras que paralelamente los objetos de texto detectados son seguidos por propagación de MSER. La cooperación de estos dos módulos va más allá del seguimiento para detección en términos de optimización de tiempo, y puede ofrecer procesamiento de vídeo en tiempo real incluso en dispositivos de bajos recursos. Finalmente, nos centramos en el problema de la identificación de la escritura en imágenes de texto de escena para construir un sistema de lectura de extremo a extremo en escenris multi-idioma. Afrontar este problema con clasificadores CNN no es una tarea sencilla, ya que estos no tienen en cuenta una característica clave de las instancias de texto de escena: su relación de aspecto es extremadamente variable. En lugar de cambiar el tamaño de imágenes de entrada a un tamaño fijo, como en el uso típico de los clasificadores CNN holísticos, proponemos un marco de clasificación basado en características locales con el fin de preservar las partes discriminativas de la imagen que son características de su clase. Se describe un nuevo método basado en el uso de conjuntos de redes unidas para aprender conjuntamente representaciones discriminativas de regiones locales de la imagen y al mismo tiempo su importancia relativa en un esquema de clasificación global. Nuestros experimentos con este procedimiento de aprendizaje demuestran la viabilidad de identificación de alfabeto en imágenes de escena natural, allanando el camino hacia los sistemas de comprensión de texto de escena de extremo a extremo en varios idiomas. / This thesis addresses the problem of automatic scene text understanding in unconstrained conditions. In particular, we tackle the tasks of multi-language and arbitrary-oriented text detection, tracking, and recognition in natural scene images and videos. For this we have developed a set of generic methods that build on top of the basic assumption that text has always some visual key characteristics that are independent of the language or script in which it is written. Scene text extraction methodologies are usually based in classification of individual regions or patches, using a priori knowledge for a given script or language. Human perception of text, on the other hand, is based on perceptual organisation through which text emerges as a perceptually significant group of atomic objects. In this thesis, we argue that the text extraction problem could be posed as the detection of meaningful groups of regions. We address the problem of text segmentation in natural scenes from a hierarchical perspective, making explicit use of text structure, aiming directly to the detection of region groupings corresponding to text within a hierarchy produced by an agglomerative similarity clustering process over individual regions. We propose an optimal way to construct such an hierarchy introducing a feature space designed to produce text group hypotheses with high recall and a novel stopping rule combining a discriminative classifier and a probabilistic measure of group meaningfulness based in perceptual organization. We propose a new Object Proposals algorithm that is specifically designed for text and compare it with other generic methods in the state of the art. At the same time we study to what extent the existing generic Object Proposals methods may be useful for scene text understanding. Then, we present a hybrid algorithm for detection and tracking of scene text where the notion of region grouppings plays also central role. A scene text extraction module based on Maximally Stable Extremal Regions (MSER) is used to detect text asynchronously, while in parallel detected text objects are tracked by MSER propagation. The cooperation of these two modules goes beyond the full-detection approaches in terms of time performance optimization, and yields real-time video processing at high frame rates even on low-resource devices. Finally, we focus on the problem of script identification in scene text images in order to build a multi-language end-to-end reading system. Facing this problem with state of the art CNN classifiers is not straightforward, as they fail to address a key characteristic of scene text instances: their extremely variable aspect ratio. Instead of resizing input images to a fixed size as in the typical use of holistic CNN classifiers, we propose a patch-based classification framework in order to preserve discriminative parts of the image that are characteristic of its class. We describe a novel method based on the use of ensembles of conjoined networks to jointly learn discriminative stroke-parts representations and their relative importance in a patch-based classification scheme. Our experiments with this learning procedure demonstrate the viability of script identification in natural scene images, paving the road towards true multi-lingual end-to-end scene text understanding.

Volume visualization is a method of extracting information from volumetric data using interactive graphics. Volume visualization aims to assist visual interpretation of data by creating three-dimensional models that reproduce real objects with sufficient detail and speed to support interactive manipulation. Illustrative rendering enhances the perception of features in a volume. Volume rendering has two major goals: to obtain high quality images in real time, and to determine how to explore volume datasets in an effective way. In this thesis we advance in these two lines. We propose several methods to approximate global illumination with low computational cost, permitting realistic and illustrative rendering. We also present a method to automatically define transfer functions given a target distribution. In addition, we introduce a method to automatize the creation of exploded views. Finally, we explore techniques to select the best viewpoints for a volume. Several of our contributions are based on information theory. / La visualització de volums és un mètode per extreure informació de dades volumètriques mitjançant imatges interactives. L’objectiu és assistir la interpretació visual de dades creant models tridimensionals que reprodueixen objectes reals amb suficient detall i velocitat per permetre’n la manipulació interactivament. La visualització il·lustrativa millora la percepció de les característiques d'un volum. La visualització de volums té dos objectius principals: obtenir imatges d’alta qualitat en temps real, i determinar com explorar volums d'una manera efectiva. En aquesta tesi avancem en aquestes dues línies. Proposem diversos mètodes per aproximar la il·luminació global amb baix cost computacional, permetent la visualització realista i il·lustrativa. També presentem un mètode per definir automàticament funcions de transferència donada una distribució objectiu. A més, presentem un mètode per automatitzar la creació d’exploded views. Finalment, explorem tècniques per seleccionar els millors punts de vista d’un volum. Diverses de les contribucions estan basades en la teoria de la informació.

Actualmente se crean, almacenan, editan y distribuyen grandes cantidades de contenidos audiovisuales, en parte debido a la capacidad de almacenamiento prácticamente ilimitada, al acceso a los medios necesarios por todo el mundo y en cualquier parte, y a la ubicua conectividad proporcionada por Internet. En este contexto, se requiere una gestión adecuada y sostenible que permita la búsqueda y recuperación de la información de interés. Es aquí donde las técnicas de procesamiento del habla juegan un papel crucial en el etiquetado y anotación automáticos de contenidos audiovisuales. La diarización de locutores es un proceso de apoyo clave para otros sistemas de procesamiento del habla, tales como el reconocimiento automático del habla y el reconocimiento automático de locutores, frecuentemente usados para la extracción automática de metadatos de documentos hablados. Entre las distintas colecciones de contenidos, puede haber locutores recurrentes que participen en diferentes sesiones dentro de una colección determinada (por ejemplo, en contenidos de televisión y radio). Dada la naturaleza local de la tecnología de diarización de locutores, un locutor recurrente arbitrario probablemente recibirá identificadores locales diferentes entre las distintas sesiones donde tal locutor participa. En esta situación tendría más sentido que los locutores recurrentes recibieran el mismo identificador abstracto, global para todas las sesiones. Esta tarea se conoce como diarización de locutores inter-sesión. La diarización de locutores actual ha conseguido muy buena precisión, pero normalmente al coste de largos tiempos de ejecución. Esta limitación podría no ser adecuada para aplicaciones de la vida real a gran escala, se hace aún más evidente el la tarea de diarización de locutores inter-sesión. En esta tesis, la aproximación a la diarización rápida de locutores basada en claves binarias se lleva a un siguiente nivel, con el objetivo de obtener rendimientos similares a los de los sistemas actuales punteros, mientras se preservan altas tasas de velocidad que permitan el tratamiento de grandes colecciones de audio en tiempos competitivos. Además, se propone un nuevo sistema de diarización de locutores inter-sesión basado en claves binarias que sigue los mismos principios previamente establecidos: precisión competitiva en tiempos de ejecución cortos. Como resultado de esta tesis, se propone un sistema mejorado de diarización que consigue una mejora relativa del 16% en rendimiento con respecto a un sistema base de claves binarias (15% DER frente a un 18.22% DER, siendo DER la tasa de error de diarización), siendo 7 veces más rápido (0.035xRT frente a 0.252xRT, siendo xRT el factor de tiempo real) y 28 veces más rápido que el tiempo real. En cuanto a la diarización inter-sesión, en esta tesis se propone un sistema binario cuya precisión es solo levemente inferior (3.5% DER absoluto) a la de su sistema homólogo para sesiones independientes, mientras que presenta factores de tiempo real alrededor de 0.036xRT. Además, la aproximación propuesta escala adecuadamente para tratar colecciones de audio de varios cientos de horas. / Today, massive amounts of audiovisual content are being generated, stored, released and delivered, in part due to the virtually unlimited storage capacity, the access to the necessary media to produce them by anybody and anywhere, and the ubiquitous connectivity provided by the Internet. In this context, suitable, affordable and sustainable content management which enables searching and retrieving information of interest is a must. Since manual handling of such amount of data is intractable, it is here where speech processing techniques may play a crucial role in the automatic tagging and annotation of audiovisual content. The task of speaker diarization (also known as the “who spoke when” task) has become a key process as a supporting technology for further speech processing systems, such as automatic speech recognition and automatic speaker recognition, used for the automatic extraction of metadata from spoken documents. Among the massive amount of audiovisual content being created, there can be recurrent speakers who participate in several sessions within a collection of audiovisual sessions. For instance, in TV and radio content one can frequently find recurrent speakers such as public figures, journalists, presenters, anchors, and so on. Due to the local nature of current speaker diarization technology (systems work on a single-session basis), an arbitrary recurrent speaker will likely receive different local abstract identifiers among the different sessions where he/she participates. In this situation, it would be more meaningful that the recurrent speakers receive the same global, abstract ID along all sessions. This task is known as cross-session speaker diarization. Current state-of-the-art speaker diarization systems have achieved very good performance, but usually at the cost of long processing times. This limitation on execution time makes current systems not suitable for large-scale, real-life applications, and becomes even more evident in the task of cross-session speaker diarization. In this thesis, the fast speaker diarization approach based on binary key speaker modeling is taken to a next level with the aim of bringing it closer to state-of-the-art performance while preserving high speed rates that enable the processing of large audio collections in competitive times. Furthermore, a new cross-session speaker diarization system based on binary key speaker modeling is proposed by following the same previously established goals: competitive performance with short execution times. As a result of this thesis, we propose a new improved single-session speaker diarization system which exhibits a 16% relative improvement in performance with regard to a baseline binary key system (15.15% DER opposed to 18.22% DER, being DER the diarization error rate), while being 7 times faster (0.035xRT against 0.252xRT, being xRT the real-time factor) and 28 times faster than real time. As for cross-session speaker diarization, in this thesis we propose a binary system whose performance is just slightly below (3.5% absolute DER) the performance of its single-session counterpart, while presenting a real-time factor of 0.036xRT. Furthermore, our approach has been shown to successfully scale for processing audio collection of several hundreds of hours.

Executar aplicacions paral·leles de pas de missatges sobre un elevat nombre de recursos de manera eficient no és una tasca trivial. A causa de la complexa interacció entre l'aplicació paral·lela i el sistema HPC, a mesura que s'augmenta el nombre de processos de l'aplicació, depenent del sistema, pot arribar un punt on l'aplicació presenti el seu límit d'escalabilitat, moment a partir del qual es començaran a produir ineficiències en el sistema, comportant a un ús ineficient del mateix. Aquest problema es torna especialment crític en aplicacions paral·leles les quals han de ser executades freqüentment, utilitzant un elevat nombre de recursos sobre un llarg període de temps Per tal d'intentar solucionar aquests problemes i fer un ús eficient del sistema, com a principal contribució d'aquesta tesi, es proposa la metodologia P3S (Prediction of Parallel Program Scalability), la qual permet predir el rendiment de l'escalabilitat forta d'aplicacions paral·leles de pas de missatges en un determinat sistema, utilitzant un temps d'anàlisi limitat i un conjunt reduït de recursos del sistema. La metodologia P3S, es basa en analitzar el comportament repetitiu de les aplicacions paral·leles de pas de missatges. Aquest tipus d'aplicacions estan compostes per un conjunt de fases identificables, les quals es van repetint al llarg de tota l'aplicació, independentment del nombre de processos de l'aplicació. La metodologia consta de tres etapes. Una primera etapa de caracterització, on es caracteritzen les fases rellevants de l'aplicació paral·lela, a partir de la informació obtinguda de l'execució d'un conjunt de signatures de l'aplicació, per a un nombre reduït de processos. Una segona etapa de modelització de l'aplicació, on es genera el model lògic d'escalabilitat de cada fase rellevant de l'aplicació paral·lela, mitjançant el qual construir la traça lògica escalable de l'aplicació. Aquesta traça permetrà predir el comportament lògic de l'aplicació, a mesura que s'augmenta el seu nombre de processos. Finalment, l'última etapa de la metodologia consisteix en predir el rendiment de l'aplicació per a un nombre específic de processos. Per a això, la traça lògica escalable serà precisada per al nombre de processos per al qual es vol predir el rendiment de l'aplicació, amb l'objectiu de predir el temps de còmput i comunicació de cada fase rellevant de l'aplicació, per aquest nombre de processos , amb la finalitat d'obtenir el temps predit de l'aplicació. Gràcies a la corba d'escalabilitat de l'aplicació, proporcionada per la metodologia P3S, els usuaris poden seleccionar els recursos més adients per executar la seva aplicació al sistema destí, el que permet tenir la seguretat d'utilitzar els recursos del sistema de manera eficient. / Ejecutar aplicaciones paralelas de paso de mensajes sobre un elevado número de recursos de forma eficiente no es una tarea trivial. Debido a la compleja interacción entre la aplicación paralela y el sistema HPC, a medida que se aumenta el número de procesos de la aplicación, dependiendo del sistema, puede llegar un punto donde la aplicación presente su límite de escalabilidad, momento a partir del cual se empezarán a producir ineficiencias en el sistema, conllevando a un uso ineficiente del mismo. Este problema se vuelve especialmente crítico en aplicaciones paralelas las cuales tienen que ser ejecutadas frecuentemente, utilizando un elevado número de recursos sobre un largo período de tiempo Con el fin de intentar solventar estos problemas y hacer un uso eficiente del sistema, como principal contribución de esta tesis, se propone la metodología P3S (Prediction of Parallel Program Scalability), la cual permite predecir el rendimiento de la escalabilidad fuerte de aplicaciones paralelas de paso de mensajes en un determinado sistema, utilizando un tiempo de análisis limitado y un conjunto reducido de recursos del sistema. La metodología P3S, se basa en analizar el comportamiento repetitivo de las aplicaciones paralelas de paso de mensajes. Este tipo de aplicaciones están compuestas por un conjunto de fases identificables, las cuales se van repitiendo a lo largo de toda la aplicación, independientemente del número de procesos de la aplicación. La metodología consta de tres etapas. Una primera etapa de caracterización, donde se caracterizan las fases relevantes de la aplicación paralela, a partir de la información obtenida de la ejecución de un conjunto de firmas de la aplicación, para un número reducido de procesos. Una segunda etapa de modelización de la aplicación, donde se genera el modelo lógico de escalabilidad de cada fase relevante de la aplicación paralela, mediante el cual construir la traza lógica escalable de la aplicación. Esta traza permitirá predecir el comportamiento lógico de la aplicación, a medida que se aumenta su número de procesos. Finalmente, la última etapa de la metodología consiste en predecir el rendimiento de la aplicación para un número específico de procesos. Para ello, la traza lógica escalable será precisada para el número de procesos para el cual se desea predecir el rendimiento de la aplicación, con el objetivo de predecir el tiempo de cómputo y comunicación de cada fase relevante de la aplicación, para ese número de procesos, con la finalidad de obtener el tiempo predicho de la aplicación. Gracias a la curva de escalabilidad de la aplicación, proporcionada por la metodología P3S, los usuarios pueden seleccionar los recursos más adecuados para ejecutar su aplicación en el sistema objetivo, lo que permite tener la seguridad de utilizar los recursos del sistema de forma eficiente. / Executing message-­‐passing applications using an elevated number of resources is not a trivial task. Due to the complex interaction between the message-­‐passing applications and the HPC system, depending on the system, many applications may suffer performance inefficiencies, when they scale to a large number of processes. This problem is particularly serious when the application is executed many times over a long period of time. With the purpose of avoiding these problems and making an efficient use of the system, as main contribution of this thesis, we propose the methodology P3S (Prediction of Parallel Program Scalability), which allows us to analyze and predict the strong scalability behavior for message-­‐passing applications on a given system. The methodology strives to use a bounded analysis time, and a reduced set of resources to predict the application performance. The P3S methodology is based on analyzing the repetitive behavior of parallel message-­‐passing applications. Such applications are composed of a set of phases, which are repeated through the whole application, independently of the number of application processes. The methodology is made up of three stages. A first characterization step, where the relevant phases of the parallel application are characterized, from the execution of a set of small-­‐scale application signatures. A second stage of modeling of the application, where the application logical scalability model is generated for each relevant application phase, whereby to construct the scalable logical trace of the application. This trace will be used to predict the logical behavior of the application, as the number of the application processes increases. Finally, the last stage of the methodology consist of predicting the application performance for a specific number of processes. In order to do that, the scalable logical trace will be specified for the number of processes to predict the application performance, with the objective to predict the computational and communication time of each relevant phase for this number of processes, in order to obtain the performance prediction. The output of the P3S methodology will be the predicted curve of application speedup. Using this information, the users can select the most appropriate resources to execute his application on the target system, in order to use the system resources efficiently.