Journal:

Programming BSP and Multi-BSP algorithms in ML
V. Allombert, F. Gava
The Journal of Supercomputing (J. Supercomput. 2019) [Link] The BSML and Multi-ML languages have been designed for programming in ML algorithms of the respectively bsp and Multi-BSP bridging models. Multi-BSP is an extension of the well-know BSP model by taking into account the different levels of networks and memories of modern hierarchical architectures. This is a new model, as well as Multi-ML, while BSP and BSML have been used for a long time in many different domains. But designing and programming Multi-BSP algorithms is intuitively more complex than with BSP. One can ask if it is beneficial to rewrite BSP algorithms using the Multi-BSP model? In this paper, we thus investigate the pro and cons of the aforementioned models and languages by experimenting with them on different typical applications. We use a methodology to measure the level of difficulty of writing code and we also benchmark them in order to show if writing Multi-ML code is worth the effort.

Multi-ML: Programming Multi-BSP Algorithms in ML
V. Allombert, F. Gava, J. Tesson
International Journal of Parallel Programming (IJPP 2017) [HAL] BSP is a bridging model between abstract execution and concrete parallel systems. Structure and abstraction brought by BSP allow to have portable parallel programs with scalable performance predictions, without dealing with low-level details of architectures. In the past, we designed BSML for programming BSP algorithms in ML. However, the simplicity of the BSP model does not fit the complexity of today’s hierarchical architectures such as clusters of machines with multiple multi-core processors. The Multi-BSP model is an extension of the BSP model which brings a tree-based view of nested components of hierarchical architectures. To program Multi-BSP algorithms in ML, we propose the Multi-ML language as an extension of BSML where a specific kind of recursion is used to go through a hierarchy of computing nodes. We define a formal semantics of the language and present preliminary experiments which show performance improvements with respect to BSML.

International Conferences:

Introduction to the Tezos Blockchain (Tutorial)
V. Allombert, M. Bourgoin, J. Tesson
International Conference on High Performance Computing and Simulation (HPCS 2019) [Link] Tezos is an innovative blockchain that improves on several aspects compared to more established blockchains. It offers an original proof-of-stake consensus algorithm and can be used as a decentralized smart contract platform. It has the capacity to amend its own economic protocol through a voting mechanism and focuses on formal methods to improve safety

Toward performance prediction for Multi-BSP programs in ML
V. Allombert, F. Gava, J. Tesson
18th International Conference on Algorithms and Architectures for Parallel Processing ( ICA3PP 2018) [Link] BSML and Multi-ML are functional parallel programming languages “à la ML” based of the respectively the BSP and Multi-BSP bridging models. Multi-BSP extends BSP to take into account hierarchical architectures. For both models, it is possible to predict the performances of algorithms thanks to embedded cost models. To do so, we propose formal a operational semantics with cost annotations for the two aforementioned languages. This work has been done in a incremental manner. First we recall the cost semantics of core-ML language. Then, we adapt it to BSML and we adapt it to multi-ML. It is then possible to evaluate the cost of a program following the annotated semantics. Finally, we compare the theoretical approach with the current implementation on a code example.

An ML implementation of the MULTI-BSP model
V. Allombert, F. Gava
International Conference on High Performance Computing and Simulation (HPCS 2018) [Link] We have designed a parallel language called MULTI-ML for programming MULTI-BSP algorithms in ML. The MULTI-BSP model provides a tree-based view of nested components of hierarchical architectures. The structure and abstraction brought by MULTI-BSP allows for portable parallel programs with scalable performance predictions, without dealing with low-level details of architecture. The MULTI-ML language is essentially based on the concept of multi-functions which are recursive functions used to execute perform recursions on the nested sub-components through the MULTI-BSP (hierarchical) architecture. In this paper we design a generic compilation scheme of the MULTI-ML language dedicated to parallel machines performing data exchanges using synchronous requests, derived from any ML compilation. This ensures that the implementation follows the semantics, allowing greater confidence in the safety of execution.

Parallel Programming with OCaml: A Tutorial (Tutorial)
V. Allombert, M. Bourgoin, F. Loulergue
International Conference on High Performance Computing and Simulation (HPCS 2018) [Link] OCaml is a multi-paradigm (functional, imperative, object-oriented) high level sequential language. Types are stati-cally inferred by the compiler and the type system is expressive and strong. These features make OCaml a very productive language for developing efficient and safe programs. In this tutorial we present three frameworks for using OCaml to program scalable parallel architectures: BSML, Multi-ML and Spoc.

A formal semantics of the Multi-ML language
V. Allombert, F. Gava
International Symposium on Parallel and Distributed Computing (ISPDC 2018) [Link] In the context of high performance computing, it is important to avoid indeterminism and dead-locks. MULTI-ML is a functional parallel programming language “à la ML ”, designed to program hierarchical architectures in a structured way. It is based of the MULTI-BSP bridging model. To ensure that a program “cannot go wrong”, we first need to define how a program “goes”. To do so, we propose a formal operational semantics of the MULTI-ML language to ensure the properties of the MULTI-BSP model. We first describe a core-language and then introduce the big step’s semantics evaluation rules. Then, we propose a set of evaluation rules that describe the behaviour of the MULTI-ML language. The memory model is also precisely defined, as the MULTI-BSP model deals with multiple level of nested memories.

An Out-of-core GPU Approach for Accelerating Geostatistical Interpolation
V. Allombert, D. Michea, F. Dupros, C. Bellier, B. Bourgine, H. Aochi, S. Jubertie
International Conference on Computational Science. 2014. Cairns, Australia. [Link] Geostatistical methods provide a powerful tool to understand the complexity of data arising from Earth sciences. Since the mid 70's, this numerical approach is widely used to understand the spatial variation of natural phenomena in various domains like Oil and Gas, Mining or Environmental Industries. Considering the huge amount of data available, standard implementations of these numerical methods are not efficient enough to tackle current challenges in geosciences. Moreover, most of the software packages available for geostatisticians are designed for a usage on a desktop computer due to the trial and error procedure used during the interpolation. The Geological Data Management (GDM) software package developed by the French geological survey (BRGM) is widely used to build reliable three-dimensional geological models that require a large amount of memory and computing resources. Considering the most time-consuming phase of kriging methodology, we introduce an efficient out-of-core algorithm that fully benefits from graphics cards acceleration on desktop computer. This way we are able to accelerate kriging on GPU with data 4 times bigger than a classical in-core GPU algorithm, with a limited loss of performances.

Talk at an International Conference without Proceedings

Programming BSP and Multi-BSP algorithms in ML
V. Allombert, F. Gava
11th International Symposium on High-Level Parallel Programming and Applications (HLPP 2018) [Link] The BSML and Multi-ML languages have been designed for programming in ML algorithms of the respectively bsp and Multi-BSP bridging models. Multi-BSP is an extension of the well-know BSP model by taking into account the different levels of networks and memories of modern hierarchical architectures. This is a new model, as well as Multi-ML, while BSP and BSML have been used for a long time in many different domains. But designing and programming Multi-BSP algorithms is intuitively more complex than with BSP. One can ask if it is beneficial to rewrite BSP algorithms using the Multi-BSP model? In this paper, we thus investigate the pro and cons of the aforementioned models and languages by experimenting with them on different typical applications. We use a methodology to measure the level of difficulty of writing code and we also benchmark them in order to show if writing Multi-ML code is worth the effort.

International Workshops

Multi-ML: Programming Multi-BSP Algorithms in ML
V. Allombert, F. Gava, J. Tesson
8th International Symposium on High-Level Parallel Programming and Applications (HLPP 2015) [Link] [PDF] BSP is a bridging model between abstract execution and concrete parallel systems. Structure and abstraction brought by BSP allow to have portable parallel programs with scalable performance predictions, without dealing with low-level details of architectures. In the past, we designed BSML for programming BSP algorithms in ml. However, the simplicity of the BSP model does not fit the complexity of today’s hierarchical architectures such as clusters of machines with multiple multi-core processors. The multi-BSP model is an extension of the BSP model which brings a tree-based view of nested components of hierarchical architectures. To program multi-BSP algorithms in ml, we propose the multi-ml language as an extension of BSML where a specific kind of recursion is used to go through a hierarchy of computing nodes. We define a formal semantics of the language and present preliminary experiments which show performance improvements with respect to BSML.

Thesis:

Functional abstraction for programming Multi-level architectures: Formalisation and implementation
7 July 2017. Paris. France [PDF] [slides] [jury] From personal computers using an increasing number of cores, to supercomputers having millions of computing units, parallel architectures are the current standard. The high performance architectures are usually referenced to as hierarchical, as they are composed from clusters of multi-processors of multi-cores. Programming such architectures is known to be notoriously difficult. Writing parallel programs is, most of the time, difficult for both the algorithmic and the implementation phase. To answer those concerns, many structured models and languages were proposed in order to increase both expressiveness and efficiency. Among other models, Multi-BSP is a bridging model dedicated to hierarchical architecture that ensures efficiency, execution safety, scalability and cost prediction. It is an extension of the well known BSP model that handles flat architectures. In this thesis we introduce the Multi-ML language, which allows programming Multi-BSP algorithms “à la ML” and thus, guarantees the properties of the Multi-BSP model and the execution safety, thanks to a ml type system. To deal with the multi-level execution model of Multi-ML, we defined formal semantics which describe the valid evaluation of an expression. To ensure the execution safety of Multi-ML programs, we also propose a typing system that preserves replicated coherence. An abstract machine is defined to formally describe the evaluation of a Multi-ML program on a Multi-BSP architecture. An implementation of the language is available as a compilation toolchain. It is thus possible to generate an efficient parallel code from a program written in Multi-ML and execute it on any hierarchical machine.

Acknowledgement:

Towards a self-consistent orbital evolution for EMRIs
A. Spallicci, P. Ritter, S. Jubertie, S. Cordier, S. Aoudia
IX Lisa Conference,Proceedings by the Astronomical Society of the Pacific Conference Serie. Paris. [Link] We intend to develop part of the theoretical tools needed for the detection of gravitational waves coming from the capture of a compact object, 1-100 solar masses, by a Supermassive Black Hole, up to a 10 billion solar masses, located at the centre of most galaxies. The analysis of the accretion activity unveils the star population around the galactic nuclei, and tests the physics of black holes and general relativity. The captured small mass is considered a probe of the gravitational field of the massive body, allowing a precise measurement of the particle motion up to the final absorption. The knowledge of the gravitational signal, strongly affected by the self-force - the orbital displacement due to the captured mass and the emitted radiation - is imperative for a successful detection. The results include a strategy for wave equations with a singular source term for all type of orbits. We are now tackling the evolution problem, first for radial fall in Regge- Wheeler gauge, and later for generic orbits in the harmonic or de Donder gauge for Schwarzschild-Droste black holes. In the Extreme Mass Ratio Inspiral, the determination of the orbital evolution demands that the motion of the small mass be continuously corrected by the self-force, i.e. the self-consistent evolution. At each of the integration steps, the self-force must be computed over an adequate number of modes; further, a differential-integral system of general relativistic equations is to be solved and the outputs regularised for suppressing divergences. Finally, for the provision of the computational power, parallelisation is under examination.