Team APR

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Journées APR d'été 2025 à Lille =====

les 2 et 3 juin 2025

==== Adresse ====


Batiment ESPRIT\\
avenue Paul Langevin\\
Villeneuve-d'Ascq, 59650\\


==== Programme préliminaire ====

  * Lundi 2 juin 2025
    * Arrivée en train suggérée à XXX
    * **12:00-13:30**: Déjeuner
    * **14:00-15:30**: Session exposés 1
    * **15:30-16:00**: Pause
    * **16:00-17:30**: Session exposés 2
    * **19:30**: dîner
  * Mardi 3 juin 2025
    * **09:00-10:30**: Session exposés 3
    * **10:30-11:00**: Pause 
    * **11:00-12:00**: Session enseignement
    * **12:00-13:30**: Déjeuner
    * **13:30-15:00**: Réunion APR
    * Départ suggéré par le train de 

==== Liste préliminaire des intervenants ====

  * Danaël Carbonneau (APR, LIP6, Sorbonne Université)
  * Amaury Curiel (APR, LIP6, Sorbonne Université)
  * Mohamed Kissi (APR, LIP6, Sorbonne Université)
  * Mamy Razafintsialonina (CEA-LIST & APR, LIP6, Sorbonne Université)
  * Loïc Sylvestre (DI, École Normale Supérieure)

----

==== Résumés ====

**Analyse théorique de l'algorithme git bisect**\\
Julien Courtiel (GREYC, Université de Caen)

Dans le royaume des logiciels de gestion de versions, git
est sûrement celui qui est assis sur le trône. Ce logiciel libre et
populaire dispose de nombreuses fonctionnalités très intéressantes
dont notamment une, peut-être plus méconnue, qui s'appelle git bisect.
Il s'agit d'un algorithme qui permet de débusquer l'origine d'un bug
qui s'est introduit dans un projet.

L'ensemble des historiques d'un projet formant naturellement un graphe
(plus précisément un DAG), git bisect peut tout simplement se voir
comme un algorithme de graphes résolvant un problème connu pour être
NP-complet. Toutefois, il est surprenant de voir qu'aucune étude
théorique de sa complexité n'a été menée. Paul Dorbec, Romain Lecoq et
moi-même, tous trois de l'Université de Caen Normandie, proposons de
rectifier cela et vérifier les bonnes performances théoriques (ou non)
de git bisect. Il s'agit de travaux en cours.

Cet exposé présentera ainsi les faiblesses et les forces de git
bisect. Tout d'abord, nous donnerons la forme des graphes pour
lesquels la stratégie de git bisect est totalement catastrophique.
Ensuite, nous montrerons que pour une certaine classe de graphes qui
est représentative des graphes "issus de la vie réelle", git bisect
est en fait une bonne approximation de la stratégie optimale. Enfin,
nous nous interrogerons sur l'existence d'un meilleur algorithme.


----


**Unranking des ZDD: Le premier algorithme d’unranking efficace basé sur le principe d’inclusion-exclusion**\\
Amaury Curiel (APR, SU)

Les ZDD sont une structure de données introduite en 1993 par S.I. Minato dans [1] permettant de représenter des fonctions booléennes de manière compacte grâce à deux règles de compression.
Dans cet exposé, nous allons présenter les ZDD et les comparer aux ROBDD [2], une autre structure de données permettant de représenter des fonctions booléennes en utilisant un autre jeu de règles de compression, et nous exhiberons une formule de comptage pour ces structures basée sur le principe d’inclusion-exclusion. Le fait que cette formule ne soit pas constructive pose un problème dans la conception d’algorithmes de génération par [[ https://oeis.org/wiki/Ranking_and_unranking_functions| unranking]].
Nous présenterons donc la manière dont nous avons résolu ce problème pour concevoir le premier algorithme d’unranking efficace basé sur le principe d’inclusion-exclusion.

[1] S.-i. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,” in Proceedings of the 30th International Design Automation Conference, in DAC '93. Dallas, Texas, USA: Association for Computing Machinery, 1993, pp. 272–277. doi: 10.1145/157485.164890.

[2] Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, no. 8, pp. 677–691, 1986, doi: 10.1109/TC.1986.1676819.


----


**Modular Counting of Linear Extensions**\\
Matthieu Dien (GREYC, Université de Caen)

The counting of linear extensions is a prominent problem about partial orders.
Unfortunately, the problem is computationally hard and in fact, relatively few counting procedures have been proposed in the literature.
In this talk, we will present a new counting algorithm based on the modular decomposition of posets.
This algorithm has a better parametrized complexity than the state of the art.
Moreover, this approach leads us to consider a new parameter of posets (the BIT-width) with two corresponding conjectures.


----

**Fouille de graphes, application à la chémoinformatique**\\
Jean-Luc Lamotte (GREYC, Université de Caen)

Cet exposé présente les travaux menés au sein du groupe de
chémoinformatique composé d'informaticiens du laboratoire GREYC et de
chimistes thérapeutiques du laboratoire CERMN. La collaboration se
concentre sur la conception de méthodes computationnelles pour
identifier des (sous-)structures chimiques d'intérêt (pour l'activité,
la toxicité ...) dans les premières étapes de la découverte de
médicaments. Pour ce faire, nous nous appuyons sur des données de
bioactivité stockées dans des bases de données chimiques publiques
telles que ChEMBL ou des données internes (chimiothèque du CERMN).
Nous disposons d'informations concernant l'affinité des ligands pour
les cibles (un ligand est une molécule qui se lie à une cible).
À partir de ces premières informations, nous calculons des
associations statistiques mettant en évidence les (sous-)structures
chimiques dont la présence semble influencer l'interaction d'une
molécule avec la (les) cible(s) d'intérêt. 

Notre travail est centré sur les caractéristiques pharmacophoriques
des molécules. Ces caractéristiques correspondent à des fonctions
chimiques importantes dans les interactions entre les ligands et les
cibles.  Toutes les méthodes sont basées sur une représentation des
molécules sous la forme de graphes de caractéristiques
pharmacophoriques et sur de la fouille de données de sous-graphes
appelés pharmacophores. 


L'exposé présentera l'approche spécifique du groupe de
chémoinformatique et les résultats obtenus.

----

**TTK is Getting MPI-Ready**\\
Ève Le Guillou (APR, SU)

This system paper documents the technical foundations for the extension of the Topology ToolKit (TTK) to distributed-memory parallelism with the Message Passing Interface (MPI).
While several recent papers introduced topology-based approaches for distributed-memory environments, these were reporting experiments obtained with tailored, mono-algorithm implementations.
In contrast, we describe in this paper a versatile approach (supporting both triangulated domains and regular grids) for the support of topological analysis pipelines, i.e. a sequence of topological algorithms interacting together.
While developing this extension, we faced several algorithmic and software engineering challenges, which we document in this paper.
We describe an MPI extension of TTK's data structure for triangulation representation and traversal, a central component to the global performance and generality of TTK's topological implementations.
We also introduce an intermediate interface between TTK and MPI, both at the global pipeline level, and at the fine-grain algorithmic level.
We provide a taxonomy for the distributed-memory topological algorithms supported by TTK, depending on their communication needs and provide examples of hybrid MPI+thread parallelizations.
Performance analyses show that parallel efficiencies range from 20% to 80% (depending on the algorithms), and that the MPI-specific preconditioning introduced by our framework induces a negligible computation time overhead.
We illustrate the new distributed-memory capabilities of TTK with an example of advanced analysis pipeline, combining multiple algorithms, run on the largest publicly available dataset we have found (120 billion vertices) on a cluster with 64 nodes (for a total of 1536 cores).
Finally, we provide a roadmap for the completion of TTK's MPI extension, along with generic recommendations for each algorithm communication category.

[[https://arxiv.org/abs/2310.08339 | [article]]]

----


**Under-approximating Abstract Interpretation**\\
Marco Milanese (APR, SU)

Static analysis by abstract interpretation has traditionally focused on
program verification, that is on checking that programs are free of bugs.
However, in practice it is not easy to achieve a low rate of false positives,
and thus verification techniques are difficult to use to catch bugs. In this PhD
we explore a different and unconventional analysis, based on abstract
interpretation, allowing to compute under-approximations and thus catching bugs.
This analysis infers sufficient pre-conditions for program defects, enabling
developers to detect real bugs and obtain precise information on the conditions
where they occur. Our work applies this analysis to the C programming languge:
firstly, by focusing on numeric properties and more recently by adding support
for the rest of the language (e.g., pointers, memory allocations). Finally,
we discuss preliminary results of our experiments and future directions
of work.

----

**Wasserstein Auto-Encoders of Merge Trees (and Persistence Diagrams)**\\
Mathieu Pont (APR, SU)

This paper presents a computational framework for the Wasserstein auto-encoding of merge trees (MT-WAE), a novel extension of the classical auto-encoder neural network architecture to the Wasserstein metric space of merge trees. In contrast to traditional auto-encoders which operate on vectorized data, our formulation explicitly manipulates merge trees on their associated metric space at each layer of the network, resulting in superior accuracy and interpretability. Our novel neural network approach can be interpreted as a non-linear generalization of previous linear attempts [79] at merge tree encoding. It also trivially extends to persistence diagrams. Extensive experiments on public ensembles demonstrate the efficiency of our algorithms, with MT-WAE computations in the orders of minutes on average. We show the utility of our contributions in two applications adapted from previous work on merge tree encoding [79]. First, we apply MT-WAE to merge tree compression, by concisely representing them with their coordinates in the final layer of our auto-encoder. Second, we document an application to dimensionality reduction, by exploiting the latent space of our auto-encoder, for the visual analysis of ensemble data. We illustrate the versatility of our framework by introducing two penalty terms, to help preserve in the latent space both the Wasserstein distances between merge trees, as well as their clusters. In both applications, quantitative experiments assess the relevance of our framework. Finally, we provide a C++ implementation that can be used for reproducibility. 

----

**Wasserstein Dictionaries of Persistence Diagrams**\\
Keanu Sisouk (APR, SU)

We introduce a multi-scale gradient descent approach for the efficient resolution of the corresponding minimization problem, which interleaves the optimization of the barycenter weights with the optimization of the atom diagrams. Our approach leverages the analytic expressions for the gradient of both sub-problems to ensure fast iterations and it additionally exploits shared-memory parallelism. Extensive experiments on public ensembles demonstrate the efficiency of our approach, with Wasserstein dictionary computations in the orders of minutes for the largest examples. We show the utility of our contributions in two applications. First, we apply Wassserstein dictionaries to data reduction and reliably compress persistence diagrams by concisely representing them with their weights in the dictionary. Second, we present a dimensionality reduction framework based on a Wasserstein dictionary defined with a small number of atoms  and encode the dictionary as a low dimensional simplex embedded in a visual space.

----

**Programmation FPGA de bas en haut et vice-versa**\\
Loïc Sylvestre (APR, SU)

Les circuits reconfigurables FPGA sont classiquement décrits
dans des langages synchrones flot de données, tels que VHDL.
Ces langages permettent d'interagir directement avec le monde
extérieur (capteurs, actionneurs), d'une façon intrinsèquement
parallèle et déterministe, en se synchronisant sur une horloge
globale. La programmation de FPGA dans ces langages est toutefois
difficile, car de très bas niveau.

Pour y remédier, je montrerai comment encoder des constructions
de programmation (fonctions, barrières de synchronisation,
mémoire partagée), dressant ainsi les bases d'un schéma de
compilation pour un langage généraliste parallèle sur une cible FPGA.

Ce présente alors un dilemme : comment garder un contrôle fin,
de bas-niveau, sur le comportement temporel des applications généralistes ?
C'est un point important pour l'interaction avec le monde
extérieur, pour prédire les performances et pour offrir à la fois du
parallélisme de tâches et de la mémoire partagée (en lecture et en écriture)
de façon sûre.

La solution que je propose consiste à donner, à un langage généraliste,
une sémantique synchrone guidée par la cible FPGA. Il s'agit alors
de définir un nouveau schéma de compilation pour que l'horloge du modèle
synchrone du langage corresponde à l'horloge globale de la cible FPGA.

Le modèle de programmation résultant semble bien adapté
pour la conception de systèmes embarqués réactifs,
la programmation d'applications parallèles avec mémoire partagée,
et l'implantation matérielle de langages de programmation existants. 

----

**Static Value Analysis by Abstract Interpretation for Functional Languages**\\
Milla Valnet (APR, SU)

To prevent programming errors, static analysers have been developed for many languages; here we will focus on functional languages. Verification tools for these languages exist, such as classical type systems or deductive methods, but automatic reasoning on numerical programs has been little explored. In this presentation, I will present my work on value analysis by abstract interpretation of functional languages, a safe and automatic approach to prevent errors at runtime.
Our first results, based on relational abstract domains and summaries of recursive fields in algebraic types, allow us to analyse first-order recursive functions manipulating recursive algebraic types, and to infer in an abstract domain their input-output relation. These methods have been successfully implemented on the MOPSA multilanguage analysis platform for the OCaml language.
Our current research aims to retain this compositionality for the analysis of higher-order functions, in order to obtain a precise input-output relationship from their point of definition. I will present our ideas, currently experimentally evaluated.

----
Team APR

User Tools

Site Tools

Page Tools
