Preface 7
Contents 13
Part I Basic Concepts 19
1 The Nature of Hardware and Software 20
1.1 Introducing Hardware/Software Codesign 20
1.1.1 Hardware 20
1.1.2 Software 22
1.1.3 Hardware and Software 25
1.1.4 Defining Hardware/Software Codesign 28
1.2 The Quest for Energy Efficiency 30
1.2.1 Relative Performance 30
1.2.2 Energy Efficiency 31
1.3 The Driving Factors in Hardware/Software Codesign 32
1.4 The Hardware--Software Codesign Space 34
1.4.1 The Platform Design Space 35
1.4.2 Application Mapping 36
1.5 The Dualism of Hardware Design and Software Design 37
1.6 More on Modeling 40
1.6.1 Abstraction Levels 40
1.7 Concurrency and Parallelism 42
1.8 Summary 45
1.9 Further Reading 45
1.10 Problems 46
2 Data Flow Modeling and Implementation 49
2.1 The Need for Concurrent Models: An Example 49
2.1.1 Tokens, Actors, and Queues 53
2.1.2 Firing Rates, Firing Rules, and Schedules 54
2.1.3 Synchronous Data Flow Graphs 55
2.1.4 SDF Graphs are Determinate 55
2.2 Analyzing Synchronous Data Flow Graphs 56
2.2.1 Deriving Periodic Admissible Sequential Schedules 57
2.2.2 Example: Euclid's Algorithm as an SDF Graph 60
2.3 Control Flow Modeling and the Limitations of Data Flow Models 61
2.3.1 Emulating Control Flow with SDF Semantics 62
2.3.2 Extending SDF Semantics 62
2.4 Software Implementation of Data Flow 64
2.4.1 Converting Queues and Actors into Software 64
2.4.1.1 FIFO Queues 65
2.4.1.2 Actors 66
2.4.2 Sequential Targets with Dynamic Schedule 67
2.4.2.1 Single-Thread Dynamic Schedules 69
2.4.2.2 MultiThread Dynamic Schedules 70
2.4.3 Sequential Targets with Static Schedule 73
2.5 Hardware Implementation of Data Flow 77
2.5.1 Single-Rate SDF Graphs 77
2.5.2 Pipelining 78
2.5.3 Multirate Expansion 80
2.6 Summary 82
2.7 Further Reading 82
2.8 Problems 83
3 Analysis of Control Flow and Data Flow 86
3.1 Data and Control Edges of a C Program 86
3.2 Implementing Data and Control Edges 88
3.3 Contruction of the Control Flow Graph 90
3.4 Construction of the Data Flow Graph 92
3.5 Application: Translating C to Hardware 96
3.5.1 Designing the Datapath 97
3.5.2 Designing the Controller 97
3.6 Single-Assignment Programs 100
3.7 Summary 103
3.8 Further Reading 103
3.9 Problems 104
Part II The Design Space of Custom Architectures 107
4 Finite State Machine with Datapath 108
4.1 Cycle-Based Bit-Parallel Hardware 108
4.1.1 Wires and Registers 109
4.1.2 Precision and Sign 111
4.1.3 Hardware Mapping of Expressions 112
4.2 Hardware Modules 115
4.3 Finite State Machines 117
4.4 Finite State Machines with Datapath 120
4.4.1 Modeling 120
4.4.2 An FSMD is Not Unique 124
4.4.3 Implementation 126
4.5 Simulation and RTL Synthesis of FSMD 128
4.5.1 Simulation 128
4.5.2 Code Generation and Synthesis 130
4.6 Proper FSMD 130
4.7 Language Mapping for FSMD by Example 132
4.7.1 GCD in GEZEL 132
4.7.2 GCD in Verilog 133
4.7.3 GCD in VHDL 135
4.7.4 GCD in SystemC 137
4.8 Summary 139
4.9 Further Reading 139
4.10 Problems 140
5 Microprogrammed Architectures 146
5.1 Limitations of Finite State Machines 146
5.1.1 State Explosion 146
5.1.2 Exception Handling 147
5.1.3 Runtime Flexibility 148
5.2 Microprogrammed Control 149
5.3 Microinstruction Encoding 150
5.3.1 Jump Field 150
5.3.2 Command Field 152
5.4 The Microprogrammed Datapath 154
5.4.1 Datapath Architecture 154
5.4.2 Writing Microprograms 155
5.5 Implementing a Microprogrammed Machine 157
5.5.1 Microinstruction Word Definition 157
5.6 Microprogram Interpreters 164
5.7 Microprogram Pipelining 168
5.7.1 Microinstruction Register 169
5.7.2 Datapath Condition-Code Register 170
5.7.3 Pipelined Next-Address Logic 171
5.8 Picoblaze: A Contemporary Microprogram Controller 171
5.9 Summary 173
5.10 Further Reading 173
5.11 Problems 174
6 General-Purpose Embedded Cores 177
6.1 Processors 177
6.1.1 The Toolchain of a Typical Microprocessor 178
6.1.2 From C to Assembly Instructions 179
6.1.3 Simulating a C Program Executing on a Microprocessor 182
6.2 The RISC Pipeline 185
6.2.1 Control Hazards 186
6.2.2 Data Hazards 188
6.2.3 Structural Hazards 189
6.3 Program Organization 190
6.3.1 Data Types 191
6.3.2 Variables in the Memory Hierarchy 192
6.3.3 Function Calls 195
6.3.4 Program Layout 198
6.4 Analyzing the Quality of Compiled Code 202
6.4.1 Analysis Based on Static Assembly Code 202
6.4.2 Analysis Based on Execution of Object Code 206
6.5 Summary 210
6.6 Further Reading 210
6.7 Problems 211
7 System On Chip 216
7.1 The System-on-Chip Concept 216
7.1.1 The Cast of Players 217
7.1.2 SoC Interfaces for Custom Hardware 218
7.2 Four Design Principles in SoC Architecture 220
7.2.1 Heterogeneous and Distributed Data Processing 220
7.2.2 Heterogeneous and Distributed Communications 221
7.2.3 Heterogeneous and Distributed Storage 222
7.2.4 Hierarchical Control 225
7.3 Example: Portable Multimedia System 226
7.4 SoC Modeling in GEZEL 228
7.4.1 An SoC with a StrongARM Core 229
7.4.2 Ping-Pong Buffer with an 8051 232
7.5 Summary 236
7.6 Further Reading 236
7.7 Problems 237
Part III Hardware/Software Interfaces 239
8 On-Chip Busses 240
8.1 Connecting Hardware and Software 240
8.2 On-Chip Bus Systems 241
8.2.1 Some Existing On-Chip Bus Systems 241
8.2.2 Bus Elements 242
8.2.3 Bus Signals 243
8.2.4 Bus Timing Diagram 244
8.3 Bus Transfers 246
8.3.1 Simple Read and Write Transfers 246
8.3.2 Transfer Sizing and Endianess 247
8.3.3 Improved Bus Transfers 251
8.3.3.1 Pipelined Transfers and Transaction Splitting 251
8.3.3.2 Burstmode Transfers 252
8.4 Multimaster Bus Systems 254
8.4.1 Bus Priority 255
8.4.2 Bus Locking 257
8.5 On-Chip Networks 259
8.6 Summary 262
8.7 Further Reading 263
8.8 Problems 263
9 Hardware/Software Interfaces 267
9.1 The Hardware/Software Interface 267
9.2 Synchronization Schemes 268
9.2.1 Synchronization Concepts 268
9.2.2 Semaphore 270
9.2.3 One-Way and Two-Way Handshake 273
9.2.4 Blocking and Nonblocking Data-Transfer 275
9.3 Memory-Mapped Interfaces 276
9.3.1 The Memory-Mapped Register 276
9.3.2 Mailboxes 279
9.3.3 First-In First-Out Queues 280
9.3.4 Slave and Master Handshakes 281
9.3.5 Shared Memory 282
9.3.6 GEZEL Modeling of Memory-Mapped Interfaces 283
9.4 Coprocessor Interfaces 287
9.4.1 Tight and Loose Coupling 289
9.4.2 The Fast Simplex Link 290
9.4.3 The LEON-3 Floating Point Coprocessor Interface 292
9.5 Custom-Instruction Interfaces 294
9.5.1 ASIP Design Flow 295
9.5.2 Example: Endianess Byte-Ordering Processor 296
9.5.3 Finding Good ASIP Instructions 301
9.6 Summary 305
9.7 Further Reading 305
9.8 Problems 306
10 Coprocessor Control Shell Design 310
10.1 The Coprocessor Control Shell 310
10.1.1 Functions of the Coprocessor Control Shell 310
10.1.2 Layout of the Coprocessor Control Shell 312
10.1.3 Communication-Constrained vs. Computation-Constrained Coprocessors 313
10.2 Data Design 315
10.2.1 Flexible Addressing Mechanisms 315
10.2.2 Multiplexing and Masking 315
10.3 Control Design 317
10.3.1 Hierarchical Control 318
10.3.2 Control of Internal Pipelining 320
10.3.2.1 Control of Linear Pipelines 321
10.3.2.2 Control of Nonlinear Pipelines 322
10.3.2.3 Control Handshakes for Pipelines 323
10.4 Programmer's Model = Control Design + Data Design 324
10.4.1 Address Map 324
10.4.2 Instruction Set 325
10.5 Example: AES Encryption Coprocessor 326
10.5.1 Control Shell Operation 327
10.5.2 Programmer's Model 327
10.5.3 Software Driver Design 330
10.5.4 Control Shell Design 331
10.5.5 System Performance Evaluation 334
10.6 Summary 336
10.7 Further Reading 336
10.8 Problems 337
Part IV Applications 342
11 Trivium Crypto-Coprocessor 343
11.1 The Trivium Stream Cipher Algorithm 343
11.1.1 Stream Ciphers 343
11.1.2 Trivium 345
11.1.3 Hardware Mapping of Trivium 346
11.1.4 A Hardware Testbench for Trivium 350
11.2 Trivium for 8-bit Platforms 350
11.2.1 Overall Design of the 8051 Coprocessor 351
11.2.2 Hardware Platform of the 8051 Coprocessor 352
11.2.3 Software Driver for 8051 356
11.3 Trivium for 32-bit Platforms 360
11.3.1 Hardware Platform Using Memory-mapped Interfaces 361
11.3.2 Software Driver Using Memory-mapped Interfaces 364
11.3.3 Hardware Platform Using a Custom-Instruction Interface 368
11.3.4 Software Driver for a Custom-Instruction Interface 370
11.4 Summary 372
11.5 Further Reading 373
11.6 Problems 373
12 CORDIC Coprocessor 375
12.1 The Coordinate Rotation Digital Computer Algorithm 375
12.1.1 The Algorithm 375
12.1.2 Reference Implementation in C 377
12.2 A Hardware Coprocessor for CORDIC 379
12.2.1 A CORDIC Kernel in Hardware 379
12.2.2 A Control Shell for Fast-Simplex-Link Coprocessors 382
12.3 An FPGA Prototype of the CORDIC Coprocessor 385
12.4 Handling Large Amounts of Rotations 388
12.5 Summary 393
12.6 Further Reading 393
12.7 Problems 394
References 395
Index 399