Software Automatic Tuning - From Concepts to State-of-the-Art Results

Software Automatic Tuning

Preface

Contents

Contributors

Part I Introduction

Chapter1 Software Automatic Tuning: Concepts and State-of-the-Art Results

1.1 Software Automatic Tuning: General Concepts

1.2 Software Automatic Tuning: State-of-the-Art

Part II Achievements in Scientific Computing

Chapter2 ATLAS Version 3.9: Overview and Status*

2.1 Introduction

2.1.1 Basic AEOS Requirements

2.1.2 Methods of Software Adaptation

2.2 ATLAS Overview

2.2.1 Explicit LAPACK Support In ATLAS

2.2.2 Dense Level 3 BLAS Support in ATLAS

2.2.2.1 Using Assembly in ATLAS

2.2.3 Dense Level 2 BLAS Support in ATLAS

2.2.4 Dense Level 1 BLAS Support in ATLAS

2.3 Status

References

Chapter3 Autotuning Method for Deciding Block Size Parameters in Dynamically Load-Balanced BLAS

3.1 Introduction

3.2 Background

3.2.1 BLAS

3.2.2 DL-BLAS

3.2.3 Motivation of the present Research

3.3 Proposed Methods

3.3.1 Parallel Efficiency Analysis

3.3.2 Diagonal Search

3.3.3 Reductive Search

3.3.4 Parameter Selection

3.4 Experiments

3.4.1 Environments

3.4.2 Performance of Diagonal Search

3.4.3 Analysis and Discussion of Diagonal Search

3.4.4 Performance Evaluation Tests

3.5 Conclusion

References

Chapter4 Automatic Tuning for Parallel FFTs

4.1 Introduction

4.2 Parallel One-Dimensional FFT

4.2.1 A Block Nine-Step FFT Algorithm

4.2.2 A Parallel One-Dimensional FFT Algorithm Based on the Block Nine-Step FFT

4.3 Parallel Multi-Dimensional FFT

4.3.1 Parallel Two-Dimensional FFT

4.3.2 Parallel Three-Dimensional FFT

4.4 Automatic Tuning of Parallel FFTs

4.4.1 Automatic Tuning of All-to-All Communication

4.4.2 Selection of the Radices

4.4.3 Selection of the Block Size

4.5 Performance Results

4.5.1 Performance of All-to-All Communication

4.5.2 Performance of One-Dimensional FFT

4.5.3 Performance of Multi-Dimensional FFTs

4.6 Conclusion

References

Chapter5 Dynamic Programming Approaches to Optimizing the Blocking Strategy for Basic Matrix Decompositions

5.1 Introduction

5.2 Basics of the Householder QR Algorithm

5.2.1 The Householder QR Algorithm

5.2.2 Blocking Strategies for the Householder QR Algorithm

5.2.2.1 Fixed-size Blocking

5.2.2.2 Recursive Blocking

5.2.3 Another Blocking Strategy: The TSQR Algorithm

5.3 Dynamic Programming Approaches to Optimizing the Blocking Strategy

5.3.1 Limitations of Conventional Blocking Strategies

5.3.2 Approaches for the Sequential Case

5.3.2.1 Variable-size Blocking

5.3.2.2 Generalized Recursive Blocking

5.3.3 Approaches for the Parallel Case

5.3.3.1 Variable-size Blocking for Distributed Memory Machines

5.3.3.2 Combination of Variable-size Blocking and TSQR

5.4 Future Directions

5.4.1 Use of Task Level Parallelism

5.4.2 Extension to Heterogeneous Architectures

5.4.3 Online Refinement of the Performance Models and the Blocking Strategy

5.4.4 Application to Other Linear Algebra Algorithms

5.5 Conclusion

References

Chapter6 Automatic Tuning of the Division Number in the Multiple Division Divide-and-Conquer for Real Symmetric Eigenproblem

6.1 Introduction

6.2 DCk Algorithm and Deflation

6.3 Deflation Occurrence Rate (DOR)

6.4 Proposal of Algorithm to Estimate the Optimal Division Number

6.5 Numerical Experiment

6.6 Summary

References

Chapter7 Automatically Tuned Mixed-Precision Conjugate Gradient Solver

7.1 Introduction

7.2 Iterative Refinement

7.3 Choosing the Target Residual Reduction for the Inner Solver

7.4 Stopping the Iterative Refinement

7.4.1 Stopping Based on Threshold

7.4.2 Stopping Based on Condition Number Estimation

7.4.3 Combined Stopping Method

7.5 Condition Number Estimation

7.6 Conclusions

References

Chapter8 Automatically Tuned Sparse Eigensolvers

8.1 Introduction

8.2 Background: AT Research Trends

8.2.1 Definition of AT

8.2.2 Six Studies on AT

8.2.3 AT Research Trends

8.3 Proposal of AT-Restarted-Lanczos

8.3.1 Restarted-Lanczos and Its Problem

8.3.2 Preliminary Experiment

8.3.3 Proposal of the Run-Time Automatic Tuning Algorithm

8.3.4 Evaluations

8.4 Conclusions

References

Chapter9 Systematic Performance Evaluation of Linear Solvers Using Quality Control Techniques

9.1 Introduction

9.2 Systematic Performance Evaluation and Systematic Analyses for Numerical Computation Algorithms

9.2.1 Systematic Performance Evaluation of Solution Algorithms

9.2.2 Construction of the Performance Information DB on the Solution Algorithms

9.3 Quality Control in the Solution Process

9.3.1 Quality Control Techniques

9.3.2 Systematic Performance Evaluation Using Survey Charts

9.4 Analysis of Causes of Poor Solution Quality

9.4.1 Preconditioning of Solution Algorithm for Linear Equations

9.4.2 Residual Vector and Convergence Criterion for Each Preconditioning System

9.5 Concluding Remarks

References

Chapter 10 Application of Alternating Decision Trees in Selecting Sparse Linear Solvers*

10.1 Introduction

10.2 Machine Learning Methods

10.2.1 Adaboost

10.2.2 Alternating Decision Trees

10.3 Solver Selection as a Classification Problem

10.3.1 Feature Selection and Computation

10.4 Applying Machine Learning

10.5 Experimental Results

10.5.1 Experiment 1: Classification on Linear Systems Generated from PDE-based Simulation Code

10.5.2 Experiment 2: Classification on Only Coefficient Matrices

10.6 Conclusions and Future Plans

References

Chapter11 Toward Automatic Performance Tuning for Numerical Simulations in the SILC Matrix Computation Framework

11.1 Introduction

11.2 The SILC Matrix Computation Framework

11.3 Performance Modeling

11.4 Experiments

11.4.1 Cloth Simulation

11.4.2 Fluid Simulation

11.4.3 Simple Initial Value Problem

11.5 Automatic Performance Tuning

11.5.1 Autotuning Mechanism for Numerical Simulations in SILC

11.5.2 Related Work and Discussions

11.6 Concluding Remarks

References

Chapter12 Exploring Tuning Strategies for Quantum Chemistry Computations

12.1 Introduction

12.2 Related Works

12.3 Methodology

12.4 Performance Results and Observations

12.5 Tuning Strategy

12.6 Conclusions and Future Work

References

Chapter13 Automatic Tuning of CUDA Execution Parameters for Stencil Processing

13.1 Introduction

13.2 Related Work

13.3 Performance Tuning for CUDA

13.4 Automatic Performance Tuning of CUDA Execution Parameters

13.4.1 Parameter Exploration Space

13.4.2 Auto-Tuning Mechanism

13.5 Performance Evaluation

13.5.1 Automatic Tuning on Himeno Benchmark

13.5.2 Automatic Tuning on LU Decomposition

13.6 Conclusions

References

Chapter14 Static Task Cluster Size Determination in Homogeneous Distributed Systems

14.1 Introduction

14.2 Problem Definition and Assumptions

14.2.1 Assumed Model

14.2.2 Problems in Conventional Cluster Merging

14.2.3 Requirements for Reducing Both the Schedule Length and the Number of Processors

14.3 Definition of an Indicative Value for Schedule Length

14.3.1 Abstract of Worst Schedule Length

14.3.2 WSL Definition

14.4 Derivation of Cluster Size for Minimizing WSL

14.4.1 An Upper Bound of WSL

14.4.2 Derivation of dopt

14.4.3 Relationship Between WSLs and Schedule Length

14.4.4 Requirements for Minimizing WSL in a Task Clustering

14.5 Task Clustering

14.5.1 Overview of the Algorithm

14.5.2 Cluster Selection Policies

14.6 Experimental Evaluation

14.6.1 Comparison Targets

14.6.2 Simulation Setup

14.6.3 Comparison of WSLS and Schedule Length in the Fixed Number of Processors

14.6.4 Processor Utilization

14.6.5 Comparison of WSLS and Schedule Length of Real Application DAGs

14.6.6 Discussion

14.7 Conclusion and Future Works

References

Part III Evolution to a General Paradigm

Chapter15 Algorithmic Parameter Optimization of the DFO Method with the OPAL Framework

15.1 Introduction

15.2 Optimization of Algorithmic Parameters

15.2.1 Black Box Construction

15.2.2 Direct Search Algorithms

15.3 The OPAL Package

15.3.1 The OPAL Structure

15.3.2 Usage of OPAL

15.4 Application to Derivative-Free Optimization

15.4.1 General Description of DFO

15.4.2 Two DFO Parameter Optimization Problems

15.4.3 Numerical Results

15.5 Discussion

References

Chapter16 A Bayesian Method of Online Automatic Tuning

16.1 Introduction

16.2 Automatic Tuning Concepts

16.3 Review of the Proposed Methods

16.3.1 Online Automatic Tuning

16.3.2 Tuning Based on Cost Function Modeling

16.3.3 Bayesian Analysis to Treat Uncertainties

16.3.4 Bayesian Suboptimal Sequential Experimental Design

16.3.5 Desirable Properties of Mathematical Methods for Automatic Tuning

16.3.6 Infinite Dilution

16.3.7 Pseudocode of the Proposed Method

16.4 Evaluation

16.4.1 Infinite Dilution with Random Sampling

16.4.2 Performance Evaluation

16.5 Conclusion

References

Chapter17 ABCLibScript: A Computer Language for Automatic Performance Tuning

17.1 Introduction

17.2 The FIBER Framework

17.2.1 FIBER Framework Basics

17.2.2 The Two Users and Auto-tuning Software Construction Assumption

17.2.2.1 Software Developer Phase

17.2.2.2 Software User (End-User) Phase

17.3 The ABCLibScript

17.4 Examples of ABCLibScript Descriptions

17.4.1 Software Developer API

17.4.2 End-User API: Before Execute-Time Auto-tuning

17.4.3 Other Programming Examples for Software Developers Using ABCLibScript

17.4.3.1 Install-Time Auto-tuning

17.4.3.2 Before Execute-Time Auto-tuning

17.4.3.3 Run-Time Auto-tuning

17.5 Future Direction of ABCLibScript

17.5.1 Evaluation of Compiler Optimization and Hardware Performance

17.5.2 Adapting ABCLibScript to Embedded Systems

17.5.3 Adapting ABCLibScript to Low-Power Optimization

17.6 Concluding Remarks

References

Chapter18 Automatically Tuning Task-Based Programs for Multicore Processors

18.1 Introduction

18.2 Example

18.2.1 Task Extensions

18.2.2 Execution

18.2.3 Scheduling for Multicore Processor

18.3 Implementation Synthesis

18.3.1 Dependence Analysis

18.3.2 Profiling

18.3.3 Candidate Implementation Synthesis

18.3.4 Simulation Stage

18.3.5 Directed-Simulated Annealing

18.3.5.1 Generation of Optimized Implementation

18.3.6 Dynamic Scheduling

18.4 Evaluation

18.4.1 Benchmarks

18.4.2 Accuracy of Scheduling Simulator

18.4.3 Optimality of Directed Simulated Annealing

18.4.4 Generality of Synthesized Implementation

18.4.5 Overhead of Bamboo

18.5 Related Work

18.6 Conclusion

References

Chapter19 Efficient Program Compilation Through Machine Learning Techniques

19.1 Introduction

19.1.1 Motivation

19.2 Design and Implementation

19.2.1 Preparing for Data Collection

19.2.2 Gathering Training Data

19.2.3 Learning Process

19.2.4 Deployment Process

19.3 Experimental Setup

19.4 Results and Discussion

19.4.1 Quality of Training Data

19.4.2 Classifier Evaluation

19.4.3 Other Benchmarks

19.5 Related Work

19.6 Conclusions and Future Work

19.7 Acknowledgments and Trademarks

References

Chapter20 Autotuning and Specialization: Speeding up Matrix Multiply for Small Matrices with Compiler Technology

20.1 Introduction

20.2 Compiler Technology: Autotuning and Specialization

20.2.1 Optimization Strategy

20.2.2 Specialization and Transformation Using CHiLL

20.2.3 Autotuning: Heuristics for Pruning the Search Space

20.2.4 Building the Library

20.3 Experiments

20.3.1 Experimental Environment

20.3.2 Generating the Library

20.3.3 Evaluating the Pruning Heuristics

20.3.4 Performance Results

20.4 Related Work

20.5 Conclusion

References

Index