The Synchronous Blog

A blog about reactive programming languages.

Posts Tagged ‘parallelism

“Céu: Embedded, Safe, and Reactive Programming”

with one comment

We have published a technical report entitled “Céu: Embedded, Safe, and Reactive Programming”.

Enjoy the reading!

Abstract:

Céu is a programming language that unifies the features found in dataflow and imperative synchronous reactive languages, offering a high-level and safe alternative to event-driven and multithreaded systems for embedded systems.

Céu supports concurrent lines of execution that run in time steps and are allowed to share variables. However, the synchronous and static nature of Céu enables a compile time analysis that can enforce deterministic and memory-safe programs.

Céu also introduces first-class support for “wall-clock” time (i.e. time from the real world), and offers seamless integration with C and simulation of programs in the language itself.

The Céu compiler generates single-threaded code comparable to handcrafted C programs in terms of size and portability.

Table of Contents:

  1. Introduction
  2. The Language Céu
    1. Parallel compositions
    2. Internal events & Dataflow support
    3. Wall-clock time
    4. Integration with C
    5. Bounded execution
    6. Determinism
    7. Asynchronous execution
    8. Simulation in Céu
    9. GALS execution
  3. Demo applications
    1. WSN ring
    2. Arduino ship game
    3. SDL game simulation
  4. Implementation of Céu
    1. Temporal analysis
    2. Memory layout
    3. Gate allocation
    4. Code generation
    5. Reactive execution
    6. Evaluation
  5. Related work
    1. Synchronous model
    2. Asynchronous model
  6. Conclusion
Advertisements

Paper accepted.

leave a comment »

Good news received last week:

Dear Mr. Francisco Sant’Anna,

I am pleased to confirm that your paper “LuaGravity, a Reactive Language
Based on Implicit Invocation” has been accepted for presentation and
publication at SBLP 2009.

All papers went through a rigorous reviewing process by the program
committee. Out of 30 research papers and 3 tutorials submitted, 12
papers and 1 tutorial were accepted.

Please make sure that in the preparation of the final paper you
carefully address the reviewers’ comments. Additionally, at least one
author is required to register in the conference for your paper to
appear in the proceedings.

Congratulations again on having your paper accepted. We look forward to
seeing you in Gramado!

Reviewer’s comments already addressed and final version submitted! One reviewer in particular pointed several constructive observations, which we took very seriously in the final version.

Follows the abstract for the paper:

The reactive programming paradigm covers a wide range of applications, such as
games and multimedia systems.
Mainstream languages do not offer proper support for reactive programming,
lacking language-level primitives that focus on synchronism and interactions
within application parts.
We propose an imperative reactive language, called
LuaGravity, based on
unconventional implicit invocation mechanisms.
LuaGravity allows dataflow programming, sequential imperative execution, and
deterministic use of shared-memory.
With this work, we intend to unite the essential features of reactive languages
while keeping a convenient imperative style of programming.

SBLP [1] is the main Brazilian congress on programming languages. This year it will be held in Gramado on August 18-21.

[1] http://sblp2009.ucpel.tche.br/

The problem with Events

with 2 comments

Following the discussion from here and here

Some problems arise from event-driven programming adoption:

  1. Inversion of control:
  2. Commanded by the environment, event-driven programs must quickly answer requests to keep the system up and running.
    For instance, if a program wants to perform a time consuming operation (e.g. I/O), it must demand it to be done in the background and register a callback to continue the previous operations. If a logical sequence has three of these time consuming operations, the job must be separated into that many callbacks.
    This characteristic leads to difficulty in visually understanding the applications’ control flow and is known as callback soup.

    Another bad consequence of this code separation is that the state kept in callbacks are independent of each other as all local variables residing in their stacks are lost on returning. To keep state, their stacks must be manually reconstructed in the heap and passed as extra parameter from callback to callback.
    This phenomenon is known as stack ripping.

    In this sense, threads offer a more natural way of programming as the programmer may use the conventional sequential flow, keeping all state in thread’s single stack.

  3. Multi-core processors:
  4. Another issue with the event-driven approach is the challenge to take advantage of multi-core architectures.

    In a common event-driven dispatcher, handlers must be run in sequence as they all share global state. When parallelized, two handlers would access the shared memory at the same time, leading to data corruption.

    This is not the case with threads which are already artificially run in parallel even in single-core, thus having all shared memory protected manually with programmed instructions.
    Well written multi-threaded programs take advantage of multi-core for free.

  5. Listener life cycle:
  6. Once a handler is registered for events it remains listening to them until a call to unregister is made.
    In some sense, this is similar to manual memory management. The system is not capable of deciding by itself when a listener must be unregistered.
    There is no such concept as “listen while some rule is valid”.


The first (and worst) problem is solved with cooperative multi-tasking.
A paper [1] explores this issue and shows this interesting graphic where the sweet spot is viewed as an improvement over both event-driven and multi-threading choices.

The second problem is a new one as multi-core architectures are still debuting.
I do have some ideas on this issue and believe that smarter people also do.
Giving different “colors” to unrelated callbacks is an option already in use [2].

The third problem arose on my own research and I’m searching for works to see if someone had already pointed that out. I’m working on a “listening scope” concept and wondered if something similar exists.

To conclude, I think that event-driven programming had always been seen more as technique than a true paradigm. Support in languages is very limited and always offered as a library layer that creates a small synchronous world for specific tasks.

[1] “Cooperative Task Management without Manual Stack Management”:
http://www.stanford.edu/class/cs240/readings/usenix2002-fibers.pdf
[2] “Multiprocessor Support for Event-Driven Programs”: people.csail.mit.edu/nickolai/papers/usenix2003-slides.pdf

Written by francisco

August 28, 2008 at 3:13 pm