xxMiX10: A MATLAB TO X10 COMPILER FOR HIGH PERFORMANCE

MIX10: A MATLAB TO X10 COMPILER FOR HIGH PERFORMANCE

by Vineet Kumar School of Computer Science McGill University, Montrxal Monday, April 14th 2014

a thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Master of Science

Copyright ©x2014 Vineet Kumar

Abstract

Matlab is a popular dynamic array-based language commonly used by students, scientists and engineers who appreciate the interactive development style, the rich set of array operators, the extensive builtin library, and the fact that they do not have to declare static types. Even though these users like to program in Matlab, their computations are often very compute-intensive and are better suited for emerging high performance computing systems. This thesis reports on MiX10, a source-to-source compiler that automatically translates Matlab programs to X10, a language designed for “Performance and Productivity at Scale"; thus, helping scientific programmers make better use of high performance computing systems.

There is a large semantic gap between the array-based dynamically-typed nature of Matlab and the object-oriented, statically-typed, and high-level array abstractions of X10. This thesis addresses the major challenges that must be overcome to produce sequential X10 code that is competitive with state-of-the-art static compilers for Matlab which target more conventional imperative languages such as C and Fortran. Given that efficient basis, the thesis then provides a translation for the Matlab parfor construct that leverages the powerful concurrency constructs in X10.

The MiX10 compiler has been implemented using the McLab compiler tools, is open source, and is available both for compiler researchers and end-user Matlab programmers. We have used the implementation to perform many empirical measurements on a set of 17 Matlab benchmarks. We show that our best MiX10-generated code is significantly faster than the de facto Mathworks’ Matlab system, and that our results are competitive with state-of-the-art static compilers that target C and Fortran. We also show the importance of finding the correct approach to representing the arrays in X10, and the necessity of an IntegerOkay analysis that determines which double variables can be safely represented as integers. Finally, we show that our X10-based handling of the Matlab parfor greatly outperforms the de facto Matlab implementation.

Rxsumx

Matlab est un langage de programmation dynamique, orientx-tableaux communxment utilisx par les xtudiants, les scientifiques et les ingxnieurs qui apprxcient son style de dxveloppement interactif, la richesse de ses opxrateurs sur les tableaux, sa librairie impressionnante de fonctions de base et le fait qu’on aie pas x dxclarer statiquement le type des variables. Bien que ces usagers apprxcient Matlab, leurs programmes nxcessitent souvent des ressources de calcul importantes qui sont offertes par les nouveaux systxmes de haute performance. Cette thxse fait le rapport de MiX10, un compilateur source-x-source qui fait la traduction automatique de programmes Matlab x X10, un langage construit pour "la performance et la productivitx x grande xchelle." Ainsi, MiX10 aide les programmeurs scientifiques x faire un meilleur usage des ressources des systxmes de calcul de haute performance.

Il y a un xcart sxmantique important entre le typage dynamique et le focus sur les tableaux de Matlab et l’approche orientxe-objet, le typage statique et les abstractions de haut niveau sur les tableaux de X10. Cette thxse discute des dxfis principaux qui doivent xtre surmontxs afin de produire du code X10 sxquentiel compxtitif avec les meilleurs compilateurs statiques pour Matlab qui traduisent vers des langages impxratifs plus conventionnels, tels que C et Fortran. Fort de cette fondation efficace, cette thxse dxcrit ensuite la traduction de l’instruction parfor de Matlab afin d’utiliser les opxrations sophistiquxes de traitement concurrent de X10.

Le compilateur MiX10 a xtx implxmentx x l’aide de la suite d’outils de McLab, un projet libre de droits, disponible x la communautx de recherche ainsi qu’aux utilisateurs de Matlab. Nous avons utilisx notre implxmentation afin d’effectuer des mesures empiriques de performance sur un jeu de 17 programmes Matlab. Nous dxmontrons que le code gxnxrx par MiX10 est considxrablement plus rapide que le systxme Matlab de Mathworks et que nos rxsultats sont compxtitifs avec les meilleurs compilateurs statiques qui produisent du code C et Fortran. Nous montrons xgalement l’importance d’une reprxsentation approprixe des tableaux en X10 et la nxcessitx d’une analyse IntegerOkay qui permet de dxterminer quelles variables de type rxel (double) peuvent xtre correctement reprxsentxes par des entiers (int). Finalement, nous montrons que notre traitement de l’instruction parfor en X10 nous permet d’atteindre des vitesses d’exxcution considxrablement meilleures que dans Matlab.

Acknowledgements

I am thankful to my supervisor, Laurie Hendren, whose constant encouragement and guidance not only helped me to understand compilers better, but also helped me become a better writer and a better presenter.

I would like to give a special thanks to David Grove for suggesting this line of research and in helping us understand key parts of the X10 language and implementation.

I am also thankful to the McLab team for building an amazing framework for compiler research on Matlab. In particular, I am thankful to Anton Dubrau (M.Sc.) for helping me understand the McSaf and Tamer frameworks, and Xu Li (M.Sc.) for all the interesting discussions on how to statically compile Matlab.

Finally, I would like to thank my parents and my brother, who made it possible for me to pursue my M.Sc. degree.

Apart from all the wonderful people around me, I am thankful to my computers, Antriksh, Heisenberg, and cougar.cs.mcgill.ca for tirelessly and reliably crunching numbers day in and day out.

This work was supported, in part, by the Natural Sciences and Engineering Research Council of Canada (NSERC).

Table of Contents

Abstract Abstract Acknowledgements Table of Contents List of Figures List of Tables 1 Introduction x1.1 Contributions x1.2 Thesis Outline 2 Introduction to the X10 Programming Language x2.1 Overview of X10’s Key Sequential Features xx2.1.1 Object-oriented Features xx2.1.2 Statements xx2.1.3 Arrays xx2.1.4 Types x2.2 Overview of X10’s Concurrency Features xx2.2.1 Async xx2.2.2 Finish xx2.2.3 Atomic xx2.2.4 At x2.3 Overview of X10’s Implementation and Runtime xx2.3.1 X10 Implementation xx2.3.2 X10 Runtime 3 Background and High-level Design of MiX10 x3.1 Background x3.2 High-level Design of the MiX10 Compiler xx3.2.1 The MiX10 Intermediate Representation 4 Techniques for Efficient Compilation of Matlab Arrays x4.1 Simple Arrays or Region Arrays xx4.1.1 Compilation to Simple Arrays xx4.1.2 Compilation to Region Arrays x4.2 Handling the Colon Expression x4.3 Array Growth 5 Handling Matlab Builtins xx5.0.1 The MiX10 Builtin Support Framework 6 Code Generation for the Sequential Core x6.1 Methods x6.2 Types, Assignments and Declarations x6.3 Loops x6.4 Conditionals x6.5 Function Calls x6.6 Cell Arrays 7 Code Generation for Concurrency in Matlab x7.1 Code Generation for the Matlab parfor Loop Construct x7.2 Introducing Concurrency Controls in Matlab x7.3 Parallelizing Vectorized Instructions 8 The IntegerOkay Analysis x8.1 Need for Declaring Variables to be of Integer Type x8.2 Effect on Performance x8.3 An Overview of the IntegerOkay Analysis x8.4 The Analysis Algorithm xx8.4.1 STEP 1 : Initialization xx8.4.2 STEP 2: The Fixed Point Solver x8.5 An Example 9 Evaluation x9.1 Benchmarks x9.2 Experimental Setup x9.3 X10 Compiler Variations x9.4 Overall MiX10 Performance x9.5 X10 C++ Backend vs. X10 Java Backend xx9.5.1 When Not to Use the X10 -O x9.6 Simple vs. Region Arrays x9.7 Effect of the IntegerOkay Analysis x9.8 Matlab parfor vs. MiX10 Parallel Code x9.9 Summary 10 Related Work x10.1 Alternatives to Matlab x10.2 Other Matlab Compilers x10.3 Compilers Targeting X10 11 Conclusions and Future Work x11.1 Conclusions x11.2 Future Work Bibliography A XML structure for builtin framework B MiX10 IR Grammar

List of Figures

2.1xArchitecture of the X10 compiler2.2xArchitecture of the X10 runtime3.1xOverview of MiX10 structure3.2xStructure of the MiX10 code generator7.1xExample of parfor, Matlab with parfor on the left, generated X10 on the right.7.2xExample of introduced concurrency controls, Matlab with introduced concurrency on the left, generated X10 on the right.9.1xPerformance of MiX10 vs other state-of-the-art static compilers, reported as speedups relative to Mathworks’ Matlab, higher is better.

List of Tables

8.1xRunning times (in seconds) for listings ?? and ??, smaller is better8.2xDefinition of the ▷◁ merge operator9.1xBenchmarks9.2xMiX10 performance comparison : X10 C++ backend vs. X10 Java backend, speedups relative to Mathworks’ Matlab, higher is better9.3xMiX10 performance comparison : Simple arrays vs. Region arrays vs. Specialized region arrays, speedup relative to Mathworks’ Matlab, higher is better9.4xPerformance evaluation for the IntegerOkay analysis, speedups relative to Mathworks’ Matlab, higher is better9.5xPerformance evaluation for MiX10 generated parallel X10 code for the Matlab parfor construct, speedups relative to Mathworks’ Matlab, higher is better

Chapterx1

Introduction

Matlab is a popular numeric programming language, used by millions of scientists, engineers as well as students worldwide[Mol]. Matlab programmers appreciate the high-level matrix operators, the fact that variables and types do not need to be declared, the large number of library and builtin functions available, and the interactive style of program development available through the IDE and the interpreter-style read-eval-print loop. However, even though Matlab programmers appreciate all of the features that enable rapid prototyping, their applications are often quite compute intensive and time consuming. These applications could perform much more efficiently if they could be easily ported to a high performance computing system.

X10 [IBM12], on the other hand, is an object-oriented and statically-typed language which uses cilk-style arrays indexed by Point objects and rail-backed multidimensional arrays, and has been designed with well-defined semantics and high performance computing in mind. The X10 compiler can generate C++ or Java code and supports various communication interfaces including sockets and MPI for communication between nodes on a parallel computing system.

In this thesis we present MIX10, a source-to-source compiler that helps to bridge the gap between MATLAB, a language familiar to scientists, and X10, a language designed for high performance computing systems. MIX10 statically compiles MATLAB programs to X10 and thus allows scientists and engineers to write programs in MATLAB (or use old programs already written in MATLAB) and still get the benefits of high performance computing without having to learn a new language.Also, systems that use MATLAB for prototyping and C++ or Java for production, can benefit from MIX10 by quickly convert- ing MATLAB prototypes to C++ or Java programs via X10

On one hand, all the aforementioned characteristics of Matlab make it a very user-friendly and thus a popular application to develop software among a non-programmer community. On the other hand, these same characteristics make Matlab a difficult language to compile statically. Even the de facto standard, Mathworks’ implementation of Matlab is essentially an interpreter with a JIT accelarator[The02] which is generally slower than statically compiled languages. GNU Octave, which is a popular open source alternative to Matlab and is mostly compatible with Matlab, introduced JIT compilation only in its most recent release 3.8 in March 2014. Before that it was implemented only as an interpreter[Oct]. Lack of formal language specification, unconventional semantics and closed source make it even harder to write a compiler for Matlab. These are some of the challenges that MiX10 shares with other static compilers which convert Matlab to C or Fortran. However, targeting X10 raises some significant new challenges. For example, X10 is an object-oriented, heap-based, language with varying levels of high-level abstractions for arrays and iterators of arrays. An open question was whether or not it was possible to generate X10 code that both maintains the Matlab semantics, but also leads to code that is as efficient as state-of-the-art translators that target C and Fortran. Finding an effective and efficient translation from Matlab to X10 was not obvious, and this thesis reports on the key problems we encountered and the solutions that we designed and implemented in our MiX10 system. By demonstrating that we can generate sequential X10 code that is as efficient as generated C or Fortran code, we then enabled the possibility of leveraging the high performance nature of X10’s parallel constructs. To demonstrate this, we exposed scalable concurrency in Matlab via X10 and examined how to use X10 features to provide a good implementation for Matlab’s parfor construct.

Built on top of McLab static analysis framework[Doh11,xDH12b], MiX10, together with its set of reusable static analyses for performance optimization and extended support for Matlab features, ultimately aims to provide Matlab’s ease of use, sequential performance comparable to that provided by state-of-the art compilers targetting C and Fortran, to support parallel constructs like parfor and to expose scalable concurrency.

1.1 Contributions

The major contributions of this thesis are as follows:

Identifying key challenges: We have identified the key challenges in performing a semantics-preserving efficient translation of Matlab to X10.

Overall design of MiX10: Building upon the McLab frontend and analysis framework, we provide the design of the MiX10 source-to-source translator that includes a low-level X10 IR and a template-based specialization framework for handling builtin operations.

Techniques for efficient compilation of Matlab arrays:

Arrays are the core of Matlab. All data, including scalar values are represented as arrays in Matlab. Efficient compilation of arrays is the key for good performance. X10 provides two types of array representations for multidimensional arrays: (1) Cilk-styled, region-based arrays and (2) rail-backed simple arrays. We compare and contrast these two array forms for a high performance computing language in context of being used as a target language and provide techniques to compile Matlab arrays to two different representations of arrays provided by X10.

Builtin handling framework: We have designed and implemented a template-based system that allows us to generate specialized X10 code for a collection of important Matlab builtin operations.

Code generation strategies for the sequential core: There are some very significant differences between the semantics of Matlab and X10. A key difference is that Matlab is dynamically-typed, whereas X10 is statically-typed. Furthermore, the type rules are quite different, which means that the generated X10 code must include the appropriate explicit type conversion rules, so as to match the Matlab semantics. Other Matlab features, such as multiple returns from functions, a non-standard semantics for for loops, and a very general range operator, must also be handled correctly.

Code generation for concurrency in Matlab: MiX10 not only supports all the key sequential constructs but also supports concurrency constructs like parfor and can handle vectorized instructions in a concurrent fashion. We have also introduced X10-like concurrency constructs in Matlab via structured comments.

Safe use of integer variables: Even after determining the correct use of X10 arrays, we were still faced with a performance gap between the code generated by the C/Fortran systems, and the generated X10 code generated by MiX10. Furthermore, we found that the MiX10 system using the X10 Java backend was often generating better code than with the X10 C++ backend, which was counter-intuitive. We determined that a key remaining problem was overhead due to casting doubles to integers. This casting overhead was quite high, and was substantially higher for the C++ back-end than for the Java back-end (since the casting instructions are handled efficiently by the Java VM). This casting problem arises because the default data type for Matlab variables is double - even variables used to iterate through arrays, and to index into arrays typically have double type, even though they hold integral values. To tackle this issue we developed an IntegerOkay analysis which determines which double variables can be safely converted to integer variables in the generated X10 code, hence greatly reducing the number of casting operations needed.

Open implementation: We have implemented the MiX10 compiler over various Matlab compiler tools provided by the McLab toolkit. In the process we also implemented some enhancements to these existing tools. Our implementation is extensible and allows for others to make further improvements to the generated X10 code, or to reuse the analyses to generate code for other target languages.

Experimental evaluation: We have experimented with our MiX10 implementation on a set of benchmarks. Our results show that our generated code is almost an order of magnitude faster than the Mathworks’ standard JIT-based system, and is competitive with other state-of-the-art tools that generate C/Fortran. Our more detailed results show the importance of using our customized and optimized X10 array representations, and we demonstrate the effectiveness of the IntegerOkay analysis. Finally, we show that our X10-based treatment of parfor significantly outperforms Matlab on our benchmarks.

1.2 Thesis Outline

This thesis is divided into 11 chapters, including this one and is structured as follows.

Chapter 2 provides an introduction to the X10 language and describes how it compares to Matlab from the point of view of language design. Chapter 3 gives a description of various existing Matlab compiler tools upon which MiX10 is implemented, presents a high-level design of MiX10, and explains the design and need of MiX10 IR. In Chapter 4 we compare the two kinds of arrays provided by X10, identify when each of them must be used in the generated code, identify and address challenges involved in efficient compilation of Matlab arrays. Chapter 5 describes the builtin handling framework used by MiX10 to generate specialized code for Matlab builtins used in the source program. Chapter 6 gives a description of efficient and effective code generation strategies for the core sequential constructs of Matlab. A description of code generation for the Matlab parfor construct is provided in Chapter 7, which also describes our strategy to introduce concurrency constructs in Matlab. In Chapter 8 we provide a description of the IntegerOkay analysis to identify variables that are safe to be declared as Long type. Chapter 9 provides performance results for code generated using MiX10 for a suite of benchmarks. It gives a comparison between performance achieved by MiX10 generated code and that generated by the Matlab coder and Mc2For compilers. Chapter 10 provides an overview of related work and Chapter 11 concludes and outlines possible future work.

Introduction to the X10 Programming

Language

In this chapter, we describe key X10 semantics and features to help readers unfamiliar with X10 to have a better understanding of the MiX10

compiler.1  ^{1This chapter is adapted from the tutorial at http://x10.sourceforge.net/documentation/intro/latest/html/}

X10 is an award winning open-source programming language being developed by IBM Research. The goal of the X10 project is to provide a productive and scalable programming model for the new-age high performance computing architectures ranging from multi-core processors to clusters and supercomputersx[IBM12].

X10, like Java, is a class-based, strongly-typed, garbage-collected and object-oriented language. It uses Asynchronous Partitioned Global Address Space (APGAS) model to support concurrency and distributionx[SBP^{+} 12]. The X10 compiler has a native backend that compiles X10 programs to C++ and a managed backend that compiles X10 programs to Java.

2.1 Overview of X10’s Key Sequential Features

X10’s sequential core is a container-based object-oriented language that is very similar to that of Java or C++x[SBP^{+} 12]. An X10 program consists of a collection of classes, structs or interfaces, which are the top-level compilation units. X10’s sequential constructs like if-else statements, for loops, while loops, switch statements, and exception handling constructs throw and tryxcatch are also same as those in Java. X10 provides both, implicit coercions and explicit conversions on types, and both can be defined on user-defined types. The as operator is used to perform explicit type conversions; for example, x as Long{self != 0} converts x to type Long and throws a runtime exception if its value is zero. Multi-dimensional arrays in X10 are provided as user-defined abstractions on top of x10.lang.Rail, an intrinsic one-dimensional array analogous to one-dimensional arrays in languages like C or Java. Two families of multi-dimensional array abstractions are provided: simple arrays, which provide a restricted but efficient implementation, and region arrays which provide a flexible and dynamic implementation but are not as efficient as simple arrays. Listing 2.1 shows a sequential X10 program that calculates the value of π using the Monte Carlo

method.2  2This example is sourced from the tutorial at http://x10.sourceforge.net/tutorials/x10-2.4/Hartree-July-2013/x10-hartree-slides-july2013.pdf

It highlights important sequential and object-oriented features of X10 detailed in the following subsections. It reads an argument from the console in an intrinsic 1 dimensions array(Rail) of String and converts it to a Long value N. It then generates two random numbers and performs computations on them in a loop from 1 to N. Finally, it calculates the value of π and displays the result on the console.

X10’s syntax is similar to that of Java. The object-oriented semantics are also similar to that of Java. Mutable and immutable variables are denoted by keywords var and val respectively. for loops can iterate over a range of values. For e.g. in listing 2.1, the for loop iterates over a LongRange of 1 to N. A LongRange represents a range of Long type integers.

import xx10.util .Random ;xxpublic xclass xSeqPi x{xxxpublic xstatic xdefxmain (args :Rail [String ])x{xxxxxvalxNx=xLong .parse (args (0));xxxxxvarxresult :Double x=x0;xxxxxvalxrand x=xnewxRandom ();xxxxxfor(1.. N)x{xxxxxxxvalxxx=xrand .nextDouble ();xxxxxxxvalxyx=xrand .nextDouble ();xxxxxxxif(x*xx+xy*yx<=x1)xresult ++;xxxxx}xxxxxvalxpix=x4*result /N;xxxxxConsole .OUT.println ("Thexvalue xofxpixisx"x+xpi);xxx}x}

Listingx2.1: Sequential X10 program to calculate value of π using Monte Carlo method

2.1.1 Object-oriented Features

A program consists of a collection of top-level units, where a unit is either a class, a struct or an interface. A program can contain multiple units, however only one unit can be made public and its name must be same as that of the program file. Similar to Java, access to these top-level units is controlled by packages. Below is a description of the core object-oriented constructs in X10:

Class A class is a basic bundle of data and code. It consists of zero or more members namely fields, methods, constructors, and member classes and interfacesx[IBM13b]. It also specifies the name of its superclass, if any and of the interfaces it implements.

Fields A field is a data item that belongs to a class. It can be mutable (specified by the keyword var) or immutable (specified by the keyword val). The type of a mutable field must be always be specified, however the type of an immutable field may be omitted if it’s declaration specifies an initializer. Fields are by default instance fields unless marked with the static keyword. Instance fields are inherited by subclasses, however subclasses can shadow inherited fields, in which case the value of the shadowed field can be accessed by using the qualifier super.

Methods A method is a named piece of code that takes zero or more parameters and returns zero or one values. The type of a method is the type of the return value or void if it does not return a value. If the return type of a method is not provided by the programmer, X10 infers it as the least upper bound of the types of all expressions e in the method where the body of the method contains the statement return e. A method may have a type parameter that makes it type generic. An optional method guard can be used to specify constraints. All methods in a class must have a unique signature which consists of its name and types of its arguments. Methods may be inherited. Methods defined in the superclass are available in the subclasses, unless overridden by another method with same signature. Method overloading allows programmers to define multiple methods with same name as long as they have different signatures. Methods can be access-controlled to be private, protected or public; private methods can only be accessed by other methods in the same class, protected methods can be accessed in the same class or its subclasses, and public methods can be accessed from any code. By default, all methods are package protected which means they can be accessed from any code in the same package. Methods with the same name as that of the containing class are called constructors. They are used to instantiate a class.

Structs A struct is just like a class, except that it does not support inheritance and may not be recursive. This allows structs to be implemented as header-less objects, which means that unlike a class, a struct can be represented by only as much memory as is necessary to represent its fields and with its methods compiled to static methods. It does not contain a header that contains data to represent meta-information about the object. The current version of X10 (version 2.4) does not support mutability and references to structs, which means that there is no syntax to update the fields of a struct and structs are always passed by value.

Function literals X10 supports first-class functions. A function consists of a parameter list, followed optionally by a return type, followed by =>, followed by the body (an expression). For example, (i:Int, j:Int) => (i<j ? foo(i) : foo(j)), is a function that takes parameters i and j and returns foo(i) if i<j and foo(j) otherwise. A function can access immutable variables defined outside the body.

2.1.2 Statements

X10 provides all the standard statements similar to Java. Assignment, if - else and while loop statements are identical to those in Java.

for loops in X10 are more advanced and apart from the standard C-like for loop, X10 provides three different kinds of for loops:

enhanced for loops take an index specifier of the form i in r, where r is any value that implements x10.lang.Iterable[T] for some type T. Code listing 2.2 below shows an example of this kind of for loops:

defxsum(a:Rail [Long ]):Long {xxxxx varxresult :Long x=x0;xxxxx forx(ixinxa){xxxxx xxxx result x+=xi;xxxxx }xxxxx return xresult ;x}

Listingx2.2: Example of enhanced for loop

for loops over LongRange iterate over all the values enumerated by a LongRange(a range of consecutive Long type values). A LongRange is instantiated by an expression like e1..e2 and enumerates all the integer values from a to b (inclusive) where e1 evaluates to a and e2 evaluates to b. Listing 2.3 below shows an example of a for loop that uses

LongRange:

defxsum(N:Long ):Long {xxxxx varxresult :Long x=x0;xxxxx forx(ixinx0..N){xxxxx xxxx result x+=xi;xxxxx }xxxxx return xresult ;x}

Listingx2.3: Example of for loop over

LongRange

for loops over Region allow to iterate over multiple dimensions simultaneously. A Region is a data structure that represents a set of points in multiple dimensions. For instance, a Region instantiated by the expression Region.make(0..5,1..6) creates a 2-dimensional region of points (x,y) where x ranges over 0..5 and y over 1..6. The natural order of iteration is lexicographic. Listing 2.4 below shows an example that calculates the sum of coordinates of all points in a given rectangle:

defxsum(M:Long ,xN:Long ):Long {xxxxx varxresult :Long x=x0;xxxxx valxR:Region x=xx10.regionarray  .Region .make (0.. M,0.. N);xxxxx forx([x,y]xinxR){xxxxx xxxx result x+=xx+y;xxxxx }xxxxx return xresult ;x}

Listingx2.4: Example of for loop over a 2-D

Region

2.1.3 Arrays

In order to understand the challenges of translating Matlab to X10, one must understand the different flavours and functionality of X10 arrays.

At the lowest level of abstraction, X10 provides an intrinsic one-dimensional fixed-size array called Rail which is indexed by a Long type value starting at 0. This is the X10 counterpart of built-in arrays in languages like C or Java. In addition, X10 provides two types of more sophisticated array abstractions in packages, x10.array and x10.regionarray.

Rail-backed Simple arrays are a high-performance abstraction for multidimensional arrays in X10 that support only rectangular dense arrays with zero-based indexing. Also, they support only up to three dimensions (specified statically) and row-major ordering. These restrictions allow effective optimizations on indexing operations on the underlying Rail. Essentially, these multidimensional arrays map to a Rail of size equal to number of elements in the array, in a row-major order.

Region arrays are much more flexible. A region is a set of points of the same rank, where Points are the indexing units for arrays. Points are represented as n-dimensional tuples of integer values. The rank of a point defines the dimensionality of the array it indexes. The rank of a region is the rank of its underlying points. Regions provide flexibility of shape and indexing. Region arrays are just a set of elements with each element mapped to a unique point in the underlying region. The dynamicity of these arrays come at the cost of performance.

Both types of arrays also support distribution across places. A place is one of the central innovations in X10, which permits the programmer to deal with notions of locality. places are discussed in more detail in section 2.2.4

2.1.4 Types

X10 is a statically type-checked language: Every variable and expression has a type that is known at compile-time and the compiler checks that the operations performed on an expression are permitted by the type of that expression. The name c of a class or an interface is the most basic form of type in X10. There are no primitive types.

X10 also allows type definitions, that allow a simple name to be supplied for a complicated type, and for type aliases to be defined. For example, a type definition like public static

type bool(b:Boolean) = Boolean{self=b} allows the use of expression
bool(true) as a shorthand for type Boolean{self=true}.

Generic types X10’s generic types allow classes and interfaces to be declared parameterized by types. They allow the code for a class to be instantiated unbounded number of times, for different concrete types, in a type-safe fashion. For instance, the listing 2.5 below shows a class List[T], parameterized by type T, that can be replaced by a concrete type like Int

at the time of instantiation (var l:List[Int] = new List[Int](item)).

class xList [T]{xxxxx varxitem :T;xxxxx varxtail :List [T]=null ;xxxxx defxthis (t:T){xxxxx xxxx item =t;xxxxx }x}

X10 types are available at runtime, unlike Java(which erases them).

Constrained types X10 allows the programmer to define Boolean expressions (restricted) constraints on a type [T]. For example, a variable of constrained type Long{self != 0} is of type Long and has a constraint that it can hold a value only if it is not equal to 0 and throws a runtime error if the constraint is not satisfied. The permitted constraints include the predicates == and !=. These predicates may be applied to constraint terms. A constraint term is either a final variable visible at the point of definition of the constraint, or the special variable self or of the form t.f where f names a field, and t is (recursively) a constraint term.

2.2 Overview of X10’s Concurrency Features

X10 is a high performance language that aims at providing productivity to the programmer. To achieve that goal, it provides a simple yet powerful concurrency model that provides four concurrency constructs that abstract away the low-level details of parallel programming from the programmer, without compromising on performance. X10’s concurrency model is based on the Asynchronous Partitioned Global Address Space (APGAS) modelx[IBM13a]. The APGAS model has a concept of global address space that allows a task in X10 to refer to any object (local or remote). However, a task may operate only on an object that resides in its partition of the address space (local memory). Each task, called an activity, runs asynchronously parallel to each other. A logical processing unit in X10 is called a place. Each place can run multiple activities. There are four types of concurrency constructs provided by X10x[IBM13b], as described in the following sections:

2.2.1 Async

The fundamental concurrency construct in X10 is async. The statement async S creates a new activity to execute S and returns immediately. The current activity and the “forked" activity execute asynchronously parallel to each other and have access to the same heap of objects as the current activity. They communicate with each other by reading and writing shared variables. There is no restriction on statement S in the sense that it can contain any other constructs (including async). S is also permitted to refer to any immutable variable defined in lexically enclosing scope.

An activty is the fundamental unit of execution in X10. It may be thought of as a very light-weight thread of execution. Each activity has its own control stack and may invoke recursive method calls. Unlike Java threads, activities in X10 are unnamed. Activities cannot be aborted or interrupted once they are in flight. They must proceed to completion, either finishing correctly or by throwing an exception. An activity created by async S is said to be locally terminated if S has terminated. It is said to be globally terminated if it has terminated locally and all activities spawned by it recursively, have themselves globally terminated.

2.2.2 Finish

Global termination of an activity can be converted to local termination by using the finish construct. This is necessary when the programmer needs to be sure that a statement S and all the activities spawned transitively by S have terminated before execution of the next statement begins. For instance in the listing 2.5 below, the use of finish ensures

that the Console.OUT.println("a(1) = " + a(1)); statement is executed

only after all the asynchronously executing operations (async a(i) *= 2; have completed.

//...x//Create xaxRail xofxsize x10,xwith xi' thxelement xinitialized  xtoxixvalxa:Rail [Long ]x=xnewxRail [Long ](10,( i:Long )=>i);xfinish xforx(ixinx0..9) {x//asynchronously  xdouble xevery xvalue xinxthexRail xxxxx async xa(i)x*=x2;x}xConsole .OUT.println ("a(1)x=x"x+xa(1));x//...

Listingx2.5: Example use of

   finish

construct

2.2.3 Atomic

The statement atomic S ensures that the statement S is executed in a single step with respect to all other activities in the system. When S is being executed in one activity all other activities containing s are suspended. However, the atomic statement S must be sequential (it should not contain an async or finish staement), non-blocking (it should not contain a blocking construct like when, explained below) and local (in this context, local means place-local, that is, it must not contain an at construct, explained in Sec.x2.2.4). Consider the code fragment in listing 2.6. It asynchronously adds Long values to a linked-list list and simultaneously holds the size of the list in a variable size. The use of atomic guarantees that no other operation, in any activity, is executed in between (or simultaneously with) these two operations, which is necessary to ensure correctness of the program.

//...xxxxx finish xforx(ixinx0..10) {xxxxx xxxx async xadd(i);xxxxx }x//...xxxxx defxadd(x:Long ){xxxxx xxxx atomic x{xxxxx xxxx xxxx this .list .add(x);xxxxx xxxx xxxx this .size x=xthis .size x+x1;xxxxx xxxx }xxxxx }x//...

Listingx2.6: Example use of

   atomic

construct

Note that, atomic is a syntactic sugar for the construct when (c) , which is the conditional atomic statement based on binary condition (c). Statement when (c) S executes statement S atomically only when c evaluates to true; if it is false, the execution blocks waiting for c to be true. Condition c must be sequential, non-blocking and local.

2.2.4 At

A place in X10 is the fundamental processing unit. It is a collection of data and activities that operate on that data. A program is run on a fixed number of places. The binding of places to hardware resources (e.g. nodes in a cluster, accelerators) is provided externally by a configuration file, independent of the program.

The at construct provides a place-shifting operation, that is used to force execution of a statement or an expression at a particular place. An activity executing at (p) S suspends execution at the current place; The object graph G at the current place whose roots are all the variables V used in S is serialized, and transmitted to place p, deserialized (creating a graph G′ isomorphic to G), an environment is created with the variables V bound to the corresponding roots in G′, and S executed at p in this environment. On local termination of S, computation resumes after at (p) S in the original location. The object graph is not automatically transferred back to the originating place when S terminates: any updates made to objects copied by an at will not be reflected in the original object graph.

2.3 Overview of X10’s Implementation and Runtime

In order to understand the compilation flow of the MiX10 compiler and enhancements made to the X10 compiler for efficient use of X10 as a target language for Matlab, it is important to understand the design of the X10 compiler and its runtime environment.

2.3.1 X10 Implementation

X10 is implemented as a source-to-source compiler that translates X10 programs to either C++ or Java. This allows X10 to achieve critical portability, performance and interoperability objectives. The generated C++ or Java program is, in turn, compiled by the platform C++ compiler to an executable or to class files by a Java compiler. The C++ backend is referred to as Native X10 and the Java backend is called Managed X10.

The source-to-source compilation approach in X10 provides three main advantages: (1) It makes X10 available for a wide range of platforms; (2) It takes advantage of the underlying classical and platform-specific optimizations in C++ or Java compilers, while the X10 implementation includes only X10 specific optimizations; and (3) It allows programmers to take advantage of the existing C++ and Java libraries.

Figure 2.1 shows the overall architecture of the X10 compilerx[IBM13b].

PIC Figurex2.1: Architecture of the X10 compiler 2.3.2 X10 Runtime

Figure 2.2 shows the major components of the X10 runtime and their relative hierarchyx[IBM13b].

The runtime bridges the gap between application program and the low-level network transport system and the operating system. X10RT, which is the lowest layer of the X10 runtime, provides abstraction and unification of the functionalities provided by various network layers.

The X10 Language Native Runtime provides implementation of the sequential core of the language. It is implemented in C++ for native X10 and Java for Managed X10.

XRX Runtime, the X10 runtime in X10 is the core of the X10 runtime system. It provides implementation for the primitive X10 constructs for concurrency and distribution (async, finish, atomic and at). It is primarily written in X10 over a set of low-level APIs that provide a platform-independent view of processes, threads, synchronization mechanisms and inter-process communication.

At the top of the X10 runtime system, is a set of core class libraries that provide fundamental data types, basic collections, and key APIs for concurrency and distribution.

PIC Figurex2.2: Architecture of the X10 runtime

Background and High-level Design of MiX10

3.1 Background

MiX10 is implemented on top of several existing Matlab compiler tools. The overall structure is given in Figure 3.1, where the new parts are indicated by the shaded boxes, and future work is indicated by dashed boxes.

PIC Figurex3.1: Overview of MiX10 structure

As illustrated at the top of the figure, a Matlab programmer only needs to provide an entry-point Matlab function (called myprog.m in this example), plus a collection of other Matlab functions and libraries (directories of functions) which may be called, directly or indirectly, by the entry point. The programmer may also specify the types and/or shapes of the input parameters to the entry-point function. As shown at the bottom of the figure, our MiX10 compiler automatically produces a collection of X10 output files which contain the generated X10 code for all reachable Matlab functions, plus one X10 file called mix10.x10 which contains generated and specialized X10 code for the required builtin Matlab functions. Thus, from the Matlab programmer’s point of view, the MiX10 compiler is quite simple to use.

Matlab is actually quite a complicated language to compile, starting with its rather unusual syntax, which cannot be parsed with standard LALR techniques. There are several issues that must be dealt with including distinguishing places where white space and new line characters have syntactic meaning, and filling in missing end keywords, which are sometimes optional. The McLab front-end handles the parsing of Matlab through a two step process. There is a pre-processing step which translates Matlab programs to a cleaner subset, called Natlab, which has a grammar that can be expressed cleanly for a LALR parser. The McLab front-end delivers a high-level AST based on this cleaner grammar.

After parsing, the next major phase of MiX10 uses the McSaf frameworkx[DH12a,xDoh11] to disambiguate identifiers using kind analysisx[DHR11], which determines if an identifier refers to a variable or a named function. This is required because the syntax of Matlab does not distinguish between variables and functions. For example, the expression a(i) could refer to four different computations, a could be an array or a function, and i could refer to the builtin function for the imaginary value i, or it could refer to a variable i. The McSaf framework also simplifies the AST, producing a lower-level AST which is more amenable to subsequent analysis.

The next major phase is the Tamerx[DH12b], which is a key component for any tool which statically compiles Matlab. The Tamer generates an even more defined AST called Tamer IR, as well as performing key interprocedural analyses to determine both the call graph and an estimate of the base type and shape of each variable, at each program point. The call graph is needed to determine which files (functions) need to be compiled, and the type and shape information is very important for generating reasonable code when the target language is statically typed, as is the case for X10.

The Tamer also provides an extensible interprocedural value analysis and an interprocedural analysis framework that extends the intraprocedural framework provided by McSaf. Any static backend will use the standard results of the Tamer, but is also likely to implement some target-language-specific analyses which estimate properties useful for generating code in a specific target language. Currently, we have implemented two analyses : (1) An analysis for determining if a Matlab variable is real or complex to enable support for complex numbers in MiX10 and other Matlab compilers based on McLab; and (2) IntegerOkay analysis to identify which variables can be safely declared to be of an integer type (Int or Long) instead of the default type Double.

For the purposes of MiX10, the output of the Tamer is a low-level, well-structured AST, which along with key analysis information about the call graph, the types and shapes of variables, and X10-specific information. These Tamer outputs are provided to the code generator, which generates X10 code, and which is the main focus of this thesis.

The X10 source code generator actually gets inputs from two places. It uses the Tamer IR it receives from the the Tamer to drive the code generation, but for expressions referring to built-in Matlab functions it interacts with the Built-in Handler which used the built-in template file we provide. We describe the functioning of the built-in handler in Chapter 5.

Chapter 4 concentrates on generating efficient code for Matlab arrays. Chapter 6 describes the code generation strategy for the sequential core of Matlab, while Chapter 7 describes our strategy to generate parallel X10 code for Matlab parfor construct, and introducing X10 like concurrency constructs in Matlab. The focus of this thesis is to address challenges in generating efficient X10 code whose performance is comparable to state-of-the-art tools that generate more traditional imperative languages like C and Fortran.

3.2 High-level Design of the MiX10 Compiler

The MiX10 code generator is the key component which makes the translation from the Tamer IR, which is based on Matlab programming constructs and semantics, to X10. The overall structure of the MiX10 code generator is given in Figure 3.2.

PIC Figurex3.2: Structure of the MiX10 code generator

The input to to MiX10 compiler is the call graph generated by Tamer and the Tame IR annotated with the necessary analysis information like shape, iscomplex, and type and IntegerOkay. Rather than do a direct code generation to X10 source code, MiX10 translates the Tamer IR to MiX10 IR, a general and extensible IR, designed by us, to represent X10. This translation is done by the X10 IR generator module of MiX10. Finally, with the inputs from the builtin handler and the X10 IR generator (after the X10 specific analyses and transformations have been done), the X10 source code generator generates the resultatnt X10 source code.

3.2.1 The MiX10 Intermediate Representation

The MiX10 IR is a low-level, three address like intermediate representation that is similar in design to the Tamer IR and abstracts the X10 constructs while capturing the static information required to generate the X10 source code. We have implemented the IR using JastAddx[EH04,xjas], which allows us to easily add new AST nodes by simply extending the JastAdd specification grammar.

There are three important reasons to use an IR, instead of directly generating the X10 code:

There are potentially two places that optimizations and transformations may happen: either at the Tamer IR level or at the MiX10 IR level. It is our intent to put any analysis or transformation that is not X10-specific into the Tamer IR, so that other back-ends can benefit from those improvements. However, optimizations and transformations that are specific to X10 programming constructs (such as points and regions) and semantics will need to be done on the MiX10 IR. Although we currently do not transform the MiX10 IR very much, the ultimate goal is to support a variety of analyses and transformations that can be used to: (1) produce more efficient X10 code, and (2) produce more readable X10 code.

There are X10 constructs that can be pretty printed to be of different kinds, for example the X10 arrays, which can either be simple arrays, region arrays or specialized region arrays, and X10 for loop which can either be C-like for loop or an iterator over a LongRange (used in generated code for parfor loop). It allows to abstract the vital information for a construct while leaving the actual syntax to the source code generator. This makes it easier to add X10 specific analyses and transformations, and makes it easy to update the compiler whenever a new or improved variation of a construct is added.

MiX10 IR can also be used as a convenient place to insert instrumentation code for the generated X10 code.

Appendix B provides the JastAdd implementation of the MiX10 IR grammar.

Techniques for Efficient Compilation of

Matlab Arrays

Arrays are the core of the Matlab programming language. Every value in Matlab is a Matrix and has an associated array shape. Even scalar values are represented as 1 × 1 arrays. Most of the data read and write operations involve accessing individual or a set of array elements. Given the central role of arrays in Matlab, it is of utmost importance for our MiX10 compiler to find effective and efficient translations to X10 arrays.

Given the shape information provided by the shape analysis enginex[LH14] built into the McLab analysis frameworkx[DH12a,xDoh11,xDH12b], it was not hard to compile Matlab arrays to X10. However, to generate X10 code whose performance would be competitive to the generated C code (via Matlab coder) and the generated Fortran code (via the Mc2For compiler), was not straightforward, and required deeper understanding of the X10 array system and careful handling of several features of the Matlab arrays.

4.1 Simple Arrays or Region Arrays

As described in Section 2.1.3, X10 provides two higher level abstractions for arrays, simple arrays, a high performance but rigid abstraction, and region arrays, a flexible abstraction but not as efficient as the simple arrays. In order to achieve more efficiency, our strategy is to use the simple arrays whenever possible, and to fall back to the region arrays when necessary. Note that it is possible to force the MiX10 compiler to use region arrays via a switch, for experimentation purposes.

4.1.1 Compilation to Simple Arrays

In dealing with the simple rail-backed arrays, there were two important challenges. First, we needed to determine when it is safe to use the simple rail-backed arrays, and second, we needed an implementation of simple rail-backed arrays that handles the column-major, 1-indexing, and linearization operations required by Matlab. When to use simple rail-backed arrays:

After the shape analysis of the source Matlab program, if shapes of all the arrays in the program: (1) are known statically, (2) are supported by the X10 implementation of simple arrays and (3) the dimensionality of the shapes remain same at all points in the program; then MiX10 generates X10 code that uses simple arrays. Column-major indexing:

In order to make X10 simple arrays more compatible with Matlab, we modified the implementation of the Array_2 and Array_3 classes in x10.array package to use column-major ordering instead of the default row-major ordering when linearizing multidimensional arrays to the backing Rail

storage.1 1http://www.sable.mcgill.ca/mclab/mix10/x10_update/

Since Matlab uses column-major ordering to linearize arrays, this modification also makes it trivial to support linear indexing operations in Matlab.

2 2http://www.mathworks.com/help/matlab/math/matrix-indexing.html

Matlab naturally supports linear indexing for individual element access. More precisely, if the number of subscripts in an array access is less than the number of dimensions of the array, the last subscript is linearly indexed over the remaining number of dimensions in a column-major fashion. Our modification to use column-major ordering for the backing Rail make it easier and more efficient to support linear indexing by allowing direct access to the underlying Rail at the calculated linear offset.

Given that we can determine when it is safe to use the simple rail-backed arrays, and our improved X10 implementation of them, we then designed the appropriate translations from Matlab to X10, for array construction, array accesses for both individual elements and ranges. Given the number of dimensions and the size of each dimension, it is easy to construct a simple array. For example a two-dimensional array A of type T and shape m × n can be constructed using a statement like val A:Array_2[T] = new Array_2[T](m,n);. Additional arguments can be passed to the constructor to initialize the array. Another important thing to note is that Matlab allows the use of keyword end or an expression involving end (like end-1) as a subscript. end denotes the highest index in that dimension. If the highest index is not known the numElems_i property of the simple arrays is used to get the number of elements in the ith dimension of the array.

4.1.2 Compilation to Region Arrays

With Matlab’s dynamic nature and unconventional semantics, it is not always possible to statically determine the shape of an arrays accurately. Luckily, with some thought to a proper translation, X10’s region arrays are flexible enough to support Matlab’s “wild" arrays. Also, since Point objects can be a set of arbitrary integers, there is no restriction on the starting index of the arrays. Region arrays can easily use one-based indexing. Array construction:

Array construction for region arrays involves creating a region over a set of points (or index objects) and assigning it to an array. Regions of arbitrary ranks can be created dynamically. For example, consider the following Matlab code snippet:

   function [x]x=xfoo(a)xxxxxtx=xbar(a);xxxxxxx=xt;xxxxx...xend

x

function [y]x=xbar(a)xxxxxifx(ax==x3)xxxxxxxxxyx=xzeros (a,a+1,a+2,a+3);xxxxxelse xxxxxxxxxyx=xzeros (a,a+1,a+2);xxxxxendxend

In this code, the number of dimensions of array t and hence array x cannot be determined statically at compile-time. In such case, it is not possible to generate X10 code that uses simple arrays, however, it can still be compiled to the following X10 code for function

foo().
   static xdefxfoo(a:xDouble ){xxxvalxt:xArray [Double ]x=xxxxxnewxArray [Double ](bar(a));xxxvalxx:xArray [Double ]x=xxxxxnewxArray [Double ](t);xxx...xxxreturn xx;x}

                            static xdefxbar(a:Double ){xxxvarxy:Array [Double ]=null ;xxxifx(ax==x3)x{xxxxxyx=xnewxArray [Double ]xxxxxxx(Mix10 .zeros (a,a+1,a+2,a+3));xxx}xxxelse x{xxxxxyx=xnewxArray [Double ]xxxxxxx(Mix10 .zeros (a,a+1,a+2));xxx}xxxreturn xy;x}

In this generated X10 code, t is an array of type Double which can be created by copying from another array returned by bar(a) without knowing the shape of the returned array. Array access:

Subscripting operations to access individual elements are mapped to X10’s region array subscripting operation. If the rank of array is 4 or less, it is subscripted directly by integers corresponding to subscripts in Matlab otherwise we create a Point object from these integer values and use it to subscript the array. In case an expression involving end is used for indexing and the complete shape information is not available, method max(Longxi), provided by the Region class is used, allowing to determine the highest index for a particular dimension at runtime. Rank specialization:

Although region arrays can be used with minimal compile-time information, providing additional static information can improve performance of the resultant code by eliminating run-time checks involving provided information. One of the key specializations that we introduced with use of region arrays is to specify the rank of an array in its declaration, whenever it is known statically. For example if rank of an array A of type T is known to be two, it can be declared as valxA:Array[T](2);. This specialization provided better performance compared to unspecialized code as shown in sectionx9.6.

4.2 Handling the Colon Expression

Matlab allows the use of an expression such as a:b (or colon(a,b)) to create a vector of integers [a,xa+1,xa+2,x...xb]. In another form, an expression like a:i:b can be used to specify an integer interval of size i between the elements of the resulting vector. Use of a colon expression for array subscripting takes all the elements of the array for which the subscript in a particular dimension is in the vector created by the colon expression in that

dimension.3 3Use of ’:’ in place of an index without lower and upper bounds indicates the use of all the indices in that dimension. Consider the following Matlab code:

function x[x]x=xcrazyArray (a)xxxxxyx=xones (3,4,5) ;xxxxxxx=xy(1,2:3,:) ;xend

Here y is a three-dimensional array of shape 3×4×5 and x is a sub-array of y of shape 1×2×5. Such array accesses can be handled by simply calling the getSubArray[T]() that we have implemented in a Helper class provided with the generated code. The generated X10 code with simple array for this example is as follows:

static xdefxcrazyArray x(a:xDouble ){xxxxxvalxy:xArray_3 [Double ]x=xnewxArray_3 [Double ](Mix10 .ones (3,x4,x5));xxxxxvalxmc_t0 :xArray_1 [Double ]x=xnewxArray_1 [Double ](Mix10 .colon (2,x3));xxxxxvarxx:xArray_3 [Double ];xxxxxxx=xnewxArray_3 [Double ](Helper .getSubArray  (1,x1,xmc_t0 (0),xmc_t0 (1),x1,x5,xy))x;xxxxxreturn xx;x}

The colon operator can also be used on the left hand side for an array set operation that updates multiple values of the array. For example, in the Matlab statement x(:,4) = y;, all the values of the fourth column of x will be set to y if y is a scalar or to corresponding values of y if y is a column vector with length equal to the size of first dimension of x. To handle this kind of operation we have implemented another helper method, setSubArray(). This method takes as input, the target array, the bounds on each dimension, and the source array. x(:,4) = y; will be

translated by MiX10 to x = Helper.setSubArray(x, 1, x.numElems_1, 4, 4,
y);

We have implemented overloaded versions of the getSubArray() and the setSubArray() methods for arrays of different dimensions. For region arrays, we provide the same methods that operate on region arrays in a different version of the Helper class. MiX10 provides the correct version of the Helper class, based on what kind of arrays are used.

4.3 Array Growth

Matlab allows explicit array growth during runtime via the horzcat() and the vertcat() builtin functions for array concatenation operations. In MiX10 this feature is supported for simple arrays as long as the array growth does not change the number of dimensions of the array. For region arrays, this feature is supported in full. For simple arrays, X10 allows a variable declared to be an array of rank i, to hold any array value of the same rank. For example, consider the following set of statements:

//...xvarxx:Array_2 [Long ];xxx=xnewxArray_2 (3,4,0) ;xyx=xnewxArray_2 (3,5,0) ;xx=y;x//...

Here, x is defined to be of type Array_2[Long] and can hold arrays of different sizes at different points in the program.

Region arrays, being more dynamic, also support array growth even if it changes the rank of the array. For example, the following set of statements are valid in an X10 program that uses region arrays:

//...xvarxx:Array [Long ];xxx=xnewxArray (Region .make (1..3,1..4)  ,0);xyx=xnewxArray (Region .make (1..3,1..5,1..6)  ,1);xx=y;x//...

Here x is a 2-dimensional array and y is a 3-dimensional array.

Section 9.6 discusses the performance results obtained by using different kinds of arrays and provides a comparison of them, thus showing the efficiency of our approach for compiling Matlab arrays to X10.

Handling Matlab Builtins

Matlab builtin methods are the core of the language and one of the features that make it popular among scientists. They provide a huge set of commonly used numerical functions. All the operators, including the standard binary operators (+,x-,x*,/), comparison operators (<,x>,x<=,x>=,x==) and logical operators (&,x&&,x|,x||) are merely syntactic sugar for corresponding builtin methods that take the operands as arguments. For example an expression like a+b is actually implemented as plus(a,b). An important thing to note is that unlike most programming languages, all the Matlab builtin methods by default operate on matrix values as a whole. For example a*b or mtimes(a,b) actually performs matrix multiplication on matrix values a and b. However, most of the builtin methods also accept one or more scalar, or more accurately, 1 × 1 matrix arguments. Builtin methods are overloaded to accept almost all possible shapes of arguments. Thus mtimes(a,b) can have both a and b as matrix arguments (including 1 × 1 matrices) with number of columns in a equal to number of rows in b, in which case the result is a matrix multiplication of a and b or one of them can be a 1 × 1 matrix and other can be a matrix of any size and the result is a matrix containing each element of the non-scalar argument times the scalar argument. Wherever possible, Matlab builtins also support complex numerical values. X10 on the other hand, like most of the programming languages operates on scalar values by default.

Due to the fact that X10 is still new and evolving, it has a very limited set of libraries, specially to support a large subset of available Matlab builtin methods. The X10 Global Matrix Library (GML) supports double-precision matrix operations however it is still not as extensive as Matlab’s set of operations and it poses some restrictions:

It works on values of type Matrix instead of X10 type Array which means it needs explicit conversion of Array values to Matrix values before performing a matrix operation and and then a conversion of the results back to Array type. This conversion may be a large overhead, especially for small data sizes.

GML is limited to Matrix values of two dimensions and containing elements of type Double, whereas many Matlab builtin methods support values of greater number of dimensions.

GML currently does not support complex numerical values whereas Matlab naturally supports them.

Currently GML requires a separate installation and configuration which is non-trivial specially for scientists who need something that works out of the box.

Due to above restrictions, X10 Global Matrix Library is useful in some situations, for example when there is a matrix multiplication of a very large data size, but cannot be used or is not a good choice for a large number of operations.

For a language with open-sourced libraries, it would be possible to actually compile the library methods to X10. However, many Matlab libraries are closed source and thus it is not possible to translate them to X10.

5.0.1 The MiX10 Builtin Support Framework

We decided to write our own X10 implementations of the commonly used Matlab builtin methods. Currently we have implemented only those methods that are used in our benchmarks. In this thesis, we concentrate on how these methods are included in the generated X10 code with minimal loss of readability and performance rather than the actual implementation.

The code below shows the X10 code for the Matlab builtin method plus(a,b) involving 2-dimensional simple arrays.

public xstatic xdefxxxplus (a:xArray_2 [Double ],xb:Array_2 [Double ]){xxxxx xxxx valxxx=xnewxArray_2 [Double ](a.numElems_1 ,xa.numElems_2 );xxxxx xxxx forx(pxinxa.indices ()){xxxxx xxxx xxxx x(p)x=xa(p)+xb(p);xxxxx xxxx }xxxxxreturn xx;x}xxpublic xstatic xdefxplus (a:Double ,xb:Array_2 [Double ]){xxxxx valxxx=xnewxArray_2 [Double ](b.numElems_1 ,xb.numElems_2 );xxxxx forx(pxinxb.indices ()){xxxxx xxxx x(p)x=xa+xb(p);xxxxx }xxxxx return xx;x}xxpublic xstatic xdefxplus (a:Array_2 [Double ],xb:Double ){xxxxx valxxx=xnewxArray_2 [Double ](a.numElems_1 ,xa.numElems_2 );xxxxx forx(pxinxa.indices ()){xxxxx xxxx x(p)x=xa(p)+xb;xxxxx }xxxxx return xx;x}xxpublic xstatic xdefxplus (a:Double ,xb:Double ){xxxxx valxx:xDouble ;xxxxx xx=xa+b;xxxxx return xx;x}

This X10 code contains four overloaded versions (and it still does not contain methods to support complex values, variables of types other than Double, simple arrays of other dimensions, and region arrays) based on whether the arguments are scalar or Array_2 and their relative position in the list of arguments.

Including all the overloaded versions and versions specialized for arrays of different dimensions or region arrays, in the generated X10 code would result in lot of lookup overhead, would require producing redundant code (versions of methods with arguments of similar shape but different types will have the same algorithm) and would generate large code with less readability. Instead we designed a specialization technique that selects the appropriate versions of only the methods used in the source Matlab program. Note that the use of generic types to handle arguments of different types is not always a good idea, since several builtin implementations involve calls to X10 library functions which are not defined on generic types. For example, functions in the x10.lang.Math librarry like

floor(Double a), max(Double a, Double b), etc. do not take generic type

arguments.

After studying numerous builtin methods we categorized them into the following five categories:

Type 1: All the parameters are scalar values or no parameters.

Type 2: All the parameters are arrays.

Type 3: First parameter is scalar, rest of the parameters are arrays.

Type 4: Last parameter is scalar, rest of the parameters are arrays.

Type 5: Any other type(Default).

Each of these categories, except Type 5, uses similar code template for different types of values. Note that due to the three address code-like structure of Tame IR, any call to a builtin almost always contains zero, one or two arguments. For builtin calls like horzcat and vertcat which may contain variable number of arguments, MiX10 packs all the arguments in a Rail and passes a single argument of type Rail. Accordingly, these builtins are implemented in Type 2 category and receive a single argument of type

Rail.

We build an XML file that contains the method bodies for each category for every builtin method (that we support). The XML also contains specialized implementations of every builtin for different kinds of arrays. We implement the following strategy to select and generate the correct and required methods. First, we make a pass through the AST to make a list of all the builtin methods used in the source Matlab program. Next, we parse the XML file once and read in the X10 code templates for all the categories of the builtin methods collected in the first step. Next, whenever a call to a builtin method is made, based on the results of the value analysis we: (1) Identify the required specialization for the method (simple array or region array); and (2) generate the correct method header and select the corresponding builtin template in the required specialization for that method. The generated methods are finally written to a X10 class file named Mix10.x10. In the code generated for actual Matlab program, the call to a builtin method is simply replaced by a call to the corresponding method in the Mix10 class. For example, Matlab expression plus(a,b) is translated to X10 expression Mix10.plus(a,b). Appendix A demonstrates the structure of the builtin XML with an example implementation of the builtin

plus.

Using the above approach not only improves the readability of the generated code, but it also allows for future extensibility, better maintenance and more specialization. Specializations that we plan to add in future are: (1) the ability to use the Global Matrix Library for the available methods in it and whenever the data size is large enough; and (2) concurrent versions of the relevant builtins to support the execution of vector instructions in parallel fashion, as described in section 7.3. We also encourage advanced users to mdoify the generated Mix10.x10 file to enhance or add builtin implementations for higher performance of the generated code.

Code Generation for the Sequential Core

Matlab is a programming language designed specifically for numerical computations. Every value is a Matrix and has an associated array shape. Even scalar values are 1×1 matrices. Vectors are 1 × n or n × 1 matrices. All the values are by default of type double. Matlab naturally supports imaginary components for all numerical values and almost all operators and library functions support complex inputs. In the rest of this chapter we describe some of the key features of Matlab that demonstrate what makes Matlab different and challenging to compile statically and techniques used by MiX10 to translate these “wild" features to X10. We provide necessary details on the various Matlab constructs as we discuss them, however for the readers who are totally unfamiliar with Matlab, we suggest reading chapter 2 of the M.Sc. thesis on the Tamer frameworkx[Dub12].

6.1 Methods

A function definition in Matlab takes one or more input arguments and returns one or more values. A typical Matlab function looks as follows:

function [x,y]x=xfoo(a,b)xxxxxxx=xa+3;xxxxxyx=xb-3;xend

This function has two input arguments a and b that can be of any type and any shape and returns two values x and y of the same shape as a and b respectively and of types determined by Matlab’s type conversion rules. The Tamer IR provides a list of input arguments and a list of return values for a function. The interprocedural value analysis identifies the types, shapes and whether they are complex numerical values for all the arguments and the return values.

Matlab functions are mapped to X10 methods. If it is the entry function, the type of the input argument is specified by the user (Tame IR requires to have an entry function or a driver function with one argument. This function may call other functions with any number of input arguments). For other functions the parameter types are computed by the value analysis performed by the Tamer on the Tame IR. The type information computed includes the type of the value, its shape and whether it is a complex value. Other statements in the function block are processed recursively and corresponding nodes are created in the X10 IR. Finally, if there are any return values, as determined by the Tame IR, a return statement is inserted in the X10 IR at the end of the method. If the function returns only one value, say x then the inserted statement is simply returnxx; but if the function returns more than one values (which is quite common in Matlab) then we return a Rail of type Any whose elements are the values that are returned. So, for the above example the return statement is returnx[xxasxAny,xyxasxAny];. Note that the use of short syntactic form for Rail construction improves the readability of the generated code. Below is the generated code for the simple example above.

static xdefxfoo(a:xDouble ,xb:xDouble ){xxxxxvarxmc_t0 :xDouble x=x3.3; xxxxxvarxx:xDouble x=xMix10 .plus (a,xmc_t0 );xxxxxvarxmc_t1 :xDouble x=x3.2; xxxxxvarxy:xDouble x=xMix10 .minus (b,xmc_t1 );xxxxxreturn x[xxasxAny,xyxasxAny];x}

Also note that the variables mc_t0 and mc_t1 are introduced by Tamer in the Tame IR.

6.2 Types, Assignments and Declarations

Matlab provides following basic types:

double,xsingle: floating point values

     uint8,xuint16,xuint32,xuint64: unsigned integer values

     int8,xint16,xin32,xint64: integer values

logical: boolean values

char: character values (strings are vectors of char)

These basic types are naturally mapped to X10 base types as follows. Floating point values are mapped to Double and Float respectively, unsigned integers are mapped to

UByte,xUShort,xUInt and ULong, integer values are mapped to Byte,xShort,xInt

and Long, logical is mapped to Boolean and char is mapped to Char (vector of chars is mapped to String type). If the shape of an identifier of type T is greater than 1 × 1 it is mapped to Array[T]. The type conversion rules are quite different from standard languages. For example, an operation involving a double and an int32 results in a value of type int32.1 1The type rules are explained in detail in the Tamer documents, www.sable.mcgill.ca/mclab/tamer.html. MiX10 inserts an explicit typecast wherever required.

All the Matlab operators are designed to work on matrix values and are provided as syntactic sugar to the corresponding builtin methods that take operands as arguments. Operators are overloaded to support different semantics for 1×1 matrices (scalar values). Matlab provides two types of operators - matrix operators and array operators. Matrix operators work on whole matrix values. These include matrix multiplication (*) and matrix division (\, /). Array operators always operate in an element-wise manner. For example array multiply operator .* performs element-wise multiplication. As described in Chapter 5, MiX10 implements all operators as builtins.

Matlab is a dynamically typed language which means that variables need not be declared and take up any value that they are assigned to. X10 however, is statically typed and requires variables to be declared before being assigned to. MiX10 maintains a list of all the declared variables. It starts with an empty list. Whenever an identifier appears in an assignment statement on LHS, if it is not already present in the list, a declaration statement is added to the X10 IR and the variable (with its associated type and value information) is added to the list, followed by an assignment statement corresponding to the statement in Matlab. If the identifier is already present in the list, the assignment statement is added to the X10 IR and the associated type and value information is updated. In case the Matlab assignment statement is inside a loop and needs a declaration, the declaration statement (without any assignment) is added to the method block outside any loop or conditional scope and the assignment statement is added in the scope where it is present in Matlab code. If the identifier on LHS is an array, then the declaration creates a new array with the shape corresponding to the shape of the RHS array. For example a Matlab statement like a=b; where shape of a is, say, 3 × 3 and type is double will be translated to

a:Array_2[Double]=newxArray_2[Double](b); for simple arrays and
a:Array[Double]=newxArray[Double](b); for region arrays (outside the scope of

any loops or conditionals).

6.3 Loops

Loops in Matlab are fairly intuitive except for one semantic difference from most of the languages. In a for loop if the loop index variable is redefined inside the body of the loop, then its new value is persistent only in a particular iteration and does not affect the number of loop iterations. For example, consider the following listing.

function x[x]x=xxforTest1 (a)xxxxxforxix=x(1:10) xxxxxxxxxi=3;xxxxxxxxxa=a+i;xxxxxendxxxxxx=a;xend

Note that inside every iteration, the value of loop index variable i is 3 but the loop still terminates after ten iterations. The above code would be translated to the following X10 code:

static xdefxforTest1 x(a:xDouble )x{xxx//Note xthat xinxthexactual xgenerated xcode xxx//thexname xofxthextemporary xvariable xintroduced xbyxMiX10 xxx//isxmangled xtoxensure xthat xthere xisxnoxxx//conflict xwith xanyxother xvariable xname .xxxxvarxmc_t0 :xLong x=x1;xxxvarxmc_t1 :xLong x=x10;xxxvarxi_x10 :xLong ;xxxvarxb:xDouble ;xxxvarxi:xLong ;xxxforx(i_x10 x=xmc_t0 ;x(i_x10 x<=xmc_t1 );xi_x10 x=x(i_x10 x+x1))xxxxxxx{xxxxxxxxxxxxix=xi_x10 ;xxxxxxxxxxxxix=x3x;xxxxxxxxxxxxbx=xMix10 .plus (a,xi)x;xxxxxxx}xxxvarxx:xDouble x=xa;xxxreturn xx;x}

To handle this somewhat different semantics we introduce a new loop index variable and assign it to the original loop index variable at the beginning of the loop body. The rest of the loop body is translated by standard rules. Note that the new loop index variable is introduced only if the actual loop index variable is redefined inside the loop body.

6.4 Conditionals

In Matlab conditionals are expressed using the if-elseif-else construct and do not have any wild semantics. Matlab also allows switch statements which are converted to equivalent if-else statements by the Tamer. It also recursively converts a statement like if (B1) S1 elseif

(B2) S2 else S3 to a series of if-else clauses like if (B1) S1 else{ if(B2)

S2 else S3}. This if-else construct is intuitively mapped to the if-else construct in X10.

6.5 Function Calls

Function calls in Matlab are similar to other programming languages if the called function returns nothing or returns only one value. However, Matlab allows a function to return multiple values. Whenever a call is made to such a function, returned values are received in a list in the order specified by function definition. For example in the statement [x,n]x=xbubble(a); a call is made to the function bubble which returns two values that are read into x and n respectively. This statement is compiled to following code in X10.

xxx//Note xthat xinxthexactual xgenerated xcode xxx//thexname xofxthextemporary xvariable xintroduced xbyxMiX10 xxx//isxmangled xtoxensure xthat xthere xisxnoxxx//conflict xwith xanyxother xvariable xname .xxxxxvarxx:xDouble ;xxxxvarxn:xDouble ;xxxxvalx_x_n :xRail [Any];xxxx_x_n x=xbubble (A)x;xxxxxx=x_x_n (0)xasxDouble x;xxxxnx=x_x_n (1)xasxDouble x;

The key idea here is to create a Rail of type Any and read the returned value. Remember that MiX10 packs the multiple return values of a method in a Rail of type Any and returns it. Individual elements of the list simply read the values from this array. If the function call is inside a loop, all the declarations are moved out of the loop and only assignments are inside the loop.

6.6 Cell Arrays

Cell arrays in Matlab are arrays of data containers called cells and each cell can contain data of

any type. For example fooCell = {'x',10,'I like',ones(3,3)}; creates a cell

array containing values of type char, double, char array and a double array. To convert to X10, the elements of the cell array are packed into a rail of type Any. While accessing an element it is type cast into its original type. Consider the following Matlab listing:

function x[x]x=xxcellTest (a)xxxmx=xones (2,3) ;xxxnx=x[4,5]; xxxmyCell x=x{m,xn*100}; xxxxx=xmyCell {1,2}; xend

It creates a cell array containing two arrays. It is translated to the below X10 code:

static xdefxcellTest x(a:xDouble )xxxxx {xxxxx//Note xthat xforxthexpurpose xofxdemonstration  ,xxxxx//this xexample xuses xregion xarrays xandxxxxx//does xnotxusexIntegerOkay  xanalysis .xxxxxxvarxmc_t2 :xDouble x=x2;xxxxx xxxx varxmc_t3 :xDouble x=x3;xxxxx xxxx varxm:xArray [Double ]x=xnewxArray [Double ](Mix10 .ones (mc_t2 ,xmc_t3 ));xxxxx xxxx varxmc_t5 :xDouble x=x4;xxxxx xxxx varxmc_t6 :xDouble x=x5;xxxxx xxxx varxn:xArray [Double ]x=xnewxArray [Double ](Mix10 .horzcat (mc_t5 ,xmc_t6 ));xxxxx xxxx varxmc_t0 :xArray [Double ]x=xnewxArray [Double ](m);xxxxx xxxx varxmc_t7 :xDouble x=x100; xxxxx xxxx varxmc_t1 :xArray [Double ]x=xnewxArray [Double ](Mix10 .mtimes (n,xmc_t7 ));xxxxx xxxx varxmyCell :xRail [Any]x=x[mc_t0 xasxAnyx,mc_t1 xasxAny];xxxxx xxxx varxmc_t9 :xDouble x=x1;xxxxx xxxx varxmc_t10 :xDouble x=x2;xxxxx xxxx varxx:xArray [Double ];xxxxx xxxx xx=xmyCell (mc_t9 xasxLong x-1,xmc_t10 xasxLong x-1)xasxArray [Double ];xxxxx xxxx return xx;xxxxx }

Code Generation for Concurrency in Matlab

Matlab programmers often recognize the parallel nature of computations involved in their programs but cannot express it due to the lack of fine-grained concurrency controls in Matlab. Some concurrency can be achieved using controls like parfor and other tools in Mathwork’s parallel computing toolbox, but this has several drawbacks: (1) the parallel toolbox is limited in terms of scaling (Matlab currently supports only up to 12 workers processes to execute applications on a multicore processorx[Mat13]); (2) the parallel toolbox must be purchased separately, so not even all licensed Matlab users will have it available; and (3) Matlab’s concurrency is often slower compared to X10’s concurrency controls (as shown in sectionx9.8). Vectorization

1 1http://www.mathworks.com/help/matlab/matlab_prog/vectorization.html  is

a technique to convert loop-based scalar operations to vector operations, for which Matlab is optimized. So, another way of exposing parallelism in Matlab is to optimize these instructions to perform the computations concurrently on the elements of the vector.

Sec.x2.2 gives an introduction to the concurrency controls in X10. Readers not familiar with X10 may find it useful to read it before continuing with this chapter.

7.1 Code Generation for the Matlab parfor Loop Construct

The Matlab parfor construct is an important feature in Matlab and is provided by the Mathworks’ parallel computing toolboxx[Mat13]. It allows the for loop iterations in the Matlab programs to be executed in parallel, whenever safely possible, thus greatly enhancing the performance of the for loop execution. Other static Matlab compilers like Matlab coder and Mc2For do not support the parfor loop due to the lack of builtin concurrency features in their target languages, C and Fortran. However, X10, being a parallel programming language, naturally provides concurrency control features. The MiX10 compiler supports parallel code generation for the Matlab parfor construct and provides significantly better performance compared to Matlab code with parfor, and also the sequential version of the X10 code generated for the same program.

The parfor (or parallel for loop) is a key parallelization control provided by the Matlab parallel computing toolbox that can be used to execute each iteration of the for loop in parallel with each other. The challenge was to implement it with X10’s concurrency controls while maintaining its complex semantics and aiming for better performance than provided by the parallel computing toolbox. There are three important semantic characteristics of Matlab’s

parfor loop:

the scope of variables inside a parfor loop, including the loop index variable, is limited to each iteration.

if a variable defined outside the loop is modified inside the loop such that its value after the loop is dependent on the sequence of execution of iterations, then its value after the loop is set to its value before the loop.

if a variable defined outside the loop is modified in a reduction assignment i.e., the final value after the iterations is independent of the order of execution of iterations, the updated value is retained after the parfor loop. Consider the Matlab code given on the left of Figure 7.1.

 function x[]x=xsaneParfor (v)xdx=xv;xx=0;xA=zeros (1,10) ;xparfor xix=x1:10 xxxxxx=xx+i;xxxxdx=xi*2;xxxxA(i)x=xd;xendxdisp (d);xend

              static xdefxsaneParfor x(v:xDouble ){xxx//This xexample xdoes xnotxxx//usexIntegerOkay  xanalysis xxxvarxd:xDouble x=xv;xxxvarxx:xDouble x=x0;xxxvalxA:xArray_1 [Double ]x=xxxxxxnewxArray_1 [Double ](Mix10 .zeros (1,x10));xxxvarxmc_t3 :xDouble x=x1;xxxvarxmc_t4 :xDouble x=x10;xxxfinish x{xxxxxforx(ixinx(mc_t3 xasxLong )..(mc_t4 xasxLong ))xxxxxxasync x{xxxxxxxxatomic xxx=xMix10 .plus (x,xixasxDouble );xxxxxxxxvarxmc_t2 :xDouble x=x2;xxxxxxxxvarxd_local :xDouble x=xxxxxxxxxxxMix10 .mtimes (ixasxDouble ,xmc_t2 );xxxxxxxxA(ixasxLong x-1)x=xd_local x;xxxxx}xxx}x}

Figurex7.1: Example of parfor, Matlab with parfor on the left, generated X10 on the right.

Here xx=xx+i; is a reduction assignmentx[Matb] statement. The value of d is local to each iteration and the initial value before the loop is retained after the loop. Note that the value of d outside the loop is invisible inside the loop. For statement A(i)x=xd;, each iteration modifies a unique element accessible only to it, hence the final value of A is independent of order of execution; thus its value is updated after the loop.

The MiX10 compiler uses the following strategy to translate parfor loops to X10:

Introduce finish and async constructs to control the flow of statements in parallel. This puts the statement immediately after the for loop in wait, until all the iterations have been executed.

Any variable defined inside the loop and not declared outside the loop previously is declared inside the async scope to make it local to the iteration.

Any variable defined inside the loop that is previously defined outside the loop and is not a reduction variable is replaced by a local temporary variable defined inside the loop.

Statements identified to be reduction statements are made atomic by using the atomic construct in X10.

An equivalent X10 code for the above example Matlab code is given on the right side of Figure 7.1. The use of finish and async ensure that each iteration is executed in parallel and the statement after the for loop is blocked until all the iterations have finished executing. Note that the for loop is iterated over a LongRange to ensure that the declaration of the loop variable i is local to each iteration. The statement x = x+i is a reduction statement, since its order of execution does not affect the value of x at the end of the loop. It is declared to be atomic to ensure that the two operations of addition and assignment in the statement are executed as a whole, without any interference from its execution in other iterations. Since the variable d is also defined outside the loop, it is replaced by a local variable d_local inside the loop. Finally, since each array variable A(i) is unique, it is executed normally for each iteration.

To conclude, we can translate the parfor in Matlab to semantically equivalent code in X10 and since X10 can handle massive scaling, we can get significantly better performance for X10 compared to Matlab as shown by our experimental results in Section 9.8.

7.2 Introducing Concurrency Controls in Matlab

In order to enable Matlab to be compiled for high performance computing it is important to let programmers exploit fine-grained concurrency in their Matlab programs. Due to the lack of fine-grained concurrency controls in traditional Matlab, we decided to introduce such controls in Matlab that can be translated by our MiX10 compiler to analogous concurrency controls in X10. However it was important that introduction of such controls should not have any side-effects when compiled by traditional Mathworks’ Matlab compiler, so we introduced them as structured special comments.

We introduced the following concurrency constructs in Matlab: (1) %!async, (2)

%!finish, (3) %!atomic, (4) %!when(condition) (5) (where condition is a

boolean expression) and (6) %!at(p) (where p is an integer value denoting a place in X10). Programmers can express these constructs before the statements that they want to control and specify the end of a control by using %!end after the statements. Note that because of the preceding % sign these constructs will be treated like comments by other Matlab compilers and will not cause any unwanted effects. It is important to note that the Matlab programmer, using these constructs in her program, must ensure that the parallel execution caused by the use of these constructs does not change the behavior of the program from that of the sequential execution of the program. In short, it is the responsibility of the programmer to ensure the safety of the program when using these constructs.

Figure 7.2 shows an example of how to use these controls in Matlab followed by the generated X10 code for it.

function x[x]x=xparallelFoo  (a)xxx%!finish xxxforx(ix=x1:length (a))xxxxx%!async xxxxxa(i)=a(i)*2;xxxxx%!endxxxendxxx%!endxend
                 static xdefxparallelfoo  x(a:xArray_1 [Double ]){xxx//This xexample xdoes xnotxxx//usexthexIntegerOkay  xanalysis xxxvarxmc_t2 :xDouble x=xMix10 .length (a);xxxvarxmc_t4 :xDouble x=x1;xxxfinish x{xxxxxforx(ixinx(mc_t4 xasxLong )..(mc_t2 xasxLong )){xxxxxxxasync {xxxxxxxxxvarxmc_t0 :xDouble ;xxxxxxxxxmc_t0 x=xmtimes (a(ix-x1),x2)x;xxxxxxxxxa(ix-x1)x=xmc_t0 x;xxxxxxx}xxxxx}xxx}xxxvalxx:xArray_1 [Double ]x=xnewxArray_1 [Double ](a);xxxreturn xx;x}

Figurex7.2: Example of introduced concurrency controls, Matlab with introduced concurrency on the left, generated X10 on the right.

7.3 Parallelizing Vectorized Instructions

The use of vectorized instructions is another optimization technique used by Matlab to speedup single operations on multiple scalar values by combining scalar values in a vector and executing the operation on the vector. Such Single instruction, multiple data style operations are good candidates for parallelization. However, efficiency of parallelization of such operations depends on the size of the vector, the complexity of the operation involved, and the executing hardware. Thus, in order to make it most effective, we wanted to provide full support for parallelization of vector instructions and give the programmer the ability to control when the vector operation is executed concurrently, based on the size of the vector.

We implemented a concurrent version of the relevant builtin operations that can operate in a parallel fashion on vectors of arbitrary

sizes.2 2Currently, these concurrent builtin implementations are not integrated into the builtin handling framework. However, due to the extensible nature of the builtin handling framework, it should be straightforward to add a specialization for a concurrent version of the builtins. We plan to do it as a future work. We also introduced a compiler switch for MiX10 that lets programmers specify a vector length threshold for all builtins or a specific builtin above which the concurrent version of the builtin will be executed. For example, if the user wants an operation sin(A) to be executed concurrently only if A is a vector of length greater than, say, 1000; then while invoking the MiX10 compiler she can specify the threshold by using the switch -vec_par_lengthxsin=1000. MiX10 will generate a call to the concurrent version of sin() if the length of A is greater than 1000 else it will call the sequential version. Using the -vec_par_length switch programmer can specify threshold for one or more or all builtin methods. For example

-vec_par_lengthxall=500xsin=1000xcos=1000 will set the threshold for sin()

and cos() to 1000 and to 500 for all other builtins.

As a future work, we plan to extensively evaluate the concurrent execution for the vectorized instructions. It would be interesting to study the performance variations of concurrently executing vector instructions, with varying threshold vector length values and on different parallel architectures.

The IntegerOkay Analysis

In this chapter we present the IntegerOkay analysis to identify which variables in the source Matlab program can be safely declared to be of an integer type instead of the default double type. In Matlab all the variables holding a numerical value are by default of type Double, which means that by default, in the X10 code generated from Matlab, all variables are statically declared to be of Double. However, in languages like X10, Java and C++, certain program operations require the variables used to be of an integer type. A prominent example of such an operation is an array access operation. An array access requires the variables used to index into the array to be of an integer type. For example, in a statement like x = A(i,j), the variables i and j are required to be of integer type and result in an error otherwise.

8.1 Need for Declaring Variables to be of Integer Type

A simple solution to handle this problem in the generated code from Matlab is to explicitly cast the variable from Double to Long, whenever it is required to be used as an integer. However, our experiments showed this approach to be very inefficient. With this approach, we observed that the C++ programs generated by the X10 compiler’s C++ backend were slow, and often even slower than the Java code generated by the X10 Java backend for the same program (which was somewhat surprising). The reason for the added slowness in the C++ code was because each typecast from Double to Long involved an explicit check on the value of the Double type variable to ensure that it lies in the 64-bit range supported by Long, whereas the cast in Java is handled by a primitive bytecode cast instruction. However, even in Java, extraneous casts clearly hurt performance.

To solve this problem, we designed and implemented the IntegerOkay analysis that identifies variables that can be safely declared to be of Long type, thus eliminating the need for costly typecasting on these variables.

8.2 Effect on Performance

To understand the effect on performance caused by typecasting consider a simple example of X10 code shown in listing 8.1 that just loops over a 2-dimensional array and sets each element A(i,j) to A(i-1,j-1) + A(i+1, j+1). In this example, the index variables i and j are declared to be of type Double and are typecast to Long when used for indexing into the array. This example reflects the type of X10 code that we would generate if we do not have the IntegerOkay analysis.

Listing 8.2 shows the same example, but with i and j declared to be Long, and thus not requiring an explicit typecast. This example reflects the code that we would be able to generate with a good IntegerOkay analysis.

static xdefxuseDoubles (scale :Double ,xn:Long ){xxxvalxa:xArray_2 [Double ]x=xxxxxnewxArray_2 [Double ](Mix10 .rand (scale ,xscale ));xxxvarxi:Double x=x0;xvarxj:Double x=x0;xvarxv:Long x=x0;xxxforx(v=0;v<n;v++){xxxxxforx(j=1;j<a.numElems_2 -1;j++){xxxxxxxforx(i=1;i<a.numElems_1 -1;i++){xxxxxxxxxa(ixasxLong ,jxasxLong )x=xa(ixasxLong x-1,xjxasxLong x-1)x+xxxxxxxxxxa(ixasxLong x+1,xjxasxLong x+1);xxxxxxx}x}x}x}

Listingx8.1: Example for using

   Double

variables

for array indexing

static xdefxuseLongs (scale :Double ,xn:Long ){xxxvalxa:xArray_2 [Double ]x=xxxxxnewxArray_2 [Double ](Mix10 .rand (scale ,xscale ));xxxvarxi:Long x=x0;xvarxj:Long x=x0;xvarxv:Long x=x0;xxxforx(v=0;v<n;v++){xxxxxforx(j=1;j<a.numElems_2 -1;j++){xxxxxxxforx(i=1;i<a.numElems_1 -1;i++){xxxxxxxxxa(i,xj)x=xa(i-1,xj-1)x+xa(i+1,xj+1);xxxxxxx}x}x}x}

Listingx8.2: Example for using

   Long

variables

for indexing

11           11 input args: 100, 200000 11 input args : 10000, 20
11           11 Java 11  C++  11 Java 11  C++
11 useDoubles 11 6.9 11  33.7  11 7.6 11  35.2
11 useLongs 11 3.4 11  1.5  11 3.7 11  2.0

11

Tablex8.1: Running times (in seconds) for listings 8.1 and 8.2, smaller is better

Table 8.1 shows running times (in seconds) for these two examples for different values of input arguments. For the listing 8.1, the C++ code generated by the X10 compiler is nearly 5 times slower as compared to the Java code generated from X10 for the same example. Compared to 8.2 it is slower than the C++ code for this example by almost 20 times. On the other hand, Java code for the listing 8.1 is nearly 2 times slower compared to the Java code for the listing 8.2. For the C++ backend, since the C++ compiler does not provide the checks for Double to Long typecast, it is implemented in the X10 C++ backend. For the Java backend, X10 relies on these checks provided by the JVM. The more efficient implementation of these checks in the JVM, compared to that in the X10 C++ backend explains for comparatively lower slowdowns for the Java code. Section 9.7 gives detailed evaluation of the performance benefits obtained by using IntegerOkay analysis on our benchmark set.

8.3 An Overview of the IntegerOkay Analysis

In this section we give a high-level overview of how the IntegerOkay analysis works. A detailed algorithm for it is provided in the next section (section 8.4). The basic idea behind the IntegerOkay analysis is that, for each variable x, if for every use and every definition of x in the given Matlab function, x can be safely assumed to be an integer, i.e. its declaration as an integer does not change the result of the program, then it can be declared as an integer. Thus, the problem boils down to answering the question of whether each use or a definition, x can be safely assumed to be an integer.

There are three possible answers to this question:

IntegerOkay: The variable use/def can be safely assumed to be an integer. For example, for a definition like x = 2.0 or for use as an array index like A(x), it is safe to assume that if x was declared to be an integer, this definition or use will not affect the result of the program. In other words, for this definition or use of x, x is

IntegerOkay.

Not IntegerOkay: The variable cannot be an integer type. For example consider the expression x/y. Here, since the type of the operands can affect the result of the division operation, it is unsafe to assume that x and y can be of integer type for this particular use. As another example, consider the definition x = 3.14. Here, since assuming x to be an integer will result in an error, x is not IntegerOkay.

Conditionally IntegerOkay: It is possible to have a case where a variable x, for a particular use or def in the function, is an integer only if some other variable, say y, is IntegerOkay everywhere in the given function. In such a case, we say that x is conditionally IntegerOkay and depends on y. For example, in a definition like x = a+b, x can be an integer if both a and b can be integers everywhere in the function. We say x is conditionally IntegerOkay and depends on a and b. Note that these particular uses of a and b are IntegerOkay because the plus() builtin can be used with integers safely. However, some other statement may constrain the solution. For example, a definition of the form a = 3.2 somewhere in the function would mean that a is not IntegerOkay everywhere and thus x is not IntegerOkay.

In our MiX10 compiler we solve the IntegerOkay problem using a simple fixed-point computation. For each variable use and definition, the algorithm initially associates it with one of the three abstract values above. We then compute the fixed-point by iteratively refining the dependency lists of the conditional variables. Consider each variable x, if every use and definition of x has been determined to be IntegerOkay, then x is removed from the dependency lists of all the variables that are Conditionally IntegerOkay and depend on x. Once the dependency list for a particular use or definition of a variable is empty, it is upgraded to be IntegerOkay for that particular use or definition.

If a variable is not IntegerOkay at some point in the function or its dependency list does not become empty for some point in the function (say, for circular dependency), it cannot be declared as an integer. Since, every time we declare a variable to be integer, one or more Conditionally IntegerOkay variables might be upgraded to IntegerOkay, we iteratively repeat the process of finding variables that are IntegerOkay at all points in the function, until we reach a fixed point. Note that since we never downgrade a variable to Not IntegerOkay or Conditionally IntegerOkay, our iterative algorithm will always terminate.

8.4 The Analysis Algorithm

The IntegerOkay analysis is an intra-procedural, flow-insensitive and path-insensitive analysis. The basic idea behind identifying whether a variable can be declared as an integer is that if a variable can safely be an integer for its every definition and every use in the function, independent of any other variable’s type, then it can be declared to be an integer for the entire function. It is important that any variable identified as IntegerOkay must be safe to be declared as an integer, thus the analysis takes a conservative approach and identifies a variable as IntegerOkay only when it is completely unambiguous. This eliminates any false-positives (a variable is identified as IntegerOkay, when in fact it is not IntegerOkay) but may lead to some false-negatives (a variable is identified not IntegerOkay, when in fact it could be intgerOkay). For example, if a variable i is used as an array index variable and also used as an argument to the rdivide() builtin call somewhere in the function, the analysis identifies it as not IntegerOkay, even though under the assumption that the function would execute without any runtime errors, i would be IntegerOkay (use of a non-integral value as an array index results in a runtime error).

The input to the analysis is a set of all the double variables in the function, a set of definitions for each of the variables in this set, and a set of all the uses for each of the variables in this variable set. The aim is to output a set of variables that can be safely declared as integers.

8.4.1 STEP 1 : Initialization

As mentioned in Sec.x8.3, the analysis initializes each definition and each use of every variable to one of the three abstract values and assigns a set of dependency variables if the assigned abstract value is conditionally IntegerOkay.

The analysis represents these three abstract values by the following state values : IntOk, NotIntOk, and CondIntOk for is IntegerOkay, not IntegerOkay, and conditionally IntegerOkay respectively. Furthermore, let d.state be the state of variable v for definition d , and u.state be the state of variable v for use u. Also, let d.deps be a set of variables on which the CondIntOk state for variable v for definition d depends on. Similarly, let u.deps be a set of variables on which the CondIntOk state for variable v for use u depends on. The analysis starts with a set of all the double variables V in the Matlab function, where each variable v has an associated set of its definitions D and uses U. Every d.state and u.state is initialized to NotIntOk and every d.deps and u.deps is initially set to ∅. Algorithm 1 gives the algorithm for the initialization step of the analysis. It checks for every definition and every use of each variable and assocites an IntegerOkay state with each use and definition. It also assocites a dependency list of variables whose state affects the state of the variable in question.

Algorithm 1: Initialization step of the IntegerOkay analysis

1: procedurexInitialize(V)

2: ▷ Let V be the set of all double variables in the function 3: ▷ Let v.D be the set of all definitions of variable v 4: ▷ Let d.state be the integerOkay state of variable v for definition d 5: ▷ Let v.U be the set of all uses of variable v 6: ▷ Let u.state be the integerOkay state of variable v for use u

7: for allxv ∈ V xdo 8: for allxd ∈ v.Dxdo 9: d.state ← GetStateDef (v,d) 10: endxfor 11: for allxu ∈ v.Uxdo 12: u.state ← GetStateUse (v,u) 13: endxfor 14: endxfor 15: endxprocedure

16: procedurexGetStateDef(v,d)

17: ▷ Let v be a variable and d be a definition of v 18: ▷ Let d.deps be the dependency list of variable v for definition d 19: ▷ Let d.RHS be the right hand side expression of definition d 20: 21: ▷ if d is an assignment from a constant

22: ifxIsConstAssignment (d)xthen 23: ifxIsRealInteger (d.RHS)xthen

24: ▷ if the RHS is a real integer

25: return IntOk 26: endxif 27: endxif

28: ▷ if d is a copy statement

29: ifxIsCopyStmt (d)xthen

30: ▷ add RHS variable (except v itself) to the dependency list of v for d

31: d.deps ← d.deps ∪ d.RHS.varName 32: d.deps ← d.deps − v

33:  return CondIntOk

34: endxif

35: ▷ if d is an assignment from a call to a builtin function

36: ifxIsAssignmentFromBuiltin (d)xthen

37: ▷ if the RHS builtin always returns integer (eg. floor(), ceil(), etc.)

38:  ifxDoesBuiltinReturnInt  (d.RHS)xthen

39: return IntOk 40: endxif

41: ▷ if the RHS builtin always returns a double (eg. pi(), etc.)

42:  ifxDoesBuiltinReturnDouble  (d.RHS)xthen

43: return NotIntOk 44: endxif

45: ▷ if the builtin returns integer depending 46: ▷ on the type of input arguments (eg. plus(), minus(), etc.)

47:  ifxDoesBuiltinReturnIntDepends  (d.RHS)xthen

48: ▷ add argumnets (except v) to the builtin to the dependency list of v for d

49: d.deps ← d.deps ∪ d.RHS.args 50: d.deps ← d.deps − v

51:  return CondIntOk

52: endxif 53: return NotIntOk 54: endxif

55: ▷ if d is an assignment from an array access

56: ifxIsAssignmentFromArrayAccess (d)xthen

57: ▷ add RHS array variable (except v itself) to the dependency list of v for d

58: d.deps ← d.deps ∪ d.RHS.arrayName 59: d.deps ← d.deps − v

60:  return CondIntOk

61: endxif

62: ▷ default return NotIntOk

63: return NotIntOk 64: endxprocedure

65: procedurexGetStateUse(v,u)

66: ▷ Let v be a variable and u be a use expression of v 67: ▷ Let u.deps be the dependency list of variable v for use u 68: ▷ if v is used as an array index in u

69: ifxIsUseArrayIndex (u)xthen 70: return IntOk 71: endxif

72: ▷ if v is used as an argument to a builtin function

73: ifxIsUseBuiltinArgument (u)xthen

74: ▷ if argument type does not affect the correctness of the result from builtin (eg. plus())

75:  ifxDoesArgTypeAffectResult  (u)xthen

76: return IntOk 77: endxif

78: ▷ if the argument type may affect the builtin result (eg. divide())

79:  ifxDoesArgTypeAffectResult  (u)xthen

80: return NotIntOk 81: endxif

82: ▷ if the affect of the argument type depends on the types of other arguments

83:  ifxDoesArgTypeDependOnOtherArgs  (u)xthen

84: u.deps ← u.deps ∪ u.args 85: u.deps ← u.deps − v

86:  return CondIntOk

87: endxif 88: endxif

89: ▷ if v is used in a copy statement

90: ifxIsUseCopyStatement (u)xthen 91: return IntOk 92: endxif 93: return NotIntOk 94: endxprocedure Algorithm 2: Fixed point solver for the IntegerOkay analysis

1: procedurexFixedpointSolver(V)

2: ▷ Let V be the set of all the double variables in the function 3: ▷ Let V ′ be the set of variables that can be declared as integers 4: ▷ Let v.D be the set of all definitions of variable v 5: ▷ Let d.state be the integerOkay state of variable v for definition d 6: ▷ Let v.U be the set of all uses of variable v 7: ▷ Let u.state be the integerOkay state of variable v for use u 8: ▷ Let v.State be the integerOkay state of variable v for the whole function 9: ▷ Let v.State be initialized to ∼

10: V ′ ← ∅ 11: repeat 12: V ′_{old} ← V ′ 13: for allxv ∈ V xdo 14: for allxd ∈ v.Dxdo 15: v.State ← v.State ▷◁d.state 16: endxfor 17: for allxu ∈ v.Uxdo 18: v.State ← v.State ▷◁u.state 19: endxfor 20: ifxv.State = IntOk xthen 21: v′ ← v 22: V ′ ← V ′ ∪ v′ 23: V ← V − v′ 24: ResolveDependencies(V,v′) 25: endxif 26: endxfor 27: changed ← V ′ ≠ V ′_{old} 28: untilx¬changed 29: endxprocedure 30: procedurexResolveDependencies(V,v′)

31: ▷ Let V be the set of all the double variables in the function 32: ▷ Let v′ be an IntegerOkay variable 33: ▷ Let v.D be the set of all definitions of variable v 34: ▷ Let d.state be the integerOkay state of variable v for definition d 35: ▷ Let d.deps be the dependency list of variable v for definition d 36: ▷ Let v.U be the set of all uses of variable v 37: ▷ Let u.state be the integerOkay state of variable v for use u 38: ▷ Let u.deps be the dependency list of variable v for use u

39: for allxv ∈ V xdo 40: for allxd ∈ v.Dxdo 41: d.deps ← d.deps − v′ 42: ifxd.deps = ∅xthen 43: d.state ← IntOk 44: endxif 45: endxfor 46: for allxu ∈ v.Uxdo 47: u.deps ← u.deps − v′ 48: ifxu.deps = ∅xthen 49: u.state ← IntOk 50: endxif 51: endxfor 52: endxfor 53: endxprocedure 8.4.2 STEP 2: The Fixed Point Solver

Once the initial state has been assigned for each use and each definition of every variable in STEP 1, the next step is to find the variables that can be of integer type across the function. The fixed point solver iteratively finds these variables until a fixed point is reached and no more variables are safe to be defined as integers.

The input to the fixed point solver is the set of all double variables V with state and dependency list initialized for each definition and each use of every variable v in V. The output of the fixed point solver is V ′, the set of variables that can be safely defined as integers. The fixed point solver also defines the variable v.State that stores the final state value for the variable v in the function, independent of any use or definition. For each variable v, v.State is assigned an initial empty value ∼. V ′ is initially set to ∅.

Algorithm 2 provides an algorithm for this fixed point solver. Note that the algorithm uses a ▷◁ operator to merge the state values of various definitions and uses of a variable to obtain its final state. Table 8.2 gives a definition of the ▷◁ operator used by this analysis. In the table, CondIntOk(s,s = ∅) is the case when d.deps ∪ u.deps = ∅ for a variable v, and CondIntOk(s,sx∅) is the case when d.deps ∪ u.depsx∅.

11  ▷◁  11   IntOk    11 CondIntOk(s,s = ∅) 11 CondIntOk(s,sx∅) 11 NotIntOk   11  ∼
11       IntOk        11   IntOk    11       IntOk        11    NotIntOk      11 NotIntOk   11       IntOk
11 CondIntOk(s,s = ∅) 11   IntOk    11       IntOk        11    NotIntOk      11 NotIntOk   11 CondIntOk(s,s = ∅)
11  CondIntOk(s,sx∅) 11 NotIntOk   11     NotIntOk       11    NotIntOk      11 NotIntOk   11  CondIntOk(s,sx∅)
11     NotIntOk       11 NotIntOk   11     NotIntOk       11    NotIntOk      11 NotIntOk   11     NotIntOk
11  ∼  11   IntOk    11 CondIntOk(s,s = ∅) 11 CondIntOk(s,sx∅) 11 NotIntOk   11  ∼

11

Tablex8.2: Definition of the ▷◁ merge operator 8.5 An Example

Consider the following pseudocode for example:

   /*1*/xxx=x3.0;
   x/*2*/xyx=x3.14;
   x/*3*/xzx=xx+y;
   x/*4*/xforx(ix=x0;xix<x5;xi++)
   x/*5*/xxxyx=xy+i;
   x/*6*/xend
   x

In this example, the initialization step proceeds as follows. On line 1, x is IntegerOkay since 3.0 is a real integer. On line 2, y is Not IntegerOkay. On line 3, z is Conditionally IntegerOkay and depends on x and y, whereas x and y are IntegerOkay in their use in the expression x+y. On line 4, i is IntegerOkay in its definition i = 0, in its use in the expression i < 5, and also in the definition i++. On line 5, y is conditionally IntegerOkay and depends on i in its definition and it is IntegerOkay in its use in y+i. i is IntegerOkay in its use in y+i. Note that on line 5, we do not include y in its own dependency list, since if we say, y is conditionally IntegerOkay and depends on y, it is safe to declare y as integer as long as it does not have any other dependencies and is IntegerOkay everywhere else in the function.

The fixed-point solver for this example proceeds as follows. We look for variables that are IntegerOkay at every point in the function. x and i are two such variables and we can declare them to be an integer. We also remove x from the dependency list of definition of z on line 3, and i from the dependency list of definition of y on line 5. Next, we search again and find that y is IntegerOkay in its use on line 3 and line 5, and also in its definition on line 5, however it is Not IntegerOkay in its definition on line 2 and thus it cannot be declared as an integer. z on line 3 is dependent on y and thus it can also not be declared as an integer. At this point, we have reached a fixed point since there are no more upgrades. Finally, we declare x and i as integers, and y and z as doubles.

Evaluation

In this chapter we evaluate the performance of our compiler. In this research our main aim was to generate X10 code for Matlab such that its sequential performance would be comparable to the performance provided by the state of the art tools which translate Matlab to more traditional imperative languages such as C and Fortran. To demonstrate our results, we compiled a set of 17 Matlab programs to X10 via the MiX10 compiler and compared their performance results with those of the original Matlab programs, C programs generated for our benchmarks via the Matlab coder, and Fortran programs generated by the Mc2For

compiler.1 1We also compared our results to Octave, a widely used open source alternative to Matlab. However, since Octave involves an interpreter, it performed slower than the standard Matlab compiler (with a mean slowdown of 66.67 times slower) over all of our benchmarks, thus in this section we do not concentrate on comparison of our results with Octave. In addition to showing our best overall sequential performance, we also demonstrate the results of compiling the generated X10 code to Java compared to C++, effects on the performance for the various efficiency enhancing techniques discussed in this thesis, and finally the performance of the parallel X10 code generated for Matlab parfor loops.

9.1 Benchmarks

The set of benchmarks used for our experiments consists of benchmarks from various sources; Most of them are from related projects like FALCONx[RP99] and OTTERx[QMSZ98a], Chalmers university of

Technology2 2http://www.elmagn.chalmers.se/courses/CEM/  , “Mathworks’
central file excahange”3 3http://www.mathworks.com/matlabcentral/fileexchange  ,

and the presentation on parallel programming in Matlab by Burkardt and

Cliff4  ^{4http://people.sc.fsu.edu/~jburkardt/presentations/matlab\_parallel.pdf}  .

This set of benchmarks covers the commonly used Matlab features like arrays of different dimensions, loops, use of numerical functions like random number generation, trigonometric operations, and array operations like transpose and matrix multiplication. Table 9.1 gives a description of all the benchmarks we used and shows their special features.

11 Benchmark 11 Source  11 Description  11 Key features
11 bbai  11 Matlab file exchange 11 Implementation of the Babai estimation algorithm 11 2-D arrays, random number generation
11 bubl  11 McLab  11 Bubble sort  11 1-D array, nested loops
11 capr  11 Chalmers University 11 Computes the capacitance of a transmission  line  using finite difference and Gauss-Seidel method 11 Array operations on 2-D arrays, nested loops

11 clos  11 Otter project  11 Calculates the transitive closure of a directed graph 11 Matrix multiplication, 2-D arrays
11 crni  11 Falcon project  11 Crank-Nicholson solution to the heat equation 11 read/write operations on a very large 2-D array
11 dich  11 Falcon project  11 Dirichlet solution to Laplace’s equation 11 Array operations on 2-D arrays, nested loops
11 diff  11 Matlab file exchange 11 Calculates the diffraction pattern of monochromatic light 11 2-D  arrays,  Concatenation operations, complex numbers
11 edit  11 Matlab file exchange 11 Calculates the edit distance between two strings 11 many 1-D arrays of characters
11 fiff  11 Falcon project  11 Computes the finite difference solution to the wave equation 11 Array operations on 2-D arrays, nested loops
11 lgdr  11 x  11 Calculates derivatives of Legendre polynomials 11 Array transpose on row vectors
11 mbrt  11 McFor project  11 Computes Mandelbrot sets  11 Complex numbers, parfor loop
11 nb1d  11 Otter project  11 Simulates the 1-dimensional n-body problem 11 Column-vectors, nested loops, parfor loop
11 matmul  11 McLab  11 naive matrix multiplication  11 2-D arrays, nested loops, parfor loop
11 mcpi  11 McLab  11 Calculates π by the Monte Carlo method 11 Scalar values, Random number generation, parfor loop
11 numprime 11 Burkardt and Cliff  11 Simulates the sieve of Eratosthenes for calculating number of prime numbers less than a given number 11 Scalar values, nested loops, parfor loop

11 optstop  11 Burkardt and Cliff  11 Solution to the optimal stopping problem 11 Row vectors, random number generation, parfor loop
11 quadrature 11 Burkardt and Cliff  11 Simulates the quadrature approach for calculating integral of a function 11 Scalar values, parfor loop

Tablex9.1: Benchmarks 9.2 Experimental Setup

We used Mathworks’ Matlab release R2013a to execute our benchmarks in Matlab and Matlab coder. We also executed them using the GNU Octave version 3.2.4. We compiled our benchmarks to Fortran using the Mc2For compiler and compiled the generated Fortran code using the GCC 4.6.3 GFortran compiler with optimization level -O3. To compile the generated X10 code from our MiX10 compiler, we used X10 version 2.4.0. We used OpenJDK Java 1.7.0_51 to compile and run Java code generated by the X10 compiler, and GCC 4.6.4 g++ compiler to compile the C++ code generated by the X10 compiler. All the experiments were run on a machine with Intel(R) Core(TM) i7-3820 CPU @ 3.60GHz processor and 16 GB memory running GNU/Linux(3.8.0-35-generic #52-Ubuntu). For each benchmark, we used an input size to make the program run for approximately 20 seconds on the de facto Matlab compiler. We used the same input sizes for compiling and running benchmarks via other compilers. We collected the execution times (averaged over five runs) for each benchmark and compared their speedups over Mathworks’ Matlab runtimes (normalized to one).

9.3 X10 Compiler Variations

The MiX10 compiler compiles the source Matlab code to X10 code, which is then compiled by the X10 compiler. The X10 compiler is also a source to source compiler that provides two backends, a C++ backend that generates C++ code and a Java backend that generates Java code, which are then compiled by their respective compilers to executable code. Both these backends provide a -NO_CHECKS switch that generates the C++/Java code that does not include dynamic array bounds checks, which are otherwise included by default. As we described in section 4.1.1, we altered the X10 compiler to use column-major array indexing. We always used the -O optimization flag for the X10 compiler for both the backends, with notable exceptions where the X10 optimizer generated code which interacted extremely negatively with the Java JIT, as discussed in section 9.5.1. For all of our experiments, we used our IntegerOkay analysis, except for the experiment which investigates the performance impact of this analysis. Our best results were obtained by compiling the generated X10 code with the C++ backend with -NO_CHECKS enabled, where the X10 code itself was generated by the MiX10 compiler with simple arrays and our IntegerOkay analysis enabled.

9.4 Overall MiX10 Performance

We compared the performance of the generated X10 code with that of the original Matlab code run on Mathworks’ implementation of Matlab. To compare against the state of the art static compilers, we also compared the performance of the MiX10 generated X10 code with the C code generated by Matlab coder and the Fortran code generated by the Mc2For compiler.

PIC Figurex9.1: Performance of MiX10 vs other state-of-the-art static compilers, reported as speedups relative to Mathworks’ Matlab, higher is better.

Figure 9.1 shows the speedups and slowdowns for the code generated for our benchmarks by different compilers. For MiX10 we have included the results for the X10 code compiled by the X10 C++ backend compiled, once with -NO_CHECKS enabled and once with -NO_CHEKCS disabled. For Fortran we included the results for the code generated without bounds checks. C code from Matlab coder was generated with default settings and includes bounds checks. We also calculated the geometric mean of speedups(slowdowns) for all the benchmarks for each compiler.

Overall, one can see that the static compilers all provide excellent speedups, often of at least an order of magnitude faster. Thus, for the kinds of benchmarks in our benchmark set, it would seem that tools like the Matlab coder, Mc2For, and our MiX10 tools are very useful. MiX10 outperforms Matlab coder in 9 out of 17 benchmarks, when compared with the X10 version compiled with bounds checks, and 10 out of 17 benchmarks when compared with the version with no bounds checks. For Fortran, the generated X10 does better in 7 out of 17 benchmarks with no bounds checks, and 6 out of 17 benchmarks with bounds checks enabled. Note that Matlab coder was not able to compile 1 of our benchmarks (diff ) due to the dynamic array growth involved in it; MiX10 supports dynamic array growth.

We achieved a mean speedup of 4.8 over Matlab, for the X10 code with bounds checks, and 6.8 for the x10 code with no bounds checks. On the other hand, Matlab coder gave a mean speedup of 6.3 and Mc2For gave a mean speedup of 10.2. However, we noticed that our mean result was skewed due to two benchmarks for which the generated X10 performed very poorly compared to the generated C code. These benchmarks are clos and lgdr. In the following paragraphs we explain the reason for their poor performance. If we do not consider these two benchmarks, we get a mean speedup of 6.7 for the X10 code with bounds checks compared to 5.2 for the C code. For the X10 code compiled with no bounds checks we get a mean speedup of 9.3 compared to 11.6 for Fortran.

clos involves repeated calls to the builtin matrix multiplication operation for the 2-dimensional matrices. The generated C code from Matlab coder uses highly optimized matrix multiplication libraries compared to the naive matrix multiplication implementation used by MiX10. Thus, MiX10 gets a speedup of 0.02 as compared to 1.05 for C. Note that the generated Fortran code is also slowed down (speedup of 0.04) due to the same reason. As a future work, We plan to replace our matrix multiplication implementation with calls to an optimized library function.

lgdr involves repeated transpose of a row vector to a column vector. Matlab and Fortran, both being array languages are highly optimized for transpose operations. MiX10 currently uses a naive transpose algorithm which is not optimized. We did achieve a speedup of over 10 times compared to Matlab but it is not as good as the speedups achieved by C (speedup of 505.0) and Fortran (speedup of 336.7). For transpose operation also, we plan to replace our current implementation with an optimized implementation or a call to an optimized library function.

Both of these examples show that in addition to generating good code, another important task is developing optimized X10 library routines for key array computations.

Other interesting numbers are shown by optstop, fiff, nb1d, and quadrature. optstop gave a speedup of just 1.5 even without bounds checks. It involves repeated random number generation, which our experiments showed to be slow for the X10 C++ backend compared to Fortran and even the Java backend. This problem is worse with C, due to which the C code from Matlab coder gives a speedup of mere 0.6(slowdown). Fortran performs better with a speedup of 4.3. bbai shows a similar pattern due to the same reason. fiff is characterized by stencil operations in a loop on a 2-dimensional array. These operations are also optimized by array-based languages like Fortran and Matlab. For nb1d, Fortran performs better due to the use of column vectors in the benchmark, which are represented as 2-dimensional arrays in X10 but in Fortran they are represented as 1-dimensional and are optimized. 2-dimensional arrays are not as fast in X10 as the 1-dimensional arrays. quadrature involves repeated arithmetic calculations on a range of numbers. We achieve a speedup of about 200 times compared to Matlab, however it is slow compared to speedups of 3348 and 502 by C and Fortran respectively. We believe that Matlab coder leverages partial evaluation for optimizing numerical methods’ implementations.

For most of the other benchmarks, we perform better or nearly equal to C and Fortran code.

Despite the facts that: (1) the sequential core of X10 is a high-level object oriented language which is not specialized for array-based operations; and (2) Generating the executable binaries via MiX10 involves two levels of source-to-source compilations (Matlab → X10 → C++); we have achieved performance comparable to C, the state of the art in statically compiled languages and Fortran, a statically compiled language highly specialized for arrays.

9.5 X10 C++ Backend vs. X10 Java Backend

The X10 compiler provides two backends, a C++ backend that compiles the X10 code to native binary via C++, and a Java backend that compiles the X10 code to JVM code via Java. We were interested to see how well these backends perform when used to compile the MiX10 generated code. Even though we did not expect Java code to perform as well as the C++ code, our aim was to make sure that we achieved good performance, significantly better than Matlab, for the X10 Java backend. This would enable Matlab programmers to use our MiX10 compiler to generate code that could be integrated into Java applications.

In this section we present the performance comparison of the MiX10 generated X10 code compiled by the X10 C++ backend with that compiled by the X10 Java backend. Columns 3 and 4 of the Table 9.2 show speedups for our benchmarks compiled with the X10 C++ backend without bounds checks, and with bounds checks respectively. Columns 5 and 6 show these values for compilation with the X10 Java backend without bounds checks, and with bounds checks respectively. We also show the geometric mean of the speedups for all the 4 cases.

11  Benchmark 11 Matlab 11 C++ (no checks) 11 C++ (checks) 11 Java (no checks) 11 Java (checks)
11  bbai 11 1 11  4.9  11  4.9  11  11.3  11  10.7
11  bubl 11 1 11  15.8  11  10.8  11  7.5  11  7.5
11  capr 11 1 11  13.5  11  12.7  11  11.1  11  6.3
11  clos 11 1 11  0.03  11  0.02  11  0.02  11  0.002
11  crni 11 1 11  6.5  11  5.3  11  5.6  11  4
11  dich 11 1 11  7.6  11  7.3  11  7  11  1.6
11  diff 11 1 11  4.6  11  4.4  11  0.3  11  0.3
11  edit 11 1 11  29.7  11  19.4  11  22.1  11  20
11  fiff 11 1 11  9.8  11  3.5  11  2.1  11  1.4
11  lgdr 11 1 11  13.5  11  11.9  11  10.6  11  10.6
11  mbrt 11 1 11  6.5  11  6.5  11  0.3  11  0.3
11  nb1d 11 1 11  6.2  11  4.8  11  5.5  11  4.1
11  matmul 11 1 11  14.7  11  2.5  11  1.1  11  0.8
11  mcpi 11 1 11  3.3  11  2.5  11  2.9  11  3
11  numprime 11 1 11  7.6  11  6.8  11  6.5  11  6.4
11  optstop 11 1 11  1.5  11  1.2  11  1.8  11  1.4
11  quadrature 11 1 11  200.9  11  182.6  11  167.4  11  154.5
11 Geometric mean 11 1 11  6.8  11  4.8  11  3.4  11  2.4

11

Tablex9.2: MiX10 performance comparison : X10 C++ backend vs. X10 Java backend, speedups relative to Mathworks’ Matlab, higher is better

The mean speedups for the C++ backend are 6.8 and 4.8 respectively for the version with bounds checks switched off, and the version with bounds checks switched on, whereas for Java backend these values are 3.4 and 2.4 respectively. This is expected, given that C++ is compiled to native binary while Java is JIT compiled.

bbai and optstop are the two exceptions, where Java performs better than C++. For bbai, both the Java versions gave a speedup of over 10, whereas for C++, the speedup is under 5 for both the versions. For optstop, the difference is not large, with C++ speedup at 1.5 (1.2 for the bounds checks version) compared to 1.8 (1.4 for the bounds checks version) for the Java backend. bbai is slower with X10 C++ backend because it includes repeated calls to the X10’s Random.nextDouble() function to generate random numbers. We found it to be significantly slower in the C++ backend compared to the Java backend. We have reported our findings to the X10 development team and they have validated our findings. optstop is slower for the same reason : It also involves repeated random number generation. Note that for these two benchmarks, even the C code generated via Matlab coder is slower than the C++ code, with speedups of 4.2 and 0.6 respectively for bbai and optstop.

Other interesting results are for the benchmarks diff, fiff, mbrt and matmul. For these benchmarks, results from the Java backend are significantly slower compared to the C++ backend. diff and mbrt involve operations on complex numbers. In the X10 C++ backend, complex numbers are stored as structs and are kept on the stack, whereas in the Java backend, they are stored as objects and reside in the heap storage. fiff and matmul are characterized by repeated array access and read/write operations on 2-dimensional arrays. For these benchmarks, the Java backend performs significantly slower compared to the C++ backend with no bounds checks(2.1 vs. 9.8 for fiff and 1.1 vs. 14.7 for matmul), however compared to the performance by the C++ beckend with bounds checks, it is not as slow(2.1 vs. 3.5 for fiff and 1.1 vs. 2.5 for matmul). The reason is that even with bounds checks turned off for the X10 to Java compiler, The Java compiler by default has bounds checks on. These checks have a significant effect on performance for 2-dimensional array operations.

9.5.1 When Not to Use the X10 -O

One of the most surprising results in this set of experiments was the fact that we had to sometimes disable the X10 -O optimizer switch when using the X10 Java backend.. For the benchmarks capr and dich, in the case when X10 bounds checks are switched on, we found very pathological performance, with slowdowns of over 2 orders of magntitude, when the X10 compiler’s optimization switch(-O) was used.

We recorded running times of 785.3 seconds for capr compared to 3.2 seconds without the optimization, and 1558.9 seconds for dich compared to 12.7 seconds without the optimization. With the help of the X10 development team we determined that switching on the optimization triggered code inlining for the array bounds check code, which then caused the resultant Java program to be too large to be handled by the JIT compiler. In fact, the Java JIT effectively gives up on this code and reverts to the interpreter.

Thus, it would seem that the X10 optimizer needs to be improved in order to apply aggressive inlining only when it does not have a negative impact on code size, and that different inlining strategies are needed for the C++ and Java backends.

9.6 Simple vs. Region Arrays

One of the key optimizations used by MiX10 is to use simple arrays, wherever possible, for higher performance. In this section we discuss the performance gains obtained by using simple arrays over region arrays and the specialized region arrays. A description of these three kinds of arrays provided by X10 was given in Sec.x2.1.3. Table 9.3 shows the relative speedups and slowdowns for our benchmarks compiled to use different kinds of X10 arrays for the C++ backend and the Java backend.

11              11        11  X10 C++ backend  11  X10 Java backend
11  Benchmark 11 Matlab 11 Simple arrays 11 Region arrays 11 Sp. region arrays 11 Simple arrays 11 Region arrays 11 Sp. region arrays
11  bbai 11 1.0 11  4.9  11  2.7  11  2.7  11  11.3  11  6.4  11  6.6
11  bubl 11 1.0 11  15.8  11  11.4  11  11.6  11  7.5  11  3.6  11  3.7
11  capr 11 1.0 11  13.5  11  11.6  11  12.4  11  11.1  11  0.02  11  10.5
11  clos 11 1.0 11  0.03  11  0.01  11  0.01  11  0.02  11  0.01  11  0.01
11  crni 11 1.0 11  6.5  11  3.6  11  3.9  11  5.6  11  4  11  4.1
11  dich 11 1.0 11  7.6  11  6.7  11  7.0  11  7.0  11  0.01  11  0.02
11  diff 11 1.0 11  4.6  11  4.2  11  4.3  11  0.3  11  0.3  11  0.3
11  edit 11 1.0 11  29.7  11  4.3  11  3.6  11  22.1  11  9.4  11  9.4
11  fiff 11 1.0 11  9.8  11  2.0  11  2.8  11  2.1  11  1.4  11  1.4
11  lgdr 11 1.0 11  13.5  11  1.6  11  1.5  11  10.6  11  5.4  11  5.4
11  mbrt 11 1.0 11  6.5  11  6.3  11  6.5  11  0.3  11  5.1  11  5.1
11  nb1d 11 1.0 11  6.2  11  0.3  11  0.3  11  5.5  11  1.4  11  1.4
11  matmul 11 1.0 11  14.7  11  1.3  11  1.4  11  1.1  11  0.5  11  0.5
11  mcpi 11 1.0 11  3.3  11  2.8  11  2.7  11  2.9  11  3.0  11  3.0
11  numprime 11 1.0 11  7.6  11  5.7  11  5.7  11  6.5  11  6.3  11  6.3
11  optstop 11 1.0 11  1.5  11  0.4  11  0.4  11  1.8  11  1.2  11  1.3
11  quadrature 11 1.0 11  200.9  11  200.9  11  200.9  11  167.4  11  143.5  11  154.5
11 Geometric mean 11 1.0 11  6.8  11  2.7  11  2.8  11  3.4  11  1.3  11  1.9

11

Tablex9.3: MiX10 performance comparison : Simple arrays vs. Region arrays vs. Specialized region arrays, speedup relative to Mathworks’ Matlab, higher is better

For the C++ backend we obtained a mean speedup of 6.8 for Simple arrays, compared to 2.7 for region arrays and 2.8 for specialized region arrays. For the Java backend, we obtained speedups of 3.4, 1.3 and 1.9 for the simple arrays, region arrays, and the specialized region arrays respectively. These results are as expected in Sec.x4.1. For the C++ backend, most noticeable performance differences between simple arrays and region arrays are for edit, fiff, lgdr, nb1d, matmul and optstop. All of these benchmarks are characterized by large number of array accesses and read/write operations on 2-dimensional arrays, except optstop and edit, which have multiple large 1-dimensional arrays. The performance difference is most noticeable for nb1d, where the region arrays are about 20 times slower than the simple arrays. This is because nb1d involves simple operations on a large column vector. With simple arrays, since the compiler knows that it is a column vector, rather than a 2-dimensional matrix, even though it is declared as a 2-dimensional array, the performance can be optimized to match that of the underlying Rail. However, this is not possible for region arrays where the size of each dimension is not known statically. For the C++ backend, we do not observe significant performance differences between the region arrays and the specialized region arrays.

For the Java backend we observed a higher difference in the mean performance for the simple arrays and the region arrays. The mean speedup for region arrays is 1.3 whereas for simple arrays it is nearly 3 times more at 3.4. There is also a significant difference between the performance of specialized region arrays and region arrays. Speedup for specialized region arrays is 1.9. Like the C++ backend, here also, most noticeable performance gain for simple arrays is for benchmarks involving a large number of array accesses and read/writes. capr and dich ask for special consideration. For capr, even with X10 compiler’s bounds checks turned off, the region array version slows down by more than 500 times compared to the simple array version and even the specialized region array version. This again, is due to the fact that region arrays, with the dynamic shape checks, generated more code than the JIT compiler could handle. For dich the slowdown due to region arrays was about 700 times compared to simple arrays. For dich, even the specialization on region arrays was not enough to reduce the code size enough to be able to be JIT compiled.

9.7 Effect of the IntegerOkay Analysis

In this section we present an overview of the performance improvements achieved by MiX10 by using the IntegerOkay analysis. Table 9.4 shows a comparison of speedups gained by using the IntegerOkay analysis over those without using it. For this experiment we used results with X10 optimizations turned on and bounds checks turned off.

11               11        11  X10 C++ backend  11  X10 Java backend
11  Benchmark 11 Matlab 11 IntegerOkay 11 All Doubles 11 IntegerOkay 11 All Doubles
11  bbai 11 1.0 11  4.9  11  3.8  11  11.3  11  8.2
11  bubl 11 1.0 11  15.8  11  2.2  11  7.5  11  4.2
11  capr 11 1.0 11  13.5  11  1.7  11  11.1  11  9.7
11  clos 11 1.0 11  0.03  11  0.02  11  0.02  11  0.01
11  crni 11 1.0 11  6.5  11  2.8  11  5.6  11  5.5
11  dich 11 1.0 11  7.6  11  1.0  11  7.0  11  5.8
11  diff 11 1.0 11  4.6  11  4.5  11  0.3  11  0.3
11  edit 11 1.0 11  29.7  11  13.5  11  22.1  11  20.0
11  fiff 11 1.0 11  9.8  11  1.0  11  2.1  11  1.8
11  lgdr 11 1.0 11  13.5  11  10.1  11  10.6  11  11.0
11  mbrt 11 1.0 11  6.5  11  6.1  11  0.3  11  0.3
11  nb1d 11 1.0 11  6.2  11  5.2  11  5.5  11  5.5
11  matmul 11 1.0 11  14.7  11  14.5  11  1.1  11  1.2
11  mcpi 11 1.0 11  3.3  11  3.3  11  2.9  11  2.9
11  numprime 11 1.0 11  7.6  11  7.6  11  6.5  11  7.1
11  optstop 11 1.0 11  1.5  11  1.0  11  1.8  11  1.0
11  quadrature 11 1.0 11 200.9  11 182.6  11 167.4  11 143.5
11 Geometric mean 11 1.0 11  6.8  11  3.4  11  3.4  11  2.9

11

Tablex9.4: Performance evaluation for the IntegerOkay analysis, speedups relative to Mathworks’ Matlab, higher is better

For the C++ backend, we observed a mean speedup of 6.8 which is two times the speedup gained by not using the IntegerOkay analysis, which is equal to 3.4. We observed a significant gain in performance by using IntegerOkay analysis for the benchmarks that involve significant number of array indexing operations. bubl, capr, crni, dich, and fiff show the most significant performance gains. The reason for this behaviour is that, X10 requires all array indices to be of type Long, thus if the variables used as array indices are declared to be of type Double (which is the default in Matlab), they must be typecast to Long type. Double to Long is very time consuming because every cast involves a check on the value of the Double type variable to ensure that it can safely fit into Long type.

For the Java backend, with the IntegerOkay analysis, we get a mean speedup of 3.4 as compared to 2.9 without it. The reason for the lower difference as compared to that for the C++ backend is that, for Java backend, the X10 compiler does not generate the value checks for Double type values, instead it relies on the JVM to make these checks, resulting in a better performance. Also note that, without the IntegerOkay analysis, the C++ backend results are slower than the Java backend results for 9 out of 17 benchmarks.

To conclude, IntegerOkay analysis is very important for efficient performance of code involving Arrays, specially for the X10 C++ backend.

9.8 Matlab parfor vs. MiX10 Parallel Code

Given that we have established that we can generate competitive sequential code, we wanted to also do a preliminary study to see if we could get additional benefits from the high-perfomance nature of X10. In this section we present the preliminary results for the compilation of Matlab parfor construct to the parallel X10 code. 7 out of our 17 benchmarks could be safely modified to use the parfor loop. We compare the performance of the generated parallel X10 programs for these benchmarks to that of Matlab code using parfor, and to their sequential X10 versions. For this experiment, we used the sequential versions of the generated X10 programs with optimizations and no bounds checks. For the parallel versions we used both the variants, with optimizations and bounds checks, and with optimizations and without bounds checks. It is important to note that the Intel(R) Core(TM) i7-3820 CPU used for this experiment has 4 CPU cores and 8 hardware threads, thus bounding the X10 parallelization speedup at 8. Table 9.5 shows the results for both the X10 C++ and the X10 Java backends.

11              11          11               11  X10 C++ backend  11  X10 Java backend
11               11          11               11 Sequential 11  Parallel  11 Sequential 11  Parallel
11  Benchmarks 11 MATLAB 11 MATLAB parfor 11 No checks 11 No checks 11 Checks 11 No checks 11 No checks 11 Checks
11  mbrt 11 1.0  11  1.7  11 6.5  11 25.3 11 25.3 11 0.3  11 1.3  11 1.3
11  nb1d 11 1.0  11  0.4  11 6.2  11 7.3  11 7.3 11 5.5  11 19.0 11 15.1
11  matmul 11 1.0  11  1.3  11 14.7 11 68.7 11 3.9 11 1.1  11 1.1  11 0.8
11  mcpi 11 1.0  11  4.6  11 3.3  11 15.7 11 15.9 11 2.9  11 18.1 11 18.2
11  numprime 11 1.0  11  5.3  11 7.6  11 30.0 11 30.9 11 6.5  11 24.8 11 26.4
11  optstop 11 1.0  11  4.1  11 1.4  11 2.0  11 2.1 11 1.8  11 10.7 11 9.7
11  quadrature 11 1.0  11  3.8  11 200.9 11 11.3 11 11.2 11 167.4 11 13.0 11 13.0
11 Geometric mean 11 1.0  11  2.3  11 8.9  11 14.5 11 9.8 11 3.7  11 7.8  11 7.1

11

Tablex9.5: Performance evaluation for MiX10 generated parallel X10 code for the Matlab parfor construct, speedups relative to Mathworks’ Matlab, higher is better

For the X10 C++ backend we achieved a mean speedup of 14.5 for the generated parallel X10 code without bounds checks, which is around 7 times of the speedup for the Matlab code with parfor, at a speedup of 2.3. Compared to X10 sequential code which has a mean speedup of 8.9, it is more than 1.5 times as fast. Even with the parallel X10 code with bounds checks we achieved a speedup of 9.8 which is over 4 times better than the Matlab parfor code. The optstop benchmark is an interesting exception. It is actually slower (at a speedup of 2.1) than the Matlab parfor version (at a speedup of 4.1). The sequential version of optstop is just slightly faster than the sequential Matlab version, with a speedup of just 1.5 (due to the reasons explained earlier in Sec.x9.4) and the total time for the parallel execution of each iteration, and managing the parallelization of these activities is just slightly faster than the sequential version. We see a similar trend for the matmul benchmark for the X10 Java backend. It shows a speedup of just 0.8 (version with bounds checks) as compared to 1.3 for the Matlab parfor version. For the parallel version of matmul, the speedup for the C++ backend with checks turned on is just 3.9 compared to 14.7 for the sequential version with no checks, however it is 1.6 times faster than the sequential version with checks, which has a speedup of just 2.5 (shown in figure 9.1). The quadrature benchmark shows very interesting numbers, with a slowdown of about 20 times and 13 times for the parallel X10 code compared to the sequential X10 code, for the C++ backend and the Java backend respectively. The quadrature benchmark consists of a loop with a large number of iterations (4600000 for our experiment), where each iteration performs an insignificant amount of computations with just 21 simple arithmetic operations on scalar values. A sequential speedup of over 200 times compared to the sequential Matlab code indicates the insignificance of each iteration in terms of computation time. In the parallel X10 code, each iteration is executed as a separate activity, and the time taken to manage the large number of activities overshadows the sequential speedup. Also, each activity has an atomic statement, which is a blocking construct (when one activity is executing the atomic statement, all other activities are blocked) and adds further overhead to the activity management system. Performance numbers for quadrature assert the fact that not all parallel Matlab programs are good candidates to be compiled to parallel X10 in a straight-forward fashion, specially the ones with large number of parallel loop iterations where each iteration itself does insignificant amount of work. As a future work, we plan to handle such programs with more sophisticated parallelization techniques. For example, one way to make a benchmark like quadrature more efficient would be to break the loop into two nested loops and executing the outer loop in a parallel fashion and the inner loop sequentially to ensure that each concurrent loop does substantial amount of work, however the challenge here is to determine the right number of iterations for the inner sequential loop to make it significant enough to take advantage of the parallelization.

Overall for the Java backend, we obtained a mean speedup of 7.8 for the X10 code with no bounds checks and 7.1 for the code with bounds checks. Compared to the Matlab parfor version we obtained about 3.5 times better performance. The parallel X10 code is over 2 times faster than the sequential X10 code (speedup of 3.7). For both, the C++ backend, and the Java backend, the mean speedup for the sequential X10 code is also substantially faster than the Matlab parallel code.

To conclude, the parallel X10 code provides much higher performance gains compared to the Matlab parfor code and even the X10 sequential code, which by itself is most of the times faster than the Matlab parallel code.

9.9 Summary

We showed that the MiX10 compiler with its efficient handling of array operations and optimizations like IntegerOkay can generate X10 code that provides performance comparable to the native code generated by the state of the art languages like C, which is fairly low-level, and Fortran, which itself is an array-based language. As a future work, we plan to use more efficient implementations of the builtin functions, and believe that it would further improve the performance of the code generated by MiX10.

With MiX10, we also took first steps to compile Matlab to parallel X10 code to take full advantage of the high performance features of X10. Our preliminary results are very inspiring and we plan to continue in this direction further, in the future.

In addition to demonstrating that our approach leads to good code, these experiments have also been quite valuable for the X10 development team. Our generated code has stressed the X10 system more than the hand-written X10 benchmarks and has exposed places where further improvements can be made.

Related Work

The work in this thesis presents a research compiler for Matlab. We provide a source-to-source static compiler that targets the high-level, object oriented language, X10. Our approach is open and extensible and generates sequential X10 code that is competitive in performance to code in state-of-the-art languages like C and Fortran, generated by other Matlab compilers. We also generated high performance code for Matlab’s parfor loops, that showed great performance improvements.

10.1 Alternatives to Matlab

Although our focus is on handling Matlab itself, there are notable open source alternatives of Matlab like Scilab[INR09], Julia[BKSE12], NumPy[Sci], FreeMat[DKB] and Octave[Oct]. Octave is an open source implementation of the Matlab language and supports most of the Matlab programs, however until the recently released version 3.8.1, Octave was solely an interpreted language and our experiments showed it to be orders of magnitude slower than Matlab. We would like to evaluate its performance for the latest version that comes with a JIT compiler. Scilab and FreeMat are similar in syntax to Matlab but have significant differences that prevent a significant portion of Matlab programs to be able to run on these systems. NumPy is a python package for scientific computing, and Julia is a technical computing language. Julia also provides a fairly advanced distributed parallel execution environment. However, these alternative systems concentrate on providing open library support and have not tackled the problems of static compilation. We are investigating if there is any way of sharing some of their library support with MiX10. A Comparative evaluation of Matlab, Octave, FreeMat, Scilab, R, and IDL on a cluster computing system is presented in a technical report by Coman at al.x[CBP^{+} 12] The MEGHA project[PAG11] provides an interesting approach to map Matlab array operations to CPUs and GPUs, but supports only a very small subset of Matlab.

10.2 Other Matlab Compilers

There have been previous research projects on static compilation of Matlab which focused particularly on the array-based subset of Matlab and developed advanced static analyses for determining shapes and sizes of arrays. For example, FALCON [RP99] is a Matlab to Fortran90 translator with sophisticated type inference algorithms. The McLab group has previously implemented a prototype Fortran 95 generatorx[Li09], and has more recently developed the next generation Fortran generator, Mc2Forx[LH14] in parallel with the MiX10 project. Some of the solutions are shared between the projects, especially the parts which extend the Tamer. Matlab Coder is a commercial compiler by MathWorks[Mata], which produces C code for a subset of Matlab. We also compared MiX10’s performance to Matlab coder. Below are more details about these and few other notable Matlab compiler research projects:

Falcon is a Matlab-to-Fortran 90 compiler that applies type inference algorithms developed for the array programming language APLx[JB01,xWS81,xBud83] and set language SETLx[Sch75]. It uses a static single-assignment(SSA) based intermediate representation, and inlines all functions and scripts into one large function. The Falcon project also curated a set of Matlab benchmarks to measure the performance of their compiler. Several of our benchmarks are originally from Falcon’s benchmark suite.

McFor is a prototype Matlab-to-Fortran 95 generator developed by the McLab research group and paved way for further research (of which MiX10 is a part) into developing efficient static Matlab compilers for Matlab. Mc2For is the second generation Matlab-to-Fortran 95 compiler built on top of the Tamer and McSaf static analysis tools. MiX10 and Mc2For share some of the solutions that extend the Tamer tool. We have also used Mc2For for our performance evaluation. A good performance by both MiX10 and Mc2For further validates the strength of our compilation techniques.

MAJIC (Matlab Just-In-time Compiler)x[AP02] is a continuation of the Falcon project. It aims to exploit optimization opportunities in the following three areas1 1http://polaris.cs.uiuc.edu/majic/techniques.html :

(1) source-level optimizations for matrix-based operations; (2) just-in-time compilation to defer compilation as much as possible and thus minimize the effects of challenges raised by Matlab’s "wild" nature as we discussed in Chapter 6; and (3) specialized optimizations for operations on sparse matrices.

Menhirx[CB98] is a retargetable Matlab compiler that can generate C or Fortran code based on a target system description(MTSD). MTSD describes target system’s properties and implementation details and thus allows efficient code generation that exploits optimized sequential and parallel libraries.

MATCHx[Joi03] is a library based compilation environment for distributed heterogeneous adaptive computing systems consisting of field-programmable gate arrays and digital signal processors. It parallelizes Matlab code based on user directives and generates C code that can call different runtime libraries.

Otterx[QMSZ98b] is a Matlab to C compiler that targets parallel computers supporting parallel numerical libraries like ScaLAPACKx[CDD^{+} 95]. It would be interesting, as a future work, to compare performance of the Otter compiler to that of MiX10 when it supports the parallel compilation of Matlab more effectively.

A major difference between MiX10 and these compilers is that MiX10 targets an object oriented language with high-level array abstractions, and which is itself source-to-source compiled, whereas all the above mentioned projects either target JIT compilation or static compilation to either Fortran, which is itself an array based language and in fact was the precursor of Matlab, or C, which is a fairly low-level language with advanced native compilers. Even though some of the techniques used by these compilers were helpful in generating X10 code for simple Matlab constructs, the novelty of MiX10 lies in the fact that it identified major challenges involved in efficiently compiling Matlab arrays and array based operations to X10 and achieved a performance comparable to that of compilers targeting C and Fortran.

10.3 Compilers Targeting X10

In terms of source-to-source compilers for X10, we are aware of two other projects. StreamX10 is a stream programming framework based on X10x[WTLY12]. StreamX10 consists of a stream programming language COStream and a compiler which translates programs in COStream to parallel X10 code. Tetsu discusses the design of a Ruby-based DSL for parallel programming that is compiled to X10x[Soh11]. Both these projects focus on compiling a parallel programming language to X10, a more efficient and generic parallel programming language. In the future, we would like to study these projects in more depth and hope to get useful insights into efficiently using X10 as a target language for parallelism in Matlab.

Conclusions and Future Work

11.1 Conclusions

This thesis is about providing a bridge between two communities, the scientists/engineers/students who like to program in Matlab on one side; and the programming language and compiler community who have designed elegant languages and powerful compiler techniques on the other side.

The X10 language has been designed to provide high-level array and concurrency abstractions, and our main goal was to develop a tool that would allow programmers to automatically convert their Matlab code to efficient X10 code. In this way programmers can port their existing Matlab code to X10, or continue to develop in Matlab and use our MiX10 compiler as a backend to generate X10 code. Since X10 is publicly available under the Eclipse Public License (x10-lang.org/home/x10-license.html ), users could have efficient high-performance code that they could freely distribute. Further, X10 itself can compile the code to either Java or C++, so our tool could be used in a tool chain to convert Matlab to those languages as well.

Our tool is part of the McLab project, which is entirely open source. Thus, we are providing an infrastructure for other compiler researchers to build upon this work, or to use some of our approaches to handle other popular languages such as R.

In this thesis we demonstrated the end-to-end organization of the MiX10 tool, and we identified that the correct handling of arrays, the minimization of casting by safely mapping Matlab double variables to X10 integer variables via IntegerOkay analysis, and handling concurrency features were the key challenges. We developed a custom version of X10’s rail-backed simple arrays, and identified where and how this could be used for generating efficient X10 code. For cases where precise static array shape and type information is not available, we showed how we can use the very flexible region-based arrays in X10, and our experiments demonstrated that it is very important to use the simple rail-backed arrays, for both the Java and C++ backends for X10.

Our experiments show that our generated X10 code is competitive with other state-of-the art code generators which target more traditional languages like C and Fortran. The C++ X10 backend produces faster code than the Java backend, but good performance is achieved in both cases.

One of the main motivations of choosing X10 as the target language is that it supports high-performance computing, which is often desirable for the computation-intensive applications developed by the engineers and scientists. To demonstrate how to take advantage of X10’s concurrency, we presented an effective translation of the Matlab parfor construct to semantically equivalent X10.

Our experiments showed significant performance gains for our generated parallel X10 code, as compared to Matlab’s parallel toolbox. This confirms that compiling Matlab to a modern high-performance language can lead to significant performance improvements.

In the process of developing MiX10, we also stressed the X10 compiler with machine generated code and found it to be mostly robust and efficient. We found that the X10 Java backend’s optimizations may in some cases generate Java code that is too large to be JIT compiled. We also found the random number generation for the C++ backend to be slower than that for the Java backend. We reported our feedback to the X10 development team and hope that our findings would help to make X10 even better. Overall, we found that with the right techniques, X10 can be used as an effective and efficient target language for scientific and array-based languages, for both, the sequential core and the parallel part.

11.2 Future Work

Based on our positive experiences to date, we plan to continue improving the MiX10 tool. There are three major areas where we plan to take ahead the development of MiX10, with the aim of making it more complete and more efficient:

Exploiting parallelism To help us better understand and efficiently exploit the inherent concurrency in the Matlab programs, first of all we would like to thoroughly evaluate and fine tune the concurrency constructs we introduced in Matlab via structured comments, and parallelism of the vectorized operations. Further, we would like to experiment to find the best way to tune the generated code for different sorts of parallel architectures. We are also planning to further our research into the direction of automatically parallelizing Matlab codes through static analysis mixed with run-time checks.

Efficient builtin implementation One of the greatest strengths of Matlab is its xlarge and efficient set of builtin libraries. This thesis concentrates more on effective and efficient compilation of Matlab constructs than finding the most efficient X10 implementations for the builtin operations. However, our experiments showed that there are some key library routines such as matrix multiply and transpose for which we need to have better X10 code for. Thus, there is scope for more work on X10 libraries, which could also be useful for other source-to-source compilers targeting X10.

Readability The code that we generate is already quite clean, but has a quite low-level structure, which might not be easily readable for non-experienced X10 programmers. We would like to apply further transformations on it to aggregate some low-level expressions, and to make the generated code look as “natural" as possible. This would help MiX10 users, who are familiar with X10, to easily fine-tune the generated X10 code to better suite their execution environments. It would also help in easy maintenance of the generated X10 code, and better integration with hand-written X10 code.

Our tool is open source, and we hope that the other research teams will use our infrastructure, as well as learn from our experiences of generating effective and efficient X10 code.

xxxBibliography

[AP02] George Almxsi and David Padua. MaJIC: compiling MATLAB for speed and responsiveness. In PLDI ’02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, Berlin, Germany, 2002, pages 294–303. ACM.

[BKSE12] Jeff Bezanson, Stefan Karpinski, ViralxB. Shah, and Alan Edelman. Julia: A Fast Dynamic Language for Technical Computing. CoRR, abs/1209.5145, 2012.

[Bud83] TimothyxA. Budd. An APL compiler for the UNIX timesharing system. In APL ’83: Proceedings of the international conference on APL, Washington, D.C., United States, 1983, pages 205–209. ACM, New York, NY, USA.

[CB98] Stxphane Chauveau and Franxois Bodin. Menhir: An Environment for High Performance Matlab. In LCR ’98: Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, 1998, pages 27–40. Springer-Verlag, London, UK.

[CBP^{+} 12] ExComan, MxBrewster, SxPopuri, AxRaim, and MxGobbert. A Comparative Evaluation of Matlab, Octave, FreeMat, Scilab, R, and IDL on Tara. Technical report, Baltimore County, US, 2012.

[CDD^{+} 95] J.xChoi, J.xDemmel, I.xDhillon, J.xDongarra, S.xOstrouchov, A.xPetitet, K.xStaney, D.xWalker, and R.xC. Whaley. LAPACK Working Note 95: ScaLAPACK: A Portable Linear Algebra Library for Distributed Memory Computers – Design Issues and Performance. Technical report, Knoxville, TN, USA, 1995.

[DH12a] Jesse Doherty and Laurie Hendren. McSAF: A static analysis framework for MATLAB. In Proceedings of ECOOP 2012, 2012, pages 132–155.

[DH12b] Anton Dubrau and Laurie Hendren. Taming MATLAB. In Proceedings of OOPSLA 2012, 2012, pages 503–522.

[DHR11] Jesse Doherty, Laurie Hendren, and Soroush Radpour. Kind analysis for MATLAB. In In Proceedings of OOPSLA 2011, 2011, pages 99–118.

[DKB]  EugenexIngerman DemetriosxKyriakis and Samit Basu.  Freemat.

http://freemat.sourceforge.net/  .

[Doh11] Jesse Doherty. McSAF: An Extensible Static Analysis Framework for the MATLAB Language. Master’s thesis, McGill University, December 2011.

[Dub12] Anton Dubrau. Taming matlab. Master’s thesis, April 2012.

[EH04] Torbjxrn Ekman and Gxrel Hedin. Reusable language specifications in JastAdd II. In Thomas Cleenewerck, editor, Evolution and Reuse of Language Specifications for DSLs (ERLS), 2004. Available from:

http://prog.vub.ac.be/~thomas/ERLS/Ekman.pdf  .

[IBM12] IBM. X10 programming language. http://x10-lang.org , February 2012.

[IBM13a] IBM. APGAS programming in X10 2.4, 2013.

http://x10-lang.org/documentation/tutorials/apgas-programming-in-x10-24.html  .

[IBM13b] IBM.  An  introduction  to  X10,  2013.

http://x10.sourceforge.net/documentation/intro/latest/html/node4.html  .

[INR09] INRIA. Scilab, 2009. http://www.scilab.org/platform/  .

[jas]  JastAdd. http://jastadd.org/ .

[JB01] PramodxG. Joisha and Prithviraj Banerjee. Correctly detecting intrinsic type errors in typeless languages such as MATLAB. In APL ’01: Proceedings of the 2001 conference on APL, New Haven, Connecticut, 2001, pages 7–21. ACM, New York, NY, USA.

[Joi03] PramodxG. Joisha. a MATLAB-to-C translator, 2003.

< http://www.ece.northwestern.edu/cpdc/pjoisha/mat2c/> .

[LH14] XuxLi and Laurie Hendren. Mc2for: A tool for automatically translating matlab to fortran 95. In In Proceedings of CSMR-WCRE 2014, 2014, pages 234–243.

[Li09] Jun Li. McFor: A MATLAB to FORTRAN 95 Compiler. Master’s thesis, McGill University, August 2009.

[Mata]  MathWorks.  MATLAB  Coder.

         http://www.mathworks.com/products/matlab-coder/  .

[Matb]  Mathworks. Reduction variables. http://www.mathworks.com/help/distcomp/advanced-topics.html#bq_of7_-3  .

[Mat13] MathWorks.  Parallel  computing  toolbox,  2013.

         http://www.mathworks.com/products/parallel-computing/  .

[Mol]  Cleve  Moler.  The  Growth  of  MATLAB
and  The  MathWorks  over  Two  Decades.

         http://www.mathworks.com/company/newsletters/news_notes/clevescorner/jan06.pdf  .

[Oct]  GNU  Octave.

         http://www.gnu.org/software/octave/index.html  .

[PAG11] Ashwin Prasad, Jayvant Anantpur, and R.xGovindarajan. Automatic compilation of MATLAB programs for synergistic execution on heterogeneous processors. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, San Jose, California, USA, 2011, PLDI ’11, pages 152–163. ACM, New York, NY, USA.

[QMSZ98a]MichaelxJ. Quinn, Alexey Malishevsky, Nagajagadeswar Seelam, and Yan Zhao. Preliminary Results from a Parallel MATLAB Compiler. In Proceedings of Int. Parallel Processing Symp., 1998, IPPS, pages 81–87.

[QMSZ98b]MichaelxJ. Quinn, Alexey Malishevsky, Nagajagadeswar Seelam, and Yan Zhao. Preliminary Results from a Parallel MATLAB Compiler. In Proc. Int. Parallel Processing Symp. (IPPS, 1998, pages 81–87. IEEE CS Press.

[RP99] LuizxDe Rose and David Padua. Techniques for the translation of MATLAB programs into Fortran 90. ACM Trans. Program. Lang. Syst., 21(2):286–323, 1999.

[SBP^{+} 12] Vijay Saraswat, Bard Bloom, Igor Peshansky, Olivier Tardieu, and David Grove. X10 Language Specification, Version 2.2. January 2012.

[Sch75] J.xT. Schwartz. Automatic data structure choice in a language of very high level. Commun. ACM, 18(12):722–728, 1975.

[Sci] Scipy.org. Numpy. http://www.numpy.org/ .

[Soh11] Tetsu Soh. Design and implementation of a DSL based on Ruby for parallel programming. Technical report, The University of Tokyo, January 2011.

[The02] The  Mathworks.  Technology  Backgrounder:
Accelerating  MATLAB,  September  2002.

http://www.mathworks.com/company/newsletters/digest/sept02/accel_matlab.pdf  .

[WS81] Zvi Weiss and HarryxJ. Saal. Compile time syntax analysis of APL programs. In APL ’81: Proceedings of the international conference on APL, San Francisco, California, United States, 1981, pages 313–320. ACM, New York, NY, USA.

[WTLY12] Haitao Wei, Hong Tan, Xiaoxian Liu, and Junqing Yu. StreamX10: a stream programming framework on X10. In Proceedings of the 2012 ACM SIGPLAN X10 Workshop, Beijing, China, 2012, X10 ’12, pages 1:1–1:6. ACM, New York, NY, USA.

AppendixxA

XML structure for builtin framework

The below listing gives the XML structure for the builtin operation plus. It contains two upper level nodes for each real and complex numbers. Each of these have specialization nodes for the simple arrays of different dimensions, and the region arrays. Each of the specializations has 5 types of implementations.

1 <plus >x 2 xx<real >x 3 xxxx<simple_array  >x 4 xxxxxx<array_1 >x 5 xxxxxxxxx<type1 >x 6 xxxxxxxxxx{x 7 xxxxxxxxxxxxvalxx:xDouble ;x 8 xxxxxxxxxxxxxx=xa+b;x 9 xxxxxxxxxxxxreturn xx;x 10 xxxxxxxxxx}x 11 xxxxxxxx</type1 >x 12 xxxxxxxx<type2 >x 13 xxxxxxxxxx{a.rank x==xb.rank }{x 14 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 15 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 16 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 17 xxxxxxxxxxxxxx}x 18 xxxxxxxxxxxxxxreturn xx;x 19 xxxxxxxxxx}x 20 xxxxxxxx</type2 >x 21 xxxxxxxx<type3 >x 22 xxxxxxxxxx{x 23 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 24 xxxxxxxxxxxxforx(pxinxb.region ){x 25 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 26 xxxxxxxxxxxx}x 27 xxxxxxxxxxxxreturn xx;x 28 xxxxxxxxxx}x 29 xxxxxxxx</type3 >x 30 xxxxxxxx<type4 >x 31 xxxxxxxxxx{x 32 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 33 xxxxxxxxxxxxforx(pxinxa.region ){x 34 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 35 xxxxxxxxxxxx}x 36 xxxxxxxxxxxxreturn xx;x 37 xxxxxxxxxx}x 38 xxxxxxxx</type4 >x 39 xxxxxxxx<type5 >x 40 xxxxxxxx</type5 >x 41 xxxxxx</array_1 >x 42 xxxxxx<array_2 >x 43 xxxxxxxx<type1 >x 44 xxxxxxxxxx{x 45 xxxxxxxxxxxxvalxx:xDouble ;x 46 xxxxxxxxxxxxxx=xa+b;x 47 xxxxxxxxxxxxreturn xx;x 48 xxxxxxxxxx}x 49 xxxxxxxx</type1 >x 50 xxxxxxxx<type2 >x 51 xxxxxxxxxx{a.rank x==xb.rank }{x 52 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 53 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 54 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 55 xxxxxxxxxxxxxx}x 56 xxxxxxxxxxxxxxreturn xx;x 57 xxxxxxxxxx}x 58 xxxxxxxx</type2 >x 59 xxxxxxxx<type3 >x 60 xxxxxxxxxx{x 61 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 62 xxxxxxxxxxxxforx(pxinxb.region ){x 63 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 64 xxxxxxxxxxxx}x 65 xxxxxxxxxxxxreturn xx;x 66 xxxxxxxxxx}x 67 xxxxxxxx</type3 >x 68 xxxxxxxx<type4 >x 69 xxxxxxxxxx{x 70 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 71 xxxxxxxxxxxxforx(pxinxa.region ){x 72 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 73 xxxxxxxxxxxx}x 74 xxxxxxxxxxxxreturn xx;x 75 xxxxxxxxxx}x 76 xxxxxxxx</type4 >x 77 xxxxxxxx<type5 >x 78 xxxxxxxx</type5 >x 79 xxxxxx</array_2 >x 80 xxxxxx<array_3 >x 81 xxxxxxxx<type1 >x 82 xxxxxxxxxx{x 83 xxxxxxxxxxxxvalxx:xDouble ;x 84 xxxxxxxxxxxxxx=xa+b;x 85 xxxxxxxxxxxxreturn xx;x 86 xxxxxxxxxx}x 87 xxxxxxxx</type1 >x 88 xxxxxxxx<type2 >x 89 xxxxxxxxxx{a.rank x==xb.rank }{x 90 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 91 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 92 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 93 xxxxxxxxxxxxxx}x 94 xxxxxxxxxxxxxxreturn xx;x 95 xxxxxxxxxx}x 96 xxxxxxxx</type2 >x 97 xxxxxxxx<type3 >x 98 xxxxxxxxxx{x 99 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 100 xxxxxxxxxxxxforx(pxinxb.region ){x 101 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 102 xxxxxxxxxxxx}x 103 xxxxxxxxxxxxreturn xx;x 104 xxxxxxxxxx}x 105 xxxxxxxx</type3 >x 106 xxxxxxxx<type4 >x 107 xxxxxxxxxx{x 108 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 109 xxxxxxxxxxxxforx(pxinxa.region ){x 110 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 111 xxxxxxxxxxxx}x 112 xxxxxxxxxxxxreturn xx;x 113 xxxxxxxxxx}x 114 xxxxxxxx</type4 >x 115 xxxxxxxx<type5 >x 116 xxxxxxxx</type5 >x 117 xxxxxx</array_3 >x 118 xxxx</simple_array  >x 119 xxxx<region_array  >x 120 xxxxxxxx<type1 >x 121 xxxxxxxxxx{x 122 xxxxxxxxxxxxvalxx:xDouble ;x 123 xxxxxxxxxxxxxx=xa+b;x 124 xxxxxxxxxxxxreturn xx;x 125 xxxxxxxxxx}x 126 xxxxxxxx</type1 >x 127 xxxxxxxx<type2 >x 128 xxxxxxxxxx{a.rank x==xb.rank }{x 129 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 130 xxxxxxxxxxxxxxforx(pxinxa.region ){x 131 xxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 132 xxxxxxxxxxxx}x 133 xxxxxxxxxxxxreturn xx;x 134 xxxxxxxxxx}x 135 xxxxxx</type2 >x 136 xxxxxx<type3 >x 137 xxxxxxxx{x 138 xxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 139 xxxxxxxxxxforx(pxinxb.region ){x 140 xxxxxxxxxxxxx(p)x=xa+xb(p);x 141 xxxxxxxxxx}x 142 xxxxxxxxxxreturn xx;x 143 xxxxxxxx}x 144 xxxxxx</type3 >x 145 xxxxxx<type4 >x 146 xxxxxxxx{x 147 xxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 148 xxxxxxxxxxforx(pxinxa.region ){x 149 xxxxxxxxxxxxx(p)x=xa(p)+xb;x 150 xxxxxxxxxx}x 151 xxxxxxxxxxreturn xx;x 152 xxxxxxxx}x 153 xxxxxx</type4 >x 154 xxxxxxxx<type5 >x 155 xxxxxxxx</type5 >x 156 xxxx</region_array  >x 157 xx</real >x 158 xx<complex >x 159 xxxx<simple_array  >x 160 xxxxxx<array_1 >x 161 xxxxxxxxx<type1 >x 162 xxxxxxxxxx{x 163 xxxxxxxxxxxxvalxx:xDouble ;x 164 xxxxxxxxxxxxxx=xa+b;x 165 xxxxxxxxxxxxreturn xx;x 166 xxxxxxxxxx}x 167 xxxxxxxx</type1 >x 168 xxxxxxxx<type2 >x 169 xxxxxxxxxx{a.rank x==xb.rank }{x 170 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 171 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 172 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 173 xxxxxxxxxxxxxx}x 174 xxxxxxxxxxxxxxreturn xx;x 175 xxxxxxxxxx}x 176 xxxxxxxx</type2 >x 177 xxxxxxxx<type3 >x 178 xxxxxxxxxx{x 179 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 180 xxxxxxxxxxxxforx(pxinxb.region ){x 181 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 182 xxxxxxxxxxxx}x 183 xxxxxxxxxxxxreturn xx;x 184 xxxxxxxxxx}x 185 xxxxxxxx</type3 >x 186 xxxxxxxx<type4 >x 187 xxxxxxxxxx{x 188 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 189 xxxxxxxxxxxxforx(pxinxa.region ){x 190 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 191 xxxxxxxxxxxx}x 192 xxxxxxxxxxxxreturn xx;x 193 xxxxxxxxxx}x 194 xxxxxxxx</type4 >x 195 xxxxxxxx<type5 >x 196 xxxxxxxx</type5 >x 197 xxxxxx</array_1 >x 198 xxxxxx<array_2 >x 199 xxxxxxxx<type1 >x 200 xxxxxxxxxx{x 201 xxxxxxxxxxxxvalxx:xDouble ;x 202 xxxxxxxxxxxxxx=xa+b;x 203 xxxxxxxxxxxxreturn xx;x 204 xxxxxxxxxx}x 205 xxxxxxxx</type1 >x 206 xxxxxxxx<type2 >x 207 xxxxxxxxxx{a.rank x==xb.rank }{x 208 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 209 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 210 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 211 xxxxxxxxxxxxxx}x 212 xxxxxxxxxxxxxxreturn xx;x 213 xxxxxxxxxx}x 214 xxxxxxxx</type2 >x 215 xxxxxxxx<type3 >x 216 xxxxxxxxxx{x 217 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 218 xxxxxxxxxxxxforx(pxinxb.region ){x 219 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 220 xxxxxxxxxxxx}x 221 xxxxxxxxxxxxreturn xx;x 222 xxxxxxxxxx}x 223 xxxxxxxx</type3 >x 224 xxxxxxxx<type4 >x 225 xxxxxxxxxx{x 226 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 227 xxxxxxxxxxxxforx(pxinxa.region ){x 228 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 229 xxxxxxxxxxxx}x 230 xxxxxxxxxxxxreturn xx;x 231 xxxxxxxxxx}x 232 xxxxxxxx</type4 >x 233 xxxxxxxx<type5 >x 234 xxxxxxxx</type5 >x 235 xxxxxx</array_2 >x 236 xxxxxx<array_3 >x 237 xxxxxxxx<type1 >x 238 xxxxxxxxxx{x 239 xxxxxxxxxxxxvalxx:xDouble ;x 240 xxxxxxxxxxxxxx=xa+b;x 241 xxxxxxxxxxxxreturn xx;x 242 xxxxxxxxxx}x 243 xxxxxxxx</type1 >x 244 xxxxxxxx<type2 >x 245 xxxxxxxxxx{a.rank x==xb.rank }{x 246 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 247 xxxxxxxxxxxxxxforx(pxinxa.indices ()){x 248 xxxxxxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 249 xxxxxxxxxxxxxx}x 250 xxxxxxxxxxxxxxreturn xx;x 251 xxxxxxxxxx}x 252 xxxxxxxx</type2 >x 253 xxxxxxxx<type3 >x 254 xxxxxxxxxx{x 255 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 256 xxxxxxxxxxxxforx(pxinxb.region ){x 257 xxxxxxxxxxxxxxx(p)x=xa+xb(p);x 258 xxxxxxxxxxxx}x 259 xxxxxxxxxxxxreturn xx;x 260 xxxxxxxxxx}x 261 xxxxxxxx</type3 >x 262 xxxxxxxx<type4 >x 263 xxxxxxxxxx{x 264 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 265 xxxxxxxxxxxxforx(pxinxa.region ){x 266 xxxxxxxxxxxxxxx(p)x=xa(p)+xb;x 267 xxxxxxxxxxxx}x 268 xxxxxxxxxxxxreturn xx;x 269 xxxxxxxxxx}x 270 xxxxxxxx</type4 >x 271 xxxxxxxx<type5 >x 272 xxxxxxxx</type5 >x 273 xxxxxx</array_3 >x 274 xxxx</simple_array  >x 275 xxxx<region_array  >x 276 xxxxxxxx<type1 >x 277 xxxxxxxxxx{x 278 xxxxxxxxxxxxvalxx:xDouble ;x 279 xxxxxxxxxxxxxx=xa+b;x 280 xxxxxxxxxxxxreturn xx;x 281 xxxxxxxxxx}x 282 xxxxxxxx</type1 >x 283 xxxxxxxx<type2 >x 284 xxxxxxxxxx{a.rank x==xb.rank }{x 285 xxxxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 286 xxxxxxxxxxxxxxforx(pxinxa.region ){x 287 xxxxxxxxxxxxx(p)x=xa(p)+xb(p);x 288 xxxxxxxxxxxx}x 289 xxxxxxxxxxxxreturn xx;x 290 xxxxxxxxxx}x 291 xxxxxx</type2 >x 292 xxxxxx<type3 >x 293 xxxxxxxx{x 294 xxxxxxxxxxvalxxx=xnewxArray [Double ](b.region );x 295 xxxxxxxxxxforx(pxinxb.region ){x 296 xxxxxxxxxxxxx(p)x=xa+xb(p);x 297 xxxxxxxxxx}x 298 xxxxxxxxxxreturn xx;x 299 xxxxxxxx}x 300 xxxxxx</type3 >x 301 xxxxxx<type4 >x 302 xxxxxxxx{x 303 xxxxxxxxxxvalxxx=xnewxArray [Double ](a.region );x 304 xxxxxxxxxxforx(pxinxa.region ){x 305 xxxxxxxxxxxxx(p)x=xa(p)+xb;x 306 xxxxxxxxxx}x 307 xxxxxxxxxxreturn xx;x 308 xxxxxxxx}x 309 xxxxxx</type4 >x 310 xxxxxxxx<type5 >x 311 xxxxxxxx</type5 >x 312 xxxx</region_array  >x 313 xx</complex >x 314 </plus >

AppendixxB MiX10 IR Grammar

Listing below gives the JastAdd implementation of the MiX10 IR grammar.

1 Program x::=xClassBlock ;x 2 PPHelper ;x 3 ClassBlock x::=xDeclStmt :Stmt *xMethod *x<UseNewArray  :Boolean >;x 4 abstract xStmt ;x 5 CommentStmt  :Stmt x::=x<Comment :String >;x 6 BreakStmt :Stmt ;x 7 ContinueStmt  :Stmt ;x 8 DeclStmt :Stmt x::=x[MultiDeclLHS  ]xLHS:IDInfo x[RHS:Exp]x 9 <Mutable :Boolean >x<Atomic :Boolean >;x 10 Literally :Stmt x::=x<Verbatim :String >;x 11 LiterallyExp  :Expx::=x<Verbatim :String >;x 12 BlockEnd :Literally ;x 13 PointLooper  :Stmt x::=xPointID :IDUse xArrayID :IDUse x 14 xx<DimNumber :int>x[Min:Exp]x[Max:Exp];x 15 Method x::=xMethodHeader  xMethodBlock  ;x 16 MethodHeader  x::=xReturnType :AccessVal x<Name :String >x 17 xxArgs :IDInfo *;x 18 ReturnStmt :Stmt x::=xReturnVal :Exp*;x 19 Type :AccessVal x::=x<Name :String >;x 20 MethodBlock  :StmtBlock ;x 21 AssignStmt :Stmt x::=xx[MultiAssignLHS  ]xLHS:IDInfo xRHS:Expx 22 xx<TypeCast :Boolean >x<Atomic :Boolean >;x 23 ExpStmt :Stmt x::=xExp;x 24 IDUse :Expx::=x<ID:String >;x 25 Dims x::=x[Exp];x 26 IDInfo :Expx::=xType x<Name :String >x<Shape :ArrayList >x 27 xx<didShapeChange  :Boolean >x<isComplex :String >xValue :Exp;x 28 MultiDeclLHS  :Expx::=xxIDInfo *x;x 29 MultiAssignLHS  :Expx::=xxIDInfo *x;x 30 abstract xUnaryExp :Expx::=xOperand :Exp;x 31 PreIncExp :UnaryExp ;x 32 PreDecExp :UnaryExp ;x 33 MinusExp :UnaryExp ;x 34 PlusExp :UnaryExp ;x 35 NegExp :UnaryExp ;x 36 EmptyExp :Exp;x 37 RegionBuilder  :Expx::=xLower :IDUse *xUpper :IDUse *x 38 xxArrayID :IDUse ;x 39 SimpleArrayExp  :Expx::=xValues :Exp*xPoint *xType ;x 40 Point :Expx::=xCoOrd :IntLiteral *x;x 41 ArrayAccess  :AccessVal x::=xArrayID :IDUse xIndices :Exp*x 42 xx<IsColVector  :Boolean >;x 43 ArraySetStmt  :Stmt x::=xLHS:IDInfo xIndices :Exp*xRHS:Exp;x 44 SubArraySetStmt  :Stmt x::=xLHS:IDInfo xLower :Exp*xUpper :Exp*x 45 xxRHS:Exp;x 46 SubArrayGetExp  :Expx::=xLower :Exp*xUpper :Exp*xArrayID :IDUse ;x 47 abstract xLiteralExp :Exp;x 48 Literal :LiteralExp x::=x<Literal :String >;x 49 StringLiteral  :Literal ;x 50 FPLiteral :Literal ;x 51 DoubleLiteral  :Literal ;x 52 IntLiteral :Literal ;x 53 BoolLiteral  :Literal ;x 54 LongLiteral  :Literal ;x 55 CharLiteral  :Literal ;x 56 abstract xBinaryExp :Expx::=xLeftOp :ExpxRightOp :Exp;x 57 abstract xArithExp :BinaryExp ;x 58 abstract xMultiplicativeExp  :ArithExp ;x 59 MulExp :MultiplicativeExp  ;x 60 DivExp :MultiplicativeExp  ;x 61 ModExp :MultiplicativeExp  ;x 62 abstract xAdditiveExp  :BinaryExp ;x 63 AddExp :AdditiveExp  ;x 64 SubExp :AdditiveExp  ;x 65 IncExp :AdditiveExp  ;x 66 DecExp :AdditiveExp  ;x 67 abstract xRelationalExp  :BinaryExp ;x 68 LTExp x:xRelationalExp  x;x 69 GTExp x:xRelationalExp  x;x 70 LEExp x:xRelationalExp  x;x 71 GEExp x:xRelationalExp  x;x 72 abstract xEqualityExp  x:xRelationalExp  ;x 73 EQExp x:xEqualityExp  x;x 74 NEExp x:xEqualityExp  x;x 75 abstract xLogicalExp :BinaryExp ;x 76 AndExp :LogicalExp ;x 77 OrExp :LogicalExp ;x 78 Modifiers x::=xModifier *;x 79 Modifier x::=x<ID:String >;x 80 Identifier :AccessVal x::=x<Name :String >;x 81 ForStmt :Stmt x::=x<isParfor :Boolean >xAssignStmt xCondition :Expx 82 xxStepper :AdditiveExp  xLoopBody xLower :IDUse xUpper :IDUse x 83 xxIncr :IDUse ;x 84 WhileStmt :Stmt x::=xCondition :ExpxLoopBody ;x 85 StmtBlock :Stmt x::=xStmt *;x 86 LoopBody :StmtBlock ;x 87 IfElseStmt :Stmt x::=xIfElseIf *x[ElseBody ];x 88 IfElseIf :Stmt x::=xCondition :ExpxIfBody ;x 89 IfBody :StmtBlock ;x 90 ElseBody :StmtBlock ;x 91 abstract xExp;x 92 AtStmt :Stmt x::=xPlace :ExpxAtBlock ;x 93 AtBlock :StmtBlock ;x 94 AsyncStmt :Stmt x::=xAsyncBlock ;x 95 AsyncBlock :StmtBlock ;x 96 FinishStmt :Stmt x::=xFinishBlock  ;x 97 FinishBlock  :StmtBlock ;x 98 AtomicStmt :Stmt x::=xAtomicBlock  ;x 99 AtomicBlock  :StmtBlock ;x 100 WhenStmt :Stmt x::=xCondition :ExpxWhenBlock ;x 101 WhenBlock :StmtBlock ;x 102 abstract xAccessVal :Exp;x 103 abstract xMethodCall :Exp;x 104 BuiltinMethodCall  :MethodCall x::=xBuiltinMethodName  :MethodId x 105 xxArgument :Exp*;x 106 MethodId :AccessVal x::=x<Name :String >;x 107 UserDefMethodCall  :MethodCall x::=xUserDefMethodName  :MethodId x 108 xxArgument :Exp*;