Pau Arumi's thesis

Thesis document

Title : Real-time Multimedia Computing on Off-the-Shelf Operating Systems: From Timeliness Dataflow Models to Pattern Languages

Find here the thesis document in a single pdf: pauarumi_thesis.pdf

Thesis defense

30th June, 12:30h. It will take place at the UPF (campus Poblenou), in the Auditorium of the Roc Boronat building
Co-directors:

Xavier Amatriain
Vicente Lopez

Tribunal members:

Jyri Huopaniemi (Nokia Research Center)
George Tzanetakis (U. of Victoria, CA)
Nacho Navarro (UPC)
Josep Blat (UPF)
Rafael Ramirez (UPF)

Abstract

Software-based multimedia systems that deal with real-time audio, video and graphics processing are pervasive today, not only in desktop workstations but also in ultra-light devices such as smart-phones. The fact that most of the processing is done in software, using the high-level hardware abstractions and services offered by the underlying operating systems and library stacks, enables for quick application development. Added to this flexibility and immediacy (compared to hardware oriented platforms), such platforms also offer soft real-time capabilities with appropriate latency bounds. Nevertheless, experts in the multimedia domain face a serious challenge: the features and complexity of their applications are growing rapidly; meanwhile, real-time requirements (such as low latency) and reliability standards increase.

This thesis focus on providing multimedia domain experts with workbench of tools they can use to model and prototype multimedia processing systems. Such tools contain platforms and constructs that reflect the requirements of the domain and application, and not accidental properties of the implementation (such as thread synchronization and buffers management). In this context, we address two distinct but related problems: the lack of models of computation that can deal with continuous multimedia streams processing in real-time, and the lack of appropriate abstractions and systematic development methods that support such models.

Many actor-oriented models of computation exist and they offer better abstractions than prevailing software engineering techniques (such as object-orientation) for building real-time multimedia systems. The family of Process Networks and Dataflow models ---based on networks of connected processing actors--- are the most suited for continuous stream processing. Such models allow to express designs close to the problem domain (instead of focusing in implementation details such as threads synchronization), and enable better modularization and hierarchical composition. This is possible because the model does not over-specify how the actors must run, but only imposes data dependencies in a declarative language fashion.

These models deal with multi-rate processing and hence complex periodic actor's execution schedulings. The problem is that the models do not incorporate the concept of time in a useful way and, hence, the periodic schedules do not guarantee real-time and low latency requirements. This dissertation overcomes this shortcoming by formally describing a new model that we named Time-Triggered Synchronous Dataflow (TTSDF), whose periodic schedules can be interleaved by several time-triggered ``activations'' so that inputs and outputs of the processing graph are regularly serviced. The TTSDF model has the same expressiveness (or equivalent computability) than the Synchronous Dataflow (SDF) model, with the advantage that it guarantees minimum latency and absence of gaps and jitter in the output. Additionally, it enables run-time load balancing between callback activations and parallelization.

Actor-oriented models are not off-the-shelf solutions and do not suffice for building multimedia systems in a systematic and engineering approach. We address this problem by proposing a catalog of domain-specific design patterns organized in a pattern language. This pattern language provides design reuse paying special attention to the context in which a design solution is applicable, the competing forces it needs to balance and the implications of its application.

The proposed patterns focus on how to: organize different kinds of actors connections, transfer tokens between actors, enable human interaction with the dataflow engine, and finally, rapid prototype user interfaces on top of the dataflow engine, creating complete and extensible applications.

As a case study, we present an object-oriented framework (CLAM), and specific applications built upon it, that makes extensive use of the contributed TTSDF model and patterns.

Document Changelog

DONE May 09

DONE new section in chapter 2 about "callback vs blockin i/o" styles and why callback is important. refered from TTSDF chapter. (GZ suggestion)
DONE a major rewrite of the conclusion and contributions chapter, including VL and XA suggestions.
DONE new section in case studies with Martin Gasset's StreamCatcher implementing TTSDF and Port Monitor. Also in the conclusions
DONE mentioned more actor-oriented systems and languages: MS filter graph, java media framework, erlang, lucid, csound... (GZ and XA sugg)
DONE summary in catalan
DONE Finish many grammatic corrections (XA sugg)
DONE Chapter 4 TTSDF: many improvements in the text (XA sugg)
DONE Chapter 4 TTSDF: the scheduling example now includes a discussion (XA sugg)
DONE Chapter 3.4 General Dataflow Patterns, intro rewritten (XA sugg)
DONE 3.1.2 SotA: Related Timeliness MoCs: general rewrite (XA sugg)
DONE 2.4 Design Patterns: long cites rephrased (XA sugg)
DONE 2.4 Design Patterns: Patterns, Frameworks and Architectures: rewritten (XA sugg)
DONE 2 Background: removed long cites. Rephrased instead (XA sugg)
DONE 2.2 Actor-oriented design: reordered sections and done small rewrites (XA sugg)
DONE Remove "Summary of the chapter" in TTSDF chapter (XA suggestion)
DONE Many grammar, biblio corrections and various suggestions from GZ
Smaller things

DONE Static Dataflow vs Synchronous Dataflow discussion (GZ comment)
DONE Future work: refactor patterns
DONE grammar corrections and repeated bibliography corrections (GZ suggestion)
DONE renamed pattern: Cascading Event Ports -> Propagating Event Ports (XA sugg)
DONE more examples of Port Monitor (in streamcatcher)
DONE added more acknowledgments

DONE March-April 09

pau_thesis_20080813.pdf August 08 version (the second draft of the thesis), the first version provided to the tribunal in March 09.

DONE Incorporate LAC09 changes.
DONE Update publications status: mmcn status and lac09
DONE Title rename: The Solution -> The Proposed Solution (VL suggestion)
DONE Title rename: Related Work -> State of the Art (VL suggestion)
DONE Title rename: final chapter section "Conclusions" -> Summary (VL suggestion)
DONE Remove "WISH DO marks"
DONE Acknowledgments: Martin Gasser
DONE Intro corrections (XA suggestions)
DONE Refactoring: renamed tex source files and removed dependencies from plop article
DONE Updated publications list

MAYBE TODO (low prio)

Background too long. And needs more relation between ideas in the summary low
Discussion about composites and clam (pattern), ref Dannenberg low
Background: Explain Time-Triggered Model
Patterns: changed names to better fit with dataflow MoCs
Pattern: Visual Prototype: give proper pattern format. Now only have sections Context, Problem, Forces and Solution.
Check if there are wrong links to Domain-specific Languages.
Maybe use Journal for patterns intro
Improve linking between CLAM section and patterns.
CLAM: link visual builder with visual prototyper pattern
CLAM: finish/polish section (Beware of the NE figure. It links to one in the intro!)
CLAM: use journal abstract for this section.
Format: give all figures a short caption for the index.
Patterns: relate Streams and Events with Context-aware MoC
Patterns: cite PLoP article.
Patterns renaming: * - High

Pattern: Change name to synchronous ports or synchronous and event/asynchronous ports
stream and event ports -> events synchronization.
multi-rate stream ports. "stream"??
Driver Ports -> Firing Rules??

idea for multiple-window: we don't want to waste space to avoid cache pressure.
Intro: comment about the causes of the inexistence of the solution yet? Low
Transversal cleaning:

in-port out-port (input port etc) -- out port wins

Related Work: section Multi-rate Dataflow Frameworks (Marsyas, Ptolomey, GStreamer) ** - Very Low
Polish general conclusions, I'm not happy with it.
3D-audio: Add multiple screenshots for the patterns examples. - Med
Related work: add reference to Time-Triggered Patterns (hardware)
Conclusions outline and first draft. No, wait having the separate conclusions ** - Low
Patterns format: highlight the solution Low
Fix Front Page easy
Fill gaps and polish ****
TTSDF: be explicit with obvious things: unconnected graphs

DONE

13 - 31 August

Rest. Vacances. Forget the thesis.

week -2 - 11-13 August

DONE Background - Related Work

DONEMMOS explain Petrinets - med
AWAY Decide what to do with Frameworks
DONE Fix Design Patterns Intro
DONE Add Design Patterns Languages
DONE Conclusions

DONE Data-flow for Dataflow in the patterns * - Very High
DONE TTSDF Model
DONE Dataflow Patterns
DONE Restructure Chapter "Case Studies" Start with "The CLAM Framework" and then "Example Applications" or "Design Examples". * - High
NO A new design examples: spectral processing. Very briefly, basically showing scheduling configurations and processing screenshots * - Low
DONE Conclusions per chapter - explain how we have addressed the problems, and what technologies have been introduced... ** - High

DONE Patterns Conclusions
DONE TTSDF Conclusions
DONE Background Conclusions
DONE Realated Work Conclusions
DONE Case Studies Conclusions

DONE Related work: rewrite the metamodel existing material, using IEEE article * - High
DEFERRED Background: Domain specific language instead of Meta-model * - Med
OUT' Decide what to do with domain specific language link at the intro.
DONE Finish background *** - High
DONE Finish related work *** - High

DONE Format as new pattern: Visual Prototyper -- **
DONEImprove Organizing the Catalog **
DONEWrite conclusions ***
DONEImprove Patterns **
DONE TTSDF model be explicit about inputs vs sources * - Med
DONE Future work: Further, techniques for balancing the run-time load, not only between sequential callbacks, but multiple processors, should be developed.
DONE Write Abstract *** - High
DONE' Curriculum Vitae section? Only publications (and software) ? Appendix?
DONE Write/update acknowledgments.
DONE Improve floats placement. Tips:

DONE With the command \FloatBarrier (from package \usepackage{placeins}) all moveable objects will be displayed before this command.
DONE The package \usepackage{float} introduces a new positioning flag H additionaly to the current one (h, t, p ...). This flag will display the object at the exactly same place as it is in the tex-script.

week -1 - 4-8 August

DONE Format: Captions a bit narrower
DONE Explain Parallelization algorithm in the model ** - Med
NO Background: generic Language (to be reused in DSL and Pattern Languages) * - Low
DONE Review thesis LaTeX format
DEFERRED Python-Qt dataflow scheduling animations *** - Very Low - for the defence.
DONE TTSDF model

DONE examples: add more
explain the examples * - High
DONE better explanations between the demos (the story) * - High
DONE (a lot) add figures * - High
DONE expand demos * - Med
DONE cost study easy * - High

DONE Conclusions: add Ralph Johnson and Didier (ericson) acknowledgment. Xavi says only at ack page.
DONE Write Acknowledgments
DONE Move shared credit at acknowledgments * - High

week 0 - 28-31 July (4 days)

DONE Design examples

DONE Polish explanation of CLAM networks
DONE Merge raytracing with network diagram
DONE Polish "difficulties"
DONE Explain Graph scheduling Results and integrate generated diagrams.

Background - Related Work

DONE Give structure to MM OS
DONE MMOS requirements
DONE MOS Concepts
DONE MMOS Real-time architecture
DONE MMOS Lee quotes
DONE MMOS OS scheduling algorithms
DONE MMOS ipods, laptops images
DONE MMOS Polishing
DONE Actor-Oriented Design: restructure and clean
DONE AO terminology normalization
DONE Add intro
DONE (applied) Lee mail, control flow and dataflow is very hard to do maintaining determinacy.

Transversal cleaning:

DONE Normalize words: * - High
DONE Data-flow
DONE Format: More separation between sections, and a line.
DONE (Left as it was) Little bit less footer margin?
DONE (Waiting answer) Check if UPF have a thesis guide

DONE OS Multimedia: only the more important stuff ** - VeryHigh
NO The interrupt model (os multimedia) - Lennart

DONE Lock-free programming / Wait free programming

DONE Write multimedia operating system section *** - Med

week 1 - 21-27 July

DONE Patterns name: A Pattern Language for Dataflow-Based Multimedia Processing Systems.
DONE Intro/Contributions list: add chapter link to each item
Write design examples: acoustic simulation ***

DONE Intro: a system that uses the model and patterns for a specific goal
DONE Context and Goal: RACINE, R-T prehearing and quality 3D rendering.
DONE Lowlatench convolution
DONE CLAM networks
DONE Difficulties (IRs of moving sources)
DONE Graph scheduling. Nice!

Yup, lost track of some done tasks...

week 2 - 14-20 July

Full-time work

DONE The Solution:

Add figure of the model solution (chronogram or seq. diagram) - low

DONE Intro: Polish Contributions - High

DONE Shared credit

DONE Fix broken references thesis-wide
DONE Recategorize Visual Prototyping patterns
Write design examples: acoustic simulation ***

DONE collect first screenshots
DONE More screenshots: flamencos chroma, raytracing flamencos, networks, decoding options, lowlatency convolution

DONE Conclusions: Put TODOs - High
DONE Review all sections and adding important TODOs - High
DONE Milestone: Send first draft - High''

week 3 - 7-13 July

Part-time work: >18h

DONE Polish the Solution - High

DONE Polish Patterns
DONE CLAM and design examples
DONE Relate with other technologies (OO, metamodel)

DONE Intro: Polish The Method * - High

DONE General introduction (format system eng. and experience soft. eng)
DONE The formal method
DONE The patterns method
DONE Model Contributions
DONE Patterns Contribution
DONE CLAM and examples

week 4 - 30 June - 5 July

Jornades Programari Lliure
Article MMCM09
Acoustics 09 Paris talk
Improvements to the TTSDF model (driven by the MMCM article)

week 5 - June 23-29

Anti-tesis: Uaa!!

dilluns 23, tot el dia -- matí reunió imt-net i vicenç defensa tesis -- tarda-nit st. joan a garriguella. dimarts, matí perdut, bastant inevitable
dimecres, vespre-nit assaig guillamino
divendres, tarda-nit bolo poparb. dissabte matí, bastant inevitable

week 6 - June 16-22

Anti-tesis: futbol dimarts vespre, assaig dimecres vespre-nit

DONE Intro: Clean out the solution, moving stuff to Background. - High
DONE Intro: DRAFT Rewrite the Problem * - High
DONE Intro: Polish the Problem - High

DONE Intro: last revision on the Problem
DONE Add figure: multi-rate dataflow
DONE Caption figure multi-rate
DONE Explain figure multi-rate

DONE DRAFT The solution
DONE relate domain-specific meta-models and languages.
DONE Move patterns details out of the solution
DONE New version of domain figure with the solution

DONE Caption

DONE Fix refs in the intro
DONE Relate general goal of the intro with the "big picture" diagram
DONE Intro: Thesis Organization
DONE Intro: DRAFT The Method * - High
DONE DRAFT the Solution

DONE Give general context
DONE Patterns

DONE Relate Contributions with modified domain figure
DONE Contributions: Caption modified domain figure
DONE Intro: Finish draft for Contributions - High

week 7 - June 9-15

Anti-tesis: assaig dimecres vespre-nit, concert dijous vespre-nit dissabte mig perdut - bolo Lleida

Milestone: Draft for Vicente

DONE Draft Light intro for chapter Time Triggered Dataflow * - High
DONE Finished Light intro for chapter Time Triggered Dataflow * - High
DONE Intro: Sketched Rewrite intro (of the intro) ** - High
DONE Intro: Finished conceptual diagram ** - High
DONE Intro: Draft conceptual diagram ** - High
DONE Intro: add conceptual model figures * - High
DONE Intro: Finished Rewrite intro (of the intro) ** - High

DONE The general problem
DONE Add references to sections
DONE Briefly explain the various techniques (domain-specific languages, etc.) and relate with figure
DONE Briefly explain the concrete problem and solution
DONE Relate both figures
DONEFix references
DONE Polish diagram
DONE' Diagram caption

DONE (new) Intro: Actor oriented diagram - Med
DONE Move Software-Based Multi-rate dataflows to the problem
DONE Intro: Draft Write The Method - High
DONE Intro: Draft Rewrite the Problem - High
DONE Intro: Draft of the intro

week 8 - June 2-8

Milestone: Vicente draft Friday June 6th (aka, first showable version of the thesis) The goal is have all sections in place with introductions with annotated gaps.

DONE Light intro for chapter Related Work * - High
DONE Model related work split in 3 subsections.
DONE (new) integrated the Visual Prototyping architecture to the patterns (needs refinement)
DONE (but super "draft") Write draft multimedia operating system section * - Low
DONE Make sure the intro doesn't start too technical (i.e. multirate example) - High
DONE (new) refactoring: split background in one file per section
DONE Write todos at the start of each section * - High
(new) find and integrate lost section about OO - High
DONE Polished version: Light start with tools for domain expertes, frameworks to support domain specific language... * - High
DONE Intro: Move details to background * - High
DONE (expanded in different tasks per chapter) Light intro for chapter Background * - High
DONE First version: Light start with tools for domain expertes, frameworks to support domain specific language... * - High
DONE Background: reorganize dataflow related sections - High
DONE Formatting: less intrusive link borders - Low
DONE Decide change or not to change: Callback Triggered -> Time Triggered: TTSDF - High
DONE Read domain specific language article and incorporate concepts * - Med
DONE Abstract: make explicit that it is draft. - High

week 9 - May 26-June 1

Dissabte i diumenge fora (casament)

DONE Schematic version of intro light start
DONE Move detailed stuff out of the intro
DONE Put all the missing sections in place
DONE Recycle stuff into appropriate section

DONE write todos at the start of sections that need rewrite

DONE Move "the problem with SDF" to The Model