Languages, Compilation, and Semantics LIP Seminar in 2019

When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid the cost of this expensive accesses, while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph. I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications of DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average. This is joint work with Charles Paperman.

Field Programmable Gate Array (FPGA) architec-tures are suitable hardware platforms for systems that need high performance and flexibility, because they support dynamic partial reconfiguration (DPR) to implement adaptive hardware algorithms e.g., for performance or energy efficiency. They are used for example in embedded systems such as UAV, e.g. for video processing. It is a challenge to design Autonomic Managers for such highly dynamic systems, taking into account the combina-torial design space of configurations and criteria and policies to decide on whether to reconfigure, and what next configuration to choose. In this paper, we propose a Domain Specific Language (DSL) called Ctrl-DPR, allowing designers to easily generate Autonomic Managers. They can describe their system and their management strategies, in terms of the entities composing the system : tasks, versions, applications, ressources, policies. The DSL relies on a behavioural modelling of these entities, targeted at the design of autonomic managers to control the reconfigurations in such a way as to enforce given policies and strategies. The models we use involve automata to describe the state space of configurations, and the transitions representing reconfigurations; they also involve discrete control techniques exploiting such models in order to obtain a correct runtime manager. These model-based control techniques are embedded in a compiler, connected to a reactive language and discrete controller synthesis tool, which enables to generate a C implementation of the controller enforcing the management strategies. We apply our DSL for the management of a video application on a UAV.

OpenMP (http://www.openmp.org) est un standard de facto qui est piloté par l’ARB (Architecture Review Board) composé de la plupart des grands constructeurs en HPC ainsi que par certains représentants universitaires. L’objectif d’OpenMP est d’offrir un ensemble de directives pour annoter du code séquentiel afin d'exploiter tous les niveaux de parallélisme qui sont offerts par les matériels, i.e. multi-cœurs, unités vectorielles et accélérateurs. Dans cette présentation nous nous attacherons à re-positionner les évolutions actuelles de la norme 4.x entre son passé (pré 3.0) et son futur (5.0) en s’intéressant plus particulièrement au modèle de tâches.

Nous présenterons la manière dont sont définies les tâches et leurs dépendances dans le modèle OpenMP. Nous verrons qu'un tel programme OpenMP est fonctionnellement portable mais que l'obtention des performances doit aussi prendre en compte l'implementation à disposition. Nous illustrerons sur quelques exemples typiques en HPC l'impact de quelques runtimes (GCC, ICC/LLVM, …) sur les performances dont certains choix d'implémentation restentcritiquables.