Optimized static real-time scheduling of communications on a broadcast bus

Description

We consider the problem of minimizing bus usage for static real-time scheduling of hierarchical dataflow specifications involving conditional execution. Statically scheduling conditional communications over an asynchronous broadcast bus involves the sending of the activation conditions themselves, which allow all processors to know which messages they must throw away or use. As the communication of an activation condition may be hierarchically conditioned itself, this results in a complex calculus of activation conditions (also called logical clocks in some settings). We provide a technique that uses this calculus to ensure that no piece of information is sent twice over the bus. Our technique can be used to reduce a given static schedule to a normal form with no redundant communication. It can also be incorporated into existing scheduling algorithms to ensure by construction the absence of redundancy. The technique can also be used to reduce communication when some form of time synchronization is used (e.g. on time-triggered buses), but some optimality properties may be lost.

Additional details