Single-ISA heterogeneous multi-core processors (SHMP) have become increasingly important due to their potential to significantly improve the execution efficiency for diverse workloads and thereby alleviate the power density constraints in Chip Multiprocessors (CMP). The importance of SHMP is further underscored by the fact that manufacturing defects and process variation could also cause single-ISA heterogeneity in CMPs even though the CMP is originally designed as homogeneous. However, to fully exploit the execution efficiency that SHMP has to offer, programs have to be efficiently mapped/scheduled to the appropriate cores such that the hardware resources of the cores match the resource demands of the programs, which is challenging and remains an open problem. This dissertation presents a comprehensive set of off-line and on-line techniques that leverage analytical performance modeling to bridge the gap between the workload diversity and the hardware heterogeneity. For the off-line scenario, this dissertation presents an efficient resource demand analysis framework that can estimate the resource demands of a program based on the inherent characteristics of the program without using any detailed simulation. Based on the estimated resource demands, this dissertation further proposes a multi-dimensional program-core matching technique that projects program resource demands and core configurations to a unified multi-dimensional space, and uses the weighted Euclidean distance between these two to identify the matching program-core pair. This dissertation also presents a dynamic and predictive application scheduler for SHMPs. It uses a set of hardware-efficient online profilers and an analytical performance model to simultaneously predict the application’s performance on different cores. Based on the predicted performance, the scheduler identifies and enforces near-optimal application assignment for each scheduling interval without any trial runs or off-line profiling. Using only a few kilo-bytes of extra hardware, the proposed heterogeneity-aware scheduler improves the weighted speedup by 11.3% compared with the commodity OpenSolaris scheduler and by 6.8% compared with the best known research scheduler. Finally, this dissertation presents a predictive yet cost effective mechanism to manage intra-core and/or inter-core resources in dynamic SHMP. It also uses a set of hardware-efficient online profilers and an analytical performance model to predict the application’s performance with different resource allocations. Based on the predicted performance, the resource allocator identifies and enforces near optimum resource partitions for each epoch without any trial runs. The experimental results show that the proposed predictive resource management framework could improve the weighted speedup of the CMP system by an average of 11.6% compared with the equal partition scheme, and 9.3% compared with existing reactive resource management scheme. / text

Le calcul intensif joue un rôle moteur de premier plan pour de nombreux domaines scientifiques. La croissance en puissance crête des supercalculateurs a évolué du téraflops au pétaflops en l'espace d'une décennie. Toutefois, la consommation d'énergie associée extrêmement élevée ainsi que le coût associé ont motivé des recherches vers des technologies plus efficaces énergétiquement comme l'utilisation de processeurs issus du domaine des systèmes embarqués à faible puissance.Selon les prévisions, les systèmes multicœurs émergents seront constitués de centaines de cœurs d'ici la fin de la décennie. Cette évolution nécessite des solutions efficaces pour l'exploration de l'espace de conception et le débogage. Les simulateurs industriels et académiques disponibles à ce jour diffèrent en termes de compromis entre vitesse de simulation et précision. Leur adoption est généralement définie par le niveau d'exploration souhaité. Les simulateurs quasi cycle-précis sont populaires et attrayants pour l'exploration architecturale. Alors que la vitesse de simulation est trivialement observée, le niveau de précision de ces simulateurs reste souvent flou. En outre, bien que permettant une évaluation flexible et détaillée de l'architecture, les simulateurs quasi cycle-précis entraînent des vitesses de simulation lentes ce qui limite leur champ d'application pour des systèmes avec des centaines de cœurs. Cela exige des approches alternatives capables de fournir des simulations rapides tout en préservant une précision élevée ce qui est cruciale pour l'exploration architecturale.Dans cette thèse, des modèles d'architectures multicœurs complexes ont été développés et évalués en utilisant des systèmes de simulation quasi cycle-précis pour l'exploration de la performance et de la puissance. Sur cette base, une approche hybride orientée traces d'exécution a été proposée pour permettre une exploration rapide, flexible et précise des architectures multicœurs à grande échelle. Sur la base de l'environnement de simulation proposé, plusieurs configurations de systèmes manycoeurs ont été construites et évaluées en évaluant le passage à l'échelle des performances. Enfin, des configurations alternatives d'architectures multicœurs hétérogènes ont été proposées et ont montré des améliorations significatives en termes d'efficacité énergétique. / Since the computational needs precipitously grow each year, HPC technology becomes a driving force for numerous scientific and consumer areas. The most powerful supercomputer has been progressing from TFLOPS to PFLOPS throughout the last ten years. However, the extremely high power consumption and therefore the high cost pushed researchers to explore more energy-efficient technologies, such as the use of low-power embedded SoCs.The evolution of emerging manycore systems, forecasted to feature hundreds of cores by the end of the decade calls for efficient solutions for the design space exploration and debugging. Available industrial and academic simulators differ in terms of simulation speed/accuracy trade-offs. Cycle-approximate simulators are popular and attractive for architectural exploration. Even though enabling flexible and detailed architecture evaluation, cycle-approximate simulators entail slow simulation speeds, thereby limiting their scope of applicability for systems with hundreds of cores. This calls for alternative approaches capable of providing high simulation speed while preserving accuracy that is crucial to architectural exploration.In this thesis, we evaluate cycle-approximate simulation techniques for fast and accurate exploration of multi- and manycore architectures. Expecting to significantly reduce simulation time still preserving the accuracy at the cycle-approximate level, we propose a hybrid trace-oriented approach to enable flexible manycore architecture simulation. We design a set of simulation techniques to overcome the main weaknesses of the trace-oriented approach. The trace synchronization technique aims to manage control and data dependencies arising from the abstraction of processor cores. The trace replication technique is proposed to simulate manycore architectures using a finite set of pre-collected traces. The computation phase scaling technique is designed to enable flexible switching between multiple processor models without considering microarchitectural difference but taking into account the computation speed ratio. Based on the proposed simulation environment, we explore several manycore architectures in terms of performance and energy-efficiency trade-offs.

In this decade the emerging multicore technology will hit the automotive industry. The increasing complexity of the multicore-systems will make a manual verification of the safety and realtime constraints impossible. For this reason, dedicated methods and tools are utterly necessary, in order to deal with the upcoming multicore issues. A lot of researchprojects for new hardware platforms and software frameworks for the automotive industry are running nowadays, because the paradigms of the “High-Performance Computing” and “Server/Desktop Domain” cannot be easily adapted for the embedded systems. One of the difficulties is the early suitability estimation of a hardware platform for a software architecture design, but hardly a research-work is tackling that. This thesis represents a procedure to evaluate the plausibility of software architecture estimations and decisions at design stage. This includes an analysis technique of multicore systems, an underlying graph-model – to represent the multicore system – and a simulation tool evaluation. This can guide the software architect, to design a multicore system, in full consideration of all relevant parameters and issues. / In den nächsten Jahren wird die aufkommende Multicore-Technologie auf die Automobil-Branche zukommen. Die wachsende Komplexität der Multicore-Systeme lässt es nicht mehr zu, die Verifikation von Sicherheits- und Echtzeit-Anforderungen manuell auszuführen. Daher sind spezielle Methoden und Werkzeuge zwingend notwendig, um gerade mit den bevorstehenden Multicore-Problemfällen richtig umzugehen. Heutzutage laufen viele Forschungsprojekte für neue Hardware-Plattformen und Software-Frameworks für die Automobil-Industrie, weil die Paradigmen des “High-Performance Computings” und der “Server/Desktop-Domäne” nicht einfach so für die Eingebetteten Systeme angewendet werden können. Einer der Problemfälle ist das frühe Erkennen, ob die Hardware-Plattform für die Software-Architektur ausreicht, aber nur wenige Forschungs-Arbeiten berücksichtigen das. Diese Arbeit zeigt ein Vorgehens-Model auf, welches ermöglicht, dass Software-Architektur Abschätzungen und Entscheidungen bereits zur Entwurfszeit bewertet werden können. Das beinhaltet eine Analyse Technik für Multicore-Systeme, ein grundsätzliches Graphen-Model, um ein Multicore-System darzustellen, und eine Simulatoren Evaluierung. Dies kann den Software-Architekten helfen, ein Multicore System zu entwerfen, welches alle wichtigen Parameter und Problemfälle berücksichtigt.

In this decade the emerging multicore technology will hit the automotive industry. The increasing complexity of the multicore-systems will make a manual verification of the safety and realtime constraints impossible. For this reason, dedicated methods and tools are utterly necessary, in order to deal with the upcoming multicore issues. A lot of researchprojects for new hardware platforms and software frameworks for the automotive industry are running nowadays, because the paradigms of the “High-Performance Computing” and “Server/Desktop Domain” cannot be easily adapted for the embedded systems. One of the difficulties is the early suitability estimation of a hardware platform for a software architecture design, but hardly a research-work is tackling that. This thesis represents a procedure to evaluate the plausibility of software architecture estimations and decisions at design stage. This includes an analysis technique of multicore systems, an underlying graph-model – to represent the multicore system – and a simulation tool evaluation. This can guide the software architect, to design a multicore system, in full consideration of all relevant parameters and issues.:Contents List of Figures vii List of Tables viii List of Abbreviations ix 1. Introduction 1 1.1. Motivation 1 1.2. Scope 2 1.3. Goal and Tasks 2 1.4. Structure of the Thesis 3 I. Multicore Technology 4 2. Fundamentals 5 2.1. Automotive Domains 5 2.2. Embedded System 7 2.2.1. Realtime 7 2.2.2. Runtime Predictions 8 2.2.3. Multicore Processor Architectures 8 2.3. Development of Automotive Embedded Systems 9 2.3.1. Applied V-Model 9 2.3.2. System Description and System Implementation 10 2.4. Software Architecture 11 2.5. Model Description of Software Structures 13 2.5.1. Design Domains of Multicore Systems 13 2.5.2. Software Structure Components 13 3. Trend and State of the Art of Multicore Research, Technology and Market 17 3.1. The Importance of Multicore Technology 17 3.2. Multicore Technology for the Automotive Industry 19 3.2.1. High-Performance Computing versus Embedded Systems 19 3.2.2. The Trend for the Automotive Industry 20 3.2.3. Examples of Multicore Hardware Platforms 23 3.3. Approaches for Upcoming Multicore Problems 24 3.3.1. Migration from Single-Core to Multicore 24 3.3.2. Correctness-by-Construction 25 3.3.3. AUTOSAR Multicore System 26 3.4. Software Architecture Simulators 28 3.4.1. Justification for Simulation Tools 28 3.4.2. System Model Simulation Software 29 3.5. Current Software Architecture Research Projects 31 3.6. Portrait of the current Situation 32 3.7. Summary of the Multicore Trend 32 II. Identification of Multicore System Parameters 34 4. Project Analysis to Identify Crucial Parameters 35 4.1. Analysis Procedure 35 4.1.1. Question Catalogue 36 4.1.2. Three Domains of Investigation 37 4.2. Analysed Projects 41 4.2.1. Project 1: Online Camera Calibration 41 4.2.2. Project 2: Power Management 45 4.2.3. Project 3: Battery Management 46 4.3. Results of Project Analysis 51 4.3.1. Ratio of Parameter Influence 51 4.3.2. General Influences of Parameters 53 5. Abstract System Model 54 5.1. Requirements for the System-Model 54 5.2. Simulation Tool Model Evaluation 55 5.2.1. System Model of PRECISION PRO 55 5.2.2. System Model of INCHRON 57 5.2.3. System Model of SymTA/S 58 5.2.4. System Model of Timing Architects 59 5.2.5. System Model of AMALTHEA 60 5.3. Concept of Abstract System Model 62 5.3.1. Components of the System Model 63 5.3.2. Software Function-Graph 63 5.3.3. Hardware Architecture-Graph 64 5.3.4. Specification-Graph for Mapping 65 6. Testcase Implementation 67 6.1. Example Test-System 68 6.1.1. Simulated Test-System 70 6.1.2. Testcases 73 6.2. Result of Tests 74 6.2.1. Processor Core Runtime Execution 74 6.2.2. Communication 75 6.2.3. Memory Access 76 6.3. Summary of Multicore System Parameters Identification 78 III. Evaluation of Software Architectures 80 7. Estimation-Procedure 81 7.1. Estimation-Procedure in a Nutshell 81 7.2. Steps of Estimation-Procedure 82 7.2.1. Project Analysis 82 7.2.2. Timing and Memory Requirements 83 7.2.3. System Modelling 84 7.2.4. Software Architecture Simulation 85 7.2.5. Results of a Validated Software Architecture 86 7.2.6. Feedback of Partly Implemented System 88 8. Implementation and Simulation 89 8.1. Example Project Analysis – Online Camera Calibration 89 8.1.1. Example Project Choice 90 8.1.2. OCC Timing Requirements Analysis 90 8.2. OCC Modelling 94 8.2.1. OCC Software Function-Graph 95 8.2.2. OCC Hardware Architecture 96 8.2.3. OCC Mapping – Specification-Graph 101 8.3. Simulation of the OCC Model with Tool Support 102 8.3.1. Tasks for Tool Setup 103 8.3.2. PRECISION PRO 105 8.3.3. INCHRON 107 8.3.4. SymTA/S 108 8.3.5. Timing Architects 112 8.3.6. AMALTHEA 115 8.4. System Optimisation Possibilities 116 8.5. OCC Implementation Results 117 9. Results of the Estimation-Procedure Evaluation 119 9.1. Tool-Evaluation Results 119 9.2. Findings of Estimation, Simulation and ECU-Behavior. 123 9.2.1. System-Specific Issues 123 9.2.2. Communication Issues 123 9.2.3. Memory Issues 124 9.2.4. Timing Issues 124 9.3. Summary of the Software Architecture Evaluation 125 10.Summary and Outlook 127 10.1. Summary 127 10.2. Usability of the Estimation-Procedure 128 10.3. Outlook and Future Work 129 11. Bibliography xii IV. Appendices xxi A. Appendices xxii A.1. Embedded Multicore Technology Research Projects xxii A.1.1. Simulation Software xxii A.1.2. Multicore Software Research Projects xxiii A.2. Testcase Implementation Results xxvi A.2.1. Function Block Processor Core Executions xxvi A.2.2. Memory Access Mechanism xxvii A.2.3. Memory Access Timings of Different Datatypes xxviii A.2.4. Inter-Processor Communication xxix A.3. Further OCC System Description xxxii A.3.1. OCC Timing Requirements of the FB xxxii A.3.2. INCHRON Validation Results xxxiv A.4. Detailed System Optimisation xxxv A.4.1. Optimisation through Hardware Alternation xxxv A.4.2. Optimisation through Mapping Alternation xxxv A.4.3. Optimisation of Execution Timings xxxvii B. Estimation-Procedure Engineering Paper xl B.1. Components and Scope of Software Architecture xl B.2. Estimation-Procedure in a Nutshell xlii B.3. Project Analysis xliii B.3.1. System level analysis xliv B.3.2. Communication Domain xlv B.3.3. Processor Core Domain xlvi B.3.4. Memory Domain xlvii B.3.5. Timing and Memory Requirements xlviii B.4. System Modelling xlix B.4.1. Function Model xlix B.4.2. Function-Graph l B.4.3. Possible ECU Target l B.4.4. Architecture-Graph l B.4.5. Software Architecture Mapping li B.4.6. Domain Specific Decision Guide lii B.5. Software Architecture Simulation liii B.6. Results of a Simulated Software Architecture lv B.7. Feedback of Partly Implemented System for Software Architecture Improvement lvi B.8. Benefits of the Estimation-Procedure lvii / In den nächsten Jahren wird die aufkommende Multicore-Technologie auf die Automobil-Branche zukommen. Die wachsende Komplexität der Multicore-Systeme lässt es nicht mehr zu, die Verifikation von Sicherheits- und Echtzeit-Anforderungen manuell auszuführen. Daher sind spezielle Methoden und Werkzeuge zwingend notwendig, um gerade mit den bevorstehenden Multicore-Problemfällen richtig umzugehen. Heutzutage laufen viele Forschungsprojekte für neue Hardware-Plattformen und Software-Frameworks für die Automobil-Industrie, weil die Paradigmen des “High-Performance Computings” und der “Server/Desktop-Domäne” nicht einfach so für die Eingebetteten Systeme angewendet werden können. Einer der Problemfälle ist das frühe Erkennen, ob die Hardware-Plattform für die Software-Architektur ausreicht, aber nur wenige Forschungs-Arbeiten berücksichtigen das. Diese Arbeit zeigt ein Vorgehens-Model auf, welches ermöglicht, dass Software-Architektur Abschätzungen und Entscheidungen bereits zur Entwurfszeit bewertet werden können. Das beinhaltet eine Analyse Technik für Multicore-Systeme, ein grundsätzliches Graphen-Model, um ein Multicore-System darzustellen, und eine Simulatoren Evaluierung. Dies kann den Software-Architekten helfen, ein Multicore System zu entwerfen, welches alle wichtigen Parameter und Problemfälle berücksichtigt.:Contents List of Figures vii List of Tables viii List of Abbreviations ix 1. Introduction 1 1.1. Motivation 1 1.2. Scope 2 1.3. Goal and Tasks 2 1.4. Structure of the Thesis 3 I. Multicore Technology 4 2. Fundamentals 5 2.1. Automotive Domains 5 2.2. Embedded System 7 2.2.1. Realtime 7 2.2.2. Runtime Predictions 8 2.2.3. Multicore Processor Architectures 8 2.3. Development of Automotive Embedded Systems 9 2.3.1. Applied V-Model 9 2.3.2. System Description and System Implementation 10 2.4. Software Architecture 11 2.5. Model Description of Software Structures 13 2.5.1. Design Domains of Multicore Systems 13 2.5.2. Software Structure Components 13 3. Trend and State of the Art of Multicore Research, Technology and Market 17 3.1. The Importance of Multicore Technology 17 3.2. Multicore Technology for the Automotive Industry 19 3.2.1. High-Performance Computing versus Embedded Systems 19 3.2.2. The Trend for the Automotive Industry 20 3.2.3. Examples of Multicore Hardware Platforms 23 3.3. Approaches for Upcoming Multicore Problems 24 3.3.1. Migration from Single-Core to Multicore 24 3.3.2. Correctness-by-Construction 25 3.3.3. AUTOSAR Multicore System 26 3.4. Software Architecture Simulators 28 3.4.1. Justification for Simulation Tools 28 3.4.2. System Model Simulation Software 29 3.5. Current Software Architecture Research Projects 31 3.6. Portrait of the current Situation 32 3.7. Summary of the Multicore Trend 32 II. Identification of Multicore System Parameters 34 4. Project Analysis to Identify Crucial Parameters 35 4.1. Analysis Procedure 35 4.1.1. Question Catalogue 36 4.1.2. Three Domains of Investigation 37 4.2. Analysed Projects 41 4.2.1. Project 1: Online Camera Calibration 41 4.2.2. Project 2: Power Management 45 4.2.3. Project 3: Battery Management 46 4.3. Results of Project Analysis 51 4.3.1. Ratio of Parameter Influence 51 4.3.2. General Influences of Parameters 53 5. Abstract System Model 54 5.1. Requirements for the System-Model 54 5.2. Simulation Tool Model Evaluation 55 5.2.1. System Model of PRECISION PRO 55 5.2.2. System Model of INCHRON 57 5.2.3. System Model of SymTA/S 58 5.2.4. System Model of Timing Architects 59 5.2.5. System Model of AMALTHEA 60 5.3. Concept of Abstract System Model 62 5.3.1. Components of the System Model 63 5.3.2. Software Function-Graph 63 5.3.3. Hardware Architecture-Graph 64 5.3.4. Specification-Graph for Mapping 65 6. Testcase Implementation 67 6.1. Example Test-System 68 6.1.1. Simulated Test-System 70 6.1.2. Testcases 73 6.2. Result of Tests 74 6.2.1. Processor Core Runtime Execution 74 6.2.2. Communication 75 6.2.3. Memory Access 76 6.3. Summary of Multicore System Parameters Identification 78 III. Evaluation of Software Architectures 80 7. Estimation-Procedure 81 7.1. Estimation-Procedure in a Nutshell 81 7.2. Steps of Estimation-Procedure 82 7.2.1. Project Analysis 82 7.2.2. Timing and Memory Requirements 83 7.2.3. System Modelling 84 7.2.4. Software Architecture Simulation 85 7.2.5. Results of a Validated Software Architecture 86 7.2.6. Feedback of Partly Implemented System 88 8. Implementation and Simulation 89 8.1. Example Project Analysis – Online Camera Calibration 89 8.1.1. Example Project Choice 90 8.1.2. OCC Timing Requirements Analysis 90 8.2. OCC Modelling 94 8.2.1. OCC Software Function-Graph 95 8.2.2. OCC Hardware Architecture 96 8.2.3. OCC Mapping – Specification-Graph 101 8.3. Simulation of the OCC Model with Tool Support 102 8.3.1. Tasks for Tool Setup 103 8.3.2. PRECISION PRO 105 8.3.3. INCHRON 107 8.3.4. SymTA/S 108 8.3.5. Timing Architects 112 8.3.6. AMALTHEA 115 8.4. System Optimisation Possibilities 116 8.5. OCC Implementation Results 117 9. Results of the Estimation-Procedure Evaluation 119 9.1. Tool-Evaluation Results 119 9.2. Findings of Estimation, Simulation and ECU-Behavior. 123 9.2.1. System-Specific Issues 123 9.2.2. Communication Issues 123 9.2.3. Memory Issues 124 9.2.4. Timing Issues 124 9.3. Summary of the Software Architecture Evaluation 125 10.Summary and Outlook 127 10.1. Summary 127 10.2. Usability of the Estimation-Procedure 128 10.3. Outlook and Future Work 129 11. Bibliography xii IV. Appendices xxi A. Appendices xxii A.1. Embedded Multicore Technology Research Projects xxii A.1.1. Simulation Software xxii A.1.2. Multicore Software Research Projects xxiii A.2. Testcase Implementation Results xxvi A.2.1. Function Block Processor Core Executions xxvi A.2.2. Memory Access Mechanism xxvii A.2.3. Memory Access Timings of Different Datatypes xxviii A.2.4. Inter-Processor Communication xxix A.3. Further OCC System Description xxxii A.3.1. OCC Timing Requirements of the FB xxxii A.3.2. INCHRON Validation Results xxxiv A.4. Detailed System Optimisation xxxv A.4.1. Optimisation through Hardware Alternation xxxv A.4.2. Optimisation through Mapping Alternation xxxv A.4.3. Optimisation of Execution Timings xxxvii B. Estimation-Procedure Engineering Paper xl B.1. Components and Scope of Software Architecture xl B.2. Estimation-Procedure in a Nutshell xlii B.3. Project Analysis xliii B.3.1. System level analysis xliv B.3.2. Communication Domain xlv B.3.3. Processor Core Domain xlvi B.3.4. Memory Domain xlvii B.3.5. Timing and Memory Requirements xlviii B.4. System Modelling xlix B.4.1. Function Model xlix B.4.2. Function-Graph l B.4.3. Possible ECU Target l B.4.4. Architecture-Graph l B.4.5. Software Architecture Mapping li B.4.6. Domain Specific Decision Guide lii B.5. Software Architecture Simulation liii B.6. Results of a Simulated Software Architecture lv B.7. Feedback of Partly Implemented System for Software Architecture Improvement lvi B.8. Benefits of the Estimation-Procedure lvii