Team APR

les 30 et 31 mai 2024

Université de Caen Normandie
Campus 2
Côte de nacre
Boulevard Maréchal Juin
14032 Caen Cedex 5

Tram ligne T2, arrêt Campus 2

Carte OpenStreetMap

• Jeudi 30 mai 2024
  • Arrivée en train suggérée à 12:03 en gare de Caen
  • 13:00-14:30: Déjeuner
  • 14:30-16:00: 1ère session, 3 exposés
  • 16:00-16:30: Pause
  • 16:30-18:00: 2ème session, 3 exposés
  • soir: dîner
• Vendredi 31 mai 2024
  • 09:00-10:30: 3ème session, 3 exposés
  • 10:30-11:00: Pause
  • 11:00-12:30: 4ème session, exposés, discussion sur l'enseignement
  • 12:30-14:00: Déjeuner
  • 14:00-15:00: Réunion APR
  • Départ suggéré par le train de 15:56 en gare de Caen

• Julien Courtiel (GREYC, Université de Caen)
• Amaury Curiel (APR, LIP6, Sorbonne Université)
• Matthieu Dien (GREYC, Université de Caen)
• Jean-Luc Lamotte (GREYC, Université de Caen)
• Ève Le Guillou (APR, LIP6, Sorbonne Université)
• Marco Milanese (APR, LIP6, Sorbonne Université)
• Mathieu Pont (APR, LIP6, Sorbonne Université)
• Keanu Sisouk (APR, LIP6, Sorbonne Université)
• Loïc Sylverstre (APR, LIP6, Sorbonne Université)
• Milla Valnet (APR, LIP6, Sorbonne Université)

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 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.

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.

[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 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.