Practical Computing on the Cell Broadband Engine (eBook)

Preface 6
Accompanying Website for this Book 12
Contents 13
List of Tables 21
List of Figures 23
Listings 27
Acronyms 31
Part I Introducing the Cell Broadband Engine 33
Chapter 1 Introduction 35
1.1 About this book 35
1.2 Background of the CBE Architecture and Processor 37
1.3 Design of the Cell Architecture 41
1.4 The Cell as a supercomputer 43
1.5 Major Components of the Cell Broadband Engine 45
1.6 Flex I/O, DDR/XDR, Interrupt Controller 46
1.7 Conclusions 46
Chapter 2 The Power Processing Element (PPE) 48
2.1 PPE: the Control Plane of the CBEA 48
2.2 PPE Problem State Registers 50
2.3 Memory arrays in the CBEA 52
2.4 Viewing the PPE as a dual-core processor: EMT specifics 54
2.5 PowerPC Instruction Set 57
2.6 SPE Memory Management and EA Aliasing 57
2.7 Power Processor Element (PPE) Cache Utilization 58
2.8 Understanding the PPE Pipeline 60
2.9 Measuring and Profiling Application Performance 64
2.10 Conclusion 65
Chapter 3 The Synergistic Processing Element 66
3.1 Introduction to Cell SPE 66
3.2 SPE Local Store 69
3.3 SPU LS Priority 70
3.4 GPRs in the SPE 71
3.5 SPE Intrinsics and Instruction 71
3.6 SPU Instruction Set: Pipelines, Execution Units and Latency 72
3.7 Load/Store Optimization on SPU 75
3.8 Branch Optimization on SPU 78
3.9 Instruction Scheduling 80
3.10 Memory flow 80
3.11 Mailbox Facility 81
3.12 Use SPU Intrinsics with Mailboxes 85
3.13 Synergistic Processor Unit Channels and Memory Flow Controller 87
3.14 SPU Timer and Events 89
3.15 SPE Context on the PPE 89
3.16 Conclusion 89
3.17 What we have not discussed 90
Chapter 4 Element Interconnect Bus 91
4.1 Introduction to the Element Interconnect Bus 91
4.2 Important things to remember about the EIB 95
4.3 Conclusions 96
Chapter 5 Direct Memory Access (DMA) 97
5.1 Introduction to DMA in the Cell Broadband Engine 97
5.2 Conclusions 101
Part II Programming the Cell Broadband Engine 102
Chapter 6 Foundations for Program Development on CBE 104
6.1 Theory of Parallel Programming 104
6.2 The Class NC of complexity analysis 106
6.3 Parallel programming concepts 107
6.4 Introduction to pthreads 108
6.5 Multi-faceted parallelism in the CBE Architecture 113
6.6 Alignment using compiler attributes 113
6.7 OpenMP 115
6.8 Double buffering example 117
6.9 Software Managed Cache 117
6.10 Physical Organization 118
6.11 Things to watch out for 118
6.12 Strategies and Paradigms for Identifying Parallelism 120
6.13 Conclusion 121
Chapter 7 The development environment 122
7.1 How to setup an PS3 for Cell development 122
7.2 Alternatives to installing GNU/Linux on the PS3 123
7.3 The CESOF Format 125
7.4 Basic development environment 127
7.5 Debugging code on the SPU 128
7.6 Conclusions 130
Chapter 8 Hello World 131
8.1 Writing simple programs on the Cell Broadband Engine 131
8.2 SPE Program Development 134
8.3 Using pthread with SPU tasks 136
8.4 Developing applications using libspe2 137
8.5 Measuring Performance using High Resolution Timers 149
8.6 Synchronization 151
8.7 Conclusions 159
Chapter 9 An Overview of the SDK 160
9.1 Major components of the Cell Broadband Engine SDK 3.0 160
9.2 Application programming libraries in the SDK 161
9.3 SPE Runtime Library 161
9.4 SPU Timer Library 162
9.5 Monte-Carlo Library 162
9.6 BLAS Library 163
9.7 LAPACK Library 164
9.8 SIMD Math API and Library 165
9.9 SPU Software Managed Cache 165
9.10 FFT Library 165
9.11 Game Math Library 165
9.12 Image Library 166
9.13 Large Matrix Library 166
9.14 Matrix Library 166
9.15 Synchronization Library 167
9.16 Vector Library 168
9.17 Multiprecision Math Library 168
9.18 ALF Library and Framework 169
9.19 DACS Library and Framework 170
9.20 Conclusions 170
Chapter 10 Basic Algorithms 171
10.1 Some number theoretic problems 171
10.2 Merit Factor of Sequences and Auto-correlation 174
10.3 Computing Greatest Common Divisor (GCD) 181
10.4 Sorting Algorithms 183
10.5 Table lookup 189
10.6 (Perfect) Hash Function 190
10.7 Minimal Perfect Hashing 192
10.8 Implementing minimal perfect hash in the SPU 194
10.9 Using perfect hash functions with large graph clusters 195
10.10 Heap Data Structure 195
10.11 Disjoint Set Union-Find Algorithms 196
10.12 Computing Zech logarithm using SPE in batch mode 198
10.13 Conclusions 201
Chapter 11 Graph Theory on the CBEA 202
11.1 Introduction 202
11.2 Definitions 202
11.3 Graph representation 203
11.4 Minimum Spanning Tree using Kruskal’s Method 206
11.5 Revisiting min-cut using MST and Karger’s Method 213
11.6 Dijkstra’s Algorithms for Shortest Paths 214
11.7 Floyd-Warshall All-pairs shortest-path 217
11.8 Formal definition of APSP (all-pairs shortest-path) 217
11.9 Maximal Independent Set 219
11.10 Approximation algorithm for maximal matching 219
11.11 Partitioning using Simulated Annealing 222
11.12 Simulated Annealing 225
11.13 Partitioning using Spectral Methods 232
11.14 On-line streaming algorithm for graph properties 237
11.15 Conclusion 246
Chapter 12 Alternative methods for parallel programming on SPE 247
12.1 Introduction 247
12.2 NESL: Nested Data Parallel Language 247
12.3 CVL and VCODE: Vector Libraries 250
12.4 A Simplified SPU ISA Simulator 252
12.5 VCODE Compiler 259
12.6 PowerList: Data structure for parallel programming 261
12.8 Tale of Dwarfs 265
12.9 Introduction to Cilk++ 266
12.10 Introduction to Intel Ct 267
12.11 Introduction to RapidMind 267
Chapter 13 Computational Mathematics on the CBEA 269
13.1 Introduction 269
13.2 Calculating PI 269
13.3 Line fitting 271
13.4 Representing Monomials and Polynomials 275
13.5 Evaluating polynomials 279
13.6 SIMD Polynomial evaluation with fixed step 280
13.7 Parallel Polynomial Evaluation 280
13.8 Evaluating Boolean Functions 283
13.9 Parallel Matrix Functions 283
13.10 Solving Equations in a Single Complex Variable 283
13.11 Conclusions 309
Chapter 14 Vector Graphics on SPU 310
14.1 Introduction 310
14.2 Basic Computational Geometry on SPU 310
14.3 Conclusion 322
Chapter 15 Optimizing SPU Programs 323
15.1 Introduction to Program Optimization for Cell 323
15.2 GNU gprof 323
15.3 Branch probability extraction 324
15.4 SPU Assembly Analysis 325
15.5 FDPRPRO: Optimization Tool 328
15.6 Conclusion 330
Part III Case Studies 331
Chapter 16 Line-of-sight Computation 333
16.1 Introduction to the line-of-sight computation 333
16.2 Basic equation for LOS calculation 336
16.3 Watershed analysis using LOS 338
16.4 LOS formulation using Bresenham’s line-drawing for interpolation 338
16.5 SIMD Implementation of line-of-sight algorithm 341
16.6 Watershed Analysis 342
16.7 SPU Implementation 343
16.8 Conclusion 349
Chapter 17 Structure Determination using PDF 350
17.1 Problem of nano-structure determination 350
17.2 Implementation of the ab-initio PDF method 351
17.3 Algorithms and data structures required for the problem 353
17.5 Conclusions 368
Chapter 18 Polytope Enumeration 369
18.1 What is a polytope ? 369
18.2 Examples of polytopes 372
18.4 Experimental Results 383
18.5 Future Work 385
18.6 Current Results 385
18.7 Conclusion 386
Chapter 19 Synthetic Aperture Radar 387
19.1 Introduction 387
19.2 Fundamental principal behind Synthetic Aperture Radar 388
19.3 Problem Statement for SAR Image Processing 389
19.4 Block Adaptive Quantization 390
19.5 Signal processing functions for SAR 393
19.6 Implementation Details 394
19.7 Experimental Results 397
19.8 Conclusions 399
Chapter 20 VLSI Design Automation 400
20.1 CAD of Very Large Scale Integrated Circuits 400
20.2 Algorithmic Design and HDL Capture 401
20.3 Equation Processing 408
20.4 Microword Optimization using Local Search on SPU 414
20.5 Conclusion 418
Chapter 21 Floorplanning: VLSI and other Applications 419
21.1 What is a VLSI floorplan 419
21.2 The sequence-pair data-structure 419
21.3 Use of a floorplan in non-VLSI applications 421
21.4 Implementation of a Sequence-pair based Floorplanner 422
21.5 Conclusions 425
Chapter 22 VLSI Placement 426
22.1 Introduction to VLSI Standard Cell Placement 426
22.2 Reading gate-level BLIF files and making a graph 429
22.3 SPU basic cell placer, using Simulated Annealing 429
22.4 What is the VLSI global routing problem 451
22.5 Conclusion 453
Chapter 23 Power Estimation for VLSI 454
23.1 Introduction 454
23.2 Static Probabilities 455
23.3 Spatial Correlations 457
23.4 A distributed algorithm for signal probability estimation for combinational circuits 458
23.5 Bit-vector implementation of probability polynomials 461
23.6 Applications of PRBC 464
23.7 A Nested Data-Parallel Implementation of the Parker-McCluskey Method 465
23.8 Analysis of our method 467
23.9 PRBC Implementation 468
23.10 Probability Polynomial Evaluation on SPU 475
23.11 Experiments 476
23.12 Conclusion 477
Chapter 24 Concluding Remarks 478
24.1 Progress in small steps 478
24.2 Use of Common Lisp 478
24.3 Future Work 479
24.4 Conclusions 481
24.5 Website Information 481
Appendix A Introduction to Common Lisp 482
A.1 Introduction to Common Lisp 482
A.2 Functions in Common Lisp 483
A.3 File I/O 484
A.4 Conclusion 484
Index 485
References 496