The Kiel Esterel processor [Elektronische Ressource] : a multi-threaded reactive processor / Xin Li

Xin Li

Sujets

• Informatik

Informations

• Publié par: christian-albrechts-universitat_zu_kiel
• Publié le: 01 janvier 2007
• Nombre de lectures: 11
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

The Kiel Esterel Processor:
A Multi-Threaded Reactive Processor
Dissertation
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
(Dr. -Ing.)
der Technischen Fakult¨at
der Christian-Albrechts-Universit¨at zu Kiel
Xin Li
Kiel
20071. Gutachter Reinhard von Hanxleden
2. Gutachter Michael Mendler
Datum der mundlic¨ hen Prufung¨ 23. Juli 2007Acknowledgements
This thesis would not have been possible without the support of many people. My
deepestgratitudeistomysupervisor,ProfessorReinhardvonHanxleden,forhisprecious
suggestions, friendlyadvice, andgivingmethefreedomtopursuearesearchtopic. Most
of all, for his patience with my mistakes and extreme generosity with his time. His
scientific vision, high standards, detailed comments and discussions, and solid insight
into embedded system design have given me guidance to follow throughout my research
efforts. I am also grateful to him for having provided me chances to attend many
conferences, which have expanded my horizon and inspired me to conduct this research
work.
Furthermore,myspecialthanksgotoProf.MichaelMendlerattheUniversit¨atBamberg,
Prof. StephenA.EdwardsatColumbiaUniversity,Dr.StavrosTripakisandDr.Claudio
Pinello at Cadence Berkeley Labs, and Prof. Alberto Sangiovanni-Vincentelli at the
University of California Berkeley for their inspiring talks, suggestions and advice which
were very helpful for my work.
Claus Traulsen and Malte Tiedje read a draft version of this thesis and gave me lots of
helpful comments, I really appreciate their help. I thank also Marian Andreas Boldt for
his discussions and collaboration. In addition to this, I am grateful for all the discus-
sions with Steffen Prochnow, Jan Lukoschus, and Sascha Ga¨dtke. I further thank my
colleaguesGesaWalsdorf,IsabellaCembrowski,MarenLutz,HaukeFuhrmann,andTim
Grebien for their kind help during my study in the Real-time and Embedded Systems
group.
I acknowledge the DAAD and DFG for giving me the financial support for this work.
Last, but not least, I would never have finished this work without the moral support
and encouragement of my parents (Zhenhua Li and Sujiao Wu), my wife (Di Zang) and
my daughter (Luopian Li) to whom I dedicated this dissertation.
iiiivAbstract
Manyembeddedsystemsbelongtotheclassofreactivesystems,whichcontinuouslyreact
toinputsfromtheenvironmentbygeneratingcorrespondingoutputs. Theprogramming
of reactive systems typically requires the use of non-standard control flow constructs,
suchasconcurrencyorexceptionhandling. Mostprogramminglanguagesdonotsupport
these constructs at all, or their use induces non-deterministic program behavior. To
addressthesedifficulties,thesynchronouslanguageEsterelhasbeendevelopedtoexpress
reactive control flow patterns in a concise manner, with a clear semantics that imposes
deterministic program behavior under all circumstances.
TherearedifferentoptionstosynthesizeanEsterelprogramintoaconcretesystem,e.g.,
software, hardware, and HW/SW co-design implementations. However, these classical
synthesis approaches suffer from the limitations of traditional processors, with their in-
structionsetarchitecturesgearedtowardsthesequentialvon-Neumannexecutionmodel,
or they are very inflexible if HW synthesis is involved.
Recently, another alternative for synthesizing Esterel has emerged, the reactive pro-
cessing approach. Here the Esterel program is running on a processor that has been
developed specifically for reactive systems. However, the main challenge when designing
a reactive architecture is the handling of control.
This thesis presents the Kiel Esterel Processor (KEP). In the KEP, the multi-threaded
reactive architecture is responsible for managing the control flow of all threads. The
KEP Instruction Set Architecture is complete in that it allows a direct mapping of all
Esterel statements onto KEP assembler. It supports Esterel’s concurrency operator ||
in a very precise, direct and efficient way. It also supports full Esterel preemptions,
i.e., the delayed and immediate strong/weak abortion and suspension. All other Esterel
kernel statements, e.g., the Esterel exception, delay, and signal emission, etc., are also
implemented directly and semantically accurate by the KEP.
As the experimental comparison with a 32-bit commercial RISC processor indicates, the
KEPhasadvantagesintermsofmemoryuse, executionspeed, andenergyconsumption.
Another advantage is the predictability of its timing behavior at the program level.
vviContents
Contents v
List of Figures ix
List of Tables xiii
1 Introduction and Motivation 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Research Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Background and Related Work 7
2.1 Implementation Technologies . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Compilation Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Handling Esterel via Reactive Processors . . . . . . . . . . . . . . . . . . 12
3 The KEP Instruction Set Architecture 17
3.1 The Esterel Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Esterel Statements . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 An Example Program . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Design of the Esterel-type Instructions . . . . . . . . . . . . . . . . . . . 30
3.2.1 Handling Concurrency . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Preemption . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3 Handling Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Signal and Schizophrenia . . . . . . . . . . . . . . . . . 35
vvi CONTENTS
3.2.5 Handling Delays. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.6 Summary of Esterel-type Instructions . . . . . . . . . . . . . . . . 37
3.3 Further Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 From Esterel to KEP Assembler . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Code Generation for the KEP – The Compiler’s Perspective . . . 42
3.4.2 EXAMPLE: Code Translation . . . . . . . . . . . . . . . . . . . . 44
3.5 Encoding KEP Instructions . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 The KEP Architecture 53
4.1 The KEP Architecture Overview . . . . . . . . . . . . . . . . . . . . . . 53
4.2 The Reactive Core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.1 The Thread Block . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.2 The Reactive Block . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.3 Decoder & Controller . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3 The Interface Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4 The Data Handling Block . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5 The Tick Manager and Energy Saving . . . . . . . . . . . . . . . . . . . 98
4.6 Putting It All Altogether . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5 Experimental Results 107
5.1 The KEP Evaluation Platform . . . . . . . . . . . . . . . . . . . . . . . . 107
5.1.1 Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.1.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.1.3 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.2 Comparison with Other Execution Platforms . . . . . . . . . . . . . . . . 110
5.3 Evaluation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6 Conclusion and Outlook 123
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2 Recommendations for Further Research . . . . . . . . . . . . . . . . . . . 125CONTENTS vii
A KEP Instruction Set 129
A.1 Esterel-type Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
A.1.1 Preemption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
A.1.2 Exception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
A.1.3 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
A.1.4 Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
A.1.5 Signal Emission and Testing . . . . . . . . . . . . . . . . . . . . . 136
A.1.6 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
A.2 Classical Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
A.2.1 Program and Machine Control . . . . . . . . . . . . . . . . . . . . 142
A.2.2 Boolean Variable Manipulation . . . . . . . . . . . . . . . . . . . 146
A.2.3 Data Transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
A.2.4 Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . 149
A.2.5 Logical Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 153
B An Introduction to the KEP Eva