Automatic rate desynchronization of embedded reactive programs

Many embedded reactive programs perform computations at dierent rates, while still requiring the overall application to satisfy very tight temporal constraints. We propose a method to auto-matically distribute programs such that the obtained parts can be run at dierent rates, which we call rate desynchronization. We consider general programs whose control structure is a nite state automaton and with a DAG of actions in each state. The motivation is to take into account long duration tasks inside the programs: these are tasks whose execution time is long compared to the other computations in the application, and whose maximal execution rate is known and bounded. Merely scheduling such a long duration task at a slow rate would not work since the whole program would be slowed down if compiled into sequential code. It would thus be impossible to meet the temporal constraints, unless such long duration tasks could be desynchronized from the remaining computations. This is precisely what our method achieves: it distributes the initial program into several parts, so that the parts performing the slow computations can be run at an appropriate rate, therefore not impairing the global reaction time of the program. We present in detail our method, all the involved algorithms, and a small running example. We also compare our method with the related work. Categories and Subject Descriptors: C.3 [Computer Systems Organization]: Special-purpose and application-based systems|Real-time and embedded systems; D.3.2 [Software]: Program