Year: 2012

January 21-25, 2013, ENS Lyon.

Speakers: Manuel Bodirsky, Michael Pinsker.

A Constraint Satisfaction Problem (CSP) is a computational problem where the task is to decide for a given finite set of variables and constraints whether there is an assignment to the variables that satisfies all constraints. Many computational problems in various areas of theoretical computer science can be modeled in this way.

If the variables take their values in some finite domain, there is a rich universal-algebraic theory that describes those constraint languages whose CSP is NP-hard, and those whose CSP is in P. In this course, we present a powerful generalization of this approach to CSPs where the underlying domain is infinite.
After introducing the necessary background in model theory, the course will also cover recent applications of structural Ramsey theory that have led to complexity classification results for large classes of CSPs.

Outline of the course

Monday: Examples of CSPs from Artificial Intelligence. Primitive positive formulas and NP-hardness proofs. Some efficient algorithms. The Feder-Vardi conjecture.

Tuesday: The universal-algebraic approach. The Inv-Pol Galois correspondence. The core of a structure. The tractability conjecture. Cyclic operations. Exercices.

Wednesday: CSPs on infinite domains. Fraïssé limits, the Ryll-Nardzewski theorem. The Inv-Pol correspondence on infinite domains. The topology of simple convergence.  Henson digraphs and other examples.

Thirsday: Introduction to Ramsey theory. Canonical functions. The classification of Graph-SAT problems.

Friday: Open problems, proposals of research projects. Exam and discussion.

Local contact: Pascal Koiran

Registration

Registration is free, but there is a limit on the number of participants and it does include neither housing nor meals (though for lunch the attendees will be granted access to the student cafeteria). Registration should be made before Monday, December 3, by clicking on this link and filling in and sending the e-mail form. You shall receive a confirmation as soon as possible.

Alternatively, you can copy/paste and fill the following form and send it by e-mail to research.school.1@gmail.com, with subject “Registration form — research school 3”

First Name:
Last Name:
Institution:
Position (MSc student, PhD student, researcher, etc.):
E-mail address:
wishes to attend the research school ‘Constraint satisfaction problems’, taking place at ENS Lyon, from Jan. 21 to Jan. 25.

January 14-18, 2013, ENS Lyon.

Speakers

Francesco Zappa Nardelli (INRIA), Mark Batty (University of Cambridge), Alastair Donaldson(Imperial College London), and Martin Vechev (ETH Zurich)

Slides

Available from here

Abstract

Optimisations performed by the hardware or by high-level language compilers can reorder memory accesses in various subtle ways. These reorderings can sometimes be observed by concurrent programs, exacerbating the usual problems of concurrent programming. The situation is even worse when we abandon traditional shared memory concurrency in favor of graphics processing units (GPUs) or exotic hardware. In these lectures we will cover recent progress in understanding and specifying the behaviour of some major processor architectures and the impact of optimisations performed by high-level programming language compilers, stablishing a solid basis for shared memory programming. We will then explore techniques which can help programmers develop reliable concurrent software by automatically discovering the necessary synchronization. We will also discuss techniques for verification of multicore software, including GPU kernels.

Schedule:

• Monday:
  • 10h30-12h30: Welcome + introduction
  • 14h: Batty: x86TSO
  • 15h30-16h30: TD: x86TSO
• Tuesday
  • 9h-10h30: Batty + Zappa: ARM & Power
  • 11h-12h30: Zappa : Compiler Optimisations + DRF
  • 14h-15h: TD: ARM & Power
  • 15h30-16h30: TD: Compiler Optimisations + DRF
• Wednesday
  • 9h-10h30: Batty : C11
  • 11h-12h30: Vechev (1)
  • 14h-15h: TD : C11
  • 15h30-16h30: TD : Vechev
• Thursday
  • 9h-10h30: Vechev (2)
  • 11h-12h30: Alastair (1)
• Friday
  • 9h-10h30: Alastair (2)
  • 11h-12h30: TD: Alastair
  • 14h-15h30: Mini-exam

For the practical sessions

Please bring your laptop with you. In case you do not have one, please get in contact with Filippo Bonchi (ens-lyon.fr).

Contact: Filippo Bonchi.

Registration

Registration is free, but there is a limit on the number of participants and it does include neither housing nor meals (though for lunch the attendees will be granted access to the student cafeteria). Registration should be made before Monday, January 8, by clicking on this link and filling in and sending the e-mail form. You shall receive a confirmation as soon as possible.

Alternatively, you can copy/paste and fill the following form and send it by e-mail to research.school.1@gmail.com, with subject “Registration form — research school 2”

First Name:

Last Name:

Institution:

Position (MSc student, PhD student, researcher, etc.):

E-mail address:

wishes to attend the research school ‘Semantics and tools for low-level concurrent programming’, taking place at ENS Lyon, from Jan. 14 to Jan. 18.

George Bosilca et Thomas Hérault,

University of Tennessee Knoxville

December 10-14, 2012, ENS Lyon.

During this course, we will discuss fault tolerance techniques for high performance computing systems.

Motivation.

In June 2008, the LANL’s Road Runner computing system was the first to  cross the hallmark of one Petaflop based on the Linpack benchmark (reaching $1.026 \cdot 10^{15}$ double precision floating point operation per second). Today, only 4 years later, the fastest computing system, the Sequoia BlueGene/Q at LLNL, sustains 16.324 Petaflops. Continuing on the same path, it is expected that as early as 2022, computing systems will conquer the 1 Exaflop milestone ($10^18$ flops). After the multicore revolution of 2000, such performance became achievable only by multiplying the number of computing components (cores) in the parallel machine. When the 2008 Road Runner machine had 122,400 cores, distributed over 20,000 heterogeneous nodes, today’s Sequoia systems exhibits no less than 1,572,864 cores, distributed over 100,000 nodes. The drawback of such exponential increase in the number of components is a disruptive decrease in the reliability of the entire

system. Indeed, the Mean Time To Interruption, defined as the average duration for which all the components of the platform behave as specified, is inversely proportional to the number of components in this platform. When in 2009, the MTTI of the largest supercomputers was estimated close to 4 days, it sharply decrease below a single day (19h04 min) in 2011, and projected to continue its descent in the following years (less than 4h by 2015, less than 2h by 2018). While technical breakthrough will hopefully allow the MTTI to remain in a tolerable area, long running applications need an execution environment more flexible, an environment allowing them to survive for longer period of time either algorithmically or by taking advantage of specialized capabilities of the programming model. Unfortunately, current programming paradigms do not account for such a hardware instability; the failure of a single component (be it memory or computing unit, hard

drive or network card) has a drastic and lasting effect on the computation. Even without accounting for the implicit energy costs, in front of the evolving expectations for the next generation computing platforms MTTI, such approaches cannot reasonably lead to sustainable software solutions.

Overview.

This course will highlight the existing solutions, and present parallel algorithms designed to provide correct solutions despite the presence of failures. We will show how the programming environment can be modified to increase the system reliability and sustainability. The course will start with an introduction to High Performance Programming, its challenges and typical algorithms.

Then we present theoretical as well as practical studies of the many fault-tolerant approaches that have been proposed over the years.

Prerequisite.

The course assumes a general knowledge of algorithms and operating system, as well as a basic understanding of machine architecture and network systems.

Update: bring your laptop! Some exercises on machine will be proposed along the course. Attendants are expected to bring a laptop with a possibility to establish a connection to a distant machine (typically, ssh): please write to the local contact (Yves Robert) if this is not possible for you — we should be able to lend a few laptops to participants.

Local contact: Yves Robert.

Registration

Registration is free, but there is a limit on the number of participants and it does include neither housing nor meals (though for lunch the attendees will be granted access to the student cafeteria). Registration should be made before Monday, December 3, by clicking on this link and filling in and sending the e-mail form. You shall receive a confirmation as soon as possible.

Alternatively, you can copy/paste and fill the following form and send it by e-mail to research.school.1@gmail.com, with subject “Registration form — research school 1”

 

First Name:

Last Name:

Institution:

Position (MSc student, PhD student, researcher, etc.):

E-mail address:

wishes to attend the research school ‘Fault tolerance for high performance computing’, taking place at ENS Lyon, from Dec. 10 to Dec. 14