High-Performance Scientific Computing [recurso electrónico] Algorithms and Applications

This book presents the state of the art in parallel numerical algorithms, applications, architectures, and system software. The book examines various solutions for issues of concurrency, scale, energy efficiency, and programmability, which are discussed in the context of a diverse range of applications. Features: includes contributions from an international selection of world-class authorities; examines parallel algorithm-architecture interaction through issues of computational capacity-based codesign and automatic restructuring of programs using compilation techniques; reviews emerging applications of numerical methods in information retrieval and data mining; discusses the latest issues in dense and sparse matrix computations for modern high-performance systems, multicores, manycores and GPUs, and several perspectives on the Spike family of algorithms for solving linear systems; presents outstanding challenges and developing technologies, and puts these in their historical context. Cover High-Performance Scientific Computing ISBN 9781447124368 Preface Acknowledgements Contents List of Contributors Chapter 1: Parallel Numerical Computing from Illiac IV to Exascale-The Contributions of Ahmed H. Sameh 1.1 Illiac IV and Cedar Legacies on Parallel Numerical Algorithms 1.2 Algorithms for Dense Matrices 1.2.1 Primitives, Dense and Banded Systems 1.2.2 Jacobi Sweeps and Sturm Sequences 1.2.3 Fast Poisson Solvers and Structured Matrices 1.3 Algorithms for Sparse Matrices 1.3.1 Computing Intermediate Eigenvalues 1.3.2 The Trace Minimization Algorithm 1.3.2.1 The Trace Min Idea 1.3.2.2 Trace Minimization and Davidson 1.3.3 Algorithms for Large Scale SVD 1.3.4 Iterative Methods for Linear Systems of Equations 1.3.5 The Spike Algorithm 1.3.5.1 Basic Spike Algorithm 1.3.5.2 Spike: A Hybrid and Polyalgorithm Factorization of the Diagonal Blocks Aj Computation of the spikes Solution Scheme for the Reduced System 1.3.5.3 The Truncated Spike Scheme for Diagonally Dominant Systems 1.3.5.4 The Recursive Spike Scheme for Non-diagonally Dominant Systems 1.3.5.5 Spike: Current and Future Directions 1.4 Floating-Point Arithmetic and Error Analysis 1.5 Contributions to n-Body Methods, Fast Multipole Methods, Boundary Integral Solvers, and Their Applications 1.5.1 Multipole-Based Hierarchical Approximation Techniques 1.5.2 Multipole Based Dense Linear System Solvers and Preconditioners 1.5.3 Improving Error Bounds for Hierarchical Approximation Techniques 1.5.4 Algorithms for Atomistic Modeling 1.6 Computational Science and Engineering References Chapter 2: Computational Capacity-Based Codesign of Computer Systems 2.1 Introduction 2.1.1 Background: Performance Basics 2.1.2 Performance Background Summary 2.2 Codesign Process 2.2.1 Three Dimensions of Codesign 2.2.2 Models 2.2.2.1 SW Models 2.2.2.2 Computer System HW Models 2.2.3 Model Philosophy and Codesign Realities 2.3 Linear Computational Capacity Theory 2.3.1 General Equations for Single Phase Computations 2.3.1.1 Capacity Definitions 2.3.1.2 Two Node Systems 2.3.1.3 Greater than Two Node Systems 2.3.1.4 General Two-Node Capacity Rule 2.3.2 Example: Single Processor-Heterogeneous Memory 2.4 Single Phase Codesign Equations 2.4.1 Capacity Equation Generation 2.4.1.1 Capacity Equation Generation Algorithm 2.4.2 Codesign Equations Physical Constraints 2.4.3 Single Phase Models and Characteristic Equation Two Node Systems General Systems 2.4.4 Observations 2.5 Multiphase Codesign Equations 2.5.1 Multiphase Model and Characteristic Equations 2.5.2 Codesign Equation 2.5.3 Software Design Equations 2.5.4 Multiphase Performance Observations 2.5.5 Overall System Optimization 2.5.6 Sensitivity Analysis 2.6 Using the Codesign Model 2.6.1 Cost Reduction 2.6.2 Performance Sensitivities and Instabilities 2.6.2.1 Sensitivity of Performance to the System 2.6.2.2 Sensitivity of Performance to the SW Load 2.6.2.3 Performance Instability Conclusions 2.6.3 Architectural Variations Affecting Capacity 2.7 Multirate Nodes 2.8 Related Work 2.9 Conclusions References Chapter 3: Measuring Computer Performance 3.1 Introduction 3.2 Traditional Measurement and Modeling 3.3 Computational Capacity Model 3.3.1 Basic Variables and Measurements 3.3.2 Single Phase CAPE Simulation 3.3.3 Multiple Phase CAPE Simulation 3.4 Dealing with Nonlinearity 3.4.1 Nonlinear Multirate Performance Model 3.4.2 Piecewise-Linear Approximation 3.5 Model Synthesis 3.5.1 Overview 3.5.2 Microbenchmarking 3.5.3 Codelet Extraction Tools 3.5.4 Macro Generation 3.5.5 SV-Node Analysis 3.5.5.1 DECAN 3.5.5.2 Finding SV-Node Saturation Time and Bandwidth by Nopping All but One SV-Node 3.5.5.3 Refining SV-Node Saturation Time by Nopping Single SV-Node 3.6 Experimental Results 3.6.1 Experimental Setting: Hardware, Software and Methodology 3.6.2 Model 3.6.3 Model Validation Results 3.7 Conclusions References Chapter 4: A Compilation Framework for the Automatic Restructuring of Pointer-Linked Data Structures 4.1 Introduction 4.2 Preliminaries Data Structure Analysis Automatic Pool Allocation Pool-Assisted Structure Splitting 4.3 Compile-Time Analysis and Transformation 4.3.1 Structure Splitting 4.3.2 Pool Access Analysis 4.3.3 Stack Management Explicit Pointer Tracking Shadow Stacks Stack Maps 4.3.4 In-Pool Addressing Expression Rewriting 4.3.5 Converting Between Pointers and Object Identifiers 4.3.6 Restructuring Instrumentation 4.4 Run-Time Support Tracing and Permutation Vector Generation Pool Reordering Stack Rewriting 4.5 Experiments Pool Reordering Tracing- and Restructuring Overhead Run-Time Stack Overhead Address Calculations 4.6 Related Work 4.7 Conclusions References Chapter 5: Dense Linear Algebra on Accelerated Multicore Hardware 5.1 Introduction and Motivation 5.2 PLASMA 5.2.1 PLASMA Design Principles 5.2.2 PLASMA Software Stack 5.2.3 PLASMA Scheduling 5.2.4 DAGs for One-Sided Factorizations 5.2.5 Performance for One-Sided Factorizations 5.3 MAGMA 5.3.1 Acceleration Techniques for GPUs 5.3.1.1 Blocking 5.3.1.2 Hybridization 5.3.1.3 Data Structures 5.3.1.4 Parallel Memory Access 5.3.1.5 Pointer Redirecting 5.3.1.6 Padding 5.3.1.7 Auto-tuning 5.3.2 Accelerating Dense Linear Algebra Kernels and Factorizations 5.4 DPLASMA 5.4.1 Dependence Analysis 5.4.2 The DAGuE Framework 5.4.2.1 Description 5.4.2.2 A Test Case: QR Factorization 5.4.2.3 DPLASMA and the DAGuE Framework 5.4.3 Performance of DPLASMA 5.5 Summary References Chapter 6: The Explicit Spike Algorithm: Iterative Solution of the Reduced System 6.1 Introduction 6.2 The Explicit Spike Algorithm 6.3 The Main Result 6.4 Conclusion References Chapter 7: The Spike Factorization as Domain Decomposition Method; Equivalent and Variant Approaches 7.1 Introduction 7.2 Single Separator Case Factorization Cost Analysis Solution Cost Analysis Comparison to Domain Decomposition Methods 7.3 Double Separator Case 7.3.1 Direct Factorization Parallel Solve Time Comparison to Single Separators 7.3.2 Full Elimination of the Subdomain 7.3.3 Original Derivation of the Spike Algorithm 7.4 Discussion References Chapter 8: Parallel Solution of Sparse Linear Systems 8.1 Introduction 8.2 Banded and Sparse Parallel DS Factorizations 8.3 Solution of General Sparse Linear Systems 8.3.1 Weighted Reordering and Banded Preconditioning 8.3.2 Domain Decomposing Parallel Sparse Solver 8.4 Conclusions References Chapter 9: Parallel Block-Jacobi SVD Methods 9.1 Background 9.1.1 Singular Value Decomposition 9.1.2 Serial SVD Algorithms 9.2 Two-Sided Block Jacobi SVD Method 9.3 One-Sided Block Jacobi SVD Algorithm 9.3.1 Dynamic Ordering 9.4 Conclusions References Chapter 10: Robust and Efficient Multifrontal Solver for Large Discretized PDEs 10.1 Introduction 10.2 Review of HSS Cholesky Factorization of a Dense Matrix 10.2.1 Hierarchically Semiseparable Structures 10.2.2 Robust HSS Cholesky Factorization 10.3 Nested Dissection for General Graphs 10.4 Robust Structured Multifrontal Factorization 10.4.1 Multifrontal Method 10.4.2 Structured Supernodal Multifrontal Factorization 10.4.3 Structured Multifrontal Solution 10.5 Algorithm, Complexity, and Rank Relaxation 10.6 Numerical Experiments References Chapter 11: A Preconditioned Scheme for Nonsymmetric Saddle-Point Problems 11.1 Introduction 11.2 Motivating Application 11.2.1 Properties of the Matrices 11.3 Solution Strategy 11.4 Proposed Nested Iterative Scheme 11.5 Convergence Analysis of the Nested Iterative Scheme 11.6 Construction of Â-1 and G-1 11.6.1 Construction of Â-1 11.6.2 Implicit Generation of Variable Gk-1 11.7 Numerical Experiments 11.7.1 Comparison with Other Preconditioners 11.7.2 The Driven-Cavity Steady-State Case 11.8 Conclusion References Chapter 12: Effect of Ordering for Iterative Solvers in Structural Mechanics Problems 12.1 Introduction 12.2 Description of the Test Problems 12.3 Ordering Schemes and Pre-conditioning 12.4 Iterative Solver Performance Results 12.5 Conclusions and Recommendations References Chapter 13: Scaling Hypre's Multigrid Solvers to 100,000 Cores 13.1 Introduction 13.2 The hypre Library 13.2.1 Conceptual Interfaces 13.2.2 Solvers 13.2.3 Considerations for Large-Scale Computing 13.3 The Multigrid Solvers 13.3.1 PFMG, SMG, and SysPFMG 13.3.2 BoomerAMG 13.3.3 AMS 13.4 Experimental Setup 13.4.1 Machine Descriptions 13.4.2 Test Runs 13.5 Scaling Studies 13.6 Concluding Remarks References Chapter 14: A Riemannian Dennis-Moré Condition 14.1 Introduction 14.2 The Riemannian Dennis-Moré Condition References Chapter 15: A Jump-Start of Non-negative Least Squares Solvers 15.1 Introduction 15.2 Background and Related Work 15.2.1 Active Set Methods 15.2.2 Projection Based Methods 15.3 Jump-Start for Active Set Methods 15.3.1 Performance Indicators 15.3.2 Relation Between Projection Based Methods and Active Set Methods 15.3.3 Observations 15.3.4 PiNNLS 15.4 Numerical Experiments 15.4.1 Experiments Design and Implementation 15.4.2 Quality of Initialization 15.4.3 Performance of PiNNLS 15.5 Conclusion and Future Work References Chapter 16: Fast Nonnegative Tensor Factorization with an Active-Set-Like Method 16.1 Introduction Notations 16.2 Related Work 16.3 ANLS Framework Mode-n matricization Khatri-Rao product 16.4 Block Principal Pivoting Method 16.5 Regularized and Sparse NNCP 16.6 Implementation and Results 16.6.1 Algorithms for NNCP Used for Comparisons 16.6.2 Data Sets 16.6.3 Experimental Results 16.7 Conclusions and Discussion References Chapter 17: Knowledge Discovery Using Nonnegative Tensor Factorization with Visual Analytics 17.1 Background 17.1.1 NTF-PARAFAC: Background 17.1.2 NTF-PARAFAC: The Algorithm 17.1.3 NTF-PARAFAC: Example of Effective Use 17.2 Python Implementation: Goals and Purpose 17.2.1 Portability, Flexibility, Cost of Use 17.2.2 Additional Dimension Creation Through Entity Tagging 17.2.3 Significance or Trust Measure Integration into NTF 17.3 Integrated Analysis Environment Capabilities 17.3.1 Deployment of NTF Algorithm (in Python) 17.4 Examples of Knowledge Discovery 17.4.1 Effect of Tensor Weights Adjustment on Analysis 17.4.2 Effect of Automated NTF Output Labeling on Analysis 17.5 Conclusions and Future Work References Index Advances in the development of parallel algorithms and system software now enable the ever-increasing power of scalable high-performance computers to be harnessed for scientific computing applications at fidelities that rival – and in many cases exceed – experimental methodologies. This comprehensive text/reference, inspired by the visionary work of Prof. Ahmed H. Sameh, represents the state of the art in parallel numerical algorithms, applications, architectures, and system software. Articles in this collection address various challenges arising from concurrency, scale, energy efficiency, and programmability, and associated solutions that have shaped the current high-performance computing landscape. These solutions are discussed in the context of diverse applications, ranging from scientific simulations to large-scale data analysis and mining. Topics and features: includes contributions from an international selection of world-class authorities, inspired by the work of Prof. Ahmed H. Sameh and his involvement in parallel numerical algorithm design since Illiac IV and the University of Illinois Cedar multiprocessor; examines various aspects of parallel algorithm-architecture interaction through articles on computational capacity-based codesign and automatic restructuring of programs using compilation techniques; reviews emerging applications of numerical methods in information retrieval and data mining; discusses the latest issues in dense and sparse matrix computations for modern high-performance systems, multicores, manycores and GPUs, and several perspectives on the Spike family of algorithms for solving linear systems; presents outstanding challenges and developing technologies, and puts these in their historical context. This authoritative reference is a must-read for researchers and graduate students in disciplines as diverse as computational fluid dynamics, signal processing, and structural mechanics. Professionals involved in applications that rely on high-performance computers will also find the text an essential resource. Advances in the development of parallel algorithms and system software now enable the ever-increasing power of scalable high-performance computers to be harnessed for scientific computing applications at fidelities that rivals and in many cases exceeds experimental methodologies. This comprehensive text/reference, inspired by the visionary work of Prof. Ahmed H. Sameh, represents the state of the art in parallel numerical algorithms, applications, architectures, and system software. Articles in this collection address solutions to various challenges arising from concurrency, scale, energy efficiency, and programmability. These solutions are discussed in the context of diverse applications, ranging from scientific simulations to large-scale data analysis and mining. Topics and features: Includes contributions from an international selection of world-class authorities, inspired by the work of Prof. Ahmed H. Sameh ; Examines various aspects of parallel algorithm-architecture interaction through articles on computational capacity-based codesign and automatic restructuring of programs using compilation techniques ; Reviews emerging applications of numerical methods in information retrieval and data mining ; Discusses the latest issues in dense and sparse matrix computations for modern high-performance systems, multicores, manycores and GPUs, and several perspectives on the Spike family of algorithms for solving linear systems ; Presents outstanding challenges and developing technologies, and puts these in their historical context ; This authoritative reference is a must-read for researchers and graduate students in disciplines as diverse as computational fluid dynamics, signal processing, and structural mechanics. Professionals involved in applications that rely on high-performance computers will also find the text an essential resource