Exploring the DataFlow Supercomputing Paradigm (eBook)

Example Algorithms for Selected Applications

Veljko Milutinovic, Milos Kotlar (Herausgeber)

eBook Download: PDF

2019
315 Seiten
Springer International Publishing (Verlag)
978-3-030-13803-5 (ISBN)

Infos

This useful text/reference describes the implementation of a varied selection of algorithms in the DataFlow paradigm, highlighting the exciting potential of DataFlow computing for applications in such areas as image understanding, biomedicine, physics simulation, and business.

The mapping of additional algorithms onto the DataFlow architecture is also covered in the following Springer titles from the same team: DataFlow Supercomputing Essentials: Research, Development and Education, DataFlow Supercomputing Essentials: Algorithms, Applications and Implementations, and Guide to DataFlow Supercomputing.

Topics and Features: introduces a novel method of graph partitioning for large graphs involving the construction of a skeleton graph; describes a cloud-supported web-based integrated development environment that can develop and run programs without DataFlow hardware owned by the user; showcases a new approach for the calculation of the extrema of functions in one dimension, by implementing the Golden Section Search algorithm; reviews algorithms for a DataFlow architecture that uses matrices and vectors as the underlying data structure; presents an algorithm for spherical code design, based on the variable repulsion force method; discusses the implementation of a face recognition application, using the DataFlow paradigm; proposes a method for region of interest-based image segmentation of mammogram images on high-performance reconfigurable DataFlow computers; surveys a diverse range of DataFlow applications in physics simulations, and investigates a DataFlow implementation of a Bitcoin mining algorithm.

This unique volume will prove a valuable reference for researchers and programmers of DataFlow computing, and supercomputing in general. Graduate and advanced undergraduate students will also find that the book serves as an ideal supplementary text for courses on Data Mining, Microprocessor Systems, and VLSI Systems.

Dr. Veljko Milutinovic teaches DataFlow supercomputing in the School of Informatics, Computing, and Engineering at Indiana University, Bloomington, IN, USA, and previously served for about a decade on the faculty of Purdue University in West Lafayette, IN, USA. He is a co-designer of DARPA's first GaAs RISC microprocessor on 200MHz and a co-designer of the DARPA's 4096-processor systolic array. He is a Life Fellow of the IEEE and a Life Member the ACM. He is a Member of The Academy of Europe, a Member of the Serbian National Academy of Engineering, and a Foreign Member of the Montenegrin Academy of Sciences and Arts. He serves as a Senior Advisor to Maxeler Technologies in London, UK.

Mr. Milos Kotlar is a Software Engineer at the Swiss-Swedish company ABB (ASEA Brown Boveri) of Zurich, Switzerland and a Ph.D. student at the School of Electrical Engineering at the University of Belgrade, Serbia. He serves as a TA for DataFlow supercomputing courses and as an RA for DataFlow supercomputing research in the domain of tensor calculus.

Inhalt

Preface 6
Contents 8
Contributors 10
Part I Theoretical Issues 12
1 Method of Big-Graph Partitioning Using a Skeleton Graph 13
1.1 Introduction 14
1.1.1 Proposed Method of Graph Partitioning 15
1.1.2 Contributions 16
1.1.3 Overview 17
1.2 Distributed Triple-Store Setup 18
1.2.1 Architecture 18
1.2.2 Distributed Query Execution System 20
1.3 Formalization and Statistics 23
1.3.1 Formalization 24
1.3.2 Computing Statistics 27
1.4 Graph Partitioning Method 29
1.4.1 Semantic Distribution 30
1.4.2 Computing Skeleton Graph 34
1.4.3 Clustering Skeleton Graph 37
1.4.4 Triple-Pattern Localization 40
1.4.5 Related Work 42
1.5 Empirical Evaluation 43
1.5.1 Benchmark Environment 44
1.5.2 Benchmark Results on Different Distribution Algorithms 45
1.6 Conclusion 47
References 48
2 On Cloud-Supported Web-Based Integrated Development Environment for Programming DataFlow Architectures 50
2.1 Introduction 51
2.2 The Control-Flow Hardware 51
2.3 The DataFlow Hardware 52
2.4 The Maxeler Framework 53
2.5 The MaxIDE Framework 56
2.6 The WebIDE Framework 56
2.7 Conclusion 58
References 58
Part II Applications in Mathematics 61
3 Minimization and Maximization of Functions: Golden-Section Search in One Dimension 62
3.1 Introduction 62
3.2 Existing Solutions 66
3.3 Essence of the DataFlow Paradigm 69
3.4 Minimization or Maximization of Functions 73
3.4.1 Unimodality 75
3.5 Golden-Section Search 77
3.5.1 Derivation of the Method 77
3.5.2 The control-flow Implementation 81
3.5.3 The DataFlow Implementation 82
3.6 Performance Evaluation 89
3.6.1 MAX4 Card Usage Evaluation 89
3.6.2 Execution Time 89
3.6.3 Test Examples 91
3.6.4 Test Results and Comparison with control-flow paradigm 92
3.6.5 Cluster Testing 93
3.7 Conclusion 94
References 96
4 Matrix-Based Algorithms for DataFlow Computer Architecture: An Overview and Comparison 98
4.1 Introduction 98
4.2 DataFlow Computation Paradigm 100
4.2.1 Maxeler Architecture 100
4.2.2 Suitable Problems for DataFlow Implementation 102
4.2.3 Acceleration Techniques 103
4.2.4 DataFlow Programming 104
4.3 Multiplication of a Matrix and Vector 104
4.3.1 Computer Representation 106
4.3.2 Problem Definition 107
4.3.3 Rowwise Matrix Access 108
4.3.4 Columnwise Matrix Access 112
4.3.5 Stripped Matrix Access 115
4.3.6 Multiplying a Matrix with a Set of Vectors 117
4.3.7 Discussion 120
4.4 Multiplication of Matrices 121
4.4.1 Problem Definition 121
4.4.2 Algorithmic Improvements 122
4.4.3 Algorithm Tuning 122
4.4.4 Naïve Matrix Multiplication 123
4.4.5 Block Matrix Multiplication 127
4.4.6 Performance Comparison 129
4.5 Extending Matrix Algorithms 133
4.5.1 Matrix Exponentiation 133
4.5.2 Counting Walks in a Graph 133
4.5.3 Counting Triangles in a Graph 134
4.5.4 Semiring Generalizations 135
4.5.5 All-Pairs Shortest Paths 135
4.6 Conclusions 136
References 137
5 Application of Maxeler DataFlow Supercomputing to Spherical Code Design 139
5.1 Introduction 139
5.2 Optimization Methods 141
5.2.1 Direct Optimization 141
5.2.2 Variable Repulsion Force Method 142
5.2.3 Force Loosening 144
5.3 Implementation 145
5.3.1 Software Implementation 146
5.3.2 Hardware Implementation 146
5.3.3 Performance 149
5.4 Results 151
5.4.1 Minimum Distances 151
5.4.2 Code Performance 152
5.5 Methodology Considerations 154
References 172
Part III Applications in Image Understanding, Biomedicine, Physics Simulation, and Business 175
6 Face Recognition Using Maxeler DataFlow 176
6.1 Introduction 177
6.2 Application of Face Recognition 182
6.3 Issues and Technical Challenges 184
6.4 Existing Solutions 186
6.5 Essence of the DataFlow Implementation 188
6.6 Comparison of GPU and FPGA Characteristics 192
6.7 Details of the Implementation 194
6.8 Some Performance Indicators 195
6.9 Conclusion 198
References 199
7 Biomedical Images Processing Using Maxeler DataFlow Engines 202
7.1 Introduction 203
7.2 Background 205
7.2.1 Field-Programmable Gate Arrays 205
7.2.2 DataFlow Computing 206
7.2.3 Maxeler's DataFlow Engines 207
7.3 Region-of-Interest-Based Image Segmentation Algorithm for (Breast) Mammogram Images on Maxeler's DFE 209
7.3.1 Background Partition Removal Algorithm 209
7.3.2 Pectoral Muscle Removal 211
7.3.3 Mapping the Region-of-Interest-Based Image Segmentation Algorithm for (Breast) Mammogram Images on DFE 211
7.3.4 Implementation Results and Discussions 217
7.4 Filtering and 3D Visualization of Murine Lungs on Maxeler's DFE 219
7.4.1 Thresholding and Binarization 222
7.4.2 Median Filter 225
7.4.3 Marching Cubes Algorithm 226
7.4.4 Implementation Results and Discussions 227
7.5 Conclusion 230
References 231
8 An Overview of Selected DataFlow Applications in Physics Simulations 233
8.1 Introduction 233
8.2 DataFlow Hardware 234
8.3 Maxeler AppGallery 236
8.4 Selected Examples of DataFlow Applications in Physics Simulations 238
8.4.1 N-Body Simulation 238
8.4.2 The Lattice–Boltzmann Method 240
8.4.3 Ray Casting 240
8.5 Conclusion 243
References 243
9 Bitcoin Mining Using Maxeler DataFlow Computers 245
9.1 Introduction 245
9.2 Bitcoin 247
9.2.1 Blockchain 247
9.2.2 Bitcoin Wallets 247
9.2.3 Digital Keys and Bitcoin Addresses 249
9.2.4 Bitcoin Transactions 249
9.2.5 Bitcoin Mining 251
9.3 Multiscale DataFlow Computing 262
9.3.1 DataFlow Engines 263
9.3.2 DataFlow Versus Control-Flow 264
9.4 DataFlow Implementation 266
9.4.1 Used Hardware 268
9.4.2 Used Software 268
9.4.3 DataFlow Application 271
9.5 Tests and Results 286
9.5.1 Test A 286
9.5.2 Test B 288
9.5.3 Test C 290
9.6 Conclusion 293
Appendix 1: BitcoinMinerCpuCode.c 294
Appendix 2: BitcoinMinerEngineParameters.maxj 303
Appendix 3: BitcoinMinerKernel.maxj 304
Appendix 4: BitcoinMinerManager.maxj 309
Appendix 5: SHA256-CPU.c 311
References 314
Index 316

Produkt-Details

• Erscheint lt. Verlag: 27.5.2019
• Reihe/Serie: Computer Communications and Networks
• Reihe/Serie: Computer Communications and Networks
• Zusatzinfo: X, 315 p. 212 illus., 101 illus. in color.
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Technik ► Nachrichtentechnik
• Schlagworte: Big Data • Dataflow • FPGA • Performance Evaluation • Supercomputing
• ISBN-10: 3-030-13803-8 / 3030138038
• ISBN-13: 978-3-030-13803-5 / 9783030138035