High Performance Programming for Soft Computing

ContentsContents

Preface v

1. Fundamentals of Soft Computing 1

1.1 Introduction 1

1.2 Type-1 Fuzzy Sets 4

1.3 Fuzzy Logic Systems 6

1.4 Type 2 Fuzzy Sets 9

1.5 Type-2 Fuzzy Inference Systems 11

1.5.1 Interval Type-2 fuzzifi cation stage 12

1.5.2 Interval Type-2 inference stage 12

1.5.3 Type-reduction and defuzzifi cation in an interval 13

Type-2 FIS

1.6 Artifi cial Neural Networks 15

1.6.1 A single neuron 16

1.6.2 ANN architectures 20

1.6.3 The learning process 22

1.6.4 The back-propagation algorithm 26

1.7 Adaptive Neuro-Fuzzy Inference System 27

1.7.1 ANFIS 27

1.7.2 ANFIS architecture 28

1.7.3 Hybrid learning algorithm 29

References 30

2. Introduction to Novel Microprocessor Architectures 33

2.1 Introduction 33

2.2 History of Computer Processors 35

2.2.1 Beginning of the computer processors 36

2.2.2 Modern commercial multicore processors 39

2.3 Basic Components of a Computer 42

2.4 Characteristics of Modern Processors 48

2.5 Classifi cation of Computer Architectures 52

2.5.1 SISD 53

2.5.2 SIMD 53

2.5.3 MISD 55

2.5.4 MIMD 56

2.6 Parallel Computer Memory Architectures 56

2.7 Measuring Performance 58

2.7.1 Computer performance 59

viii High Performance Programming for Soft Computing

2.7.2 Analyzing the performance in multicore/ 63

multiprocessor systems

2.8 Conclusions 69

References 70

3. High-Performance Optimization Methods 72

3.1 Introduction 73

3.2 Unconstrained Iterative Optimization Methods 75

3.2.1 Gradient descent method 76

3.2.2 Newton’s method 77

3.2.3 Conjugate gradient method 78

3.3 Unconstrained Optimization Using Parallel Computing 79

3.3.1 MATLAB mex-fi le implementation 81

3.3.2 Testing algorithm performance 83

3.4 Global Optimization Using Memetic Algorithms 83

3.4.1 Set up of the implemented MA 84

3.4.2 Experiments and results 86

3.5 Concluding Remarks 90

3.6 Apendix 91

References 93

4. Graphics Processing Unit Programming and Applications 94

4.1 Introduction 94

4.2 CUDA: Compute Unifi ed Device Architecture 96

4.2.1 Programming model 96

4.2.2 Kernel functions 97

4.2.3 Thread hierarchy 97

4.2.4 Memory spaces and hierarchy 99

4.3 CUDA Programming: Fractal Generation and Display 100

4.3.1 Code analysis 103

4.3.2 Benchmarking GPU vs. CPU implementation 108

4.4 Conclusions 108

References 109

5. GPU-based Conjugated Gradient Solution for Phase 110

Field Models

5.1 Introduction 110

5.2 Conjugate Gradient Method 111

5.2.1 Solution of a linear system as an optimization 112

problem

5.2.2 Steepest descent (SD) method 113

5.2.3 Conjugate directions method 116

5.2.4 Linear conjugate gradient method 120

5.2.5 Non-linear conjugate gradient method 122

5.3 Phase Field Model 123

5.3.1 Discretization of the Allen-Cahn equation 125

5.3.2 CUSPARSE and CUBLAS 127

5.3.3 GPU-based solution for the A-C equation 127

5.4 Results 128

5.4.1 1-D case 129

5.4.2 2-D case 129

5.5 Conclusions and Future Work 130

References 131

6. Parallel Computing Applied to a Diffusive Model 133

6.1 Introduction 133

6.2 Random Walk 134

6.3 Continuous Distributions 137

6.4 Solution via Finite Difference Approach 139

6.5 High Performance Computing Resources 142

6.6 Conclusions 147

References 147

7. Ant Colony Optimization (Past, Present and Future) 148

7.1 Introduction 148

7.1.1 Introduction to swarm intelligence 149

7.1.2 Biological inspiration 150

7.2 The Simple ACO Algorithm 152

7.3 Ant System 153

7.3.1 Tour construction in ant system 154

7.3.2 Update of pheromone trails 154

7.3.3 ACO for the Traveling Salesman Problem 155

7.4 Elitist AS: An Extension of AS 158

7.5 Ant-Q: Introduction to Q-Learning 158

7.6 Ant Colony System (ACS) 160

7.7 MAX-MIN AS 161

7.8 Rank-based AS 162

7.9 ANTS 163

7.10 BWAS: 2000 163

7.11 10 Hyper–Cube AS (HC–AS): 2001 165

7.12 The Present of ACO: High Performance Computing 166

7.12.1 Introduction to parallel ant colony optimization 166

7.13 Application of SACO in Mobile Robotics 167

7.14 The Future of ACO: A Final Conclusion 168

References 169

8. Tool Path Optimization Based on Ant Colony Optimization 172

for CNC Machining Operations

8.1 Introduction 172

8.2 Introduction to CNC Programming using CAD/CAM 173

ContentsContents ix