Implementing a run-time library for a parallel MATLAB compiler Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_projects/mk61rg99w

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Issued
Table of Contents
  • 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
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2009-06-03T22:04:34Z (GMT). No. of bitstreams: 1 Alexey_Malishevsky.pdf: 652020 bytes, checksum: 8f13a3f995497761b8ef17bd35b4562a (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-06-03T22:04:34Z (GMT) No. of bitstreams: 1 Alexey_Malishevsky.pdf: 652020 bytes, checksum: 8f13a3f995497761b8ef17bd35b4562a (MD5)
  • description.provenance : Submitted by Philip Vue (vuep@onid.orst.edu) on 2009-06-03T18:40:11Z No. of bitstreams: 1 Alexey_Malishevsky.pdf: 652020 bytes, checksum: 8f13a3f995497761b8ef17bd35b4562a (MD5)

Relationships

In Administrative Set:
Last modified: 07/05/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items