Improved DSM efficiency, flexibility, and correctness [Elektronische Ressource] / Ronald Veldema

DepartmentInformatik
TechnicalReportCS-2010-03
Ronald Veldema
Improved DSM Efficiency, Flexibility, and
Correctness
January 2010
Please cite as:
Ronald Veldema, “Improved DSM Efficiency, Flexibility, and Correctness,” University of Erlangen, Dept. of Computer
Science, Technical Report CS-2010-03, January 2010.
Friedrich-Alexander-Universität Erlangen-Nürnberg
Department Informatik
Martensstr. 3 91058 Erlangen Germany
www.informatik.uni-erlangen.deContents
1 Introduction 5
2 A Proposal for OpenMP for Java 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Differences to the C++ OpenMP Specification . . . . . . . . . . . . . . . 9
2.3.1 Pragmas and Conditional Compilation . . . . . . . . . . . . . . . 9
2.3.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Specific Aspects of a Java Binding . . . . . . . . . . . . . . . . . . . . . . 12
2.4.1 Java-OpenMP Memory Model . . . . . . . . . . . . . . . . . . . . 12
2.4.2 Interaction between Parallel Regions and Java Threads . . . . . 13
2.4.3 Exception Management . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Runtime Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.1 Runtime Support Library . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.2 Object-pooling Support . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.3 Environment Variables . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 A Reference Implementation of Java-OpenMP in Jackal . . . . . . . . . 15
2.6.1 Performance evaluation of a Jav Version of the Lattice-
Boltzmann Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Reparallelization and Migration 19
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Reparallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Repartitioning of work-sharing constructs . . . . . . . . . . . . . 22
3.3.2 Loop schedule types . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.4 Context for added worker threads . . . . . . . . . . . . . . . . . . 25
3.3.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.1 Thread Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.2 Multi-process checkpointing . . . . . . . . . . . . . . . . . . . . . 28
3.4.3 Interaction with reparallelization . . . . . . . . . . . . . . . . . . . 29
3.5 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5.1 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5.2 Overheads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5.3 Speedup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
12 CONTENTS
3.5.4 Migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Heterogeneous Thread Migration 35
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 Issues of heterogeneous thread migration . . . . . . . . . . . . . . 37
4.1.2 of migration heuristics . . . . . . . . . . . . . . . . . . . . . 38
4.1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Jackal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1 Example UDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3.2 How to use UDS strings . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.3 Record and Restore of thread stacks . . . . . . . . . . . . . . . . . 42
4.3.4 Expert level aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 A Framework for Application Migration 53
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Design Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3 OGRE: Open Grid Research Environment . . . . . . . . . . . . . . . . . . 56
5.3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.2 Application Life Cycle . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3.3 Migration Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3.4 Grid-wide File System . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.3.5 Application Adapter . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4.1 GridFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.4.2 Migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6 Tapir’s Multi-core Support 65
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2 Language features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.1 Functional language core . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.2 Mutable Arguments are created by Flow expressions . . . . . . 69
6.2.3 Reduction types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2.4 Support for OO-style polymorphism . . . . . . . . . . . . . . . . 71
6.2.5 for code reuse . . . . . . . . . . . . . . . . . . . 72
6.2.6 Multi-dimensional arrays with named dimensions . . . . . . . . 72
6.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3.1 Cuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.3.2 Threaded execution . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.3.3 Array Implementer Classes . . . . . . . . . . . . . . . . . . . . . . 75
6.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.4.1 Synthetic micro-benchmarks . . . . . . . . . . . . . . . . . . . . . 76
6.4.2 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 76CONTENTS 3
6.4.3 LBM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.4.4 Computational network . . . . . . . . . . . . . . . . . . . . . . . . 77
6.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7 RDMA based DSM Protocols 79
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.3 DSM protocol template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.4 Object requests by means of RDMA . . . . . . . . . . . . . . . . . . . . . 83
7.5 Processing the list(s) of cached objects . . . . . . . . . . . . . . . . . . . . 85
7.5.1 Invalidation protocol handlers . . . . . . . . . . . . . . . . . . . . 85
7.5.2 RDMA-based update protocol handlers . . . . . . . . . . . . . . . 85
7.6 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8 Tapir’s Model-checking Support 93
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.2 Self-consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
8.3 Aspect oriented testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.4 Application specific code transformations to reduce the state space . . . 99
8.4.1 Transformation rules . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.4.2 Compile-time predicates . . . . . . . . . . . . . . . . . . . . . . . . 100
8.4.3 Propagation rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.5 Application specific black boxing to reduce the state space . . . . . . . . 101
8.5.1 Locks, condition variables, and compile-time asserts . . . . . . . 102
8.5.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.6 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.8 conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .