Laboratoire de l’Informatique du Parallélisme › LIP › ralip2009 › projet.pdf · La maîtrise de cette complexité demande toujours plus de connaissances, avec une machine

AERES

Campagne d'évaluation 2011-2014Unité de recherche

Laboratoire de l’Informatique du Parallélisme

UMR n 5668

Gilles Villard

CNRSÉcole Normale Supérieure de Lyon

INRIAUniversité Claude Bernard Lyon 1

Projet scientifique et annexes

Laboratoire de l’Informatique du ParallélismeLIP, École normale supérieure de Lyon - 46, allée d’Italie, 69364 Lyon cedex 07

Scientific project

LIP documents concerning the evaluation (extended progress report, publications, etc.)will be available at http://www.ens-lyon.fr/LIP/Eval

http://www.ens-lyon.fr/LIP/Eval

Résumé du projet

Le calcul —les ordinateurs, les réseaux de communication, et leurs applications— participe de manière cruciale auprogrès de la société. Les infrastructures numériques ont connu une croissance très rapide au point d’être maintenantubiquitaires. La société perçoit ces infrastructures aussi bien sous la forme des systèmes embarqués ou pervasifs que souscelle de réseaux de calculateurs maintenant à l’échelle de la planète. Outre cet impact technologique, on assiste à un autrechangement, plus récent, mais tout aussi fondamental : les sciences non-informatiques adoptent souvent, par nécessité, unmode de pensée informatique et algorithmique.

Notre défi est de participer et d’accompagner cette double révolution. Le projet du LIP s’inscrit dans l’étude dumonde numérique futur et de ses fondements théoriques, dans l’optique d’inventer de nouveaux concepts informatiqueset d’anticiper leur répercussion sur les autres sciences. Nos ouvertures stratégiques, qui sont riches et traditionnelles versles mathématiques, vont en outre vers les sciences numériques, la modélisation, les sciences du vivant et les industriesde communication et de semi-conducteurs (pôles de compétitivité Minalogic et System@tic). Ces ouvertures assurent enparticulier notre ancrage dans le tissu lyonnais et régional.

Nos recherches s’organiseront selon deux axes complémentaires et transverses aux équipes :– Défis des futures architectures de calcul et de communication : conception, utilisation et adéquation aux contraintes

et besoins des applications ;– Modèles et méthodes en informatique mathématique : aspects fondamentaux et contribution à l’algorithmique, au

développement logiciel et matériel innovant et aux avancées technologiques.La machine (ordinateur, infrastructure) est le centre de nos études. Elle est pour nous aussi bien une entité abstraite

qu’un objet physique. Depuis toujours au LIP les recherches vont du fondamental au développement, ce qui est à la foisune base solide pour notre projet et une source majeure d’invention. Pour l’objet réel, des combinaisons à l’infini d’unitésde calcul, de communication, et de mémoire, conduisent à une complexité fantastique (puces, multi-cœurs, processeursembarqués, nuages de calculateurs, réseau internet, systèmes pervasifs, etc.). La maîtrise de cette complexité demandetoujours plus de connaissances, avec une machine qui soit à la fois une cible et un moyen pour la recherche. Dans cecontexte, le LIP met un accent particulier sur la qualité du calcul et sur l’utilisation optimisée, fiable et sécurisée desressources. L’informatique mathématique et l’algorithmique sont des thèmes partagés par tout le laboratoire. Ils revêtentun rôle central afin d’inventer de nouveaux modèles et paradigmes qui nous permettent de faire face au changementd’échelle et à la complexité des problèmes que nous étudions.

Les sciences numériques amènent des défis stratégiques importants. Du traitement du signal et de la synthèse avecAlcatel-Lucent et STMicroelectronics, au projet AFM-CNRS-IBM Décrypton et aux infrastructures numériques intercon-tinentales, nous continuerons à participer à ces défis dans le cadre d’un thème complémentaire aux deux axes mentionnésci-dessus :

– Aspects applicatifs et multi-disciplinaires : calcul haute performance, modélisation informatique, systèmes com-plexes et sciences du vivant,

thème où nous trouvons notamment notre participation aux projets de la Fédération Lyonnaise de Modélisation et SciencesNumériques et les évolutions de nos collaborations avec l’Institut des Systèmes Complexes.

Nos objectifs et évolutions scientifiques nous conduisent à une ré-organisation de six à huit équipes : Arénaire (Arith-métique des ordinateurs), Avalon (Algorithmes et architectures logicielles pour les plates-formes orientées services),CompSys (Compilation, systèmes enfouis et calcul intensif), D-Net (Réseaux dynamiques), MC2 (Modèles de calculet complexité), Plume (Théorie de la preuve et sémantique formelle), Reso (Protocoles et logiciels optimisés pour réseauxhaut débit), Roma (Optimisation des ressources : modèles, algorithmes et ordonnancement). Ces équipes couvrent unlarge éventail de l’informatique incluant les domaines : nouvelles architectures et infrastructures de calcul, internet dufutur, réseaux dynamiques, développement logiciel et matériel, calcul parallèle, protocoles de communication, ordonnan-cement, services et composants, évaluation de performance, compilation, synthèse, optimisation de code, calcul certifié,calcul algébrique, cryptographie, algèbre linéaire, réseaux Euclidiens, complexité, complexité algorithmique, systèmes àévènements discrets, automates, graphes, modèles de programmation, preuve formelle, logique, etc.

Le LIP, comme Unité Mixte de Recherche, est associé au CNRS, à l’ENS, à l’UCBL et à l’INRIA. Les équipesArénaire, Avalon, Compsys, D-Net, Reso et Roma sont des projets existants, en création ou en voie de création à l’INRIA.

i

ii

Nouvel organigramme du laboratoire

Contents

1 LIP general project 11.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 LIP’s internal evolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Main scientific evolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.3 Local, national, and international evolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1.4 Strengths and opportunities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Scientific project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 Addressing the challenges of future computational and communication architectures . . . . . . . 71.2.2 Mathematical computer science models, methods, and algorithms . . . . . . . . . . . . . . . . . 81.2.3 Cross-fertilization with other disciplines, and application domains . . . . . . . . . . . . . . . . . 9

1.3 Implementing the project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.1 Weaknesses and risks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.2 Governance and animation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.3 Personnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3.4 Teaching and training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.5 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Arénaire - Computer Arithmetic 132.1 Team Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Towards the automatic design of operators and functions . . . . . . . . . . . . . . . . . . . . . . 142.3.2 New mathematical tools for function approximation . . . . . . . . . . . . . . . . . . . . . . . . 152.3.3 Linear algebra and polynomial evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.4 Methods for Certified Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.5 Euclidean lattice reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.6 Pairing-based cryptology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Avalon - Algorithms and Software Architectures for Service Oriented Platforms 193.1 List of participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Compsys - Compilation and Embedded Computing Systems 214.1 Team Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.2 Self-assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.3.1 Vision and new goals of the team . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3.2 Evolution of research activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 D-NET - Dynamic networks 275.1 List of participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.3.1 Sensor network, distributed measure and distributed processing . . . . . . . . . . . . . . . . . . 295.3.2 Statistical Characterization of Complex Interaction Networks . . . . . . . . . . . . . . . . . . . . 305.3.3 Theory and Structural Dynamic Properties of dynamic Networks . . . . . . . . . . . . . . . . . . 31

v

vi Contents

6 MC2 - Models of Computation and Complexity 336.1 Team composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

7 Plume - Proof Theory and Formal Semantics 377.1 Team Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

7.3.1 Logical foundations of programming languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.3.2 Semantic tools for new behavioural properties of programs . . . . . . . . . . . . . . . . . . . . . 407.3.3 Formalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

8 Reso - Optimized Protocols and Software for High-Performance Networks 438.1 List of participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.2 List of participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.3 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.4 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

9 ROMA - Resource Optimization: Models, Algorithms, and Scheduling 479.1 List of participants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

10 IT Support Team MI-LIP 5310.1 Team Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5310.2 Self-Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5310.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

1. LIP general project

1.1 Context

Together with the scientific, political and structural evolutions of our environment, LIP’s growth is an important elementwe have considered for drawing up our project for the next years. In 2009, LIP has over fifty percent more members thanin 2005, and more than twice as many members as in 2000.

Computing (computers, communications, applications) is making major and crucial contributions to society’s progress. Inthe mean time, the amount of infrastructures making up the digital world continues to grow rapidly and starts to consumesignificant energy resources. Computing and digital resources, as well as their use, are our central objects of study,from both an abstract and practical point of view. Our main research directions are organized around two general andinterweaved key challenges:- addressing the complexity of future computational and communication architectures, and the way their design and use

efficiently match application constraints and needs;- inventing mathematical computer-science models and methods that contribute, beyond their fundamental aspects, to

algorithmic, software/hardware, and technological advances, as well as to the progress of other scientific disciplines.The machine—or the computer—is seen as either an abstract entity or tangible object. The “real” computer is a set ofprocessing, networking and memory resources (e.g., chips, multi-cores, embedded processor, grids, clouds, networkingand computing infrastructures, pervasive systems) whose combinations lead to a fantastic complexity. The machine is botha research target and a computational means for research. Facing its complexity, we put an accent on the way resourcescan be used in an optimized, trustful, and safe way. Topics regarding the study of the computer as an abstract entity, suchas mathematical computer science and algorithmics, are transversal to the laboratory. They deal with the invention of newparadigms, the modeling of our problems, and how to handle the change of scale of the problems we study. Moreover,a relatively recent and crucial change is that non-Computer Science disciplines need and adopt the computer science andalgorithmics “thinking”. Anticipating the repercussions of new computational concepts in other sciences, we participate toand support this revolution. Specifically in the context of Lyon and its region, strategic interactions with other disciplinestake place through applications in numerical and computational sciences, complex-systems modeling, biosciences, andcommunication and semiconductor industries.LIP’s tradition of creative interactions between fundamental research and innovative software and hardware production isa solid foundation for our plan.In this section, we analyze the evolutions of our context, from LIP’s environment to the international one. From there,we give an overview of LIP’s scientific project in Section 1.2 (more detailed projects will be given for each research teamand the IT support team from Chapter 2 to Chapter 10), and different aspects for conducting this project are addressed inSection 1.3.

1.1.1 LIP’s internal evolutions

Since 2005, our number of permanent faculties and researchers from CNRS, INRIA, ENS-Lyon, and UCBL, 45 now, hasincreased by more than 45%. Research activities are strengthened by the equivalent of 3 full-time permanent researchengineers, by 15 temporary research members, and by about as many PhD students as permanent members. For the 48permanent scientific members we have 1:

Arénaire Compsys Graal MC2 Plume ResoOct. 2005 5.5 3 (+2) 8 9 4 3.5Sept. 2009 9.5 4 12.5 5 7 10

During the last four years, grid projects such as Grid’5000 have brought about many synergies between the Graal andReso teams on the high-performance distributed platforms and networks thematic. Including all scientific members, thistheme (internet and networks, scheduling, distributed resources and services, high-performance computing) representsmore than half of the laboratory, and is highly productive. The scientific aspects related to the lab’s growth have beenconsidered regularly, in particular at LIP’s level, together with administrative questions. New points of focus have beenidentified that will lead us to modify LIP’s organization with new teams. Following the growth of the Graal research team,

1In addition to the three permanent researchers, Tanguy Risset and Antoine Fraboulet, both at INSA-Lyon, were part of Compsys, as INRIA project-team, until 2007. This is indicated as “(+2)” in the table.

1

2 Part 1. LIP general project

two new teams will be started in 2010, one on the design of algorithms and scheduling strategies that optimize the resourceusage of scientific computing applications and one on models and algorithms for service-oriented computing platforms.Research related to networking and network science will follow two axes. On one hand, the Reso team will deal withtraffic-awareness, network sharing, and energy efficiency in high-speed network infrastructures. On the other hand, theD-Net team will be launched and address problems related to the science of dynamic graphs and match this work to real-world complex networks. Research related to embedded systems, and more precisely synthesis, quality, and optimizationof programs (compilation and computer arithmetic, software/hardware), has been highly developed, especially within thecompetitiveness cluster Minalogic involving the Arénaire and Compsys teams. The convergence on code synthesis willcertainly be accentuated. Compsys has a small but quite stable number of permanent members, thanks to the hiring ofone new INRIA researcher. Arénaire has grown with researchers partly oriented towards mathematical computing. Moregenerally, LIP’s groups interacting the most with mathematics have evolved towards logic/semantic, algebraic, and appliedmathematics aspects (numerical analysis, statistics, etc.). After a lot of departures, team MC2, dealing with models ofcomputation and complexity, reveals a weakening that may have an impact on our discrete mathematics (automata, graphtheory) expertise. A long-term support is necessary for fostering MC2’s fundamental research. After a strong involvementin complex systems following the creation of the Complex System Institute (IXXI) in 2002, the team will re-concentrateits efforts on computational complexity and combinatorics, but also wishes to open up to new algorithmic themes likealgorithms for discrete-event systems. After a clear evolution, team Plume has gathered a much stronger expertise onlogic and formal analysis of computer programs.We have a number of strengths in algorithmics, algorithmic complexity, and fundamental and mathematical computerscience, which are transversal domains. In particular, the quality of the computation, and the optimized use of the re-sources are main concerns. Our 2005-2009 progress report presents our research and production in various branches offundamental computer science. The report also shows our ability to mix these aspects with more practical concerns andthe key role of our software/hardware design and developments, and transfer activities.The Complex System Institute (IXXI) is now an efficient and large structure independent from the laboratory. LIP’sinterface with the institute, whose weakening has followed MC2’s, will be strengthened with the creation of the D-Net team on dynamic networks. The main interactions with disciplines other than mathematics are through variouscomputational applications and modeling (including our IXXI collaborations): among these disciplines, bioscience is anemerging theme with projects in several teams.A notable consequence of our growth is that, since 2008, we have to work at three distinct locations on the Gerland site.To preserve the cohesion of the laboratory, we will encourage transverse research themes and pay special attention to thelab’s scientific and administrative life.

1.1.2 Main scientific evolutions

In addition to the political aspects that we will see in the next section, the main ingredients for working out our project havebeen the teams’ evolution and the key transverse themes drawn from this thematic progress. Among the main evolutions,we may point out:

Logical foundations of programming primitives. The Plume team has increased its expertise on mathematical andlogical tools for the study of programs, notably with linear logic, game semantics and realizability. This will allow us towork on the foundations of a larger set of programming constructs and to address new questions such as controlling thecomplexity of programs as part of the general question of analyzing resource usage.

Algorithmics of discrete event systems. The MC2 team plans to develop this research topic following its work aboutNetwork Calculus, a deterministic queuing theory for worst-case performance evaluation. Discrete event systems likePetri nets can be viewed as dynamical systems or as models of computation, and their analysis may require tools fromvarious fields like linear algebra, (min,+) tropical algebra, graph algorithmics or computational geometry. Some supportcan come from applicative fields like the analysis of communication networks and this theme may increase the interplaywith LIP’s other teams.

High-performance geometry of numbers and applications. The successful match of arithmetic expertise and Euclideanlattice expertise in the recent years encourages Arénaire researchers to tackle new applications at this new frontier, suchas lattice-based cryptography, MIMO decoding for wireless communications, new methods for the design of numericalfilters, and many others.

Ensuring performance and accuracy of larger computing cores. After successfully embracing elementary and com-pound functions of one variable, the Arénaire team wants to extend the notion of arithmetic core to even larger coressuch as functions of several variables, signal processing filters, linear algebra or pairing-based cryptography cores. The

§1.1 LIP general project 3

challenges are a better understanding of the bit-level complexity of these problems, the development of new specificmathematical tools, and a focus on automatic code generation and validation with more interactions with the compilationcommunity.

Program optimizations/transformations for embedded computing: just-in-time compilation & high-level synthesis.Rhône-Alpes’s context, with the semiconductor industry in the Grenoble area and competitiveness pole Minalogic, is anopportunity to push further research activities on compilation, architecture, and high-level synthesis, in close collaborationwith industrial partners. For programs, the diversity of architectures and the need for portability increases the interest forjust-in-time compilation, starting from a low-level platform-independent code representation. For circuits, the develop-ment of more mature industrial high-level synthesis tools creates a need for source-to-source program transformations (tobe applied at the front end of these tools). These two aspects are explored by Compsys.

Foundation of a science of dynamic networks. The main goal of D-Net team is to develop knowledge in the field ofnetworking science, so as to provide a better understanding of dynamic graphs from both analytical and structural pointsof view. In order to develop tools of practical relevance in real-world settings, we will base our methodological studies onreal data sets obtained during large-scale in situ experiments. The conjunction of real-world data with the development oftheoretical tools proposed in D-Net may impact various scientific fields, ranging from epidemiology to computer science,economics, and sociology.

The Internet’s architecture redesign aims at solving network-manageability, security and Quality of Service issues.High and predictable performance for emerging high-end cloud and computing applications remain indeed hard to obtaindue to the unsuitability of the bandwidth-sharing paradigms and communication protocols of the traditional Internet pro-tocol architecture. Reso will emphasize fundamental issues of network science such as bandwidth and network-resourcesharing paradigms, network-resource virtualization and scheduling, energy efficiency, traffic metrology and modeling,flow-aware quality of service and transport protocols.

Static scheduling of dynamic systems described with probabilistic models. In the past, most of the theoretical researchin Graal dealt with the design of static algorithms for static systems, i.e., for systems whose characteristics were supposednot to evolve during the lifespan of the studied problem (namely, the execution of an application). During the reportingperiod, the Graal team more and more focused on solutions for dynamic systems. The Graal team initiated its first workdealing with online problems. It has also begun to work on the design of static solutions for dynamic systems that aredescribed through probabilistic models, and will increase its effort in this domain.

Algorithms and software architectures for service-oriented platforms. The new Avalon team, started by severalresearchers from the Graal research team, will focus on algorithmics and software design research issues of softwareas a service (SaaS) and service-oriented computing (SOC) environments over grids, clouds, and P2P systems. Fromprogramming models down to middleware design and resource- and data-management heuristics, the efficient design ofthese important components of the future Internet requires some fundamental researches.

Complex systems and biosciences. Biosciences and bioinformatics are among the main research subjects of the Lyonarea. LIP invests resources in this direction: as a test application of computing on large-scale platforms (Graal and thefuture Avalon team); in relation with the Complex System Institute on modeling (e.g., spreading of pathogens, gene-regulatory networks) using fundamental computer science tools such as dynamic networks (D-Net), automata (MC2), orgame theory (Plume).

The teams’ evolution emphasize the duality of “computing” in the laboratory: the practical challenges related to futureinfrastructures, and their applications, rely on fundamental and mathematical computer science approaches. This dualitywill provide our two main transverse areas. On practical aspects, our common concern is inventing new tools for resource-usage optimization, and improving security and quality of computing. Beyond the lab, this common concern is a strongbasis for enlarging our collaborations in computational sciences. On fundamental aspects, original and sophisticatedmodels and methods will produce frameworks for concepts to be stated, and new computational approaches. FundamentalCS research is also essential from a multi-disciplinary point of view.

1.1.3 Local, national, and international evolutions

Lyon evolutions. The French reform is illustrated by the creation of the PRES Université de Lyon and the developmentof Lyon Cité Campus (Campus plan), with scientific orientations focused on health science and modeling complexity. LIPfinds a motivation in this clear global dynamic of the city for gaining a foothold in local collaborations. In particular


we may refer to the Blaise Pascal Center on numerical science, and to the Numerical Science & Modeling Federationproject. The increasing involvement of UCBL with LIP is illustrated by the fact that one third of our faculty members2

occupy Lyon-1 positions. The reform is also illustrated by the application of the LRU law—Loi relative aux libertés etresponsabilités des universités—at ENS and at UCBL. Together with the new ENS school, this may modify the respectiveroles (local versus national) of our four heading organizations regarding, e.g., logistics, scientific policies. Since 2008, webelong to a new and enlarged Doctoral School, and since 2009 to the enlarged UCBL Faculté des Sciences et Technologies.

Regional and national evolutions. CNRS and INRIA play key roles at both the regional and national levels. Duringthe last four years, they have provided about 1.6MC3 either directly to the laboratory, to the teams, or on specific actionssuch as postdocs, invited positions, and international and risk projects. During the same period, the corresponding globaloperating budget has been 8.6MC. The start of CNRS INS2I institute (national) and collegiums (regional) is expected, inparticular, to increase computer science recognition and the cooperation with other disciplines at the regional level. Alongwith long-term research, our positioning with respect to CNRS’s strategic plan 2020 (and the 2009-2013 CNRS-Étatcontract) especially touches: the complexity of computing and communicating infrastructures, with reliability, securityand energy challenges; the interaction of computer science and mathematics for novel methods, in relation with the INSMIinstitute. The national GDR CNRS structures, in particular with respect to the animation of scientific communities, aremajor instruments for our fundamental research, and its visibility. We are highly involved for example in the GDR“Informatique Mathématique” or “Architecture, Système et Réseau”, and in the recent GDR “Calcul”.About 80% of LIP scientific members belong to one of the four joint INRIA project-teams, and are highly involved inthe life of the Grenoble - Rhône-Alpes research center. LIP is positioned with respect to the current 2008-2012 INRIAstrategic plan especially following three priorities: reliability of computing systems; computation and internet of thefuture; software synthesis and compilation for embedded systems. We are positioned with respect to INRIA’s regionalpolicy on mastering dynamic and heterogeneous resources. We may emphasize INRIA’s support to our participation tothe regional competitiveness cluster Minalogic, and to our industrial collaborations with STMicroelectronics and Alcatel-Lucent through national contracts. The re-organization of the STMicroelectronics research objectives, in collaborationwith CEA and INRIA, towards the development of a multi-core platform (Platform2012) may also offer new collabo-ration opportunities. INRIA’s increasing strength in Lyon also defines priorities in biosciences that could represent newopportunities for us.Numerical and computational sciences are important priorities identified at the regional level by our heading organiza-tions. Our upstream research on the design and the use of computing and communicating infrastructures, such as withinthe Grid’5000 project, creates opportunities for transferring our methods to other domains. Through projects on gridcomputing or embedded systems, and our participation to, e.g., the Fédération lyonnaise de calcul haute performanceand the Rhône-Alpes regional cluster “Informatique, signal, logiciels embarqués”, we also find various opportunities forcollaborating with other disciplines (life-science computing, signal processing, high-performance numerical solvers, etc.).During the last four years, the global CNRS, ENS, INRIA, and Lyon 1 funding has represented 29% of our budget (re-curring fundings determined by the four-year plan have been about 8.5%). The ratio was over 36% during the previous2001-2004 plan. The corresponding total budgets are 8.6MC and 3.4MC, hence the major change in the proportionreflects a quick increase of external fundings, rather than lower organization fundings. Among the former, fundings fromthe Rhône-Alpes region represent 15% of the total budget, and those from the national research agency (ANR) represent27%. Hence ANR is now an important actor whose programmation gives a new level of scientific orientations. This is animportant tool for funding the theoretical sides of our research, especially through the “white programs”. Our industrialcontracts represent 5.5% of the total budget. This proportion does not accurately illustrate our industrial collaborations.Indeed, beyond the fact that budget measurements should not be the only indicators, we point out that regional, ANR, orEuropean projects may involve industrial partners, or may be related to industrial contracts.

International evolutions. ANR, with somehow simpler administrative approaches than European ones, has probablyreduced the level of our efforts for European fundings. However, our European participation remains at a high level.The fundings represent about 22% of the total budget, i.e., 1.9MC. The main projects are, for instance, on grid andinternet infrastructures, complex systems simulation, or life science and health, together with Marie Curie actions (trainingnetworks and fellowships), that is now within FP7 “Cooperation” and “People”. The European positioning of the newENS school may enlarge our sphere of collaborations. CNRS and INRIA Offices for International Relations (DREIand DRI), and ENS, increasingly provide a key support and framework for innovative international risk projects. Thisincludes fine-grained starting collaborations (Italy, Serbia, USA, Australia, Brazil, etc.), standardization actions (IEEEfloating point or interval arithmetic standards), international associated teams (metagenomics on grids, LIP-U. Hawaii),or co-agreements for student supervision.

2by faculty member we mean people who teach and research, by opposition to full-time researchers.3All budgets here are non-consolidated.

http://www.cbp.cecam.fr/tiki-index.php


1.1.4 Strengths and opportunities

LIP produces high-quality research results. This is assessed by our publication track, our involvement in communities, ournational and international collaborations (academic and industrial), our funding sources, the distribution of our software.The researchers we attract and the strengths of LIP’s teams allow us to regularly re-consider our research directions, whichoften leads to important emerging themes. The combination of our four heading organizations institutions is a key added-values for the laboratory. With the complementary supports and policies of our organizations, and with their respectivestrengths, we are in a privileged and attractive situation (research resources, students’ level, etc.). We are somehow betterprepared to further potential changes, for example if a French computer-science alliance between our organizations iscreated.Our scientific project is built on another key combination: our expertise in both fundamental and practical computerscience. This allows us to take advantage of a number opportunities. Among those, the national and international poli-cies tend to recognize computer science as being an actual science, albeit a relatively young one. We are positioned toaddress the crucial needs in new computer science models, methods, and algorithms. The city, region, and national multi-disciplinary policies on computing and mastering resources, represent a unique opportunity for our practical computerscience approach. In addition, in the progress report, we have demonstrated our strength for handling various national andlocal industrial collaborations.

1.2 Scientific project

As already mentioned, computing (computers, communications, applications) is making major and crucial contributionsto society’s progress. Technological impact and ubiquity of resources are usually perceived by society as “embeddedand pervasive computer systems” and “physical and virtual infrastructures”. However, in addition to the technologicalprogress, a relatively recent and crucial change is that non-Computer Science disciplines need and adopt the computerscience and algorithmic “thinking”. A main challenge is to participate to and support both aspect of this revolution. Ourpositioning is to study together future infrastructures and theoretical frameworks, specifically to invent computationalconcepts, while anticipating their repercussions in other sciences.The machine, either real (embedded, distributed, pervasive) or abstract, is both a research target and a computationalmeans for our research. Mastering its complexity, especially the optimized use of resources, requires long-term efforts,and its quick change forces us to regularly adapt and adjust our points of focus. Computing and digital resources, as wellas their use, are our objects of study. Facing the increasing and quickly changing complexity of the machine paradigms,we put an accent on the way computational and networking resources can be used in an optimized way, trustfully, andsafely. Mathematical computer science and algorithmics are topics transversal to the laboratory, in particular for proposingnew theoretical frameworks.On one hand, technological progress increases the complexity of machines while improving their computational andnetworking capabilities. This induces the need for new studies to acquire the knowledge needed to harness the power ofthese new machines. On the other hand, our research often takes advantage of the new computation power to improveknowledge, namely by allowing to perform more exhaustive simulations and experiments. In return, the technologicalchoices for future infrastructures may be influenced. The “abstract” computer (or any computer that could ever be built)especially shows that the computer is not only a tool, but a fundamental object of research in its own right. Studying bothreal and abstract machines, in most groups of the lab, is one of our main and solid strength. This allows us to make andpreserve a bridge between theoretical and practical computer science, and is a key source of invention.About the computer and beyond the computer, the traditional collaboration between computer science and mathematicsleads to innovative models and methods. These benefit to both disciplines. At this junction of mathematics and computerscience, we also address computational science challenges. As the scope and importance of problems that are posed tocomputers grow, it is essential to design new approaches, algorithmic tools, and software solutions to tackle them. Thecomputer science and algorithmic “thinking” is now widely applied for modeling various complex phenomena, whichrepresents another important axis of our collaborations with other sciences.

Two main transverse areas. LIP is a key place for taking advantage of various scientific competences, approaches andstrategies. LIP has a successful tradition of a balanced and efficient mixing of theoretical and practical aspects, as wellas long-term and project-based research headed by multiple heading organizations and scientific governances. To takeinto account our scientific evolutions and our recent growth, a first element of our project is to re-organize the laboratoryinto 8 teams and project-teams. In addition to a sustained help to the teams’ points of focus, the policy will be to fostertwo main transverse issues, with two sub-issues each, that cross-fertilize fundamental, applied, and technological aspects.These issues, deduced from our analysis, and according to the scientific policies of our heading organizations, representthe added-value of the laboratory level:


I. Addressing the challenges of future computational and communication architectures

I.a. Automation and specification for quality, optimization, and reliability of computation and communication

I.b. Methods, algorithms, and software/hardware architectures for future infrastructures

II. Mathematical computer science models, methods, and algorithms

II.a. Mathematical methods and algorithms

II.b. Models, logic, and complexity for programs and systems

The two issues are seen as shared challenges and directions within LIP, independently of the division of the laboratory intoteams. This is presented below with a general point of view, and with more details by teams from Chapter 2 to Chapter 10.Fundamental algorithmics acts as a binder between the two issues, in particular with parallel algorithmics which is quiteubiquitous.

New project-teams. All teams show major scientific evolutions. Nevertheless, four teams continue for the next plan:Arénaire on Computer arithmetic; Compsys on Compilation and embedded computing systems; MC2 on Models of com-putation and complexity; Plume on Programs and proofs. The Graal team leads to two new projects with two complemen-tary aspects of parallelism: Roma on Resource Optimization: Models, Algorithms, and Scheduling ; Avalon on Algorithmsand Software Architectures for Service Oriented Platforms. The team Reso on Optimized protocols and software for high-performance networks, is refocused on the future Internet, and after a two years incubation within Reso, the D-Net teamon Dynamic networks is created.

Combining practical and theoretical challenges. There is a strong interdependency between issue I, the quick techno-logical development, and the infrastructures’ constraints and complexity. We build on complementary research on hard-ware and software synthesis, compilation (Arénaire, Compsys), distributed architectures and networks (Avalon, D-Net,Reso, Roma). The computer and its components are changing; via modeling and abstract approaches, we design new toolsto anticipate the changes, to study their impacts and design new approaches that cope with them, and to widen our targetarchitecture spectrum. More directions in formal analysis (Compsys, Plume), the minimization of energy consumption(Compsys, Roma, Reso), and safety and security questions (Arénaire, Plume) will be encouraged.The second issue with II.a, about the study of “purely” mathematical objects, concerns all the teams. Algebra, geometryof numbers, logic, graph theory, combinatorial approaches, optimization, statistics, and numerical analysis are key math-ematical themes on which we strongly rely, and that may benefit from our algorithmic progress. Issues that directly comefrom computer science’s own mathematical concepts, and that mostly relate to abstract machines, expressiveness, mod-eling, and programs, give issue II.b, where for instance languages (Plume) or problems (MC2) are mathematical objects,where abstract parallel models are designed (Roma), and where we work on expressing numerical quality (Arénaire).The two issues are interweaved through most teams. Long-term fundamental progress guarantees our strength for in-venting and anticipating computer evolution (ex: distributed algorithmics, scheduling, optimized and reliable resourceusage, quantum computing). We conceive both theoretical and practical machine models. Our fundamental studies onmathematical problems, for example to provide optimized solution algorithms and implementations, identify needs (e.g.,new scheduling model and strategy, new type of arithmetic operator), and provide test applications for our practical de-velopments (e.g., linear algebra, cryptography, Euclidean lattices, signal processing). LIP has long been at the forefrontof this effort. Conversely, empirical progress, and invention of theoretical models, may emerge from the abstraction ofpractical phenomenons (e.g., metrology and models for the future Internet, spread of diseases), or upstream objects (e.g.,abstract formalization of recent and challenging programming construct, modeling of multi-core architectures, mathemat-ical framework in code optimization). Test applications are also used to validate (fundamental) hypotheses or proposedsolutions.Our research, especially regarding Issue I, strongly relies on experimental computing and communicating platforms,including grids, sensor platforms, and FPGA platforms and board. We plan to encourage risk initiatives and equipmentsin this direction, jointly with the development of software platforms (HPC, SOC, networking, synthesis tools). Thelocal and national experimental equipments in which we are involved are the crucial research facet of high-performance(production) equipments.

Cross-fertilization with other disciplines. Computational and numerical sciences are major priorities of our headingorganizations. From hardware signal processing with Alcatel-Lucent and STMicroelectronics, and high-level synthesis,to the AFM-CNRS-IBM Décrypthon project, and intercontinental service computing, our main collaborations with disci-plines other than mathematics fall into this challenge. We mainly exchange on new algorithms, program optimizations,middlewares, and large-scale experimentations. The Lyon and Rhône-Alpes context is very favorable for strengthening


these aspects within the theme:

Cross-fertilization with other disciplines, and application domains

a. High performance for computational sciences

b. Computer-science models, complex systems, biosciences

where we especially find our participation to the Numerical Science & Modeling Federation project, the renewal of ourcollaboration with the IXXI institute through the application of dynamic graphs, and biosciences applications.

From fundamental research to startup companies. The fact that LIP is well-known for its high-level fundamentalresearches should not hide the importance and quality of our software developments. In 2009, three startups were initiatedin three different research teams: Graal Systems issued from Graal, LinKTiss issued from Reso, and Cosmo issued fromMC2. Researchers and engineers from each team will be involved in these creations and our theoretical results as well assome of our software prototypes will be transferred.

1.2.1 Addressing the challenges of future computational and communication architectures

During the previous plan, synergies have been mainly created on one hand between Graal and Reso, and on the otherhand between Arénaire and Compsys. Our project is to enlarge collaborations and take advantage of complementaritiesbetween “all” lab groups for which the machine plays a key role. A common concern is the optimization of resource usagein computing. The teams of the lab address this issue at different levels with various approaches. Although the objects,methods, and goals of these teams widely differ, some convergences can be observed. At this level again, two transverseand interweaved sub-issues may be identified. The first one is more directly related to the optimized solving of non-CSproblems. The second one is dedicated to “pure” CS problems.

Automation and specification for quality, optimization, and reliability of computation and communication. Avalon,Arénaire, and Roma, specifically consider application domains. These application domains are mostly at the interface withmathematical/scientific computing (e.g., linear algebra, signal processing, data-intensive applications). The challengesare then to design and synthesize algorithms and codes, and to conceive new software tools that automatically applyour (human) expertise. In addition to resource usage, the issues of HPC implementations, of accuracy/quality, and ofreliability, are increasingly important for all. We also target automated code validation, and explore machine-checkableproofs. Plume provides the necessary interface with semantics, specifically through proof assistants. For example, linearalgebra kernels, sparse direct solvers, lattice-basis reduction libraries (specifically Arénaire and Roma) lead to commonneeds to fully harness the computational power of multi-cores. LIP is the place where a common culture can be built.Security questions are currently less considered, the lab should make progress on these questions (e.g., cryptography,security issues with internet redesign).

Methods, algorithms, and software/hardware architectures for future infrastructures. At the heart of CS questions,two major points of convergence are on computer/networking/sensor platforms and software/synthesis tools. All teamssomehow target common complex infrastructures and developments for which the lab policy will be to provide additionalhuman and material support. The issue of power consumption, once reserved to embedded systems (Compsys, D-Net), isnow shared by all. Reso, Roma and Avalon target “classical” objectives such as platform utilization, and execution time ortraffic load, but also the crucial energy consumption one. Regarding statistical characterization of traffic, research carriedout in Reso ranges from technological (Metroflux) to methodological and theoretical issues. The underlying objective isto make “traffic awareness" a full constituent of future networks, allowing differentiating the flows’ treatment accordingto their generating application.Arénaire works at the microscopic level, studying how to improve basic computing units (operations and elementaryfunctions) in software or in hardware. Compsys works at the compilation level, studying how to make the best use ofthe available execution units and memory units of a processor. D-Net works at the hardware/software level, studyingcross-layer approaches to provide an optimized mapping of a software protocol on a hardware device, and to study howto optimize the life time of embedded sensors by performing activity scheduling. Avalon works at the middleware level,studying how Service-Oriented Computing platforms can scale to the Internet level. With the widespread use of multi-cores, parallelism and scheduling problems are now ubiquitous. This should lead to stronger team collaborations aroundthe understanding of how the characteristics of new architectures impact classical CS problems and our previous works.As very-large-scale platforms and networks may be failure-prone, reliability is a challenge shared by Avalon, D-Net,Roma and Reso. The teams target reliable algorithms or protocol implementations that are able to cope with the volatilityand dynamicity of platforms and equipments. General points of convergence, specifically for Avalon and Reso, are aboutvirtualization and quality of service.


1.2.2 Mathematical computer science models, methods, and algorithms

We have mentioned that making bridges between theoretical and practical computer science is an important source ofinvention. We have also mentioned how effective the collaboration between computer science and mathematics is forproducing innovative models and methods. Conceiving and applying abstract/theoretical tools is a concern commonto LIP’s teams. In the first sub-issue we mostly apply our expertise in various mathematical domains to complexity,modeling, and algorithmic progress. The second sub-issue deals with CS progress about theoretical algorithmics, newabstract machines and models, logics, semantics, programming models, and graph theory.

Mathematical methods and algorithms. This issue concerns all teams, and has a key role for LIP’s cohesion as there area lot of scientific interactions on this subject. In particular we strongly rely on: category theory, logics, graph theory,combinatorial approaches, algebra, number theory (in particular, geometry of numbers), optimization, statistics, andnumerical analysis. This expertise is essential for our technological, algorithmic, and software progress. We may illustratethis with some key examples for the future.Tools from more traditional mathematical theories are used to study computer-science problems. For instance, in Aré-naire and MC2, works in algebraic and algorithmic complexity naturally involve algebra, in particular polynomial algebraand number theory. The latter field is used by Arénaire to model and solve various practical problems of efficiency orreliability of computations. Arénaire works in geometry of numbers and, for instance, investigates challenging applica-tions of Euclidean lattices in cryptography and computer arithmetic. The combination of its expertise in arithmetic andhardware implementations with a deep knowledge of algebraic curve-based cryptology allows Arénaire to take part to thedesign of optimized hardware implementations for pairing-based cryptography. A characteristic of Compsys is its focuson combinatorial optimization problems (e.g., linear programming methods, polyhedral optimizations) coming from itsapplication field, the automation of code optimizations. In this context, mathematical and operation research tools areboth used and developed. In HPC linear algebra and lattice reduction, as well as in the process of design of functionevaluation libraries, numerical analysis plays a key role for conceiving more efficient automatic tools and solutions, whileimproving (or preserving) the numerical quality (Arénaire, Roma).Probability theory and especially stochastic processes is used in MC2 to study the behavior of probabilistic cellularautomata. Statistical signal processing is present in Reso’s activities in at least two prospects: application-oriented clas-sification of flows and study of scale-invariant properties in traffic traces. In the latter case, we aim at providing accuratecharacterization and estimation of the diverse forms of scaling laws present in traffic: long-range dependence, local Hölderregularity and multifractal spectra. Reso also works at identifying new multifractal scaling laws in long-lived TCP flowsand at proving large deviation theorems to ensure that the same properties hold with adequate models devised for TCPprotocols.

Models, logic, and complexity for programs and systems. With this issue we address mathematical CS concepts relatedto logic, abstract machines, modeling, and programming. Most of the work of MC2 and Plume can be categorized inmathematical computer science, with contributions to the development of new, computer-science oriented, mathematicaltheories. For instance, there are rich mathematical theories of computational complexity or of cellular automata. Implicitcomputational complexity gives logical characterizations of an increasing number of complexity classes by means oftyping systems. This is a complementary way, with respect to more traditional algorithmic complexity, to study thecomplexity of programs (Plume, MC2). Roma always starts a new study by formally assessing the complexity of theproblem at hand, and by checking the influence of different hypotheses on the complexity of the problem (homogeneity ofcommunication capabilities, for instance). For NP-complete problems attempts are made to derive as precise as possible(theoretical) bounds on the performance of the optimal solution.Plume deals with logical foundations of programming languages with a specific focus on trying to enlarge the spectrum oflogically understood programming primitives (e.g., concurrency, probabilities, imperative features, control) and softwareproperties (e.g., termination, complexity). Unifying the known approaches by means of linear logic, game semantics,or realizability theory is a key goal. This includes the theory of parallel programming to provide abstract tools forguarantying safety properties of computation, and to define semantically founded core-programming languages such asprocess algebras. The need for formal proofs of program properties requires progress on the foundations of mathematicsas well as a specific understanding of the constraints underlying the development of proofs in proof assistants. The latteris related to the application context of the proof, and makes the bridge with the work of Arénaire about specification andproof aspects for the reliability of programs.In order to harness the complexity of incoming machines/platforms and new applications, programming models needto be investigated. Challenges include identifying pertinent programming concepts with two major constraints. Theyhave to be simple enough to be manipulated by programmers and to be based on solid foundations to enable efficientexecution on a large variety of hardware, which can moreover be dynamic. A promising research direction is to work withmeta-models to transform high-level models to models closed to the execution environment. Successful preliminary work


has already been started by the Avalon team with software component models. Service-Oriented Computing platformsand middleware systems need models and algorithms for several design issues such as service discovery, deployment,composition and orchestration, etc. Roma’s studies are always based on platform models. These models must be preciseenough to enable the prediction of the algorithms’ behavior when deployed and run on the actual platforms. But thesemodels should be simple enough to be analyzable. Hence the need to find good trade-offs. Specifically, models will bedefined to base the work on multi-cores.

MC2 has been one of the French pioneers in the study of graph decompositions (in particular, tree decompositions) andhas remained actively interested in this subject. Graph decompositions were introduced originally with a purely mathe-matical motivation, but turned out to yield efficient algorithms for a huge variety of problems. Roma will pursue its workon hypergraph partitioning. The underlying idea is to extend the existing hypergraph partitioning approaches to allow theirapplication to new contexts. Currently, Roma uses hypergraph partitioning to solve problems that are often homogeneousin nature. The team will study how to enrich hypergraphs in order to use them to solve heterogeneous versions of theseproblems. D-Net will continue working on dynamic graph models for network science. This emerging and promisingdomain has proposed a stream of studies aimed at identifying more properties, their causes and consequences, and cap-turing them into relevant models. One goal is to use such models as key parameters in the characterization of complexityclass for distributed algorithms on dynamic networks and for the study of various phenomena of interest like robustness,spreading of information or viruses, and protocol performance for dynamic networks.

1.2.3 Cross-fertilization with other disciplines, and application domains

High performance for computational sciences. Since LIP’s creation, several teams have started collaborations withscientists from other fields of science. From fundamental algorithms and models to the validation of parallel algorithmsand applications over clusters and grids, these exchanges have always been beneficial for the researchers of every disci-pline. More recently, the Blaise Pascal Center and the Numerical Science & Modeling Federation allow starting moreformal collaborations. More than just sharing clusters and supercomputers, both research instruments will allow strongcollaborations between LIP experts in high-performance computing and scientists from other fields like physics, chem-istry, applied mathematics. LIP will also provide an expertise at the interface between numerical analysis and computing,about improving the numerical quality of results in HPC. Lectures will be given by LIP researchers, and national andinternational collaborations will be started.

Link with microelectronics, electrical engineering, and the semi-conductor industry. Computer science is a naturalbridge between mathematics and electrical engineering, from more formal aspects to real hardware developments. Thecompetitiveness pole Minalogic and the Rhône-Alpes region with several semi-conductor indutries or research centers(e.g., STMicroelectronics, CEA) offer opportunities to work with specialists of embedded-systems design, circuit synthe-sis, micro-electronics, power consumption, and embedded applications. Compsys and Arénaire participate to this inter-disciplinary effort where computer science, through formal methods and software developments, is becoming essential.Collaborations are also developed with other micro-electronics labs in France (e.g., LIP6, Lab-STICC).

Computer-science models, complex systems, biosciences. In biosciences collaborations were started between LIPresearch teams and other laboratories in the Rhône-Alpes region and France. The Décrypthon project between AFM,CNRS, and IBM offers the access to two grids (a server-based grid and a desktop grid) and the expertise of the Graalresearchers for studying application design over such large-scale platforms. Graal also works with researchers of theINRIA project-team Bamboo based in the Laboratoire de Biométrie et Biologie Évolutive (UCBL) on the automaticgeneration of protein domain families. The fundamental objective of this collaboration is to enable bioinformaticians tocope with the exponential increase of the size of biological databases by using the power of distributed computing. Anotheraspect of our investment in biosciences is related to IXXI. D-Net targets inherently multidisciplinary goals, specificallyregarding “Social/Human Dynamics" and “Biology – Health". One goal of D-Net is to tackle the problems associated withthe spread of infectious diseases over dynamic social networks, and propose novel tools and models. The real networksunder direct study represent an example of human and social interactions, and their study will yield interesting insightsinto human dynamics. Moreover, the main dynamical processes to be studied are spreading of pathogens, which representan important public health issue. Although complex systems will be less prominent in its activities, MC2 too has initiatedprojects linked to IXXI and biosciences. A main objective is the study of some dynamical discrete systems like cellularautomata, boolean and gene-regulatory networks, as well as self-assembly tilings, with an emphasis on their combinatorialand algorithmic aspects. In Plume, game theory and Nash equilibria are applied to the study of gene-regulatory networks.


1.3 Implementing the project

LIP members are highly creative and motivated by their projects, hence the laboratory builds on strong foundations. Thenew team organization and the future directions reflect our own evolutions and those of the international, national, andlocal contexts. Below we describe the main risks we face, and then we review the main ingredients of the laboratory’spolicy for the coming years.

1.3.1 Weaknesses and risks

The increasing administrative workload for researchers, and administrative and technical staff is a concern. The rapidincrease of the lab’s size is a very good sign. However, it requires paying attention to our administrative organizationand infrastructures. The ratio between the numbers of administrative staff and scientific members remains quite low,especially with respect to the increasing importance of project-based research (contracts and temporary human-resourcemanagement, evaluation processes, etc.), and the numerous funding sources. With the LRU law, the AERES evaluationprocess, and the evolutions of research organizations, crucial changes are happening very quickly. These changes havebeen quite time-consuming for LIP’s researchers in 2009. The autonomy implies an increased local accounting that mayalso have an impact on the administrative responsibilities of the researchers (budget rather than position management).The French reform and the evolution in many countries leads to a pressing demand for bibliometric measurements, andindicators in general. The computer-science community, whose production is revealed through very diverse aspects, maybe extremely sensitive to that demand. Researchers hope for a careful use of the measures, especially with respect to theirpolitical impact, and their effect on scientific orientations.Our association with multiple organizations has always been a major strength. With the LRU, the larger autonomy ofthe organizations may partly hinder their synchronization, and in turn LIP’s running (multiple scientific policies, contractnegotiation, administrative deadlines, etc.). Local tools such as the INRIA-ENS outline agreement, aspects of the CNRSinstitutes, and the PRES should ease communication. As recommended by the expert committee of our previous evaluationin 2006, our collaborations at the Lyon level have been clearly strengthened, especially at the teaching and doctoralprogram level. With a project well-positioned with respect to the research policy of the University of Lyon, we shouldcontinue in this direction.Some of our objectives are essentially related to the technological progress that we must anticipate, and to our managementof pioneer experimental facilities. Together with long-term software development and maintenance, this requires sustainedinfrastructure investments, and engineering support. An under-dimensioned support could impede our objectives. As seenin the progress report, our quick growth also requires an efficient training and research strategy for increasing the numberof doctoral students (and PhD grants) in an international context that may not be favorable, especially in computer science.The fact that we are working on three geographical sites requires special efforts (scientific events, transverse initiatives,etc.) to preserve the laboratory’s added-value and cohesion in research and teaching.

1.3.2 Governance and animation

A main change will be the laboratory’s organization in 8 teams. The non-INRIA teams are stable. Plume is headedby O. Laurent since Jan. 2009 when D. Hirschkoff became vice-head of the lab. MC2 is co-headed by P. Koiran (on atwo-year leave in Toronto) and É. Thierry since Sept. 2009. The organization of the INRIA project-teams also dependson the projects’ life cycles at INRIA. The thematics should however remain globally stable. Arénaire had to modifyits organization after G. Villard took the head of the laboratory. F. De Dinechin has the co-responsability of the team,especially for preparing the 2010 INRIA project evaluation. Compsys remains headed by A. Darte, and Reso by P. Vicat-Blanc Primet. Graal will split into two project-teams, Avalon and Roma headed by F. Desprez and F. Vivien, respectively.D-Net is in the process of becoming an INRIA project-team headed by É. Fleury.The Laboratory Council will be modified from 16 to 18–20 members. We do not think we will have main changes toour current model of governance which is very effective. We will keep frequent Council meetings (every other week,currently) for discussing the main strategic points as well as everyday questions, and General lab meetings four times ayear. The heads of teams and the direction meet frequently. The effective interfaces with the CS Department, the Écoledoctorale, the “Teaching council” (graduate CS studies) and the “Commission des habilités” (lab supervision of doctoralstudents), will remain unchanged.The scientific animation of the laboratory must take into account our growth, diversity, and geographical situation. Inaddition to the teams’ seminars–which are very good tools—we will encourage transverse seminars. For instance, a Coqseminar will start for 2009/2010, in particular between Arénaire and Plume, and the Embedded-computing day will beorganized again with STMicroelectronics. Beyond the lab and students seminars, we plan to organize general scientificevents for the lab such as a retreat, new-members day, PhD day, etc., that we did not organize in the past. We will alsoencourage invitations of young researchers. The activity and budgets of the teams tend to provide more fundings for thelaboratory’s scientific policy, which allows supporting the aforementioned plan.


With various objectives (e.g., LIP database, research reports, bibliographic statistics, preparation of reports and evalua-tions) we plan to pursue our policy of using the French repository HAL to give access to all of LIP’s publications in thefuture.Our partnership with INRIA is reinforced in 2009 with a first annual ENS-INRIA meeting (July 2009) for discussing issuesrelated to INRIA project-teams. We expect our future associations to be discussed between our four current organizations.The CNRS INS2I institute at the local level, and UCBL and ENS with the University of Lyon, should also help ourpositioning (especially with respect to other CS labs), partnerships, and running at the Lyon level. Indeed, it seems thatmore and more strategic points will be discussed at this level.

1.3.3 Personnel

The main aspects of our policy are to: look for outstanding applications and foster emerging themes on the long term;preserve the stability of the groups and domains of the lab; help to balance the involvement of the heading organizations;strengthen our two scientific axes together with their interweaving, and links with other disciplines in relation with theexisting policies at the regional level.

Faculty members and researchers. To foster the development of all the teams and the diversity of our teaching, anelement of our hiring policy at ENS or UCBL will be to balance positions among teams. An important point is to haveenough senior positions in every team to ensure a long-term existence to important themes. Another point is to encouragethe balance in terms of number of people per organization. In particular, we may plan to prioritize UCBL positions on ourmost theoretical/mathematical themes. At the Professor level, we will favor scientific and administrative leadership, andnew themes on the long term. Assistant Professor hirings should strengthen existing or newly created axes. At INRIA, thelast years’ growth is not expected to continue. However, as well as for CNRS, we will continue our policy of attractingcandidates at the highest level, and taking advantage of the ease of mobility at the national level. Our policy will encouragepostdocs stays that are important for helping PhDs find positions.

Doctoral students. LIP members are highly involved in the hiring, progress, and future of PhD candidates. To takeinto account the growth of the laboratory, and preserve the quality of our students and our supervision ratio, we workon the international opening and evolutions of our Master’s teaching and Doctoral Program (see Section 1.3.4 below).Students are followed at the lab level by the Commission des habilités (at the interface with the Doctoral School). Thiswill continue, especially regarding research progress and production, continuing training, and teaching.

Administrative staff. At the administrative level, after a very unstable and over-loaded situation during the whole periodof the four-year plan, we expect a clear improvement for January 2010. In the new situation we should have: two perma-nent ENS assistants—C. Iafrate and L. Lécot—and one CNRS permanent one (hiring in Dec. 2009). We do not have anyinformation about the future plans of the CNRS assistant on extended maternity leave since 2006 (C. Desplanches). ThreeINRIA assistants will be, at least partially, working for the laboratory and LIP project-teams: S. Boyer, E. Bresle, andC. Suter. These assistants will also work for project-teams outside LIP. Very regular discussions with INRIA administra-tion allows a smooth running of the assistant service, especially for balancing the loads between work for LIP and workfor outside teams. Our short-term objective is to start 2010 with a stable staff representing the equivalent of 5 full-timepermanent positions, then increase the staff over the following years. As soon as our unstable situation ends, the objectiveof our policy will be to improve the diversity of their tasks, mainly through scientific-administrative aspects more closelyrelated to the teams’ objectives and life (e.g., funding management, organization of scientific events). Over the reportingperiod, some administrative tasks were moved from the administrative staff to researchers. We may note that a first steptoward our objective is for the administrative staff, in the near future, to be able to reclaim theses tasks.

Technical staff. LIP is organized with an IT support team of three permanent engineers: J.-C. Mignot (CNRS), D. Ponsard(CNRS), and S. Torres (ENS). The team is highly effective in a key support for IT research infrastructures, from networkservices and everyday computers, to experimental and pioneer platforms, with the exception of FPGA platforms andboards for which we are lacking skills and manpower. Also due to insufficient manpower, it is difficult for the IT supportteam to be involved in software development and/or maintenance. The objectives of the team are detailed in Chapter 10.For the effectiveness of the services, we will pursue the policy of partly involving the engineers in research projects.The team is relatively under-dimensioned with respect to our needs. Our involvement in national and local infrastructureprojects (such as the INRIA ADT Aladdin and the Blaise Pascal Center and Numerical Science & Modeling Federationproject), and the evolution of our platforms, depend on the consolidation of the team. In addition to the IT team, wehave two permanent research engineers: É. Boix (CNRS, who manages a startup creation), and M. Imbert (ServiceExpérimentation et Développement, INRIA) working full-time on research projects (Graal, Reso). LIP objectives (suchas platforms evolution and hardware/software development on the long term) also depend on a more important permanent

https://www.grid5000.fr/mediawiki/index.php/Grid5000:Home


support. As analyzed in the progress report, on these aspects we heavily rely on temporary engineers whose number hasincreased quickly. Permanent positions are mandatory to enable long-term support to sophisticated software, since it canrequire a strong expertise which takes a long time to acquire. Permanent positions would ease a long-term laboratorypolicy on these questions.

1.3.4 Teaching and training

The involvement of researchers and academical staff in the teaching at ENS Lyon is already rather strong, and we expectthis to continue and even develop. Recent reforms (LRU, and the will, especially at ENS Lyon, to smooth the distinctionbetween academical and purely research positions) will certainly provide further stimulations in this direction.An important challenge that LIP and the Département d’Informatique will face is the evolution of the local Master inComputer Science. Starting from academical year 2009-2010, a renewed curriculum is offered. The main noveltiesinclude a stress on the importance of training periods in research labs (in France and abroad), as well as a 6-week periodof teaching sessions in the spirit of summer schools (concentrated in time, often focused on a rather specialized researchtopic) and a minor in complex systems. These courses will be liable to attract, beyond Master pupils, doctoral students aswell as researchers, and to enhance the visibility of the Master.We expect the renewal of the Masters Programme to be carried on and further developed in the next years. In doing this,it will be important to address the representativity of LIP’s research themes, which are becoming more diverse as the labgrows. This phenomenon must be confronted with the rather stable number of (local) students. The commitment of thenew ENS Lyon to strongly develop tight connections with other teaching institutions, at an international level, should offeropportunities to address these questions. Local and regional partnerships (notably Lyon and Grenoble) are also paths thatcan be explored.We also plan to further develop the collaboration with UCBL (Université Lyon 1), which is naturally based on the UCBLpersonnel working at LIP. The main challenge in doing this is to establish a balanced partnership, which would allow LIPto be present, with its expertise, in the landscape of Lyon, taking into account the evolving structures at UCBL (reform ofthe UFRs, in particular).Finally, a possibility in terms of training will also be offered by the development of the Blaise Pascal Center.

1.3.5 Infrastructure

Our objectives regarding hardware and software infrastructures are further detailed in Chapter 10. Particular emphasiswill be put on the diversification of our platforms (HPC, networking, synthesis tools, etc.) and on the support of soft-ware development. Another priority for the IT team is to enforce a security policy (Politique de sécurité des systèmesd’information, PSSI).As part of Lyon Cité Campus (Campus plan), our project (2-3 years) is to gather all LIP’s teams on a single location, atGerland. To stay as close to students as possible, we would prefer ENS’s site. The connection with ENS students remainsclearly central for our teaching activities. UCBL’s Gerland site would provide another quality site.LIP researchers evince great energy, and new opportunities will most certainly appear during the next few years. Theobjective of geographical grouping is quite motivating and will ensure the best possible realisation for our projects.

2. Arénaire - Computer Arithmetic

2.1 Team Composition

Permanent researchers: Brisebarre Nicolas (CR CNRS), de Dinechin Florent (MCF ÉNS Lyon), Hanrot Guillaume (PrÉNS Lyon), Jeannerod Claude-Pierre (CR INRIA), Lefèvre Vincent (CR INRIA), Louvet Nicolas (MCF UCBLyon1), Muller Jean-Michel (DR CNRS), Revol Nathalie (CR INRIA), Villard Gilles (DR CNRS).

2.2 Self-Assessment

Strong points The Arénaire team is unique in the world in its focus and breadth. Arénaire has a recognized expertisein hardware arithmetic, software arithmetic cores, arithmetic algorithms, floating-point design and use, validationand formal proof of arithmetic cores, number-theoretic tools useful to computer arithmetic, and linear algebra.Most other computer arithmetic research groups, in France or abroad, focus only on a few of these fields. Moreimportantly, this expertise is shared to a large extent by most Arénaire members.Arénaire is an attractive team, and there are still many areas where the team could grow while keeping its consistency(VLSI, cryptography, signal processing, languages, formal proofs among others).

Weak points The team puts very strong emphasis on software development, but receives comparatively little institutionalsupport for it. In particular, some of our projects lack the stability that a full-time engineer would bring.Arithmetic research should be driven by applications, and Arénaire has to keep looking for new interdisciplinary orindustrial cooperations.

Opportunities The publication of the Handbook of floating-point arithmetic, which targets a wide audience, shouldattract contacts and, hopefully, collaborations with people well outside our community.The interval standardization effort is both an opportunity to exploit the breadth of Arénaire, and an opportunity tostrengthen our common culture. The Arénaire expertise is also needed in other standardization efforts, in particularlanguage standards.In a wider sense, the team is open to research opportunities brought by new technology targets (such as GPGPU,reconfigurable computers, massively multicore architectures, nanoscale technologies, or quantum computing) ornew application domains.A great opportunity is the project refoundation in 2010, due to the 12-year age limit of INRIA project-teams.

Risks Being the largest team in France in traditional computer arithmetic presents some risks, for instance we have toensure that our former PhD students keep finding interesting positions. Being open to the wider community is thekey.Arénaire researchers suffer the current nationwide increase of research management tasks.This additional pressureleaves less time for research itself, degrades our working conditions, and might degrade the team’s atmosphere.

2.3 Perspectives

As long as computers compute, they will need arithmetic at their very core. Moreover, as long as technology evolves, thearithmetic units will have to adapt to its evolution. Arénaire researchers can be assured they always will have problems tosolve.However, we want to create evolution, not to follow it. This is often a long-term goal. It took twelve years to obtain thestandardization of correct rounding of elementary functions. It took six years before formal proof tools could routinely beused in Arénaire when designing arithmetic cores, and it may take as long before they are routinely used by our colleagues.Pairing-based cryptography or multiple-precision interval arithmetic are other examples that need long-term laboring.If we take as a starting point the two historical research directions of the team (building better operators, and making bestuse of the existing operators), three major changes in the research activities of the team have been initiated in the previousyears, and are expected to evolve further:

1. The notion of arithmetic operator has gotten coarser and coarser. What we will call “arithmetic operators” isno longer limited to hardware operators for addition, multiplication, or division. It already includes elementaryfunctions and numerical kernels such as linear algebra operators and FFT.

13

14 Part 2. Arénaire

2. The two historical directions, initially carried by different researchers, have turned out to require the same expertiseat different levels. This shared expertise is what defines the project.

3. Operator validation using tools from interval arithmetic to formal theorem provers has become a routine part of thearithmetic operator design.

These observations have motivated the shift from designing operators to designing operator generators: programs thatoutput a low-level description of the operators, taking care of their optimization and validation. In other words, ourresearch is shifting from building arithmetic expertise to automating this expertise.Automation of the arithmetic expertise requires new tools from the number theory and computer algebra communities.This explains the new recruits to the team over the period. They are encouraged to develop their own (possibly non-arithmetic) personal expertise, notably linear algebra or Euclidean lattices. They also bring new arithmetic researchdirections such as finite field arithmetic, lattice-based optimization, and cryptography.Automation in turn opens a new frontier: can these tools, initially designed for standard-defined functions, also be usedto implement arbitrary, user-defined functions?We now face a new problem: how will the user specify the function to be implemented? This question can be solved intwo ways. One approach is to get closer to the compilation community, so that the design of arithmetic operators becomesa part of the compilation process. Another is to get closer to the computer algebra community that deals with symbolic-numeric computations. In most current programming languages, an expression like sqrt(x*x+y*y) is defined as thecomposition of two library multiplications, one library addition, and one library square root, each hopefully implemented(in hardware or software) according to standards such as IEEE-754. However, the programmer probably had in mindan atomic function

�x2 + y2 which can be implemented much more efficiently than the current composition, and also

possesses useful mathematical properties which are lost during composition.If arithmetic cores are application-specific and generated at compile time, they can no longer be tested, and must thereforebe automatically validated. In this respect, the last decade concentrated on formalizing fixed-precision computation onscalar functions to a point where its validation could be usefully automated. We now have two directions to explore:machine-checkable proofs of multiple-precision algorithms, and for multi-valued functions such as linear algebra opera-tors. The ultimate goal is to automatically generate formal proofs of arbitrary numerical code, but progress towards thisgoal has to be incremental. A promising direction is to use techniques based on floating-point error-free transformations,which on one side rely on standard floating-point, therefore could build up on existing knowledge, and on the other sidehave been shown to address both arbitrary precision and multi-valued functions.

Structuration of scientific perspectives Designing an optimized complex operator involves many steps. An approx-imation may be used, for example a polynomial to approximate a function. Perspectives related to approximation arereviewed in Section 2.3.2. Then there are usually several possible ways to evaluate the computation. Perspectives relatedto evaluation are detailed in Section 2.3.3. Perspectives related to the certification of approximation and evaluation willbe detailed in Section 2.3.4. Section 2.3.1 will refine the issues related to the automation of operator design. Perspectiveslinking arithmetic and euclidean lattices are surveyed in Section 2.3.5 and those linking arithmetic and pairing-basedcryptography are briefly presented in Section 2.3.6.

2.3.1 Towards the automatic design of operators and functions

What we have successfully automated so far (mostly in the previous 4 years) is program generation for statically-definedelementary functions of one real variable. To apply these techniques to arbitrary code at compile time leads to newchallenges. A first challenge is to identify a relevant compound function in a program, along with information that willallow to implement it efficiently (input range, required output accuracy, rounding mode,...). This is a static analysisproblem and requires interaction with compiler experts. A second challenge is the automatic analysis of such a function,which implies the following tasks:

• Compute maximal-width subranges on which the output requires no computation at all (zero, infinity). This can betedious and error-prone if done by hand. A major side effect of this step is to generate test vectors for corner cases.

• Identify computer arithmetic properties answering to questions like “Is further range reduction possible?”, “Arethere floating-point midpoints?”, “Can overflow occur?”, etc. Today, this is essentially handwritten by experts, sothe challenge is to automate it and to implement dictionaries containing such knowledge.

• Investigate automating range reduction. Generic reduction schemes can be used (for example, interval splittinginto sub-intervals) but involve many parameters, and we have to model the associated cost/performance/accuracytradeoffs. More function-specific range reduction steps can be an outcome of the previous analysis steps.

§2.3 Computer Arithmetic 15

This general automation process will be progressively set up and refined by working on real implementations, in softwareor hardware, of a significant set of operators: all the C99 elementary functions, other functions such as the ICDF func-tion used in Gaussian random number generators, variations around the euclidean norm such as x/

�x2 + y2, complex

arithmetic, interval operators, FFTs, and other signal processing transforms. We also plan to study operators similar tothe now classical FMA, like DP2 which computes a× b + c× d. This instruction is available in the latest x86 instructionset extensions, where it involves three intermediate roundings. Implementing it with one rounding only will improve thecomplex product and other operations. Challenges more specific to software and hardware targets are given below.

Software operator design Most of the software we design brings in some floating-point functionality. We target twomain types of processors. First, we target embedded processors without a floating-point unit (FPU), for which we needto implement the basic operators, coarser elementary functions, and compile-time arbitrary functions. On such targets,memory may be limited, and power consumption is important. Second, we target general-purpose processors that dopossess an FPU for the basic operations. The challenge is then to use this FPU to its best to implement coarser operatorsand compile-time functions. The main metrics here are performance and, to a lesser extent, code size. A challengecommon to both types of targets is to model instruction-level parallelism and to manage to exploit it automatically.

Hardware operator design Automating hardware operator design is a must when targeting FPGAs, or reconfigurablecircuits, which are increasingly being used to accelerate scientific or financial calculations. The challenge here is to designoperators specifically for these applications: not only should their low-level architecture match the peculiar metrics ofFPGAs, but also, the high-level architecture, and even the operator specifications should be as application-specific aspossible, and probably completely different to what we are used to design into VLSI circuits. Such operators can onlybe produced by generators, and this is the motivation of the FloPoCo generator framework, still in early development.In addition to designing the operators themselves, current challenges include accurately modelling the FPGAs, powerestimation, and interaction with high-level (also known as C-to-hardware) compilers.However, we will also keep working on more traditional arithmetic for processors, in particular to enhance FPUs. Hereautomation is mostly useful for design exploration and testing. Besides the already mentioned DP2 operator, one operatorwe wish to study is the Add3 operator, that returns the correctly rounded sum of its three arguments. It would improve theperformance of general code, and also boost “triple-double” arithmetic. Since Add3 has the same instruction-set footprintas the FMA, the challenge is to reuse as much of the FMA datapath as possible.We also want to work on more hardware-specific aspects of validation, such as fault coverage or built-in self-test, incollaboration with the hardware verification community.

2.3.2 New mathematical tools for function approximation

Our algorithms (and their implementations in the Sollya toolbox) for computing polynomial approximations under con-straints will be generalized in several directions.

From one variable to several variables We want to approximate functions of several variables. We first need toimplement a generalization of the Remez algorithm in the real coefficient case. We will also address the case of rationalapproximation in one variable.A second general step will consist in the suitable adaptation of the LLL-based approach we developed in the one variablecase. The applications we have in mind are the design of function evaluation tools in several variables. This work willalso help improving the E-method and making it practical.

From monomials to other function basis Currently, our algorithms and their implementations address the case, inone variable, of a basis of the form (xi) where i belongs to a finite subset of N.We aim at dealing with other bases. The classical basis of Chebyshev polynomials should lead to a better numericalanalysis without losing any efficiency during evaluation. The trigonometric polynomials could allow for new applicationsin the design of numerical filters.

Challenges in the search for correct rounding worst cases With our current algorithms, the cost of finding the worstcases for correct rounding grows exponentially with the width of the floating-point format, and is not practical beyonddouble precision (64-bit width). We wish to tackle larger formats (x87-extended and quadruple precisions), decimalformats, and more functions (including the most frequently used special functions). This will require work both on thealgorithms themselves and on their implementation. In particular, we wish to improve the work on numerically irregularfunctions, such as the trigonometric functions (sine, cosine, tangent) on huge arguments.Also, the programs that compute worst cases are very complex, which might cast some doubt on the correctness of thereturned results. We wish our next programs to be formally proven (at least for the critical parts).


2.3.3 Linear algebra and polynomial evaluation

Linear algebra and polynomial evaluation are key tools for the design, synthesis, and validation of fast and accuratearithmetics. Conversely, arithmetic features can strongly impact the cost and numerical quality of computations withmatrices, vectors, and polynomials. Thus, deepening our understanding of such interactions is one of our major long-termgoals. To achieve this, the expertise acquired in the design of basic arithmetic operators will surely be quite valuable. Butthe certification methods that we are planning to develop simultaneously (see Section 2.3.4) should be even more crucial.

Certified linear algebra We will investigate the theoretical and practical costs of computing certified and effective errorbounds on standard linear algebra operations like factorizations, inversion, linear equation solving, and the computationof eigenvalues. A first direction is symbolic computing of a priori error bounds by manipulating truncated series. Anotherdirection deals with improving the efficiency and quality of self-validating methods for computing error bounds at runtime. Concerning structured linear algebra, we have two additional goals. In exact arithmetic (algebraic complexitymodel), we want to finish our investigation of complexity reductions from one structure to another. In floating-point andfixed-point arithmetics, we plan to study how the structure of the matrix can be used to speed up the computation ofcondition numbers and of certified and effective error bounds.

Certified code generation We plan to improve our work on code generation for polynomials, and to extend it to generalarithmetic expressions as well as to operations typical of level 1 BLAS, like sums and dot products. Due to the intrinsicmultivariate nature of such problems, the number of evaluation schemes is huge and a challenge here is to compute andcertify in a reasonable amount of time evaluation programs that satisfy both efficiency and accuracy constraints. Toachieve this goal, we will in particular study the design of specific program transformation techniques driven by the tightand guaranteed error bounds that our certification tools (see Section 2.3.4 below) will produce.

2.3.4 Methods for Certified Computing

The basic principle of certified computing is to verify the assumptions of mathematical theorems via computer arithmetic.Verifying these assumptions can usually be carried out using symbolic computation but when dealing with numericalproblems, the computation of rigorous error bounds or enclosures is often sufficient to conclude. In this case, intervalarithmetic or carefully controlled floating-point computations can often be used to improve performances.

Certified bounds on roundoff errors A priori bounds on the global roundoff error generated by a floating-point pro-gram can already be computed automatically with Gappa, in the case of straight-line programs. One of our next challengeswill be to handle a priori error bounds in programs involving loops of variable length, and where the computing precisionvaries with each operation. We also want to develop techniques to compute rigorous a posteriori error bounds, either withinterval arithmetic, or using the specifications of the IEEE-754 floating-point arithmetic, with the goal of developing codegenerators to automate the design of certified algorithms based on these techniques. We also want to study the tradeoffbeen the cost and the sharpness of the computed error bound.

Certified enclosures and interval arithmetic Since early 2008, an important effort is being made towards the stan-dardization of interval arithmetic, and this effort will be maintained upon completion of a standard planned at earliestin 2012. A first issue we will address is the development of an efficient interval arithmetic library for general purposecomputing. The goal is to reduce the overhead incurred by interval arithmetic, compared to floating-point arithmetic. Asecond issue is the design and implementation of general algorithms for enclosing the solutions of linear and nonlinearsystems. A third research direction deals with best ways of using arbitrary precision arithmetic adaptively in order toreach a prescribed accuracy.

Higher order techniques Automatic differentiation is a tool that is more and more used to get either sensitivity mea-sures or more generally Taylor models. Future research will focus on the complexity, algorithmic, and implementationaspects of computing or estimating condition numbers using automatic differentiation. Taylor models arithmetic is usedto reduce the so-called “dependency problem” of naive interval arithmetic. A challenge is to combine Taylor models withfloating-point expansions (double-double, triple-double,...) rather than with arbitrary precision, for efficiency reasons.

Formal proof The methods mentioned so far certify the quality of the result up to a bug in their implementation. To geta higher degree of confidence the certification can be checked by a theorem prover such as Coq. There are however twodifficulties: First, the chosen arithmetics or methods must be implemented and proven within the prover. Second and mostimportant, a theorem prover calculates extremely slowly. This implies that it cannot perform the same operations as the

§2.3 Computer Arithmetic 17

original algorithm: the computational path must be reworked in order to factor and simplify parts of it, and to reduce itsnumber of operations. This approach, started with Gappa, should be enlarged to a wider variety of certification methods.

Representation issues A general challenge is to represent and store not only programming information such as thenumerical type and value of a variable, but also higher-level information (the semantics of the computation), known bythe programmer. We will work on a language for that, and use it to build a database of properties useful for dealing withfloating-point arithmetic that can be used in the automation of code synthesis and certification.

2.3.5 Euclidean lattice reduction

Lattice reduction has proved useful for several different problems arising in computer arithmetic, including the computa-tion of the worst cases for the rounding of mathematical functions in fixed precisions and the approximation of functionsby floating-point polynomials. Lattice reduction has many other applications in computer science and computationalmathematics, making it worthwhile to devise faster general-purpose lattice reduction algorithms.

Using floating-point arithmetic within lattice reduction algorithms We wish to finish the work started with the L2

algorithm, and already largely simplified by the H-LLL algorithm. We want to provide a more complete answer to thequestion of how to best use floating-point arithmetic within LLL-type algorithms, and carry the developed techniques overto stronger reduction algorithms (e.g., BKZ) and also to faster reduction LLL-type algorithms (e.g., Segment-LLL).

Studying Schnorr’s hierarchy of reductions We want to study the hierarchy of reduction algorithms (due to Schnorr),from fast but weak reductions (LLL) to stronger but slower reductions(HKZ). A related question is to compute a shortestnon-zero lattice vector as efficiently as possible (theoretically and in practice, with massive parallelism and hardwareimplementation, with and without heuristics). We will also try to simplify and improve upon the large diversity ofdifferent trade-offs between efficiency and output quality of reduction algorithms. To devise better algorithms, we willinvestigate the elaborate techniques used in the proofs of security of lattice-based cryptosystems, such as discrete Gaussiandistributions, transference theorems and quantum lattice algorithms.

Faster LLL-type algorithms From a theoretical point of view, we will try to use floating-point arithmetic along withblocking techniques to speed up LLL reduction, and to devise a quasi-linear time LLL-reduction algorithm (for fixeddimensions). From a practical point of view, we will use models developed by the LaRedA ANR project, such as thesand-pile model, to optimize the codes, and combine the different developed algorithms in a clever way, to rigorouslyachieve the result in the fastest possible way. A good test for these improvements would be the automatic verificationof all bounds obtained with Coppersmith’s technique for attacking different variants of the RSA cryptosystem (whichwould require huge amounts of large LLL reductions). The latter is likely to provide interesting results on lattice-basedtechniques for solving the Table Maker’s Dilemma, including for functions of several variables.

Lattice-based cryptography With code-based cryptosystems, lattice-based cryptosystems are the only public-keycryptosystems known today that resist would-be quantum computers. They also provide very precise and strong securityproperties: the security often provably reduces to worst-case instances of problems closely related to NP-hard problems.One can also expect quasi-optimal complexities for encrypting and decrypting (O(1) bit operations per message bit), byusing structured lattices. However, for the moment it seems hard to make these cryptosystems practical, and we planto tackle that problem by assessing precisely the practical security and by optimizing the implementation by using ourarithmetical expertise.

Other applications Finally, we plan to investigate the applications of lattice reduction in other fields, such as MIMOdecoding for wireless communications, numerical analysis, and optimization.

2.3.6 Pairing-based cryptology

Curve-based cryptology is the other public-key cryptological tool we plan to tackle in the years to come. More precisely,we will mainly focus on the arithmetic and hardware implementation issues related to pairing-based cryptography.We plan to extend our previous works on the ηT pairing to the genus 2 case in order to compare it to the elliptic curvecase. Moreover, we wish to study in detail the other existing pairings (Ate, optimal pairings, etc).We also plan to studythe case of finite fields with large characteristic (its use is a recommendation of the NSA, in particular). This will lead usto work with ordinary curves.


3. Avalon - Algorithms and Software Architectures for ServiceOriented Platforms

3.1 List of participants

Permanent researchers: Yves Caniou (MCF UCBL), Eddy Caron (MCF ENS Lyon), Frédéric Desprez (DR2 INRIA,head), G. Fédak (CR1 INRIA), Christian Perez (CR1 INRIA).

3.2 Perspectives

Keywords Algorithm Design, Scheduling, Distributed Computing, Services, Software Components, SaaS, SOC, SOAList of permanent researchers: Yves Caniou, Eddy Caron, Frédéric Desprez (head), G. FédakVision and new goals of the team The fast evolution of hardware capabilities in term of wide area communication as

well as of machine virtualization leads to the requirement of another step in the abstraction of resources with respectto applications. Those large scale platforms based on the aggregation of large clusters (Grids), huge datacenters(Clouds) or collections of volunteer PC (Desktop computing platforms) are now available for researchers of differentfields of science as well as private companies. This variety of platforms and the way they are accessed have also animportant impact on how applications are designed (i.e., the programming model used) as well as how applicationsare executed (i.e., the runtime/middleware system used). The access to these platforms is driven through the use ofdifferent services providing mandatory features such as security, resource discovery, virtualization, load-balancing,etc. Software as a Service (SaaS) has thus to play an important role in the future development of large scaleapplications. The overall idea is to consider the whole system, ranging from the resources to the application, asa set of services. Hence, a user application is an ordered set of instructions requiring and making uses of someservices like for example a service of execution. Such an execution service is also an application – but at themiddleware level – that is proposing some services (here used by the user application) – and potentially using otherservices like for example a scheduling service. This model based on services provided and/or offered is generalizedwithin software component models which deal with composition issues as well as with deployment issues.

The long term goal of the Avalon team is to contribute to the design of programming models supporting a lot ofarchitecture kinds, to implement it by mastering the various algorithmic issues involved, and by studying the im-pact on application-level algorithms. Ideally, an application should be written once; the complexity is to determinethe adequate level of abstraction to provide a simple programming model to the developer while enabling effi-cient execution on a wide range of architectures. To achieve such a goal, the team plans to contribute at differentlevel including distributed algorithms, programming models, deployment of services, services discovery, servicecomposition and orchestration, large scale data management, etc. All our theoretical results will be validated onsoftware prototypes using applications from different fields of science such as bioinformatics, physics, cosmology,etc. Grid’5000 will be our platform of choice for our experiments.

A: Programming Models A first research direction deals with programming models in general, and composition basedprogramming models such as component models or services in particular. Many (partial) models have been pro-posed to solve particular use cases. While it was needed because of these use cases were important and they werea huge expectation to have working solution, it turns out that it is a limitation as it does not enable to create anapplication requiring several models. For example, GridRPC and Google’s Map-Reduce are two important andwell studied paradigms; each of them having their own and not collaborative models and implementations.

Similar situations occur for other paradigms like workflows, data-sharing, and skeletons for example. We haveshown how these paradigms can fit into a software component models (which have the benefit of being buildaround the concept of composition and include the issue of deployment). However, models and implementationshave been manually done.

Hence, a research direction that we have started to work on is to make use of model transformation techniquesfor transforming high level concepts into lower. This would lead a powerful mechanism to transform user levelconcepts into system level concepts such as those provided by service based infrastructure so as to increase theapplication portability while enabling platform specific optimization.

B: Computing on Large and Volatile Desktop Grids Desktop Grids use the computing, network and storage resourcesfrom idle desktop PC’s distributed over multiple-LAN’s or the Internet to compute a large variety of resource-demanding distributed applications. Today, this type of computing platform forms one of the the largest distributedcomputing systems, and currently provides scientists with tens of TeraFLOPS from hundreds of thousands of hosts.

19

20 Part 3. Avalon

Although these platforms are efficient for high throughput computing, little work has been done to provide access tothese vast amount of computing resources through a set of high-level reliable services, such as massively distributedstorage system for example. We think that service oriented approach would broaden the usage of Desktop Grids,not only to involve more scientific communities but also commercial enterprises and the general public.

Our first research challenge will target the data service and execution of data-intensive application on DesktopGrids. While these applications need to access, compute, store and circulate large volumes of data, little attentionhas been paid to data management in such large-scale, dynamic, heterogeneous, volatile and highly distributedGrids. Throughout the past few years, we have designed a middleware called BitDew for large scale data man-agement and distribution and studied its applicability to data-driven master/worker parallel scheme for data-intenseapplication. We will leverage on this experience to investigate how to implement collective file management ser-vices, how to build efficient services for scientific data delivery networks and services supporting for the MapReduce programming model in the context of Desktop Grid.

A second research challenge is to integrate Desktop Grids with existing Service Oriented Platforms such as Gridsand Cloud Computing. Although we have previous experience in bridging Desktop Grids and the EGEE Gridsthrough the European EDGeS FP7 collaboration, the Cloud is a new and emerging paradigm that we should keepan eye on. We have good hope that the convergence of Cloud computing and Desktop Grid can be achieved withthe following work plan: introduction of virtualization technologies in DG systems, modification of DG schedulersto allow reservations and design of a new security model which will allow to mix trusted and untrusted resources ina single distributed infrastructure.

C: Deployment/Resource Management While programming models become more and more abstract to support of widerange of resources and uses cases, resource management systems (RMS) did not evolve. They are always mainlybased on the concept of bag of tasks to execute; each task being a sequential job or a fixed-range of processors(for static MPI applications). Moreover, RMS select the resources without any cooperation. Thus, the gap betweenprogramming models and RMS has become too large to achieve an efficient use of resources. For example, resourceselection is done at least at two levels: runtimes of programming models try to build a representation of the resources(but that can not be exact without the support of RMS and that is a duplication of the work done by RMS) in orderto transform their high level abstractions into system abstractions (like processes and data files). This is done infunction of the type and number of available resources without any guarantee that the RMS will provide suchresources (they may have been allocated to another user in the meantime).

Hence, a research direction is to work to reduce this gap. The problem is to understand and define the abstractionoffered by RMS so that they can achieve their goals (security, fairness, etc.) while enabling advanced programmingmodels to participate to the resource selection. This step should leverage research on the mapping and the schedulingof an application (with its data) on resources.

D: Services management for High Performance Computing Service Oriented Computing (SOC) is a computing paradigmthat uses services as the basic block to support the rapid development of large scale application over Grids andClouds. Services can be described, published, discovered, and dynamically composed to develop such applica-tions. Many research directions have to be explored to obtain performance on different architectures. Differentperformance measures can be used such as completion time, platform throughput, and energy consumption.

[Service deployment] Depending on the characteristics of the target platform and the number of requests forgiven services, replication and deployment decisions can be taken. More than just a middleware problem, this leadsto a careful modelization of the platform, the middleware, and the service itself. Data management issues can bealso involved.

[Service composition and orchestration] Applications built upon services can be described as workflows. Theseworkflows can use sequential and parallel services, specific data repositories and replicas, and particular schedulingstrategies.

[Service discovery] We develop a P2P platform to deal with hybrid environments based on Petascale architec-ture and Grid. This platform provides a service discovery system based on the DLPT (Distributed LexicographicPlacement Table). We will design new algorithms to take benefit of this hybrid environment. And we will designalgorithms to deal with multiples batch scheduler with task migration. We plan to perform dynamic reservationsystem based on the current load of the environment and the number of requests.

4. Compsys - Compilation and Embedded Computing Systems


Permanent researchers Christophe Alias (CR INRIA), Alain Darte (DR CNRS), Paul Feautrier (PR ENS, emeritus),Fabrice Rastello (CR INRIA).

External collaborator Laure Gonnord-Danthony (MCF Lille).

Evolution of the team

Before its creation, all members of Compsys have been working, more or less, in the field of automatic parallelization andhigh-level program transformations. Paul Feautrier was the initiator of the polytope model for program transformations inthe 90s and, before coming to Lyon, started to be more interested in programming models and optimizations for embeddedapplications, in particular through collaborations with Philips. Alain Darte worked on mathematical tools and algorithmicissues for parallelism extraction in programs. He became interested in the automatic generation of hardware accelerators,thanks to his stay at HP Labs in the Pico project in Spring 2001. Antoine Fraboulet did a PhD with Anne Mignotte – whowas working on high-level synthesis (HLS) – on code and memory optimizations for embedded applications. FabriceRastello did a PhD on tiling transformations for parallel machines, then was hired by STMicroelectronics where heworked on assembly code optimizations for embedded processors. Tanguy Risset worked for a long time on the synthesisof systolic arrays, being the main architect of the HLS tool MMAlpha.Most researchers in France working on high-performance computing (automatic parallelization, languages, operatingsystems, networks) moved to grid computing at the end of 90s. We all thought that applications, industrial needs, andresearch problems were more important in the design of embedded platforms. Furthermore, we were convinced that ourexpertise on high-level code transformations could be more useful in this field. This is the reason why Tanguy Rissetcame from Rennes to Lyon in 2002 to create the Compsys team (Compilation and Embedded Computing Systems) withAlain Darte and Anne Mignotte (who retired soon after, for personal reasons), then Paul Feautrier, Antoine Fraboulet,and Fabrice Rastello quickly joined the group. Compsys has then always been (until 2007) a team based at LIP, butwith external collaborators from Insa-Lyon (Anne Mignotte and Antoine Fraboulet first, then Tanguy Risset). Compsysbecame an Inria project-team in 2004 and was evaluated positively in 2007. In 2005, Tanguy Risset left the LIP to take aprofessor position at Insa-Lyon, while Antoine Fraboulet came to LIP, in the context of an Inria delegation. In 2006-2007,both left slowly the group activities, until the Inria evaluation of Compsys (Spring 2007) to which they participated. Then,the team continued with only three permanent researchers: Paul Feautrier, Fabrice Rastello, Alain Darte. In January2009, Christophe Alias (who was post-doc in Compsys) came back from his post-doc in the USA to take an Inria researchscientist position within Compsys. Compsys has thus now 4 permanent researchers. The reduction in manpower due to thedeparture of Tanguy Risset and Antoine Fraboulet has and will induce a more focused range of activities and objectives.

4.2 Self-assessment

We first evaluate each of our three past objectives.

Code optimization for special-purpose processors Our activities with STMicroelectronics are a huge success forus, not only for the contracts we get. Being able to work within a complete industrial compiler makes our study morethan just theoretical: we can try heuristics, evaluate ideas, address problems with realistic constraints. This makes ourresearch more relevant. The collaboration is thus fruitful for both sides: we help STMicroelectronics dive more deeplyin the literature and on specific research problems, they help us by bringing new problems and by sharing their strongexpertise on architecture and compilation subtleties, and their compiler infrastructure.This collaboration was considered as a success story by Inria: Compsys was viewed as an example to follow, for thefuture collaborations between Inria and STMicroelectronics (Alain Darte was part of the committee who established thegeneral agreement between Inria and STMicroelectronics on joint research efforts). Also, through this activity, Compsyssucceeded to attract young researchers: two PhD students from ENS-Lyon, one international post-doc and maybe anotherone in a near future, and one engineer from STMicroelectronics who will continue as a PhD student.As for scientific results, our first contributions and the comments we got from other researchers were very encouraging.The best paper award for our theoretical paper at CGO’07 (a conference with mainly practical contributions) was also, forus, a sign that more and more researchers think that tightening theory and practice is fundamental. Our other contributionswere all very well welcomed. All in all, 10 of our publications are linked to our work with STMicroelectronics, 7 beingjoint publications, and 3 received a best paper award in the main conference on code generation and optimization (CGO).

21

22 Part 4. Compsys

We were asked to give tutorials (ESWEEK’08, CGO’09, and maybe LCPC’09) on the new view we proposed on registerallocation. We also co-organized the very first international workshop on SSA, during 4 days, with almost all specialistsof the topic, including the very first ones who introduced the technique.The work on this topic is slow and far from being finished. Being able to beat 30 years of heuristics, even if we improvedthe theoretical understanding, is not obvious. Also, as our last results illustrate, we are currently exploiting our new un-derstanding to improve JIT register allocators. Compsys just signed a new contract (Mediacom) with STMicroelectronics,for the next 3 years, on this topic. This activity should thus continue, hopefully successfully, in the future. However,as Fabrice Rastello is at the heart of the collaboration on code optimization with STMicroelectronics, this activity willclearly suffer from his departure in sabbatical in 2010-2011.

High-level code transformations Parametric integer linear programming, polyhedra manipulations, Ehrhart polyno-mials are now standard in the loop transformation community. But a mathematical tool was missing to better understand“bounding box” problems. We think that our introduction of the old but non-classical concept of admissible lattices,with its application to memory reduction, is an important achievement that may find other applications. Similarly, the“summarizing” principles we use for our scalable scheduler for CRP are important as they address complexity issues andmodularity. We also developed the tools corresponding to these theoretical achievements, which was part of our objec-tives. Slowly, we succeed to push the interest for polyhedral techniques in compilation for embedded systems (softwarebut also hardware accelerators). The industry (STMicroelectronics, Thales, but also in the USA with Synfora, ReservoirLabs, GCC, AMD) is considering such techniques with more and more interest.Our results in high-level synthesis are of a more preliminary nature. Clément Quinson obtained interesting results on theHLS tool UGH and we learned a lot by studying and porting STMicroelectronics applications to industrial HLS tools suchas CatapultC and PicoExpress. Alexandru Plesco had promising – but hard to publish – experimental results on loop trans-formations for HLS tools (in this case, Spark and Altera C2H). But the problem is really hard, manipulating/controllingHLS tools and FPGA platforms is hard, developing in such tools nearly impossible. In addition, it is really hard to findstudents that can understand simultaneously mathematics, computer science, and architecture/synthesis. And the same istrue for us as advisers. This made our collaboration with STMicroelectronics (HLS team) not as successful as it could havebeen. We need to do better on this very important challenge in the future. We are trying to increase our collaborations onthis topic, first with the Cairn team (Rennes) and STMicroelectronics (HLS team), through the project S2S4HLS, secondwith most HLS specialists in France (TimA in Grenoble, Lip6 in Paris, LabSTICC in Lorient). Also, our current workon the termination of while loops, a problem that initially arose when trying to transform while loops so that HLS toolscan accept them, seems quite promising, with many interesting research directions, with both theoretical and softwaredevelopments.

Hardware and software system integration This third objective should have been, a priori, the hardest to develop dueto many factors. This was the topic with the maximal distance to our initial expertise. To enter the world of hardware andsoftware integration, we needed to learn the problems faced by this community, understand new objectives and constraints,and not try to just stick our high-performance computing expertise. The good thing is that we learned a lot, the bad thingis that this led us maybe a bit too far from our initial goals and spread our activities on a too large spectrum with respectto our size. Also, hardware/software integration is a very hard topic, with no clear perfect solution, a lot of developments,and a lack of students with the adequate expertise if we want to increase the compilation aspects for architecture design.Nevertheless, we can consider that the collaboration with CEA-LETI and ARES team at Insa-Lyon was a success, withinteresting contributions in traffic generators, simulators for performance and power, and models of power consumption,and three PhD theses (respectively Antoine Scherrer, Nicolas Fournel, and Philippe Grosse). However, this activitywas mainly developed by Tanguy Risset and Antoine Fraboulet (as well as Paul Feautrier, but within an opportunisticcollaboration with CEA-LETI, which will not be continued), therefore, it will not be continued in Compsys. Compsyswill focus on the compilation and code optimization aspects.

General self-assessment All Compsys activities try to bring theoretical and algorithmic contributions to optimizationproblems that can have a direct impact on software developments for embedded computing systems. For us, addressingrelevant problems and validating our results, possibly with industrial partners, is of prime importance. This is the reasonwhy we are interested only in contracts with real collaborations between academic partners and industry. In particular,we prefer direct contracts, as we obtained with STMicroelectronics or CEA-LETI (the ITEA project Martes had limitedEuropean collaborations, but a good collaboration with Thales at national level). With respect to this view of collabora-tions/contracts, we can consider that we succeeded: we had and will have industrial or semi-industrial (CEA) partners forall our activities and sufficient contracts to make Compsys run. This is also because Compsys is an Inria project-team,which brings us a helpful funding and possible hiring (post-doc or researcher).As for publications, our point of view is that we must publish only in the top conferences, maybe few papers, but goodpapers. In this respect, we also were successful with 5 best paper awards in the last 4 years and publications almost onlyin ACM/IEEE conferences.

§4.3 Compilation and Embedded Computing Systems 23

Like most groups in Computer Science, most of our publications are in conferences. This is mostly due to the necessity, foryoung researchers, to accumulate a significant number of publications in the three years of preparation of a PhD, which isnot compatible with the long publication delays of most journals.This is a common situation in computer science. Effortsto change this situation are under way (see the recent issues of the Communications of th ACM), but one may wonder ifthe advent of electronic publication will not change the parameters of the problem.Finally, in terms of manpower, Compsys has always been a small team, and it will remain so because the compilercommunity is fairly small. The departure of Tanguy Risset and Antoine Fraboulet was a big loss, but Compsys could hirea new Inria researcher, Christophe Alias, and several post-docs (one or two every year). The initial expertise of ChristopheAlias is unfortunately not on the hardware synthesis side, so it does not compensate the departure of Tanguy Risset. But,in addition to a good expertise on program transformations, it brings a strong expertise in software developments, whichwill be of great help for Compsys to maintain an activity in which applicability is highly desirable.

4.3 Perspectives

Keywords Embedded systems, DSP, VLIW, FPGA, hardware accelerators, compilation, code optimization, just-in-timecompilation, memory optimization, program analysis, high-level synthesis (HLS), parallelism, scheduling, linearprogramming, polyhedra, graphs, regular computations.

4.3.1 Vision and new goals of the team

Due to the reduction of the team and the fact that we did not replace the expertise of Tanguy Risset and Antoine Fraboulet,we will have to narrow the range of our activities and to focus more on the software side. This is mandatory if wewant to achieve significant results. We will therefore concentrate on only two activities: code optimization for embeddedprocessors, in particular JIT compilation, and high-level synthesis, in particular front-end optimizations.

Code optimization and JIT compilation We want to continue our analysis of combinatorial problems arising in codeoptimization. Thanks to a deeper understanding of these optimization problems, we can not only derive aggressivesolutions with more costly approaches but also derive cleaner and finally simpler solutions. For example, understandingthe SSA form, the subtleties of critical control-flow edges, allows us to consider new strategies for register allocation thatcan be both fast and efficient, thus techniques that are good candidates for JIT compilation.More generally, we want to consider “split compilation” in the context of “deferred code generation” for embeddedprocessors. The challenge is to be able to split expensive code generation techniques into an off-line part and an on-linepart. In deferred code generation, the source program is cross-compiled into a low-level, processor-independent, programrepresentation usually referred to as byte codes. Code generation is then performed either at load time, or just-in-time(JIT). The main motivation is the drastic reduction of the program footprint in flash memory. For example, the byte-code program image has not yet been affected by optimizations that increase code size. Furthermore, the same imagecan serve the heterogeneous processors in the embedded device (portability). To make deferred code generation moreefficient, split compilation tries to move the expensive analyzes to the upstream compiler and relies on annotations on thebyte-code program representation (in an intermediate language such as CLI) to drive the deferred code generator programtransformations. Again, to make this possible, only a deep understanding of code optimizations, of optimal solutions andof what can be obtained by heuristics, of interactions between different optimizations, of concepts and strategies that arearchitecture-independent and those that are not, etc., will make this research fruitful.

High-level synthesis High-level synthesis has become a necessity, mainly because the exponential increase in the num-ber gate per chip far outstrips the productivity of human designers. Besides, applications that need hardware acceleratorsusually belong to domains, like telecommunications and game platforms, where fast turn-around and time-to-market min-imization are paramount. We believe that our expertise in compilation can contribute to the development of the neededprogram transformations/optimizations and tools.The problem can be tackled in two ways. First, one can select an existing tool, either academic such as SPAR or GAUT,or industrial such as CatapultC or C2H, and write front-end optimizers for it. The other, more ambitious approach, isto attempt the direct elaboration of VHDL code, to be submitted to synthesis tools. Both approaches have strengths anddrawbacks; it is too early to decide which one will give the best results.Our first experiments with HLS tools reveal two important issues. First, HLS tools are, of course, limited to certain typesof input programs so as to make their design flows successful. It is a painful and tricky task for the user to transform theprogram so that it fits these constraints and to tune it to get good results. Automatic or semi-automatic program trans-formations can help the user achieve this task. Second, users, even expert users, have only a very limited understandingof what back-end compilers do and why they do not lead to the expected results. An effort must be done to analyze thedifferent design flows of HLS tools, to explain what to expect from them, and how to use them to get a good quality of

24 Part 4. Compsys

results. Our first goal is thus to develop high-level techniques that, used in front of existing HLS tools, improve theirutilization. This should also give us directions on how to modify them. We should be able to give some contributionson this topic, even tools, if we rely on other well-written tools. We plan to use Rose (Livermore National Laboratories)for high-level transformations and build on top of back-end compilers such as Ugh (Ivan Augé, Frédéric Pétrot), Gaut(Philippe Coussy), or the compiler developed by the team of Scott Mahlke(University of Michigan) for academic tools,and Altera C2H, CatapultC, or PicoExpress for industrial ones.More generally, we want to consider HLS as an exercise in parallelization. In this approach, one has to solve manyoptimization problems, concerning the encoding of the FSA, the optimal use of registers, the implementation of controlconstructs. Nevertheless, the results can be disappointing because this approach makes poor use of the inherent parallelismof hardware. So far, no HLS tools is capable of generating designs with communicating parallel accelerators, even if,in theory, at least for the scheduling part, a tool such as PicoExpress could have such capabilities. The reason is that itis, for example, very hard to automatically design parallel memories, how to decide the distribution of array elements inmemory banks to get the desired performances with parallel accesses. Also, how to express communicating processesat the language level? How to express constraints, pipeline behavior, communication media, etc.? To better exploitparallelism, a first solution is to extend the source language with parallel constructs, as in all derivations of the Kahnprocess networks model, including communicating regular processes (CRP). The other solution is a form of automaticparallelization. However, classical methods, which are mostly based on scheduling, are not directly applicable, firstlybecause they pay poor attention to locality, which is of paramount importance in hardware. Beside, their aim is to extractall the parallelism in the source code; they rely on the runtime system to tailor the parallelism degree to the availableresources. Obviously, there is no runtime system in hardware. The real challenge is thus to invent new schedulingalgorithms that take both resource and locality into account, and then to infer the necessary hardware from the schedule.This is probably possible only for programs that fit into the polytope model.

4.3.2 Evolution of research activities

We just illustrate here some of our current developments and research directions.

Register spilling for JIT and split compilation Just-in-time compilers are catching up with ahead-of-time frameworks,stirring the design of more efficient algorithms and more elaborate intermediate representations. They rely on continuous,feedback-directed (re-)compilation frameworks to adaptively select a limited set of hot functions for aggressive optimiza-tion. Leaving the hottest functions aside, (quasi-)linear complexity remains the driving force structuring the design ofjust-in-time optimizers.Despite the developments of SSA-based register allocation that we explored in the recent years, the problem of spilling,i.e., the problem of deciding which variables must be moved to memory to save registers, and when, is largely open. Evenan optimal formulation, possibly very expensive, has not been proposed. Because of this lack of clear understanding,spilling is addressed by heuristics which are very poor or not fast enough, or both. One of our challenges in the next yearswill be to better understand how to spill variables and to develop fast and efficient algorithms for JIT compilation, evenfor complex architectures with register aliasing. This research will be conducted in the context of the Mediacom contract,with STMicroelectronics. Quentin Colombet will start very soon a PhD thesis on the topic.With the Inria project-team Alchemy, we want to go even further, we want to develop a split compiler design, wheremore expensive ahead-of-time analysis guide lightweight just-in-time optimizations. A split register allocator can bevery aggressive in its offline stage (even optimal), producing a semantically digest through bytecode annotations thatcan be processed by a lightweight online stage. The algorithmic challenges are threefold: (sub-)linear-size annotation,linear-time online stage, minimal loss of code quality. In most cases, portability of the annotation is an important fourthchallenge. We will develop a split register allocator meeting those four challenges, where a compact annotation derivedfrom an optimal integer linear program drives a linear-time algorithm near optimality.

SSA, SSI, ψ-SSA The static single information form (SSI) is a compiler intermediate representation that extends theSSA Form. The fact that interference graphs for procedures represented in SSA form is chordal is a nice property thatinitiated our work on register allocation under SSA form. In 2007, Philip Brisk “proved” a similar result concerningSSI: the interference graph would be an interval graph. This property may have consequences for register allocation andliveness analysis. Unfortunately, the algorithms and proofs are based on several incorrect claims and theories (in particularthe program structure tree of Johnson et al.) that we are currently debunking. We recently proved that the interval graphproperty is correct. The proof and algorithm that generate a suitable ordering of basic blocks, to get the interval graphrepresentation, is based on the notion of loop nesting forest.We just started this research. Our goal is to complete the understanding of such intermediate representation to, then,derive better algorithms. More complex than SSA and SSI, our goal is to extend our results to ψ-SSA, a form of SSA thattakes predication into account and that is very useful for STMicroelectronics architectures. All code transformations andoptimizations must be studied and adapted to ψ-SSA.

§4.3 Compilation and Embedded Computing Systems 25

Loop transformations for HLS and communication optimizations In previous studies, we explored the use of looptransformations in front of HLS tools. We used the Wrapit loop transformation tools developed by the Inria project-team Alchemy and integrated into the ORC open-source compiler. Starting from C code, synthesized by the Spark HLStool, we showed important performance improvements of the resulting design (in terms of silicon area and communi-cation optimization). This preliminary study also confirmed that there is a strong need for data communication/storagemechanisms between the host processor and the hardware accelerator. We are currently investigating how to design ahardware/software interface model for enabling communication optimizations, such as burst communications. This mayimply the design of a memory controller, the development of a performance model, as well as compilation techniques,possibly with compilation directives. The integration with existing HLS tools is tricky, current investigations are madewith the Altera C2H code generator.More generally, we would like to develop a library of communications, associated with directives in the C code, to bet-ter exploit data transfers between hardware accelerators and the outside world. So far, HLS tools communicate usuallythrough FIFOs, which prevents prefetching, data packing, data reorganization, parallelism. Going beyond this communi-cation model, with optimized communications, is an important challenge.

Program termination and static worst-case execution time Knowledge of the worst case execution time (WCET)of a function or subroutine is a key information for embedded systems, as it allows the construction of a schedule and theverification that real-time constraints are met. The WCET problem is obviously connected to the termination problem: apiece of code that does not terminate has no WCET. The standard method for proving termination is to compute a rankingfunction (Floyd 1967), which maps the operations of the program to a well-ordered set in such a way that the rankingdecreases as the computation advances. We noticed that the constraints on a ranking function are similar to the causalitycondition that applies to a schedule, as defined for automatic parallelization, with just a change of sign. This allowedus to reinvest most of the techniques for multi-dimensional scheduling (Feautrier 1992) and to obtain multi-dimensionalranking functions in a very efficient way. The WCET of the program can then be obtained easily (at least in theory) bymeans of polyhedral techniques.The method we are investigating is able to handle (but of course not decide termination of) every program whose controlcan be translated into a counter automaton. This roughly covers programs whose control depends on integer variablesexclusively, using conditionals, for loops and while loops whose tests are affine expressions on variables. Furthermore,it seems to be very easy to approximate programs which are outside this class by familiar techniques, like ignoring non-affine tests or variables with too complex a behavior. Termination of the approximate program entails termination of theoriginal one, but the converse is not true. This method can be extended in several interesting directions:

• In some cases, when termination cannot be proved, it is possible to construct a certificate of non-termination in theform of a looping scenario, which should be an invaluable help for debugging.

• The class of ranking functions should be extended to parametric and piecewise affine function. This will extend theclass of programs that can be proven to terminate.

• The initial motivation of this work was to automatically transform some while loops into DO loops with early exitsor additional guards. Such a representation is indeed more suitable for HLS tools.

We already have a prototype but a lot of work remains to be done, both for theory and implementation of our algorithms.This activity will take place within the contract S2S4HLS (source-to-source four high-level synthesis) with STMicroelec-tronics and the Inria project-team Cairn.

26 Part 4. Compsys

5. D-NET - Dynamic networks


Permanent researchers: Guillaume Chelius (CR1 INRIA), Eric Fleury (Pr ENS Lyon).

5.2 Self-Assessment

Strong points The team has a strong record and has produced high quality research results. This is assessed by thepublication track, by the involvement of team members in numerous program committees, in international collab-orations, in research project at the European level (IP FP6 Health and Life Science MOSAR project) and Nationalwide (ANR SensLAB and INRIA ADT SensTOOLS) and by the development and deployment of large scale ex-perimental testbed (SensLAB1) and distribution of our software (WSNET2).

The D-NET team has a strong expertise in wireless sensor networks, wireless protocols, distributed algorithms andin the development and the deployment of sensor networks in order to setup large scale data gathering in situ testbeds. The team has re-considered its main core research objectives since the new availability of a large datasetreporting the dynamics of networks (contacts between persons in the MOSAR project) will allow us to developmethods and tools with a direct connection to real-world data. There is a crucial need for analysis tools, and for theunderstanding of dynamical processes on dynamical networks. Interestingly, the real-world dynamical graph is alsomultimodal, since contacts, antibiotic pressure and bacteria clone evolutions are recorded. This multimodality alsopresents new challenges that will be addressed. The D-NET team therefore has both very fundamental and veryapplied aspects that are tightly linked

Weak points The size of the team is clearly the Achilles heel of D-NET. In order to be comfortable and to accommodateany change, the staff should be multiplied by two. The stress on the size is accentuated by the fact that GuillaumeChelius may envisage to move in order to progress in his own carrier and that Eric Fleury has several administrativeduties (head of the CS department, CNRS GDR ASR board, IXXI scientific and steering board).

The team is involved in SensLAB and SensTOOLS (prime investigator) where heavy developments are donewhereas all development positions are temporary positions. Moreover, SensLAB will require additional devel-opments after the end of the ANR support in order to maintain the test bed (user support and integration of newfunctionality).

The D-NET team takes a transverse view of several complementary and multidisciplinary domains in order to tacklethe complexity of the study of dynamical networks and spreading processes. The core area of research involvedin the D-NET project spans fundamental computer science (graph theory, complexity, and algorithms) but requiresalso fruitful interdisciplinarity with physics (statistical physics, information theory, nonlinear dynamics and discretesystems) and even biology and epidemiology.

Opportunities In the very active field of complex networks, the development of a large body of research in the last tenyears has largely been stimulated by the availability of empirical data, and the increase in computer power needed toanalyze these data. While many interesting questions remain open even for what concerns static networks, the nextchallenging issues, which the community is starting to address, are given by the generalization of known tools andthe development of new methods able to deal with dynamically evolving networks. While some theoretical studieson simplified models have started to appear, important and relevant development has to be based on real empiricaldata. The availability of the data sets3 coming from the MOSAR project represents in this context a strong assetthat will give the groups involved in this project a head start in the scientific competition.

5.3 Perspectives

Keywords: measure, sensor network, complex network, dynamic network, graph, network science, distributed algorithm.

1http://www.senslab.info2http://wsnet.gforge.inria.fr/3The data set forms a huge dynamic complex interaction network since all contacts between 600 people are recorded every half minute during a 6

month long experiment (300 Millions of temporal neighboring snapshots).

27

http://www.senslab.info

http://wsnet.gforge.inria.fr/

28 Part 5. D-NET

Vision and new goal of the team

The main goal of the D-NET team is to lay solid foundations to the characterization of dynamically evolving networks,and to the field of dynamical processes occurring on large scale dynamic interaction networks. In order to develop toolsof practical relevance in real-world settings, we will ground our methodological studies on real data sets obtained duringlarge scale in situ experiments.Let us take the context of health science and public health policy. The spread of infectious diseases remains an urgentpublic health issue. All modeling approaches crucially depend on our ability to describe the interactions of individualsin the population. They rely therefore on the availability of data on individuals’ interactions, which define complexnetworks on which diseases spread. Only recently has it become possible to study large scale interaction networks, suchas collaboration networks, e-mail or phone call networks, networks of sexual contacts, etc... This has prompted manyresearch efforts in complex network science, mainly in two directions. First, attention has been paid to the networkstructure, considered as static graphs. A large amount of research has focused on spreading models on complex networks,and has showed that the network topology has a strong impact on the dynamics of the system. However, the dynamics ofnetworks (the changes in their topology) and on networks (e.g., spreading processes) are still generally studied separately.There is therefore an important need for the development of tools and methods for the joint analysis of both dynamics.The D-NET project puts the emphasis on the cross fertilization between these two research lines which will definitivelylead to considerable advances. The D-NET project has the following fundamental goals:

1. To develop distributed measurement approaches based on sensor networks in order to capture physical phenoma inspace and time;

2. To develop the study of dynamically evolving interaction networks, by building specific tools targeted at character-izing and modeling their dynamical complex properties.

3. To study dynamical processes occurring on dynamical networks, such as spreading processes, taking into accountboth the dynamics of and on the network structure.

4. To apply these theoretical tools on large scale experimental data sets. We will benefit from a large data set describingthe contacts patterns within a hospital environment.

5. to set up and foster multidisciplinary collaborations in order to develop in the case of the MOSAR context ourunderstanding of the spread of nosocomial infections, and of the prevalence of antimicrobial-resistant bacteria(AMRB), in order to develop strategies aiming at controlling and mitigating such spreading.

The D-NET project targets the study of dynamically evolving networks, from the point both of their structure and ofthe dynamics of processes taking place on them. Most activity on complex networks has up to now focused on staticnetworks, towards the characterization of their structure, and the understanding of how this structure influences dynamicssuch as spreading phenomena. The important step that this project wants to undertake is to take into account the fact thatthe networks themselves are dynamical entities. This means that the topology evolves and adapts in time, possibly drivenby (or in interaction with) the dynamical process unfolding on top of it.This step is motivated by two points. On the one hand, the new availability of a large dataset reporting the dynamics ofreal networks, mainly by deploying sensor networks closer to the physical object in order to record and gather the dynamicof the network studied (in the MOSAR context, sensors measure all contacts between persons); this dataset will allow usto develop methods and tools with a direct connection to real-world data. On the other hand, the specific context of thedataset, precisely defines a need for such tools, and for the understanding of dynamical processes on dynamical networks,in order to be able to develop appropriate measures, or protocols. In the MOSAR context, namely a hospital environmentin which AMRB spread, measure can be containment or health policies. Interestingly, the real-world dynamical graph isalso multimodal and several sensors may record various data at different time scale. This multimodality also presents newchallenges that will be addressed.The D-NET project has therefore two major goals: on the one hand, to develop the knowledge in the networking sciencefield in order to provide a better understanding of dynamic graphs from both the analysis and structural point of view.This fundamental aspect will be grounded on real world large scale dynamic networks. On the other hand, our gaol is tohelp develop a better understanding of the physical object studied. The point requires the joint study of both dynamics ofthe network and on the network, and required a tied collaboration with others fields in order to take advantage of the firstgoal. The D-NET project therefore has both very fundamental and very applied aspects that are tightly linked.The impact of the research developed in D-NET goes beyond the context of disease spreading studied within the MOSARcontext, thanks to the inherent interdisciplinarity of the field of complex networks. Dynamical processes on dynamicallyevolving networks are indeed present in several fields, including rumor spreading in social networks, opinion formationphenomena, fashion phenomena, the diffusion of innovation in a population. The spread of computer viruses may take

§5.3 Dynamic networks 29

place through email networks or bluetooth connections, which are both dynamical. The development of efficient algo-rithms for information spreading in wireless/P2P/DTN networks should also be improved by the understanding of thedynamics of these networks and their temporal properties. The study of all these processes will benefit from the toolsdeveloped in this project, which represents a unique opportunity to study a real-world spreading process, occurring on acontact network whose dynamics is known. The conjunction of real-world data with the development of theoretical toolsproposed in this project will therefore impact various scientific fields, ranging from epidemiology to computer science,economics and sociology.

5.3.1 Sensor network, distributed measure and distributed processing

In order to gather information on the dynamic behavior of a specif physical phenomena, a measure must be performed.The quality of the measure is crucial and determines all the analysis. Moreover, by conducing and controling the measureand its bias during the experiment, one may derive and optimize the analysis. Sensors networks are one efficient wayto measure a phusical phenoma at various space and time scale. One important chalenge is to understand how to takeadvantage of the numerous deployments of heterogeneous sensor networks that will make various kinds of objects able tocommunicate and to interact with their environments in order to design a global large scale sensing tool able to monitorand sense the physical environment. By gathering several distributed heterogeneous sensing devices together, one couldbuild a accurate sensing tool. Given a target application, the goal is the select a set of available sensors and to set upthe way to collect their data in order to fulfill the requirements of the application. Such data collected and selected onthe fly, are able to sense directly and with a high accuracy the phenomena of interest. Sensor could be heterogeneous interms of sensing capacities, in terms of deployment density, in terms of mobility. The key feature is that heterogeneity is afundamental and beneficial quality of distributed sensing tool, not just a problem to overcome. In order to understand suchdistributed heterogeneous sensing networking as a whole and coherent sensing tool, this will require the development ofboth theoretical and practical techniques to deploy such distributed sensing tools on top of existing sensor networks, tomanage this distributed measure tool and to perform efficient and reliable distributing computing to analyze multi scaledynamic data. With these main challenges in mind, we define the following objectives:

Characterize the various sensing measures that we can exploit. Such characterization must take into account the dif-ferent correlations in space and time that exist between all sensors. The characterization must also handle thevarious time scales that may exist in the measures.

The challenge is due to the heterogeneous data resolution. Moreover, data will be multi modal and multi scale withpossible irregularities and will offer much correlation (time /space). Fundamental challenges lie in the current lackof tools, models, and methods for the characterization and analysis of time series describing dynamic sensing data.Data set collected by various sensors, may be characterized by the lack of most common simple statistical propertiessuch as stationary, linearity, or Gaussianity. Relevant time scales may be difficult to identify, or may even not exist.Observed properties have non-trivial relations and even the choice of the time scale granularity that should be usedin the analysis is a difficult problem, since it may bias the analysis in an uncontrolled way.

Methodology and design of a global sensing tool. In order to use multi variable/scale sensing data we need to normal-ize data format and access method. Moreover, based on the characterization described above, we will propose amethodology to select the appropriate measure in order to fulfill the application requirements.

Heterogeneity is a fundamental, beneficial quality of distributed sensing tool, not just a problem to overcome.Heterogeneous sensing systems are more immune to the weaknesses of sensing modalities and more robust againstdefective, missing, or malicious data sources than even carefully designed homogeneous systems. However, dataheterogeneity also presents main challenges when trying to integrate data from many different sensors. We need toa way to model, describe, combine and query these different data sets.

Methodology of distributed processing that should be performed in order to guarantee an accurate measure. The goalhere is to take advantage of the fact that computation could be delocalized closer to the sensing phenomena. Ex-ploiting space/time correlation could be used in order to optimize the amount of data sent through the network.

Design robust distributed processing in order to be able to analyze the data from the different sensors i sa hardchallenge. Sensors constantly generate tiny data, so we could consider sensor data as one of streaming data. Con-sidering this feature of sensor data, we’ll try to construct a system on which users can program these streamingdata as like UNIX pipe. Managing calculated streaming data, we’ll be able to reduce a large amount of searchand computation cost, because typical computed data are used again and again. In other words, our system willdynamically compute and merge sensor data, considering user queries

30 Part 5. D-NET

5.3.2 Statistical Characterization of Complex Interaction Networks

The dynamically evolving networks can be regarded as "out of equilibrium" systems. Indeed, their dynamics is typicallycharacterized by non standard and intricate statistical properties, such as non-stationarity, long range memory effects,intricate space and time correlations. Moreover, such dynamics often exhibit no preferred time scale or equivalentlyinvolve a whole range of scales and are characterized by a scaling or scale invariance property.Another important aspect of network dynamics resides in the fact that the sensors measure information of different na-ture. For instance, in the MOSAR project, inter-individual contacts are registered, together with the health status of eachindividual, and the time evolution of the resistance to antibiotics of the various strains analyzed. Moreover, such infor-mation is collected with different and unsynchronized resolutions in both time and space. This property, referred to asmulti-modality, is generic and central in most dynamical networks.If such approach is crucial, it represents also a great challenge and risk for us since the core area of research involved inthese statistical characterization of large scale dynamic dataset spans fundamental physics (statistical physics, informationtheory, nonlinear dynamics and discrete systems). New faculty hires should strengthen the D-NET skill and we also fosterour ongoing collaboration with SiSyPhe team at ENS Lyon. With these main challenges in mind, we define the followingobjectives:

From "primitive" to "analyzable" data: Observables. The various and numerous modalities of information collectedon the network generate a huge " primitive " data set. It has first to be processed to extract " analyzable data", which can be envisioned with different time and space resolutions: it can concern either local quantities, suchas the number of contacts of each individual, pair-wise contact times and durations, or global measures, e.g., thefluctuations of the average connectivity. The first research direction consists therefore of identifying, from the" primitive data ", a set of " analyzable data " whose relevance and meaningfulness for the analysis of networkdynamic and network diffusion phenomena will need to be assessed. Such " analyzable data " needs also to beextracted from large " primitive data " set with " reasonable " complexity, memory and computational loads.

Granularity and resolution. The corresponding data will take the form of time-series, " condensing " network dynamicsdescription at various granularity levels, both in time and space. For instance, the existence of a contact betweentwo individuals can be seen as a link in a network of contacts. Contact networks corresponding to contact sequencesaggregated at different analysis scales (potentially ranging from hours to days or weeks) can be built. However, it isso far unclear to which extent the choice of the analysis scale impacts the relevance of network dynamics descriptionand analysis. An interesting and open issue lies in the understanding of the evolution of the network from a set ofisolated contacts (when analyzed with low resolution) to a globally interconnected ensemble of individuals (at largeanalysis scale).

In general, this raises the question of selecting the adequate level of granularity at which the dynamics shouldbe analyzed. This difficult problem is further complicated by the multi-modality of the data, with potentiallydifferent time resolutions. We will therefore consider as an alternative the analysis of network dynamics jointly at allresolutions, through wavelet decompositions and multiresolution analyses. While these tools have been studied fora quite long time for self-similar and multifractal processes, their tailoring to network dynamics implies challengingtheoretical issues that will be addressed: for instance, multivariate models for such processes remain to be invented;alternations of periods of regular and irregular behaviors may require the development of processes that go beyondthe so-called intermittency models.

(non-)Stationarity. Stationarity of the data is another crucial issue. Usually, stationarity is understood as a time invari-ance of statistical properties. This very strong definition is difficult to assess in practice. Recent efforts have putforward a more operational concept of relative stationarity in which an observation scale is explicitly included.The present research project will take advantage of such methodologies and extend them to the network dynamicscontext.

The rationale is to compare local and global statistical properties at a given observation scale in time, a strategy thatcan be adapted to the various time series that can be extracted from the data graphs so as to capture their dynamics.This approach can be given a statistical significance via a test based on a data-driven characterization of the nullhypothesis of stationarity.

Dependencies, correlations and causality. To analyze and understand network dynamics, it is essential that (statistical)dependencies, correlations and causalities can be assessed amongst the different components of the " analyzabledata ". For instance, in the MOSAR framework, it is crucial to assess the form and nature of the dependencies andcausalities between the time series reflecting e.g., the evolution along time of the strain resistance to antibiotics andthe fluctuations at the inter-contact level. However, the multimodal nature of the collected information togetherwith its complex statistical properties turns this issue into a challenging task. Therefore, Task1 will also address the

§5.3 Dynamic networks 31

design of statistical tools that specifically aim at measuring dependency strengths and causality directions amongstmutivariate signals presenting these difficulties.

The objective is to provide elements of answers to natural yet key questions such as : Does a given property observedon different components of the data result from a same and single network mechanism controlling the ensembleor rather stem from different and independent causes? Do correlations observed on one instance of information(e.g., topological) command correlations for other modalities? Can directionality in correlations (causality) beinferred amongst the different components of multivariate data? These should also shed complementary lights onthe difficulties and issues associated to the identification of " important " nodes or links...

5.3.3 Theory and Structural Dynamic Properties of dynamic Networks

The study of relevant statistical analyses and characterizations of network dynamics is a key and necessary step beforeother analysis in order to get an accurate insight of the data. To go further in the characterization of the dynamics, weneed to focus on intrinsic properties of evolving networks. New notions (as opposed to classical static graph properties)have to be introduced: rate of vertices or links appearances or disappearances, the duration of link presences or absences.Moreover, more specific properties related to the dynamics have to be defined and are somehow related to the way tomodel a dynamical graph. Classical graph notions like the definition of path, connected components and k-core haveto be revisited in this context. Advanced properties need also to be defined in order to apprehend the intrinsic dynamicstructural issues of such dynamic graphs. The notion of communities (dense group of nodes) is important in any social/ interaction network context and may play an important role within an epidemic process. To transpose the static graphcommunity concept into the dynamical graph framework is a challenging task and appears necessary in order to betterunderstand how the structure of graphs evolves in time. In these contexte we define the following objectives:

Toward a dynamic graph model and theory. We want to design new notions, methods and models for the analysis ofdynamic graphs. For the static case, graph theory has defined a vast and consistent set of notions and methods suchas degrees, paths, centrality measures, cliques. These notions and methods are completely lacking for the study ofdynamic graphs; not only do we not have basic notions allowing the description of a graph and its dynamics, butwe also lack the basic definitions and algorithms for manipulating dynamic graphs: there is no consensus on theway to encode such graphs, and for instance even the basic notion of distance between vertices does not have awidely acknowledged equivalent for dynamic graphs. Our goal is therefore to fill this lack, by providing the basicnotions for manipulating dynamic graphs as well as the notions and indicators to describe its dynamic meaningfully(as complex networks theory does for static complex networks). For instance, it is crucial to generalize the notionof centrality of a node, in a context where a node can have a large degree or centrality in a snapshot at time t and amuch lower one a t + 1.

Dynamic communities. The detection of dynamic communities is particularly appealing to describe dynamic networks.In order to extend the static case, one may apply existing community detection methods to successive snapshotsof dynamic networks. This is however not totally satisfying for two main reasons: first, this would take a largeamount of time (directly proportional to the data span); moreover, having a temporal succession of independentcommunities is not sufficient and we loose valuable information and dependencies. We also need to investigatethe temporal links, study the time granularity and look for time periods that could be compressed within a singlesnapshot.

Tools for dynamic graph visualization. Designing generic and pure graph visualization tools is clearly out of the scopeof the project. Efficient graph drawing tools or network analysis toolkit/software are now available (e.g., GUESS,TULIP, Sonivis, Network Workbench). However, the drawback of most softwares is that the dynamics is not takeninto account. Since we will study the hierarchy of dynamics through the definition of communities we plan toextend graph drawing methods by using the communities’ structures. We also plan to handle the time evolution inthe network analysis toolkit. A tool like TULIP is well designed and could be improved by allowing operations(selection, grouping, sub graph computation...) to take place on the time dimension as well.

32 Part 5. D-NET

6. MC2 - Models of Computation and Complexity

6.1 Team composition

Permanent researchers: Pascal Koiran (PR ENS Lyon), Natacha Portier (MCF ENS Lyon), Eric Thierry (MCF ENSLyon), Eric Rémila (IUT Roanne).

6.2 Self-Assessment

Weak points The team’s main difficulty at this time is clearly the sharp drop in size due to the departure of severalpermanent members: Vincent Bouchitté (assistant professor at University Lyon 1, deceased in 2005), MarianneDelorme (assistant professor at University Lyon 1, retired), Jacques Mazoyer (professor at the IUFM and then atLyon 1 after the merger of the IUFM with Lyon 1, retired), Michel Morvan (now in charge of research at VeoliaEnvironnement), Andrei Romashchenko, Olivier Finkel and Nicolas Schabanel (all 3 CNRS researchers). All thesedepartures have led to a loss of scientific expertise and leadership for our team and the LIP laboratory; they havealso made the daily life of the team more difficult. In particular, we have discovered to our dismay that with thecurrent team size, holding the MC2 seminar (groupe de travail) on a weekly basis may no longer be feasible.

Some excellent candidates have applied to CNRS and ENS positions to join the team, but apparently this hasnot been sufficient to convince our parent institutions (tutelles) to compensate for some of these losses. Anotheroption besides CNRS and ENS Lyon would be to hire assistant professors or professors from Lyon 1, our thirdparent institution. Despite numerous discussions with the various persons involved and the support of last two LIPdirectors, Frédéric Desprez and Gilles Villard, our efforts in this direction have so far remained unsuccessful.

Strong points In spite of this difficult situation we were able to maintain a good level of scientific activity. This is truefor some of the longtime strengths of our team such as algebraic complexity or tilings, and more recent topicssuch as quantum computing; also we have managed to preserve some of the team’s longstanding experience incellular automata despite the retirement of Marianne Delorme and Jacques Mazoyer, thanks in particular to thedevelopment of the new research topic of probabilistic cellular automata. Likewise, the new role played by graph-theoretic concepts such as the treewidth in our work on algebraic complexity is helping to preserve some of ourexpertise in graph theory (indeed, the study of treewidth in France was pioneered by Vincent Bouchitté). We havealso begun to work on topics that are completely new for the team, e.g. network calculus or applications of gametheory to economics. Finally, the creation of a startup should give an enduring legacy to our work on complexsystems, even though this is no longer a central topic in the team’s project (more on this in the next section).

6.3 Perspectives

Keywords algorithms, computational complexity, combinatorics.

Vision and new goals of the team With the departure of Michel Morvan, complex systems will feature much less promi-nently among the team’s research topics. Our project is to focus our research activities on algorithms and compu-tational complexity theory. These two subjects are complementary: in the field of algorithms one tries to designand analyze efficient algorithms (that is, to obtain upper bounds) while the main goal of computational complexityis to obtain hardness results (and ideally, unconditional lower bounds). There is another less obvious reason whythese two subjects are complementary: the techniques of computational complexity are very often algorithmic innature. An important example is provided by the theory of NP-completeness. To show that a certain problemB is NP-complete, one constructs a reduction from A to B where A is a problem which is already known to beNP-complete. That is, to show that a certain task (deciding B) has no efficient algorithm we design an efficientalgorithm for a different task (reducing A to B). This example is of course very well-known, but it may not be sowell known to non-experts that plenty of other results from computational complexity theory, including recent re-sults, are based on algorithmic techniques. For instance, it follows from the large body of work on hardness versusrandomness tradeoffs that the two tasks of proving unconditional lower bounds and derandomizing algorithms areessentially equivalent. The former task is therefore reduced to a task which is conceptually simpler and in any caseof a clearly algorithmic nature: designing efficient deterministic algorithms.

Besides algorithms and computational complexity, combinatorics and in particular graph theory is a third, comple-mentary, topic that we would like to develop. Increasing the team’s combinatorial expertise will be clearly useful

33

34 Part 6. MC2

for the development of a successful research program in combinatorial algorithms. Combinatorics and complexitytheory are also very complementary since advanced mathematical techniques play an ever increasing in moderncomplexity theory, and combinatorics is one of the main mathematical disciplines on which complexity theory candraw. This is by no means the only mathematical discipline to play an important role in complexity theory; algebraand probability theory also spring to mind, and in fact it is becoming increasingly difficult to name a mathematicalfield which does not play a role in complexity theory. The choice of combinatorics seems especially appropriatebecause this subject is, we believe, currently underrepresented in the LIP laboratory and more generally at ENSLyon.Currently, the permanent MC2 researchers who are most involved in algorithms and the study of combinatorialstructures are Eric Rémila and Eric Thierry. Those who are most involved in complexity theory are Pascal Koiranand Natacha Portier.Our top priority for the new reporting period will be to hire new team members in the 3 areas of algorithms,complexity theory and combinatorics (in combinatorics we will favor those subfields that are particular relevant toalgorithms and complexity theory). We believe that the quality of our research, our strong involvement in teachingand mentoring of doctoral students should convince our tutelles to support us in this endeavor. Looking morebroadly at the "big picture" of the French higher education system we find another reason to support team MC2,namely, the important role that ENS Lyon has to play in the nationwide development of theoretical computer scienceand more generally of mathematical computer science (which could be defined as the study of computer scienceproblems with mathematical techniques). Indeed, theoretical / mathematical computer science are fields with a highlevel of international competition where a taste and a talent in both mathematics and computer science are a must.In the French higher education system, ENS Lyon is one of the very few institutions with the ability to train suchstudents in any significant number. Their training must of course rely on research at the highest possible level.There are two main trends in theoretical computer science: the "logics and semantics" trend, and the "algorithmsand complexity" trend. Track B of ICALP (arguably the main European conference in theoretical computer science)is devoted to the first trend, and the corresponding LIP team is the Plume team. Track A of ICALP is devoted to thesecond trend, and our ambition is to represent this "algorithms and complexity" trend at ENS Lyon. Clearly, withthe current team size there is still a long way to go.Finally, we list below some of the current team’s projects for the near future.

Algebraic Complexity From September 2009 to September 2011 most of the team’s work in algebraic complexity willtake place in Toronto: Pascal Koiran and Natacha Portier will participate in a thematic program at the Fields Instituteon Foundations of Computational Mathematics, and will visit the computer science department of the Universityof Toronto. Natacha Portier’s visit is made possible by the European fellowship PACCAP (Problems in AlgebraicComplexity and Complexity of Algebraic Problems). Pascal Koiran’s visit is made possible by his IUF membershipand additional support from the Fields Institute. We give below some examples of problems on which we wouldlike to work.Our first example deals with the worst case complexity of systems of polynomial equations and we plan to studythis problem in the boolean model of computation, at least initially. Work by Shub and Smale, and more recently byBeltran and Pardo, show that the approximation of roots of systems of n polynomial equations in n complex vari-ables has polynomial average-case complexity. Their results are based on homotopy Newton methods. Strangelyenough, it seems that in the worst-case setting very little is known on the complexity of this fundamental problem:we have neither an efficient algorithm nor a hardness result (note however that if the number of equations is notconstrained to be equal to the number of variables, it is an easy and well-known result that the problem becomesNP-hard). We conjecture that this problem is hard in the worst-case setting, and we will work towards establish-ing this result. One explanation for the lack of current hardness result is that the decision version of the problemalways has a positive answer: a system of n polynomial equations in n complex variables always has solutions inprojective space. It seems impossible to establish NP-hardness for such problems. In the 1990’s, this observationled Papadimitriou to the systematic study of TFNP (Total Function NP) search problems. In the last few years therehas been renewed interest in this line of work due in particular to the extensive work on computational game theory.As is well known, the approximation of Nash equilibria is a central problem in computational game theory, and itis a prominent example of a total search problem. Our goal will therefore be to establish a hardness result, or evena completeness result, for an appropriate class of total search problems.A related example is the use of condition numbers in complexity estimates. There is a significant body of work onalgorithms for systems of polynomial equations that have a “good” behavior from a complexity-theoretic point ofview when the input system is “well-conditioned”. Such results have been obtained for instance by Shub and Smalein the complex case, and by Cucker, Krick, Malajovich and Wschebor in the real case. It is not clear how far theseresults are from optimality since, as in our first example, no lower bound (or completeness result) that would take

§6.3 Models of Computation and Complexity 35

the condition number into account seems to be known. We will try to obtain such results. Most likely, they wouldtake the following form: if certain discrete complexity classes are distinct, then certain problems about systems ofpolynomial equations do not admit algorithms that would have a too “well-behaved” dependency on the conditionnumber (and other parameters such as the number of variables).Our third example is Linear Programming. For discrete (rational) data, this problem can be solved in polynomialtime by the ellipsoid method or by interior point methods. For real-valued data it is known that well-conditionedinstances can be solved efficiently, but it is a longstanding open question whether this problem has polynomialworst-case algebraic complexity. We plan to study the connections of this problem to other open problems of al-gebraic complexity, such as the complexity of evaluating the permanent. In fact, it is already known that LinearProgramming has polynomial worst-case algebraic complexity under the the extremely strong hypothesis that thepermanent has polynomial-size arithmetic circuits and that P=PSPACE. As explained above, the conjunction ofthese two hypotheses implies that all problems that can be solved in parallel polynomial time over the reals, includ-ing Linear Programming, can in fact be solved in polynomial time. But Linear Programming has arguably a lowercomplexity than a generic problem in the class of parallel polynomial time problems. One can therefore hope thata similar “transfer theorem” can be established for this specific problem under a weaker hypothesis.Our last example is MaxFLS: given a system of linear equations, find a feasible subsystem of maximum cardinality.It has been known at least since the work of Amaldi and Kann that this problem is NP-hard in the boolean setting.As in the previous example it can be shown that this problem has polynomial algebraic complexity under the twohypotheses that the permanent has polynomial-size arithmetic circuits, and that P=PSPACE. Again, we would like toobtain a transfer theorem under a weaker hypothesis (e.g., by getting rid of the hypothesis P=PSPACE). Such resultswould perhaps contribute to put back the focus of research in Algebraic Complexity Theory from decision problemsto evaluation problems, as they would show that it is not more difficult to prove a lower bound for the permanentthan to prove a lower bound for certain decision problems. In any case, we note that interest in the complexitytheory community for the permanent polynomial is currently on the rise. For instance, it is a central object of studyin Mulmuley’s Geometric Complexity Theory program, and in the work by Kabanets and Impagliazzo on hardnessversus randomness tradeoffs.

Quantum Computing As explained above, Natacha Portier and Pascal Koiran will spend the next 2 years in Torontowhere they should work mostly on non-quantum topics. Our team will nonetheless remain quite active in quan-tum computing thanks to the arrival in September 2009 of Pablo Arrighi (associate professor at Université JosephFourier in Grenoble, visiting LIP thanks to a délégation CNRS) and Jonathan Grattage (on an ATER position).Pablo Arrighi’s current research is devoted mostly to quantum cellular automata (QCA). This used to be a rathermessy topic since there are several competing definitions of QCA. Pablo Arrighi and his coworkers have done alot to clarify the situation by studying the relations between these definitions. They have in particular shown theequivalence between certain operational and axiomatic definitions. These results are the quantum counterparts ofHedlund’s theorem, a well-known theorem from classical CA theory which establishes the equivalence between theoperational definition of classical cellular automata (a line of locally interacting finite automata) and their axiomaticdefinition as a continuous shift-invariant mapping on the space of configurations. Universal QCA are another topicof interest on which Arrighi and Grattage have collaborated. Their arrival in the team should be mutually beneficialsince they will benefit from our expertise in classical and probabilistic CA, and current members will benefit fromtheir expertise in QCA. A promising topic to study during their visit is the extension to open quantum systems ofthe founding work done by Arrighi and his coworkers for QCA (the QCA that they have studied should be viewedas examples of closed quantum systems since their global evolution rules are unitary). One possible starting pointwould be to try and obtain a Hedlund-style theorem for probabilistic cellular automata (apparently, no such theoremis currently known).

Analysis of discrete dynamical systems It includes the analysis of several models sharing the fact that the configura-tions are discrete (that is composed of a finite or countable number of elementary pieces, each one being in a statewhich may change) and the dynamics is given by local updating rules (when updating a local state, the rule onlytakes into account neighboring states). The time at which updates occur can be discrete or continuous, and there isusually many different update regimes which can be considered. Some of them can be deterministic, probabilisticor even driven by adversaries or external parameters. Beyond the observations of trajectories (that is the sequencesof updated configurations) where simulation can be useful, the general objective is usually the prediction and pos-sibly the control of such dynamics. It concerns both the asymptotic behavior and the transitory behavior of thetrajectories.Eric Rémila and Eric Thierry are involved in the study of such models:

• Self-assembly tilings: in this recent model introduced by Winfree, tiles are squares (resp. cubes) that aggregateon 2D (resp. 3D) grid. Each type of tile has different types of glues on its border allowing tiles to stick

36 Part 6. MC2

together if adjacent glues exceed some threshold given by an external parameter, the “temperature”. Thismodel generalizes the classical Wang tiles with colored borders and the dynamical point of view consists inconsidering the construction of tilings as a growth process from initial seeds. Among the questions, we wishto study expressiveness: given a set of tiles, which shapes or patterns can be generated ? and reciprocallygiven a language of shapes, is it possible to generate them by a set of tiles ? How to characterize sets of tileswhich can tile the whole plane or space ? With regard to the dynamics, it concerns the asymptotic behavior.Other questions concern the transitory part, like evaluating the time needed to generate a given pattern, or theinfluence of the temperature.

• Cellular automata: we wish to continue the study of cellular automata for dynamics different from the classicalsynchronous updates. Allowing different update schemes like probabilistic ones enable to model asynchro-nism or faulty behaviors. There exist many open problems, some that we have identified when studyingparticular rules like Minority or the ones listed in A. Toom’s book “Cellular Automata with Errors: Problemsfor Students of Probability”. A collaboration has been initiated with J. Mairesse (LIAFA, Paris 7) about theform of stationary distributions for probabilistic updates in 1D cellular automata, which are directly linked tothe enumeration of some combinatorial objects (directed animals).

• Gene networks: M. Noual’s PhD thesis co-advised by J. Demongeot anf E. Rémila will begin in Fall 2009about gene networks: we will study attractors and limit cycles and robustness according to the update schemechosen. The dynamics is strongly dependent on the topology of the gene network, that is the structure of itsunderlying graph.

Our approach will put an emphasis on the combinatorial aspects of those models, and computational complexitywill also bring some new insights by setting the difficulty of predicting properties of the dynamics. Here are someknown results which give the flavor of what we may look for: the ergodicity of 1D cellular automata enduringprobabilistic i.i.d. errors is undecidable (A. Toom), finding the state of a vertex at time t for a boolean networkwith the Majority rule is P-space complete (C. Moore) (which means that it is likely that one can not parallelizea simulation to speedup the prediction at time t). With such a point of view, this theme enters the team researchorientation re-centered on algorithms, combinatorics and computational complexity. Note that in the literature, anew banner called unconventional computing emcompasses those dynamics which have a strong computationalpower (universality for tilings and cellular automata).

Algorithmics of discrete event systems Network Calculus is a theory for the worst-case performance evaluation of par-ticular discrete event systems. Its formalism making use of (min,+) tropical algebra has attracted several the-oretical works about communication networks, and an important application is the analysis of critical embeddednetworks like the ones found in aerospace. It is believed that this theory will be an important alternative to modelchecking for those particular worst-case evaluations, due to a better scalability. However it remains to be provedand users suffer from the absence of software tools implementing the results from this theory. The main reason isthat the algorithmics corresponding to the mathematical solutions of the literature has not been much studied. Ourteam has started to propose some algorithms and will carry on this study. Eric Thierry has received some ANRfundings (ANR PEGASE) starting at Fall 2009, to reinforce the team on this topic by recruiting a post-doctoralfellow as well as a research engineer.

The development of algorithms for Network Calculus is likely to require results from (min,+) algorithmics (dueto the formalism which approximates real systems by (min,+)-linear models), graph algorithmics (due to theimportance of the topology of the models), linear algebra (due to reduction of some (min,+)-linear operators tosome (+,×)-linear ones), number theory (due to some periodicity issues), linear programming and more generallycomputational geometry (in order to deal with the combinations of constraints which are usually piecewise linearfunctions). Many problems are open concerning the computational complexity of Network Calculus analyzes. Forinstance, for such models of communication networks, it is not known whether the stability of the network (that isthe fact that the amount of data in the network remains bounded) is decidable or not. Dealing with such theoreticalissues is imperative in our opinion in order to design a good software tool.

Beyond Network Calculus, the team wishes to develop its expertise on the algorithmics of discrete event systemsby investigating some other discrete event systems like Petri nets or stochastic extensions of Network Calculus, andstudy the precise complexity of some underlying problems like the computation of (min,+)-convolutions which isa quite common operation but has not been much studied.

7. Plume - Proof Theory and Formal Semantics


Permanent researchers Audebaud Philippe (MCF ENSL), Baillot Patrick (CR CNRS), Duprat Jean (MCF ENSL),Hirschkoff Daniel (MCF ENSL), Laurent Olivier (CR CNRS), Lescanne Pierre (Pr ENSL), Riba Colin (MCFENSL).

7.2 Self-Assessment

Since September 2008, the Plume team entered a transitional period towards the development of additional researchdirections, around logical foundations of programming languages. The next four years will mainly be dedicated to theestablishment of these new activities and to the stabilization of our group.

Strong points The dynamism of the team has recently been renewed with the arrival of several young bright researchersto foster new and challenging research directions. Our team is highly attractive (as shown, in particular, by thenumber and quality of applications to permanent, post-doc, ATER, ... positions).

We start to gather our expertises in the various aspects of the Curry-Howard correspondence to develop new in-teractions: complexity for concurrency, realizability techniques in implicit complexity, linear logic approaches toconcurrency, semantics of quantification, game based interpretations of logic, ...

The current funding of the team is mainly provided by ANR projects and gives appropriate support for missionsand invitations.

In the specific environment of the ENS Lyon, the team plays an important role in the community through itsinvestment in teaching. Among the French PhD students in our topics, an important proportion are former studentsof ENS Lyon.

Weak points After the retirement of Pierre Lescanne planned for 2012, there will be no senior (i.e. rank A) permanentposition at Plume. With at least 5 junior (i.e. rank B) positions, the team will need (at least) two professors (orresearch directors) to deal appropriately with the team management.

The number of PhD students in the team is rather low. The arrival of new members and the increase of the numberof “habilités à diriger des recherches” should have a strong impact on this point in the next years. However it shouldbe noticed that it remains very difficult for good PhD students in our subjects to find permanent positions.

In the future we should probably try to add more diversity in our funding resources, in particular using bilateralfunding and European funding.

Opportunities Initiated with the GeoCal ACI NIM (2004–2006), the Paris-Lyon-Marseille-Chambéry network plays acrucial role in the development of the research synergies at a national level around linear logic and the semantics ofprogramming languages. This community is currently incarnated within the GDR Informatique Mathématique (inthe GeoCal and LAC working groups in particular), and is at the same time probably too big for the model definedby ANR projects.

A by-product of this research dynamics is a number of good students who just finished their PhD or are about todefend it. This guarantees a very high level in the future recruitments.

The team could benefit from a better integration in the research environment in logic at Lyon, in particular throughcloser interactions with the mathematical logic team of University Lyon 1 (at Institut Camille Jordan), that mainlyfocuses on model theory. Some collaboration already started through the European MALOA (MAthematical LOgicand Applications) project for doctoral studies (kick-off planned in autumn 2009).

Strong relations with logic teams and people working in mathematical computer science in the area could be a goodstarting point for the development of master studies around these topics at Lyon.

Outside France, our team is involved in very strong international collaborations: Italy (Bologna, Roma, Torino,...), UK (Cambridge, London, ...), Japan (Kyoto, JAIST, Nagoya), USA (Worcester, Boston, ...), Serbia (Novi Sad),Poland (Krakow), Germany (München), ...

37

38 Part 7. Plume

Risks Dealing with the growth of a research team, in times where important changes impacts the French academic life,entails an increasing amount of time spent on administrative duties, not for research.

In the specific case of funding, dealing with short term research projects compels us to do frequent re-applications(which are very time-demanding). In lack of sufficient recurrent funding, the resources of the team are currentlyonly guaranteed for the next two or three years.

Concerning our hiring policy, we will possibly have to challenge the attractiveness of the Paris sites. However, basedon our very good relationship with the corresponding teams, we are confident that we can manage to coordinateour hiring policies in an efficient way. As proved in the past, our collaboration with these teams is always verysuccessful.

7.3 Perspectives

Keywords Proof theory; semantics of programming languages; computer assisted proofs; Curry-Howard correspon-dence; linear logic; realizability; game semantics; implicit computational complexity; concurrency theory; proba-bilities

Vision and new goals of the team Based on the fruitful interaction between logic and computer science, our main ob-jectives are directed towards extensions of the Curry-Howard correspondence to additional logical/programmingparadigms. The current evolution of the team leads to a particular effort on logical approaches and to a reinforceduse of abstract tools.

Our methodology is to build on mathematical theories in order to study programming languages. More preciselywe want to develop new techniques from logic and semantic tools. Indeed these topics have strongly progressedduring the last ten years and can now be brought together in a working framework. We plan to focus on threemain mathematical tools. First, on the modelling side, game semantics has emerged as a versatile and accuratesetting for representing programs and their interaction. It can handle a large spectrum of programming primitives.Second, on the reasoning side, our tool will be logic which, thanks to the proofs-as-programs paradigm, makes itpossible to develop type systems and program extraction from proofs. Linear logic emerged as a powerful system tostudy logic(s) from this point of view. Finally, to prove the properties of our logical systems and relate them to themodelling side, we will take advantage of techniques coming from realizability, as well as from game semantics.Using these common tools, we will focus on developing type systems and program extraction mechanisms indifferent directions: imperative program extraction, integration of bounded complexity constraints, extension toconcurrent computation, semantics of probabilistic aspects, ...

The long-term goal of establishing a unified framework (based on linear logic and related tools) for the foundationsof rich programming languages (integrating concurrent, probabilistic, ... aspects with a semantic control overtermination, complexity, ...) can be seen as the specificity of our team.

7.3.1 Logical foundations of programming languages

The Curry-Howard correspondence establishes a strong relation between programs with their types on the one hand, andproofs with their formulas on the other. This correspondence holds for appropriate pairs consisting of a programminglanguage and a logic. Our three main tools (linear logic, game semantics, and realizability) are among the most advancedones in this topic.Linear logic has been introduced twenty years ago by J.-Y. Girard from an analysis of the semantics (denotational se-mantics more precisely) of intuitionistic logic and of the λ-calculus. Linear logic has had a strong influence on, and hasbecome a key tool in various domains related to logic and computer science: from proof-theory to security protocols,through denotational semantics, and type systems for programming languages.Originating in the idea of modelling computation using the interaction between a program and its environment, gamesemantics has renewed the study of denotational semantics. Its first major success has been to solve the long standingproblem of giving a syntax-independent presentation of the fully abstract model (i.e. a model in which the interpretationsof two programs are equal if and only if these programs have the same behaviour, as given by the observational equiva-lence) of PCF. Game semantics has now been successfully applied both on the logic side and on the programming sidewith applications to software verification.Underlying all the computational interpretations of logical proofs, realizability can be presented as a generalization oftyping. It associates programs to types in a richer way than with usual type systems, and thus can be used to “define”types from their computational contents. As a consequence, it is often at the basis of program extraction mechanisms.Connections between these tools have already been established: game semantics was inspired from linear logic, recentmodels of linear logic are built with game interpretations, realizability can be given a game-like interpretation, realizability

§7.3 Proof Theory and Formal Semantics 39

is used in models of second order linear logic, double-orthogonal approaches coming from linear logic are now crucial inrealizability, ... However this does not lead yet to a completely unified corpus of methods.

Games and proof theory of constructive classical logic

The computational content of proofs in propositional classical logic through the systems defining constructive classicallogic (LC, λµ-calculus, ...) is now well understood, thanks to the Curry-Howard correspondence.Recent progresses on game models for logical systems have been obtained by a convergence of logical games for intu-itionistic logic (in proof theory) and game semantics for extensions of PCF (in computer science).This provides us with appropriate tools for a computation aware analysis of the theorems developed in proof theoryin the last century in first and second order classical logic. Successful examples have been obtained in the past in thepropositional setting: Gödel’s double-negation translations are continuation passing style transformations, for example.Beside higher-order logic, there are on-going works on the computational interpretation of additional axioms. A specificfocus is put on (variants of) the axiom of choice. We are interested in the use of games and realizability (Krivine’s styleor in relation with bar recursion) interpretations of these axioms. In this context, it is important to unify tools developedin the first-order logic framework and in the arithmetic framework.A important general question is the unification of these two key interactive interpretations of logic: game semantics andrealizability.Outside constructive classical logic, we will work on understanding the computational content of “symmetric” classicalsystems based on the sequent calculus and dealing with a non-deterministic cut-elimination procedure.

Applications of Linear Logic

In the domain of light linear logics which are providing implicit characterizations of complexity classes, new systemshave recently emerged: linear logics by levels, variations on bounded linear logic. We are interested in the syntactic studyand development of these systems with two main goals. The first one is the access to additional complexity classes. Thesecond one is to make progress on the intensional expressive power in a given class (PTIME for example): finding systemsable to capture more algorithms (intensional power) for a fixed class of functions (extensional power). We also work onthe denotational semantics of these variants of linear logic. By means of game semantics in particular, we hope to findmodels with intrinsic complexity guarantees (any proof interpretable in the model is normalizable in polynomial time forexample).The discovery of concurrent behaviours in the normalization of differential interaction nets derived from differential linearlogic opens new perspectives in the foundations of distributed computation. The range of the programming primitivesexpressible in this setting is still under investigation. The study of the denotational models of differential linear logicwill allow us to find abstract characterizations of behavioural equivalences of processes (a key ingredient in the theory ofprocess algebras).In the direction of unifying our approaches, a key lock will be to understand the compatibility of the variants of linearlogic we use (light, differential, ...).A long term goal is to extend Curry-Howard to computations modelled by rewriting theory in order to give them a logicalcontent. A starting point is to use linear logic and game semantics in order to give a logical structure to residuals graphsissued form rewriting.

Program extraction and proofs/programs transformations

Direct applications of the Curry-Howard correspondence are obtained by transforming proofs into programs or by apply-ing tools from proof theory in computer science and conversely.The paradigm of program extraction from proofs gives a way to build certified software without the necessity to provecorrection of the obtained code. The validity of the requested specification is a built-in consequence of the approach. Aformal proof is developed in a proof assistant (this requires human interaction) and the associated code is automaticallyextracted. We will focus our attention on these mechanisms in the future with a specific interest in extraction from classicallogic (and additional axioms) and from logical systems with bounded complexity.The development of the first classical extractor for Coq triggers important new questions: efficient execution of theobtained programs, extraction of witnesses in a large class of existential formulas, program extraction from (variants of)the axiom of choice in relation with side effects in programming, ...Using the ideas from variants of linear logic for implicit computational complexity (ICC), we will study proof systemswhich allow for the extraction of programs with certified complexity bounds, for instance PTIME. Our setting would add,to the usual extraction paradigm, the certification that the obtained programs admit a given complexity bound.

40 Part 7. Plume

Realizability and program extraction are two strongly related theories. Our work on extraction in classical logic is basedon Krivine’s realizability. On the ICC side, realizability techniques, as they begin to be used for light linear logics, willprobably turn out to be very important.The transfer of technologies obtained through the Curry-Howard correspondence is still under development. Standardprogram transformations such as terminal recursion, defunctionalization, ... have to be understood as proof transforma-tions and the logical properties of the transformed objects should be studied. In the converse direction, focusing in logicor iterated forcing can be studied as program transformations.

7.3.2 Semantic tools for new behavioural properties of programs

Semantics (in particular denotational semantics) provides means to apply mathematical tools to the understanding of deepproperties of programming languages. Results are often very strong but as a consequence they are often restricted toparticular programming primitives. We want to build on recent progresses in the Curry-Howard correspondence (andrelated tools) to address the semantics of richer languages.A typical application of this approach is the definition of a type system. In particular, there is a focus on so-called strongtypings which, by constraining programmers to a reasonable programming discipline, provide guarantees on programbehaviours.We will focus mainly on implicit complexity constraints on the execution of programs, concurrent behaviours of compu-tational systems, and randomized aspects of languages. This naturally leads us to address new research directions such asthe control of complexity properties of concurrent processes.

ICC

We want to work on the expressiveness of implicit complexity criteria. For this purpose, we will study, given a criterion,the behavioural properties of the programs satisfying the criterion. For instance we can try and investigate necessary (and,possibly, sufficient) conditions on the behaviour of abstractions of these programs. The purpose of this approach is onthe one hand to reveal theoretical limitations of certain criteria, by showing that certain families of programs cannot bevalidated, and, on the other hand, to compare different criteria.In order to design realistic functional languages with bounds on usage of resources, a crucial point is to combine a usablebut constrained form of recursion with a rich pattern-matching mechanism. To address this question, we envisage tomix typing constraints coming from light linear logics with other termination criteria for higher-order recursion such assized-based termination.

Concurrency

Regarding the theory of process calculi, which provides formal models of concurrent and mobile computation, we willcontinue working on the behavioural properties of processes. Questions we plan to address include algebraic characteri-zations of observational equivalences, the definition of methods for the guarantee of behavioural properties, and of prooftechniques for reasoning about concurrent systems.A new planned research direction stems from the interaction with ICC for sequential computation. We aim at investigatingtechniques to guarantee quantitative bounds on concurrent systems, by designing suitable type systems or static criteria.For instance we would like to introduce criteria to guarantee that after an interaction, a system will react after a certainnumber of internal steps, or that during execution, the size of the system will remain bounded. Such properties are clearlyrelevant in a concurrent setting: for instance, one would like a request to a server to be answered after a reasonable numberof computation steps, or that an agent does not use too many resources for too much time.

Randomized aspects of computation

Adding probabilistic traits to imperative languages has been broadly studied. Among the main references on this topic, themore related to our source of interest include works done by Kozen, Morgan and Mc Giver. When it comes to functionalparadigm though, one has to deal with new objects: so called high order types, hence functional spaces.On a practical side, the consequence is one could provide programs which generate randomized functional terms; andthis is different from providing programs which return a randomized value form any given value for the input parame-ter(s)! The theoretical consequence is that we must understand which mathematical meaning (semantics) can be given tofunctional spaces in the first place.This correspondence between programs and mathematical objects matches the broader Curry-Howard correspondence,for which experience shows that the actual understanding of probabilistic traits should benefit from exploring side by sideboth practical and theoretical issues. Therefore, our research program in the area is twofold: developing semantics (theadaptation of mathematical objects taken from functional analysis like Polish spaces and similar ones looks promising);

§7.3 Proof Theory and Formal Semantics 41

and proceed forward building formal tools to specify and prove properties on actual programs, as we are confident thisapproach could benefit from programmer’s needs and/or understanding on randomized algorithms. Also, research areassuch as Cryptography and Complexity could contribute to provide deeper insight on that matter.

7.3.3 Formalization

Proof assistants and formal logics are not only an object of study for us. We also use them for the formalization ofmathematical theories. Formalization is often important and useful to clarify the axioms and reasonings being used, andto find appropriate ways to define the objects being manipulated. Currently our developments are made with the Coqsystem.Our formal study of game theory and Nash equilibria will be continued with applications to the Internet (infinite games)and to biology (feasibility-desirability games and coalition games).The formalization of Euclidean plane geometry will be turned into a tool to help pupils in the solving of geometricproblems by providing dynamic drawings and proof verifications. This requires good interaction between the drawingtool and the proof assistant, through the definition of specific tacticals.We also use Coq for proving properties of various algorithms. Examples that we plan to address include watermarkingalgorithms, distributed and/or randomized algorithms.

42 Part 7. Plume

8. Reso - Optimized Protocols and Software for High-PerformanceNetworks


Permanent researchers: Begin Thomas (MCF UCB Lyon 1 since 10/2009), Gelas Jean-Patrick (MCF UCB Lyon 1),Gluck Olivier (MCF UCB Lyon 1), Gonçalves Paulo (CR1 INRIA), Guerin-Lassous Isabelle (Pr UCB Lyon),Lefevre Laurent (CR1 INRIA), Vicat-Blanc Primet Pascale (DR2 INRIA).


8.3 Self-Assessment

Strong points The arrivals of new senior researchers and the subsequent fruitful cross-fertilisation increased the dynamicof all researches around the network topic within the ENS. Our impact expanded to the international grid andnetwork research community as well as the industrial field.Reso actively promoted the mixity of the research team by attracting and recruiting high skilled young women (assenior researcher or PhD student). This helps in balancing the team, facilitates the internal communication andincreases the quality of the team dynamic.

Reso is focusing on a very active research domain which has a strong social and economical impact. The network-ing but also services research communities are highly challenged by an uncontrolled evolution of the traditionaldisciplines due to huge economical and social forces feeded by technologies like web2.0 and optical fiber deploye-ment. The increasing complexity and heterogeneity of network infrastructures, along with the evolving nature ofapplications and services, challenges the design of new architectures that need to scale, be energy-efficient and eco-nomically sustainable. Since 2002, Reso positioned itself at the edge of computing and networking to understandbut also propose solutions to accelerate but also smooth the convergence. Today, self-managed and self-organizedarchitectures, virtualization, high availability and energy-efficiency are becoming very hot topic in the context ofCloud services and Future Internet. Our explorations of these aspects from both the global system theoretical opti-misation point of view and the network devices experimental point of view give us a strong advance that we planexploit in the near future.

How to guarantee quality of service in machine/user-to-machine/user communication while efficiently using theresources of the networks is becoming major challenge. The two main problems we tackled and will continue toexplore in the future are: i) dynamic bandwidth sharing and congestion control in Future Internet and ii) control andflow management with a semantic networking approach. During the last period we focused on the three followingquestions:

1) what type of congestion control and transport protocol should be used in the context of large-scale deployedhigh-speed networks (fiber to the home, for example)?

2) how to efficiently share, but also dynamically provision the bandwidth of a network dedicated to computingtasks?

3) is the "flow-aware" approach a valuable solution to solve the end-to-end quality of service issue in the very-high-speed Future Internet?

These questions appeared to be more and more critical and far from beeing close. We proposed solutions thathave interested both the research and industrial communities and that made our team and laboratory more visiblenationally and internationally. We hope to expand our impact in the future and to be able to disseminate largely oursolutions.

In particular we believe that probing, data analysis and statistical inference is a sensible triangle approach thatshould soon become an inherent component of emerging system designs. The Reso team leverages 2 main assets toaddress these challenges :

1) a multidisciplinary competence comprising network and protocols specialists, researchers in statistical signalprocessing and an experimented computer engineering team. In the fall 2009, a newly hired researcher willbring in a new expertise in queueing and optimization theory ;

43

44 Part 8. Reso

2) an original and pioneer experimental facility relying on a large scale, independent and fully reconfigurablenetwork plate-form (Grid5000), and on a versatile and scalable measurement probe which permits fine packet-grain captures at 10Gbps.

Weak points Our skills have their downsides on their own. In particular we undergo :

1) the weaknesses of an experimental facility, with its inevitable unstable hardware and software solutionsthought to realize the best trade-off between flexibility and robustness ;

2) the natural difficulty that exists amongst scientists with different backgrounds to share a common languageand to meet on a unifier project. In addition, our traffic awareness activity is quite recent in the Reso team andcertainly, still lacks a fully satisfactory maturity.

8.4 Perspectives

Vision and new goals of the team Our vision is that the Internet of the Future will be a wide reservoir and a vast marketfor all kinds of small or huge resources and services for the communication and processing of information. Anyentity, biological or not, will be able to access and combine those with the duration, trust-level, and capacity it willchoose to pay for. Advanced optical technologies will be densified from the core backbone and will play a majorrole in the access of this reservoir. Distributed systems that aggregate storage- and computing-resources into avirtual and integrated dynamic data processing environment, also called Clouds, will become ubiquitous. Althoughthese systems will theoretically offer solutions for resource aggregation, high and predictable performance for ap-plications may be hard to obtain due to the unsuitability of the bandwidth-sharing paradigms (fairness, best effort,no QoS), communication protocols, and software overheads. Reso will continue to address several issues such asquality of service, security, traffic metrology, traffic modeling, and network-resource scheduling with the aim ofsolving issues such as timely, cost-efficient, energy-efficient, and reliable traffic delivery. Reso will pursue and em-phasis the investigation of fundamental issues of network science such as bandwidth- and network resource sharingparadigms, network-resource virtualisation and scheduling, energy efficiency, traffic metrology , traffic modeling,quality of service, transport protocols. Reso aims at playing an active and visible role in the transformation ofthe Internet architecture and will associate its effort with major actors in this domain. In France, we are alreadyleading a partnerships with Bell Labs (Alcatel-Lucent) and we are builing an other strong collaboration with Or-angeLabs (France-Telecom). We are also joining two important european consortium sharing our vision for theFuture Internet: GEYSERS and 4WARD.

Evolution of Research activities We propose to keep our main focus on high speed networks: the usage of these highspeed networks is increasing (FTTH for example) and their technical specificities are evolving a lot (ligh pathconfiguring automation, optical burst switching and packet switching technologies emerging). However, the use ofwireless networks as access networks is greatly increasing and, in the future, packets are very likely to be transmittedon different networking technologies. Therefore, some of our future works will include wireless networks as accessnetworks in the targeted high speed networks. We will continue to apply the same methodology which mixes theoryand large scale experiments on real testbeds. Our goal is to put more emphasis on theoretical aspects and upstreamresearch adopting the clean slate thinking proned by the networking community. In particular, Reso will focus ofkey issues such as:

– where and how to integrate the autonomy required to manage and control high-speed networks at large scale?

– how to deal with the cost of resource and network virtualization on communication performance?

– what type of congestion control should be used in the context of a large-scale deployment of high-speed accessnetworks (fiber to the home for instance)?

– is the traffic of the grid and of high-speed networks self-similar as the Internet traffic is? What are the criticalscales? In which sense is self similarity harmful to quality of experience?

– how to efficiently share the bandwidth in a network that interleaves real-time multimedia applications andcomputing applications?

– how to improve the interactions of message-based communications or interactive traffic and transport layer inwide area networks, that can include wireless access networks?

Our work will continue to follow four major research topics :

1 – Optimized protocol implementations and networking equipements.

§8.4 Optimized Protocols and Software for High-Performance Networks 45

Current challenges facing Future Internet will concern the way this large distributed infrastructure will beable to adapt to new usages and context changing. In this research axis, we explore the integration of context-awareness functionality to address important issues : reliability of communications, dynamic programmabilityof network equipments and energy consumption of distributed infrastructures. This axis bases its experimentalevaluation and validation at large scale on real distributed infrastructures (like Grid5000/ALADDIN).Reso focuses this activity on the following directions :

Autonomic Network Programmability : The key enabling factor of new network services is programmabilityat every level; that is the ability for new software capabilities to self-configure themselves over the network.We explore the concept of "dynamic programming enablers" for dynamic service driven configuration ofcommunication resources. Dynamic programming enablers apply to an executable service that is injected andactivated into the network system elements to create the new functionality at runtime. The basic idea is toenable trusted parties (users, operators, and service providers) to activate management-specific service andnetwork components into a specific platform. We study mechanisms and infrastructures required to supportthese components. We aim at providing new functionality to services using Internet facilities, addressingthe self-management operations in differentiated and integrated services. The goal is the enhancement ofthe creation and the management (customization, delivery, execution and stop) of Internet services. We havedesigned the ANPI software framework (Autonomic Network Programming Interface) allowing large scaleautonomic service deployment (currently used in the Autonomic Internet european project). This orientationis currently supported by the EU FP7 "Autonomic Internet" project (2008-2010).Session awareness : Most of the NGN services involve a session model based on multiple flows required forthe signaling and for the data exchange, all along the session lifespan. New service-aware dependable systemsare more than ever required. Challenges to these models include the client and server transparency, the lowcost during failure free periods and the sustained performance during failures. Based on our previous workwith FT RD (“Procedes de gestion de sessions multi-flux”, N. Ayari, D. Barbaron, L. Lefevre, France TelecomRD Patent, June 2007), we continue to explore and propose session aware distributed network solutions whichsupport the reliability mandatory to operators services. A running collaboration with University of Sevilla(Spain) is currently running on this topic.Energy awareness : Large scale distributed systems (and more generally next generation Internet) are facinginfrastructures and energy limitations (use, cooling etc.). Energy aspects will change the way we designsoftware frameworks, services and protocols. In the context of monitored and controlled energy usage, weare proposing and continue to explore the design of energy aware equipments and frameworks, which allowusers and middleware to efficiently use large scale distributed architectures. We are developing solutions todynamically monitor energy usage, inject energy information as a resource in distributed systems and adaptexisting jobs (OAR) and network (BDTS) schedulers to autonomically benefit from energy information intheir scheduling decisions. This research is validated through experimental evaluation on Grid’5000 platformand inside the ALADDIN initiative. This topic is currently supported by the INRIA "Action de RechercheConcertee" called "Green-NET". Reso is also member of the European action COST IC0804 on “Energyefficiency in large scale distributed systems” (2009-2013).

2 – Quality of Service and Transport layer for Future Networks.Reso team foresees to extend its activities to heterogeneity. By heterogeneity, we mean the heterogeneityof communication technologies (i.e. wired, fiber, wireless, etc.) and the heterogeneity of traffic (best efforttraffic, computing applications, real-time applications, etc.). It is clear that the current networks follow thistrend in terms of technologies and of usage. Optimizing the communication of a specific application on asingle technology network is a step towards a more efficient application but the obtained performance is notclear on an end-to-end heterogeneous path that is shared by different kinds of applications. It is important totake these constraints into account at the beginning. Our goals are twofold:

– Designing techniques that provide a network resources sharing of the different applications while ensur-ing the constraints required by some applications. Different shares (such as max-min, proportional, etc.)can be considered.

– Optimizing the user satisfaction while ensuring a good use of the network (which corresponds in turn tothe operator satisfaction). We plan to identify the different trade-offs that can be obtained.

It is clear that the answers to these goals should be dynamic and distributed. The different approaches thatwill be tackled for these studies are:

Modeling of the studied systems. Concerning the modeling of the traffic, we intend to reuse the works carriedout by the traffic analysis activity. How to model the heterogenity of communication technologies is one ofthe first questions to address.

46 Part 8. Reso

Dynamic and distributed optimization. Approaches like Lagrangian optimization for instance are very promis-ing techniques for optimizing in a dynamic and distributed way. We have already used such an approach in avery specific context. We intend to apply it in a more general setting. The dynamic tuning of some parametersof this technique is still an issue that we need to solve to derive truly dynamic optimization solutions.

Traffic-aware solutions. Within the framework of the BellLabs-INRIA Joint Lab., our aim is to design qualityof service solutions that are based on the traffic knowledge. We have obtained some first results, but we intendto intensify this study, mainly with the use on history dependent utility functions corresponding to the users’satisfaction. We plan to use these functions in different quality of service mechanisms, like admission controlor active queue management for instance. This use raises the issue of the knowledge distribution to thesemechanisms: which information to give, which periodicity, on which area, evaluation of the false operationdue to out-of-date information, etc. We will answer to these questions.

The network virtualisation. In this topic we will address mainly two challenges: resource sharing and perfor-mance isolation in virtual node from one hand, virtual infrastructures on physical infrastructure mapping onan other one. From the theoretical and technical point of views, both are optimisation problems that will betackled by adopting a "spiral" research methodology. This approach relies on problem modeling, analysisand simulations coupled with software development and concept experimentation. Starting with ultra simplecases (equipments with few ports, networks with few nodes), our aim is to progressively enlarge the problemscale in order to study real operator networks et tools. For this, Reso team and its emergente LinKTiss spinoffwill pursue a tight interaction integrating our industrial partners (Alcatel-Lucent and Orange) in the loop. Webelieve that such a dynamic approach, if supported by our institutions, will strongly benefit to all participatingentities. This activity will also be supported by the HIPCAL project and the newly accepted FP7 IP GEYSERSeuropean project.

Experimental measurements. As said previously, our methodology merges theory and experiments. It is veryimportant to test our solutions on a real testbed. The obtained results provide a feedback that we intendto fine-tune our solutions (like the convergence parameter used in the Lagrangian optimization techniquefor instance). We will use Grid5000. We intend to add wireless nodes to this platform in order to get aheterogeneous testbed.

3 – High-Speed Network’s traffic metrology, analysis and modelling.Regarding this axis, Reso team foresees to reinforce and to focus its traffic analysis activity on two maindirections.

Semantic Networking. Within the framework of the BellLabs-INRIA Joint Lab., our aim is to identify relevantfeatures of traffic data able to discriminate between the underlying classes of applications. The ultimate goalis then to condition differentiated treatments to different flow categories, having in mind to optimize resourcesallocation and sharing. To this end, our work encompasses several facets : sampling theory, statistical char-acterization and modeling of discrete time series (i.e. point processes), parameter estimation, learning theoryfor classification purpose. All these tasks must comply with real time constraints, to guarantee that trafficawareness can be effectively implemented in the core routers of very high speed networks.This project is for us a great opportunity to strengthen our collaboration with the MAESTRO team (INRIASophia Antipolis), which is also partner of the Joint Lab. Concretely, we plan to co-advise two new PhDstudents on these topics, both supported by Joint Lab scholarships.

Performance evaluation An important advantage of our metrology testbed is its ability to generate, under re-alistic network situations, real lived traffics whose origin and transfer conditions are fully controlled. Thisallows us to monitor the buffer occupancy at a bottleneck point and then to relate the congestion characteris-tics (global and per flow loss rates, packets’ drop distribution, transmission delay estimation, etc) to statistical– or geometrical – properties of the input traffic. More precisely, we are concerned with scaling propertiesof aggregated and flow based throughputs (adapting to effectively impacting time scales what has been donewith long range dependence), and on their dependence on the used protocols. This study led us to considerMarkov models of TCP traffics and to devise a new multifractal analysis approach to account for the particulartime varying instantaneous throughput due to these retroactive control mechanisms. We then expect to findsome mapping between this large deviation principle and characteristics of TCP variants, which would explaindifferent measured performances.This study is a joint work with the SISYPHE team of Inria Rocquencourt (J. Barral), and should be reinforcedwith the arrival of a new researcher on queuing and optimization theory.

4 – Network Services for high demanding applications.

The main focus will be on energy efficiency, network virtualisation and traffic awareness.

9. ROMA - Resource Optimization: Models, Algorithms, andScheduling


Permanent researchers: Anne Benoit (MCF ENS Lyon), Jean-Yves L’Excellent (CR INRIA), Loris Marchal (CR CNRS),Yves Robert (Pr ENS Lyon and Institut Universitaire de France), Bernard Tourancheau (Pr UCB Lyon 1), Bora Uçar(CR CNRS), Frédéric Vivien (CR INRIA).

9.2 Self-Assessment

Strong pointsOver the years, the team has steadily produced high quality research results. This is assessed by the publicationtrack, by the involvement of team members in numerous program committees, by the many international collabo-rations the team is involved in, and by the distribution of our softwares.The quality of the team work is best exemplified by the fact that it has attracted five new permanent staff membersover the last three years. These new recruits brought new competencies which, in turn, will help define the teamproject. The international contacts also ensure that the team has a broad and accurate view of the research field atan international scale.The team is regularly re-considering its research and long term objectives. This leads to a smooth and regularevolution of our points of focus. For instance, during the reporting period, the team considered the problematics ofonline scheduling and of scheduling in stochastic contexts, and this for the first time. Also, during the past year, theteam has begun focusing on multicore platforms. and it plans to extend its efforts in that direction.With the arrival of new members, the team has enlarged its scope towards programming models, and more particu-larly to component and service based programming models, and desktop grids.

Weak pointsThe team is involved in the development of the MUMPS software. However, all software development positionsare temporary positions (1 to 3 year positions, most of them in the lower part of the hiring scale), that dependon irregular funding. As a consequence, it is difficult (if not impossible) to have long term development plansand to ensure the necessary software stability and support, even for recognized softwares (this is best exemplifiedwith the MUMPS software, whose future depends on how much time permanent researchers manage to spend onmaintenance, user support and integration of new research).During the last two years, the GRAAL team—from which the ROMA team originates—was split among twogeographically different sites. The team cohesion greatly suffered from this decision, that was a consequence of thestrong penury of working space in the main site of the laboratory.During the last years, the laboratory suffered from recurring administrative under-staffing (increase of the number oflaboratory members, non-permanent administrative positions, natural turn-around of personnel). As a consequence,more and more administrative duties are assured by researchers, which is clearly detrimental to the research work.

9.3 Perspectives

Since the GRAAL project-team was created in April 2004, the number of the team permanent researchers jumped from fiveto twelve (four of the new permanent members being full-time researchers and three holding teacher-researcher positions).Each new permanent member brought to the team new and invaluable skills. As a consequence, the breadth and natureof the problems studied by the team has very significantly evolved. We propose to replace the large and diverse GRAALteam by two small and more coherent teams: ROMA — Resource Optimization: Models, Algorithms, and Scheduling, andAvalon — Algorithms and Software Architectures for Service Oriented Platforms.The former is presented here.

New team ROMA — Resource Optimization: Models, Algorithms, and Scheduling

Keywords: Optimization, Algorithms, Scheduling strategies, Sparse Linear Systems, Software DevelopmentVision and new goals of the team

The ROMA team aims at designing algorithms and scheduling strategies that optimize the resource usage of scien-tific computing applications.

47

48 Part 9. ROMA

Modern computing platforms provide huge amounts of computational power: GENCI’s Jade supercomputer in-cludes 3,057 quad core processors1; the Grid’5000 research grid 3,202 processors2; the EGEE production gridsome 40,000 CPUs3, and the World Computing Grid desktop grid aggregates more than 1 million devices4. Suchhuge computational powers may be used to solve more quickly or more precisely large computational problems.More importantly, they are a sine qua non for scientists devoted to solve problems that are far beyond reach cur-rently. However, a careless use of those platforms would ruin such endeavors. A core belief of the ROMA team isthat resources must be spared: computational time, communication capabilities, energy, memory, etc., when con-sidering computing infrastructures; and throughput, response time, stretch, etc., when considering users. However,resource optimization is quite difficult because these platforms have new, and hard to manage, characteristics: theycontain multicore processors and sometimes specialized processors such as GPUs; they may be distributed on avery large scale, which can significantly impact communications; they may be volatile and even unreliable; andtheir usage may be subject to conflicting objectives from the platform owner(s) and users.To enable scientific computing applications to fully harness modern computing platforms, the ROMA team focuseson:

• the design of algorithms suited for multicore architectures;• the design of multicriteria optimizations which both guarantee the efficiency of platform usage and some

Quality of Service for users;• the design of static approaches able to cope with platform dynamicity;• the design of sparse solvers, which are ubiquitous in scientific applications;• the design and analysis of combinatorial algorithms.

A: Algorithms for Multicore PlatformsThe major recent change in computer architecture is the ubiquity of multicore processors. The number of coresper processor should significantly increase, leading in the near future to many-core processors containing tens orhundreds of cores. Therefore, even on large-scale platforms gathering many processors, it is important to exploitthe parallel capabilities already present inside each processor: the multicore nature of the processing elements is acritical point to achieve good performance.Our first objective is to understand the impact of multicore processors, and to come up with a simple yet realisticmodel for multicore architectures. In particular, while experimenting and optimizing the practical performanceof our algorithms on such architectures, we have to give a special attention to their hierarchical structure, to thedistribution of data storage along this hierarchy, and to the increasing heterogeneity of platforms.Hierarchical structure. Because they contain multicore processors, all modern platforms have a hierarchical struc-ture, and this structure impacts the way algorithms must be designed. In particular, the granularity of computationsmust be hierarchical and adapted to the hierarchy levels. For instance, a linear algebra operation should be dividedinto large blocks at node levels, which in turn are sub-divided into smaller blocks to be distributed to the computingcores. This hierarchical structure is partially described by the NUMA factor (Non Uniform Memory Access), thatis, the ratio between the times taken to reach a data in a far distant memory and in a local one. This factor, however,does not describe other characteristics of the hierarchy, such as potential memory or bandwidth contentions whenseveral sub-parts of a program simultaneously make intensive use of memory or data movement.Distribution of data storage. Another key characteristic of these platforms is the distribution of memories, evenwithin a single computing processor. Cores are provided with a private data cache, of relatively small size, andwith a shared cache of larger size which again eases the access to data and enable data sharing between cores. Ona larger scale, data is distributed into the memory of nodes. Theoretical studies provide cache efficient algorithms,and some recent studies even deal with multicore processors with shared and distributed caches. Most of thesestudies, however, consist in minimizing the number of cache-misses, that is the number of times a value has to beloaded from the memory to a cache line. This model, although interesting to formally assess the cache-efficiencyof an algorithm, is not practical for algorithmic design. In particular, this model lacks several parameters, such ascache latency for each cache level, cache bandwidth, or more generally the number of simultaneous accesses that acache supports. These parameters can greatly influence the performance of a cache-intensive algorithm. We do notlook for an extremely precise execution model, such as those used in VLSI simulation. We rather need to modelthe application-level behavior, so as to correctly predict cache and communications interactions, as well as theiroverlap with computations.Heterogeneity. Future processors are likely to be heterogeneous themselves, as they will certainly incorporatespecial-purpose cores alongside general-purpose ones. This trend is exemplified by the Cell BE processor and theemerging use of Graphical Processing Units (GPUs) for general-purpose processing (GP-GPU). As a consequence,

1http://www.genci.fr/spip.php?article322https://www.grid5000.fr3http://www.eu-egee.org/4http://www.worldcommunitygrid.org

http://www.genci.fr/spip.php?article32

https://www.grid5000.fr

http://www.eu-egee.org/

http://www.worldcommunitygrid.org

§9.3 Resource Optimization: Models, Algorithms, and Scheduling 49

future computing platforms will be far more heterogeneous than existing ones. This will allow us to build on ourexpertise on algorithm design for heterogeneous platforms. Nevertheless, new characteristics will have to be takeninto account, such as: the presence of heterogeneity at a smaller scale; new data movement characteristics (cachemisses are more relevant than communication times); special relationships between hierarchy and heterogeneity (acluster of nodes is likely to include a homogeneous cluster of heterogeneous processors).

There will be two main directions to our algorithmic work on multicore architectures. In the first direction, we willstudy how our previous work on heterogeneous platforms can be adapted to this new architectures, and to whatextent. In this direction, we have already started to adapt our scheduling work on heterogeneous platforms to theCELL BE processor, as an example of heterogeneous multicore processors. As a second direction, we will focuson the optimization of some linear algebra kernels to multicore architectures, both in sparse and dense settings. Fordense linear algebra kernels, we have started investigating the matrix-matrix multiplication on a multicore processorunder the objective of minimizing the number of cache misses (shared cache misses, distributed cache misses, ora combination of both). We also started a study of the algebraic path problem (which models a number of linearalgebra operations), on a more complex architecture, including GPUs and CPUs, which requires a more complexmodeling. For sparse linear algebra, we plan to experiment multicore parallelism based on threads in the parallelsparse direct solver that we develop, MUMPS. By working on the design of an OpenMP version of MUMPS (ontop of MPI), hybrid parallelism using both threads and message passing should help improving memory usage andperformance on multicore platforms. The use of more heterogeneous processors including GP-GPU seems to be alonger term issue that may need to be tackled too. See paragraph D below for the context in which this work onsparse direct solvers will take place.

B: Multi-criteria Optimization. Classical scheduling aims at mapping a task graph, i.e., an application made of severaltasks with dependencies, onto a set of distributed resources and to minimize the makespan, i.e., the execution timeof the whole application. Recent work has shown, however, that in many contexts makespan minimization is notappropriate. For instance, for pipelined applications, the throughput maximization is more meaningful: the goal is toprocess as many data sets per time unit as possible. Going further in that direction, we plan to consider multi-criteriaoptimization problems mixing user-oriented and system-oriented metrics. User-oriented metrics will ensure thatthe produced schedule satisfy some Quality of Service constraints (like the stretch metric which forbids starvation).System-oriented metrics will ensure that system resources are not wasted (like throughput maximization).Among the potential system metrics is energy consumption, a strongly emerging objective given the specific energy-related problems of actual computing platforms (energy cost, problems and cost of cooling), and the global envi-ronmental context. Green scheduling aims at minimizing energy consumption, by running processors at lowerfrequencies, or by reducing the number of processors enrolled. Of course being “green” often involves running at aslower pace, thereby reducing the application makespan or throughput. Minimizing the energy consumption couldtypically be experimented in our parallel sparse direct solver MUMPS, which requires a huge amount of computingpower for large-scale industrial applications. Since performance will still be a significant issue, we will considerbi-criteria optimization techniques that take both performance and energy consumption into account (see paragraphD for more information on the context in which this could be done).Another metric, important for instance on desktop Grids, is the reliability. Indeed, with the advent of very large-scale heterogeneous platforms, resources may be cheap and abundant, but resource failures (computers, commu-nication links, etc.) are more likely to occur and have an adverse effect on the applications. We aim at designingrobust schedules: the schedule should be prepared, so to speak, to react to resource variations, and should be capableto reserve more resources than needed so as to re-allocate computations as the execution progresses, based on somehistogram of the current execution. A solution consists in replicating the processing of key tasks, mapping themonto distinct sets of resources, and gathering results in a data-flow operation mode. The question of determiningwhich tasks to replicate, and to which extent, raises a clear trade-off between the price to pay for robustness (orperformance guarantees) and the efficient usage of resources at the system level.

C: Static Management of Dynamicity. Grid computing platforms and components are subject to a great variability. Sta-tistical models are mandatory to deal with changes in resource performance, such as CPU speeds or link bandwidths.In addition, frequent hardware failures are unavoidable in large-scale platforms composed of several thousands ofprocessors, which calls for deploying robust algorithms capable of surviving several resource faults during execu-tion.At a smaller scale, collaborative environments allow users who have a massive, compute-intensive workload, toenlist the help of others’ computers in executing the workload. The resulting cooperating computers may belong toa nearby or remote cluster of workstations, or they could be geographically dispersed computers that are availableunder global computing or volunteer computing software such as BOINC. These collaborative platforms add varioustypes of uncertainty to the execution. The most dramatic events in this context are unrecoverable interruptions thatkill all work currently in progress on the interrupted computer when being suddenly reclaimed by its owner.In both scenarios, the need for some kind of robustness is obvious. There are two possible approaches:

50 Part 9. ROMA

• React on-the-fly to performance variations and/or failures, by migrating tasks/processes files dynamically,during execution;

• Statically handle resource variability, by designing algorithms that perform redundant computations, andschedules that replicate tasks.

Both approaches have their own merits. The dynamic approach—considered in Paragraph B—is more flexiblebut induces a lot of overhead and monitoring. The static approach (at compile-time) is less costly and does notrequire any complicated save-and-restore mechanism. However, it does require some knowledge of the applicationand platform parameters to be efficient. For instance task replication should not be conducted systematically butonly for those tasks whose success is critical to the application. Along a similar line, when distributing workin a collaborative environment, we face two dilemmas: (i) sending work to remote computers in small chunkslessens vulnerability to interruption-induced losses, but it also increases the impact of per-work-unit overhead andminimizes the opportunities for “parallelism” within the assemblage of remote computers; and (ii) replicating worklessens vulnerability to interruption-induced losses, but it also minimizes the expected productivity advantage fromhaving access to many remote computers. In this framework, the more we know about the probability distributionsthat govern failures and/or interruptions, the better we can tune the job granularity and the replication factor so asto maximize the expected production.In this scope, we plan to revisit some of our previous work on scheduling for heterogeneous platforms, this timeassuming platforms to be prone to failures and/or interruptions. We will mainly focus on problems dealing withdivisible loads.

D: Sparse Direct Solvers. This theme of research is the object of a close collaboration with P. Amestoy (Professor,ENSEEIHT-IRIT), A. Buttari (CNRS researcher, ENSEEIHT-IRIT), and A. Guermouche (Assistant professor,Univ. of Bordeaux). Most often, our research efforts, both collaborative and individual, are combined and im-plemented in the software package MUMPS.The solution of sparse systems of linear equations of the form Ax = b (with A being symmetric or unsymmetric,most often with an irregular structure) is in the core of many scientific applications, usually related to numericalsimulation spanning domains such as geophysics, chemistry, electromagnetism, structural optimization, and com-putational fluid dynamics. The importance and diversity of the fields of application are our main motivation topursue research on sparse direct solvers. Our focus is on solvers based on multifrontal methods (MUMPS imple-ments such a method for sequential and parallel environments). The main issues in such kind of solvers are efficientmemory usage and high performance execution on parallel platforms while demonstrating stringent accuracy andnumerical properties. As our objective is to stay close to applications, our research directions are motivated by theneeds from applications. The following four research directions may evolve depending on the priorities of, andcontracts with, current and future industrial and academic partners.The first research direction concerns memory issues. Memory poses the limits for the use of sparse direct solvers.For example, if a user has a 3D, regular, finite-element mesh of size q × q × q, the asymptotic optimal size of thefactors is of O(q4). To handle such sizes, one can use out-of-core techniques, where disks supplement memory, orparallelism, where the memory of several computing units is used. Throughout the past few years, we have workedon out-of-core aspects in order to find efficient and effective methods for storing the factorized matrix on disk.Further research remains to be done in order to further reuce core memory usage, and we should in particular studyhow one can use disk storage to reduce the working memory requirement of the multifrontal approaches. Beforethat, we will tackle the memory scalability of parallel multifrontal approaches in order to use as efficiently aspossible the distributed memory of parallel platforms. This raises considerations both theoretical (how to schedulethe graph of tasks to minimize and balance memory usage, for example) and practical (how much performance isone ready to lose in order to improve the memory scalability and be able to process larger problems?).The second research direction is related to modern computing platforms such as addressing large numbers of proces-sors (for example Blue Gene machines with thousands of processors) and taking advantage of multicore processors.The memory scalability is clearly an issue for the first point, but communication patterns and performance issuesalso need to be revisited, evaluated, and most likely to be partly redesigned. In order to better address multicorearchitectures (see also paragraph A), we plan to experiment hybrid parallelism (message passing and threads). Wewill also keep an eye on the developments of the standards for GP-GPU (general purpose graphical processingunits) and energy consumption issues (control processor frequency or core usage depending on the computationalphases of the solver, see also paragraph B).The third line of research evolves around the widely-known interplay between combinatorial optimization methods(mostly algorithmic graph theory) and the pre-processing phase of the sparse direct solvers. In current state-of-the-art direct solvers, almost all pre-processing issues are parallelized with some acceptable performance, exceptcomputing weighted matchings in bipartite graphs. A matching corresponds to a set of pivots deemed to be benefi-cial (both from a numerical and a structural point of views) during the later stages of the factorization. Computinga matching is a task of sequential nature, and hence resisted many attempts of parallelization. We plan to compute

§9.3 Resource Optimization: Models, Algorithms, and Scheduling 51

approximate matchings, sacrificing certain optimality properties to achieve an acceptable parallel performance.The fourth research direction concerns the QR decomposition, which is used for sparse least-square problems forexample, and has many applications. The ambitious long-term plan consists in developing a parallel distributedcode for least-square problems. There are tight relations with the third research direction as matching techniques(this time cardinality matching) are used extensively in the QR decomposition. Furthermore, the issues relating tomemory use are also highly likely to arise.

E: Combinatorial Scientific Computing. This theme of research, in general, concentrates on development, application,and analysis of combinatorial algorithms to enable scientific and engineering (SCE) computations. Here we restrictto the solution of linear systems of equations with direct and iterative methods. We enlarge the applications of com-binatorial techniques to high-performance computing applications through the use of task scheduling algorithms.Our point of view is that there are commonalities between task scheduling problems for high-performance comput-ing applications, and the partitioning/ordering problem for SCE applications. Therefore, the solutions designed forone set of applications can be used to design solutions for the other set. Similarly, the problems that arise naturallyin one set can be used to imagine different scenarios for the other set. The end result, therefore, is the enrichmentof the models and methods for the two domains. Below, we describe the application of hypergraph partitioning toscheduling file-sharing tasks, and we pose a variant of the partitioning problem which naturally arises in the taskscheduling domain. In this case, a known technique from SCE is carried over and enriched. The application of theenriched model to the SCE is going to be evaluated.In hypergraph models used for some task scheduling problems, vertices correspond to tasks, and hyperedges corre-spond to files that tasks take as input. The general modeling approach, then, asks for a partitioning of the verticesof the hypergraph into a given number of parts such that the parts have equal vertex weights, and such that a linearfunction of the hyperedges that have vertices in two or more parts is minimized (called cutsize). In the task schedul-ing problem, these two objectives relate to balancing the loads of the processors and minimizing the communicationcost. The partitioning problem is NP-hard, and hence efficient heuristic approaches are needed.An important aspect of the hypergraph model is that all vertices in an hyperedge are equally related. For example,the set of tasks that take a particular file as input are all assumed to incur the same cost. Therefore, in a computingplatform where the communication costs are not uniform, the model cannot capture the heterogeneity. This was anissue in early papers and had been approximated by using an average cost for each hyperedge. In this proposal, weaim to enrich the hypergraph models to encapsulate the non-uniformity among the vertices in an hyperedge. Sucha model has never been imagined before, and therefore a number of fundamental questions should be posed andsolved, such as (i) what is the proper definition of a cutsize? (ii) is the partitioning problem still NP-hard?We believe that such an enriched hypergraph model would open a new direction in modeling different problems andwould have applications in scientific computing domain as well. Here we focus on the applications in schedulingfile-sharing tasks. Consider a duplicated file residing in two different servers where a task needs that file forexecution. The task thus can download the file from either of the servers, each entailing a different cost due tothe heterogeneous communication network. In hypergraph terms, the vertex that corresponds to the mentionedtask should be connected to the two hyperedges representing the same file but with different weights. How shouldwe partition the hypergraph, and how should we decode the partitioning information (which hyperedge should betaken into account while calculating the partitioning—returning back to the quest of searching for a proper cutsizedefinition)?Another aspect that we will address within this modeling framework is task duplication to reduce costs. In hyper-graph terms, this corresponds to selectively duplicating some vertices in order to reduce the cutsize. The problemhas already been addressed in the VLSI community for the standard hypergraph models. Due to the heterogeneityin the communication medium, the approaches proposed in those works again would not be fitting to the presentedframework, thus new algorithms are needed. We also think that it is possible to address the task and file duplicationsimultaneously by integrating enriched hypergraph model (to encapsulate file duplication) and vertex duplication(to encapsulate the task duplication).

52 Part 9. ROMA

10. IT Support Team MI-LIP


Permanent engineers: Mignot Jean-Christophe (IR CNRS, 50%), Ponsard Dominique (IE CNRS), Torres Serge (IRENS, 60%).

10.2 Self-Assessment

Strong points

• Experienced and mostly stable work force: most engineers are in the LIP for several years and are wellintegrated within the laboratory and the ENS de Lyon.

• The process of organizational strengthening and strategic refocusing: this will help to have, on one hand, amore robust infrastructure and, on the other hand, allow for a more optimal use of resources;

• A wide and rather coherent base of services and platforms: along the years, the team has built a suite ofelements that provide a confortable working environment for the laboratory. Future work will be able tocapitalize over the existing base to extend and upgrade it.

Weak points

• Insufficient work force and the effects of fixed term contracts: man power is chronically insufficient. (Endof) Fixed term contracts shake the team operation, especially for the GRID’5000 management area. This isexacerbated by the low manpower issue.

• Slowness and precariousness in organizational evolution: it takes a constant effort to maintain the focus onobjectives and plans. This applies to the internal functioning of the team and to the coordination with thelaboratory as well.

• To loose supervision and security: not enough attention has been given so far to the monitoring of the in-frastructure and, too often, malfunctions are reported by users rather than by automatic supervision systems.Security issues have not been systematically analyzed and addressed even if this aspect is not overlooked forsome critical systems.

Opportunities

• The arrival a (several) new permanent engineer(s) : this would relax the work load tension and allow for adifferent organization. The arrival of “young blood” would also be an occasion to reconsider current workingmethods and technologies.

• Evolution of the context caused by the creation of a new school and the so-called “Plan Campus”: this opensnew opportunities for access to computing services and expertise (“Centre Blaise Pascal”, synergies aroundscientific computing in the Lyon area).

Risks

• Departure of a member. This risk has already materializing with the departure of Aurélien Cedeyn. But othersare possible, if not presently planed. The seniority of the team members and their long standing in their presentposition makes them eligible for an assignment to other duties, should one of them want to make a transfer. Inthe current situation, this would seriously jeopardize the day-to-day operation of the team, not to speak aboutit’s future plans.

• Freeze in computing IT investments at ENS de Lyon: present indications and lack of formal commitmentof the ENS management in the development of IT infrastructure for research (mainly data center / computerroom) rise some concern about the possibility for the LIP to expand it’s platform development. GRID’5000is the first threatened project and the laboratory could be deterred from taking new initiatives in the realm ofresearch instruments by a lack visibility on it’s ability to host them.

• Disruption, in the of the creation of the new ENS de Lyon, of the present mode of cooperation establishedwith the current ENS de Lyon PSI.

53

54 Part 10. MI-LIP

10.3 Perspectives

KeywordsVision and new goals of the team

The future of team’s activity is delineated by a vision where the lab carries on with the current projects and has theability to take new initiatives as needed by the development of research in the laboratory.

The stand of the MI-LIP is based on the conception that the most efficient use of its limited manpower is to use itto support research projects of the laboratory. In fact, research engineers of MI-LIP are already part-time directlyinvolved in research teams, this will probably become the norm for all. As a consequence, we will try to rely asmuch as possible on our partners for vanilla services. For instance:

• We have got rid our own authentication system to rely on the ENS information system connected authentica-tion infrastructure.

• We will participate in the ENS-wide file service system instead of, as we did up to now, develop our ownsolution.

• We have tried, with little success so far, to involve the other laboratories of the ENS in the definition ofcommon tools and procedures for the management of Linux workstations.

This is not always possible and sometimes, after a carefull analysis, we will locally continue to offer basic serviceswhen proximity and tailoring to specific needs are requested. One of our primary goals remains to offer an efficientwork environment to the laboratory scientists. Efficiency in this realm involves :

• responsiveness;

• personalization;

• uncluttered user computing environment despite the increasing complexity of the infrastructures.

In the case of high-end services, such as high performance computing, we do not try to compete with actual andneighboring computing centers such as PSMN (Pôle Scientifique de Modélisation Numérique, a local mesocenter)not to speak of the IN2P3 (one of the largest french computing centers based in Lyon). Nevertheless, we willcontinue to try and offer a varied computing environment, including some rather powerfull equipments, to helpour scientists to develop and debug their experiments in a familiar environment. When vast amounts of computingpower are really required, we will help them to transition to platform more fit to their needs.

This leaves room for the involvement with possibly large and/or technologically advanced research (as opposed toproduction) infrastructures such as GRID’5000 or Décrypthon. Experience already gathered in these two projectscan be levered for their next stages as well as for other initiatives. This confers a greater value to the skills of themembers team and helps the vivify their interest in their trade.

This vision also includes the idea that not all the engineers of the lab should be members of the MI-LIP team. Manyof them, in fact a majority, are directly embedded in research team and work on specific projects. The laboratoryfinds this organization more efficient than a “cleaner” solution (from a mere management perspective) such asflocking all the engineers in a single administrative entity. Besides, such a gathering would be in contradiction withthe organization in INRIA, were engineers are directly attached to projects. It does not mean a lack of interchangesbetween engineers, no matter what their internal affiliation is. They do exist, though informally, and could be furtherextended with initiatives such as an “engineers seminar”, similar to the scientific seminars held in the laboratory.There are plenty of technical topics of general interest to fill the agenda of, say, monthly meetings.

The merger of ENS de Lyon and ENS LSH to create a new research and higher education institution, that will hostmost of the laboratory activities, may significantly alter the context of IT operations and, as a consequence, impactthe MI-LIP activities. Due care will have to be given, in coordination with other research labs, to preserve and,possibly improve the fruitful cooperation established with the PSI of the current ENS de Lyon.

Evolution of Research (support) activitiesFor the forecoming period the main activity axis and goals will be:

Local infrastructure

• Consolidate the team: incorporate of new engineers, strengthen operations (more formal managementrelying on standards, such as 2700x and best practices).

• Develop monitoring, and, in general, all the aids that allow for a more proactive management of theinfrastructure.

§10.3 IT Support Team 55

• Define and enforce of a security policy for the laboratory (PSSI) what can efficiently done only at campuslevel (in the frame of the new ENS de Lyon).

• Rationalize the computing infrastructure: virtualization, setup new and more cost efficient solutions (e.g.merge departmental xerocopying and network printing into a single system).

• Fortify the supporting infrastructure: computer room cooling and powering, participate in new infrastruc-ture projects.

• Switch to IPV6: this change, driven by powerfull external factors, will have a deep inpact on all our IToperations.

• Setup new tools to enhance and professionalize user support (e.g. request tracker system) and to create,as well “interruptibility shields” for the engineers (to allow for a more efficient work).

Large scale research instruments

GRID’5000: In the forseeable future, GRID’5000 will remain the single most important project the MI-LIPwill be involved with. The ADT ALADDIN-G5K initiative, the ongoing flow of new experiments andprojects based on this platform and the commitment of the LIP to it’s development make it a clear priorityfor the MI-LIP team. Lots of improvements and evolutions are planed, at project level, that the Lyon nodewill have to participate in and/or comply with:

• Increase the node capacity in Lyon: we are still far from the minimum requirements of 500 sock-ets/cores per Grid’5000 site. Actions (funding, government contract, hardware installation, incorpo-ration into the platform) will have to be taken. But this implies that some issues are solved before-hand...

• Fix the infrastructure hosting problems in ENS de Lyon, and if not possible, find another solution!• Integrate the services more tightly using Puppet or a similar framework.• Setup an advanced network monitoring solution. The current devices do not allow for a sufficient

level of control, new tools are needed.• Enforce a better network control: e. g. give the ability to transport VLANs between distant nodes all

over the platform.• Switch to IPV6 with public addresses. Switching to IPV6 will probably a necessity in the forecoming

period (see before). It will also be an opportunity, using public addresses, to improve the usability ofthe platform. Beyond the mere deployment of IPV6, this also implies a strengthened security.

This wealth of project allows us to put some emphasis again on the stable manpower that is needed toachieve them.

Décrypthon: Lyon will remain a node of the project. As stated before, MI-LIP participation will consistessentially of offering healthy hosting conditions and basic system administration. The fixed term contractengineer hired in 2009-2010 will be embedded into the team that drive the research activity. Should theproject grow, the MI-LIP would be able to cope with the increased needs.

Other projects: Stating that research is an unpredictable activity is a classical cliché and can’t be an excusefor a lack of planning. But, up to a certain point, it holds a bit of truth, especially nowadays : projects canemerge at any time and this period is particularly fit for unexpected events. The context of IT research isquickly moving at different scales (national, regional, local) and, without incurring the waste of withold-ing usefull resources for hypothetic new projects, we must be ready to adapt our plan, should the situationchange. In more specific term that means the team must maintain a good level of basic infrastructures(with some margin) and technical proficiency to be able to accommodate in good conditions with, at least,the early steps of new projects. Their full development is different story...

Documents

Laboratoire de l’Informatique du Parallélisme › LIP › ralip2009 › projet.pdf · La maîtrise de cette complexité demande toujours plus de connaissances, avec une machine