Time-Predictable Architectures

Building computers that can be used to design embedded real-time systems is the subject of this title. Real-time embedded software requires increasingly higher performances. The authors therefore consider processors that implement advanced mechanisms such as pipelining, out-of-order execution, branch prediction, cache memories, multi-threading, multicorearchitectures, etc. The authors of this book investigate the timepredictability of such schemes.

PREFACE ix

CHAPTER 1. REAL-TIME SYSTEMS AND TIME PREDICTABILITY 1

1.1. Real-time systems 1

1.1.1. Introduction 1

1.1.2. Soft, firm and hard real-time systems 4

1.1.3. Safety standards 6

1.1.4. Examples 7

1.2. Time predictability 15

1.3. Book outline 16

CHAPTER 2. TIMING ANALYSIS OF REAL-TIME SYSTEMS 19

2.1. Real-time task scheduling 19

2.1.1. Task model 19

2.1.2. Objectives of task scheduling algorithms 20

2.1.3. Mono-processor scheduling for periodic tasks 21

2.1.4. Scheduling sporadic and aperiodic tasks 23

2.1.5. Multiprocessor scheduling for periodic tasks 23

2.2. Task-level analysis 24

2.2.1. Flow analysis: identifying possible paths 25

2.2.2. Low-level analysis: determining partial execution times 27

2.2.3. WCET computation 29

2.2.4. WCET analysis tools 32

2.2.5. Alternative approaches to WCET analysis 32

2.2.6. Time composability 35

CHAPTER 3. CURRENT PROCESSOR ARCHITECTURES  37

3.1. Pipelining 37

3.1.1. Pipeline effects 38

3.1.2. Modeling for timing analysis 41

3.1.3. Recommendations for predictability 49

3.2. Superscalar architectures 49

3.2.1. In-order execution 50

3.2.2. Out-of-order execution 52

3.2.3. Modeling for timing analysis 55

3.2.4. Recommendations for predictability 56

3.3. Multithreading 57

3.3.1. Time-predictability issues raised by multithreading 58

3.3.2. Time-predictable example architectures 60

3.4. Branch prediction 62

3.4.1. State-of-the-art branch prediction 62

3.4.2. Branch prediction in real-time systems 64

3.4.3. Approaches to branch prediction modeling 65

CHAPTER 4. MEMORY HIERARCHY 69

4.1. Caches 71

4.1.1. Organization of cache memories 71

4.1.2. Static analysis of the behavior of caches 74

4.1.3. Recommendations for timing predictability 81

4.2. Scratchpad memories 87

4.2.1. Scratchpad RAM 87

4.2.2. Data scratchpad 87

4.2.3. Instruction scratchpad 88

4.3. External memories 93

4.3.1. Static RAM 93

4.3.2. Dynamic RAM 97

4.3.3. Flash memory 103

CHAPTER 5. MULTICORES 105

5.1. Impact of resource sharing on time predictability 105

5.2. Timing analysis for multicores 106

5.2.1. Analysis of temporal/bandwidth sharing 107

5.2.2. Analysis of spatial sharing 110

5.3. Local caches 111

5.3.1. Coherence techniques 112

5.3.2. Discussion on timing analyzability 115

5.4. Conclusion 121

5.5. Time-predictable architectures 121

5.5.1. Uncached accesses to shared data 121

5.5.2. On-demand coherent cache 123

CHAPTER 6. EXAMPLE ARCHITECTURES 127

6.1. The multithreaded processor Komodo 127

6.1.1. The Komodo architecture 128

6.1.2. Integrated thread scheduling 130

6.1.3. Guaranteed percentage scheduling 131

6.1.4. The jamuth IP core 132

6.1.5. Conclusion 134

6.2. The JOP architecture 134

6.2.1. Conclusion 136

6.3. The PRET architecture 136

6.3.1. PRET pipeline architecture 136

6.3.2. Instruction set extension 137

6.3.3. DDR2 memory controller 137

6.3.4. Conclusion 138

6.4. The multi-issue CarCore processor 138

6.4.1. The CarCore architecture 139

6.4.2. Layered thread scheduling 140

6.4.3. CarCore thread scheduling algorithms 142

6.4.4. Conclusion 146

6.5. The MERASA multicore processor 146

6.5.1. The MERASA architecture 147

6.5.2. The MERASA processor core 148

6.5.3. Interconnection bus 149

6.5.4. Memory hierarchy 149

6.5.5. Conclusion 150

6.6. The T-CREST multicore processor 151

6.6.1. The Patmos processor core 151

6.6.2. The T-CREST interconnect 152

6.6.3. Conclusion 153

6.7. The parMERASA manycore processor 154

6.7.1. System overview 154

6.7.2. Memory hierarchy 155

6.7.3. Communication infrastructure 157

6.7.4. Peripheral devices and interrupt system 159

6.7.5. Conclusion 161

BIBLIOGRAPHY 163

INDEX 179

Christine Rochange is Associate professor at Université Paul Sabatier (IRIT), Toulouse, France.

Pascal Sainrat, Université Paul Sabatier, (IRIT), Toulouse, France.

Sascha Uhrig, University of Dortmund, Germany.