L'objectiu bàsic del present treball és, el de, partint de l'estudi de Martínez-Quintanilla, plantejar un sistema informatitzat per al traçat de la perspectiva curvilínia de pantalla cilíndrica, capaç de poder representar, amb una qualitat gràfica raonablement alta, conjunts arquitectònics o urbanístics d'una certa complexitat, és a dir, de bon principi quedà clar que, perquè el treball reixís en els seus objectius, calia que el sistema permetés la consecució de dibuixos en perspectiva de pantalla cilíndrica, representats sobre paper amb eliminació de línies ocultes i amb el grau de complexitat normalment exigible per a un tipus de perspectiva panoràmica com aquesta. El treball s'estructura en cinc capítols: En el Primer Capítol s'exposen els conceptes generals de la perspectiva curvilínia de pantalla cilíndrica i, seguint l'estudi de Martínez-Quintanilla, es fa una breu repassada als seus antecedents històrics, acabant per una exposició dels trets bàsics del sistema manual proposat per Martínez-Quintanilla.El Capítol 2 analitza els grans temes que cal afrontar per tal de plantejar el tractament informàtic de la perspectiva de pantalla cilíndrica. Un repàs a les alternatives possibles permet prendre un seguit d'opcions que configuren ja l'esquelet de l'aproximació que farem al tema. El Capítol acaba amb una descripció detallada de l'estructura d'informació que s'adopta per al plantejament informàtic del problema, punt -no cal dir-ho- d'importància cabdal per al seguiment de la resta del treball.El Capítol 3 s'ocupa de la descripció del sistema desenvolupat per a la creació dels models a representar, i hi són estudiades un gran nombre de situacions compromeses, exposant-se algorismes apropiats per a la seva resolució. El Capítol 4 estudia la visualització dels models mitjançant perspectiva curvilínia de pantalla cilíndrica. En concret s'hi estudia l'obtenció i representació interna de la projecció, i l'eliminació de línies ocultes per a traçat vectorial, considerant les característiques específiques d'una perspectiva en què la major part de les rectes apareixen com a corbes i en la qual desapareix el concepte de pla d'esvaïment.Per últim, en el Capítol 5 s'exposen un seguit de consideracions i optimitzacions deduïdes de les primeres experiències d'utilització dels Sistemes, experiències encara un tant restringides, ateses les limitacions de l'equip utilitzat, però que permeten extreure conclusions certament importants, de cara a la programació d'una segona versió dels Sistemes, ja sobre els nous equips de l'E.T.S.A.Vallès.

Con la llegada de una amplia variedad de arquitecturas multicore (NUMA, UMA), seleccionar la mejor configuración del nodo de cómputo para una cierta aplicación paralela de memoria compartida, se convierte en la actualidad en un gran reto. Nuestro trabajo hace frente a este tema caracterizando los nodos de cómputo y las aplicaciones. Los nodos se caracterizan ejecutando pequeños programas (o microbenchmarks, μB), que contienen núcleos de estructuras representativas del comportamiento de programas paralelos de memoria compartida. Los μBs ejecutados en cada uno de los nodos nos proporcionan perfiles de rendimiento, o datos medidos del comportamiento, que se almacenan en una base de datos y se utilizan para estimar el comportamiento de nuevas aplicaciones. La aplicación es ejecutada sobre un nodo base para identificar sus fases representativas. Para cada fase se extrae información de rendimiento comparable con la de los μBs, con el fin de caracterizar dicha fase. En la base de datos de los perfiles de rendimiento se localizan aquellos μBs que tienen características similares en comportamiento a cada fase de la aplicación, ejecutados todos sobre el nodo base. Finalmente, se usan los perfiles seleccionados, pero ejecutados sobre los otros nodos candidatos, para comparar el rendimiento de los nodos de cómputo y seleccionar el nodo de cómputo apropiado para la aplicación. / With the advent of multicore architectures, there arises a need for comparative evaluations of the performance of well-understood parallel programs. It is necessary to gain an insight into the potential advantages of the available computing node configurations in order to select the appropriate computing node for a particular shared-memory parallel application. This paper presents a methodology to resolve this issue, by constructing a database with behavior information for various representative shared-memory programming structures, and then estimating the application behavior as a combination of these data. These structures are represented by small specific chunks of code called microbenchmarks (μB) based on the study of memory access patterns of shared-memory parallel applications. μBs set is run on each candidate node, and all execution performance profiles are stored in a database for future comparisons. Then, applications are executed on a base node to identify different execution phases and their weights, and to collect performance and functional data for each phase. Information to compare behavior is always obtained on the same node (Base Node (BN)). The best matching performance profile (from performance profile database) for each phase, is then searched. Finally, the candidates nodes performance profiles identify in the match process are used to project performance behavior in order to select the appropriate node for running the application. Resource centers own different machine configurations. This methodology helps the users or systems administrator of data centers to schedule the jobs efficiently.

Traditionally, parallel computing has been associated with special purpose applications designed to run in complex computing clusters, specifically set up with a software stack of dedicated libraries together with advanced administration tools to manage co Traditionally, parallel computing has been associated with special purpose applications designed to run in complex computing clusters, specifically set up with a software stack of dedicated libraries together with advanced administration tools to manage complex IT infrastructures. These High Performance Computing (HPC) solutions, although being the most efficient solutions in terms of performance and scalability, impose technical and practical barriers for most common scientists whom, with reduced IT knowledge, time and resources, are unable to embrace classical HPC solutions without considerable efforts. Moreover, two important technology advances are increasing the need for parallel computing. For example in the bioinformatics field, and similarly in other experimental science disciplines, new high throughput screening devices are generating huge amounts of data within very short time which requires their analysis in equally short time periods to avoid delaying experimental analysis. Another important technological change involves the design of new processor chips. To increase raw performance the current strategy is to increase the number of processing units per chip, so to make use of the new processing capacities parallel applications are required. In both cases we find users that may need to update their current sequential applications and computing resources to achieve the increased processing capacities required for their particular needs. Since parallel computing is becoming a natural option for obtaining increased performance and it is required by new computer systems, solutions adapted for the mainstream should be developed for a seamless adoption. In order to enable the adoption of parallel computing, new methods and technologies are required to remove or mitigate the current barriers and obstacles that prevent many users from evolving their sequential running environments. A particular scenario that specially suffers from these problems and that is considered as a practical case in this work consists of bioinformaticians analyzing molecular data with methods written with the R language. In many cases, with long datasets, they have to wait for days and weeks for their data to be processed or perform the cumbersome task of manually splitting their data, look for available computers to run these subsets and collect back the previously scattered results. Most of these applications written in R are based on parallel loops. A loop is called a parallel loop if there is no data dependency among all its iterations, and therefore any iteration can be processed in any order or even simultaneously, so they are susceptible of being parallelized. Parallel loops are found in a large number of scientific applications. Previous contributions deal with partial aspects of the problems suffered by this kind of users, such as providing access to additional computing resources or enabling the codification of parallel problems, but none takes proper care of providing complete solutions without considering advanced users with access to traditional HPC platforms. Our contribution consists in the design and evaluation of methods to enable the easy parallelization of applications based in parallel loops written in R using non-dedicated environments as a computing platform and considering users without proper experience in parallel computing or system management skills. As a proof of concept, and in order to evaluate the feasibility of our proposal, an extension of R, called R/parallel, has been developed to test our ideas in real environments with real bioinformatics problems. The results show that even in situations with a reduced level of information about the running environment and with a high degree of uncertainty about the quantity and quality of the available resources it is possible to provide a software layer to enable users without previous knowledge and skills adapt their applications with a minimal effort and perform concurrent computations using the available computers. Additionally of proving the feasibility of our proposal, a new self-scheduling scheme, suitable for parallel loops in dynamics environments has been contributed, the results of which show that it is possible to obtain improved performance levels compared to previous contributions in best-effort environments. The main conclusion is that, even in situations with limited information about the environment and the involved technologies, it is possible to provide the mechanisms that will allow users without proper knowledge and time restrictions to conveniently make use and take advantage of parallel computing technologies, so closing the gap between classical HPC solutions and the mainstream of users of common applications, in our case, based in parallel loops with R. mplex IT infrastructures. These High Performance Computing (HPC) solutions, although being the most efficient solutions in terms of performance and scalability, impose technical and practical barriers for most common scientists whom, with reduced IT knowledge, time and resources, are unable to embrace classical HPC solutions without considerable efforts. Moreover, two important technology advances are increasing the need for parallel computing. For example in the bioinformatics field, and similarly in other experimental science disciplines, new high throughput screening devices are generating huge amounts of data within very short time which requires their analysis in equally short time periods to avoid delaying experimental analysis. Another important technological change involves the design of new processor chips. To increase raw performance the current strategy is to increase the number of processing units per chip, so to make use of the new processing capacities parallel applications are required. In both cases we find users that may need to update their current sequential applications and computing resources to achieve the increased processing capacities required for their particular needs. Since parallel computing is becoming a natural option for obtaining increased performance and it is required by new computer systems, solutions adapted for the mainstream should be developed for a seamless adoption. In order to enable the adoption of parallel computing, new methods and technologies are required to remove or mitigate the current barriers and obstacles that prevent many users from evolving their sequential running environments. A particular scenario that specially suffers from these problems and that is considered as a practical case in this work consists of bioinformaticians analyzing molecular data with methods written with the R language. In many cases, with long datasets, they have to wait for days and weeks for their data to be processed or perform the cumbersome task of manually splitting their data, look for available computers to run these subsets and collect back the previously scattered results. Most of these applications written in R are based on parallel loops. A loop is called a parallel loop if there is no data dependency among all its iterations, and therefore any iteration can be processed in any order or even simultaneously, so they are susceptible of being parallelized. Parallel loops are found in a large number of scientific applications. Previous contributions deal with partial aspects of the problems suffered by this kind of users, such as providing access to additional computing resources or enabling the codification of parallel problems, but none takes proper care of providing complete solutions without considering advanced users with access to traditional HPC platforms. Our contribution consists in the design and evaluation of methods to enable the easy parallelization of applications based in parallel loops written in R using non-dedicated environments as a computing platform and considering users without proper experience in parallel computing or system management skills. As a proof of concept, and in order to evaluate the feasibility of our proposal, an extension of R, called R/parallel, has been developed to test our ideas in real environments with real bioinformatics problems. The results show that even in situations with a reduced level of information about the running environment and with a high degree of uncertainty about the quantity and quality of the available resources it is possible to provide a software layer to enable users without previous knowledge and skills adapt their applications with a minimal effort and perform concurrent computations using the available computers. Additionally of proving the feasibility of our proposal, a new self-scheduling scheme, suitable for parallel loops in dynamics environments has been contributed, the results of which show that it is possible to obtain improved performance levels compared to previous contributions in best-effort environments. The main conclusion is that, even in situations with limited information about the environment and the involved technologies, it is possible to provide the mechanisms that will allow users without proper knowledge and time restrictions to conveniently make use and take advantage of parallel computing technologies, so closing the gap between classical HPC solutions and the mainstream of users of common applications, in our case, based in parallel loops with R.

Este trabajo de investigación pertenece al ámbito de las técnicas y métodos para la creación y la producción de contenidos multimedia y se centra en el estudio de las tareas que desarrollan los autores de contenidos multimedia. El Laboratorio de Aplicaciones Multimedia de la UPC (en adelante LAM) ha desarrollado y aplicado durante los últimos años un modelo de producción de contenidos digitales multimedia orientado a facilitar la integración de los expertos en contenidos en el proceso de producción multimedia. El trabajo en el que se basa este estudio se inicia en el año 1992, y recoge la experiencia de:- El análisis de las producciones realizadas con anterioridad al periodo del estudio por 15 personas y en 39.840 horas.- 145 proyectos desarrollados con la participación de 54 personas.- Las anotaciones en las hojas de trabajo de 88.919 horas correspondientes a las distintas tareas de la producción multimedia realizadas durante el periodo que comprende el estudio.- La experiencia en la aplicación para la formación en técnicas y métodos para la producción multimedia de: -- 120 profesores de Universidad-- 3.820 estudiantes de Ingeniería-- 730 estudiantes especializados en la producción multimedia.Los diversos sistemas desarrollados para este modelo, basados en el diseño de procesos y en el uso y adaptación de las herramientas de software comerciales, se han aplicado de forma sistemática en los 31 proyectos que constituyen la base empírica de esta investigación. La investigación tiene como objetivo central el desarrollo de un modelo de producción multimedia centrado en el autor. El modelo desarrollado y experimentado se ha obtenido a partir de la observación y análisis del tipo de tareas, y del conocimiento relacionado con ellas, que intervienen en el desarrollo de contenidos multimedia y permite trasladar al autor algunas de las capacidades de los perfiles profesionales que intervienen en el proceso de producción.La presentación de la investigación se ha organizado en 5 capítulos:1. Objetivos y método.Se definen los objetivos de la investigación, se delimita el ámbito para el cual tienen validez los resultados aportados y se expone el proceso de trabajo que se ha seguido.2. Estudio teórico.Se presentan los conocimientos que constituyen el marco teórico de referencia para la investigación. 3. Desarrollo y descripción del modelo.Se describe el trabajo de campo realizado consistente en el desarrollo gradual del modelo y en la obtención de los criterios para su mantenimiento y mejora.4. Resultados.Se define el modelo para la capacitación de autores de contenidos, que constituye el resultado concreto de esta investigación.5. ConclusionesSe finaliza la memoria de la investigación con una síntesis de las conclusiones a las que ha permitido llegar la investigación, así como las líneas de continuidad de la misma.

L’Optical Flow (OF) és l’input d’una gran varietat de Sistemes de Suport a Decisions (DSS) com ara assistència a la conducció, guia UAV o diagnosis mèdic. En aquestes situacions, l’absència de ground truth ens obliga a avaluar la qualitat de l’OF calculat mitjançant quantitats calculades a partir de les seqüències o bé a partir del mateix OF. Aquestes quantitats es coneixen generalment com a Mesures de Confiança (CM). Encara que tinguem una mesura de confiança, necessitem alguna eina per tal d’avaluar la seva capacitat per descartar píxels de la imatge que tenen tendència a tindre error. Els mètodes actuals només aporten una avaluació descriptiva del rendiment de les CM, el problema és que aquests mètodes no són capaços de comparar equitativament les diferents CM i OF. Així doncs, necessitem definir una metodologia que avalu¨ı el rendiment de les tècniques d’OF. Aquesta tesi aporta la definició d’una metodologia que ens permet decidir quines parelles ”optical flow - mesura de confiança” (OF-CM) estan millor preparades per a definir una cota de l’error de l’OF donat un nivell de confiança per a un DSS. Per tal de definir aquesta metodologia, la tesis engloba els següents punts: • Marcadors qualificatius. Es presenten 3 gràfiques descriptives que avaluen de forma visual les capacitats de CM d’acotar l’error de l’OF. A més a més de les gràfiques descriptives, donada una gràfica representant la parella OF-CM, donem una qualificació automàtica que categoritza la gràfica donat el tipus de perfil. • Metodologia estadística. Es proporciona una metodologia comparativa que permet determinar quina és la millor parella OF-CM per a acotar l’error de l’OF, aquesta metodologia consta de dues parts. Primer s’avalua el valor predictiu de la CM mitjançant la gràfica descriptiva. Després, per a una mostra de gràfiques descriptives calculades sobre unes seqüències de training, s’obté una corba genèrica que es podrà fer servir per a seqüències que no tenen ground truth. En el segon pas, s’avalua la corba genèrica obtinguda i les seves capacitats per a reflectir el valor predictiu de la mesura de confiança mitjançant ANOVA’s. La metodologia presentada mostra el potencial en aplicació clínica per a DSS. En concret, s’ha analitzat l’impacte de diferents artefactes en la imatge com ara soroll o deteriorament en el resultat final d’OF per a imatges del cor. També s’ha aplicat per a millorar la navegació dintre l’arbre bronquial en una broncoscòpia. / Optical Flow (OF) is the input of a wide range of decision support systems such as car driver assistance, UAV guiding or medical diagnose. In these real situations, the absence of ground truth forces to assess OF quality using quantities computed from either sequences or the computed optical flow itself. These quantities are generally known as Confidence Measures, CM. Even if we have a proper confidence measure we still need a way to evaluate its ability to discard pixels with an OF prone to have a large error. Current approaches only provide a descriptive evaluation of the CM performance but such approaches are not capable to fairly compare different confidence measures and optical flow algorithms. Thus, it is of prime importance to define a framework and a general road map for the evaluation of optical flow performance. This thesis provides a framework able to decide which pairs ”optical flow - con- fidence measure” (OF-CM) are best suited for optical flow error bounding given a confidence level determined by a decision support system. To design this framework we cover the following points: • Descriptive scores. As a first step, we summarize and analyze the sources of inaccuracies in the output of optical flow algorithms. Second, we present several descriptive plots that visually assess CM capabilities for OF error bounding. In addition to the descriptive plots, given a plot representing OF-CMcapabilities to bound the error, we provide a numeric score that categorizes the plot according to its decreasing profile, that is, a score assessing CM performance. • Statistical framework. We provide a comparison framework that assesses the best suited OF-CM pair for error bounding that uses a two stage cascade process. First of all we assess the predictive value of the confidence measures by means of a descriptive plot. Then, for a sample of descriptive plots computed over training frames, we obtain a generic curve that will be used for sequences with no ground truth. As a second step, we evaluate the obtained general curve and its capabilities to really reflect the predictive value of a confidence measure using the variability across train frames by means of ANOVA. The presented framework has shown its potential in the application on clinical decision support systems. In particular, we have analyzed the impact of the different image artifacts such as noise and decay to the output of optical flow in a cardiac diagnose system and we have improved the navigation inside the bronchial tree on bronchoscopy.

A medida que los supercomputadores aumentan su potencia, es posible ejecutar aplicaciones con mayor carga computacional y que procesan volúmenes de datos cada vez más grandes. Tradicionalmente, para proporcionar un rendimiento rápido y fiable, los sistemas de ficheros paralelos se centraban en la distribución escalable de los datos. Sin embargo, mayores cargas de trabajo presionan los servidores de metadatos todavía más, con un número de peticiones de metadatos cada vez mayor. Estas operaciones hacen un gran consumo de CPU, y, generalmente, un sólo servidor de metadatos ya no es suficiente. En esta tesis presentamos la arquitectura de un nuevo sistema de ficheros paralelo que proporciona un servicio de metadatos completamente distribuido. Creemos que esto es clave al enfrentarse a la era exabyte en los sistemas de ficheros paralelos. Nuestra primera propuesta es "Fusion Parallel File System" (FPFS). FPFS es un sistema de ficheros paralelo donde todos los dispositivos trabajan como servidores tanto de datos como de metadatos. Con esta arquitectura sencilla incrementamos la capacidad del clúster de metadatos, que pasa a ser tan grande como el clúster de datos. Asimismo, incrementamos el rendimiento y escalabilidad de todo el sistema. Nuestra segunda contribución es el dispositivo OSD+. Proponemos el uso de dispositivos OSD mejorados para construir la arquitectura de FPFS. Los OSD regulares sólo pueden manejar objetos de datos y sus operaciones; nuestra propuesta amplía los dispositivos OSD, de manera que también puedan manejar metadatos a través de lo que hemos llamado "objetos de directorio". Nuestra tercera aportación es el diseño e implementación de un clúster de metadatos basado en dispositivos OSD+ para FPFS. En el clúster distribuimos de forma uniforme los metadatos a través de los nodos del clúster por medio de los objetos de directorio. Nuestra distribución del espacio de nombres minimiza las migraciones en caso de renombramientos de directorios o de cambios dentro del clúster. Garantizamos la atomicidad por medio de un protocolo de compromiso en tres fases y de los sistemas de ficheros locales en cada OSD+. Nuestra cuarta contribución es el diseño e implementación del manejo de directorios gigantes en FPFS. Estos directorios almacenan desde miles a millones de entradas que son accedidas por miles de clientes concurrentemente. Utilizamos los objetos de directorio para permitir a FPFS distribuir de forma dinámica esos directorios a través de varios servidores. A su vez, este diseño mejora el manejo que hacemos de los renombramientos, evitando gran parte de las migraciones de datos. Nuestra última contribución es el diseño e implementación de las operaciones por lotes. Estas operaciones juntan cientos o miles de entradas del mismo tipo de operación en un sólo paquete. Con ellas conseguimos hacer un mejor uso de los recursos existentes, desplazando, en muchos casos, el cuello de botella de la red a los servidores. Para evaluar el rendimiento de nuestra propuesta, hemos implementado un prototipo del servicio de metadatos en un entorno Linux, y comparado su rendimiento con otros sistemas de ficheros paralelos como: Lustre, OrangeFS y Ceph. En las pruebas, se han usado distintos tipos de sistemas de ficheros, y distintos tipos de discos (discos duros y de estado sólido) en los servidores. Asimismo, se han usado benchmarks con distintos tipos de carga de trabajo de metadatos con el fin de evaluar el rendimiento de los metadatos. Los experimentos muestran que FPFS puede crear, stat, y borrar cientos de miles de ficheros vacíos por segundo con unos pocos OSD+s. Los ratios obtenidos con FPFS son un orden de magnitud mayor que el rendimiento que obtiene Lustre con un sólo servidor de metadatos, y que el rendimiento de OrangeFS y Ceph con un clúster de metadatos. / The growth in the number of nodes and computational power of supercomputers allow us to process not only larger and more compute-intensive workloads, but also data-intensive workloads that access and store vast amounts of data. Traditionally, to provide fast and reliable performance, parallel file systems have focused on scalable data distribution to share out the storage and management of large data volumes between several nodes. However, increasing workload is now pushing metadata servers to their limits, with not only greater volumes of data but also critically ever-greater numbers of metadata requests. Metadata operations are very CPU consuming, and a single metadata server is often no longer sufficient. In this thesis we define a new parallel file system architecture that provides a completely distributed metadata service. We believe this is key as we approach the exabyte scale-era in parallel file systems. The main contributions to reach this aim are the following. First, we introduce the Fusion Parallel File System (FPFS) that presents a novel architecture that merges the metadata cluster and the data cluster into one large cluster through the use of a single type of server. This enlarges the capacity of the metadata cluster because it becomes as large as the data cluster, also augmenting the overall system capacity. Second, we propose OSD+ devices to support the FPFS architecture. Object-based Storage Devices (OSDs) have proved to be a perfect tool for parallel file systems, since their inherent intelligence allows file systems to delegate tasks to the devices themselves, such as the management of the device space. OSD+s are improved object-based storage devices that, in addition to handle data objects, as traditional OSDs do, can also manage "directory objects", a new type of object able to store and handle metadata. Third, we develop a scalable metadata cluster made up of hundreds to thousands of OSD+ devices. The design takes into account essential aspects, like a balanced namespace distribution, able to adapt to cluster changes, and the atomicity of operations that involve several OSD+s. Fourth, we enlarge the metadata service capabilities by including support for huge directories. Directories storing thousand to millions of files accessed by thousands of clients at the same time are becoming common in file systems, and present performance downgrades if not handled properly. We modify OSD+ devices to dynamically distribute these directories among several objects in different OSD+s in the cluster. Finally, we propose the use of batch operations, which embed several operations of the same type into a single network packet. This way, we optimize network resources, and significantly reduce network traffic on the system, reducing network delays and round-trips. To evaluate the performance of our proposal, we have implemented a prototype built on a Linux environment, and compared its performance with other well-known parallel file systems as: Lustre, OrangeFS, or Ceph. In the tests, we have used different backend file systems, and different type of backend devices (hard disks, and solid state drives). We have run benchmarks with different types of metadata workloads, in order to evaluate the metadata performance. Experiments show that FPFS can create, stat and unlink hundreds of thousands of empty files per second with a few OSD+s. The rates obtained by FPFS are an order of magnitude better than what Lustre achieves when a single metadata server is used, and what OrangeFS and Ceph achieve when a metadata cluster is deployed.

The present thesis addresses several machine learning problems on generative and predictive models on sequential data. All the models considered have in common that they can be de ned in terms of nite-state machines. On one line of work we study algorithms for learning the probabilistic analog of Deterministic Finite Automata (DFA). This provides a fairly expressive generative model for sequences with very interesting algorithmic properties. State-merging algorithms for learning these models can be interpreted as a divisive clustering scheme where the "dependency graph" between clusters is not necessarily a tree. We characterize these algorithms in terms of statistical queries and a use this characterization for proving a lower bound with an explicit dependency on the distinguishability of the target machine. In a more realistic setting, we give an adaptive state-merging algorithm satisfying the stringent algorithmic constraints of the data streams computing paradigm. Our algorithms come with strict PAC learning guarantees. At the heart of state-merging algorithms lies a statistical test for distribution similarity. In the streaming version this is replaced with a bootstrap-based test which yields faster convergence in many situations. We also studied a wider class of models for which the state-merging paradigm also yield PAC learning algorithms. Applications of this method are given to continuous-time Markovian models and stochastic transducers on pairs of aligned sequences. The main tools used for obtaining these results include a variety of concentration inequalities and sketching algorithms. In another line of work we contribute to the rapidly growing body of spectral learning algorithms. The main virtues of this type of algorithms include the possibility of proving nite-sample error bounds in the realizable case and enormous savings on computing time over iterative methods like Expectation-Maximization. In this thesis we give the rst application of this method for learning conditional distributions over pairs of aligned sequences de ned by probabilistic nite-state transducers. We also prove that the method can learn the whole class of probabilistic automata, thus extending the class of models previously known to be learnable with this approach. In the last two chapters we present works combining spectral learning with methods from convex optimization and matrix completion. Respectively, these yield an alternative interpretation of spectral learning and an extension to cases with missing data. In the latter case we used a novel joint stability analysis of matrix completion and spectral learning to prove the rst generalization bound for this type of algorithms that holds in the non-realizable case. Work in this area has been motivated by connections between spectral learning, classic automata theory, and statistical learning; tools from these three areas have been used.

A la literatura recent hi podem trobar la introducció de noves famílies de codis de Reed- Muller quaternaris lineals RMs. Les imatges d’aquests nous codis a través del mapa de Gray són codis binaris Z4-lineals que comparteixen els paràmetres i les propietats (longitud, dimensió, distància mínima, inclusió, i relació de dualitat) amb la família de codis de Reed- Muller binaris lineals. El kernel d’un codi binari C es defineix com K(C) = {x 2 Zn2 : C + x = C}. La dimensió del kernel és un invariant estructural per els codis binaris equivalents. Part d’aquesta tesi consisteix en establir els valors de la dimensió del kernel per aquestes noves famílies de codis de Reed-Muller Z4-lineals. Tot i que dos codis Z4- lineals no equivalents poden compartir el mateix valor de la dimensió del kernel, en el cas dels codis de Reed-Muller RMs aquest resultat es suficient per donar-ne una classificació completa. Per altra banda, un codi quaternari lineal de Hadamard C, és un codi que un cop li hem aplicat el mapa de Gray obtenim un codi binari de Hadamard. És conegut que els codis de Hadamard quaternaris formen part de les famílies de codis quaternaris de Reed- MullerRMs. Definim el grup de permutacions d’un codi quaternari lineal com PAut(C) = {  2 Sn :  (C) = C}. Com a resultat d’aquesta tesi també s’estableix l’ordre dels grups de permutacions de les famílies de codis de Hadamard quaternaris. A més a més, aquests grups són caracteritzats proporcionant la forma dels seus generadors i la forma de les òrbites del grup PAut(C) actuant sobre el codi C. Sabem que el codi dual, en el sentit quaternari, d’un codi de Hadamard és un codi 1-perfecte estès. D’aquesta manera els resultats obtinguts sobre el grup de permutacions es poden transportar a una família de codis quaternaris 1- perfectes estesos / Recently, new families of quaternary linear Reed-Muller codes RMs have been introduced. They satisfy that, under the Gray map, the corresponding Z4-linear codes have the same parameters and properties (length, dimension, minimum distance, inclusion, and duality relation) as the codes of the binary linear Reed-Muller family. The kernel of a binary code C is K(C) = {x 2 Zn2 : C + x = C}. The dimension of the kernel is a structural invariant for equivalent binary codes. In this work, the dimension of the kernel for these new families of Z4-linear Reed-Muller codes is established. This result is sufficient to give a full classification of these new families of Z4-linear Reed-Muller codes up to equivalence. A quaternary linear Hadamard code C is a code over Z4 that under the Gray map, the corresponding Z4-linear code is a binary Hadamard code. It is well known that quaternary linear Hadamard codes are included in the RMs families of codes. The permutation automorphism group of a quaternary linear code C of length n is defined as PAut(C) = {  2 Sn :  (C) = C}. In this dissertation, the order of the permutation automorphism group of all quaternary linear Hadamard codes is established. Moreover, these groups are completely characterized by providing their generators and also by computing the orbits of their action on C. Since the dual of a Hadamard code is an extended 1-perfect code in the quaternary sense, the permutation automorphism group of the quaternary linear extended 1-perfect codes is also established.

La tesis presenta una aproximació a un conjunt de tècniques per permetre l'extensió de les capacitats computacionals, sota demanada, en comunitats formades per usuaris d'Internet que volen agregar els seus recursos per aconseguir una finalitat comuna. Aquest tipus de comunitats, emergeixen com a noves formes d'organització gràcies a l'increment de les capacitats computacionals i l'ampla de banda. La computació voluntaria com la que es dona en sistemes com SETI@home, Grids col.laboratius com OurGrid o LaCOLLA, Ad-hoc i Grids d'igual a igual com P-Grid o X-Grid d'Apple, Grids Oberts com els adreçats per SORMA o Grid4All i moltes d'altres formes de computació Grid basades en agrupació de recursos en forma d'Organitzacions Virtuals són l'objectiu d'aquest treball. Aquests sistems es caracteritzen pel propòsit dels seus participants, és a dir, dur a terme un objectiu comú fent ús de l'agregació dels sesus propis recursos. Els sistemes esmentats, contrariament als sistemes Grid d'alt rendiment computacional, són oberts a nous participants fet que els converteix en escenaris inpredictibles, dinàmics i on els recuros poden connectar-se i desconnectar-se de forma espontànea. Mentre que l'aspecte crític dels Grids d'altes prestacions és el rendiment computacional, l'estabilitat i la disponibilitat són els aspectes més importants en els sistemes adrec cats en aquest treball. La tesis homogeinitza els conceptes dels paradigmes anteriors sota el nom de Sistemes Contributius, nom que és usat al llarg de la dissertació per referir-nos a sistemes en els quals els seus usuaris fan contribució dels seus recursos per tal que aquest siguin usats de forma col.lectiva i axií aconseguir un objectiu comú. L'expansió de recursos en els Sistemes Contributius és una funcionalitat requerida per tal de augmentar les limitades capacitats computacionals dels grups col.laboratius formats de forma ad-hoc. Sobretot en moments puntuals quan els recursos necessaris són majors que els disponibles en el grup. Quatre aspectes s'adressen al llarg de la dissertació. Primer, les propietats i principals applicacions dels Sistemes Contributius són identificades, així com es motiva la necessitat d'infraestructures que permetin l'expansió de recursos computacionals sota demanda. Aquestes idees van en la direcció de l'Utility Computing, emergents línies de negoci de les principals companyies de la IT. D'aquesta manera, la tesis proposa la provisió de recursos computacionals sota demanda a aquelles organitzacions que en necessitin, mitjanc cant l'agregació de recursos dels extrems d'Internet, ja siguin usuaris finals de la xarxa, altres organitzacions virtuals o proveidors de recursos. En aquest treball, l'assignació de recursos es gestionada per models de mercat ja que proveixen de mecanismes eficients i simples per gestionar l'assignació de recursos. Aquesta proposta aporta noves oportunitats als usuaris finals d'Internet per tal d'establir el seu negoci a la xarxa mitjanc cant la venda dels seus recursos no usats. A més a més aquest treball dona l'oportunitat a communitats petites a creixer i a portar capacitats de super-computació als usuaris finals d'Internet. En segon lloc, la tesis descriu semànticament els recursos computacionals per tal de constru"ir una base comú de coneixement sobre els recursos d'Internet. La descripció semàntica dels recursos permet un enteniment comú de la naturalesa dels recursos, permetent així l'agrupació i agregació de diferents tipus de tecnologíes mentre es mantenen la mateixa semàntica. Una base semàntica comú permet que aplicacions i sistemes de gestió de recursos siguin independents de la naturalesa real dels recursos. En aquest treball considerem com a aspecte fonamental aillar la gestió dels recursos de la seva naturalesa específica. La descripció semàntica a més permet el desenvolupament de especificacions genèriques que ens permeten definir els requeriments dels usuaris en sistemes d'assignació de recursos basats en mercats computacionals. Tercer, arquitectures que permeten l'expansió de recursos computacionals sota demanda en Sistemes Contributius són presentades. Aquestes arquitectures han estat especialment dissenyades per prove"ir de recursos computacionals mitjanc cant mercats a escenaris caracteritzats pel dinamisme, evolució i heterogene"itat dels seus recursos. L'arquitectura aporta les principals funcionalitats orientades a l'assignació de recursos mitjanc cant subhastes i permet a més a més l'execució d'aquests mercats sota demanda. Finalment, es presenta un mecanisme de mercat adaptat a l'assignació de recursos computacionals. Aquesta contribució es motiva pel fet que no existeix fins avui cap mecanisme que permeti l'assignació efficient de recursos computacionals en que la seva única diferència és la unitat de temps en la que s'ofereixen. La tesis construeix un camí per assolir l'expansió de recursos computacionals de forma flexible i decentralitzada en comunitats on els recursos són compartits pels seus participants. Aquest camí es construeix mitjanc cant l'anàlisis dels escenaris d'aplicació, l'estudi i definició de models semàntics que permeten la descripció dels recursos computacionals, proposant també arquitectures flexibles i configurables que permeten aconseguir l'expansió dels recursos computacionals sota demanda i proposant mecanismes de mercat adaptats a tal escenari. / The thesis presents an approach to on-demand capacity expansion in communities of Internet users that aggregate their resources to achieve a common objective. Such commu- nities are emerging as forms of organisation taking advantage of an increasing broadband access and computational capacity. Volunteer computing such as SETI@home, Collab- orative Grids such as OurGrid and LaCOLLA, Ad-hoc and Peer-to-Peer Grids, such as P-Grid and the XGrid project from Apple, Open Grids such as those addressed by SORMA and Grid4All and many other approaches of Grid Computing based on Virtual Organisa- tions are the focus of our work. These systems are characterised by the purpose of their participants, i.e. to achieve a common objective taking advantage of the aggregation of other resources. The cited systems, in contrast to high performance computing Grids, are open to new participants, which makes their behaviour unpredictable and dynamic, and resources are usually connected and disconnected spontaneously. While the critical aspect of high performance Grids is computational performance, stability and availability are the main issues for the systems addressed in this work. The thesis homogenises the concepts of those paradigms under the term Contributory System, which is used throughout the thesis to refer to the systems where users provide their resources to be used collectively to achieve a common objective. Resource expan- sion in Contributory Systems is required so as to increase the limited capacities of ad-hoc collaborative groups under unexpected load surges, temporary resource requirements or other policies defined by the objectives of the Virtual Organisation that they constitute. Four aspects are addressed by the dissertation. Firstly, it identifies the main properties and applications of Contributory Systems and motivates the need for infrastructures to enable on-demand resource expansion. This goes in the direction of Utility Computing trends which are main business lines for IT companies. Thus the thesis proposes the on-demand provision of idle resources from the extremes of the Internet, other Virtual Or- ganisations or Resource Providers to those organisations that have resource needs. In this work, resource allocation is handled by market models which provide efficient while simple mechanisms to mediate the allocation of resources. This proposal enables new emerging opportunities to Internet users to make their business on the Internet by selling their idle resources. Besides, this brings the opportunity to small communities to grow and to bring super-computing capacities to Internet end-users. Secondly, the thesis describes semantically Computational Resources so as to build a common knowledge about the Internets resources. The semantic description enables a common understanding of the nature of resources, permitting the pooling and aggrega- tion of distinct types of technologies while maintaining the same semantics. This makes applications and resource management frameworks independent of the real nature of the resources which we claim as a fundamental aspect to keep resource management indepen- dent of the dynamics and evolution of technology in computational environments, such as in Contributory Systems. A semantic description permits the development of generic specifications to provide bid and offer descriptions in computational markets. Thirdly, the architecture for on-demand resource expansion in Contributory Systems is presented. It has been designed to provide the main functionalities to on-demand provi- sion of resources through markets to scenarios characterized by dynamism, evolution and heterogeneity. The architecture provides the main market oriented functionalities and en- ables dynamic and on-demand execution of market mechanisms. Finally, a specific Grid-oriented market mechanism is presented. The approach is moti- vated due to the unsuitability of current auctions to efficiently allocate time-differentiated resources (usually provided by many different resource providers) such as most of the re- sources in a Contributory System. The thesis builds a roadmap to achieve flexible and decentralized resource expansion in communities where resources are shared by their participants by analysing the main scenarios where it can be applied, providing the semantics and specification to enable the description of the user's requirements, proposing a flexible and configurable architecture to deal with on-demand resource expansion in Virtual Organisations and proposing an specific mechanism adapted to trade computational resources.

Evaluar el rendimiento de una aplicación paralela es cada vez más complejo. Una vez terminado el desarrollo, cuando una aplicación pasa a producción, el rendimiento y la eficiencia son fundamentales para los usuarios y administradores. Por ello, cada vez es más importante ser capaz de tener información para seleccionar adecuadamente cuál es el sistema más apropiado para ejecutar la aplicación, o cuánto tiempo de ejecución llevará ejecutar la aplicación entera, a fin de tener una previsión que permita hacer una mejor gestión y utilización uso de los recursos disponibles. La evaluación del rendimiento es importante a todos los niveles relacionados con los sistemas informáticos, incluyendo el diseño, el desarrollo, ventas/compras, en el uso, actualización y el redimensionamiento de los sistemas. La evaluación del rendimiento se vuelve necesaria cuando el diseñador quiere comparar entre varios sistemas informáticos y decidir cuál es el mejor sistema para un determinado conjunto de aplicaciones. Incluso si no hay alternativas, la evaluación del rendimiento del sistema actual ayuda a determinar cuál es el rendimiento de una aplicación, la necesidad de recursos y ayuda a decidir si las mejoras deben realizarse.