To: seminaire@pauillac.inria.fr
From: Francois.Pottier@inria.fr
Subject: SEM - INRIA : Cristal - 24/02/06 - Paris - FR

           Vous pouvez vous abonner à nos annonces de séminaires
             http://pauillac.inria.fr/seminaires/subscribe.html

                             S E M I N A I R E
       ___      .                       
      /    ___   __  /_  _   /             /| /|  _   __ __ _       _ 
     /    /   / /_  /   __| /    -----    / |/ | / \ /_ /  / \ | / __|
    |___ /   / __/ |_  |_/ |_            /     | |_/__/ |_ |_/ |/ |_/
                                                
                          I N R I A - Rocquencourt
                         Amphi Turing du bâtiment 1

                         Vendredi 24 fevrier, 10h30

                        ---------------------------
                        Albert Cohen et Marc Pouzet
                        ---------------------------

                                 INRIA, LRI

           ======================================================
           N-Synchronous Kahn Networks: Relaxing a Clock Calculus
             for Periodic Real-Time Systems through Sub-Typing
           ======================================================

The design of high-performance stream-processing systems is a fast
growing domain, driven by markets such like high-end TV, gaming, 3D
animation and medical imaging. It is also a surprisingly demanding
task, with respect to the algorithmic and conceptual simplicity of
streaming applications. It needs the close cooperation between
numerical analysts, parallel programming experts, real-time control
experts and computer architects, and incurs a very high level of
quality insurance and optimization.

In search for improved productivity, we propose a programming model
and language dedicated to high-performance stream processing. This
language builds on the synchronous programming model and on domain
knowledge, the periodic evolution of streams, to allow
correct-by-construction properties to be proven by the compiler. These
properties include resource requirements and delays between input and
output streams. Automating this task avoids tedious and error-prone
engineering, due to the combinatorics of the composition of filters
with multiple data rates and formats. Correctness of the
implementation is also difficult to assess with traditional
(asynchronous, simulation-based) approaches. This language is thus
provided with a relaxed notion of synchronous composition, called
n-synchrony: two processes are n-synchronous if they can communicate
in the ordinary (0-)synchronous model with a FIFO buffer of size $n$.

Technically, we extend a core synchronous data-flow language with a
notion of periodic clocks, and design a relaxed clock calculus (a type
system for clocks) to allow non strictly synchronous processes to be
composed or correlated. This relaxation is associated with two
sub-typing rules in the clock calculus. Delay, buffer insertion and
control code for these buffers are automatically inferred from the
clock types through a systematic transformation into a standard
synchronous program. We formally define the semantics of the language
and prove the soundness and completeness of its clock calculus and
synchronization transformation. Finally, the language is compared with
existing formalisms.