Synchronization of periodic clocks

ABSTRACT

We propose a programming model dedicated to real-time video-streaming applications for embedded media devices, including high-definition TVs. This model is built on the synchronous programming model extended with domain-specific knowledge --- periodic evolution of streams --- to allow correct-by-construction properties of the application to be proven by the compiler. These properties include buffer requirements and delays between input and output streams.Such properties are tedious to analyze by hand, due to the combinatorics of video filters, multiple data rates and formats. We show how to extend a core synchronous data-flow language with a notion of periodic clocks, and to design a relaxed clock calculus (a type system for clocks) to allow non strictly synchronous processes to be composed. This relaxation is associated with a subtyping rule in the clock calculus. Delay, buffer insertion and control code for these buffers are automatically inferred from the clock types through a systematic program transformation.

REFERENCES

• 1: A. Benveniste, P. Caspi, S. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The Synchronous Languages Twelve Years Later. Proceedings of the IEEE, 91(1):64--83, 2003.
• 2: J.-Y. Brunel , W. M. Kruijtzer , H. J. H. N. Kenter , F. Pétrot , L. Pasquier , E. A. de Kock , W. J. M. Smits, COSY communication IP's, Proceedings of the 37th conference on Design automation, p.406-409, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337515]
• 3: J. Buck, S. Ha, E. A. Lee, and D. G. Messerschmitt. Ptolemy: A framework for simulating and prototyping heterogenous systems. Int. Journal in Computer Simulation, 4(2):155--182, 1994.
• 4: Zbigniew Chamski , Marc Duranton , Albert Cohen , Christine Eisenbeis , Paul Feautrier , Daniela Genius, Application-domain-driven system design for pervasive video processing, Ambient intelligence: impact on embedded system design, Kluwer Academic Publishers, Norwell, MA, 2003
• 5: A. Cohen, M. Duranton, C. Eisenbeis, C. Pagetti, and M. Pouzet. Synchronizing periodic clocks in kahn networks. Technical Report 5603, INRIA, June 2005. http://www.inria.fr/rrrt/rr-5603.html.
• 6: Jean-Louis Colaço , Alain Girault , Grégoire Hamon , Marc Pouzet, Towards a higher-order synchronous data-flow language, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017792]
• 7: J.-L. Colaço and M. Pouzet. Clocks as first class abstract types. In Rajeev Alur and Insup Lee, editors, EMSOFT'03, volume 2855 of Lecture Notes in Computer Science, pages 134--155. Springer, 2003.
• 8: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 9: K. Goossens, G. Prakash, J. Rover, and A. P. Niranjan. Interconnect and memory organization in SOCs for advanced set-top boxes and TV - evolution, analysis, and trends. In Jari Nurmi, Hannu Tenhunen, Jouni Isoaho, and Axel Jantsch, editors, Interconnect-Centric Design for Advanced SoC and NoC, chapter 15, pages 399--423. Kluwer, April 2004.
• 10: G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information processing, pages 471--475, Stockholm, Sweden, Aug 1974. North Holland, Amsterdam.
• 11: A.J.M. Moonen, M. Bekooij, and J. van Meerbergen. Timing analysis model for network based multiprocessor systems. In proceedings of ProRISC, 15th annual Workshop of Circuits, System and Signal Processing, pages pages 91 -- 99, Veldhoven, The Netherlands, November 2004. ISBN: 90-73461-43-X.
• 12: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 13: J. E. Vuillemin, On Circuits and Numbers, IEEE Transactions on Computers, v.43 n.8, p.868-879, August 1994 [doi>10.1109/12.295849]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages

General Terms:
Languages, Performance, Reliability, Theory

Keywords:
correctness by construction, high-performance video streaming, synchronous language, type inference and sub-typing