In the highly dynamic and information rich environment of military submarine operations, the Commanding Officer must make split second decisions that could ultimately result in the destruction or survival of Ownship or the accomplishment of its designated mission. Despite extensive training and expertise, the fog of war often shadows real world encounters. Pieces of the tactical puzzle may be scattered, broken, and/or even missing. It is the Commanding Officer's job to meld the fog into a clear tactical picture and intuitively decide upon the optimal course of action to obtain his mission goals and objectives. A mathematically derived optimal solution could be used as a decision making aid for the Commanding Officer to enhance Ownship's performance. A highly innovative hybrid Bayesian/differential game modeling approach is being developed to tackle this problem. The resulting theory and technology will facilitate tactical operations by addressing such practical problems as tradeoff evaluation for course of action and maintaining tactical advantage while avoiding counter detection.

In many time and mission-critical real-time applications there are humans in the loop. These humans are expected to make correct or largely correct decisions under conditions of massive information overload, uncertainty and stress, i.e., sources of exceptional complexity of these systems! We help these humans in their tasks through intelligent agent-based decision support systems (DSS). Utilizing suites of heuristics from many different fields of applied mathematics, optimization theory, scheduling and resource allocation and Artificial Intelligence, these DSS provide quality advice and rationale when it is needed, where it is needed and in the terminology and at the level of detail that is needed. The result is increased situational awareness, increased ability to assess risk and decision tradeoffs, reduced stress and, in general, very substantially reduced system complexity and as a result, considerably better operation of the time and mission-critical real-time application by the humans in the loop. Alexander D. Stoyen is an academic and technologist with significant experience in the fields of complex realtime systems and decision support systems. As a technologist, he is Founder and Chief Technical Officer of 21st Century Systems, Inc. (21CSI), a small-business researching, prototyping and developing revolutionary intelligent agent-based decision support systems for time and mission-critical systems with humans in the loop. In its five years of operation (since 1996), 21CSI has fielded DSS prototypes for a wide variety of military platforms. 21CSI has also developed and is now licensing and selling commercially a product AEDGEtm. AEDGEtm is a DSS construction toolkit, suitable for commercial and R&D organizations. With offices in Nebraska, Colorado, New York and Washington, DC, the company is now in the process of further expansion and creation of a separate commercial division, to support the AEDGEtm product and to develop, market and sell commercial AEDGEtmbased products. As an academic, Dr. Stoyen is on federal research development leave from the University of Nebraska at Omaha, where he has been Endowed Full Professor of Computer Science since January 1999 and Director, Center for Management of Information Technology AY’1999-2001. He is also appointed by courtesy to the Department of Computer Science Engineering (UN-Lincoln). At the University of Nebraska, Dr. Stoyen is advising Doctoral and Master’s students and is working on a major NSF-funded project in the area of Quality of Service networking and communications over Internet-2. Dr. Stoyen received his Ph.D. in Computer Science from the University of Toronto in 1987. Upon graduation, he joined IBM T.J. Watson Research Center as a research staff member. In 1990, he became an Assistant Professor of Computer Science at the New Jersey Institute of Technology, where he built the Dependable Real-Time Systems Laboratory. At the time of leaving NJIT in January 1999, Dr. Stoyen was an Associate Professor of Computer Science and of Electrical and Computer Engineering. Dr. Stoyen has held visiting, consulting and advisory appointments at universities, corporations and other organizations throughout North America, Europe and Asia. He has contributed significantly to a number of key technological concepts in real-time systems and has published more than 110 articles in journals, books and conference proceedings. Dr. Stoyen has served as an organizer of many professional events, chair of IEEE Technical Committees, and editor or guest editor of book series and archived peer-reviewed journals, including IEEE Computer, J. Real-Time Imaging and J. Real-Time Systems. Dr. Stoyen is a Senior Member of the IEEE and is an IEEE Computer Society Golden Core Member. Proceedings of the Seventh International Conference on Engineering of Complex Computer Systems (ICECCS’01) 1050-4729/01 $10.00 © 2001 IEEE

The authors present an architectural overview of an agent based decision support environment. We have selected the domain of AWACS Command and Control, in which human controllers need to make critical decisions under strict timing constraints in a dynamically changing environment. The decision support training environment is based on distributed simulation, tightly coupled with an intelligent agent infrastructure. The agents apply heuristics based algorithms to provide decision support to the human controllers.

Engineering of modern complex real time systems is driven by a host of design objectives, often differing not only in nature, importance, and form, but also in dimensional units and range, and themselves interacting in complex ways. These objectives influence design decisions throughout the entire system life cycle. We consider the problem of formulating the cost of a design decision driven by multiple objectives. We start by discussing issues and relationships among non functional objectives, their decomposition, and attribute cost functions used to quantify them. We then describe a hierarchical model along with an equational form for system cost function synthesis. Finally, examples are given to show how the model applies to actual multi objective problems in the design of complex real time systems.

Task graphs have been used for the specification and analysis of real time systems for some time. We are currently developing a mobile code management system that uses such a representation for specification, analysis, and execution time scheduling, dispatch, and resource allocation decisions. We describe our three level limited hierarchical task graph model. We discuss graph topology, the use of task graphs for both specification and description, and planned software engineering tools that will take advantage of our model. We concentrate on the use of task graphs to model iteration, branching structures, optional execution, and parallelism within a function execution.

Engineering of complex distributed real-time applications is one of the hardest tasks faced by the software profession today. All aspects of the process, from design to implementation, are made more difficult by the interaction of behavioral and platform constraints. Providing tools for this task is likewise not without major challenges. In this paper, we discuss a tool suite which supports the development of complex distributed real-time applications in a suitable high-level language (CRL). The suite's component tools include a compiler, a transformer-optimizer, an allocator-migrator, a schedulability analyzer, a debugger-monitor, a kernel, and a (simulated) network manager. The overall engineering approach supported by the suite is to provide as simple and natural an integrated development paradigm as possible. The suite tools address complexity due to distribution, scheduling, allocation and other sources in an integrated manner (largely) transparent to the developer. To reflect the needs of propagation of functional and nonfunctional requirements throughout the development process, a number of robust code transformation and communication mechanisms have been incorporated into the suite. To facilitate practical use of the suite, the developed programs compile-transform to a safe subset of C++ with appropriate libraries and runtime support. (In this safe subset (C++) the use of pointers is minimized. Aliases are not allowed.

Deterministic worst-case execution for satisfying hard-real-time constraints, and speculative execution with rollback for improving average-case throughput, appear to lie on opposite ends of a spectrum of performance requirements and strategies. Nonetheless, we show that there are situations in which speculative execution can improve the performance of a hard real-time system, either by enhancing average performance while not affecting the worst-case, or by actually decreasing the worst-case execution time. The paper proposes a set of compiler transformation rules to identify opportunities for speculative execution and transform the code. Moreover, we have conducted an extensive experiment using simulation of randomly generated real-time programs to evaluate applicability and profitability of speculative execution. The simulation results indicate that speculative execution improves average execution time and program timeliness. Finally, a prototype implementation is described in which these transformations have been evaluated for realistic applications.

Temporal load-balancing, spreading out the executions of tasks over time, is desirable in many applications in complex systems. A form of temporal load balancing is discussed, scheduling to maximize minimum inter-completion time (MICT-scheduling) and minimum global inter-completion time (MGICT-scheduling). It is shown that MICT- and MGICT-scheduling are, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MICT- and MGICT-scheduled.

Traffic reshaping and its impact on providing deterministic guarantees of timely data delivery in a packet-switched virtual-circuit fixed-packet network are investigated. Two types of traffic smoothing are considered: global reshaping (when traffic on all network connections is smoothed) and local reshaping (when the traffic specification is changed only for a single connection). The conditions when reshaping is beneficial are derived and the optimal values of traffic model parameters are obtained. In particular, it is shown that, when one tries to minimize end-to-end delay bounds for leaky bucket constrained traffic, the traffic either should be made constant bit rate (CBR) or should not be reshaped at all. It is proven that changing the leaky bucket specification to the dual leaky bucket specification is always able to yield better timeliness guarantees and utilisation of network resources. Finally, local reshaping for the dual leaky bucket model is studied.

Engineering of complex distributed real-time applications is one of the hardest tasks faced by the software profession today. All aspects of the process, from design to implementation, are made more difficult by the interaction of behavioral and platform constraints. Providing tools for this task is likewise not without major challenges. In this paper, we discuss a tool suite at New Jersey Institute of Technology's Real-Time Computing Lab which supports the development of complex distributed real-time applications in a suitable high-level language (CRL). The suite's component tools include a compiler, a transformer-optimizer, an allocator-migrator, schedulability analyzers, a debugger-monitor, a kernel, and a (simulated) network manager. The overall engineering approach supported by the suite is to provide as simple and natural an integrated development paradigm as possible. The suite tools address complexity due to distribution, scheduling, allocation and other sources in an integrated manner (largely) transparent to the developer. To reflect the needs of propagation of functional and non-functional requirements throughout the development process, a number of robust code transformation and communication mechanisms have been incorporated into the suite. To facilitate practical use of the suite, the developed programs compile-transform to a safe subset of C++ with appropriate libraries and runtime support.

A general model for traffic flows on packet-switched, virtual-circuit based, fixed-packet networks is introduced, and an exact schedulability test is obtained for systems of such flows. Rules are derived that make the evaluation of this schedulability test feasible and efficient under certain circumstances. The practical relevance of this approach is demonstrated by applying it to a number of standard traffic models.

The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints is considered. A new heuristic with the time complexity of O(n/sup 2/m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.

The overhead of the general checkpointing approach is infeasible for distributed real-time systems where timing is critical. We present a new compiler based approach which classifies data, and minimizes the data needed for checkpointing using static data flow analysis and language support. Our approach provides static guarantees of timeliness while checkpointing, and explores timely recovery for real-time systems. We outline our approach and discuss the necessary architecture and language support needed to make this feasible.

Compiler optimization techniques have been applied to facilitate development and performance timing of non-real-time systems. Unfortunately, regular compiler optimization can complicate the analysis and destroy timing properties of real-time systems. This paper discusses the difficulties of performing compiler optimization in distributed real-time systems. An algorithm is presented to apply machine-independent compiler optimization safely to distributed real-time systems. The algorithm uses resources' busy-idle profiles to investigate effects of optimizing one process on other processes. A restricted form of resource contention is assumed to simplify the analysis.

A complex application consists of a set of software modules, executed on a distributed system, guided by requirements imposed by the designer and the system. The REAL project at NJIT has been investigating the resource allocation problem for such a system. We give a classification of and syntax for constraints, provide a rule-based approach for constraint management, and discuss issues in generating implied constraints and consistency checking.

Achieving fault-tolerance using a primary-backup approach involves overhead of recovery such as activating the backup and propagating execution states, which may affect the timeliness properties of real-time systems. We propose a semi-passive architecture for fault-tolerance and show that speculative execution can enhance overall performance and hence shorten the recovery time in the presence of failure. The compiler is used to detect speculative execution, to insert check-points and to construct the updated messages. Simulation results are reported to show the contribution of speculative execution under the proposed architecture.

A real-time image encoder is designed by using codesign methodology is presented. The real-time image encoder composed of several functional modules. Each of these modules have their separate functions and can be built by software or hardware. Since there are so many combinations of hardware/software partitions can be found within these four modules. Thus, a good design methodology must be used to find a good hardware/software partition between these modules. In this paper, we use codesign methodology to partition the hardware and software of the real-time image encoder. Four major representative methods are chosen for discussion and performance evaluation. The results show that the codesign methodology can help us to select a good partition design and give up some designs that are not possible to meet the system specifications. Thus, it can shorten the design cycle and the development cost can be reduced.

The new generation of real-time systems are characterized by multiple, conflicting non-functional desiderata on goals. Furthermore, the systems exhibit very large size and complexity—in both application structures and underlying software and hardware platforms. We argue that current high-level real-time languages do not meet the challenge of these complex real-time systems and introduce a new language—CRL—that we claim does. Relevant real-time features of CRL are discussed and a summary is provided vis-à-vis future features that would address non-functional goals other than timeliness. A current implementation status and how CRL fits into a rather ambitious environment for the construction of complex real-time systems (under construction in our Real-Time Computing Lab at NJIT) are briefly presented.

Deterministic worst-case execution to satisfy hard real-time constraints, and speculative execution with rollback to improve average-case throughput, appear to lie on opposite ends of a spectrum of performance requirements and strategies. Nonetheless, we show there are situations in which speculative execution can probably improve the performance of a hard real-time system, either by improving average performance while not affecting the worst case, or by actually decreasing worst-case execution time. We also show how related strategies for partial or total precomputation can lead to improved performance. Finally, we discuss possible compiler transformations to detect chances of profitable speculative execution.>

The paradigm of computing defined by real-time applications places significant requirements on programming languages, among them (1) interfacing to hardware devices, (2) maintainability, portability, reliability, and safely, (3) fault tolerance, and nonstop operation; (4) concurrency, and (5) achieving correct timing predictably (and the consequent paramount schedulability analyzability requirement). We trace how these requirements affect various mechanisms of a typical programming language. Ada9X/spl minus/a new emerging standard for Ada/spl minus/is then illustrated as an example of a serious attempt to address these requirements in a programming language standard. While Ada9X is far from perfect, it is a significant step, and we are hopeful for the trend of schedulability analyzable languages to gain momentum and continue.>

Abstract Remote‐procedure calls (RPCs) allow distributed, high‐level language programs to communicate and synchronize in the usual manner via subprogram calls. One of the great challenges in RPC research is to preserve the traditiional call semantics despite the distribution and heterogeneity of the new environment. The main contribution of SUPRA‐RPC is in addressing the passing of subprograms as RPC parameters. In doing so, SUPRA overcomes a number of technical difficulties, stemming from scoping, side‐effects and other sources. Since supporting subprogram RPC parameters is harder than supporting non‐subprogram RPC parameters, the three (of six) components of the SUPRA architecture extend in novel ways the traditional functionality found in their counterparts in other RPC systems. The SUPRA stub generator extracts information not only from remote entry interfaces, but from any scope potentially referenced by a subprogram passed as an RPC parameter. In addition to the usual call‐ and accept‐stubs and the marshaling and unmarshaling routines, the generator constructs out‐of‐scope access stubs, callback' and callback‐handling‐stubs, and modified parameter subprograms and others. The SUPRA run‐time support manages a run‐time symbol table to keep track of referencing environments and out‐of‐scope objects. When an out‐of‐scope object is unavailable for access or execution on the server, the object is reached by a synchronous, ‘under‐the‐covers’ callback. The SUPRA process management supports servers with independent threads of control, manages (possibly nested) callbacks and pools of callback handler threads, and maintains correct identification of thread‐initiated calls or callbacks. A SUPRA prototype has been implemented on Sun Unix workstations. The prototype supports C, C++ and CommonLisp programs. A prototype graphical demonstration has been implemented as well, that represents RPC concepts in terms of common life objects and situations.

A set of language-independent schedulability analysis techniques is presented. Utilizing knowledge of implementation- and hardware-dependent information in a table-driven fashion, these techniques provide accurate worst-case time bounds and other schedulability information. A prototype schedulability analyzer has been developed to demonstrate the effectiveness of these techniques. The analyzer consists of a partially language-dependent front-end, targeted at real-time Euclid, a real-time language specifically designed with a set of schedulability analysis provisions built-in, and a language-dependent back-end. The analyzer has been used on a number of realistic real-time programs run on a multiple-microprocessor system. Predicted program performance differs only marginally from the actual performance.>

Concert, a high-level-language approach to programming heterogeneous distributed systems, is described. The Concert model introduces a small set of language extensions into conventional procedural languages. These language extensions support a cooperative peer process model which addresses in the distributed environment the same issues addressed by language semantics in the conventional environment. The Concert implementation provides layered support for these language extensions, bridging a different source of heterogeneity at each layer. A prototype Concert system currently includes C programs running on OS/2 on multiple PS/2s communicating via calls with one another as well as with PL/I programs running on VM/370.>

Real-Time Euclid, a language designed specifically to address reliability and guaranteed schedulability issues in real-time systems, is introduced. Real-Time Euclid uses exception handlers and import/export lists to provide comprehensive error detection, isolation, and recovery. The philosophy of the language is that every exception detectable by the hardware or the software must have an exception-handler clause associated with it. Moreover, the language definition forces every construct in the language to be time- and space-bounded. Consequently, Real-Time Euclid programs can always be analyzed for guaranteed schedulability of their processes. Thus, it is felt that Real-Time Euclid is well-suited for writing reliable real-time software.