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 throughbounded 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

- GSM encoder/decoder
- GSM encoder/decoder with additional buffers
- node
`f`(Section 3) - node
`g`(Section 5.3) - node
`tight_cycle`

(Section 6) - extended version Section 5.4
- extended version Section 6

More examples are available in the Lucy-n distribution.

This document was translated from L^{A}T_{E}X byH^{E}V^{E}A.