Christine Rochange is Professor at Paul Sabatier University in Toulouse, France. She is conducting research activities in the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab). Her current research interests include the analysis of worst-case execution times of sequential and parallel real-time applications.Sascha Uhrig is a Junior Professor leading the Microcontroller Systems group at the Department of Electrical Engineering and Information Technology at the Technical University of Dortmund, Germany. His research interests concern processor and computer architecture with the focus on time-predictable architectures. He is working on multithreaded as well as multicore processors, including memory hierarchies.Pascal Sainrat is Professor at Paul Sabatier University in Toulouse, France. He is the leader of the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab) and his current research interests concern the design of time-predictable architectures.

• PREFACE ixCHAPTER 1. REAL-TIME SYSTEMS AND TIME PREDICTABILITY 11.1. Real-time systems 11.1.1. Introduction 11.1.2. Soft, firm and hard real-time systems 41.1.3. Safety standards 61.1.4. Examples 71.2. Time predictability 151.3. Book outline 16CHAPTER 2. TIMING ANALYSIS OF REAL-TIME SYSTEMS 192.1. Real-time task scheduling 192.1.1. Task model 192.1.2. Objectives of task scheduling algorithms 202.1.3. Mono-processor scheduling for periodic tasks 212.1.4. Scheduling sporadic and aperiodic tasks 232.1.5. Multiprocessor scheduling for periodic tasks 232.2. Task-level analysis 242.2.1. Flow analysis: identifying possible paths 252.2.2. Low-level analysis: determining partial execution times 272.2.3. WCET computation 292.2.4. WCET analysis tools 322.2.5. Alternative approaches to WCET analysis 322.2.6. Time composability 35CHAPTER 3. CURRENT PROCESSOR ARCHITECTURES  373.1. Pipelining 373.1.1. Pipeline effects 383.1.2. Modeling for timing analysis 413.1.3. Recommendations for predictability 493.2. Superscalar architectures 493.2.1. In-order execution 503.2.2. Out-of-order execution 523.2.3. Modeling for timing analysis 553.2.4. Recommendations for predictability 563.3. Multithreading 573.3.1. Time-predictability issues raised by multithreading 583.3.2. Time-predictable example architectures 603.4. Branch prediction 623.4.1. State-of-the-art branch prediction 623.4.2. Branch prediction in real-time systems 643.4.3. Approaches to branch prediction modeling 65CHAPTER 4. MEMORY HIERARCHY 694.1. Caches 714.1.1. Organization of cache memories 714.1.2. Static analysis of the behavior of caches 744.1.3. Recommendations for timing predictability 814.2. Scratchpad memories 874.2.1. Scratchpad RAM 874.2.2. Data scratchpad 874.2.3. Instruction scratchpad 884.3. External memories 934.3.1. Static RAM 934.3.2. Dynamic RAM 974.3.3. Flash memory 103CHAPTER 5. MULTICORES 1055.1. Impact of resource sharing on time predictability 1055.2. Timing analysis for multicores 1065.2.1. Analysis of temporal/bandwidth sharing 1075.2.2. Analysis of spatial sharing 1105.3. Local caches 1115.3.1. Coherence techniques 1125.3.2. Discussion on timing analyzability 1155.4. Conclusion 1215.5. Time-predictable architectures 1215.5.1. Uncached accesses to shared data 1215.5.2. On-demand coherent cache 123CHAPTER 6. EXAMPLE ARCHITECTURES 1276.1. The multithreaded processor Komodo 1276.1.1. The Komodo architecture 1286.1.2. Integrated thread scheduling 1306.1.3. Guaranteed percentage scheduling 1316.1.4. The jamuth IP core 1326.1.5. Conclusion 1346.2. The JOP architecture 1346.2.1. Conclusion 1366.3. The PRET architecture 1366.3.1. PRET pipeline architecture 1366.3.2. Instruction set extension 1376.3.3. DDR2 memory controller 1376.3.4. Conclusion 1386.4. The multi-issue CarCore processor 1386.4.1. The CarCore architecture 1396.4.2. Layered thread scheduling 1406.4.3. CarCore thread scheduling algorithms 1426.4.4. Conclusion 1466.5. The MERASA multicore processor 1466.5.1. The MERASA architecture 1476.5.2. The MERASA processor core 1486.5.3. Interconnection bus 1496.5.4. Memory hierarchy 1496.5.5. Conclusion 1506.6. The T-CREST multicore processor 1516.6.1. The Patmos processor core 1516.6.2. The T-CREST interconnect 1526.6.3. Conclusion 1536.7. The parMERASA manycore processor 1546.7.1. System overview 1546.7.2. Memory hierarchy 1556.7.3. Communication infrastructure 1576.7.4. Peripheral devices and interrupt system 1596.7.5. Conclusion 161BIBLIOGRAPHY 163INDEX 179

Christine Rochange is Professor at Paul Sabatier University in Toulouse, France. She is conducting research activities in the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab). Her current research interests include the analysis of worst-case execution times of sequential and parallel real-time applications.Sascha Uhrig is a Junior Professor leading the Microcontroller Systems group at the Department of Electrical Engineering and Information Technology at the Technical University of Dortmund, Germany. His research interests concern processor and computer architecture with the focus on time-predictable architectures. He is working on multithreaded as well as multicore processors, including memory hierarchies.Pascal Sainrat is Professor at Paul Sabatier University in Toulouse, France. He is the leader of the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab) and his current research interests concern the design of time-predictable architectures.

• PREFACE ixCHAPTER 1. REAL-TIME SYSTEMS AND TIME PREDICTABILITY 11.1. Real-time systems 11.1.1. Introduction 11.1.2. Soft, firm and hard real-time systems 41.1.3. Safety standards 61.1.4. Examples 71.2. Time predictability 151.3. Book outline 16CHAPTER 2. TIMING ANALYSIS OF REAL-TIME SYSTEMS 192.1. Real-time task scheduling 192.1.1. Task model 192.1.2. Objectives of task scheduling algorithms 202.1.3. Mono-processor scheduling for periodic tasks 212.1.4. Scheduling sporadic and aperiodic tasks 232.1.5. Multiprocessor scheduling for periodic tasks 232.2. Task-level analysis 242.2.1. Flow analysis: identifying possible paths 252.2.2. Low-level analysis: determining partial execution times 272.2.3. WCET computation 292.2.4. WCET analysis tools 322.2.5. Alternative approaches to WCET analysis 322.2.6. Time composability 35CHAPTER 3. CURRENT PROCESSOR ARCHITECTURES  373.1. Pipelining 373.1.1. Pipeline effects 383.1.2. Modeling for timing analysis 413.1.3. Recommendations for predictability 493.2. Superscalar architectures 493.2.1. In-order execution 503.2.2. Out-of-order execution 523.2.3. Modeling for timing analysis 553.2.4. Recommendations for predictability 563.3. Multithreading 573.3.1. Time-predictability issues raised by multithreading 583.3.2. Time-predictable example architectures 603.4. Branch prediction 623.4.1. State-of-the-art branch prediction 623.4.2. Branch prediction in real-time systems 643.4.3. Approaches to branch prediction modeling 65CHAPTER 4. MEMORY HIERARCHY 694.1. Caches 714.1.1. Organization of cache memories 714.1.2. Static analysis of the behavior of caches 744.1.3. Recommendations for timing predictability 814.2. Scratchpad memories 874.2.1. Scratchpad RAM 874.2.2. Data scratchpad 874.2.3. Instruction scratchpad 884.3. External memories 934.3.1. Static RAM 934.3.2. Dynamic RAM 974.3.3. Flash memory 103CHAPTER 5. MULTICORES 1055.1. Impact of resource sharing on time predictability 1055.2. Timing analysis for multicores 1065.2.1. Analysis of temporal/bandwidth sharing 1075.2.2. Analysis of spatial sharing 1105.3. Local caches 1115.3.1. Coherence techniques 1125.3.2. Discussion on timing analyzability 1155.4. Conclusion 1215.5. Time-predictable architectures 1215.5.1. Uncached accesses to shared data 1215.5.2. On-demand coherent cache 123CHAPTER 6. EXAMPLE ARCHITECTURES 1276.1. The multithreaded processor Komodo 1276.1.1. The Komodo architecture 1286.1.2. Integrated thread scheduling 1306.1.3. Guaranteed percentage scheduling 1316.1.4. The jamuth IP core 1326.1.5. Conclusion 1346.2. The JOP architecture 1346.2.1. Conclusion 1366.3. The PRET architecture 1366.3.1. PRET pipeline architecture 1366.3.2. Instruction set extension 1376.3.3. DDR2 memory controller 1376.3.4. Conclusion 1386.4. The multi-issue CarCore processor 1386.4.1. The CarCore architecture 1396.4.2. Layered thread scheduling 1406.4.3. CarCore thread scheduling algorithms 1426.4.4. Conclusion 1466.5. The MERASA multicore processor 1466.5.1. The MERASA architecture 1476.5.2. The MERASA processor core 1486.5.3. Interconnection bus 1496.5.4. Memory hierarchy 1496.5.5. Conclusion 1506.6. The T-CREST multicore processor 1516.6.1. The Patmos processor core 1516.6.2. The T-CREST interconnect 1526.6.3. Conclusion 1536.7. The parMERASA manycore processor 1546.7.1. System overview 1546.7.2. Memory hierarchy 1556.7.3. Communication infrastructure 1576.7.4. Peripheral devices and interrupt system 1596.7.5. Conclusion 161BIBLIOGRAPHY 163INDEX 179

Christine Rochange is Professor at Paul Sabatier University in Toulouse, France. She is conducting research activities in the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab). Her current research interests include the analysis of worst-case execution times of sequential and parallel real-time applications.Sascha Uhrig is a Junior Professor leading the Microcontroller Systems group at the Department of Electrical Engineering and Information Technology at the Technical University of Dortmund, Germany. His research interests concern processor and computer architecture with the focus on time-predictable architectures. He is working on multithreaded as well as multicore processors, including memory hierarchies.Pascal Sainrat is Professor at Paul Sabatier University in Toulouse, France. He is the leader of the TRACES group at the Institut de Recherche en Informatique de Toulouse (IRIT lab) and his current research interests concern the design of time-predictable architectures.

• PREFACE ixCHAPTER 1. REAL-TIME SYSTEMS AND TIME PREDICTABILITY 11.1. Real-time systems 11.1.1. Introduction 11.1.2. Soft, firm and hard real-time systems 41.1.3. Safety standards 61.1.4. Examples 71.2. Time predictability 151.3. Book outline 16CHAPTER 2. TIMING ANALYSIS OF REAL-TIME SYSTEMS 192.1. Real-time task scheduling 192.1.1. Task model 192.1.2. Objectives of task scheduling algorithms 202.1.3. Mono-processor scheduling for periodic tasks 212.1.4. Scheduling sporadic and aperiodic tasks 232.1.5. Multiprocessor scheduling for periodic tasks 232.2. Task-level analysis 242.2.1. Flow analysis: identifying possible paths 252.2.2. Low-level analysis: determining partial execution times 272.2.3. WCET computation 292.2.4. WCET analysis tools 322.2.5. Alternative approaches to WCET analysis 322.2.6. Time composability 35CHAPTER 3. CURRENT PROCESSOR ARCHITECTURES  373.1. Pipelining 373.1.1. Pipeline effects 383.1.2. Modeling for timing analysis 413.1.3. Recommendations for predictability 493.2. Superscalar architectures 493.2.1. In-order execution 503.2.2. Out-of-order execution 523.2.3. Modeling for timing analysis 553.2.4. Recommendations for predictability 563.3. Multithreading 573.3.1. Time-predictability issues raised by multithreading 583.3.2. Time-predictable example architectures 603.4. Branch prediction 623.4.1. State-of-the-art branch prediction 623.4.2. Branch prediction in real-time systems 643.4.3. Approaches to branch prediction modeling 65CHAPTER 4. MEMORY HIERARCHY 694.1. Caches 714.1.1. Organization of cache memories 714.1.2. Static analysis of the behavior of caches 744.1.3. Recommendations for timing predictability 814.2. Scratchpad memories 874.2.1. Scratchpad RAM 874.2.2. Data scratchpad 874.2.3. Instruction scratchpad 884.3. External memories 934.3.1. Static RAM 934.3.2. Dynamic RAM 974.3.3. Flash memory 103CHAPTER 5. MULTICORES 1055.1. Impact of resource sharing on time predictability 1055.2. Timing analysis for multicores 1065.2.1. Analysis of temporal/bandwidth sharing 1075.2.2. Analysis of spatial sharing 1105.3. Local caches 1115.3.1. Coherence techniques 1125.3.2. Discussion on timing analyzability 1155.4. Conclusion 1215.5. Time-predictable architectures 1215.5.1. Uncached accesses to shared data 1215.5.2. On-demand coherent cache 123CHAPTER 6. EXAMPLE ARCHITECTURES 1276.1. The multithreaded processor Komodo 1276.1.1. The Komodo architecture 1286.1.2. Integrated thread scheduling 1306.1.3. Guaranteed percentage scheduling 1316.1.4. The jamuth IP core 1326.1.5. Conclusion 1346.2. The JOP architecture 1346.2.1. Conclusion 1366.3. The PRET architecture 1366.3.1. PRET pipeline architecture 1366.3.2. Instruction set extension 1376.3.3. DDR2 memory controller 1376.3.4. Conclusion 1386.4. The multi-issue CarCore processor 1386.4.1. The CarCore architecture 1396.4.2. Layered thread scheduling 1406.4.3. CarCore thread scheduling algorithms 1426.4.4. Conclusion 1466.5. The MERASA multicore processor 1466.5.1. The MERASA architecture 1476.5.2. The MERASA processor core 1486.5.3. Interconnection bus 1496.5.4. Memory hierarchy 1496.5.5. Conclusion 1506.6. The T-CREST multicore processor 1516.6.1. The Patmos processor core 1516.6.2. The T-CREST interconnect 1526.6.3. Conclusion 1536.7. The parMERASA manycore processor 1546.7.1. System overview 1546.7.2. Memory hierarchy 1556.7.3. Communication infrastructure 1576.7.4. Peripheral devices and interrupt system 1596.7.5. Conclusion 161BIBLIOGRAPHY 163INDEX 179