Optimal Composition of Real-Time Systems
Optimal Composition of Real-Time Systems
复制标题
实时系统的优化组成
DOI：
10.1016/0004-3702(94)00074-3
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Stuart J. Russell
中科院分区：
文献类型：
--
作者：
S. Zilberstein;Stuart J. Russell
实时系统是为行动的效用强烈依赖于时间的环境而设计的。Dean、Horvitz等人最近的研究表明，随时算法是实时系统设计的一个有用工具，因为它们允许用计算时间换取决策质量。然而，为了构建复杂的系统，我们需要能够将较小的、随时可重用的模块组合成较大的系统。本文讨论了与组合相关的两个基本问题：如何保证组合系统的可中断性；以及如何在组件之间优化分配计算时间。第一个问题是通过一个简单而通用的结构来解决的，它只会产生一个小的、持续的惩罚。第二个问题通过离线编译过程来解决。我们证明了一般编译问题是np完全的。然而，高效的局部编译技术每次只处理一个程序结构，可以为大量程序产生全局最优分配。我们用两个简单的应用程序来说明这些结果。
Real-time systems are designed for environments in which the utility of actions is strongly time-dependent. Recent work by Dean, Horvitz and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be traded for decision quality. In order to construct complex systems, however, we need to be a ble to compose larger systems from smaller, reusable anytime modules. This paper addresses two basic problems associated with composition: how to ensure the interruptibility of the composed system; and how to allocate computation time optimally among the components. The first problem is solved by a simple and general construction that incurs only a small, constant penalty. The second is solved by an off-line compilation process. We show that the general compilation problem is NP-complete. However, efficient local compilation techniques, working on a single program structure at a time, yield glo bally optimal allocations for a large class of programs. We illustrate these results with two simple applications.