Automatic Rate Desynchronization of Embedded Reactive Programs

作     者：Girault, Alain Nicollin, Xavier Pouzet, Marc 

作者机构：Inria Rhône-Alpes Pop Art project Saint-Ismier cedex 655 avenue de l'Europe 38334 France INPGrenoble Verimag Giéres Centre Équation 2 avenue de Vignate 38610 France Université Paris-Sud LRI Orsay cedex 91405 France 

出 版 物：《ACM Transactions on Embedded Computing Systems》 (ACM Trans. Embedded Comput. Syst.)

年 卷 期：2006年第5卷第3期

页      面：687-717页

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Algorithms automatic distribution Design desynchronization Embedded programs long-duration tasks parallelization algorithm reactive systems 

摘      要：Many embedded reactive programs perform computations at different rates, while still requiring the overall application to satisfy very tight temporal constraints. We propose a method to automatically distribute programs such that the obtained parts can be run at different rates, which we call rate desynchronization. We consider general programs whose control structure is a finite 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. © 2006, ACM. All rights reserved.