JavaScript is disabled for your browser. Some features of this site may not work without it.
Implementing a run-time library for a parallel MATLAB compiler
Malishevsky, Alexey
Date:
1998-04-09
Abstract:
Programming parallel machines has been a di cult and unrewarding task. The short lifespan
of parallel machines and their incompatibility have made it di cult to utilize them. Our goal
here is to create an environment for parallel computing which allows users to take advantage
of parallel computers without writing parallel programs. MATLAB is accepted everywhere as a
standard of computing, being very powerful, portable, and available on many computers. Its slow
speed limits its utility as a language for manipulating large data sets. However, the emergence of
publicly available parallel libraries like ScaLAPACK has made it possible to implement a portable
MATLAB compiler targeted for parallel machines. My project was the implementation of the
run-time support for such a compiler. The system implements a subset of MATLAB functionality.
Benchmarking ten MATLAB scripts reveals performance gains over the MATLAB interpreter. In
addition, I have studied various data distributions and their e ect on parallel performance. This
report describes the parallel MATLAB compiler, the run-time library, and its implementation. It
presents performance data collected on a variety of parallel platforms as well as the e ect of choice
of the data distributions on performance.
Description:
1 Introduction 11
2 Previous Work 13
3 MATLAB to C Compiler 14
3.1 An Overview of the Compilation Process . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Inline Loop Generation vs. Calls to the Run-time Library for Elementwise Operations . 17
4 Looking for the Best Data Distribution 18
5 Overview of the Run-time Library 19
5.1 Stages of Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.1.1 The MPI Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.1.2 The ScaLAPACK Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.1.3 Data Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Diagram of Module Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.3 ScaLAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.4 The Current Run-time Library Functionality . . . . . . . . . . . . . . . . . . . . . . . . 24
6 The Implementation of the Run-time Library 26
6.1 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.4 The Type and Shape of Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.5 Initialization and Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.5.1 The Initialization of the MPI Library and the Creation of Communication Groups 28
6.5.2 The blacs Data Structure, BLACS contexts, and their Initialization . . . . . . . 29
6.5.3 The Initialization of Arrays of Pointers to Function Names . . . . . . . . . . . . 30
6.5.4 Matrix Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.6 Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.7 Run-time Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.8 Implementation of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.8.1 Trapz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.8.2 Array Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.8.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.8.4 Matrix-Vector Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.8.5 Vector-Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.8.6 Local Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.8.7 Outer Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.8.8 Dot Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.8.9 Mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.8.10 Matrix Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.8.11 Matrix Back Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.8.12 Matrix Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.8.13 Transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.8.14 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.8.15 Svd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.8.16 Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.8.17 Rank, Norm, and Cond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.8.18 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.8.19 Poly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.8.20 Polyval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.8.21 Min and Max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.8.22 Matrix Power . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.8.23 QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.8.24 Vector Init . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.8.25 Real/Imag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.8.26 Conj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.8.27 Flipud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.8.28 Fliplr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.8.29 Hess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.8.30 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.8.31 Fft and i t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6.8.32 Interp1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7 Benchmark Scripts 44
7.1 Conjugate Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.2 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.3 Ocean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.4 An n-body Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.5 Bar Impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.6 Linear Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.7 Centroid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.8 Wing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.9 Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.10 Mortgage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.11 Rector Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8 The Environment 47
9 Results and Explanations 47
9.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
9.2 Comparing the Performance on Di erent Platforms . . . . . . . . . . . . . . . . . . . . 48
9.2.1 The Sun Enterprise Server 4000 and the Meiko CS-2 . . . . . . . . . . . . . . . 48
9.2.2 A Cluster of Four SparcServer 20 Workstations . . . . . . . . . . . . . . . . . . 49
9.2.3 A Cluster of Ten SparcStation 4 Workstations . . . . . . . . . . . . . . . . . . . 49
9.2.4 A Cluster of Pentium II's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9.3 Comparing the Performance of Individual Scripts . . . . . . . . . . . . . . . . . . . . . 51
9.3.1 Conjugate Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.3.2 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.3.3 Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.3.4 Ocean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 9.3.5 Bar Impact . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.3.6 Centroid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.3.7 Linear Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.3.8 Wing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.3.9 Mortgage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9.3.10 An n-body Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
9.3.11 Rector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
10 Choosing the Data Distribution Parameters for Scripts 54
10.1 Selecting the Shape of the Virtual Processor Grid . . . . . . . . . . . . . . . . . . . . . 54
10.2 Selecting the Block Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
11 Choosing the Data Distribution Parameters for the MATLAB Operators and Built-
in Functions 56
11.1 Selecting the Shape of the Virtual Processor Grid . . . . . . . . . . . . . . . . . . . . . 56
11.2 Selecting the Block Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12 The Performance of Individual MATLAB Operators and Built-in Functions 59
13 Prediction of a Script's Performance 61
14 Analyzing Feasibility of Scripts for Parallelization 63
14.1 An Overview of the Limitations of Otter . . . . . . . . . . . . . . . . . . . . . . . . . . 63
14.2 Time Complexity of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
14.3 Array Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
14.4 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
15 Future Work 66
15.1 The Full Functionality of the Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
15.2 Static Code Analysis and Automatic Selection of the Data Distribution Parameters . . 66
15.3 Array Slicing Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
15.4 Making an External Interface to the Library . . . . . . . . . . . . . . . . . . . . . . . . 67
15.5 Parallel I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 15.6 Replacing ScaLAPACK calls with LAPACK calls for Sequential Execution . . . . . . . 68
16 Conclusions 69
A Standard Deviations of the Running Time (Percentage of Mean) 72
A.1 Sun Enterprise Server 4000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
A.2 The Meiko CS-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
A.3 A Cluster of SparcStation 4 Workstations . . . . . . . . . . . . . . . . . . . . . . . . . . 74
A.4 A Cluster of SparcServer 20 Workstations . . . . . . . . . . . . . . . . . . . . . . . . . 75
A.5 A Cluster of Pentium II's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
B Conjugate Gradient Script 77
C Transitive Closure Script 79
D Ocean Script 81
E An n-body Problem Script 84
F Barimpact Scripts 86
F.1 Barimpacrun Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
F.2 Barimpac Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
G Linear Interpolation Script 88
H Sphere Script 90
I Centroid Script 91
J Mortgage Script 92
K Wing Script 94
L Rector Scripts 98
L.1 Rectorrun Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
L.2 Rector Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 M Compiled C Code of Ocean Script 101
This item appears in the following Collection(s)
Search ScholarsArchive@OSU
Browse
-
All of ScholarsArchive@OSU
-
This Collection
