Suchergebnisse

Cache Coherent NUMA (ccNUMA) architectures are a widespread paradigm due to the benefits they provide for scaling core count and memory capacity. Also, the flat memory address space they offer considerably improves programmability. However, ccNUMA architectures require sophisticated and expensive cache coherence protocols to enforce correctness during parallel executions, which trigger a significant amount of on- and off-chip traffic in the system. This paper analyses how coherence traffic may be best constrained in a large, real ccNUMA platform comprising 288 cores through the use of a joint hardware/software approach. For several benchmarks, we study coherence traffic in detail under the influence of an added hierarchical cache layer in the directory protocol combined with runtime managed NUMA-aware scheduling and data allocation techniques to make most efficient use of the added hardware. The effectiveness of this joint approach is demonstrated by speedups of 3.14× to 9.97× and coherence traffic reductions of up to 99% in comparison to NUMA-oblivious scheduling and data allocation. ; This work has been supported by the Spanish Government (Severo Ochoa grants SEV2015-0493), by the Spanish Ministry of Science and Innovation (contracts TIN2015-65316-P), by the Generalitat de Catalunya (contracts 2014-SGR-1051 and 2014-SGR-1272), by the RoMoL ERC Advanced Grant (GA 321253) and the European HiPEAC Network of Excellence. The Mont-Blanc project receives funding from the EU's H2020 Framework Programme (H2020/2014-2020) under grant agreement no 671697. M. Moretó has been partially supported by the Ministry of Economy and Competitiveness under Juan de la Cierva postdoctoral fellowship number JCI-2012-15047. M. Casas is supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the Cofund programme of the Marie Curie Actions of the 7th R&D Framework Programme of the European Union (Contract 2013 BP B 00243). ; Peer Reviewed ; Postprint (author's final draft)

Cache Coherent NUMA (ccNUMA) architectures are a widespread paradigm due to the benefits they provide for scaling core count and memory capacity. Also, the flat memory address space they offer considerably improves programmability. However, ccNUMA architectures require sophisticated and expensive cache coherence protocols to enforce correctness during parallel executions, which trigger a significant amount of on- and off-chip traffic in the system. This paper analyses how coherence traffic may be best constrained in a large, real ccNUMA platform comprising 288 cores through the use of a joint hardware/software approach. For several benchmarks, we study coherence traffic in detail under the influence of an added hierarchical cache layer in the directory protocol combined with runtime managed NUMA-aware scheduling and data allocation techniques to make most efficient use of the added hardware. The effectiveness of this joint approach is demonstrated by speedups of 3.14× to 9.97× and coherence traffic reductions of up to 99% in comparison to NUMA-oblivious scheduling and data allocation. ; This work has been supported by the Spanish Government (Severo Ochoa grants SEV2015-0493), by the Spanish Ministry of Science and Innovation (contracts TIN2015-65316-P), by the Generalitat de Catalunya (contracts 2014-SGR-1051 and 2014-SGR-1272), by the RoMoL ERC Advanced Grant (GA 321253) and the European HiPEAC Network of Excellence. The Mont-Blanc project receives funding from the EU's H2020 Framework Programme (H2020/2014-2020) under grant agreement no 671697. M. Moretó has been partially supported by the Ministry of Economy and Competitiveness under Juan de la Cierva postdoctoral fellowship number JCI-2012-15047. M. Casas is supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the Cofund programme of the Marie Curie Actions of the 7th R&D Framework Programme of the European Union (Contract 2013 BP B 00243). ; Peer Reviewed ; Postprint (author's final draft)

The adoption of complex MPSoCs in critical real-time embedded systems mandates a detailed analysis their architecture to facilitate certification. This analysis is hindered by the lack of a thorough understanding of the MPSoC system due to the unobvious and/or insufficiently documented behavior of some key hardware features. Confidence on those features can only be regained by building specific tests to both, assess whether their behavior matches specifications and unveil their behavior when it is not fully known a priori. In this work, we introduce a systematic approach that constructs this thorough understanding of the MPSoC architecture-- and assess against its specification in processor documentation -- with a focus on the cache coherence protocol in the avionics-relevant NXP T2080 architecture as our use-case. Our approach covers all transitions in the MESI cache coherence protocol, with emphasis on the coherence between DMA and processing cores. We build evidence of their behavior based on available debug support and performance monitors. Our analysis discloses unexpected behavior for coherence-related notifications as well as some hardware monitors. ; This work has been partially supported by the Spanish Ministry of Science and Innovation under grant PID2019-107255GB; the European Union's Horizon 2020 research and innovation programme under grant agreement No. 878752 (MASTECS) and the European Research Council (ERC) grant agreement No. 772773 (SuPerCom); the HiPEAC Network of Excellence; and the Natural Sciences and Engineering Research Council of Canada (NSERC). ; Peer Reviewed ; Postprint (author's final draft)

The arrival of multiprocessor chips rises again some questions about the way of writing programs, which must then include a high degree of parallelism. We tackle this problem via two orthogonal approaches. First, via the work-stealing paradigm, for which we perform a study targeting on the first hand to seek for simple architectural characteristics giving the best performances for an implementation of this paradigm; and on the second hand to show that the overhead compared to a static parallelization is low, while allowing performances improvement thanks to dynamic load balancing. This question is nevertheless especially tackled via the transaction based programming paradigm -- sequence of instructions executing atomically from the other cores' point of view. Supporting this abstraction requires the implementation of a system called TM, often complex, either software or hardware. The study focuses first on the comparison between two hardware TM systems based on different architecture choices (cache coherence protocol), and then on the impact on performances of several conflict resolution policies, in other words the actions to be taken when two or more transactions try to access the same pieces of data. ; L'avènement des puces multicoeurs repose certaines questions quant aux moyens d'écrire les programmes, qui doivent alors intégrer un degré élevé de parallélisme. Nous abordons cette question par l'intermédiaire de deux points de vue orthogonaux. Premièrement via le paradigme du vol de travail, pour lequel nous effectuons une étude visant d'une part à rechercher quelles sont les caractéristiques architecturales simples donnant les meilleures performances pour une implémentation de ce paradigme ; et d'autre part à montrer que le surcout par rapport à une parallélisation statique est faible tout en permettant des gains en performances grâce à l'équilibrage dynamique des charges. Cette question est néanmoins surtout abordée via le paradigme de programmation à base de transactions -- ensemble d'instructions s'exécutant de manière atomique du point de vue des autres coeurs. Supporter cette abstraction nécessite l'implantation d'un système dit TM, souvent complexe, pouvant être logiciel ou matériel. L'étude porte premièrement sur la comparaison de systèmes TM matériels basés sur des choix architecturaux différents (protocole de cohérence de cache), puis sur l'impact d'un point de vue performances de plusieurs politiques de résolution des conflits, autrement dit des actions à prendre quand deux transactions essaient d'accéder simultanément les mêmes données.

Energy efficiency has become the main challenge for high performance computing (HPC). The use of mobile asymmetric multi-core architectures to build future multi-core systems is an approach towards energy savings while keeping high performance. However, it is not known yet whether such systems are ready to handle parallel applications. This paper fills this gap by evaluating emerging parallel applications on an asymmetric multi-core. We make use of the PARSEC benchmark suite and a processor that implements the ARM big.LITTLE architecture. We conclude that these applications are not mature enough to run on such systems, as they suffer from load imbalance. Furthermore, we explore the behaviour of dynamic scheduling solutions on either the Operating System (OS) or the runtime level. Comparing these approaches shows us that the most efficient scheduling takes place in the runtime level, influencing the future research towards such solutions. ; This work has been supported by the Spanish Government (SEV2015-0493), by the Spanish Ministry of Science and Innovation (contracts TIN2015-65316-P), by Generalitat de Catalunya (contracts 2014-SGR-1051 and 2014-SGR-1272), by the RoMoL ERC Advanced Grant (GA 321253) and the European HiPEAC Network of Excellence. The Mont-Blanc project receives funding from the EU's Seventh Framework Programme (FP7/2007-2013) under grant agreement number 610402 and from the EU's H2020 Framework Programme (H2020/2014-2020) under grant agreement number 671697. M. Moretó has been partially supported by the Ministry of Economy and Competitiveness under Juan de la Cierva postdoctoral fellowship number JCI-2012-15047. M. Casas is supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the Cofund programme of the Marie Curie Actions of the 7th R&D Framework Programme of the European Union (Contract 2013 BP B 00243). ; Peer Reviewed ; Postprint (author's final draft)

Energy efficiency has become the main challenge for high performance computing (HPC). The use of mobile asymmetric multi-core architectures to build future multi-core systems is an approach towards energy savings while keeping high performance. However, it is not known yet whether such systems are ready to handle parallel applications. This paper fills this gap by evaluating emerging parallel applications on an asymmetric multi-core. We make use of the PARSEC benchmark suite and a processor that implements the ARM big.LITTLE architecture. We conclude that these applications are not mature enough to run on such systems, as they suffer from load imbalance. Furthermore, we explore the behaviour of dynamic scheduling solutions on either the Operating System (OS) or the runtime level. Comparing these approaches shows us that the most efficient scheduling takes place in the runtime level, influencing the future research towards such solutions. ; This work has been supported by the Spanish Government (SEV2015-0493), by the Spanish Ministry of Science and Innovation (contracts TIN2015-65316-P), by Generalitat de Catalunya (contracts 2014-SGR-1051 and 2014-SGR-1272), by the RoMoL ERC Advanced Grant (GA 321253) and the European HiPEAC Network of Excellence. The Mont-Blanc project receives funding from the EU's Seventh Framework Programme (FP7/2007-2013) under grant agreement number 610402 and from the EU's H2020 Framework Programme (H2020/2014-2020) under grant agreement number 671697. M. Moretó has been partially supported by the Ministry of Economy and Competitiveness under Juan de la Cierva postdoctoral fellowship number JCI-2012-15047. M. Casas is supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the Cofund programme of the Marie Curie Actions of the 7th R&D Framework Programme of the European Union (Contract 2013 BP B 00243). ; Peer Reviewed ; Postprint (author's final draft)

Table of Contents: Proving Hybrid Systems / by Andre Platzer (p.1) -- Formal Verification of Arithmetic Datapaths using Algebraic Geometry and Symbolic Computation / by Priyank Kalla (p.2) -- Reactive Synthesis / by Roderick Bloem (p.3) -- Abductive Inference and Its Applications in Program Analysis, Verification, and Synthesis / by Isil Diling (p.4) -- Democratization of Formal Verification with Collective Intelligence / Ziyad Hanna (p.5) -- Detecting Hardware Trojans: A Tale of Two Techniques / by Sharad Malik (p.6) --The Genesis and Development of Model Checking: Fact vs. Fiction / by Allen Emerson (p.7) -- The FMCAD 2015 Graduate Student Forum / by Georg Weissenbacher (p.8) -- Verification of Cache Coherence Protocols wrt. Trace Filters / by Parosh Aziz Abdulla, Mohamed Faouzi Atig, Zeinab Ganjei, Ahmed Rezine and Yunyun Zhu (p.9) -- Compositional Reasoning Gotchas in Practice / by Chirag Agarwal, Paul Hylander, Yogesh Mahajan, Jonathan Michelson and Vigyan Singhal (p.17) -- Universal Boolean Functional Vectors / by Jesse Bingham (p.25) -- Compositional Safety Verification with Max-SMT / by Marc Brockschmidt, Daniel Larraz, Albert Oliveras, Enric Rodr´ıguez Carbonell and Albert Rubio (p.33) --Formal Verification of Automatic Circuit Transformations for Fault-Tolerance by / Dmitry Burlyaev and Pascal Fradet (p.41) -- An SMT-based Approach to Fair Termination Analysis / by Javier Esparza and Philipp J. Meyer (p.49) -- Compositional Recurrence Analysis / by Azadeh Farzan and Zachary Kincaid (p.57) -- Pushing to the Top / by Arie Gurfinkel and Alexander Ivrii (p.65) -- Skolem Functions for Factored Formulas / by Ajith John, Shetal Shah, Supratik Chakraborty, Ashutosh Trivedi and S. Akshay (p.73) -- Theory-Aided Model Checking of Concurrent Transition Systems / by Guy Katz, Clark Barrett and David Harel (p.81) -- Compositional Verification of Procedural Programs using Horn Clauses over Integers and Arrays / by Anvesh Komuravelli, Nikolaj Bjorner, Arie Gurfinkel and Kenneth McMillan (p.89) -- IC3 Software Model Checking on Control Flow Automata / by Tim Lange, Martin R. Neuhaußer and Thomas Noll (p.97) -- Accelerating Invariant Generation / by Kumar Madhukar, Bjorn Wachter, Daniel Kroening, Matt Lewis and Mandayam Srivas (p.105) -- Comparing Different Functional Allocations in Automated Air Traffic Control Design / by Cristian Mattarei, Alessandro Cimatti, Marco Gario, Stefano Tonetta and Kristin Y. Rozier (p.112) -- Pattern-based Synthesis of Synchronization for the C++ Memory Model / by Yuri Meshman, Noam Rinetzky and Eran Yahav (p.120) -- Better Lemmas with Lambda Extraction / by Mathias Preiner, Aina Niemetz and Armin Biere (p.128) -- CAQE: A Certifying QBF Solve / by Markus N. Rabe and Leander Tentrup (p.136) -- Difference Constraints: An adequate Abstraction for Complexity Analysis of Imperative Programs. / by Moritz Sinn, Florian Zuleger and Helmut Veith (p. 144) -- Reverse Engineering with Simulation Graphs / by Mathias Soeken, Baruch Sterin, Rolf Drechsler and Robert Brayton (p.152) -- Template-based Synthesis of Instruction-Level Abstractions for SoC Verification / by Pramod Subramanyan, Yakir Vizel, Sayak Ray and Sharad Malik (p.160) -- Transaction Flows and Executable Models: Formalization and Analysis of Message passing Protocols / by Murali Talupur, Sandip Ray and John Erickson (p.168) ; Computer Sciences

Network-on-Chip (NoC) is emerging as a critical shared architecture for CMPs (Chip Multi-/Many-Core Processors) running parallel and concurrent applications. As the core count scales up and the transistor size shrinks, how to optimize power and performance for NoC open new research challenges. As it can potentially consume 20--40\% of the entire chip power, NoC power efficiency has emerged as one of the main design constraints in today's and future high performance CMPs. For NoC power management, we propose a novel on-chip DVFS technique that is able to adjust per-region NoC V/F according to voted V/F levels from communicating threads. A thread periodically votes for a preferred NoC V/F level that best suits its individual performance interests. The final DVFS decision of each region is adjusted by a region DVFS controller democratically based on the majority of votes it receives. Mutually exclusive locks are pervasive shared memory synchronization primitives. In advanced locks such as the Linux queue spinlock comprising a low-overhead spinning phase and a high-overhead sleeping phase, we show that the lock primitive may create very high competition overhead (COH), which is the time threads compete with each other for the next critical section grant. For performance enhancement, we propose a software-hardware cooperative mechanism that can opportunistically maximize the chance of a thread winning critical section in the low-overhead spinning phase and minimize the chance of winning critical section in the high-overhead sleeping phase, so that COH is significantly reduced. Besides, we further observe that the cache invalidation-acknowledgement round-trip delay between the home node storing the critical section lock and the cores running competing locks can heavily downgrade application performance. To reduce such high lock coherence overhead (LCO), we propose in-network packet generation (iNPG) to turn passive ``normal'' NoC routers into active ``big'' ones that can not only transmit but also generate packets to ...

5G is envisioned to tackle, in addition to a considerable increase in traffic volume, the task of connecting billions of devices with heterogeneous service requirements. In order to address the challenges of 5G, we advocate a more efficient use of the available information, with more service and user awareness, and an expansion of the RAN intelligence. In particular, we focus on two key enablers of 5G, namely massive MIMO and proactive caching. In the third chapter, we focus on addressing the bottleneck of CSI acquisition in TDD Massive MIMO. In order to do so, we propose novel spatial grouping schemes such that, in each group, maximum coverage of the signal's spatial basis with minimum overlapping between user spatial signatures is achieved. The latter enables to increase connection density while improving spectral efficiency. TDD Massive MIMO is also the focus of the fourth chapter. Therein, based on the different rates of wireless channels aging, CSI estimation periodicity is exploited as an additional DoF. We do so by proposing a dynamic adaptation of the TDD frame based on the heterogeneous channels coherence times. The Massive MIMO BSs are enabled to learn the best uplink training policy for long periods. Since channel changes result primarily from device mobility, location awareness is also included in the learning process. The resulting planning problem was modeled as a two-time scale POMDP and efficient low complexity algorithms were provided to solve it. The fifth chapter focuses on proactive caching. We focus on improving the energy efficiency of cache-enabled networks by exploiting the correlation in traffic patterns in addition to the spatial repartition of requests. We propose a framework that strikes the optimal trade-off between complexity and truthfulness in user behavior modeling through adaptive content popularity-based clustering. It also simplifies the problem of content placement, which results in a rapidly adaptable and energy efficient content allocation framework. ; 5G est prévu pour s'attaquer, en plus d'une augmentation considérable du volume de trafic, la tâche de connecter des milliards d'appareils avec des exigences de service hétérogènes. Afin de relever les défis de la 5G, nous préconisons une utilisation plus efficace des informations disponibles, avec plus de sensibilisation par rapport aux services et aux utilisateurs, et une expansion de l'intelligence du RAN. En particulier, nous nous concentrons sur deux activateurs clés de la 5G, à savoir le MIMO massif et la mise en cache proactive. Dans le troisième chapitre, nous nous concentrons sur la problématique de l'acquisition de CSI dans MIMO massif en TDD. Pour ce faire, nous proposons de nouveaux schémas de regroupement spatial tels que, dans chaque groupe, une couverture maximale de la base spatiale du signal avec un chevauchement minimal entre les signatures spatiales des utilisateurs est obtenue. Ce dernier permet d'augmenter la densité de connexion tout en améliorant l'efficacité spectrale. MIMO massif en TDD est également au centre du quatrième chapitre. Dans ce cas, en se basant sur les différents taux de vieillissement des canaux sans fil, la périodicité d'estimation de CSI est supplémentaire. Nous le faisons en proposant un exploité comme un degré de liberté supplémentaire. Nous le faisons en proposant une adaptation dynamique de la trame TDD en fonction des temps de cohérence des canaux hétérogènes. Les stations de bases MIMO massif sont capables d'apprendre la meilleure politique d'estimation sur le uplink pour de longues périodes. Comme les changements de canaux résultent principalement de la mobilité de l'appareil, la connaissance de l'emplacement est également incluse dans le processus d'apprentissage. Le problème de planification qui en a résulté a été modélisé comme un POMDP à deux échelles temporelles et des algorithmes efficaces à faible complexité ont été fournis pour le résoudre. Le cinquième chapitre met l'accent sur la mise en cache proactive. Nous nous concentrons sur l'amélioration de l'efficacité énergétique des réseaux dotes de mise en cache en exploitant la corrélation dans les modèles de trafic en plus de la répartition spatiale des demandes. Nous proposons un cadre qui établit un compromis optimal entre la complexité et la véracité dans la modélisation du comportement des utilisateurs grâce à la classification adaptative basée sur la popularité du contenu. Il simplifie également le problème du placement de contenu, ce qui se traduit par un cadre d'allocation de contenu rapidement adaptable et économe en énergie.