Cristian Ramon-Cortes
email: cristian.ramoncortes@bsc.es

Ramon Amela
email: ramon.amela@bsc.es

Jorge Ejarque
email: jorge.ejarque@bsc.es

Philippe Clauss
email: philippe.clauss@inria.fr

Rosa M Badia
email: rosa.m.badia@bsc.es

AutoParallel: A Python module for automatic parallelization and distributed execution of affine loop nests

 due to the simplicity of its syntax, while still achieving a good performance even being an interpreted language. Moreover, the community has helped to develop a large number of libraries and modules, tuning the most commonly used to obtain great performance.

However, there is still room for improvement when preventing users from dealing directly with distributed and parallel computing issues. This paper proposes and evaluates AutoParallel, a Python module to automatically find an appropriate task-based parallelization of affine loop nests to execute them in parallel in a distributed computing infrastructure. This parallelization can also include the building of data blocks to increase task granularity in order to achieve a good execution performance. Moreover, AutoParallel is based on sequential programming and only contains a small annotation in the form of a Python decorator so that anyone with little programming skills can scale up an application to hundreds of cores.

Introduction

Computer simulations have become more and more crucial to both theoretical and experimental studies in many different fields, such as structural mechanics, chemistry, biology, genetics, and even sociology. Several years ago, small simulations (with up to several cores or even several nodes within the same grid) were enough to fulfill the scientific community requirements and thus, the experts of each field were capable of programming and running them. However, nowadays, simulations requiring hundreds or thousands of cores are widely used and, to this point, efficiently programming them becomes a challenge even for computer scientists. On the one hand, interdisciplinary teams have become popular, with field experts and computer scientists joining their forces together to keep their research at the forefront. On the other hand, programming languages have made a considerable effort to ease the programmability while maintaining acceptable performance. In this sense, Python [START_REF] Van Rossum | Python language reference manual[END_REF] has risen to the top language for nonexperts [START_REF] Cass | The 2017 Top Programming Languages (IEEE Spectrum)[END_REF], being easy to program while maintaining good performance trade-off and having a large number of third-party libraries available. Similarly, Go [START_REF]The Go Programming Language[END_REF] has also gained some momentum thanks to its portability, reliability, and ease of concurrent programming, although it is still in its early stages.

Even if some great efforts have been accomplished for programming frameworks to ease the development of distributed applications, we go one step further with Au-toParallel: a Python module to automatically parallelize applications and execute them in distributed environments. Our philosophy is to ease the development of parallel and distributed applications so that anyone with little programming skills can scale up an application to hundreds of cores. In this sense, AutoParallel is based on sequential programming and only includes a small annotation in the form of a Python decorator. It relies on PLUTO [START_REF] Bondhugula | Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model[END_REF] to parallelize affine loop nests and taskifies the obtained code so that PyCOMPSs can distributedly execute it using any underlying infrastructure (clusters, clouds, and containers). Moreover, to avoid single instruction tasks, AutoParallel also includes an optional feature to increase the tasks' granularity by automatically building data blocks from PLUTO tiles.

The rest of the paper is organized as follows. Section 2 describes the state of the art. Section 3 presents PyCOMPSs and PLUTO. Next, Section 4 describes the architecture of AutoParallel and Section 5 presents its performance results. Finally, Section 6 concludes the paper and gives some guidelines for future work.

State of the Art

Nowadays simulations are run in distributed environments and, although Python has become a reference programming language, there is still much work to do to ease parallel and distributed computing issues. In this concern, Python can provide parallelism at three levels. First, parallelism can be achieved internally through many libraries such as NumPy [START_REF] Walt | The NumPy Array: A Structure for Efficient Numerical Computation[END_REF] and SciPy [START_REF] Jones | SciPy: Open source scientific tools for Python[END_REF], which offer vectorized data structures and numerical routines that automatically map operations on vectors and matrices to the BLAS [START_REF]BLAS (Basic Linear Algebra Subprograms)[END_REF] and LAPACK [START_REF] Anderson | LAPACK Users' guide[END_REF] functions; executing the multi-threaded BLAS version (using OpenMP [START_REF] Dagum | OpenMP: An Industry-Standard API for Shared-Memory Programming[END_REF] or TBB [START_REF]Threading Building Blocks (Intel®TBB)[END_REF]) when present in the system. Notice that, although parallelism is completely transparent for the application user, parallel libraries only benefit from intra-node parallelism and cannot run across different nodes.

Secondly, many modules can explicitly provide parallelism. The multiprocessing module provides [START_REF]Parallel Processing and Multiprocessing in Python[END_REF] support for the spawning of processes in SMP machines using an API similar to the threading module, with explicit calls for creating processes. In addition, the Parallel Python (PP) module [START_REF]Parallel Python Software[END_REF] provides mechanisms for parallel execution of Python codes, with an API that includes specific functions for specifying the number of workers to be used, submitting the jobs for execution, getting the results from the workers, etc. Also, the mpi4py [START_REF] Dalcn | MPI for Python[END_REF] library provides a binding of MPI for Python which allows the programmer to handle parallelism both inter-node and intra-node. However, in all cases, the burden of parallelism specific issues is assigned to the programmer.

Finally, other libraries and frameworks enable Python distributed and multi-threaded computations such as Dask [START_REF]Dask: Library for dynamic task scheduling[END_REF], PySpark [START_REF]PySpark[END_REF], and PyCOMPSs [START_REF] Amela | Enabling Python to Execute Efficiently in Heterogeneous Distributed Infrastructures with PyCOMPSs[END_REF], [START_REF]Executing linear algebra kernels in heterogeneous distributed infrastructures with PyCOMPSs[END_REF]. Dask is a native Python library that allows both the creation of custom DAG's and the distributed execution of a set of operations on NumPy and pandas [START_REF] Mckinney | Pandas: a Foundational Python Library for Data Analysis and Statistics[END_REF] objects. PySpark is a binding to the widely extended framework Spark [START_REF] Zaharia | Spark: Cluster Computing with Working Sets[END_REF]. Py-COMPSs is a task-based programming model that offers an interface on Python that follows the sequential paradigm. It enables the parallel execution of tasks by means of building, at execution time, a data dependency graph for the tasks that compose an application. The syntax of PyCOMPSs is minimal, using decorators to enable the programmer to identify methods as tasks and a small API for synchronization. PyCOMPSs relies on a runtime that can exploit the inherent parallelism at task level and execute the application using a distributed parallel platform (clusters, clouds, and containers).

Technical Background

This section provides a general overview of the satellite frameworks that directly interact with the AutoParallel module: PyCOMPSs and PLUTO. It also highlights some of their features that are crucial for their integration.

PyCOMPSs

COMPSs [START_REF] Badia | COMP superscalar, an interoperable programming framework[END_REF], [START_REF] Lordan | ServiceSs: an interoperable programming framework for the Cloud[END_REF] is a task-based programming model that aims to ease the development of parallel applications, targeting distributed computing platforms. It relies on its runtime to exploit the inherent parallelism of the application at execution time by detecting the task calls and the data dependencies between them.

The COMPSs runtime natively supports Java applications but also provides bindings for Python and C/C++. Precisely, the Python binding is known as PyCOMPSs. All the bindings are supported through a binding-commons layer which focuses on enabling the functionalities of the runtime to other languages. It is written in C and has been designed as an API with a set of defined functions to communicate with the runtime through the JNI [START_REF] Liang | Java Native Interface: Programmer's Guide and Reference[END_REF].

As shown in Figure 1, the COMPSs runtime allows applications to be executed on top of different infrastructures (such as multi-core machines, grids, clouds or containers [START_REF] Ramon-Cortes | Transparent Orchestration of Task-based Parallel Applications in Containers Platforms[END_REF]) without modifying a single line of the application code. Thanks to the different connectors, the runtime is capable of handling all the underlying infrastructure so that the user only defines the tasks. It also provides faulttolerant mechanisms for partial failures (with job resubmission and reschedule when tasks or resources fail), has a live monitoring tool through a built-in web interface, supports instrumentation using the Extrae [START_REF]Extrae Tool[END_REF] tool to generate postmortem traces that can be analyzed with Paraver [START_REF]Paraver Tool[END_REF], has an Eclipse IDE, and has pluggable cloud connectors and task schedulers. Additionally, the programming model is based on sequential programming which means that users do not need to deal with any parallelization and distribution issue such as thread creation, synchronization, data distribution, messaging or fault-tolerance. Instead, application developers only select which methods must be considered as tasks, and the runtime spawns them asynchronously on a set of resources instead of executing them locally and sequentially.

PyCOMPSs Programming Model.

Regarding programmability, tasks are identified by inserting annotations in the form of Python decorators. These annotations are inserted at method level and indicate that invocations to a given method should become tasks at execution time. The @task decorator also contains information about the directionality of the method parameters specifying if a given parameter is read (IN), written (OUT) or both read and written in the method (INOUT). Figure 2 shows an example of a task annotation. The parameter c has direction INOUT, and parameters a and b are set to the default direction IN. The directionality tags are used at execution time to derive the data dependencies between tasks and are applied at an object level, taking into account its references to identify when two tasks access the same object.

Additionally to the @task decorator, the @constraint decorator can be optionally defined to indicate some task hardware or software requirements. Continuing with the previous example, the task constraint ComputingUnits tells the runtime how many CPUs are consumed by each task execution. The available resources are defined by the system administrator in a separated XML configuration file. Other constraints that can be defined refer to the processor architecture, memory size, disk storage, operating system or available libraries. A tiny synchronization API completes the PyCOMPSs syntax. As shown in Figure 3, the API function compss_wait_on waits for the completion of all the tasks modifying the result's value and brings the final value to the node executing the main program. Then, the execution of the main program is resumed. Given that PyCOMPSs is used mostly in distributed environments, synchronization implies a data transfer from remote storage or memory space to the node executing the main program.

for block in data: partial_res = wordcount_task(block) reduce_task(result, partial_res) final_result = compss_wait_on(result)

PLUTO

Many compute-intensive scientific applications spend most of their execution time running nested loops. The Polyhedral Model [START_REF] Cohen | Facilitating the Search for Compositions of Program Transformations[END_REF] provides a powerful mathematical abstraction to analyze and transform loop nests in which the data access functions and loop bounds are affine combinations (linear combinations with a constant) of the enclosing loop iterators and parameters. As shown in Figure 4, this model represents the instances of the loop nests' statements as integer points inside a polyhedron, where inter and intrastatement dependencies are characterized as a dependency polyhedron. Combining this representation with Linear Algebra and Integer Linear Programming, it is possible to reason about the correctness of a sequence of complex optimizing and parallelizing loop transformations. PLUTO [START_REF] Bondhugula | Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model[END_REF], [START_REF]Pluto[END_REF] is an automatic parallelization tool based on the Polyhedral model to optimize arbitrarily nested loop sequences with affine dependencies. At compile time, it analyses C source code to optimize and parallelize affine loop-nests and automatically generate OpenMP C parallel code for multi-cores. Although the tool is fully automatic, many options are available to tune tile sizes, unroll factors, and outer loop fusion structure.

Figure 5. Pluto source-to-source transformation. Source: [START_REF] Bondhugula | A Practical Automatic Polyhedral Parallelizer and Locality Optimizer[END_REF] As shown in Figure 5, PLUTO internally translates the source code to an intermediate OpenScop [START_REF] Bastoul | OpenScop: A Specification and a Library for Data Exchange in Polyhedral Compilation Tools[END_REF] representation using CLAN [START_REF] Bastoul | Putting Polyhedral Loop Transformations to Work[END_REF]. Next, it relies on the Polyhedral Model to find affine transformations for coarse-grained parallelism, data locality, and efficient tiling. Finally, PLUTO generates the OpenMP C code from the OpenScop representation using CLooG [START_REF] Bastoul | Code Generation in the Polyhedral Model Is Easier Than You Think[END_REF]. We must highlight that the generated code is also optimized for data locality and made amenable to auto-vectorization.

Loop Tiling.

Among many other options, PLUTO can tile code by specifying the --tile option. In general terms, as shown in Figure 6, tiling a loop of given size N results in a division of the loop in N/T repeatable parts of size T. For instance, this is suitable when fitting loops into the L1 or L2 caches or, in the context of this paper, when building the data blocks to increase the tasks' granularity.

# Original loop # Tiled loop for i in range(N):

for i in range(N/T): print(i) for t in range(T): print(i * T + t) Along with this option, users can let PLUTO set the tile sizes automatically using a rough heuristic, or manually define them in a tile.sizes file. This file must contain one tile size on each line and as many tile sizes as the loop nest depth.

In the context of parallel applications, tile sizes must be fine-tuned for each application so that they maximize locality while making sure there are enough tiles to keep all cores busy.

Architecture

The framework proposed in this paper eases the development of distributed applications by letting users program their application in a standard sequential fashion. It is developed on top of PyCOMPSs and PLUTO. When automatically parallelizing sequential applications, users must only insert an annotation on top of the potentially parallel functions to activate the AutoParallel module. Next, the application can be launched using PyCOMPSs.

@P A R A L L E L() DECORATOR
Following the same approach than PyCOMPSs, we have included a new decorator @parallel() to specify which methods should be automatically parallelized at runtime. Notice that functions using this decorator must contain affine loops so that the module can propose a parallelization. Otherwise, the source code will remain intact. Table 1 shows the valid flags for the decorator.

As shown in Figure 7, the AutoParallel Module analyzes the user code searching for @parallel() annotations. Essentially, when found, the module calls PLUTO to generate its parallelization and substitutes the user code by a newly generated code. Once all annotations have been processed, the new tasks are registered into PyCOMPSs, and the execution continues as a regular PyCOMPSs application (as described in Section 3.1). Finally, when the application has ended, the generated code is stored in a (_autogen.py) file and the user code is restored.

AutoParallel Module

Next, we describe the five components of the AutoParallel module. For the sake of clarity, Figure 8 shows the relationship between all the components and its expected inputs and outputs. • Parallelizer Returns the Python code resulting from parallelizing an OpenScop file. Since Python does not have any standard regarding parallel annotations, the parallel loops are annotated using comments with OpenMP syntax.

• Python to PyCOMPSs Translator Converts an annotated Python code into a PyCOMPSs application by inserting the necessary task annotations and data synchronizations. This component also performs loop taskification if it is enabled (see Section 4.2 for more details).

• Code Replacer Replaces each loop nest in the initial user code by the auto-generated code so that PyCOMPSs can execute the code in a distributed computing platform. When the application has finished, it restores the user code and saves the autogenerated code in a separated file.

For instance, Figure 9 shows the relevant parts of an Embarrassingly Parallel application with the main function annotated with the @parallel() decorator that contains two nested loops.

# Main F u n c t i o n from pycompss . a p i . p a r a l l e l i m p o r t p a r a l l e l @ p a r a l l e l ( ) d e f ep ( mat , n s i z e , m size , c1 , c2 ) :

f o r i i n r a n g e ( n s i z e ) : f o r j i n r a n g e ( m s i z e ) :

mat [ i ] [ j ] = compute ( mat [ i ] [ j ] , c1 , c2 )
# MAIN i f name == " main " : # P a r s e a r g u m e n t s . . . # I n i t i a l i z e m a t r i c e s MAT = i n i t i a l i z e m a t r i x ( NSIZE , MSIZE ) # B e g i n c o m p u t a t i o n ep (MAT, NSIZE , MSIZE , COEF1 , COEF2 ) In addition, Figure 10 shows its parallelization. Notice that the source code contains two nested loops with a single inner statement. It contains a task definition (with its data dependencies) that matches the original loop statement, a new main loop nest proposed by PLUTO (which exploits the inherent parallelism available in the original code), and a final barrier used as synchronization point.

Loop Taskification

Many compute-intensive scientific applications are not designed as block computations, and thus, the tasks proposed by the AutoParallel module are single statements. Although this can be harmless in tiny parallel environments, it leads to poor performances when executed using large distributed environments since the tasks' granularity is not large enough to surpass the overhead of transferring the task definition, and the input and output data. To face this issue, we have extended the Python to PyCOMPSs Translator with support for loop taskification.

Essentially, loop taskification means processing the parallel code and converting into tasks all the loops of a certain depth of the loop nest. Since tasks may use N-dimensional arrays, this also implies to create the necessary data blocks (chunks) for each callee and revert them after the task execution. Continuing with the previous example, Figure 11 shows its parallelization with loop taskification. Notice that the generated code with loop taskification is significantly more complex. The code defines a task containing the inner-most loop of the original code' statements (only one in this case) and all its data dependencies accordingly. The main loop is also modified by chunking the necessary data for the task execution, flattening the data as a single dimension list, calling the task, rebuilding the chunks after the task callee, and re-assigning the values to the original variables. Notice that this last assignment is performed by pre-calculating the number of expected parameters and using PyCOMPSs Future Objects to avoid any synchronization in the master code (objects are only synchronized and transferred when required by a task execution). The end of the main code also includes a barrier as a synchronization point.

However, taskification may annihilate all the potential parallelism of the application (for instance, by setting taskify_loop_level=2 in the previous example). To prevent this, we have integrated PLUTO's tiling transformation so that the loop taskification can be achieved on tiles.

Python Extension for CLooG

As described in Section 3.2, PLUTO operates internally with the OpenScop format. It relies on CLAN to translate input code from C/C++ or Fortran to OpenScop, and on CLooG to translate output code from OpenScop to C/C++ or Fortran.

Since we are targeting Python code, a translation from Python to OpenScop is required before calling PLUTO, and another translation from OpenScop to Python is required at the end. For the input, we have chosen to manually translate the code using the Python To OpenScop Translator component since CLAN is not adapted for supporting other language and PLUTO may take OpenScop format as input. We have extended CLooG so that the written output code is directly in Python: the language options were extended, and the Pretty Printer was modified in order to translate every OpenScop statement in its equivalent Python format. Since Python does not have any standard regarding parallel annotations, the parallel loops are annotated with comments in OpenMP syntax.

Experimentation

Computing Infrastructure

Results presented in this section have been obtained using the MareNostrum IV Supercomputer located at the Barcelona Supercomputing Center (BSC).

We have used PyCOMPSs version 2.3.rc1807 (available at [START_REF]COMPSs GitHub[END_REF]), PLUTO version 0.11.4, CLooG version 0.19.0, and AutoParallel version 0.2 (available at [START_REF]PyCOMPSs AutoParallel Module GitHub[END_REF]). We have also used Intel®Python 2.7.13, Intel®MKL 2017, Java OpenJDK 8 131, GCC 7.2.0, and Boost 1.64.0.

All the benchmark codes used for this experimentation are also available at [START_REF]Experimentation GitHub[END_REF].

MareNostrum IV. The MareNostrum IV begun operating at the end of June 2017. Its current peak performance is 11.15 Petaflops, ten times more than its previous version, MareNostrum III. The supercomputer is composed by 3456 nodes, each of them with two Intel® Xeon Platinum 8160 (24 cores at 2,1 GHz each). It has 384.75 TB of main memory, 100Gb Intel®Omni-Path Full-Fat Tree Interconnection, and 14 PB of disk storage [START_REF]MareNostrum IV Technical Information[END_REF].

Blocked Applications

The first set of experiments has been designed to compare the application's code automatically generated by the AutoParallel module (autoparallel version) against the one written by a PyCOMPSs user (userparallel version). To this end, we have and QR decompositions described and analyzed in our previous work [START_REF] Amela | Enabling Python to Execute Efficiently in Heterogeneous Distributed Infrastructures with PyCOMPSs[END_REF].

In general terms, the matrices are chunked in smaller square matrices (known as blocks) to distribute the data easily among the available resources so that the square blocks are the minimum entity to work with [START_REF] Gunnels | FLAME: Formal Linear Algebra Methods Environment[END_REF]. Furthermore, the initialization is performed in a distributed way, defining tasks to initialize the matrix blocks. These tasks do not take into account the nature of the algorithm, and they are scheduled in a round robin manner. Next, all the computations are performed considering that the data is already located on a given node.

Given a fixed matrix size, increasing the number of blocks increases the maximum parallelism of the application since blocks are the tasks' minimum work entities. On the other hand, increasing the block size increases the tasks' computational load which, at some point, will surpass the serialization and transfer overheads. Hence, the number of blocks and the block size for each application are a trade-off to fill all the available cores while maintaining acceptable performance.

Next subsections analyze each application in depth, with a figure showing the execution results that contains two plots. For both plots, the horizontal axis shows the number of worker nodes (with 48 cores each) used for each execution, the blue color is the userparallel version and the green color is the autoparallel. The top plot represents the mean, maximum, and minimum execution times over 10 runs and the bottom plot represents the speed-up of each version with respect to the userparallel version running with a single worker.

Cholesky.

The Cholesky factorization can be applied to Hermitian positive-defined matrices. This decomposition is a particular case of the LU factorization, obtaining two matrices of the form U = L t . Our version of this application applies the right-looking algorithm [START_REF] Bientinesi | Families of Algorithms Related to the Inversion of a Symmetric Positive Definite Matrix[END_REF] because it is more aggressive, meaning that in an early stage of the computation there are blocks of the solution that are already computed and all the potential parallelism is released as soon as possible.

Table 2 analyses the userparallel and autoparallel versions in terms of code complexity, loop configuration, and number of different task types. The code complexity is measured using the Babelfish Tools [START_REF]Babelfish Tools[END_REF] and includes lines of code, cyclomatic complexity, and n-path. Although the generated code is not much larger than the original one, it is significantly more complex in terms of cyclomatic complexity and n-path. This is because the PLUTO call inside the AutoParallel module has exploits better the application parallelism. Notice that, although the autoparallel version has three 3-depth loop nests instead of a single loop nest with four loops, the maximum loop depth remains the same (three). Furthermore, regarding the amount of task calls, userparallel version includes three tasks (potrf, solve_triangular, and gemm), while the autoparallel version includes four tasks (that map to the previous operations plus an additional one to generate blocks initialized to zero). 12 shows the execution results of the Cholesky decomposition over a dense matrix of 65536 × 65536 elements decomposed in 32 × 32 blocks with 2048 × 2048 elements each. As explained at the beginning of this section, we have chosen 32 blocks because it is the minimum amount providing enough parallelism for 192 cores, and a bigger block size (e.g., 4096×4096) was impossible due to memory constraints. The speed-up of both versions is limited by the block-size due to the small task granularity, reaching 2 when using 4 workers. Although the userparallel version spawns 6512 tasks and the autoparallel version spawns 7008 tasks, the execution times and the overall performance of both versions are almost the same. This is due to the fact that the autoparallel version spawns an extra task per iteration to initialize blocks to zero on the matrix's lower triangle that has no impact in the overall computation time. For the LU decomposition, an approach without pivoting [START_REF] Golub | Matrix Computations[END_REF] has been the starting point. However, since this approach might be unstable in general [START_REF] Demmel | Stability of Block Algorithms with Fast Level-3 BLAS[END_REF], some modifications have been included to increase the stability of the algorithm while keeping the block division and avoiding bringing an entire column into a single node.

As shown in Table 3, both versions have two main loops with a maximum depth of three and a total of six nested loops. However, the autoparallel version has 315% more paths in the flow than the userparallel because it has different optimization codes for different variable values. Regarding the task types, on the one hand, the userparallel version contains calls to four different tasks: multiply, invert_triangular, dgemm, and custom_lu. On the other hand, the autoparallel version generates twelve different task types because it generates one task type per statement in the original loop, even if the statement contains the same task call. For instance, the original LU contains four calls to the invert_triangular function that are detected as different statements and converted to different tasks. Regarding the number of tasks, the userparallel version spawns 14676 tasks while the autoparallel version spawns 15227 tasks. This difference is due to the fact that the autoparallel version initializes distributedly an intermediate zero matrix, while the userparallel initializes it in the master memory. Figure 14 shows a detailed paraver trace of both versions running with 4 workers (192 cores). The autoparallel version (right) is more coloured because, as previously explained, it has more tasks although, in the end, they execute the same function. Notice that the performance degradation of the autoparallel version is due to the fact that the maximum parallelism is lost before the end of the execution. Unlike traditional QR algorithms that use the Householder transformation, our implementation uses a method based on Givens rotations [START_REF] Quintana-Orti | Scheduling of QR Factorization Algorithms on SMP and Multi-Core Architectures[END_REF]. This way, data can be accessed by blocks instead of columns.

The QR decomposition represents one of the most complex use cases in terms of data dependencies thus, having a high base cyclomatic complexity. As shown in Table 4, the generated code differs significantly in terms of loop configurations but not regarding code since the autoparallel version has similar cyclomatic complexity, 34% more lines of code, and 51% more paths. Although the maximum loop depth remains the same, the auto-generated code has two main loops instead of one. Regarding the task types, while the userparallel version has four tasks (namely qr, dot, little_qr, and multiply_single_block), the autoparallel version has twenty different task types. 15 shows the execution results of the QR decomposition with a 32768 × 32768 matrix of 16 × 16 blocks with 2048 × 2048 elements each. The autoparallel version spawns 26304 tasks and the userparallel version spawns 19984 tasks. As in the previous examples, the overall performance is limited by the block size. However, the userparallel version slightly outperforms the autoparallel version; achieving a 2.37 speed-up with 4 workers instead of 2.10. The difference is mainly because the autoparallel version spawns four copy tasks per iteration (copy_reference), while the userparallel version executes this code in the master side copying only the reference of a future object.

Fine-grain Applications

The second set of experiments is designed to evaluate the capability of generating distributed code from a purely sequential code. To this end, we have implemented a Python version of many applications from the Polyhedral Benchmark suite [START_REF]PolyBench/C: The Polyhedral Benchmark suite[END_REF].

As discussed in next subsections, this approach provides several advantages in terms of code re-organization and data blocking but, in its current state, has still significant performance issues. Hence, this paper only presents a preliminary evaluation of the GEMM application.

GEMM.

The presented implementation of the General Matrix-Matrix product of general rectangular matrices with float complex elements performs:

C = α • A • B + β • C.
In general terms, the arrays and matrices are implemented as plain NumPy arrays or matrices. This means that there are no blocks and thus, the minimum work entity is a single element (a float). As in the previous set of experiments, the initialization is performed in a distributed way (defining tasks to initialize the matrix elements), and the computations are performed considering that the data is already located in a given node.

We have evaluated a userparallel Fine-Grain version and an autoparallel version built using taskification. For comparison purposes, we have also evaluated a userparallel Blocked version. Although the userparallel FG works with single elements and userparallel B with blocks, both versions include 2 tasks: scale, and multiply. The autoparallel version defines four tasks: the two original ones and their two loop-tasked versions. The original tasks are kept because in configurations that do not use PLUTO's tiles it is possible to find callees that cannot be taskified. However, in this case, only the loop-tasked versions are called during the execution. Concerning the code, as shown in Table 5, the Loop Tasking version is significantly more complex in terms of lines of code, cyclomatic complexity, and n-path, but is capable of splitting the main loop into two loops (one for the scaling operations and another for the multiplications) for better parallelism. Although both performances are completely unacceptable, there is still room for comparison. First, the autoparallel version is capable of splitting the main loop to isolate the scaling operations. Second, defining single elements as the minimum task entity leads to tasks with too little computation that cause a massive overhead of serialization and transfer inside PyCOMPSs. On the other hand, automatically building data blocks from the sequential user code improves almost 5 times the application performance. More in-depth, building data blocks helps PyCOMPSs to surpass the serialization and transfer overheads. However, building data blocks also increases significantly the number of parameters of each task (around 8 × 8 × 3 = 192 parameters per task) which slows down the PyCOMPSs scheduler and task manager.

We believe that Loop Tasking is a good approach for this kind of applications provided that PyCOMPSs is enhanced with support for collections. This means that task parameters should be defined as lists of objects that are handled by the PyCOMPSs runtime as a single entity. This would significantly lower the scheduling, serialization, and transferring overheads.

Conclusions and Future Work

This paper has presented and evaluated AutoParallel, a Python module to automatically parallelize affine loop nests and execute them on distributed infrastructures. Built on top of PyCOMPSs and PLUTO, it is based on sequential programming so that anyone can scale up an application to hundreds of cores.

The evaluation shows that the codes automatically generated by the AutoParallel module for the Cholesky, LU, and QR applications can achieve the same performance than the manually parallelized versions. Thus, AutoParallel goes one step further in easing the development of distributed applications.

As future work, although the Loop Taskification provides an automatic way to create blocks from sequential applications, its performance is still far from acceptable. On the one hand, we believe that the AutoParallel module could better simplify the chunk accesses since they are executed inside each task. On the other hand, PyCOMPSs could support collection objects (i.e, lists) with different sizes so that we could avoid flattening and rebuilding of chunks, and serializing each object in a separate file.

Finally, AutoParallel could be integrated with different tools similar to PLUTO to support a larger scope of loop nests. For instance, APOLLO [START_REF] Sukumaran-Rajam | The Polyhedral Model of Nonlinear Loops[END_REF], [START_REF] Martinez Caamao | Full runtime polyhedral optimizing loop transformations with the generation, instantiation, and scheduling of codebones[END_REF] provides automatic, dynamic and speculative parallelization and optimization of programs' loop nests of any kind (for, while or do-while loops). However, its integration would require PyCOMPSs to be extended with some speculative mechanisms.

A.2.5. Datasets. The datasets of each application are pseudo-randomly generated during the execution since the size is the only relevant parameter for the computational results. However, the users can check the correctness of the algorithms against the their sequential version by using the -d option when invoking the run scripts.

A.3. Installation

A.4. Experiment workflow

Once that PyCOMPSs, PLUTO, and the AutoParallel module are installed, any example can be executed. To ensure that everything runs smoothly, the users should use the prepared scripts: the run.sh for laptops and the enqueue.sh, and experiments.sh scripts for supercomputers.

More in detail, each application contains:

• README.md : File describing the application and its commands

A.5. Evaluation and expected result

On the one hand, the run.sh script is prepared to run executions on laptops. Although it can be simply invoked without parameters (setting up the default values), the script is a wrapper of the runcompss command and accepts many additional flags (e.g., -d for debug). For instance, here is the command to execute the Cholesky application:

$ cd e x a m p l e s / c h o l e s k y $ . r u n . s h Two executions will be triggered; one for the autoparallel and another for the userparallel version. The output for the Cholesky example should include the following lines: ------------------------------------The results section provides information about the application execution, such as the application parameters and the computation time (CHOKESKY_TIME in the example). The execution summary shows, between others, the total number of executed tasks. Furthermore, inside the results folder the users will find the paraver traces and the task dependency graphs:

$ cd e x a m p l e s / c h o l e s k y / r e s u l t s / l o c a l / $ o k u l a r a u t o p a r a l l e l / c o m p l e t e g r a p h . p d f $ o k u l a r u s e r p a r a l l e l / c o m p l e t e g r a p h . p d f $ w x p a r a v e r a u t o p a r a l l e l / t r a c e / * . p r v $ w x p a r a v e r u s e r p a r a l l e l / t r a c e / * . p r v On the other hand, the enqueue.sh, and experiments.sh scripts are prepared to run executions on supercomputers. The first is a wrapper of the enqueue_compss to enqueue a single execution of the application. The users must specify version (autoparallel or userparallel), job dependency, number of nodes, wall-clock time, number of cpus per node, tracing value, graph value, log level, and the application parameters (in the Cholesky example: the matrix size and block size).

$ . / e n q u e u e . s h a u t o p a r a l l e l None 2 150 48 t r u e f a l s e o f f 32 2048

The experiments.sh script enqueues several jobs to reproduce the experimentation described in Section 5 and can be run without arguments. The results can be easily summarized to a CSV file by running the results.sh script, that will create a results folder with a results.summary file inside containing:

A.6. Experiments Customization

The application parameters can be modified inside the corresponding experiments.sh script of each application. Moreover, the PyCOMPSs options can be tuned inside the corresponding enqueue.sh script.

Figure 1 .

 1 Figure 1. COMPSs overview

@

  constraint(ComputingUnits="$CUS") @task(c=INOUT) def multiply(a, b, c): c += a * b

Figure 2 .

 2 Figure 2. Sample task annotation

Figure 3 .

 3 Figure 3. Sample call to synchronization API

Figure 4 .

 4 Figure 4. Pluto overview. Source: Pluto's official website[START_REF]Pluto[END_REF]

Figure 6 .

 6 Figure 6. Tiling example

Figure 7 .

 7 Figure 7. AutoParallel Module Overview

Figure 8 .

 8 Figure 8. AutoParallel Module Internals

Figure 9 .

 9 Figure 9. EP example: user code

#Figure 11 .

 11 Figure 11. EP example: auto-generated code with loop taskification

Figure 12 .

 12 Figure 12. Cholesky decomposition: Execution times and speed-up

Figure 13 .

 13 Figure 13. LU decomposition: Execution times and speed-up

Figure 14 .

 14 Figure 14. LU decomposition: Paraver trace. At left, userparallel and, at right, the autoparallel version

Figure 15 .

 15 Figure 15. QR decomposition: Execution times and speed-up

Figure 16

 16 Figure16shows the execution results of the GEMM application with a matrix of 64 × 64 elements with 1 worker (48 cores). For the autoparallel, the tile sizes are set to 8 and, for the blocked userparallel, the matrix has 8×8 blocks with 8 elements each. The left plot shows the execution time of the userparallel FG (blue) and the autoparallel LT (green). The right plot shows the slow-down of both versions with respect to the blocked userparallel B version running with a single worker.

Figure 16 .

 16 Figure 16. GEMM: Execution times and slow-down

1 ) 5 )

 15 Prepare the system # Runtime d e p e n d e n c i e s $ s u d o a p t-g e t i n s t a l l o p e n j d k -8-j d k u u i d-r u n t i m e c u r l wget o p e n s s h-s e r v e r maven g r a p h v i z xdg -u t i l s $ e x p o r t JAVA HOME=<p a t h t o o p e n j d k > # P y t h o n and Commons b i n d i n g s d e p e n d e n c i e s $ s u d o a p t-g e t i n s t a l l l i b t o o l a u t o m a k e b u i l de s s e n t i a l p y t h o n-dev l i b p y t h o n 2 . 7 p y t h o n-p i p l i b b o o s t -a l l -dev l i b x m l 2-dev c s h $ s u d o p i p 2 i n s t a l l numpy d i l l d e c o r a t o r # E x t r a e t r a c i n g module d e p e n d e n c i e s $ s u d o a p t-g e t i n s t a l l l i b x m l 2 g f o r t r a n l i b p a p idev p a p i-t o o l s # A u t o P a r a l l e l and PLUTO d e p e n d e n c i e s $ s u d o a p t-g e t i n s t a l l libgmp3-dev f l e x b i s o n l i b b i s o n -dev t e x i n f o $ s u d o p i p 2 i n s t a l l a s t o r enum34 i s l p y sympy 2) Clone PyCOMPSs and enter the newly created directory $ g i t c l o n e h t t p s : / / g i t h u b . com / bsc-wdc / compss . g i t $ cd compss 3) Initialize and patch the submodules (PLUTO, Au-toParallel, and Extrae) $ . / s u b m o d u l e s g e t . s h $ . / s u b m o d u l e s p a t c h . s h 4) Install everything (a) into a given target location or (b) into the default location /opt/COMPSs (requires root privileges) $ cd b u i l d e r s $ ( a ) . / b u i l d l o c a l $HOME/ COMPSs $ ( b ) s u d o -E . / b u i l d l o c a l Check up the environment $ r u n c o m p s s -v COMPSs v e r s i o n 2 . 3 D a i s y

•autoparallel:

  Folder containing the autoparallel version of the application -app_name.py : Source file of the autoparallel version of the application -app_name_autogen.py : Source file automatically generated run.sh : Script to run the autoparallel version of the application • userparallel : Folder containing the userparallel version of the application -app_name.py : Source file of the userparallel version of the application run.sh : Script to run the userparallel version of the application • run.sh : Script to run the all the versions of the application • enqueue.sh : Script to enqueue the application to a queue system (SLURM, LSF, or PBS)• experiments.sh : Script to run all the experiments with all the versions of the application • results.sh : Script to parse the experiments results In the rest of the artifact description, we will explain the most important options to set up in order to reproduce the results of the paper.

  RESULTS-----------------VERSION AUTOPARALLEL MSIZE 4 BSIZE 4 DEBUG F a l s e TOTAL TIME 3 . 9 1 8 2 2 1 9 5 0 5 3 INIT TIME 3 . 2 2 2 7 8 1 1 8 1 3 4 CHOLESKY TIME 0 . 6 9 5 4 4 0 7 6 9 1 9 6 -------------------------[ ( 5 3 3 0 ) API ] ---COMPSs Task E x e c u t i o n Summary --. . . [ ( 5 3 3 1 ) API ] -T o t a l e x e c u t e d t a s k s : 36 [ ( 5 3 3 1 ) API ]

  JOB ID VERSION MSIZE BSIZE TRACING NUM WORKERS TOTAL TIME INIT TIME COMP TIME NUM TASKS 2210018 a u t o p a r a l l e l 32 2048 t r u e 1

TABLE 1 .

 1 LIST OF FLAGS FOR THE

	Flag	Default Value	Description
	pluto_extra_flags	None	List of flags for the inter-nal PLUTO command
	taskify_loop_level 0	Taskification loop depth (see Section 4.2)
	force_autogen	True	When set to False, loads a previously generated code
			When set to True, only
	generate_only	False	generates the parallel ver-
			sion of the code

TABLE 3 .

 3 LU CODE ANALYSISFigure13shows the execution results of the LU decomposition with a 49152 × 49152 dense matrix of 24 × 24 blocks with 2048 × 2048 elements each. As in the previous example, the overall performance is limited by the block size. This time the userparallel version slightly outperforms the autoparallel version; achieving, respectively, a 2.45 and 2.13 speed-up with 4 workers (192 cores).

	Version	Code Analysis LoC CC NPath Main Total Depth Loops Analysis	Task Types
	userparallel 238	35	79872 2	6	3	4
	autoparallel 320	39	331776 2	6	3	12

Acknowledgments

This work has been supported by the Spanish Government (SEV2015-0493), by the Spanish Ministry of Science and Innovation (contract TIN2015-65316-P), by Generalitat de Catalunya (contract 2014-SGR-1051), and by the European Commission through the Horizon 2020 Research and Innovation program under contract 800898 (ExaQUte project). Cristian Ramon-Cortes predoctoral contract is financed by the Ministry of Economy and Competitiveness under the contract BES-2016-076791.

Thanks to Cédric Bastoul for his support with CLooG.

Appendix A. Artifact Description

A. 1. Abstract This description contains the information required to launch the experiments of the SC18 paper "AutoParallel:A Python module for automatic parallelization and distributed execution of affine loop nests". More precisely, we explain how to install the AutoParallel module and its dependencies, and how to run the experiments described in Section 5.

A.2. Description

A.2.1. Check-list (artifact meta information). [START_REF]COMPSs GitHub[END_REF] and [START_REF]PyCOMPSs AutoParallel Module GitHub[END_REF] respectively. The examples used for the experimentation can be found under the examples folder.

A.2.3. Hardware dependencies. None.

A.2.4. Software dependencies. PyCOMPSs depends on the COMPSs Runtime, the Python and Commons bindings, and the Extrae tracing module that are automatically installed. However, the users must provide valid Java, Python, and GCC installations.

PLUTO depends on Candl, Clan, CLooG, ISL, Open-Scop, PipLib, and PolyLib modules that are automatically installed. However, the users must explicitly provide valid GMP, Flex, and Bison installations.

The AutoParallel module requires a valid installation of PyCOMPSs and PLUTO. Moreover, the users must check that the following Python modules are available: AST, AS-TOR, enum34, logging, inspect, islPy, symPy, subprocess, and unittest.

The examples used for the experimentation require the NumPy Python module.