Quality-aware management of data streams is gaining more and more importance with the amount of data produced by streams growing continuously. The resources required for data stream processing depend on different factors and are limited by the environment of the data stream management system (DSMS). Thus, with a potentially unbounded amount of stream data and limited processing resources, some of the data stream processing tasks (originating from different users) may not be satisfyingly answered, and therefore, users should be enabled to negotiate a certain quality for the execution of their stream processing tasks. After the negotiation process, it is the responsibility of the Data Stream Management System to meet the quality constraints by using adequate resource reservation and scheduling techniques. Within this paper, we consider different aspects of real-time scheduling for operations within a DSMS. We propose a scheduling concept which enables us to meet certain time-dependent quality of service requirements for user-given processing tasks. Furthermore, we describe the implementation of our scheduling concept within a real-time capable data stream management system, and we give experimental results on that.

This dissertation entitled ’Model-Based Exploration of Parallelism in the Context of Automotive Multi-Core Systems’ deals with the analytical investigation of different temporal relationships for automotive multi-processor systems subject to critical, embedded, real-time, distributed, and heterogeneous domain requirements. Vehicle innovation increasingly demands high-performance platforms in terms of, e.g., highly assisted or autonomous driving such that established software development processes must be examined, revised, and advanced. The goal is not to develop application software itself, but instead to improve the model-based development process, subject to numerous constraints and requirements. Model-based software development is, for example, an established process that allows systems to be analyzed and simulated in an abstracted, standardized, modular, isolated, or integrated manner. The verification of real-time behavior taking into account various constraints and modern architectures, which include graphics and heterogeneous processors as well as dedicated hardware accelerators, is one of many challenges in the real-time and automotive community. The software distribution across hardware entities and the identification of software that can be executed in parallel are crucial in the development process. Since these processes usually optimize one or more properties, they belong to the category of problems that can only be solved in polynomial time using non-deterministic methods and thus make use of (meta) heuristics for being solved. Such (meta) heuristics require sophisticated implementation and configuration, due to the properties to be optimized are usually subject to many different analyses. With the results of this dissertation, various development processes can be adjusted to modern architectures by using new and extended processes that enable future and computationally intensive vehicle applications on the one hand and improve existing processes in terms of efficiency and effectiveness on the other hand. These processes include runnable partitioning, task mapping, data allocation, and timing verification, which are addressed with the help of constraint programming, genetic algorithms, and heuristics.

The estimation of the worst-case execution time (WCET) of a task is a problem that concerns the field of embedded systems and, especially, real-time systems. Estimating a safe WCET for single-core architectures without speculative mechanisms is a challenging task and an active research topic. However, the advent of advanced hardware mechanisms, which often lack predictability, complicates the current WCET analysis methods. The field of Embedded Systems has high safety considerations and is, therefore, conservative with speculative mechanisms. However, nowadays, even safety-critical applications move to the direction of multiprocessor systems. In a multiprocessor system, each task that runs on a processing unit might affect the execution time of the tasks running on different processing units. In shared-memory symmetric multiprocessor systems, this interference occurs through the shared memory and the common bus. The presence of private caches introduces cachecoherence issues that result in further dependencies between the tasks. The purpose of this thesis is twofold: (1) to evaluate the feasibility of an existing one-pass WCET analysis method with an integrated cache analysis and (2) to design and implement a cachebased multiprocessor WCET analysis by extending the singlecore method. The single-core analysis is part of the KTH’s Timing Analysis (KTA) tool. The WCET analysis of KTA uses Abstract Search-based WCET Analysis, an one-pass technique that is based on abstract interpretation. The evaluation of the feasibility of this analysis includes the integration of microarchitecture features, such as cache and pipeline, into KTA. These features are necessary for extending the analysis for hardware models of modern embedded systems. The multiprocessor analysis of this work uses the single-core analysis in two stages to estimate the WCET of a task running under the presence of temporally and spatially interfering tasks. The first phase records the memory accesses of all the temporally interfering tasks, and the second phase uses this information to perform the multiprocessor WCET analysis. The multiprocessor analysis assumes the presence of private caches and a shared communication bus and implements the MESI protocol to maintain cache coherence. / Uppskattning av längsta exekveringstid (eng. worst-case execution time eller WCET) är ett problem som angår inbyggda system och i synnerhet realtidssystem. Att uppskatta en säker WCET för enkelkärniga system utan spekulativa mekanismer är en utmanande uppgift och ett aktuellt forskningsämne. Tillkomsten av avancerade hårdvarumekanismer, som ofta saknar förutsägbarhet, komplicerar ytterligare de nuvarande analysmetoderna för WCET. Inom fältet för inbyggda system ställs höga säkerhetskrav. Således antas en konservativ inställning till nya spekulativa mekanismer. Trotts detta går säkerhetskritiska system mer och mer i riktning mot multiprocessorsystem. I multiprocessorsystem påverkas en process som exekveras på en processorenhet av processer som exekveras på andra processorenheter. I symmetriska multiprocessorsystem med delade minnen påträffas denna interferens i det delade minnet och den gemensamma bussen. Privata minnen introducerar cache-koherens problem som resulterar i ytterligare beroende mellan processerna. Syftet med detta examensarbete är tvåfaldigt: (1) att utvärdera en befintlig analysmetod för WCET efter integrering av en lågnivå analys och (2) att designa och implementera en cache-baserad flerkärnig WCET-analys genom att utvidga denna enkelkärniga metod. Den enkelkärniga metoden är implementerad i KTH’s Timing Analysis (KTA), ett verktyg för tidsanalys. KTA genomför en så-kallad Abstrakt Sök-baserad Metod som är baserad på Abstrakt Interpretation. Utvärderingen av denna analys innefattar integrering av mikroarkitektur mekanismer, såsom cache-minne och pipeline, i KTA. Dessa mekanismer är nödvändiga för att utvidga analysen till att omfatta de hårdvarumodeller som används idag inom fältet för inbyggda system. Den flerkärniga WCET-analysen genomförs i två steg och uppskattar WCET av en process som körs i närvaron av olika tids och rumsligt störande processer. Första steget registrerar minnesåtkomst för alla tids störande processer, medans andra steget använder sig av första stegets information för att utföra den flerkärniga WCET-analysen. Den flerkärniga analysen förutsätter ett system med privata cache-minnen och en gemensamm buss som implementerar MESI protokolen för att upprätthålla cache-koherens.

With the advent of high-density micro-electrodes arrays, developing neural probes satisfying the real-time and stringent power-efficiency requirements becomes more challenging. A smart neural probe is an essential device in future neuroscientific research and medical applications. To realize such devices, we present a 22 nm FDSOI SoC with complex on-chip real-time data processing and training for neural signal analysis. It consists of a digitally-assisted 16-channel analog front-end with 1.52 μ W/Ch, dedicated bio-processing accelerators for spike detection and classification with 2.79 μ W/Ch, and a 125 MHz RISC-V CPU, utilizing adaptive body biasing at 0.5 V with a supporting 1.79 TOPS/W MAC array. The proposed SoC shows a proof-of-concept of how to realize a high-level integration of various on-chip accelerators to satisfy the neural probe requirements for modern applications.

[ES] La constante necesidad de un mayor rendimiento para cumplir con la gran demanda de potencia de cómputo de las nuevas aplicaciones, (ej. sistemas de conducción autónoma), obliga a la industria a apostar por la tecnología basada en Sistemas en Chip con Procesadores Multinúcleo (MPSoCs) en sus sistemas embebidos de seguridad-crítica. Los sistemas MPSoCs generalmente incluyen una red en el chip (NoC) para interconectar los núcleos de procesamiento entre ellos, con la memoria y con el resto de recursos compartidos. Desafortunadamente, el uso de las NoCs dificulta alcanzar la predecibilidad en el tiempo, ya que pueden aparecer conflictos en muchos puntos y de forma distribuida a nivel de red. Para afrontar este problema, en esta tesis se propone un nuevo paradigma de diseño para NoCs de tiempo real donde los conflictos en la red son eliminados por diseño. Este nuevo paradigma parte del Grafo de Dependencia de Canales (CDG) para evitar los conflictos de red de forma determinista. Nuestra solución es capaz de inyectar mensajes de forma natural usando un periodo TDM igual al límite teórico óptimo sin la necesidad de usar un proceso offline exigente computacionalmente. La red se ha integrado en un sistema multinúcleo basado en tiles y adaptado a su jerarquía de memoria. Como segunda contribución principal, proponemos un nuevo planificador dinámico y distribuido capaz de alcanzar un rendimiento pico muy cercanos a las NoC basadas en un diseño wormhole sin comprometer sus garantías de tiempo real. El planificador se basa en nuestro diseño de red para explotar sus propiedades clave. Los resultados de nuestra NoC muestran que nuestro diseño garantiza la predecibilidad en el tiempo evitando interferencias en la red entre múltiples aplicaciones ejecutándose concurrentemente. La red siempre garantiza el rendimiento y también mejora el rendimiento respecto al de las redes wormhole en una red 4 x 4 en un factor de 3,7x cuando se inyecta trafico para generar interferencias. En una red 8 x 8 las diferencias son incluso mayores. Además, la red obtiene un ahorro de área total del 10,79% frente a una implementación básica de una red wormhole. El planificador propuesto alcanza una mejora de rendimiento de 6,9x y 14,4x frente la versión básica de la red DCFNoC para redes en forma de malla de 16 y 64 nodos, respectivamente. Cuando lo comparamos frente a un conmutador estándar wormhole se preserva un rendimiento de red del 95% al mismo tiempo que preserva la estricta predecibilidad en el tiempo. Este logro abre la puerta a nuevos diseños de NoCs de alto rendimiento con predecibilidad en el tiempo. Como contribución final, construimos una taxonomía de NoCs basadas en TDM con propiedades de tiempo real. Con esta taxonomía realizamos un análisis exhaustivo para estudiar y comparar desde tiempos de respuesta, a implementaciones con bajo coste, pasando por soluciones de compromiso para diseños de NoCs de tiempo real. Como resultado, obtenemos nuevos diseños de NoCs basadas en TDM. / [CA] La constant necessitat d'un major rendiment per a complir amb la gran demanda de potència de còmput de les noves aplicacions, (ex. sistemes de conducció autònoma), obliga la indústria a apostar per la tecnologia basada en Sistemes en Xip amb Processadors Multinucli (MPSoCs) en els seus sistemes embeguts de seguretat-crítica. Els sistemes MPSoCs generalment inclouen una xarxa en el xip (NoC) per a interconnectar els nuclis de processament entre ells, amb la memòria i amb la resta de recursos compartits. Desafortunadament, l'ús de les NoCs dificulta aconseguir la predictibilitat en el temps, ja que poden aparéixer conflictes en molts punts i de forma distribuïda a nivell de xarxa. Per a afrontar aquest problema, en aquesta tesi es proposa un nou paradigma de disseny per a NoCs de temps real on els conflictes en la xarxa són eliminats per disseny. Aquest nou paradigma parteix del Graf de Dependència de Canals (CDG) per a evitar els conflictes de xarxa de manera determinista. La nostra solució és capaç d'injectar missatges de mra natural fent ús d'un període TDM igual al límit teòric òptim sense la necessitat de fer ús d'un procés offline exigent computacionalment. La xarxa s'ha integrat en un sistema multinucli basat en tiles i adaptat a la seua jerarquia de memòria. Com a segona contribució principal, proposem un nou planificador dinàmic i distribuït capaç d'aconseguir un rendiment pic molt pròxims a les NoC basades en un disseny wormhole sense comprometre les seues garanties de temps real. El planificador es basa en el nostre disseny de xarxa per a explotar les seues propietats clau. Els resultats de la nostra NoC mostren que el nostre disseny garanteix la predictibilitat en el temps evitant interferències en la xarxa entre múltiples aplicacions executant-se concurrentment. La xarxa sempre garanteix el rendiment i també millora el rendiment respecte al de les xarxes wormhole en una xarxa 4 x 4 en un factor de 3,7x quan s'injecta trafic per a generar interferències. En una xarxa 8 x 8 les diferències són fins i tot majors. A més, la xarxa obté un estalvi d'àrea total del 10,79% front una implementació bàsica d'una xarxa wormhole. El planificador proposat aconsegueix una millora de rendiment de 6,9x i 14,4x front la versió bàsica de la xarxa DCFNoC per a xarxes en forma de malla de 16 i 64 nodes, respectivament. Quan ho comparem amb un commutador estàndard wormhole es preserva un rendiment de xarxa del 95% al mateix temps que preserva la estricta predictibilitat en el temps. Aquest assoliment obri la porta a nous dissenys de NoCs d'alt rendiment amb predictibilitat en el temps. Com a contribució final, construïm una taxonomia de NoCs basades en TDM amb propietats de temps real. Amb aquesta taxonomia realitzem una anàlisi exhaustiu per a estudiar i comparar des de temps de resposta, a implementacions amb baix cost, passant per solucions de compromís per a dissenys de NoCs de temps real. Com a resultat, obtenim nous dissenys de NoCs basades en TDM. / [EN] The ever need for higher performance to cope with the high computational power demands of new applications (e.g autonomous driving systems), forces industry to support technology based on multi-processors system on chip (MPSoCs) in their safety-critical embedded systems. MPSoCs usually include a network-on-chip (NoC) to interconnect the cores between them and, with memory and the rest of shared resources. Unfortunately, the inclusion of NoCs difficults achieving time predictability as network-level conflicts may occur in many points in a distributed manner. To overcome this problem, this thesis proposes a new time-predictable NoC design paradigm where conflicts within the network are eliminated by design. This new paradigm builds on top of the Channel Dependency Graph (CDG) in order to deterministically avoid network conflicts. Our solution is able to naturally inject messages using a TDM period equal to the optimal theoretical bound without the need of using a computationally demanding offline process. The network is integrated in a tile-based manycore system and adapted to its memory hierarchy. As a second main contribution, we propose a novel distributed dynamic scheduler that is able to achieve peak performance close to a wormhole-based NoC design without compromising its real-time guarantees. The scheduler builds on top of our NoC design to exploit its key properties. The results of our NoC show that our design guarantees time predictability avoiding network interference among multiple running applications. The network always guarantees performance and also improves wormhole performance in a 4 x 4 setting by a factor of 3.7x when interference traffic is injected. For a 8 x 8 network differences are even larger. In addition, the network obtains a total area saving of 10.79% over a standard wormhole implementation. The proposed scheduler achieves an overall throughput improvement of 6.9x and 14.4x over a baseline conflict-free NoC for 16 and 64-node meshes, respectively. When compared against a standard wormhole router 95% of its network throughput is preserved while strict timing predictability is kept. This achievement opens the door to new high performance time predictable NoC designs. As a final contribution, we build a taxonomy of TDM-based NoCs with real-time properties. With this taxonomy we perform a comprehensive analysis to study and compare from response time specific, to low resource implementation cost, through trade-off solutions for real-time NoCs designs. As a result, we derive new TDM-based NoC designs. / Picornell Sanjuan, T. (2021). Conflict-Free Networks on Chip for Real Time Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/177347

[ES] La presente tesis doctoral propone la arquitectura de un sistema de Geo-visualización Espaciotemporal de actividad delictiva y criminal, para ser aplicada a Sistemas de Comando y Control (C2S) específicamente dentro de sus Sistemas de Información de Comando y Control (C2IS). El sistema de Geo-visualización Espaciotemporal se basa en el análisis masivo de datos reales de actividad delictiva, proporcionado por la Policía Nacional Colombiana (PONAL) y está compuesto por dos aplicaciones diferentes: la primera permite al usuario geo-visualizar espaciotemporalmente de forma dinámica, las concentraciones, tendencias y patrones de movilidad de esta actividad dentro de la extensión de área geográfica y el rango de fechas y horas que se precise, lo cual permite al usuario realizar análisis e interpretaciones y tomar decisiones estratégicas de acción más acertadas; la segunda aplicación permite al usuario geo-visualizar espaciotemporalmente las predicciones de la actividad delictiva en periodos continuos y cortos a modo de tiempo real, esto también dentro de la extensión de área geográfica y el rango de fechas y horas de elección del usuario. Para estas predicciones se usaron técnicas clásicas y técnicas de Machine Learning (incluido el Deep Learning), adecuadas para el pronóstico en multiparalelo de varios pasos de series temporales multivariantes con datos escasos. Las dos aplicaciones del sistema, cuyo desarrollo se muestra en esta tesis, están realizadas con métodos novedosos que permitieron lograr estos objetivos de efectividad a la hora de detectar el volumen y los patrones y tendencias en el desplazamiento de dicha actividad, mejorando así la conciencia situacional, la proyección futura y la agilidad y eficiencia en los procesos de toma de decisiones, particularmente en la gestión de los recursos destinados a la disuasión, prevención y control del delito, lo cual contribuye a los objetivos de ciudad segura y por consiguiente de ciudad inteligente, dentro de arquitecturas de Sistemas de Comando y Control (C2S) como en el caso de los Centros de Comando y Control de Seguridad Ciudadana de la PONAL. / [CA] Aquesta tesi doctoral proposa l'arquitectura d'un sistema de Geo-visualització Espaitemporal d'activitat delictiva i criminal, per ser aplicada a Sistemes de Comandament i Control (C2S) específicament dins dels seus Sistemes d'informació de Comandament i Control (C2IS). El sistema de Geo-visualització Espaitemporal es basa en l'anàlisi massiva de dades reals d'activitat delictiva, proporcionada per la Policia Nacional Colombiana (PONAL) i està composta per dues aplicacions diferents: la primera permet a l'usuari geo-visualitzar espaitemporalment de forma dinàmica, les concentracions, les tendències i els patrons de mobilitat d'aquesta activitat dins de l'extensió d'àrea geogràfica i el rang de dates i hores que calgui, la qual cosa permet a l'usuari fer anàlisis i interpretacions i prendre decisions estratègiques d'acció més encertades; la segona aplicació permet a l'usuari geovisualitzar espaciotemporalment les prediccions de l'activitat delictiva en períodes continus i curts a mode de temps real, això també dins l'extensió d'àrea geogràfica i el rang de dates i hores d'elecció de l'usuari. Per a aquestes prediccions es van usar tècniques clàssiques i tècniques de Machine Learning (inclòs el Deep Learning), adequades per al pronòstic en multiparal·lel de diversos passos de sèries temporals multivariants amb dades escasses. Les dues aplicacions del sistema, el desenvolupament de les quals es mostra en aquesta tesi, estan realitzades amb mètodes nous que van permetre assolir aquests objectius d'efectivitat a l'hora de detectar el volum i els patrons i les tendències en el desplaçament d'aquesta activitat, millorant així la consciència situacional , la projecció futura i l'agilitat i eficiència en els processos de presa de decisions, particularment en la gestió dels recursos destinats a la dissuasió, prevenció i control del delicte, la qual cosa contribueix als objectius de ciutat segura i per tant de ciutat intel·ligent , dins arquitectures de Sistemes de Comandament i Control (C2S) com en el cas dels Centres de Comandament i Control de Seguretat Ciutadana de la PONAL. / [EN] This doctoral thesis proposes the architecture of a Spatiotemporal Geo-visualization system of criminal activity, to be applied to Command and Control Systems (C2S) specifically within their Command and Control Information Systems (C2IS). The Spatiotemporal Geo-visualization system is based on the massive analysis of real data of criminal activity, provided by the Colombian National Police (PONAL) and is made up of two different applications: the first allows the user to dynamically geo-visualize spatiotemporally, the concentrations, trends and patterns of mobility of this activity within the extension of the geographic area and the range of dates and times that are required, which allows the user to carry out analyses and interpretations and make more accurate strategic action decisions; the second application allows the user to spatially visualize the predictions of criminal activity in continuous and short periods like in real time, this also within the extension of the geographic area and the range of dates and times of the user's choice. For these predictions, classical techniques and Machine Learning techniques (including Deep Learning) were used, suitable for multistep multiparallel forecasting of multivariate time series with sparse data. The two applications of the system, whose development is shown in this thesis, are carried out with innovative methods that allowed achieving these effectiveness objectives when detecting the volume and patterns and trends in the movement of said activity, thus improving situational awareness, the future projection and the agility and efficiency in the decision-making processes, particularly in the management of the resources destined to the dissuasion, prevention and control of crime, which contributes to the objectives of a safe city and therefore of a smart city, within architectures of Command and Control Systems (C2S) as in the case of the Citizen Security Command and Control Centers of the PONAL. / Salcedo González, ML. (2023). Arquitectura de un sistema de geo-visualización espacio-temporal de actividad delictiva, basada en el análisis masivo de datos, aplicada a sistemas de información de comando y control (C2IS) [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/192685