Milutinovic / Kotlar Exploring the DataFlow Supercomputing Paradigm

Example Algorithms for Selected Applications
1. Auflage 2019
ISBN: 978-3-030-13803-5
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 318 Seiten

Reihe: Computer Science (R0)

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.

Autoren/Hrsg.

Milutinovic, Veljko

Kotlar, Milos

Inhaltsverzeichnis

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