Frédéric Gava

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.

What is bulk-synchronous parallel (BSP) computing and is not? Behind this naive question, we can find complex formalisms. We first define a model that contain all BSP algorithms; This model comes with what is called abstract state machines (ASMs). Then, we prove, by using an operational semantics and a fair simulation, the algorithmic equivalence between an imperative language (with BSP routines) and the previous model. We finally give the intuition of an example that is not BSP complete.

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.