Parallel algorithms and parallel programming

Program

Parallelism is now ubiquitous in computers because all modern computers contain multicore processors. This lecture series focuses on the design of efficient parallel algorithms and on their actual implementation. The lectures will deal with the theoretical models used to design and analyze parallel algorithms. A number of classical algorithmic problems will be studied in details: complexity study, algorithm design and analysis, approximation algorithms, etc. The lectures will be supplemented with six exercise sessions, and six laboratory sessions. The aim of the lab sessions is to introduce students to parallel programming through message passing (MPI).

Overview

  • The theoretical model of sorting networks
  • The theoretical model of PRAMS
  • Algorithms on processor rings and processor grids: vector-matrix product, matrix-matrix product, 2D stencils, etc.
  • Taks graph scheduling, with and without communications, with and without resource constraints: complexity, approximation algorithms, and heuristics
  • Dependence analysis and automatic parallelization
  • Introduction to algorithms for GPUs

Students will be graded through a final examination and a continuous assessment. The continuous assessment will comprise both a mid-term examination and a programming homework.

Teachers

Performance evaluation

Description :

This course presents basic tools for qualitative and quantitative performance evaluation of communication and computing systems. It is a
theoritical course but some real systems will be analyzed such as communication networks. This course will also present an introduction to
statistics and some discussions about the experimental method.

Plan of the course :

  1. Short refresher about probability prerequisites
  2. Simulation schemes and random generation
  3. Discrete time Markov chains
  4. Continuous time Markov chains and queuing theory
  5. Markovian decision process
  6. Petri nets
  7. Statistics

Prerequisites :

A classical but strong background in probability is necessary (like some knowledge about finite state Markov chains or convergence of random  variables).

People in charge of the course:

  • Eric Thierry (a web page dedicated to the course will be made available from E. Thierry’s page).
  • Julien Herrmann

Distributed Systems

Program

This lecture focuses on algorithmic for distributed systems. We will introduce distributed algorithms to solve communication problem, resource allocation, synchronization, … Thus leader election problems, waves algorithm, termination, routing, fault tolerance, self-stabilization, etc. are some examples that we will see  during the lecture. Different kind of distributed system programming and implementation will be studied through ERLANG, CORBA or the DIET middleware.

Speakers

Language

English upon request.

ER-01 : Algorithms for geometric approximation

From the 11th to the 15th of January 2010 — ENS Lyon

Goals

More and more fields like biology, statistical analysis or machine learning, have to deal with data which are actually scatter plots in high dimensional spaces. These data have some topological and geometrical characteristics that express the properties of the modelled systems. For instance, the density of a scatter plot may be concentrated around a variety of intrinsic dimension much lesser that the one of the ambient space. Extracting such an information is not an easy task. First, the data suffer from some noise. Then, the structures and the algorithms of algorithmic geometry often have complexities that increase exponentially with the dimension and are not well scalable for this kind of data.

This series of lectures proposes an introduction to algorithmic geometry, focused on the approximation and geometrical object sampling issues. It starts from classical concepts (convex hull, Voronoi diagrams) and addresses recently developed methods (core sets, topological persistence) in order to approximate the geometrical and topological properties of higher dimension objects, while avoiding the exponential explosion of complexity related to the dimension.

Lecturers

  1. Jean-Daniel Boissonnat
  2. Frédéric Chazal
  3. Mariette Yvinec

Outline of the course

Algorithms for geometric approximation

  1. Metric structures for point sets
    • Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat)
    • Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal)
    • Randomized algorithms and core sets (M. Yvinec)
  2. Simplicial approximation of manifolds
    • Mesh generation by Delaunay refinement (M. Yvinec)
    • Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat)
    • Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat)
  3. Geometric inference (F. Chazal)
    • Sampling theory for compact sets
    • Persistent homology and data analysis

Prerequisite

The course is self-contained.

Bibliography

  • M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
  • J.-D. Boissonnat and M. Teillaud, editors. Effective Computational Geometry for Curves and Surfaces, Springer-Verlag, 2006.
  • J.-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
  • F. Chazal, D. Cohen-Steiner, Geometric Inference, submitted as a chapter in a book entitled “Tesselations in the Sciences”, November 2007.
  • F. Chazal, D. Cohen-Steiner, A. Lieutier, A Sampling Theory for Compacts in Euclidean Space, Proceedings of the 22nd ACM Symposium on Computational Geometry 2006.
  • E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.
  • K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
  • A. Zomorodian, Topology for Computing, Cambridge Monographs on Applied and Computational Mathematics, cambridge University Press, 2005.

Registration

There are no registration fees. For organization reasons it is however necessary to register online; [registration closed].

Location and schedule

All the lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).
A tentative schedule:

  • Monday, January 11
    • 2:00 PM – 5:00 PM. Convex hulls, Voronoi diagrams and Delaunay triangulations (J.-D. Boissonnat).
      Slides available here then here.
  • Tuesday, January 12
    • 8:30 AM – 11:30 AM. Mesh generation by Delaunay refinement (M. Yvinec).
      Slides available here then here.
    • 1:30 PM – 4:30 PM. Restricted Delaunay triangulation, e-samples and surface mesh generation (J.-D. Boissonnat).
      Slides available here.
  • Wednesday, January 13
    • 8:30 AM – 11:30 AM. Dimension reduction, approximate nearest neighbor search, the k-means algorithm (F. Chazal).
      Slides available here.
    • 1:30 PM – 4:30 PM. Randomized algorithms and core sets (M. Yvinec).
      Slides available here then here.
  • Thursday, January 14
    • 8:30 AM – 11:30 AM. Sampling theory for compact sets (F. Chazal).
      Slides available here.
  • Friday, January 15
    • 8:30 AM – 11:30 AM. Manifold reconstruction in 3 and higher dimensions (J.-D. Boissonnat).
      Slides available here.
    • 1:00 PM – 4:00 PM. Persistent homology and data analysis (F. Chazal).
      Slides available here.

Local organizers

There are several useful informations on the main page of the research schools in Computer Science at ENS Lyon.

ER-02 : Graphs and Combinatorial Optimization

du 18 au 22 janvier 2010 — ENS Lyon

Intervenants :

Lieu des cours et emploi du temps

Tous les cours auront lieu dans l’amphithéatre B, au 3ème étage du bâtiment GN1 (bâtiment principal du site « Sciences » de l’ENS Lyon), ENS Lyon, 46 allée d’Italie, Lyon 7ème.

Lundi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-17h15)
Mardi : Louis Esperet (8h-10h) ; Andras Sebö (10h15-12h15)
Mercredi : Andras Sebö (8h-10h) ; Myriam Preissmann (10h15-12h15) ; Andras Sebö (14h-16h)
Jeudi : Myriam Preissmann (9h30-12h45)
Vendredi : Frédéric Maffray (9h30-12h45) ; Louis Esperet (14h-16h)

Louis Esperet (slides -> cours1, cours2)

Cours 1 (Lundi 14h-17h15) Coloration vs. coloration par listes

  • méthodes inductives (Thomassen)
  • déchargement

Cours 2 (Mardi 8h-10h) Graphes sans triangles et coloration

  • constructions
  • méthodes probabilistes (premier moment)

Cours 3 (Vendredi 14h-16h) Coloration fractionnaire, coloration d’hypergraphes

  • méthodes algébriques (Borsuk-Ulam)
  • méthodes probabilistes (Lemme Local de Lovasz)

Frédéric Maffray (fiche exercices -> télécharger Fiche)

Cours 1 (Lundi 9h30-12h45):

  • Introduction du concept de graphes parfaits
  • Graphes triangulés, décomposition par clique d’articulation, sommets simpliciaux, ordre d’élimination, algorithme MCS,
  • utilisation de ces structures pour résoudre les problèmes d’optimisation (coloration, clique max, stable max).
  • Représentation d’un triangulé comme graphe d’intersection de sous-arbres d’un arbre.
  • Exemples de graphes triangulés: graphes d’intervalles, graphes “splits”.

Cours 2 (Vendredi 9h30-12h45):

  • Relation entre nombre chromatique et orientation (Gallai-Roy)
  • graphes de comparabilité, ensembles partiellement ordonnés,théorème de Dilworth.
  • théorème de Lovasz (parfait = complémentaire de parfait)

Myriam Preissmann

Cours 1 (Mercredi 10h15-12h15) :

  • Flot maximum
  • Algorithme “Push-Relabel” et flots paramétriques.
  • Calcul de l’arête-connectivité d’un graphe non orienté avec, et sans calcul de flot max.

Cours 2 (Jeudi 9h30-12h45) :

  • Flot de coût minimum.
  • Les k-flots non nuls.
  • Théorème du 8-flot.

Andras Sebö (fiches d’exercices -> télécharger Fiche 1, Fiche 2)

Cours 1 Mardi (10h15-12h15)

  • Quelques modèles d’optimisation combinatoire.
  • Matroïdes, algorithme glouton et polytôpe associé.

Cours 2 (Mercredi 8h-10h)

  • Algorithme de l’intersection de deux matroïdes.
  • Applications.

Cours 3 (Mercredi 14h-16h)

  • Algorithme de couplage de cardinalité maximum (Edmonds).
  • Théorème de caractérisation lié (Tutte-Berge).
  • Applications et généralisations.

S’il y a des questions sur les exercices de la fiche fournie ci-dessus, vous pourrez les poser après le premier cours.

Bibliographie : Schrijver: Combinatorial Optimization; Lovász, Plummer: MatchingTheory; Lovasz: Combinatorial Problems and Exercises,

Autres informations pratiques

Voir la page des Ecoles du Master d’Informatique.

Correspondant local

Eric Thierry (prenom.nom@ens-lyon.fr)

ER-03: Game theory for networks

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

Location and schedule

All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).

Schedule:

  • Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
    Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc.  We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value.   Solution of 2 by 2 matrix games.
    Non-zero sum games. We present the notion of Nash equilibrium as   well as epsilon Nash equilibrium. We then introduce    Coordination Games and present their properties. We then study    Lemke’s algorithm for computing the equilibrium in non-zero sum games    with two players. We present examples of channel selection games.   We end this part with the concept of Correlated equilibrium

    Afternoon: Corinne Touati 14h30 – 17h00
    Notions from cooperative game theory: Bargaining and fairness.
    Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
    1. Optimalité
    a. Définition de Pareto et notions liées
    b. Propriétés des ensembles de Pareto (par ex. compacité)
    c. Epsilon-approximation et méthodes de résolutions
    d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.

  • Tuesday 26/01/10  Morning: Corinne Touati 10:30 – 12:30
    2. Fairness and Nash bargaining.
    a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
    b. Equivalent optimizations and properties
    c. Alpha fairness
    d. Algorithmic solutions.
    e. Application to flow control and TCP.
    3. Performance evaluation of the resource allocation:
    a. The Gain index,
    b. Price of anarchy
    c. Selfish Degradation Factor
    d. Pareto equilibrium

    Afternoon: Eitan Altman 14:00 – 16:30
    Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria,   The strict diagonal concavity property (which extends concavity    to a game context). This notion is used to establish    uniqueness of equilibrium in convex games.
    We then introduce games with coupled constraints    as in Rosen, as well as the related    notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.

  •  Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
    Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
    Medium access games: the aloha game.

    Afternoon Rachid El-Azouzi 14:00 – 17:00
    Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
    Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
    Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.

  • Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
    Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
    Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.

    Afternoon: Corinne Touati 14:00 – 17:00
    Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence

  • Friday 29/01/10Morning: Eitan Altman  11:00  – 13:00
    The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium.  Parallel links. Load balancing problems. Relation to Ad-hoc networks.

    Afternoon: Eitan Altman 14:30 – 17:00
    Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.

Correspondant local

  • Paulo Goncalves

ER-04 : New computation paradigms: physics-like models of computation, efficient algorithmics

From the 1st till the 5th february  2010 — ENS Lyon

Intervenants :


Schedule: (Amphi B of ENS-Lyon)

  • First part: Mon. 14:00-18:00, Tue. 14:00-18:00, Wed. 9:00-13:00.
  • Second part: Wed. 14:00-17:00, Thu. 9:00-12:00 & 14:00-17:00, Fri. 9:00-12:00.

Course outline :

Our understanding of what a computer is (models of computation)  and of the way one
 may use  it in  order to solve mathematical problems(algorithmics) is under
 constant evolution. Beyond  the traditional approach, which is essentially based
 upon deterministic discrete systems (automata  of all sorts), a new vision is
 emerging which considers that probabilistic phenomena (randomness, approximations)
 and even quantum phenomena (interference, entanglement) should not be seen as just
 added difficulties, but rather as novel tools awaiting to be exploited and offering
 remarkable  perspectives. What are the limits of the traditional approach which we
 can overcome with these new tools? What more can we expect from them?
Lecture 1 (P.Arrighi) : Quantum information, causality and cellular automata
Lately quantum physical phenomena turned out to be extremely useful for speeding up
 or securing a number of important information processing and communication tasks.
 In the last 15 years, rather impressive theoretical results show that qualitative
 and quantitative performances would then become possible, beyond reach of classical
 computation. For instance it was proved that a quantum computer can factorise an
integer number in polynomial time, or search for an element within a unstructured
list of n elements, in time square root of n. These results are a threat to contemporary
 cryptography, but what quantum physics takes on the one hand, it gives it back on
the other. Some quantum communication systems, already available in industry, warrant
 provably unconditionnally secure communication channels.
This module provides background material from linear algebra, then from quantum
 mechanics. Then main results relating to the particular, non-local nature of quantum
 information are then given. The course is then oriented towads the quest for a model
 of computation which is quantum and distributed at the same time, and that takes into
 account several of the fundamental symmetries of physics (causality,
 translation-invariance). This will bring us to the study of themes such as causality
 in quantum mechanics, the definition of cellular automata in such a context, the
 nature of the interplay  between Physics and Computation.
Syllabus:
- Linear algebra
- Postulates of quantum theory
- Explorations on the nature of quantum information (Deutsch's algorithm,
No-distinguishing, No-cloning, Super-dense coding, Teleportation)
- Density matrices, quantum operators
- Entanglement (classification, non-local boxes)
- Causal operators and their structure
- Cellular Automata : three definitions and their equivalence
- Axiomatic definition of quantum cellular automata
- Structure theorems
- Universal quantum cellular automata

LECTURE 2 (F. Magniez) : Efficient algorithmics
This course aims at tackling those techniques which enable the construction of
 efficient  algorithms for  a variety of contexts. These techniques rely on
tools stemming from  probabilities and approximations. The contexts model the
 sort of constraints that we are placing upon the machine in terms of
resources (time, space, randomness, query, comunication) and data access
(unconstrained (random access), or sequential (streaming)).
The themes we will hence cover:
- Random walks: k-SAT, (s,t)-CONNECTIVITY in RL
- Expander graphs: derandomizaton, (s,t)-CONNECTIVITY in L
- Approximation algorithms (approximation on the output)
- Property testing (approximation on the input)
- PCP Theorem  (light version): application to inaproximability results
- Streaming algorithm
- One-way communication complexity: application to non existence of
 streaming algorithms

Correspondant local

  • Pablo Arrighi

ER-05 : Game semantics and linear logic

February, 8-12, 2010 — ENS Lyon

Lecturers :

Introduction

Linear logic was introduced by Jean-Yves Girard in 1986 as a
refinement of intuitionnistic logic. In the context of the
Curry-Howard correspondence between proofs and programs, linear logic
has renewed a lot of questions in proof theory in relation with the
semantics of programs.

Partly inspired by models of linear logic, game semantics provided in
1994 the first fully abstract model of the functional programming
language PCF. It has evolved towards the interpretation of various
additional programming features as well as applications to the
verification of programs.

These topics have evolved in two separate directions (proof theory for
linear logic, and programming semantics for game semantics) but with
many transfers of ideas between them along the past fifteen years.

Location and schedule

The lectures will take place in “amphithéatre B”, at the 3rd floor of the GN1 building (main building at 46, allée d’Italie).
Tentative schedule:

  • Monday, February 8:
    • 10:00 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Tuesday , February 9:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Wednesday, February 10:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 4:30 PM Linear logic
  • Thursday, February 11:
    • 9:30 AM – 12:30 AM Linear logic
  • Friday, February 12:
    • 8:30 AM – 11:30 AM Game semantics
    • 1:30 PM – 3:00 PM Game semantics

On thursday, Febr. 11 afternoon, the
Choco seminar , on related topics, might also interest the participants.

Course outline

Course 1: Game Semantics with Applications [in English, 12h]

Dan Ghica (University of Birmingham)

content:

  • basic concepts of game semantics
  • the fully abstract game model of a procedural concurrent programming language
  • concrete algorithmic representations of game models
  • applications of finite-state game models to program verification
  • approximating and refining game models
  • a survey of more advanced techniques for program verification using game models
  • Geometry of Synthesis, a categorical framework for circuit design
  • extracting circuit descriptions from game semantics
  • a survey of open problems in game semantics and applications

Course 2: Linear Logic [12h]

Lorenzo Tortora de Falco (University of Roma 3)
Olivier Laurent (LIP – ENS Lyon)
content:

  • sequent calculus for linear logic (1h30, monday LTdF)
  • proof-nets (3h, monday, tuesday LTdF)
  • translations of intuitionistic and classical logics (3h, tuesday, wednesday OL)
  • the coherent model and the relational model (1h30,wednesday LTdF)
  • geometry of interaction and game semantics for linear logic (3h, thursday OL)

(LTdF: Lorenzo Tortora de Falco, OL: Olivier Laurent)

References and documents

Course 1:

  • Dan Ghica. Game semantics of programming languages with applications. February 2010.
  • Dan Ghica, Andrzej Murawski. Angelic Semantics of Fine-Grained Concurrency. ( pdf ) Annals of Pure and Applied Logic, Volume 151, Issues 2-3, February 2008, Pages 89-114

Course 2:

  • Olivier Laurent. Théorie de la démonstration. pdf . pages 89-90 (section 5.3), 87-89 (section 5.2), pages 143-150 (chap. 10), pages 111-122 (chap. 7), pages 130-134 (section 8.3)
  • Samson. Abramsky. Semantics of Interaction: an introduction to Game Semantics. pdf pages 1-14.

Local contact

There are several useful informations on the main page of the research schools in Computer Science at ENS Lyon.