Search

La predicció de salts és un component essencial de qualsevol processador modern. A mesura que els pipelines creixen, la penalizació per mispredict es veu incrementada, i evitar-la és clau per a obtenir un bon rendiment. En aquest projecte, es desenvoluparà i implementarà una Unitat de Predicció de Salts per a un processador comercial RISC-V de 64 bits (nom en clau Avispado). La unitat estarà basada en el predictor de salts TAGE, il·lustrat per Seznec et al. l’any 2006. El predictor serà completament parametritzable, per a permetre al futur una expansió fàcil. El disseny estarà implementat íntegrament en SystemVerilog sintetitzable. Es mostraran els resultats de la síntesi, analitzant l’àrea i el timing de la unitat. Primer, un banc de proves autònom serà utilitzat, comparant diferents implementacions d’un predictor de salts que porten cap al predictor TAGE. Després, es realitzaran algunes modificacions al predictor perquè pugui reemplaçar al predictor existent a Avispado. Múltiples configuracions del predictor TAGE seran comparades mitjançant l’execució de benchmarks, estudiant com diferents pressupostos d’emmagatzematge afecten la ràtio de mispredicts. La predicción de saltos es un componente esencial de cualquier procesador moderno. A medida que los pipelines crecen, la penalización por mispredict se ve incrementada, y evitarla es clave para obtener un buen rendimiento. En este proyecto, se desarrollará e implementará una Unidad de Predicción de Saltos para un procesador RISC-V de 64 bits comercial (nombre en clave Avispado). La unidad estará basada en el predictor de saltos TAGE, ilustrado por Seznec et al. en 2006. El predictor será completamente parametrizable, para permitir en el futuro una expansión fácil. El diseño estará implementado íntegramente en SystemVerilog sintetizable. Se mostrarán los resultados de la síntesis, analizando el área y el timing de la unidad. Primero, un banco de pruebas autónomo será usado, comparando diferentes implementaciones de un predictor de saltos que llevan hacia el predictor TAGE. Después, se realizarán algunas modificaciones al predictor para que pueda reemplazar al predictor existente en Avispado. Múltiples configuraciones del predictor TAGE serán comparadas mediante la ejecución de benchmarks, estudiando como distintos presupuestos de almacenamiento afectan al ratio de mispredicts. Branch prediction is a fundamental component of any modern processor. With growing pipelines, the mispredict penalty gets higher, and avoiding it is key to obtain a good performance. In this project, a Branch Prediction Unit for a commercial in-order 64-bit RISC-V core (code named Avispado) will be developed and implemented. This unit will be based on the TAGE branch predictor, showcased by Seznec et al. in 2006. The predictor will be fully parameterizable, to allow for easy future expansion. The design will be fully implemented in synthesizable SystemVerilog. Synthesis results will be provided, analyzing area and timing of the unit. First, a standalone testbench will be used, comparing various branch predictor implementations that lead to the TAGE predictor. Afterwards, some modifications will be made to allow the predictor to replace Avispado’s existing branch predictor. Multiple configurations will be compared and benchmarked, studying how different storage budgets affect the misprediction rate.

[ES] Dada la actual necesidad de innovación a nivel arquitectural, es necesario contar con herramientas y metodologías eficientes para validar y evaluar nuevos diseños. En el ámbito de este TFM se ha diseñado e implementado un procesador RISC-V totalmente parametrizado en un intervalo de tiempo muy reducido. Esto se ha logrado incorporando y desarrollando a lo largo del flujo de trabajo herramientas que han facilitado este proceso, combinando la simplicidad y eficiencia de la simulación con la precisión y utilidad de contar con una implementación hardware. El procesador en sí soporta la ejecución fuera de orden (mediante renombrado de registros explícito y colas de issue), decodificación/lanzamiento/commit superescalar de ancho variable, y genericidad en la mayoría de las estructuras de datos. En cuanto al juego de instrucciones, soporta las principales del ISA RISC-V y varias de sus extensiones. La implementación ha sido validada ejecutando programas de ejemplo sobre múltiples configuraciones. El código se ha planteado para que sea flexible y de fácil expansión: siguiendo nuestra metodología y con las herramientas desarrolladas, futuros proyectos de investigación que consistan en la modificación de una arquitectura podrán ser validados e implementados rápidamente, incluso en un entorno que, al igual que muchos grupos de investigación, esté formado por gente con bases y conocimientos distintos. En esa línea, este trabajo ya ha allanado el terreno para experimentar con ideas más innovadoras, y se proporciona un ejemplo de esto: el desarrollo de una extensión sobre nuestro núcleo que añade funcionalidades propias de un sistólico., [EN] Given the dire need for architectural innovation, efficient tools and methodologies are required to validate, test, and evaluate new designs. For this Master's Thesis we designed and implemented a fully parameterized RISC-V core in a very restricted timeframe. We achieved this by means of a toolflow that combines the simplicity and efficiency of simulation with the accuracy and general usefulness of an actual hardware implementation. The core itself supports Out-of-Order execution (by means of explicit register renaming and Issue Queues), superscalar instruction decode/issue/commit with variable width, and most of its data structures are generic. As for the instruction set, it can handle the main instructions of the base RISC-V ISA and several of its extensions. Its correctness has been validated with sample programs running on multiple configurations. The code has been engineered with flexibility and expandability in mind: aided by the rest of said toolflow, future research that involves modifying the architecture can be validated and implemented as soon as possible, even in an environment that, as many research groups, is formed by people of many different backgrounds. In that regard, it has already laid the groundwork to test more innovative ideas, and an example of this is provided in the form of a systolic extension to our base core., [CA] Amb l’actual necessitat d’innovació a nivell arquitectural, és necessari comptar amb ferramentes i metodologies eficients per a validar i avaluar nous dissenys. En l’àmbit d’este TFM s’ha dissenyat i implementat un processador RISC-V totalment parametritzat en un interval de temps molt reduït. Açò s’ha aconseguit incorporant i desenvolupant al llarg del flux de treball ferramentes que han facilitat este procés, combinant la simplicitat i eficiència de la simulació amb la precisió i utilitat de comptar amb una implementació hardware. El processador en si suporta l’execució fora d’orde (amb register renaming explícit i cues d’issue) , decodificaci ó/llançament/commit superescalar d’ample variable, i genericitat en la majoria de les estructures de dades. Quant al joc d’instruccions, suporta les principals de l’ISA RISC-V i diverses de les seues extensions. La implementació ha sigut validada executant programes d’exemple sobre múltiples configuracions. El codi s’ha plantejat perquè siga flexible i de fàcil expansió: seguint la nostra metodologia i amb les ferramentes desenvolupades, futurs projectes d’investigació que consistisquen en la modificació d’una arquitectura podran ser validats i implementats ràpidament, inclús en un entorn que, igual que molts grups d’investigació, estiga format per gent amb bases i coneixements distints. En eixa línia, este treball ja ha aplanat el terreny per a experimentar amb idees més innovadores, i es proporciona un exemple d’açò: el desenvolupament d’una extensió sobre el nostre nucli que afig funcionalitats pròpies d’un sistólic.

El projecte consisteix a en la cerca de la viabilitat i el desenvolupament d'una aplicació que permeti executar Open Overlay Router sobre el sistema operatiu Apple iOS. Open Overlay Router és un implementació de codi amb llicencia Apache 2.0 per crear xarxes de overlay programables, esta disponible per als sistemes operatius Android, Linux i OpenWrt. Amb aquest projecte incorporarem Apple iOS a la llista de sistemes operatius suportats. This project consist of the feasibility investigation and the development of an application that allows to run Open Overlay Router on the Apple iOS operating System. Open Overlay Router is an implementation of code with Apache 2.0 license that allows you to create programable overlay networks. Is available for Android, Linux and OpenWRT operating Systems. With this project we will incorporate Apple iOS to the list of supported operating systems.

El projecte VerilCIRC Metrics té l'objectiu de crear una eina útil per a l'ensenyament a distància del disseny de circuits digitals. S'integra en un projecte més ampli anomenat VerilCIRC, que actualment ja proporciona als alumnes les eines necessàries per resoldre els exercicis que se'ls assignen. VerilCIRC ja disposa d'un sistema per avaluar les solucions proposades pels alumnes en termes de funcionalitat. Amb el projecte VerilCIRC Metrics es vol afegir la capacitat d'avaluar les solucions en funció de la seva qualitat, en termes d'optimització de recursos i estalvi d'àrea i retard dels circuits. El proyecto VerilCIRC Metrics tiene el objetivo de crear una herramienta útil para la enseñanza a distancia del diseño de circuitos digitales. Se integra en un proyecto más amplio llamado VerilCIRC, que actualmente ya proporciona a los alumnos las herramientas necesarias para resolver los ejercicios que se les asignan. VerilCIRC ya dispone de un sistema para evaluar las soluciones propuestas por los alumnos en términos de funcionalidad. Con el proyecto VerilCIRC Metrics se quiere añadir la capacidad de evaluar las soluciones en función de su calidad, en términos de optimización de recursos y ahorro de área y retraso de los circuitos. The VerilCIRC Metrics project aims to create a useful tool for distance learning of digital circuit design. It integrates into a larger project called VerilCIRC, which now provides students with the tools needed to solve the exercises assigned to them.

Traditionally, the formal modelling of systems has been done by using mathematical expression. Actually the current growing capacity of computers provides new tools to support the process of decision making in various disciplines and areas. Nowadays, computer simulation has become an essential part of system modelling. By definition a computer simulation is an attempt to model almost all the imaginable real-life or hypothetical situation on a computer so that it can be studied to see how the system works. It is a tool to virtually investigate the behaviour of the system under study. This is exactly the aim of this master thesis, examining the conduct of the system that is wanted to study using data mining methods. In essence, that system is a distributed network with resource sharing, implanted in order to solve the insufficiency of CPU resources due to the constant increasing demand. The simulation tool is capable of running various cooperation games, strategies and topologies in a fully distributed environment in order to know what the relationship between these elements is. Furthermore, the procedures used to handle the resultant information are data mining algorithms which combine tools from statistics and artificial intelligence with database management. Then, the first part focuses on the study of the simulator tool; the parameters used and output results. The second task is to investigate the data mining methods and tools used to the implementation. The next objective is to adapt the simulator results to the analysis tools and execute them. And finally analyze the results in other to check the effectiveness to see the behaviour of the system.

Transactional memory (TM) is a new optimistic synchronization technique which has the potential of making shared memory parallel programming easier compared to locks without giving up from the performance. This thesis explores four aspects in the research of transactional memory. First, it studies how programming with TM compares to locks. During the course of work, it develops the first real transactional application ¿ AtomicQuake. AtomicQuake is adapted from the parallel version of the Quake game server by replacing all lock-based synchronization with atomic blocks. Findings suggest that programming with TM is indeed easier than locks. However the performance of current software TM systems falls behind the efficiently implemented lock-based versions of the same program. Also, the same findings report that the proposed language level extensions are not sufficient for developing robust production level software and that the existing development tools such as compilers, debuggers, and profilers lack support for developing transactional application. Second, this thesis introduces new set of debugging principles and abstractions. These new debugging principles and abstractions enable debugging synchronization errors which manifest at coarse atomic block level, wrong code inside atomic blocks, and also performance errors related to the implementation of the atomic block. The new debugging principles distinguish between debugging at the language level constructs such as atomic blocks and debugging the atomic blocks based on how they are implemented whether TM or lock inference. These ideas are demonstrated by implementing a debugger extension for WinDbg and the ahead-of-time C# to X86 Bartok-STM compiler. Third, this thesis investigates the type of performance bottlenecks in TM applications and introduces new profiling techniques to find and understand these bottlenecks. The new profiling techniques provide in-depth and comprehensive information about the wasted work caused by aborting transactions. The individual profiling abstractions can be grouped in three groups: (i) techniques to identify multiple conflicts from a single program run, (ii) techniques to describe the data structures involved in conflicts by using a symbolic path through the heap, rather than a machine address, and (iii) visualization techniques to summarize which transactions conflict most. The ideas were demonstrated by building a lightweight profiling framework for Bartok-STM and an offline tool which process and display the profiling data. Forth, this thesis explores and introduces new TM specific optimizations which target the wasted work due to aborting transactions. Using the results obtained with the profiling tool it analyzes and optimizes several applications from the STAMP benchmark suite. The profiling techniques effectively revealed TM-specific bottlenecks such as false conflicts and contentions accesses to data structures. The discovered bottlenecks were subsequently eliminated with using the new optimization techniques. Among the optimization highlights are the transaction checkpoints which reduced the wasted work in Intruder with 40%, decomposing objects to eliminate false conflicts in Bayes, early release in Labyrinth which decreased wasted work from 98% to 1%, using less contentions data structures such as chained hashtable in Intruder and Genome which have higher degree of parallelism.

Les últimes dècades el rendiment dels processadors i de les memòries ha millorat a diferent ritme, limitant el rendiment dels processadors i creant el conegut memory gap. Sol·lucionar aquesta diferència de rendiment és un camp d'investigació d'actualitat i que requereix de noves sol·lucions. Una sol·lució a aquest problema són les memòries “cache”, que permeten reduïr l'impacte d'unes latències de memòria creixents i que conformen la jerarquia de memòria. La majoria de d'organitzacions de les “caches” estan dissenyades per a uniprocessadors o multiprcessadors tradicionals. Avui en dia, però, el creixent nombre de transistors disponible per xip ha permès l'aparició de xips multiprocessador (CMPs). Aquests xips tenen diferents propietats i limitacions i per tant requereixen de jerarquies de memòria específiques per tal de gestionar eficientment els recursos disponibles. En aquesta tesi ens hem centrat en millorar el rendiment i la eficiència energètica de la jerarquia de memòria per CMPs, des de les “caches” fins als controladors de memòria. A la primera part d'aquesta tesi, s'han estudiat organitzacions tradicionals per les “caches” com les privades o compartides i s'ha pogut constatar que, tot i que funcionen bé per a algunes aplicacions, un sistema que s'ajustés dinàmicament seria més eficient. Tècniques com el Cooperative Caching (CC) combinen els avantatges de les dues tècniques però requereixen un mecanisme centralitzat de coherència que té un consum energètic molt elevat. És per això que en aquesta tesi es proposa el Distributed Cooperative Caching (DCC), un mecanisme que proporciona coherència en CMPs i aplica el concepte del cooperative caching de forma distribuïda. Mitjançant l'ús de directoris distribuïts s'obté una sol·lució més escalable i que, a més, disposa d'un mecanisme de marcatge més flexible i eficient energèticament. A la segona part, es demostra que les aplicacions fan diferents usos de la “cache” i que si es realitza una distribució de recursos eficient es poden aprofitar els que estan infrautilitzats. Es proposa l'Elastic Cooperative Caching (ElasticCC), una organització capaç de redistribuïr la memòria “cache” dinàmicament segons els requeriments de cada aplicació. Una de les contribucions més importants d'aquesta tècnica és que la reconfiguració es decideix completament a través del maquinari i que tots els mecanismes utilitzats es basen en estructures distribuïdes, permetent una millor escalabilitat. ElasticCC no només és capaç de reparticionar les “caches” segons els requeriments de cada aplicació, sinó que, a més a més, és capaç d'adaptar-se a les diferents fases d'execució de cada una d'elles. La nostra avaluació també demostra que la reconfiguració dinàmica de l'ElasticCC és tant eficient que gairebé proporciona la mateixa taxa de fallades que una configuració amb el doble de memòria.Finalment, la tesi es centra en l'estudi del comportament de les memòries DRAM i els seus controladors en els CMPs. Es demostra que, tot i que els controladors tradicionals funcionen eficientment per uniprocessadors, en CMPs els diferents patrons d'accés obliguen a repensar com estan dissenyats aquests sistemes. S'han presentat múltiples sol·lucions per CMPs però totes elles es veuen limitades per un compromís entre el rendiment global i l'equitat en l'assignació de recursos. En aquesta tesi es proposen els Thread Row Buffers (TRBs), una zona d'emmagatenament extra a les memòries DRAM que permetria guardar files de dades específiques per a cada aplicació. Aquest mecanisme permet proporcionar un accés equitatiu a la memòria sense perjudicar el seu rendiment global. En resum, en aquesta tesi es presenten noves organitzacions per la jerarquia de memòria dels CMPs centrades en la escalabilitat i adaptativitat als requeriments de les aplicacions. Els resultats presentats demostren que les tècniques proposades proporcionen un millor rendiment i eficiència energètica que les millors tècniques existents fins a l'actualitat., Processor performance and memory performance have improved at different rates during the last decades, limiting processor performance and creating the well known "memory gap". Solving this performance difference is an important research field and new solutions must be proposed in order to have better processors in the future. Several solutions exist, such as caches, that reduce the impact of longer memory accesses and conform the system memory hierarchy. However, most of the existing memory hierarchy organizations were designed for single processors or traditional multiprocessors. Nowadays, the increasing number of available transistors has allowed the apparition of chip multiprocessors, which have different constraints and require new ad-hoc memory systems able to efficiently manage memory resources. Therefore, in this thesis we have focused on improving the performance and energy efficiency of the memory hierarchy of chip multiprocessors, ranging from caches to DRAM memories. In the first part of this thesis we have studied traditional cache organizations such as shared or private caches and we have seen that they behave well only for some applications and that an adaptive system would be desirable. State-of-the-art techniques such as Cooperative Caching (CC) take advantage of the benefits of both worlds. This technique, however, requires the usage of a centralized coherence structure and has a high energy consumption. Therefore we propose the Distributed Cooperative Caching (DCC), a mechanism to provide coherence to chip multiprocessors and apply the concept of cooperative caching in a distributed way. Through the usage of distributed directories we obtain a more scalable solution and, in addition, has a more flexible and energy-efficient tag allocation method. We also show that applications make different uses of cache and that an efficient allocation can take advantage of unused resources. We propose Elastic Cooperative Caching (ElasticCC), an adaptive cache organization able to redistribute cache resources dynamically depending on application requirements. One of the most important contributions of this technique is that adaptivity is fully managed by hardware and that all repartitioning mechanisms are based on distributed structures, allowing a better scalability. ElasticCC not only is able to repartition cache sizes to application requirements, but also is able to dynamically adapt to the different execution phases of each thread. Our experimental evaluation also has shown that the cache partitioning provided by ElasticCC is efficient and is almost able to match the off-chip miss rate of a configuration that doubles the cache space. Finally, we focus in the behavior of DRAM memories and memory controllers in chip multiprocessors. Although traditional memory schedulers work well for uniprocessors, we show that new access patterns advocate for a redesign of some parts of DRAM memories. Several organizations exist for multiprocessor DRAM schedulers, however, all of them must trade-off between memory throughput and fairness. We propose Thread Row Buffers, an extended storage area in DRAM memories able to store a data row for each thread. This mechanism enables a fair memory access scheduling without hurting memory throughput. Overall, in this thesis we present new organizations for the memory hierarchy of chip multiprocessors which focus on the scalability and of the proposed structures and adaptivity to application behavior. Results show that the presented techniques provide a better performance and energy-efficiency than existing state-of-the-art solutions.

Los usuarios del Departamento de Arquitectura de Computadores tienen a su disposición un equipo de técnicos encargados de gestionar, mantener y crear los recursos y servicios informáticos que el departamento pone a disposición de éstos. En la actualidad, la mayor parte de incidentes y peticiones relativas a estos recursos y servicios se reciben a través del correo electrónico o del teléfono (y, en menor medida, en persona), por lo que los técnicos se encargan de introducirlas en el gestor de incidentes para su posterior resolución. Este hecho es fuente de imprecisiones y retrasos, en algunos casos evitables, tal y como se muestra en este proyecto. La finalidad de este proyecto es el desarrollo de una aplicación que pueda atender, gestionar y resolver los incidentes y peticiones de un entorno real de atención al usuario. Ha de ser suficientemente flexible como para poder añadir nuevos módulos de resolución de incidentes, así como para poder ser independiente del gestor de incidentes utilizado. El sistema se distribuye con algunos módulos para resolver los incidentes más típicos, pero existe la posibilidad de aumentar fácilmente su número si se siguen las instrucciones disponibles en el manual del desarrollador. El sistema se ha desarrollado de forma que soporta el gestor de incidentes GN6, propiedad de UPCNet, pero está preparado para utilizar cualquier gestor de incidentes si se implementa correctamente el módulo que lo gestione.

The adoption of multi- and many-core architectures for mainstream computing undoubtedly brings profound changes in the way software is developed. In particular, the use of fine grained locking as the multi-core programmer’s coordination methodology is considered by more and more experts as a dead-end. The transactional memory (TM) programming paradigm is a strong contender to become the approach of choice for replacing locks and implementing atomic operations in concurrent programming. Combining sequences of concurrent operations into atomic transactions allows a great reduction in the complexity of both programming and verification, by making parts of the code appear to execute sequentially without the need to program using fine-grained locking. Transactions remove from the programmer the burden of figuring out the interaction among concurrent operations that happen to conflict when accessing the same locations in memory. The EU-funded FP7 VELOX project designs, implements and evaluates an integrated TM stack, spanning from programming language to the hardware support, and including runtime and libraries, compilers, and application environments. This paper presents an overview of the VELOX TM stack and its associated challenges and contributions.

For a non IT expert to use services in the Cloud is more natural to negotiate the QoS with the provider in terms of service-level metrics –e.g. job deadlines– instead of resourcelevel metrics –e.g. CPU MHz. However, current infrastructures only support resource-level metrics –e.g. CPU share and memory allocation– and there is not a well-known mechanism to translate from service-level metrics to resource-level metrics. Moreover, the lack of precise information regarding the requirements of the services leads to an inefficient resource allocation –usually, providers allocate whole resources to prevent SLA violations. According to this, we propose a novel mechanism to overcome this translation problem using an online prediction system which includes a fast analytical predictor and an adaptive machine learning based predictor. We also show how a deadline scheduler could use these predictions to help providers to make the most of their resources. Our evaluation shows: i) that fast algorithms are able to make predictions with an 11% and 17% of relative error for the CPU and memory respectively; ii) the potential of using accurate predictions in the scheduling compared to simple yet well-known schedulers.

This paper shows that breaking the barrier of 1 triangle/clock rasterization rate for microtriangles in modern GPU architectures in an efficient way is possible. The fixed throughput of the special purpose culling and triangle setup stages of the classic pipeline limits the GPU scalability to rasterize many triangles in parallel when these cover very few pixels. In contrast, the shader core counts and increasing GFLOPs in modern GPUs clearly suggests parallelizing this computation entirely across multiple shader threads, making use of the powerful wide-ALU instructions. In this paper, we present a very efficient SIMD-like rasterization code targeted at very small triangles that scales very well with the number of shader cores and has higher performance than traditional edge equation based algorithms. We have extended the ATTILA GPU shader ISA (del Barrioet al. in IEEE International Symposium on Performance Analysis of Systems and Software, pp. 231–241, 2006) with two fixed point instructions to meet the rasterization precision requirement. This paper also introduces a novel subpixel Bounding Box size optimization that adjusts the bounds much more finely, which is critical for small triangles, and doubles the 2x2- pixel stamp test efficiency. The proposed shader rasterization program can run on top of the original pixel shader program in such a way that selected fragments are rasterized, attribute interpolated and pixel shaded in the same pass. Our results show that our technique yields better performance than a classic rasterizer at 8 or more shader cores, with speedups as high as 4x for 16 shader cores.

Commercialization of computing resources will become more and more important as the transition from Grid computing in academic environments to commercial services based on concepts such as utility or Cloud computing progresses. This results in the necessity to not only base components on technical aspects, but also to include economical aspects in their design. This paper presents a framework that links technical and economical aspects to the management of computational resources. Economic enhancements like dynamic pricing and client classification are introduced based on a technical resource management environment and positioned within this resulting in a proposed architecture for an Economically Enhanced Resource Manager (EERM). The introduced approach is evaluated considering various economic design criteria and example scenarios.

This project is written with the purpose to find a solution to the high levels of energy consumption that there are nowadays. The current proliferation of network devices that are continuously powered on produces an urgent need to think about a simple and effective way to reduce their power consumption. We find out that most people prefer to leave their PCs always on; this mainly dues to the little sensibility that people have toward the cost of keeping a PC on and the cost of both, in terms of time and technical skill, to properly and quickly switch on and off a PC. These somehow surprising facts suggested us to design a solution able to control the power state of PCs in the Campus, explicitly targeting the ease of use. The result is Polisave, a centralized web-based architecture which allows users to schedule power state of their PCs; the server remotely triggers power-up and power-down events by piloting a custom software which has to be installed in each PC. This thesis is based on the realization of Polisave for Linux. This project examines how to perform actions to turn on, suspend, hibernate or shut down computers with Linux through the programming. There is also a great survey of two complex technologies such as HAL, which allows obtaining the hardware characteristics of a computer and DBUS, which allows multiple applications to communicate. It also analyses other simple but important technologies in the Linux software such as logs, daemons, GUI... Therefore, the result of this thesis is not only a software to perform energy saving actions, but a small study with examples of technologies which can help anyone interested in learning these technologies.

This paper presents the system architecture of a Content- Based Image Retrieval system implemented as a web service. The proposed solution is composed of two parts, a client run- ning a graphical user interface for query formulation and a server where the search engine explores an image repository. The separation of the user interface and the search engine follows a Service as a Software (SaaS) model, a type of cloud computing design where a single core system is online and available to authorized clients. The proposed architecture follows the REST software architecture and HTTP proto- col for communications, two solutions that combined with metadata coded in RDF, make the proposed system ready for its integration in the semantic web. User queries are formulated by visual examples through a graphical inter- face and content is remotely accessed also through HTTP communication. Visual descriptors and similarity measures implemented in this work are mostly de ned in the MPEG-7 standard, while textual metadata is coded according to the Dublin Core speci cations.

Las tecnologías de la información (TI) cada vez juegan un papel más importante en los negocios de hoy en día. Empresas de todo tipo y dimensiones aumentan su demanda e invierten con el objetivo de incrementar la competitividad en el mercado en el que se encuentran. Ante esta situación, se plantea un modelo de negocio en el que tanto la infraestructura de comunicaciones como los sistemas de una empresa cualquiera puedan ser proporcionados mediante un interlocutor único y especializado en soluciones globales de TI. El interlocutor proveería y/o gestionaría las comunicaciones LAN y WAN, además de ofrecer servicios centralizados de Data Center que permitiría a las empresas tanto a disminuir costes en infraestructuras como a despreocuparse por la necesidad de disponer de personal técnico cualificado.

In recent years, the size and dynamics of the global routing table have increased rapidly along with an increase in the number of edge networks. The relation between edge network quantity and routing table size/dynamics reveals a major limitation in the current architecture. In this paper we introduce the two problematics target as the main cause for the Internet scalability issue. Subsequently, we describe the different proposals that address the scalability problem. We group them in three categories: Separation, Elimination and Geographic

Memory-intensive threads can hoard shared re- sources without making progress on a multithreading processor (SMT), thereby hindering the overall system performance. A recent promising solution to overcome this important problem in SMT processors is Runa-head Threads (RaT). RaT employs runahead execution to allow a thread to speculatively execute instructions and prefetch data instead of stalling for a long-latency load. The main advantage of this mechanism is that it exploits memory-level parallelism under long latency loads without clogging up shared resources. As a result, RaT improves the overall processor performance reducing the resource contention among threads. In this paper, we propose simple code semantic based techniques to increase RaT efficiency. Our proposals are based on analyzing the prefetch opportunities (usefulness) of loops and subroutines during runahead thread executions. We dynamically analyze these particular program structures to detect when it is useful or not to control the runahead thread execution. By means of this dynamic information, the proposed techniques make a control decision either to avoid or to stall the loop or subroutine execution in runahead threads. Our experimental results show that our best proposal signifi cantly reduces the speculative instruction execution (33% on average) while maintaining and, even improving the performance of RaT (up to 3%) in some cases.

Non-Uniform Cache Architectures (NUCA)have been proposed as a solution to overcome wire delays that will dominate on-chip latencies in Chip Multiprocessor designs in the near future. This novel means of organization divides the total memory area into a set of banks that provides non-uniform access latencies and thus faster access to those banks that are close to the processor. A NUCA model can be characterized according to the four policies that determine its behavior: bank placement, bank access, bank migration and bank replacement. Placement determines the first location of data, access defines the searching algorithm across the banks, migration decides data movements inside the memory and replacement deals with the evicted data. This paper analyzes the performance of several alternatives that can be considered for each of these four policies. Moreover, the Parsec v2.0 benchmark suite has been used to handle this evaluation because it is a representative group of upcoming shared-memory programs for Chip Multiprocessors. The results may help researchers to identify key features of NUCA organizations and to open up new areas of investigation.

We present an innovative architecture that enables the digital representation of original works and derivatives while implementing Digital Rights Management (DRM) features. The architecture’s main focus is on promoting trust within the multimedia content value networks rather than solely on content access and protection control. The system combines different features common in DRM systems such as licensing, content protection, authorization and reporting together with innovative concepts, such as the linkage of original and derived content and the definition of potential rights. The transmission of reporting requests across the content value network combined with the possibility for authors to preserve rights over derivative works enables the system to distribute income amongst all the actors involved in different steps of the creation and distribution chain. The implementation consists of a web application which interacts with different external services plus a desktop user application used to render protected content. It is currently publicly accessible for evaluation.

As long as computers continue to get more CPU processing power, data centers need to optimize their power usage. We can do this and maintain the same complexity level as before by using virtualized environments. We can put a large number of small isolated servers, inside a large one and improve a large number of values like the wattage or power consumption, space usage, and resource usage. In this paper, we present a prototype with which we distribute resources between two virtualized servers, one with Tomcat and another with Globus, and both sharing the same host. The prototype is able to maintain the required SLA and QoS using prediction with simulation in real time. Our goal is to demonstrate that simulation can be used to improve resource managers decissions. In this paper, we use those simulations inside a shared server with several different applications using virtualization.

Non-Uniform Cache Architectures (NUCA) have been proposed as a solution to overcome wire delays that will dominate on-chip latencies in Chip Multiprocessor designs in the near future. This novel means of organization divides the total memory area into a set of banks that provides non-uniform access latencies and thus faster access to those banks that are close to the processor. A NUCA model can be characterized according to the four policies that determine its behavior: bank placement, bank access, bank migration and bank replacement. Placement determines the first location of data, access defines the searching algorithm across the banks, migration decides data movements inside the memory and replacement deals with the evicted data. This paper analyzes the performance of several alternatives that can be considered for each of these four policies. Moreover, the Parsec benchmark suite has been used to handle this evaluation because it is a representative group of upcoming sharedmemory programs for Chip Multiprocessors. The results may help researchers to identify key features of NUCA organizations and to open up new areas of investigation.

The fast growth of bioinformatics field has attracted the attention of computer scientists in the last few years. At the same time the increasing database sizes require greater efforts to improve the computational performance. From a computer architecture point of view, we intend to investigate how bioinformatics applications can benefit from future multi-core processors. In this paper we present a preliminary study of the Cell BE processor limitations when executing two representative sequence alignment applications (Ssearch and ClustalW). The inherent large parallelism of the targeted algorithms makes them ideal for architectures supporting multiple dimensions of parallelism (TLP and DLP). However, in the case of Cell BE we identified several architectural limitations that need a careful study and quantification.

Ambient Networks will enable mobile terminals to communicate in an environments populated by several networks, devices, services and artefacts in a transparent way to the final user. In these scenarios, one way of implementing services uses web service architecture. So it is important to study how these mobile devices will integrate efficiently to access web services. Because of the reduced capabilities of the mobile devices, their access to web services is not easy and might have some performance costs related to show data speeds and processing both HTTP commands and XML. Moreover, sOlne mobile devices could not support web service access and if supported it lacks of web service search engine. In order to allow mobile devices to access web services efficiently, giving a solution to the previous problems, we propose a new architecture based on a peer-to-peer with distributed hash tables network, as a gateway between the mobile device and web service. This architecture is a base software simulator for an Anlbient Network environnlent developed in our research group. Nodes of the peer-topeer network publish services, allow finding them easily and acting as a gateway to the mobile devices for accessing web services more efficiently.

Parallel programming on SMP and multi-core architectures is hard. In this paper we present a programming model for those environments based on automatic function level parallelism that strives to be easy, flexible, portable, and performant. Its main trait is its ability to exploit task level parallelism by analyzing task dependencies at run time. We present the programming environment in the context of algorithms from several domains and pinpoint its benefits compared to other approaches. We discuss its execution model and its scheduler. Finally we analyze its performance and demonstrate that it offers reasonable performance without tuning, and that it can rival highly tuned libraries with minimal tuning effort.

En aquesta tesi s'han realitzat una sèrie d'experiments per tal de cercar, identificar, caracteritzar i comparar diversos mètodes d'obtenció de vistes d'objectes reals per aplicacions interactives de realitat augmentada, telepresència o altres que puguin idear-se en el futur. Durant el desenvolupament dels mètodes trobats, de naturalesa diversa, han sorgit dificultats que han fet aprofundir aquest treball en l'àmbit de la geometria de la síntesi de vistes, la reconstrucció de l'estructura tridimensional dels objectes, l'acceleració de certs algoritmes amb l'ajut del maquinari existent o la portabilitat de les dades a través de la xarxa.Concretament, s'han identificat tres mètodes que poden satisfer els requeriments plantejats. El primer, accés a vistes d'objectes comprimides en fitxers, es basa en l'organització de les dades presentada, la capacitat de compressió dels algoritmes i el suport del maquinari a la tasca de descompressió. El segon mètode, reconstrucció tridimensional i projecció emprant el coprocessador gràfic, aprofita les altes prestacions d'aquests últims, impulsats per les necessitats del mercat. El tercer, selecció d'un conjunt representatiu de vistes i interpolació entre elles, aprofita les propietats de la rectificació de tres vistes i l'exactitud de la interpolació de vistes si es disposa d'un mapa de disparitat prou dens. Aquesta necessitat ha connectat aquest mètode amb el segon, al que cal el model tridimensional reconstruït, ja que hi ha una equivalència entre les dues expressions de la informació. Per la comparació dels resultats dels mètodes estudiats, s'han seguit tres criteris: - El primer, òbviament, el de la qualitat de les vistes obtingudes de l'objecte. Ha calgut identificar les principals fonts d'error en els processos i cercar uns avaluadors d'aquest error. A més d'aquests numèrics se n'han cercat de subjectius ja que el destinatari de les vistes serà un ésser humà. - El temps d'obtenció d'una vista (important per la interactivitat), projectat a les plataformes tecnològiques existents o previsibles.- La mida de les dades necessàries per cadascun dels mètodes, que limitarà la portabilitat de la visualització dels objectes. Durant la realització d'aquesta tesi, s'han realitzat algunes contribucions, la majoria d'elles ja publicades, que es poden resumir en:- Disseny d'una metodologia per la representació d'objectes a partir de conjunts de vistes i mètodes de síntesi. En aquesta metodologia s'ha presentat un protocol per l'adquisició i ordenació de les dades, idees per la selecció del conjunt mínim de vistes, un criteri per gravar la mínima informació necessària, ajuts a l'obtenció de la informació tridimensional de l'escena necessària, i un algoritme ràpid i general de síntesi de vistes.- Supressió de les restriccions geomètriques del mètode de síntesi per rectificació de tres vistes, permetent generalitzar la ubicació de la càmera virtual i optimitzar la distància del pla de reprojecció per maximitzar l'àrea de la vista interpolada.- Especificació de l'algoritme de síntesi de vistes pel mètode de rectificació de tres vistes, de forma que es pugui implementar amb processadors tipus DSP o conjunts d'instruccions específiques dels processadors CISC, per assolir les necessitats de les aplicacions interactives.- Presentació d'un mètode de refinament de models tridimensionals obtinguts per space carving mitjançant estereovisió. El mètode combina dues tècniques conegudes de visió per ordinador obtenint un millor resultat en la reconstrucció tridimensional.- Acceleració del mètode de reconstrucció tridimensional per projecció de vòxels amb la utilització de mapes de distància, estructures en arbre i el coprocessador gràfic present en els computadors personals. Els resultats obtinguts en la tesi s'han adaptat per aplicar-se a un projecte de simulació de situacions de conducció en carreteres amb realitat augmentada, desenvolupat per la UPC i la Universitat de Toronto i un segon de representació remota de vistes d'objectes arqueològics, desenvolupat per la UPC, la UB i un conjunt d'universitats estrangeres. This work shows a set of experiments to identify, characterize and compare several methods for obtaining real object views in interactive applications such as augmented reality, telepresence or other future developments. While developing those methods, the problems found have induced a deeper study of view synthesis geometry, object three-dimensional structure, hardware process acceleration and data portability through the internet. Three methods have been found that meet the ends of this work. First, file-stored object-view access rests in data organization, compression- algorithm capabilities and hardware support to decompression. The second method, 3D object reconstruction and graphic coprocessor based projection, takes advantage of market driven GPU evolution. Finally, the representative view-set selection and interpolation method, uses the three-view-rectification properties and the precision of view interpolation when a dense-enough disparity map is available. This last requirement binds the second and third methods in the need of a good 3D object reconstruction, 3D models and disparity maps being two expressions for the same data. To compare the method results three criteria have been used: - Object view image quality. It has been necessary to identify the main source of errors on the processes and to find some evaluators for those errors. As the results of the process are images to be shown to humans, with those numerical evaluators a subjective evaluator has been used too. - Process time, important for the interactivity aim, calculated with current technology but projected to next foreseeable platforms. - Amount of data that must be recorded in each method, which will be a key point for portability. While developing this work, some contributions have been achieved and they can be summarized as:- Design of a methodology to represent any object view from a reduced set of views and synthesis methods. The methodology includes a protocol to acquire and organize data, ideas for a minimum view set selection, a criterion to record the minimum amount of data, improvements in obtaining the three-dimensional structure of the scene and a fast and general synthesis algorithm.- Suppression of some geometric restrictions in the three-view-rectification method, allowing a more general positioning for the virtual camera and a maximization of the virtual image area through the distance to the reprojection plane.- A complete specification for the modified three-view rectification and view interpolation method allowing its implementation with DSP or MMX instructions to achieve the requirements of interactive applications. - Presentation of a method to refine three-dimensional models obtained by space carving through stereovision. This method combines two well-known computer vision techniques to achieve a better result in 3D reconstruction. - Acceleration of the space carving 3D reconstruction method with the use of an octree voxel organization, projection to special distance maps and taking advantage of the GPU performance to speed-up the projection. Some of the results of this work will be used in the construction of an augmented reality driving simulator (UPC- University of Toronto) and the implementation of a remote viewer of archaeological objects (UPC - UB - other universities).

Ad-hoc On-Demand Distance Vector (AODV) routing protocol has been and continues to be a very active and fruitful research protocol since its introduction in the wireless ad-hoc networks. AODV uses a static value for its route lifetime parameter called Active Route Timeout (ART) which indicates the time that the route can stay active in the routing table. Route lifetime may be more accurately determined dynamically via measurement, instead of static value. To accomplish this, the fuzzy logic system is used to obtain adaptive values for ART depending on the situation of the transmitter and intermediate nodes. To study the effect of various parameters on ART, three design methods for fuzzy ART are proposed here, namely: fuzzy-SKP, fuzzy- Power, and fuzzy-Comb. Analysis shows that the proposed design methods are quite efficient and superior to the conventional design method with respect to routing overhead (25%) and average end-to-end delay (41%). Hence, the proposed fuzzy system is able to optimize ART efficiently.

The use of evolutionary algorithms has been proposed as a powerful random search strategy to solve the join order problem. Specifically, genetic programming used in query optimization has been proposed as an alternative to the limitations of dynamic programming with large join queries. However, very little is known about the impact and behavior of the genetic operations used in this type of algorithms. In this paper, we present an analysis that helps us to understand the effect of these operations during the optimization execution. Specifically, we study five different aspects: the age of the members in the population in terms of generations, the number of query execution plans (QEP) discarded without producing new offsprings, the average QEP life time in generations, the efficiency of the genetic operations and the evolution of the best cost. All in all, our analysis allows us to understand the impact of crossovers compared to mutation operations and the dynamically changing effects of these operations.

Una forma habitual de secuenciar de modo dinámico los trabajos en los sistemas de fabricación es mediante el empleo de reglas de secuenciación. Sin embargo, el problema que presenta este método es que el comportamiento del sistema de fabricación dependerá de su estado, y no existe una regla que supere a las demás en todos los posibles estados que puede presentar el sistema de fabricación. Por lo tanto, sería interesante usar en cada momento la regla más adecuada. Para lograr este objetivo, se pueden utilizar sistemas de secuenciación que emplean aprendizaje automático que permiten, analizando el comportamiento previo del sistema de fabricación (ejemplos de entrenamiento), obtener el conocimiento necesario para determinar la regla de secuenciación más apropiada en cada instante. En el presente trabajo se realiza una revisión de los principales sistemas de secuenciación existentes en la literatura que utilizan aprendizaje automático para variar de forma dinámica la regla de secuenciación empleada en cada momento.

In this paper, we show that the multicast problem in trees can be expressed in term of arranging rows and columns of boolean matrices. Given a $p \times q$ matrix $M$ with 0-1 entries, the {\em shadow} of $M$ is defined as a boolean vector $x$ of $q$ entries such that $x_i=0$ if and only if there is no 1-entry in the $i$th column of $M$, and $x_i=1$ otherwise. (The shadow $x$ can also be seen as the binary expression of the integer $x=\sum_{i=1}^{q}x_i 2^{q-i}$. Similarly, every row of $M$ can be seen as the binary expression of an integer.) According to this formalism, the key for solving a multicast problem in trees is shown to be the following. Given a $p \times q$ matrix $M$ with 0-1 entries, finding a matrix $M^*$ such that: 1- $M^*$ has at most one 1-entry per column; 2- every row $r$ of $M^*$ (viewed as the binary expression of an integer) is larger than the corresponding row $r$ of $M$, $1 \leq r \leq p$; and 3- the shadow of $M^*$ (viewed as an integer) is minimum. We show that there is an $O(q(p+q))$ algorithm that returns $M^*$ for any $p \times q$ boolean matrix $M$. The application of this result is the following: Given a {\em directed} tree $T$ whose arcs are oriented from the root toward the leaves, and a subset of nodes $D$, there exists a polynomial-time algorithm that computes an optimal multicast protocol from the root to all nodes of $D$ in the all-port line model.

Rule-Driven processing has been proved as a way of achieving high speed in fuzzy hardware. Up to now, rule-driven architectures were designed to work with minimum or product as T-norm. This paper proposes two new rule-driven models designed for any T-norm (programmable T-norm) and any kind of membership function. The first one gives a valid theory for rule-driven processing with programmable T-norm and stablishes the background for the second model. The second model has been designed taking into account its implementation characteristics and for normalized membership functions with an overlap factor of two. The architecture proposed can be implemented either by hardware or software.

This paper describes a pedagogic computer named \M aquina Rudimentaria". This computer has been de- signed to be used in a rst course on logic design or com- puter architecture; orthogonality and simplicity have been the major goals. The description of the computer includes the de nition of both the machine and the assembly lan- guage, the implementation of the datapath and the opti- mization of the control unit. A programming framework has been designed to allow the development of small pro- grams in assembly language, their compilation and detailed simulation on the proposed architecture.

A computational model for a fuzzy coprocessor (types and structures of data and the set of instructions) is proposed. The coprocessor will be charged only of the typical operations of fuzzy logic as calculating membership degrees, unions and intersectíons of fuzzy sets, fuzzy inferences, defuzzifications and so on. One main novelty is that the programming language admits fuzzy rules conditions in which there would be linguistic edges preceding the predicates and the coprocessor is designed to deal with them directly. In order to that, the compiler codifies as the predicates as the edges into the instructions. Using this coprocessor the number of linguistic values of the variables and the number of rules can be reduced and the executions of systems based on fuzzy rules will be speeded up.

Diversos autores han propuesto técnicas para la especificación de protocolos de comunicación. En este artículo se consideran los trabajos más significativos realizados hasta la fecha en este campo. Se presentan primeramente las técnicas que basan la especificación del protocolo en alguna forma del modelo de estados y que emplean el análisis de la alcanzabilidad de la máquina resultante para la verificación. A continuación se discuten los métodos que utilizan lenguajes formales y de alto nivel para la descripción del protocolo y aserciones para el estudio de sus propiedades. Por último se consideran las técnicas más recientes orientadas a la automatización parcial o total del diseño de protocolos. La presentación en forma comparada y crítica de los diversos métodos permite perfilar las características que deberían satisfacer toda técnica de diseño de protocolos que se compara favorablemente con las ya existentes. Several authors have put forward techniques for the specification and verification of communication protocols. In this paper the most relevant presentations to date in this field are considered. The techniques that base the protocol specification upon some form of the state model and that use some sort of reachability analysis of the resulting machine for verification purposes are first presented. Methods that use formal and high level languages for protocol description and assertions for the study of their proprieties, are then discussed. And finally the more recent techniques orientated towards the partial or total protocol design automation are considered. A comparative and critical exposure of the different methods enables one to pin down the characteristics that ought to be satisfied by the techniques of communication protocol design. In a forthcomming paper the basic principles of a new method of protocol design, which compares favorably with existing techniques, will be developed.

With the development of software tools to ease translator and compiler programming procedures as main motivation, the present article deals with a specific high level language (FORTRAN) coded translator structure. The translator design is suited for automatic generation from its TBNF, a modification of BNF, metalanguage description. Both formal language definition and translator design techniques are revised as a preparation, "its corresponding automatic generation techniques are mentioned as well. The BASIC, which has been developped at CCUPB, serves as example for the translator structure description. An outline of both, the listing and runtime BASIC machines is algo included. The BASICCCUPB forros part of the translator construction methods line of research followed at CCUPB. The article includes references relevant to the concepts involved. Amb la motivació de construir eines que facilitin la programació de traductors i de compiladors, el present article versa sobre l'estructura d'un traductor codificat en un llenguatge d'alt nivell (FORTRAN). L'estructura d'aquest traductor està preparada per a ésser generada automàticament partint d'un llenguatge d'alt nivell basat en el meta-llenguatge TBNF, versió modificada de la BNF. Com a preparació es revisa la definició formal de llenguatges i les diverses tècniques de traductors, esmentant els mètodes de generació automàtica de traductors que es corresponen amb les tècniques de traductors existents. L'exemple del BASIC construit al CCUPB ens serveix per a descriure l'estructura dels traductors. S'inclou també les descripcions de les màquines ideals BASIC executora i llistadora. El BASIC-CCUPB forma part de la línia d'investigació de mètodes de construcció de traductors que es porta a terme al CCUPB. L'article conté també referències rel.levants als conceptes presentats.

En este trabajo se presentan dos aspectos de una metodología nueva de diseño de protocolos, concretamente, los referentes a la especificación y validación de la estructura lógica de protocolos de comunicación. Para especificar el funcionamiento de los elementos integrantes de los protocolos se crea un lenguaje descriptivo de alto nivel, el LDP. Las descripciones de protocolos en LDP son el puntode partida de los algoritmos de validación que se proponen. La validación se basa en la construcción de un árbol que expresa todos los posibles caminos de ejecución del protocolo y permite detectar errores en su estructura lógica tales como bloqueos, bloqueos temporales, comportamiento cíclico, etc. In this work two aspects of a new methodology for designing communication protocols are presented. They are those related with the specification and the validation of the logical structure of protocols. A high level descriptive language, LDP, is introduced for specification purposes. The LDP descriptions constitute the starting point for the proposed validation algorithms. The validation is based in the generation of a tree reflecting all the execution paths of the protocol and it permits to detect errors in its logical structure such as deadlocks, tempo-blocking, cyclic behaviour and so on.

Aquest article tracta de les precedències entre conjunts d'informació i, especialment, del problema de l'anàlisi de la derivabilitat de conjunts d'informació, del qual pretén d'explorar-ne noves vies de solució. L'enfocament del treball consisteix en partir de l'esquema de les informacions del sistema, on hi constin totes les informacions que puguin existir. En base a aquest esquema, es poden definir tots els conjunts d'informació que interessin. Llavors l'anàlisi de la derivabilitat el plantegem com un procediment que rep la definició dels conjunts d'informació d'entrada i sortida del sistema i l'esquema corresponent, i que ens dóna com a resultat si les sortides són o no derivables. Creiem que el mètode que proposem és, alhora, potent i simple, tot i que és necessari continuar la recerca vers uns eixos que també apuntem. En particular, hi ha l'adaptació al model relacional i l'aplicació a la resolució d'altres problemes. This paper deals with precedences among information sets and mainly with the problem of the information set derivability analysis, for which some new solution procedures are explored. The approach in this contribution starts from the scheme of system informations, in which all possible existing informations are present. On the basis of this scheme any relevant information set can be defined, whereupon the derivability analysis can be considered as a procedure that, from the system input and output information sets' definition and the corresponding scheme, finds out as result whether the outputs are or are not derivable. It is thought that the method described is powerful yet simple although, as it is also pointed out, research must still be pursued along some lines, particulary on the adaptation to the relational model, and on its application to the solution of other problems.

A dynamic memory is a storage medium constituted by an array of cells and an interconnection network between them. It is characterized by the constant circulation of the stored data. The concern is to design the interconnection network in order to have small access times and a simple control of the memory. Several interconnection schemes have been proosed in the literature. This paper presents a quite general model for such structures that greatly facilitates both the design and the control of the memory. It is shown that most known proposals of dynamic memory interconnection networks are particular instances of the model and that it leads to some new ones. A quite general model for dynamic memory networks is proposed that greatly facilitates both the design and the control of the memory. It is shown that most known proposals of dynamic memory interconnection networks are particular instances of the model and that it leads to some novel networks. The discussion covers Cayley diagrams, de Bruijn digraphs, the memory of A.V. Aho and J.D. Ullman (1974), odd-sized memories, J. Lenfant's memories (1977), an optimal-size memory, and vectorial dynamic memories

This paper presents the architecture of the Phosphorus Grid-enabled GMPLS (G2MPLS) Network Control Plane that implements the concept of Grid Network Services provisioning through a set of seamlessly integrated procedures.

The growing influence of wire delay in cache design has meant that access latencies to last-level cache banks are no longer constant. Non-Uniform Cache Architectures (NUCAs)have been proposed to address this problem. Furthermore, an efficient last-level cache is crucial in chip multiprocessors (CMP) architectures to reduce requests to the offchip memory, because of the significant speed gap between processor and memory and the limited memory bandwidth. Therefore, a bank replacement policy that efficiently manages the NUCA cache is desirable. However, the decentralized nature of NUCA has prevented previously proposed replacement policies from being effective in this kind of caches. As banks operate independently of each other, their replacement decisions are restricted to a single NUCA bank. We propose a novel mechanism based on the bank replacement policy for NUCA caches on CMP, called The Auction. This mechanism enables the replacement decisions taken in a single bank to be spread to the whole NUCA cache. Thus, global replacement policies that rely on the current state of the NUCA cache, such as evicting the least frequently accessed data in the whole NUCA cache, are now feasible. Moreover, The Auction adapts to current program behaviour in order to relocate a line that is being evicted from a bank in the NUCA cache to the most suitable position in the whole cache. We propose, implement and evaluate three approaches of The Auction mechanism.We also show that The Auction manages the cache efficiently and significantly reduces the requests to the off-chip memory by increasing the hit ratio in the NUCA cache. This translates into an average IPC improvement of 8%, and reduces energy consumed by the memory system by 4%.

The emergence of hardware accelerators, such as graphics processing units (GPUs), has challenged the interaction between processing elements (PEs) and main memory. In architectures like the Cell/B.E. or GPUs, the PEs incorporate local memories which are fed with data transferred from memory using direct memory accesses (DMAs). We expect that chip multiprocessors (CMP) with DMA-managed local memories will become more popular in the near future due to the increasing interest in accelerators. In this work we show that, in that case, the way cache hierarchies are conceived should be revised. Particularly for last-level caches, the norm today is to use latency-aware organizations. For instance, in dynamic nonuniform cache architectures (D-NUCA) data is migrated closer to the requester processor to optimize latency. However, in DMA-based scenarios, the memory system latency becomes irrelevant compared with the time consumed for moving the DMA data, so latency-aware designs are, a priori, inefficient. In this work, we revisit the last-level cache designs in DMA-based CMP architectures with master-worker execution. Two scenarios are evaluated. First, we consider a set of private caches with data replication across them, where coherency of the copies is ensured through a hardware protocol. In this scenario, a PE has a nearby copy of the datum, improving cache access latency. Second, we consider a partitioned cache, where the allocation of a datum to a cache block is determined based on its physical address. In this scenario, there are no copies of data, and access to a datum has a variable latency. In contrast with traditional load/store-based architectures, we found that the partitioned last-level cache scheme outperforms the cache with data replication for DMA-based scenarios.

—Parallel file systems are very sensitive to adverse conditions, and the lack of synergy between such file systems and some of the applications running on them has a negative impact on the overall system performance. Our observations indicate that the increased pressure on metadata management is one of the relevant causes of performance drops. This paper proposes a virtualization layer above the native file system that, transparently to the user, reorganizes the underlying directory tree, mitigating bottlenecks by taking advantage of the native file system optimizations and limiting the effects of potentially harmful application behavior. We developed COFS (COmposite File System) as a proof-of-concept virtual layer to evaluate the feasibility of the proposal.

Partial Differential Equations (PDE) are the heart of most simulations in many scientific fields, from Fluid Mechanics to Astrophysics. One the most popular mathematical schemes to solve a PDE is Finite Difference (FD). In this work we map a PDE-FD algorithm called Reverse Time Migration to a GPU using CUDA. This seismic imaging (Geophysics) algorithm is widely used in the oil industry. GPUs are natural contenders in the aftermath of the clock race, in particular for High-performance Computing (HPC). Due to GPU characteristics, the parallelism paradigm shifts from the classical threads plus SIMD to Single Program Multiple Data (SPMD). The NVIDIA GTX 280 implementation outperforms homogeneous CPUs up to 9x (Intel Harpertown E5420) and up to 14x (IBM PPC 970). These preliminary results confirm that GPUs are a real option for HPC, from performance to programmability.

We have developed a new kind of simulator based in queue models and statistical methods. It allows a fast and accurate simulation. It is really useful to perform a really fast design space exploration. We have validated the model against a real chip, Intel Ivy Bridge Processor

HPC machines are introducing more and more heterogeneity in their architecture on the road to exascale systems. The increasing complexity of the machines due to the variety of hardware architectures and accelerators makes efficient programming a task harder than ever. Heterogeneous parallel programming models, such as OmpSs@FPGA, help the programmer handle the most unfriendly parts of working with accelerators. This master thesis analyzes the OmpSs@FPGA communication system and proposes a set of techniques to overcome the problems related to it and potentially improve the performance of the applications. The results show that the techniques proposed speed up the applications under certain conditions and, most importantly, solves some of the limitations that had the previous communication system. In particular, the new techniques specially improve the explotation of fine-grain parallelism and open the door to explore new possibilities with regard to data communication and re-use. Moreover, a tool (autoVivado) that automatically manages the process of bitstream generation, from the synthesis of the HLS code to the generation of the device-tree, has been developed as part of this master thesis. autoVivado has been fully integrated with the OmpSs@FPGA compiler infrastructure, providing the programmers a way to transparently generate parallel heterogenous programs and bitstreams from OmpSs applications that use FPGA accelerators.

Article dans revue scientifique avec comité de lecture.; This paper is devoted to the gossip (or all-to-all) problem in the chordal ring under the one-port line model. The line model assumes long distance calls between non neighboring processors. In this sense, the line model is strongly related to circuit-switched networks, wormhole routing, optical networks supporting wavelength division multiplexing, ATM switching, and networks supporting connected mode routing protocols. Since the chordal rings are competitors of networks as meshes or tori because of theirs short diameter and bounded degree, it is of interest to ask whether they can support intensive communications (typically all-to-all) as eÆciently as these networks. We propose polynomial algorithms to derive optimal or near optimal gossip protocols in the chordal ring.

Cloud users want to express their requirements in terms of high-level metrics (e.g. in terms of execution time, not in terms of CPU MHz). Moreover, at the submission time they would like to know if the resource provider will ful l with their requirements in order to decide if they would rather prefer another provider. On the other hand, the resource provider have to translate these high-level metrics into hard- ware related metrics, to know if he have enough resources to execute the user's requests. In this context, we present our prediction system to foresee the amount of CPU required for a job to nish before its deadline. This prediction system uses machine learning techniques to learn about the jobs and on-line adjust itself. Before all this training is done, the Prediction System uses an analytical model for this purpose. We also contribute with a deadline-based scheduler which uses these predictions to discard jobs that will not meet its deadline in order to maximize the provider's revenue by means of a dynamic and effi cient resource allocation to jobs. We show how our system is able to provide higher revenue to resource providers compared to simple yet well known schedulers like EDF, SJF, etc.