Scheduling and Buffer Sizing of n-Synchronous Systems -- MPC12



Scheduling and Buffer Sizing of n-Synchronous Systems
Typing of Ultimately Periodic Clocks in Lucy-n

MPC 2012


Louis Mandel and Florence Plateau
LRI, Univ. Paris-Sud 11
LIENS, École Normale Supérieure
INRIA, Paris-Rocquencourt

Abstract:
Lucy-n is a language for programming networks of processes communicating through bounded buffers. A dedicated type system, termed a clock calculus, automatically computes static schedules of the processes and the sizes of the buffers between them.

In this article, we present a new algorithm which solves the subtyping constraints generated by the clock calculus. The advantage of this algorithm is that it finds schedules for tightly coupled systems. Moreover, it does not overestimate the buffer sizes needed and it provides a way to favor either system throughput or buffer size minimization.


Article: .pdf
Extended version (with proofs): .pdf
Commented implementation of the resolution algorithm in OCaml: source code and documentation
Lucy-n: clock typing prototype (bytecode OCaml version 3.12.1 - needs Glpk)
Lucy-n web page: www
Examples: .tgz

More examples are available in the Lucy-n distribution.


This document was translated from LATEX by HEVEA.