Encyclopedia of Parallel Computing

Springer Reference......Page 1
Encyclopedia of Parallel\rComputing......Page 4
ISBN 9780387097657......Page 5
Preface......Page 6
Editors......Page 8
List of Contributors......Page 16
History......Page 36
Execution Semantics......Page 37
RPC-Like Messaging......Page 38
Local Synchronization Constraints......Page 39
Encapsulation and Atomicity......Page 40
Location Transparency......Page 41
Implementations......Page 42
Pattern-Directed Communication......Page 43
Bibliography......Page 44
Introduction......Page 46
General-Purpose Multiprocessor Systems......Page 47
Affinity Scheduling and Load Sharing Trade-off......Page 49
Bibliography......Page 50
Comparator Networks for Sorting......Page 51
The Sorting-by-Splitting Approach......Page 52
Approximate Separation via Approximate Halving via Bipartite Expander Graphs......Page 53
The Structure of the Bagging Schedule......Page 54
Argument that the Invariant Is Maintained......Page 55
Bibliographic Notes and Further Reading......Page 57
Introduction......Page 58
Geometric Multigrid......Page 59
Algebraic Multigrid......Page 61
Parallel Algebraic Multigrid......Page 64
Related Multigrid Approaches......Page 66
Bibliography......Page 67
Definition......Page 68
Models......Page 69
Experiments......Page 70
Speedup and Efficiency......Page 71
Algorithm Libraries......Page 72
Allen and Kennedy Algorithm......Page 73
Discussion......Page 74
Bibliographic Notes and Further Reading......Page 76
Definition......Page 77
Lower Bounds......Page 78
Fully Connected Systems......Page 79
Hypercube......Page 80
Bibliography......Page 81
Previous Opteron Generations......Page 82
System-on-a-Chip......Page 83
Delivering More Memory Bandwidth......Page 84
``Barcelona\'\' Core Architecture......Page 85
Virtualization and Rapid Virtualization Indexing......Page 86
Amdahl\'s Argument......Page 87
History......Page 88
Estimates of the ``Serial Fraction\'\' Prove Pessimistic......Page 90
Observable Fraction and Superlinear Speedup......Page 91
System Cost: Linear with the Numberof Processors?......Page 92
Analogies......Page 93
Bibliography......Page 94
Introduction......Page 95
Structure of a Molecular Dynamics Computation......Page 97
The Role of Specialization in Anton......Page 98
The High-Throughput Interaction Subsystem (HTIS)......Page 99
The Flexible Subsystem......Page 101
Anton Performance......Page 102
Future Directions......Page 103
Bibliographic Notes and Further Reading......Page 104
Bibliography......Page 105
Discussion......Page 106
Array Indexing......Page 107
Array Operators......Page 108
Bibliography......Page 109
Introduction to Array Languages......Page 110
Compiler Techniques for Array Languages......Page 111
Consecutive Array Operations......Page 112
Data Access Functions......Page 113
Synthesis of Array Operations......Page 114
Optimizations on Index Ranges......Page 115
Compression Schemes......Page 116
Programming with Sparse Arrays......Page 118
Selection of Compression and Distribution Schemes......Page 119
Related Entries......Page 120
Bibliography......Page 121
Introduction......Page 122
Iterative Algorithms......Page 123
Synchronous Iterations and Their Problems......Page 124
Asynchronous Iterations: Basic Idea and Convergence Issues......Page 125
Asynchronous Communication......Page 126
Two-Stage Iterative Methods and Flexible Communications......Page 127
Bibliography......Page 128
Definition......Page 130
Essentials of Empirical Tuning......Page 131
Methods of Software Adaptation......Page 132
Empirical Tuning in the Rest of the Package......Page 133
Rough ATLAS Timeline Including Stable Releases......Page 134
Bibliography......Page 135
Automatically Tuned Linear Algebra Software (ATLAS)......Page 136
Intellectual Genesis......Page 137
Search......Page 138
Bibliography......Page 139
The BSP Model......Page 142
The LogP Model......Page 144
Bibliographic Notes and Further Reading......Page 146
Introduction......Page 147
Extreme Values of Linear Functions......Page 148
Dependence Concepts......Page 150
Banerjee\'s Test......Page 151
Remarks......Page 152
Bibliography......Page 154
Introduction......Page 155
Bisimulation Equivalence......Page 157
Testing Equivalence......Page 158
Weak Variants of the Equivalences......Page 159
Hierarchy of Weak Equivalences......Page 161
Definition......Page 162
Discussion......Page 163
Beowulf Clusters......Page 164
Bernstein\'s Conditions......Page 165
Bioinformatics......Page 169
Bisimulation Equivalence......Page 171
Non-well-Founded Sets......Page 172
Concurrency......Page 173
Introduction......Page 174
Sorting an Arbitrary Sequence......Page 175
Analysis......Page 176
Lower Bounds......Page 177
Future Directions......Page 178
Bibliographic Notes and Further Reading......Page 179
Bibliography......Page 180
Fundamental Properties......Page 181
Derivation of Adaptive Bitonic Merging......Page 184
A GPU Implementation......Page 187
Outline of the Implementation......Page 188
Preconditioning the Input......Page 189
Timings......Page 190
Bibliographic Notes and Further Reading......Page 191
Introduction......Page 192
Vector–Vector Operations (Level-1 BLAS)......Page 193
Matrix–Vector Operations (Level-2 BLAS)......Page 194
Matrix–Matrix Operations (Level-3 BLAS)......Page 195
PLAPACK......Page 196
Bibliographic Notes and Further Reading......Page 197
Blocking......Page 199
Background and Motivation......Page 200
Configuration......Page 201
Processor Elements......Page 202
VLSI: Programmable Interconnect......Page 203
Architecture: The Pringle......Page 204
Software: Poker......Page 205
Algorithms: Simple......Page 206
Theory: Graphs......Page 207
Related Entries......Page 209
Blue Gene/P......Page 210
Introduction......Page 211
PC-Based Prediction Schemes......Page 212
Global History Predictors......Page 213
Toward Using Very Long Global History......Page 214
Predicting Indirect Branch Targets......Page 215
Conclusion......Page 216
Definition......Page 217
Example......Page 218
Application to Superlinear Speedup......Page 219
Bibliography......Page 220
Tree-Based Broadcast Algorithms......Page 221
Pipelining......Page 222
Simultaneous Trees......Page 223
Composing from Other Collective Communications......Page 224
Bibliographic Notes and Further Reading......Page 225
Bibliography......Page 226
The BSP Model......Page 227
BSP vs Traditional Parallel Models......Page 228
Memory Management......Page 229
Basic Algorithms......Page 230
The BSPlib Standard......Page 231
Bibliography......Page 232
Bulk Synchronous Parallelism (BSP)......Page 234
Basics of Bus Design......Page 235
Case Study: Snooping-Based Cache Coherence Protocols......Page 236
Bus Scalability......Page 237
Crossbars......Page 238
Bibliographic Notes and Further Reading......Page 239
Butterfly......Page 240
The Initial Design of C*......Page 242
The Revised Design of C*......Page 244
Cache Coherence and Memory Consistency......Page 247
Snoopy Cache Coherence......Page 248
Example: An Enhanced MESI Cache Coherence Protocol......Page 249
Broadcast-Based Cache Coherence Versus Directory-Based Cache Coherence......Page 250
Definition......Page 251
Finding a Memory Line......Page 252
Flat COMA......Page 253
Bibliography......Page 254
Introduction......Page 255
Outline of the Algorithm......Page 258
Parallelization......Page 259
Introduction......Page 262
Machine Organization of Cedar......Page 263
Programming Cedar......Page 266
Definition......Page 269
Cell Broadband Engine......Page 270
Cell B.E.-Based Systems......Page 271
Programming Cell......Page 272
Bibliography......Page 275
Definition of Cellular Automata......Page 276
Wolfram Rule Scheme......Page 277
HPP Lattice Gas......Page 278
FHP Rules......Page 279
Self-organized Criticality: Forest Fire Model......Page 280
Parallel Implementation......Page 281
References......Page 282
Bibliography......Page 283
History......Page 284
Global-View Abstractions......Page 285
Data Parallelism......Page 286
Locales......Page 287
Task Parallelism......Page 288
Future Directions......Page 289
Bibliography......Page 290
Programming Model in Abstract......Page 291
Chare-arrays and Iterative Computations......Page 292
Supporting Task Parallelism with Seed Balancers......Page 293
Fault Tolerance......Page 294
Code Example......Page 295
Languages in the Charm Family......Page 297
Availability and Usage......Page 298
Definition......Page 299
System-Level Checkpointing......Page 300
Trade-offs......Page 301
Checkpointing in Shared Memory Applications......Page 302
Coordinated Checkpointing......Page 303
Uncoordinated Checkpointing......Page 304
Time Sharing of Large-Scale Resources......Page 305
Exploration of Alternate Executions......Page 306
Bibliography......Page 307
Definition......Page 308
Introduction......Page 309
The Origins of Cilk......Page 310
Optimization and Enhancement......Page 311
Research at MIT......Page 312
The Dag Model for Multithreading......Page 313
The Span Law......Page 314
Performance Bounds......Page 315
Work Stealing......Page 316
Stacks and Cactus Stacks......Page 317
Reducer Hyperobjects......Page 318
Bibliography......Page 321
Cilk-1......Page 323
Introduction and Overview......Page 324
Motivation......Page 325
Software Architecture......Page 326
Exploratory Period: Before 1980......Page 327
Enabling Period: 1980–1992......Page 328
Classical Period: 1993–2004......Page 329
Advanced Period: 2005 to Present (and Beyond)......Page 330
Bibliography......Page 331
Chronology......Page 332
Cm* Architecture Evolution......Page 333
Cm* Architecture......Page 334
Cm\'s and Slocals......Page 335
The Interface Between Kmap and Computer Module......Page 336
Communication with Cm*......Page 337
Bibliography......Page 338
Execution model......Page 339
Writing Code for the Coarray Model......Page 340
Abstract Maps......Page 341
Blocked Vectors......Page 343
Application to Partial Differential Equations......Page 344
Definition......Page 345
Representing Statement Instances: Iteration Domains......Page 346
Representing Order and Placement: Mapping Functions......Page 347
Putting Everything Together......Page 348
Fourier–Motzkin Elimination-Based Scanning Method......Page 349
QRW-Based Scanning Method......Page 350
Related Entries......Page 352
Definition......Page 353
Algorithm 1......Page 354
Classification of Collective Operations......Page 355
Commonly Used Collective Communications......Page 356
A Motivating Example (continued)......Page 358
Message-Passing Interface (MPI)......Page 359
Bulk Synchronous Processing Libraries......Page 360
Bibliographic Notes and Further Reading......Page 361
Introduction......Page 362
Adapter-Based Support......Page 363
InfiniBand Collective Offload......Page 364
Support Through Dedicated Networks......Page 365
Collectives Today......Page 366
Bibliography......Page 367
Searching for All Feasible Solutions......Page 369
Parallelization......Page 370
Searching for Any Feasible Solution......Page 371
Branch-and-Bound......Page 372
Bidirectional Search......Page 373
Alpha-Beta Pruning......Page 374
AND-OR Tree Search......Page 375
Community Climate Model (CCM)......Page 376
Introduction......Page 377
Terminology......Page 378
Community Atmosphere Model......Page 379
Community Land Model......Page 381
Parallel Ocean Program......Page 382
Community Ice Code......Page 383
Coupler......Page 384
Bibiographic Notes and Further Reading......Page 385
Community Earth System Model (CESM)......Page 386
Introduction......Page 387
Simple Example......Page 388
Performance Model......Page 389
Application Architectures......Page 391
Summary......Page 392
Bibliography......Page 394
Rasterization......Page 395
Ray Tracing......Page 396
Micropolygons......Page 397
Bibliography......Page 398
Introduction......Page 399
Collections Indexed by Tags......Page 400
Example......Page 401
Mapping to Target Platforms......Page 403
Related Work......Page 404
Bibliography......Page 405
Concurrent ML Basics......Page 406
First-Class Synchronous Operations......Page 407
Implementations......Page 410
Bibliography......Page 411
Congestion Basics......Page 413
Congestion Impact on Network Performance......Page 415
Network Overdimensioning......Page 417
Reactive Techniques......Page 418
HOL Blocking Elimination Techniques......Page 419
Future Directions......Page 420
Bibliography......Page 421
Origins......Page 422
Connection Machine Model CM-1......Page 423
Connection Machine Model CM-2......Page 426
Connection Machine Model CM-5......Page 429
Bibliography......Page 432
Discussion......Page 435
Bibliography......Page 437
Discussion......Page 438
Introduction......Page 441
Branch Condition Encoding......Page 442
Number Representations......Page 443
Instruction Set Listing......Page 444
Functional Units......Page 445
Scoreboard Unit......Page 446
Bibliography......Page 448
Definition......Page 449
Historical Performance Trends......Page 450
Description of the Dodge Neon Benchmark......Page 453
The Transition from Vector Systems to Massively Parallel Systems......Page 454
The Cray T3E......Page 455
Global Memory......Page 457
E-Registers......Page 458
Network......Page 459
Technology......Page 460
Historical Perspective......Page 461
The Evolution of Microkernels......Page 462
Serverization......Page 463
Checkpoint/Restart......Page 467
OS Jitter......Page 468
Programming Models......Page 470
SHMEM......Page 471
Language-Based Global-Address-Space Models......Page 472
The User Experience......Page 473
The T3E Contribution......Page 475
Definition......Page 476
Introduction and Historical Perspective: The Rise, Domination, and Decline of Cray Vector Systems......Page 477
Pipelining and Vector Processing......Page 479
Advantages of Vector Processors......Page 480
Cray XMP2/4......Page 483
Cray T3D MPP......Page 484
Cray SV1/32......Page 485
Cray X1......Page 486
Bibliographic Notes and Further Reading......Page 487
Introduction......Page 488
Threadstorm......Page 489
Programming Model......Page 490
Scorpio......Page 491
Synonyms......Page 492
Discussion......Page 505
Routing......Page 506
Avoiding Deadlock in the Presence of Faults and Turn Constraints......Page 507
SeaStar Router Microarchitecture......Page 508
Key Parameters Associated with Age-Based Arbitration......Page 510
Related Entries......Page 511
Crossbar......Page 512
Process Language......Page 513
Process Semantics......Page 514
Tools and Applications......Page 515
Discussion......Page 516
Bibliography......Page 517
Instruction Cache Group......Page 518
A-Switch......Page 519
Single-Step......Page 520
Mechanical Package......Page 521
Appendix......Page 522
Definition......Page 523
System Architecture......Page 524
Cydra 5 Numeric Processor......Page 525
Specialized Loop Control......Page 527
Cydra 5 Memory......Page 528
Cydra 5 Compiler Technology......Page 529
Bibliographic Notes and Further Reading......Page 531
Bibliography......Page 532
Physical Layout......Page 534
Energy......Page 535
Related Entries......Page 536
Notation Needed by Data Distribution......Page 537
Block Distribution......Page 538
Block-Cyclic......Page 539
Iteration Space Partitioning......Page 540
Partitioning on Subscript Expressions in Many Variables......Page 541
Bibliography......Page 542
Static Data Flow Architecture......Page 543
Dynamic Data Flow Architecture......Page 544
Future Prospects......Page 545
Bibliography......Page 546
Definition......Page 547
Basic Simple DFGs......Page 548
Compound Simple DFGs......Page 549
The Apply Actor......Page 550
Applications......Page 551
Bibliography......Page 552
Association Rule Mining......Page 553
Classification......Page 555
Clustering......Page 556
Bibliographic Notes and Further Reading......Page 557
Bibliography......Page 558
Example......Page 559
Deadlock Detection, Prevention, and Avoidance......Page 560
Distributed Deadlock......Page 561
Overview......Page 562
The Debugging Process......Page 563
Breakpointing in Parallel Programs......Page 565
Parallel Debugging Tools......Page 566
Future Directions......Page 568
Bibliography......Page 569
Background for Alpha......Page 570
Alpha Architecture......Page 572
Hardware Implementations......Page 573
EV4: First Commercially Available Design......Page 574
EV45: Compaction of EV4 into .5bold0mu mumu No Author Given CMOS Technology......Page 575
EV6: Speed Demon and Brainiac......Page 576
EV7: Integrating System Functions......Page 577
EV8: Araña......Page 578
Bibliography......Page 579
Process Execution Modules......Page 580
Shared Memory......Page 581
Software......Page 582
Bibliography......Page 583
Nonsymmetric Systems......Page 584
Step 2:......Page 585
Bibliography......Page 586
Set Abstractions......Page 587
Sets of Statement Instances......Page 588
Dependence Abstractions......Page 589
Conclusion......Page 590
Dependence Cone......Page 591
Bernstein\'s Conditions......Page 592
Scalars, Arrays, and Beyond......Page 593
Dependence Tests......Page 594
Dependence Direction Vectors......Page 595
Definition......Page 596
Internal Determinacy......Page 597
Determinacy in Other Parallel Programming Models......Page 598
Determinate Parallel Execution......Page 599
Determinism......Page 600
Regions and Effects......Page 601
Region Parameters......Page 602
Region Path Lists (RPLs) and Nested Effects......Page 603
Arrays......Page 604
Commutativity Annotations......Page 605
Controlled Nondeterminism......Page 606
Related Entries......Page 607
Distributed Memory Computers......Page 608
Historical Background......Page 609
Architecture......Page 610
Software......Page 611
Related Entries......Page 612
Definition......Page 613
Domain Decomposition for PDEs......Page 614
Number of Subdomains......Page 615
Partitioning Algorithms......Page 616
Dynamic Approaches......Page 617
Schur Complement–Based Approaches......Page 618
Schwarz Alternating Procedures......Page 619
Application Areas......Page 620
Bibliography......Page 621
Introduction......Page 622
DLPAR Addition of a CPU......Page 623
DLPAR Addition of a Memory Block (LMB)......Page 624
DLPAR of I/O Slots......Page 625
DLPAR-Safe, DLPAR-Aware, and DLPAR-Friendly Programs/Applications......Page 626
Dynamic Reconfiguration......Page 627
Hardware......Page 628
Operating System......Page 629
Parallel File System......Page 630
Job Scheduling......Page 631
Introduction......Page 633
Basic Eden Constructs......Page 634
Defining Non-hierarchical Process Networks in Eden......Page 635
Grace......Page 636
Algorithmic Skeletons......Page 637
EdenTV – The Eden Trace Viewer Tool......Page 639
Future Directions......Page 640
Bibliographic Notes and Further Reading......Page 641
Bibliography......Page 642
Eigenproblems.......Page 643
The Symmetric Eigenvalue Problem......Page 644
Parallel Jacobi algorithms.......Page 645
Parallel Sturm sequences.......Page 646
Parallel Jacobi algorithms for SVD.......Page 647
Bidiagonalization of a matrix by Householder reductions.......Page 648
Bibliography......Page 649
Design Principles......Page 650
Data Speculation......Page 651
Combining Speculation and Predication......Page 653
Predication Support......Page 654
Register Structure......Page 655
Bibliography......Page 656
Introduction......Page 657
System Topology......Page 658
System Software......Page 659
Application Programming with the EGPA Monitor......Page 660
MEMSY......Page 663
Exemplary Applications......Page 664
Bibliography......Page 665
Introduction......Page 666
Collision Sense Multiple Access with Collision Detection......Page 667
The First Ethernet, and the First Commercial Ethernet Success......Page 668
CSMA/CD Ethernet Modeling and Problems......Page 669
Switched Ethernet......Page 670
Ethernet and Beyond......Page 671
Exaop Computing......Page 672
The Importance of Exascale......Page 673
The Challenges of Exascale......Page 674
Memory......Page 675
Packaging......Page 676
Usability......Page 677
Bibliography......Page 678
Extensional Equivalences......Page 679
Introduction......Page 680
Threats......Page 681
Fault Removal......Page 683
Recovery Blocks......Page 684
N-Self-Checking Programming......Page 685
Introspection-Based Adaptive Fault Tolerance......Page 687
Example Problems......Page 688
Checkpointing and Rollback Recoveryin Message-Passing Systems......Page 689
Exception Handling......Page 690
Bibliography......Page 691
Introduction......Page 693
FFTs: Representation......Page 694
Iterative FFTs......Page 696
Recursive FFT Algorithms......Page 699
Other FFT Topics......Page 704
Bibliography......Page 705
Introduction......Page 706
Data Distribution......Page 707
Consistency......Page 708
Underlying Storage Abstraction......Page 709
Metadata Storage and Access......Page 710
Fault Tolerance......Page 711
Parallel File System Interfaces......Page 712
Current Parallel File Systems......Page 713
Fixed-Size Speedup......Page 714
Introduction......Page 715
Software and Performance......Page 716
FPS-264......Page 717
Types of Flow Control......Page 718
Flow Control Versus Switching......Page 719
Impact of Flow Control and Buffer Size......Page 720
Link-Level Flow Control......Page 721
End-to-End Flow Control......Page 723
Introduction......Page 724
SISD: Single Instruction, Single Data Stream......Page 725
Scalar (Including Pipelined) Processors......Page 727
VLIW Processors......Page 728
Vector Processors......Page 729
MIMD: Multiple Instruction, Multiple Data Stream......Page 730
Related Entries......Page 731
Introduction......Page 732
The Database......Page 733
Database Design......Page 734
Query Database......Page 735
Distributed Memory Parallelizer......Page 736
Future Directions......Page 737
Bibliography......Page 738
Introduction......Page 739
Overview......Page 740
Overview......Page 741
Examples......Page 742
Overview......Page 743
Bibliographic Notes and Further Reading......Page 744
Bibliography......Page 745
Fortran 90......Page 746
Fortran 2008......Page 747
Array Variables......Page 748
Elemental Procedures......Page 749
Allocatable Arrays......Page 750
Pure Procedures......Page 751
Coarrays (Fortran 2008 Only)......Page 752
Design Principles......Page 753
Syntax......Page 754
Type System......Page 755
Functions and Methods......Page 756
Parametric polymorphism (or Generic types and functions)......Page 758
Parallelism......Page 759
Components and APIs......Page 760
Innovations......Page 761
Influences from Other Programming Languages......Page 768
Future Directions......Page 769
Synonyms......Page 770
FACOM VP100/200 Series......Page 771
Numerical Wind Tunnel......Page 774
FUJITSU VPP500......Page 775
VPP300/VPP700/VPP5000 Series......Page 776
Conclusion......Page 777
Bibliography......Page 778
Introduction......Page 779
Data Parallel Languages......Page 780
Dataflow Languages......Page 781
Parallel Functional Languages Today......Page 782
Bibliography......Page 783
Introduction......Page 784
Task Scheduling......Page 785
Deterministic Futures in Imperative Languages......Page 786
Bibliography......Page 787
Introduction......Page 790
Algorithmic Formulations of Genome Assembly......Page 792
Parallelization for the Overlap Graph Model......Page 794
The cluster-then-assemble Approach......Page 795
Short Read Assembly......Page 797
Parallel De Bruijn Graph Construction and Compaction......Page 799
Incorporation of Distance Constraints Using Pair-End Information......Page 800
Future Trends......Page 801
Acknowledgment......Page 802
Definition......Page 803
History and Development of GpH......Page 804
Lazy Thread Creation......Page 805
The seq Primitive......Page 806
Evaluation Strategies......Page 808
Visualizing the Behavior of GpH Programs......Page 809
GdH and Mobile Haskell......Page 811
Future Directions......Page 812
Bibliography......Page 813
Introduction......Page 814
Basic Global Arrays......Page 815
Discussion on the Example Program......Page 816
Global Arrays Concepts......Page 819
Historical Development and Comparison with Other Programming Models......Page 820
Comparison with Other Programming Models......Page 821
Bibliography......Page 822
Introduction......Page 823
History......Page 824
Related Projects......Page 827
LSI Economics and GRAPE......Page 828
Future of Special-Purpose Processors......Page 829
Bibliography......Page 830
Divide and Conquer......Page 831
Classical Algorithms......Page 832
Graph Workload......Page 833
Adapting to the Available Parallelism......Page 834
Reducing Synchronization......Page 835
Algorithmic Optimizations......Page 836
Implementation on Distributed Memory Machines......Page 837
Bibliography......Page 838
Parallel Computing Applications of Graph Partitioning......Page 840
Graph Partitioning Algorithms for Parallel Computing......Page 841
Hypergraph Partitioning......Page 842
Graphics Processing Unit......Page 843
History......Page 844
Modeling the Earth\'s Climate System......Page 845
Climate Model Requirements......Page 846
A Science Optimized Processor Design......Page 847
Hardware/Software Codesign Strategy......Page 848
Hardware Support for New Programming Models......Page 851
Fault Resilience......Page 852
Bibliography......Page 853
Graphical Explanation......Page 854
The Rise of Microprocessor-Based Systems......Page 855
Observable Fraction and Scaling Models......Page 856
Commuting Time......Page 857
Biological Brains......Page 858
Bibliography......Page 859
Gustafson–Barsis Law......Page 860
Data Model......Page 862
Examples of Using HDF5......Page 864
Tools......Page 865
Parallel File I/O......Page 866
Future Directions......Page 867
High-Performance I/O......Page 868
Case Study: Smith–Waterman Algorithm......Page 869
Sequence Database Search......Page 871
Case Study: mpiBLAST......Page 873
Multiple Sequence Alignment......Page 874
Case Study: ClustalW......Page 875
Case Study: T-Coffee......Page 876
Bibliographic Notes and FurtherReading......Page 877
Bibliography......Page 878
Definition......Page 879
The TOP500 Influence......Page 880
Short History of the Benchmark......Page 881
Benchmark Submission Procedures and Results......Page 883
Bibliography......Page 884
Discussion......Page 885
Hybrid Programming With SIMPLE......Page 886
SMP Node......Page 889
The Alltoall Primitive......Page 890
Data Parallel......Page 891
Memory Management......Page 892
A Possible Approach......Page 894
Hypercube......Page 895
History......Page 896
Algorithms with Pure Hypercube Communication Patterns......Page 898
Algorithms with Next Neighbor Communication Pattern......Page 899
Meshes as a Generalization of Binary Hypercubes into k-ary n-Cubes......Page 900
Mapping Hypercube Algorithms into Meshes and Tori......Page 901
Hypercube Machine Prototypes and Products......Page 903
Research Conferences on Hypercubes......Page 904
Bibliography......Page 905
Formal Definition of Hypergraph Partitioning......Page 906
Sparse Matrix Partitioning......Page 907
Three Main Models for Matrix Partitioning......Page 908
Some Other Methods for Matrix Partitioning......Page 909
Some Other Applications of Hypergraph Partitioning......Page 912
Bibliographic Notes and Further Reading......Page 915
Hyperplane Partitioning......Page 916
HyperTransport Links......Page 917
HyperTransport Packets......Page 919
Sized Write Transaction......Page 920
Virtual Channels and Flow Control in HyperTransport......Page 921
Improving the Scalability of HyperTransport......Page 922
Bibliography......Page 924
Compute Section......Page 926
Host Section......Page 929
Blue Gene System Software......Page 930
Overall Operating System Architecture......Page 931
The Compute Node Kernel......Page 932
System Software for the Service Node......Page 933
Blue Gene and Its Impact on Science......Page 934
Definition......Page 935
Instruction-Level Parallelism......Page 936
Independent Instruction Facilities......Page 937
Load/Store Architecture......Page 938
Thread Level Parallelism......Page 939
TLP Support in Power7 Processor......Page 940
Bibliographic Notes......Page 941
Introduction......Page 942
Hardware Architecture......Page 943
Software Architecture......Page 944
Bibliography......Page 946
Instruction Processing......Page 947
The Technology......Page 948
History......Page 949
Software......Page 950
Assessment......Page 951
Introduction......Page 952
The Multilevel Method......Page 953
Mathematical Background......Page 954
The Parallelization Approach......Page 955
Numerical Example......Page 959
Bibliographic Notes and Further Reading......Page 960
Implementations of Shared Memory in Software......Page 961
Topology and Network Components......Page 962
Messaging......Page 964
Network Layer Features......Page 965
Transport Layer Features......Page 966
Management and Services......Page 967
InfiniBand Today......Page 968
Bibliographic Notes and Further Reading......Page 969
Instruction-Level Parallelism......Page 970
Microprocessor components......Page 971
Instruction Level Parallelism......Page 973
History of x86 Processors......Page 974
Pipeline Structure......Page 976
Cache Subsystem......Page 977
New Developments......Page 978
Introduction......Page 979
Uninitialized Memory Accesses......Page 980
Atomicity Violations......Page 981
Intel® Parallel Inspector Defect Model......Page 982
Implementation......Page 983
Introduction......Page 984
Workflow......Page 985
Profiling OpenMP......Page 986
Timeline Pane......Page 987
Profile Pane......Page 988
Excess Hold Times and Lock Convoys......Page 989
Introduction......Page 990
Parallel Algorithms......Page 991
Reduction and Scan......Page 992
Task Scheduler......Page 993
Exceptions and Cancellation......Page 995
Task Groups......Page 996
Memory Allocator......Page 997
Related Entries......Page 998
Introduction......Page 999
Shared Medium Networks......Page 1000
Direct Networks......Page 1001
Indirect Networks......Page 1003
Routing......Page 1005
Deadlock and Livelock......Page 1006
Deadlock-Free Routing......Page 1007
Bibliographic Notes and Further Reading......Page 1009
Definition......Page 1010
Hardware Environments......Page 1011
Overview of Parallel Application Execution and I/O Scenario......Page 1012
HPC I/O Access Patterns......Page 1013
POSIX I/O......Page 1014
Parallel I/O Libraries......Page 1015
Parallel I/O Today......Page 1016
Bibliographic Notes and Further Reading......Page 1017
Bibliography......Page 1018
Isoefficiency......Page 1019
Overview......Page 1020
Spin Glasses......Page 1021
Monte Carlo Simulations of Spin Glasses......Page 1022
JANUS: The Architecture......Page 1023
JANUS Performance......Page 1025
Future Directions......Page 1026
Definition......Page 1027
Transformation......Page 1028
Copy Semantics for Local Object Arguments in Remote Method Invocations......Page 1029
Collectively Replicated Objects......Page 1030
Bulk Synchronous Collective Synchronization......Page 1031
Definition......Page 1032
Introduction......Page 1033
Node Allocation......Page 1034
Space and Time-Sharing......Page 1035
Bibliography......Page 1036
KSR......Page 1038
Discussion......Page 1040
Definitions......Page 1041
Layouts......Page 1042
Skewing Schemes: Matrix Processing......Page 1043
Reordering......Page 1044
A solution based on fundamental computer science.......Page 1045
Supported operations.......Page 1046
Compatibility with LAPACK.......Page 1047
SuperMatrix.......Page 1048
Introduction......Page 1049
Tuple Space Operations......Page 1050
Master/Worker Pattern......Page 1051
Implementations......Page 1052
Open Linda......Page 1053
Key Characteristics of Linda, and Comparison to Other Approaches......Page 1054
History......Page 1055
Definition......Page 1056
Origins of Dense Linear Systems......Page 1057
Discretized Partial Differential Equations......Page 1058
Basic Iteration Procedure......Page 1059
Bibliography......Page 1060
Dense Matrix Computations......Page 1061
General scheme.......Page 1062
The sequential algorithm.......Page 1063
Dense matrix.......Page 1064
Gram-Schmidt procedures.......Page 1065
Householder QR with column pivoting.......Page 1066
Bibliography......Page 1067
Discussion......Page 1068
Detailed Operation Counts......Page 1069
Related Entries......Page 1070
Discussion......Page 1071
Discussion......Page 1073
Example......Page 1074
Bibliographic Notes and Further Reading......Page 1075
Discussion......Page 1076
Related Entries......Page 1077
Discussion......Page 1078
Classifying Load Balancers......Page 1079
Recursive Bisection......Page 1081
Graph Partitioning......Page 1082
Software Frameworks......Page 1083
Task Scheduling Methods......Page 1084
Bibliography......Page 1085
Introduction......Page 1086
Network Locality......Page 1087
Program Transformations for Exploiting Caches......Page 1088
Cache-Oblivious Programs......Page 1089
Related Entries......Page 1090
Logarithmic-Depth Sorting Network......Page 1091
Logic Programing......Page 1092
Operational View and Comparison with Other Programming Paradigms......Page 1093
And-Parallelism......Page 1094
Independent And-Parallelism......Page 1095
Dependent And-Parallelism......Page 1097
Or-Parallelism......Page 1098
Automatic Detection of Parallelism......Page 1099
Syntax and (Intuitive) Semantics......Page 1100
Variations on Semantics......Page 1101
Eventual and Atomic Tells......Page 1102
Definition......Page 1103
Mathematical Preliminaries......Page 1104
Unimodular Transformations......Page 1105
Inner Loop Parallelization......Page 1106
Outer Loop Parallelization......Page 1108
Echelon Transformation......Page 1110
Bibliography......Page 1113
Types of Parallel Loops......Page 1114
Doall Loops......Page 1115
Forall Loops......Page 1116
Variables in Parallel Loops......Page 1117
Parallel Loops in OpenMP......Page 1118
Parallel Loops in Intel(R) Threading Building Blocks......Page 1120
Bibliographic Notes and Further Reading......Page 1121
LU Factorization......Page 1122
Introduction......Page 1124
Platforms for Scalable Data Management and Analysis......Page 1125
Architectural Resources......Page 1126
Stochastic Decomposition......Page 1127
Exploiting Priority Structural Properties......Page 1128
Bibliography......Page 1129
Rewriting Logic and Maude in a Nutshell......Page 1130
Rewriting Logic Semantics of Programming Languages......Page 1135
Maude\'s Implementation and Formal Environment......Page 1136
Definition......Page 1137
Hybrid Machines......Page 1138
Sun SPARC-Based Machines......Page 1139
Direct User Space Communication......Page 1140
Network Collective Operations......Page 1141
Definition......Page 1142
Relaxed Memory Models......Page 1143
Bibliography......Page 1144
Introduction......Page 1145
DRAM Basics......Page 1147
Amount of Memory......Page 1148
Future Directions......Page 1149
Bibliographic Notes and Further Reading......Page 1150
Message-Passing Performance Models......Page 1151
METIS......Page 1152
Alternate Partitioning Objectives......Page 1153
Support for Multiphase and Multi-physics Computations......Page 1154
Computing a Fill-Reducing Orderingof a Sparse Matrix......Page 1155
Partitioning a Graph......Page 1156
Partitioning Adaptively Refined Meshes......Page 1157
Related Entries......Page 1158
Introduction......Page 1159
OS and Hardware Metrics......Page 1160
Parallelism Metrics......Page 1161
Speedup......Page 1162
Benchmark Metrics......Page 1163
Summary......Page 1164
Physics Goals......Page 1165
Characteristics of Lattice QCD as a Computational Problem......Page 1166
Coding Style and Examples......Page 1167
Data Types......Page 1168
Site Structure......Page 1169
Macros......Page 1170
Gathers......Page 1171
Assembly Code Options......Page 1172
Public Availability of Gauge Configurations: Gauge Connection, ILDG......Page 1173
Bibliography......Page 1174
Volunteer Computing......Page 1175
Cluster Computers......Page 1176
Symmetric Multi Processors......Page 1177
Network......Page 1178
Network Interface......Page 1179
Remote Data Access......Page 1180
Application Type......Page 1181
Usage......Page 1182
Bibliographic Notes and Further Reading......Page 1183
Models for Algorithm Design and Analysis......Page 1184
Overview......Page 1185
Representative Models......Page 1187
Bibliography......Page 1192
Modulo Scheduling and Loop Pipelining......Page 1193
Preliminaries......Page 1194
Modulo Scheduling Algorithm......Page 1195
Remarks: Infeasibility of MII......Page 1198
Limitations......Page 1199
Enhanced Modulo Scheduling......Page 1200
Modulo Scheduling with Multiple Initiation Intervals......Page 1201
Kernel Recognition......Page 1202
OPT: Optimal Loop Pipelining of Innermost Loops......Page 1203
Bibliography......Page 1207
Definition......Page 1208
Auxiliary and Private Variables......Page 1209
Example......Page 1210
Other Signaling Strategies......Page 1211
Synonyms......Page 1212
A Self-fulfilling Prophecy......Page 1213
Moore\'s Law and Software......Page 1214
Implications for Parallel Computing......Page 1215
The ASCI Program and Other ``Above Trend\'\' Efforts......Page 1216
Design Effort Limits......Page 1217
Related Entries......Page 1218
MPI-1......Page 1219
Major Features of MPI-1......Page 1221
Major Features of MPI-2......Page 1223
The Future of MPI......Page 1224
Bibliography......Page 1225
Access Pattern Expression......Page 1226
Data Access Functions......Page 1227
File Consistency......Page 1229
File Hints for Performance......Page 1231
Bibliography......Page 1233
Introduction......Page 1234
The Trace Machines......Page 1235
Trace Scheduling Compiler......Page 1239
Bibliography......Page 1243
Finite-Element Analysis-Based Formulation......Page 1244
Assembled Matrix Point of View......Page 1246
Factorization......Page 1247
Parallel Execution......Page 1249
Bibliography......Page 1250
Introduction......Page 1251
Basic Concurrency Constructs......Page 1252
Speculative Computing and Sponsors......Page 1253
Storage Management......Page 1254
Debugging Tools......Page 1255
Bibliographic Notes and Further Reading......Page 1256
Multistage Interconnection Networks......Page 1257
Classification of Multithreading Techniques......Page 1258
Benefit of Multithreaded Processors......Page 1259
Fine Grain Multithreading (FGMT)......Page 1260
Coarse Grain Multithreading......Page 1261
Simultaneous Multithreading Commercial Processors......Page 1262
Related Entries......Page 1265
Bibliography......Page 1266
Introduction......Page 1267
General Comments......Page 1268
Analysis Step......Page 1269
Factorization Step......Page 1270
Origins of MUMPS......Page 1271
Further Comments......Page 1272
MUMPS......Page 1273
History......Page 1274
Switches......Page 1275
Network Interface Cards......Page 1276
Communication-Layer Design Issues......Page 1279
Bibliographic Notes and Further Reading......Page 1281
Bibliography......Page 1282
Biomolecular Simulation......Page 1284
Parallel Design and Implementation......Page 1285
Performance......Page 1287
Future Directions......Page 1288
Definition......Page 1289
Discussion......Page 1290
The Original Eight Benchmarks......Page 1291
Evolution of the NAS Parallel Benchmarks......Page 1293
Computational Techniques and Algorithmic Considerations......Page 1294
Parallelization Challenges......Page 1295
Interactions in N-Body Simulations......Page 1296
Computation of Short-Range Terms......Page 1297
Computation of Long-Range Terms......Page 1298
NAMD......Page 1300
Accelerated Dynamics......Page 1301
History of the Supercomputer SX Series......Page 1303
SX-9 Architecture......Page 1304
Processor......Page 1305
6-way super-scalar configuration......Page 1306
Main Memory Unit (MMU)......Page 1307
Outline of the SUPER-UX Operating System for the SX-9......Page 1308
Application Program and Performance......Page 1309
Concluding Remarks......Page 1311
Bibliographic Notes and Further Reading......Page 1312
Parallel Operations on Sequences......Page 1313
Nested Parallelism......Page 1314
The Cost Semantics......Page 1315
Bibliography......Page 1317
Definition......Page 1318
Parallel-NetCDF and the I/O Software Stack......Page 1319
The Parallel-NetCDF API and File Format......Page 1320
Standard Interface......Page 1321
A more realistic example......Page 1323
Nonblocking Interface......Page 1324
Conclusion......Page 1325
Bibliography......Page 1326
Introduction......Page 1327
Notifications......Page 1328
Advanced Architecture......Page 1329
Bibliographic Notes and Further Reading......Page 1332
Definition......Page 1333
Cache-Oblivious Algorithms......Page 1334
A Model for Network Obliviousness......Page 1335
Bibliography......Page 1338
Introduction......Page 1339
Meshes......Page 1340
Torus......Page 1341
Routing Functions......Page 1342
Future Directions......Page 1343
Bibliography......Page 1344
Fault Models......Page 1345
Transient and Permanent Faults......Page 1346
Fault-Tolerant Routing......Page 1347
Fault-Tolerant Routing in Direct Networks......Page 1348
Fault-Tolerant Routing in Indirect Networks......Page 1349
Bibliography......Page 1350
Topologies......Page 1351
Multistage Networks......Page 1352
Butterfly......Page 1353
Fat Tree......Page 1354
Related Entries......Page 1355
Definition......Page 1356
Progress and Correctness Guarantees for Non-blocking Algorithms......Page 1357
Theoretical Foundations......Page 1358
Helping......Page 1360
Memory Contention and Adaptive Algorithms......Page 1361
Non-blocking Algorithms: Pros and Cons......Page 1362
Bibliography......Page 1363
Introduction......Page 1364
Data Management Policies: S-NUCAand D-NUCA......Page 1365
Bank Mapping......Page 1366
Data Movement and Replacement......Page 1367
System Topologies......Page 1368
Coherency in CMP Systems Adopting NUMA Caches......Page 1369
Dynamic Mapping......Page 1370
Research Directions......Page 1371
Bibliographic Notes and Further Reading......Page 1372
Numerical Libraries......Page 1373
Accelerating Computer Graphics......Page 1374
Parallel Computing Architecture......Page 1375
Thread Synchronization......Page 1377
Throughput-Oriented Design......Page 1378
Bibliography......Page 1379
Overview......Page 1380
Gaussian Basis Set Approach......Page 1381
Plane Wave Approach......Page 1382
Coupled Cluster Theory......Page 1383
Classical Molecular Dynamics......Page 1384
Combined Quantum Mechanical Molecular Mechanics......Page 1385
Parallel Framework......Page 1386
Bibliographic Notes and Further Reading......Page 1387
Bibliography......Page 1388
Traditional Dependence Abstractions......Page 1390
Dependence Relations......Page 1391
Iteration Space Transformation......Page 1392
Representation and Manipulation of Sets and Relations......Page 1393
Conjunctions of Affine Equations and Inequations......Page 1394
The Gist Operation......Page 1396
Disjunctive Normal Form......Page 1397
Non-affine Terms and Uninterpreted Function Symbols......Page 1398
Bibliography......Page 1399
Introduction......Page 1400
Overview of Features......Page 1401
Loop Parallelism......Page 1402
Implementation......Page 1403
Performance of OpenMP Programs......Page 1404
Related Entries......Page 1405
Definition......Page 1406
Platform-Independent Monitoring......Page 1407
OpenMP Profiling with ompP......Page 1408
Overheads Analysis......Page 1409
Scalability Analysis......Page 1410
Future Directions......Page 1412
Bibliography......Page 1413
Definition......Page 1414
Symmetric Objects......Page 1416
Remote Write/Read......Page 1417
Synchronization......Page 1419
Atomic Memory Operations......Page 1421
Reductions......Page 1423
Tool Support......Page 1424
Toward an Open SHMEM standard......Page 1425
Introduction......Page 1426
Parallel Computing Systems......Page 1427
Overview of OS Approaches......Page 1429
Parallel OS Functionality......Page 1430
Lightweight Versus Full-Featured Operating Systems......Page 1432
Future Directions......Page 1434
Bibliography......Page 1435
Overview......Page 1436
Interference Freedom......Page 1437
Examples......Page 1438
The Axioms......Page 1439
Bibliographic Notes and Further Reading......Page 1440
Bibliography......Page 1441
Discussion......Page 1442
Introduction and History......Page 1444
Parallel Architectures......Page 1445
Application Software Development......Page 1446
System Architecture Performance Criteria......Page 1447
Parallel Performance......Page 1448
Future......Page 1450
Parallel Prefix Sums......Page 1451
Programming with Skeletons......Page 1452
Data-Parallel Skeletons and Transformational Programming......Page 1453
Task- and Algorithm-Oriented Skeletons......Page 1455
Skeleton-Based Systems......Page 1456
Definition......Page 1457
Productive Parallel Programming......Page 1458
C, C++, Fortran, and UPC Programming in Eclipse......Page 1459
Code and Static Analysis for Parallel Programs......Page 1460
Parallel Debugging......Page 1461
Future Directions......Page 1462
Bibliographic Notes and Further Reading......Page 1463
Optimal Parallelism Detection in Loops......Page 1464
Definition of a SURE......Page 1466
The case of a single equation......Page 1467
The case of several equations......Page 1468
Representation of DO Loops......Page 1470
Approximations of Distances: Dependence Level and Direction Vector......Page 1471
Uniformization Principle: From Dependence Polyhedra to SUREs......Page 1472
Going Beyond, with the Affine Form of Farkas Lemma......Page 1473
Integer Interpreted Automata and Invariants......Page 1474
A Greedy Complete Polynomial-Time Procedure......Page 1475
Bibliography......Page 1476
Introduction......Page 1477
Dependence Analysis......Page 1478
Semantic Analysis......Page 1479
Transformations for Reducing the Number of Dependences......Page 1480
Scheduling Transformations......Page 1481
Autoparallelization Today......Page 1482
Future Directions......Page 1483
Bibliographic Notes And Further Reading......Page 1484
Introduction......Page 1485
Unlimited Resources......Page 1486
ALAP Algorithm......Page 1487
List Scheduling......Page 1488
Linear Analysis......Page 1489
An Example......Page 1490
Bibliographic Notes and Further Reading......Page 1492
Introduction......Page 1493
Sparse Gaussian Elimination in PARDISO......Page 1494
Parallelization Strategies in PARDISO......Page 1496
Example......Page 1497
Future Research Directions......Page 1498
Partial Computation......Page 1499
Introduction......Page 1500
The Overall PASM Organization......Page 1502
The Parallel Computation Unit......Page 1504
The Memory Storage and Management Systems......Page 1507
Using the PASM System......Page 1508
Conclusions......Page 1509
Bibliography......Page 1510
Discussion......Page 1511
Implementation......Page 1512
Uses of Path Expressions......Page 1513
Synonyms......Page 1514
Preliminaries......Page 1515
Stand-Alone Program......Page 1516
Customizing PaToH\'s Hypergraph Partitioning......Page 1517
Bibliography......Page 1521
Introduction – A Brief History of PCIe......Page 1522
Signaling, Speed, and Bandwidth......Page 1523
Link Configuration......Page 1524
Packet-Based Protocol......Page 1525
Data Link Layer......Page 1526
Architecture Features......Page 1527
Scalable Performance......Page 1528
Differentiated Quality of Service (Qos) Support......Page 1529
PCI Express Today......Page 1530
Future Directions......Page 1531
Bibliographic Notes and Further Reading......Page 1532
Definition......Page 1533
Architecture Variants......Page 1534
Hypercubic Overlays and Consistent Hashing......Page 1535
Dealing with Churn......Page 1537
Fostering Cooperation......Page 1538
Current Trends and Outlook......Page 1539
Bibliography......Page 1540
Definition......Page 1541
Compute Node Design......Page 1542
PERCS Interconnect......Page 1543
Routing Between Nodes......Page 1544
Collective Accelerator Unit (CAU)......Page 1545
Host Fabric Interface......Page 1546
POWER7 Processor Overview......Page 1547
On-chip Integrated Fabric and Chip Interconnect......Page 1548
Blue Waters: The First PERCS Installation......Page 1549
Definition......Page 1550
Sampling......Page 1551
Level of Detail......Page 1552
Performance Aspects......Page 1553
Automation......Page 1554
Representative Tools......Page 1555
Bibliography......Page 1556
Performance Properties......Page 1557
Architecture......Page 1558
Definition......Page 1560
Example: A Barber Shop......Page 1561
Petri Nets and Finite State Machines......Page 1562
The Petri Net Hierarchy......Page 1563
Continuous and Hybrid Petri Nets......Page 1564
Definition......Page 1565
Discussion......Page 1566
Library Design......Page 1567
Applications......Page 1573
Definition......Page 1574
Introduction......Page 1575
Messaging......Page 1576
Array Programming and Implicit Parallelism......Page 1577
Collectives, Teams, and Synchronization......Page 1578
Bibliography......Page 1579
Output......Page 1580
Optimality Criteria......Page 1581
Vectorization......Page 1582
Coarse-Grain Parallelism in Maximum Likelihood Analyses......Page 1583
Coarse-Grain Parallelism in Bayesian Analyses......Page 1584
Future Directions......Page 1585
Bibliographic Notes and Further Reading......Page 1586
Bibliography......Page 1587
Introduction......Page 1589
Syntax......Page 1590
Examples......Page 1591
Names......Page 1592
Types......Page 1593
Theory......Page 1594
Related Entries......Page 1596
Pipelining......Page 1597
Objects and Communications......Page 1598
Distributing and Interfacing with Parallel Operands......Page 1599
An Illustrative Example......Page 1600
Discussion......Page 1603
Discussion......Page 1605
Simple Usage Example......Page 1606
Performance Measurement ToolsBased on PMPI......Page 1607
Verification Tools Based on PMPI......Page 1608
Related Entries......Page 1609
Definition......Page 1610
Detecting Parallelism......Page 1611
Mapping Parallel Computation to the Target Machine......Page 1613
Internal Organization......Page 1614
Bibliography......Page 1615
The Basic Model......Page 1616
An Example......Page 1619
Scheduling......Page 1620
Extensions......Page 1621
Treatment of Expressions......Page 1622
Array Shrinking......Page 1623
Mathematical Support......Page 1624
Bibliographic Notes and Further Reading......Page 1625
Bibliography......Page 1626
POSIX Threads (Pthreads)......Page 1627
CMOS Technology Determinants......Page 1628
Power-Performance Efficiency Metrics......Page 1631
A Review of Key Ideas in Power-Aware Architectures......Page 1632
Power Efficiency at the ProcessorCore Level......Page 1633
Power-Efficient Microarchitecture Paradigms......Page 1639
Bibliography......Page 1641
Introduction......Page 1643
Complexity Measures and Work–Time Framework......Page 1645
Prefix Sums or Scan......Page 1646
Fractional Independent Set......Page 1647
Superfast Maximum Algorithm......Page 1648
Bibliographic Notes and Further Reading......Page 1649
Discussion......Page 1650
Jacobi and Block-Jacobi Preconditioners......Page 1651
Preconditioners Based on Incomplete Factorization......Page 1652
Threshold-Based Incomplete Factorization......Page 1654
Multigrid Preconditioners......Page 1655
Geometric Multigrid......Page 1656
Algebraic Multigrid......Page 1657
Bibliographic Notes......Page 1658
Introduction......Page 1659
Process Operators and Operational Semantics......Page 1661
CCS: Calculus of Communicating Systems......Page 1665
CSP: A Theory of Communicating Sequential Processes......Page 1666
ACP: An Algebra of Communicating Processes......Page 1667
Future Directions......Page 1668
Synchrony vs Asynchrony......Page 1669
Bibliography......Page 1670
Process Description Languages......Page 1671
Programming Languages......Page 1672
Exhaustive Rigid Body Searching......Page 1673
Incorporation of Protein Flexibility in Protein–Protein Docking......Page 1675
Scoring Functions for Protein–Protein Docking......Page 1677
Critical Assessments of Protein–Protein Docking Methods......Page 1679
Applications of Protein–Protein Docking and Large-Scale Predictions......Page 1680
Bibliography......Page 1681
Introduction......Page 1682
Resource Management......Page 1683
Message Passing......Page 1684
Fault Tolerance......Page 1685
Bibliography......Page 1686
The Computing Node......Page 1688
The Global Features......Page 1689
The Theoretical Physics Research Thanks to apeNEXT......Page 1690
Bibliography......Page 1691
Introduction......Page 1692
The Principle of Lattice Gauge Theory Calculations......Page 1693
Parallelization......Page 1695
Definition......Page 1696
Introduction......Page 1697
First Examples......Page 1698
Second Generation QCD Machines......Page 1699
Beyond One Teraflops......Page 1701
Bibliographic Notes and Further Reading......Page 1702
Definition......Page 1703
Overview......Page 1704
Networks......Page 1705
Software......Page 1707
QCDSP Architecture......Page 1709
Conclusion......Page 1710
Bibliography......Page 1711
Introduction......Page 1712
First Generation, QsNet......Page 1713
Packet Routing and Flow Control......Page 1715
Network Fault Detection and Fault Tolerance......Page 1717
Communication Libraries......Page 1718
Elan3lib......Page 1719
Hardware-Based Multicast......Page 1720
Second Generation, QsNetII......Page 1721
Related Entries......Page 1722
Bibliography......Page 1723
Quicksort......Page 1724
Introduction......Page 1726
Feasible program executions......Page 1727
Apparent races......Page 1728
Race Conditions as Programming Errors......Page 1729
Causality......Page 1730
Bibliography......Page 1731
Introduction......Page 1732
HB-Based Data Race Detection......Page 1733
Lockset-Based Data Race Detection......Page 1735
Dynamic Methods......Page 1736
Static Methods......Page 1737
Complexity......Page 1738
Bibliography......Page 1739
Definition......Page 1741
Introduction......Page 1742
Detecting Races in Programs that Use Locks......Page 1743
Series-Parallel Parse Trees......Page 1744
Access History......Page 1745
Data-Race Detection......Page 1746
SP-Bags......Page 1747
SP-Order......Page 1749
Parallel SP-Maintenance......Page 1751
Bibliographic Notes and Further Reading......Page 1752
Bibliography......Page 1753
Definition......Page 1754
Problem Formulation......Page 1755
Mathematical Preliminaries and Notation......Page 1756
Matrix Decomposition......Page 1757
Block Cyclic Reduction......Page 1758
FACR......Page 1759
Domain Decomposition......Page 1760
Bibliography......Page 1761
Random-Access Reduce and Scan......Page 1763
Carry-lookahead adder:......Page 1766
Linked List Reduce and Scan......Page 1767
Bibliography......Page 1770
Discussion......Page 1771
Related Entries......Page 1775
Introduction......Page 1776
Roadrunner Hardware Architecture......Page 1777
Triblade Architecture......Page 1778
Software Complexity......Page 1780
Reliability, Availability, and Serviceability......Page 1782
Router Architecture......Page 1783
Taxonomy of Routing Algorithms......Page 1784
Deadlock Handling......Page 1785
Routing in k-ary n-cubes......Page 1786
Routing in k-ary n-trees......Page 1787
Routing in Irregular Networks. Agnostic Routing......Page 1789
Bibliography......Page 1790
History......Page 1791
Architecture......Page 1792
Machine Model......Page 1793
The Generalized Dependence Graph......Page 1794
Dependence Analysis and Array Expansion......Page 1795
Task Formation and Placement......Page 1796
Target-Specific Optimizations: GPU......Page 1797
Bibliography......Page 1799
Synonyms......Page 1800
Inspector/Executor Methods and Distributed Memory......Page 1801
Communication Schedules......Page 1802
Runtime Parallelization......Page 1803
Compiler Implementations......Page 1804
Runtime System......Page 1806
Discussion......Page 1808
Definition......Page 1810
Functionality......Page 1811
Instrumentation......Page 1812
Call-Path Profiling......Page 1813
Parallel Wait-State Search......Page 1814
Wait-State Search on Clusters without Global Clock......Page 1815
Time-Series Call-Path Profiling......Page 1816
Related Entries......Page 1817
Bibliographic Notes and Further Reading......Page 1818
Bibliography......Page 1819
Linear Array......Page 1820
Simultaneous Trees......Page 1821
Scan, Reduce and......Page 1822
Task Graphs and Scheduling......Page 1823
Scheduling One-Dimensional Loops......Page 1824
Scheduling Multidimensional Loops......Page 1825
From Loops to Recurrences......Page 1827
Bibliographic Notes and Further Reading......Page 1828
Introduction......Page 1829
Main Concepts of SCI......Page 1830
Implementations and Applications of SCI......Page 1833
System Area Network for Clusters......Page 1834
I/O Subsystem Interconnect......Page 1836
Bibliography......Page 1837
Central Idea and Program Example......Page 1838
Independence Between Two Statements......Page 1840
Disjoint Parallelism and Its Limitations......Page 1842
Practical Relevance......Page 1843
Bibliography......Page 1844
Discussion......Page 1845
Bibliographic Notes and Further Reading......Page 1846
Organization......Page 1847
Packet and Instruction Architecture......Page 1851
Software......Page 1852
Discussion......Page 1853
SIMD ISA......Page 1854
Introduction......Page 1855
Programmer\'s View......Page 1856
Implementation of an SSI......Page 1857
Process Migration......Page 1858
Batch System......Page 1859
Imperfect SSI......Page 1860
Bibliography......Page 1861
Language Definition......Page 1862
Build-in-Place Analysis......Page 1863
Runtime System......Page 1864
Performance......Page 1865
Small-World Network Analysis and Partitioning (SNAP) Framework......Page 1866
Introduction......Page 1867
Graph Representation......Page 1868
Parallelization Strategies......Page 1869
Community Identification Algorithmsin SNAP......Page 1870
Bibliography......Page 1871
What Is a SoC?......Page 1872
Quality Criteria......Page 1873
Why Is It a SoC ``Revolution\'\'?......Page 1874
SoC Design Methodology......Page 1875
Bibliographic Notes and Further Reading......Page 1876
Introduction......Page 1877
Background and Notation......Page 1879
Petascale Computing Challenges for Social Network Problems......Page 1880
Distributed Streaming Algorithms......Page 1881
Bibliography......Page 1882
Introduction......Page 1883
Implementations Using Instrumentation......Page 1884
Memory Models......Page 1885
Leveraging Hardware Coherence......Page 1886
Leveraging Additional Hardware Support......Page 1887
Bibliographic Notes and Further Reading......Page 1888
Bibliography......Page 1889
Parallel Quicksort......Page 1890
Parallel Radix Sort......Page 1891
Sample Sort......Page 1892
Histogram Sort......Page 1893
GPU-Based Sorting......Page 1894
Future Directions......Page 1895
Bibliography......Page 1896
Construction......Page 1897
Computation of Mappings......Page 1898
Locality Properties of Space-Filling Curves......Page 1899
High Performance Computing and Load Balancing with Space-Filling Curves......Page 1900
Bibliography......Page 1901
Introduction......Page 1902
Modifications of SPAI......Page 1903
Bibliography......Page 1904
Sequential Algorithms......Page 1905
Implementation of Parallel Bor\'27uvka......Page 1906
Flexible Adjacency List Representation......Page 1907
A Hybrid Parallel MST Algorithm......Page 1908
Implementation with Fine-Grained Locks......Page 1909
Experimental Results......Page 1910
Bibliography......Page 1911
Discussion......Page 1912
Task Graph Model of Sparse Factorization......Page 1914
Supernodes......Page 1916
Sparse Factorization Formulations Based on Task Roles......Page 1917
Pivoting in Parallel Sparse LDLT and LU Factorization......Page 1919
Parallel Solution of Triangular Systems......Page 1920
Synonyms......Page 1921
SPEC HPC96......Page 1922
SPEC OMP2001......Page 1923
SPEC MPI2007......Page 1924
Bibliographic Notes and Further Reading......Page 1927
SPEC MPI2007......Page 1928
Basic Concepts in Thread-Level Speculation......Page 1929
Multiple Versions of the Same Variablein the System......Page 1931
Basic Concepts......Page 1932
Techniques to Avoid Squashes......Page 1933
Bibliography......Page 1934
Fundamentals of Loop Parallelization......Page 1936
Compiler Limitation and Run-time Parallelization......Page 1937
DOALL Speculative Parallelization: The LRPD Test......Page 1939
DOACROSS Speculative Parallelization......Page 1941
While Loop Speculative Parallelization......Page 1942
Speculative Parallelization as a Parallel Programming Paradigm......Page 1944
Bibliographic Notes and Further Reading......Page 1945
Bibliography......Page 1946
Definition......Page 1947
Introduction......Page 1948
The SPIKE Algorithm: Basics......Page 1949
SPIKE: A Hybrid and Polyalgorithm......Page 1950
LU/UL Strategy......Page 1951
Speed-Up Performances on Small Number of Processors......Page 1952
The SPIKE Solver: Current and Future Implementation......Page 1953
Bibliography......Page 1954
Introduction......Page 1955
Algorithm Representation......Page 1957
Spiral Program Generation: Overview......Page 1958
Fixed Input Size: Loop Code......Page 1960
Fixed Input Size: Parallel Code......Page 1962
General Input Size......Page 1964
Bibliography......Page 1967
Definition of the Subject......Page 1968
Introduction......Page 1969
The SPMD Model......Page 1970
The EPEX Programming Environment – Implementation of the SPMD Model......Page 1972
Advancing into the Future: Directions, Opportunities, Challenges, and Approaches......Page 1975
Bibliography......Page 1977
Synonyms......Page 1978
Example Programming Models......Page 1979
Methods for Graph Wiring......Page 1980
Optimization and Scheduling......Page 1981
Algorithms......Page 1982
Bibliography......Page 1983
Introduction......Page 1984
Parallel Suffix Tree Construction......Page 1985
Practical Parallel Algorithms for Out-of-Core Strings......Page 1986
Suffix Arrays......Page 1988
Bibliography......Page 1989
Definition......Page 1990
Overall Algorithm......Page 1991
Sparse Matrix Data Structure......Page 1992
Numerical Pivoting......Page 1993
Task Ordering......Page 1994
Parallelization and Performance......Page 1995
Bibliography......Page 1996
Introduction......Page 1997
Register Renaming......Page 1998
Speculative Execution......Page 1999
Brief Early History......Page 2000
Motivation......Page 2001
Multicore Model......Page 2002
Case Study: Merge Sort......Page 2003
Programming in SWARM......Page 2004
Algorithm Design and Examples in SWARM......Page 2005
Synonyms......Page 2006
Canonical Switch Architecture......Page 2007
Alternative Switch Architectures......Page 2008
Input Buffer Organization......Page 2009
Pipelined Organization......Page 2010
Bibliographic Notes and Further Reading......Page 2011
A Generic Router Model......Page 2012
Basic Concepts......Page 2013
Basic Switching Techniques......Page 2014
Circuit Switching......Page 2015
Packet Switching......Page 2016
Wormhole Switching......Page 2018
A Comparison of Switching Techniques......Page 2021
Bibliography......Page 2023
Discussion......Page 2024
NB:......Page 2025
Relaxations of Mutual Exclusion......Page 2026
Scalable Busy-Wait Locks......Page 2027
Barriers......Page 2028
Semantic Details......Page 2029
Rendezvous and Remote Procedure Call......Page 2030
System Integration......Page 2031
Information Theoretic Approaches......Page 2032
Approaches Based on Bayesian Networks......Page 2034
Approaches Based on Differential Equations......Page 2035
Future Directions......Page 2036
Synonyms......Page 2037
Background: Motivated by Emergence of VLSI......Page 2038
Concept......Page 2039
Variations......Page 2040
Systolic Algorithms......Page 2041
NOSC Systolic Array Test Bed......Page 2042
Warp and iWarp......Page 2043
Future Directions......Page 2044
Bibliographic Notes and Further Reading......Page 2045
Bibliography......Page 2046
Introduction......Page 2048
Fundamental Results......Page 2049
Definitions......Page 2050
Solving Pb(&Infinity;)......Page 2051
List Scheduling Heuristics......Page 2052
Critical Path Scheduling......Page 2053
The Macro-Dataflow Model......Page 2054
Complexity and List Heuristics with Communications......Page 2055
Workflow Scheduling......Page 2056
Period and Latency......Page 2057
Recommended Reading......Page 2059
Introduction......Page 2060
TAU Design......Page 2061
TAU Measurement......Page 2062
Summary......Page 2063
Tensilica......Page 2064
Beginnings......Page 2065
Compiler Optimization......Page 2066
Operating System......Page 2067
Related Entries......Page 2068
Introduction......Page 2069
Key Components of TECM......Page 2070
The Contributions of Parallel Computing to TECM Developments......Page 2071
Bibliographic Notes and Further Reading......Page 2073
Thin Ethernet......Page 2074
Introduction......Page 2075
Motivations for Tiling......Page 2076
Legality of Tiling......Page 2078
Tile Selection and Optimal Tiling......Page 2079
Tiled Code Generation......Page 2080
Future Directions......Page 2081
Bibliographic Notes and Further Reading......Page 2082
Bibliography......Page 2083
Titanium\'s Parallelism Model......Page 2084
Titanium\'s Memory Model......Page 2085
Titanium Arrays......Page 2086
Unordered Loops, Value Types, and Overloading......Page 2087
Distributed Arrays......Page 2088
Application Experience......Page 2089
Definition......Page 2090
Method of Solution......Page 2091
Introduction......Page 2092
Interconnect Topologies......Page 2093
Objective Functions......Page 2094
Randomized Heuristics......Page 2095
Related Entries......Page 2096
Definition......Page 2097
Introduction......Page 2098
Region Formation – Trace Picking......Page 2099
Region Enlargement......Page 2100
Region Compaction – Instruction Scheduler......Page 2101
Compensation Code......Page 2102
Bibliographic Notes and Further Reading......Page 2104
Bibliography......Page 2105
Introduction......Page 2106
Mathematical Definitions and Normal Forms......Page 2107
Regular Sets......Page 2108
Undecidability Results for Rational Sets......Page 2109
Infinite Traces......Page 2110
Logics, Algebra, and Automata......Page 2111
Traces and Asynchronous Communication......Page 2112
Bibliographic Notes and Further Reading......Page 2113
Introduction......Page 2114
The Transactional Model......Page 2115
Motivation......Page 2116
Lock Elision......Page 2117
Weak vs Strong Isolation......Page 2118
Eager vs Lazy Conflict Detection......Page 2119
Bibliography......Page 2120
Definition......Page 2121
Transactions......Page 2122
Example Closed Nesting Implementation Approach......Page 2123
Open Nesting......Page 2124
An Example Open Nesting Protocol......Page 2125
Coarse-Grained Transactions......Page 2126
Extended Semantics......Page 2127
Bibliography......Page 2128
Tuning and Analysis Utilities......Page 2129
Fetch-and-Add (and Friends)......Page 2130
A Fetch-and-Add Semaphore......Page 2131
The Topology......Page 2132
Combining Fetch-and-Adds......Page 2133
Combining Switch Design......Page 2134
Systolic Queues......Page 2135
Semi-Systolic Combining Queues......Page 2136
Bibliography......Page 2137
Mathematical Preliminaries......Page 2138
Fourier\'s Method of Elimination......Page 2139
Basic Concepts......Page 2141
Parallelization by Unimodular Transformation......Page 2143
Loop Skewing......Page 2145
Bibliographic Notes and Further Reading......Page 2146
Definition......Page 2147
The Question of Universality......Page 2148
Bandwidth and Area......Page 2149
Universal Fat-Tree Architectures......Page 2150
Conclusions......Page 2152
Introduction......Page 2153
Parallelism Model......Page 2154
Memory Model......Page 2155
An Example Program......Page 2156
Applications......Page 2157
Bibliography......Page 2158
Use-Def Chains......Page 2159
Instrumentation......Page 2160
Master Timeline......Page 2161
Charts......Page 2162
Licenses and Other Software......Page 2163
Discussion......Page 2164
History......Page 2165
Compiler Supported Exploitation......Page 2166
Data Formatting......Page 2167
MMX......Page 2168
Bibliography......Page 2169
Discussion......Page 2170
VLIW Implementation......Page 2171
Benefits of VLIW......Page 2172
Code Size......Page 2174
Other Modern VLIW Microprocessors......Page 2175
Precursors of VLIWs......Page 2176
Synonyms......Page 2177
A Model of VLSI Computation......Page 2178
VLSI Architectures and Algorithms......Page 2180
Meshes......Page 2181
Hypercubic Networks......Page 2182
A Critical Comment......Page 2183
VNG......Page 2184
Introduction......Page 2186
The Warp Machines......Page 2188
Compilers......Page 2191
Applications......Page 2193
Whole Program Analysis......Page 2194
Workflow Scheduling......Page 2195
Foundations......Page 2196
Primary Concepts: Regions, Arrays, andDirections......Page 2197
Array Operators and theWYSIWYGPerformanceModel......Page 2198
Advanced ZPL......Page 2199
Bibliographic Notes and FurtherReading......Page 2200
Bibliography......Page 2201
List of Entries......Page 2202