Pipelined Processor Farms - Structured Design for Embedded Parallel Systems

Contents......Page 14
Foreword......Page 6
Preface......Page 8
Acknowledgments......Page 10
Acronyms......Page 20
Part I: Introduction and Basic Concepts......Page 24
1.1 Overview......Page 26
1.2 Origins......Page 27
1.4 Introduction to PPF Systems......Page 29
1.5 Conclusions......Page 33
Appendix......Page 35
2 Basic Concepts......Page 42
2.1 Pipelined Processing......Page 45
2.2 Pipeline Types......Page 49
2.3 Data Farming and Demand-based Scheduling......Page 52
2.4 Data-farm Performance Criteria......Page 53
2.5 Conclusion......Page 55
Appendix......Page 56
3 PPF in Practice......Page 62
3.1 Application Overview......Page 63
3.2 Parallelization of the Postcode Recognizer......Page 64
3.3 Parallelization of the address verifier......Page 72
3.4 Meeting the Specification......Page 76
Appendix......Page 78
4 Development of PPF Applications......Page 82
4.1 Analysis Tools......Page 83
4.2 Tool Characteristics......Page 84
4.3 Development Cycle......Page 85
4.4 Conclusion......Page 87
Part II: Analysis and Partitioning of Sequential Applications......Page 90
5.1 Confidence Building......Page 92
5.2 Automatic and Semi-automatic Parallelization......Page 94
5.3 Language Proliferation......Page 96
5.4 Size of Applications......Page 97
5.5 Semi-automatic Partitioning......Page 98
5.6 Porting Code......Page 100
5.8 Optimizing Compilers......Page 102
5.9 Conclusion......Page 104
6 Graphical Simulation and Performance Analysis of PPFs......Page 106
6.2 Simulation Implementation......Page 107
6.3 Graphical Representation......Page 109
6.4 Display Features......Page 113
6.5 Cross-architectural Comparison......Page 114
6.6 Conclusion......Page 118
7 Template-based Implementation......Page 120
7.1 Template Design Principles......Page 121
7.2 Implementation Choices......Page 124
7.3 Parallel Logic Implementation......Page 125
7.4 Target Machine Implementation......Page 126
7.5 \'NOW\' Implementation for Logic Debugging......Page 129
7.6 Target Machine Implementations for Performance Tuning......Page 134
7.7 Patterns and Templates......Page 137
7.8 Conclusion......Page 138
Part III: Case Studies......Page 140
8 Application Examples......Page 142
8.1 Case Study 1: H.261 Encoder......Page 143
8.2 Case Study 2: H263 Encoder/Decoder......Page 157
8.3 Case Study 3: \'Eigenfaces\' — Face Detection......Page 164
8.4 Case Study 4: Optical Flow......Page 170
8.5 Conclusion......Page 186
9 Design Studies......Page 188
9.1 Case Study 1: Karhunen-Loéve Transform (KLT)......Page 189
9.2 Case Study 2: 2D- Wavelet Transform......Page 196
9.3 Case Study 3: Vector Quantization......Page 204
9.4 Conclusion......Page 211
10 Counter Examples......Page 214
10.1 Case Study 1: Large Vocabulary Continuous-Speech Recognition......Page 215
10.2 Case Study 2: Model-based Coding......Page 221
10.3 Case Study 3: Microphone Beam Array......Page 227
10.4 Conclusion......Page 231
Part IV: Underlying Theory and Analysis......Page 234
11 Performance of PPFs......Page 236
11.2 Performance Metrics......Page 237
11.3 Gathering Performance Data......Page 245
11.4 Performance Prediction Equations......Page 246
11.5 Results......Page 248
11.6 Simulation Results......Page 250
11.7 Asynchronous Pipeline Estimate......Page 252
11.8 Ordering Constraints......Page 255
11.9 Task Scheduling......Page 260
11.10 Scheduling Results......Page 263
11.11 Conclusion......Page 266
Appendix......Page 267
12 Instrumentation of Templates......Page 272
12.1 Global Time......Page 273
12.3 Local Clock Requirements......Page 274
12.4 Steady-state Behavior......Page 275
12.5 Establishing a Refresh Interval......Page 278
12.6 Local Clock Adjustment......Page 281
12.7 Implementation on the Paramid......Page 282
12.8 Conclusion......Page 284
Part V: Future Trends......Page 286
13 Future Trends......Page 288
13.2 Adapting to Mobile Networked Computation......Page 290
13.3 Conclusion......Page 292
References......Page 294
C......Page 324
F......Page 325
L......Page 326
P......Page 327
S......Page 328
V......Page 329
Z......Page 330