Digital Twins (DTs) have emerged as essential tools for virtualizing and enhancing Cyber-Physical Systems (CPS) by providing synchronized digital counterparts that enable monitoring, control, prediction, and optimization. Initially conceived as passive digital shadows, DTs are increasingly evolving into intelligent and proactive entities, enabled by the integration of Artificial Intelligence (AI). Among these advancements, Opportunistic Digital Twins (ODTs) represent a novel class of DTs: living, AI-aided, and actionable models that opportunistically exploit edge-cloud resources to deliver enriched and adaptive representations of physical entities and processes. However, despite their promise, current research lacks systematic engineering methods to ensure reliable coordination, determinism, and real-time responsiveness of ODTs in distributed and resource-constrained CPS. This article addresses this gap by introducing an engineering approach to build dependable and efficient ODTs by leveraging the deterministic concurrency, explicit timing semantics, and disciplined event handling of Lingua Franca (LF). The approach is exemplified through a Smart Traffic Management case study centered on Emergency Vehicle Preemption (EVP), where the ODT dynamically selects AI models based on runtime conditions while ensuring deterministic coordination across distributed nodes. Experimental results confirm the feasibility and effectiveness of our methodology, underscoring the potential of LF-based ODT engineering to enhance reliability, adaptability, and scalability in intelligent and distributed CPS deployments.

Ensuring predictable and deterministic behavior in distributed cyber-physical systems (CPS) is essential for guaranteeing safety, reliability, and real-time behavior. However, achieving this predictability is challenging due to network uncertainties, asynchronous execution, and complex timing interactions.

Many software systems are polyglot; that is, they comprise programs implemented in a combination of programming languages. Program verifiers, however, tend to be customized for individual languages. Verification by compiling to a common encoding requires supporting full language syntax and semantics which is prohibitive for modern languages. We present POLYVER, an alternative compositional approach to polyglot verification that bootstraps off-the-shelf language-specific verifiers with abstraction and synthesis. POLYVER uses contracts written in an intermediate language to abstract individual procedures in the system. Our verification approach uses language-specific verifiers (e.g., for C or Rust) to validate these contracts and the UCLID5 model checker for com- positionally verifying a temporal property on the overall system using the contracts. The intermediate language sidesteps the need for compiling implementation languages to a common encoding, a key obstacle with polyglot verification. Finally, POLYVER automates the generation of contracts using synthesis oracles such as large-language-models (LLMs). Overall POLYVER performs contract synthesis and verification in a counterexample-guided abstraction refinement and inductive synthesis (CEGIS-CEGAR) loop to verify the system-level property. We use POLYVER to verify programs in the Lingua Franca polyglot language. We are able to verify systems with C and Rust procedures, as well as C language fragments that were unsupported in previous work.

The rise of intelligent autonomous systems, especially in robotics and autonomous agents, has created a critical need for robust communication middleware that can ensure real-time processing of extensive sensor data. Current robotics middleware like Robot Operating System (ROS) 2 faces challenges with nondeterminism and high communication latency when dealing with large data across multiple subscribers on a multi-core compute platform. To address these issues, we present High-Performance Robotic Middleware (HPRM), built on top of the deterministic coordination language Lingua Franca (LF). HPRM employs optimizations including an in-memory object store for efficient zero-copy transfer of large payloads, adaptive serialization to minimize serialization overhead, and an eager protocol with real-time sockets to reduce handshake latency. Benchmarks show HPRM achieves up to 114x lower latency than ROS2 when broadcasting large messages to multiple nodes. We then demonstrate the benefits of HPRM by integrating it with the CARLA simulator and running reinforcement learning agents along with object detection workloads. In the CARLA autonomous driving application, HPRM attains 91.1% lower latency than ROS2. The deterministic coordination semantics of HPRM, combined with its optimized IPC mechanisms, enable efficient and predictable real-time communication for intelligent autonomous systems. Code and videos can be found on our project page: https://hprm-robotics.github.io/HPRM

To design performant, expressive, and reliable cyber-physical systems (CPSs), researchers extensively perform quasi-static scheduling for concurrent models of computation (MoCs) on multi-core hardware. However, these quasi-static scheduling approaches are developed independently for their corresponding MoCs, despite commonality in the approaches. To help generalize the use of quasi-static scheduling to new and emerging MoCs, this article proposes a unified approach for a class of deterministic timed concurrent models (DTCMs), including prominent models such as synchronous dataflow (SDF), Boolean-controlled dataflow (BDF), scenario-aware dataflow (SADF), and Logical Execution Time (LET). In contrast to scheduling techniques tailored exclusively to specific MoCs, our unified approach leverages a common intermediate formalism called state space finite automata (SSFA), bridging the gap between high-level MoCs and executable schedules. Once identified as DTCMs, new MoCs can directly adopt SSFA-based scheduling, significantly easing adoption. We show that quasi-static schedules facilitated by SSFA are provably free from timing anomalies and enable straightforward worst-case makespan analysis. We demonstrate the approach using the reactor model—an emerging discrete-event MoC—programmed using the Lingua Franca ( LF ) language. Experiments show that quasi-statically scheduled LF programs exhibit lower runtime overhead compared to the dynamically scheduled LF programs, and that the analyzable worst-case makespans enable compile-time deadline checking.

Mathematical models can yield certainty, as can probabilistic models where the probabilities degenerate. The field of formal methods emphasizes developing such certainty about engineering designs. In safety critical systems, such certainty is highly valued and, in some cases, even required by regulatory bodies. But achieving reasonable performance for sufficiently complex environments appears to require the use of AI technologies, which resist such certainty. This extended abstract suggests that certainty and intelligence may be fundamentally incompatible.

The reactor model is a model of computation for concurrent systems that includes semantics for time to guarantee deterministic execution of events. However, the guarantee of determinism comes at the price of raising the complexity of building a runtime scheduling algorithm that efficiently exploit parallelism of real time systems. In this paper we propose a methodology called “timing enclaves” for partitioning of reactor programs written using Lingua Franca, a novel coordination language that implements the reactor model. Timing enclaves decouple the timeline of an application to use multiple schedulers that allow parallel computation while preserving determinism. We evaluate our approach on a baseband processing benchmark, a complex use case with a high degree of parallelism and real-time constraints. We show that our approach has performance comparable to a prior asynchronous and nondeterministic implementation while ensuring determinism.

Timing control while preserving determinism is often a key requirement for ensuring the safety and correctness of distributed cyber-physical systems (CPS). Discrete-event (DE) systems provide a suitable model of computation (MoC) for time-sensitive distributed CPS. The high-level architecture (HLA) is a useful tool for the distributed simulation of DE systems, but its techniques can be adapted for implementing distributed CPS. However, HLA incurs considerable overhead in network messages conveying timing information between the distributed nodes and the centralized run-time infrastructure (RTI). This paper gives a novel approach and implementation that reduces such network messages while preserving DE semantics. An evaluation of our runtime demonstrates that our approach significantly reduces the volume of messages for timing information in HLA.

Parallel Reinforcement Learning (RL) frameworks are essential for mapping RL workloads to multiple computational resources, allowing for faster generation of samples, estimation of values, and policy improvement. These computational paradigms require a seamless integration of training, serving, and simulation workloads. Existing frameworks, such as Ray, are not managing this orchestration efficiently, especially in RL tasks that demand intensive input/output and synchronization between actors on a single node. In this study, we have proposed a solution implementing the reactor model, which enforces a set of actors to have a fixed communication pattern. This allows the scheduler to eliminate work needed for synchronization, such as acquiring and releasing locks for each actor or sending and processing coordination-related messages. Our framework, Lingua Franca (LF), a coordination language based on the reactor model, also supports true parallelism in Python and provides a unified interface that allows users to automatically generate dataflow graphs for RL tasks. In comparison to Ray on a single-node multi-core compute platform, LF achieves 1.21x and 11.62x higher simulation throughput in OpenAI Gym and Atari environments, reduces the average training time of synchronized parallel Q-learning by 31.2%, and accelerates multi-agent RL inference by 5.12x.

We discuss a novel approach for constructing deterministic reactive systems that revolves around a temporal model that incorporates a multiplicity of timelines. This model is central to Lingua Franca ( LF ), a polyglot coordination language and compiler toolchain we are developing for the definition and composition of concurrent components called reactors, which are objects that react to and emit discrete events. Our temporal model differs from existing models like the logical execution time (LET) paradigm and synchronous languages in that it reflects that there are always at least two distinct timelines involved in a reactive system; a logical one and a physical one—and possibly multiple of each kind. This article explains how the relationship between events across timelines facilitates reasoning about consistency and availability across components in cyber-physical systems (CPSs).

Modern cyber-physical systems often make use of heterogeneous systems-on-chip with reconfigurable logic to provide adequate computing power and flexible I/O. However, modeling, verifying, and implementing the computations spanning CPUs and reconfigurable logic are still challenging. The hardware and software components are often designed by different teams and at different levels of abstraction, making it hard to reason about the resulting computation. We propose to lift both hardware and software design to the same level of abstraction by using the Lingua Franca coordination language. Lingua Franca is based on a sparse synchronous model that allows modeling concurrency and timing while keeping a sequential model for the actual computation. We define hardware reactors as a subset of the reactor model of computation underlying Lingua Franca. We also present and evaluate reactor-chisel, a hardware runtime implementing the semantics of hardware reactors, and an extension to the Lingua Franca compiler enabling reactor-oriented hardware–software codesign.

Complex software systems often feature distinct modes of operation, each designed to handle a particular scenario that may require the system to respond in a certain way. Breaking down system behavior into mutually exclusive modes and discrete transitions between modes is a commonly used strategy to reduce implementation complexity and promote code readability. The work in this paper aims to bring the advantages of working with modal models to mainstream programming languages, by following the polyglot coordination approach of Lingua Franca (LF), in which verbatim target code (e. g., C, C++, Python, Typescript, or Rust) is encapsulated in composable reactive components called reactors. Reactors can form a dataflow network, are triggered by timed as well as sporadic events, execute concurrently, and can be distributed across nodes on a network. With modal models in LF, we introduce a lean extension to the concept of reactors that enables the coordination of reactive tasks based on modes of operation.

Actor frameworks and similar reactive programming techniques are widely used for building concurrent systems. They promise to be efficient and scale well to a large number of cores or nodes in a distributed system. However, they also expose programmers to nondeterminism, which often makes implementations hard to understand, debug, and test. The recently proposed reactor model is a promising alternative that enables deterministic concurrency. In this article, we present an efficient, parallel implementation of reactors and demonstrate that the determinacy of reactors does not imply a loss in performance. To show this, we evaluate Lingua Franca (LF), a reactor-oriented coordination language. LF equips mainstream programming languages with a deterministic concurrency model that automatically takes advantage of opportunities to exploit parallelism. Our implementation of the Savina benchmark suite demonstrates that, in terms of execution time, the runtime performance of LF programs even exceeds popular and highly optimized actor frameworks. We compare against Akka and CAF, which LF outperforms by 1.86× and 1.42×, respectively.

In distributed applications, Brewer’s CAP theorem tells us that when networks become partitioned (P), one must give up either consistency (C) or availability (A). Consistency is agreement on the values of shared variables; availability is the ability to respond to reads and writes accessing those shared variables. Availability is a real-time property whereas consistency is a logical property. We extend consistency and availability to refer to cyber-physical properties such as the state of the physical system and delays in actuation. We have further extended the CAP theorem to relate quantitative measures of these two properties to quantitative measures of communication and computation latency (L), obtaining a relation called the CAL theorem that is linear in a max-plus algebra. This paper shows how to use the CAL theorem in various ways to help design cyber-physical systems. We develop a methodology for systematically trading off availability and consistency in application-specific ways and to guide the system designer when putting functionality in end devices, in edge computers, or in the cloud. We build on the Lingua Franca coordination language to provide system designers with concrete analysis and design tools to make the required tradeoffs in deployable embedded software.

Formal verification of cyber-physical systems (CPS) is challenging because it has to consider real-time and concurrency aspects that are often absent in ordinary software. Moreover, the software in CPS is often complex and low-level, making it hard to assure that a formal model of the system used for verification is a faithful representation of the actual implementation, which can undermine the value of a verification result. To address this problem, we propose a methodology for building verifiable CPS based on the principle that a formal model of the software can be derived automatically from its implementation. Our approach requires that the system implementation is specified in Lingua Franca (LF), a polyglot coordination language tailored for real-time, concurrent CPS, which we made amenable to the specification of safety properties via annotations in the code. The program structure and the deterministic semantics of LF enable automatic construction of formal axiomatic models directly from LF programs. The generated models are automatically checked using Bounded Model Checking (BMC) by the verification engine Uclid5 using the Z3 SMT solver. The proposed technique enables checking a well-defined fragment of Safety Metric Temporal Logic (Safety MTL) formulas. To ensure the completeness of BMC, we present a method to derive an upper bound on the completeness threshold of an axiomatic model based on the semantics of LF. We implement our approach in the LF V erifier and evaluate it using a benchmark suite with 22 programs sampled from real-life applications and benchmarks for Erlang, Lustre, actor-oriented languages, and RTOSes. The LF V erifier correctly checks 21 out of 22 programs automatically.

Abstract In 2010, Fuhrmann et al. argued for enhancing modeler productivity by providing tooling that, put simply, combines the best of textual and graphical worlds. They referred to this as pragmatics , and argued that a key enabler would be the ability to automatically synthesize customized graphical views from a (possibly textual) model. The model would be the “ground truth” used, for example, for downstream code synthesis and simulation; the graphical views would typically be abstractions from the model serving various purposes, including documentation. Twelve years later, we reflect on their proposal, and illustrate the current state with the recently developed polyglot coordination language Lingua Franca (LF). LF has been designed with pragmatics in mind since early on, and some characteristics of LF make it particularly suited for pragmatics-aware programming and modeling. However, the underlying pragmatic principles are broadly applicable, and by now a set of mature open source tools is available for putting them into practice.

This article is about deterministic models, what they are, why they are useful, and what their limitations are. First, the article emphasizes that determinism is a property of models, not of physical systems. Whether a model is deterministic or not depends on how one defines the inputs and behavior of the model. To define behavior, one has to define an observer. The article compares and contrasts two classes of ways to define an observer, one based on the notion of “state” and another that more flexibly defines the observables. The notion of “state” is shown to be problematic and lead to nondeterminism that is avoided when the observables are defined differently. The article examines determinism in models of the physical world. In what may surprise many readers, it shows that Newtonian physics admits nondeterminism and that quantum physics may be interpreted as a deterministic model. Moreover, it shows that both relativity and quantum physics undermine the notion of “state” and therefore require more flexible ways of defining observables. Finally, the article reviews results showing that sufficiently rich sets of deterministic models are incomplete. Specifically, nondeterminism is inescapable in any system of models rich enough to encompass Newton’s laws.

Many programming languages and programming frameworks focus on parallel and distributed computing. Several frameworks are based on actors, which provide a more disciplined model for concurrency than threads. The interactions between actors, however, if not constrained, admit nondeterminism. As a consequence, actor programs may exhibit unintended behaviors and are less amenable to rigorous testing. We show that nondeterminism can be handled in a number of ways, surveying dataflow dialects, process networks, synchronous-reactive models, and discrete-event models. These existing approaches, however, tend to require centralized control, pose challenges to modular system design, or introduce a single point of failure. We describe “reactors,” a new coordination model that combines ideas from several of these approaches to enable determinism while preserving much of the style of actors. Reactors promote modularity and allow for distributed execution. By using a logical model of time that can be associated with physical time, reactors also provide control over timing. Reactors also expose parallelism that can be exploited on multicore machines and in distributed configurations without compromising determinacy.

Programmable logic controllers (PLCs) are an established platform, widely used throughout industrial automation but poorly understood among researchers. This article gives an overview of the state of the practice, explaining why this settled technology persists throughout industry and presenting a critical analysis of the strengths and weaknesses of the dominant programming styles for today's PLC-based automation systems. We describe the software execution patterns that are standardized loosely in IEC 61131-3. We identify opportunities for improvements that would enable increasingly complex industrial automation applications while strengthening safety and reliability. Specifically, we propose deterministic, distributed programming models that embrace explicit timing, event-triggered computation, and improved security.

Computer architectures used in safety-critical domains are subjected to worst-case execution time analysis. The presence of performance-driven microarchitectures may trigger undesired timing phenomena, called timing anomalies, and complicate the timing analysis. This paper investigates pipelines specifically designed to simplify the worst-case execution time analysis (also called predictable pipelines). We propose formal and executable models of four research-oriented pipelines and one industrial pipeline to validate some of their claims related to their timing behavior. We indeed validate, via bounded model checking, the absence of a type of timing anomalies called amplification timing anomalies, or its potential presence by identifying prerequisite to situations where they can occur.

Model checking a software system is about verifying that the state trajectory of every execution of the software satisfies formally specified properties. The set of possible executions is modeled as a transition system. Each "state" in the transition system represents an assignment of values to variables, and a state trajectory (a path through the transition system) is a sequence of such assignments. For cyberphysical systems (CPSs), however, we are more interested in the state of the physical system than the values of the software variables. The value of model checking the software therefore depends on the relationship between the state of the software and the state of the physical system. This relationship can be complex because of the real-time nature of the physical plant, the sensors and actuators, and the software that is almost always concurrent and distributed. In this paper, we study different ways to construct a transition system model for the distributed and concurrent software components of a CPS. We describe a logical-time based transition system model, which is commonly used for verifying programs written in synchronous languages, and derive the conditions under which such a model faithfully reflects physical states. When these conditions are not met (a common situation), a finer-grained event-based transition system model may be required. Even this finer-grained model, however, may not be sufficiently faithful, and the transition system model needs to be refined further to express not only the properties of the software, but also the properties of the hardware on which it runs. We illustrate these tradeoffs using a coordination language called Lingua Franca that is well-suited to extracting transition system models at these various levels of granularity, and we extend the Timed Rebeca language and its tool Afra to perform this extraction and then to perform model checking.

We discuss a novel approach for constructing deterministic reactive systems that evolves around a temporal model which incorporates a multiplicity of timelines. This model is central to LINGUA FRANCA (LF), a polyglot coordination language and compiler toolchain we are developing for the definition and composition of concurrent components called Reactors, which are objects that react to and emit discrete events. What sets LF apart from other languages that treat time as a first-class citizen is that it confronts the issue that in any reactive system there are at least two distinct timelines involved; a logical one and a physical one-and possibly multiple of each kind. LF provides a mechanism for relating events across timelines, and guarantees deterministic program behavior under quantifiable assumptions.

In this paper, we propose a robust solution for the path planning and scheduling of the moving objects in a Track-based Traffic Control System (TTCS). The moving objects in a TTCS pass over pre-specified sub-tracks. Each sub-track accommodates at most one moving object in-transit. Due to the uncertainties in the context of a TTCS, we assign an arrival time window to each moving object for each sub-track in its route, instead of an exact value. The moving object can safely enter into the sub-track in the mentioned time window. To develop a safe plan, we adapt the tagged-signal model and provide a rigorous mathematical formalism for the actor model of a TTCS. To illustrate the applicability of the provided semantics, we provide a formal model of TTCSs in the Alloy language and use its analyzer to verify the developed model against system safety properties.

Accurate localization from Cyber-Physical Systems (CPS) is a critical enabling technology for context-aware applications and control. As localization plays an increasingly safety-critical role, location systems must be able to identify and eliminate faulty measurements to prevent dangerously inaccurate localization. In this article, we consider the range-based localization problem and propose a method to detect coordinated adversarial corruption on anchor positions and distance measurements. Our algorithm, G ordian , rapidly finds attacks by identifying geometric inconsistencies at the graph level without requiring assumptions about hardware, ranging mechanisms, or cryptographic protocols. We give necessary conditions for which attack detection is guaranteed to be successful in the noiseless case, and we use that intuition to extend G ordian to the noisy case where fewer guarantees are possible. In simulations generated from real-world sensor noise, we empirically show that G ordian ’s trilateration counterexample generation procedure enables rapid attack detection even for combinatorially difficult problems.

An emerging type of network architecture called edge computing has the potential to improve the availability and resilience of IoT services under anomalous situations such as network failures or denial-of-service (DoS) attacks. However, relatively little has been explored on the problem of ensuring availability even when edge computers that provide key security services (e.g., authentication and authorization) become unavailable themselves. This article proposes a resilient authentication and authorization framework to enhance the availability of IoT services under DoS attacks or failures. The proposed approach leverages a technique called secure migration , which allows an IoT device to migrate to another trusted edge computer when its own local authorization service becomes unavailable. Specifically, we describe the design of a secure migration framework and its supporting mechanisms, including (1) automated migration policy construction and (2) protocols for preparing and executing the secure migration. We formalize secure migration policy construction as an integer linear programming (ILP) problem and show its effectiveness using a case study on smart buildings, where the proposed solution achieves significantly higher availability under simulated attacks on authorization services.

Programming time-critical systems is notoriously difficult. In this paper we propose an actor-oriented programming model with a semantic notion of time and a deterministic coordination semantics based on discrete events to exercise precise control over both the computational and timing aspects of the system behavior.

Actors have become widespread in programming languages and programming frameworks focused on parallel and distributed computing. While actors provide a more disciplined model for concurrency than threads, their interactions, if not constrained, admit nondeterminism. As a consequence, actor programs may exhibit unintended behaviors and are less amenable to rigorous testing. We show that nondeterminism can be handled in a number of ways, surveying dataflow dialects, process networks, synchronous-reactive models, and discrete-event models. These existing approaches, however, tend to require centralized control, pose challenges to modular system design, or introduce a single point of failure. We describe “reactors,” a new coordination model that combines ideas from several of the aforementioned approaches to enable determinism while preserving much of the style of actors. Reactors promote modularity and allow for distributed execution. By using a logical model of time that can be associated with physical time, reactors also admit control over timing.

Discovery, invention, and design are all about models. When we say "Joseph Priestly discovered oxygen in 1774," we do not mean that Priestly dug up a canister of oxygen, recognized it as something new, and released it, for the first time, into the air. We mean instead that Priestly came up with a model for the composition of air and the role of one of its components. The model was the discovery, not the O$_2$ molecule. Models in engineering and science are strongly affected by the modeling paradigm within which a model is constructed. Priestly's paradigm was firmly rooted in a theory of phlogiston, a fire-like element released in combustion, and his inability to break out of this rut made his work more like idiosyncratic philosophy than like science. The constraints of a modeling paradigm can be debilitating, but at the same time, they are essential. The constraints define the "platform" in "platform-based design." No effective modeling paradigm lacks constraints, and those constraints do not just limit our thinking, they also enable our thinking. In engineering, constraints are even more important because models that cannot be turned into real, working systems are not useful models. Whereas in science the value of a model lies in how well it matches a pre-existing physical system, in engineering, the value of a manufactured physical system lies in how well it matches a model. Sangiovanni-Vincetelli has pointed out that modeling constraints provide a "freedom from choice" that makes it easier to build models for which we can create matching physical realizations. Because of this, engineers strive to grow the number of relevant modeling paradigms, those for which we can build effective physical realizations, whereas scientists strive to shrink the number of relevant paradigms, those needed to explain the physical world.

Connected cars have the potential to transform a vehicle from a transportation platform to a platform for integrating humans with a city. To that end we introduce semantic accessors (actor based local proxies for remote services) as a novel, and powerful discovery mechanism for connected vehicles that bridges the domains of Internet of Things (IoT) composition frameworks and the semantic web of things. The primary components of this approach include a local semantic repository used for maintaining the vehicle's perspective of its real-world context, accessors for querying and dynamically updating the repository to match evolving vehicular context information, accessors for services (such as parking) linked to a service ontology, and a swarmlet controller responsible for managing the above in accordance with user input. We demonstrate this semantic accessor architecture with a prototype Dashboard display that downloads accessors for new services as they become available and dynamically renders their self-described user interface components.

This paper describes an implementation in progress of a C-based framework for execution of deterministic, concurrent, real-time software components called "reactors." The component interfaces and their interconnections are given a coordination language called Lingua Franca, while the work done by the components is given in ordinary C. The implementation described here can exploit multiple cores and is capable of realizing rate monotonic and earliest deadline first scheduling policies.

Model-based design methodologies are commonly used in industry for the development of complex cyber-physical systems (CPSs). There are many different languages, tools, and formalisms for model-based design, each with its strengths and weaknesses. Instead of accepting some weaknesses of a particular tool, an alternative is to embrace heterogeneity, and to develop tool integration platforms and protocols to leverage the strengths from different environments. A fairly recent attempt in this direction is the functional mock-up interface (FMI) standard that includes support for co-simulation. Although this standard has reached acceptance in industry, it provides only limited support for simulating systems that mix continuous and discrete behavior, which are typical of CPS. This paper identifies the representation of time as a key problem, because the FMI representation does not support well the discrete events that typically occur at the cyber-physical boundary. We analyze alternatives for representing time in hybrid co-simulation and conclude that a superdense model of time using integers only solves many of these problems. We show how an execution engine can pick an adequate time resolution, and how disparities between time representations internal to co-simulated components and the resulting effects of time quantization can be managed. We propose a concrete extension to the FMI standard for supporting hybrid co-simulation that includes integer time, automatic choice of time resolution, and the use of absent signals. We explain how these extensions can be implemented modularly within the frameworks of existing simulation environments.

No abstract available.

The emerging class of wide-area streaming analytics faces the challenge of scarce and variable WAN bandwidth. Non-adaptive applications built with TCP or UDP suffer from increased latency or degraded accuracy. State-of-the-art approaches that adapt to network changes require developer writing sub-optimal manual policies or are limited to application-specific optimizations.

In this paper, we describe a component-based software architecture for the Internet of Things in which proxies for Things and services that we call “accessors” interact with one another under a concurrent, time-stamped, discrete-event (DE) semantics. These proxies are analogous to web pages, which proxy a cloud-based service such as a bank, but instead of being designed to interface those services with humans, accessors are designed to interface services and Things with other services and Things. A deterministic DE semantics is combined with a widely used pattern for handling network interactions that we call asynchronous atomic callbacks (AACs). AAC enables many concurrent pending requests to be active at once without blocking and without the treacherous concurrency pitfalls of threads. In effect, our architecture combines AAC with actors where the actor model has been endowed with a temporal semantics. We show how this architecture can leverage the previously reported secure swarm toolkit (SST) to achieve stateof- the-art authentication, authorization, and encryption of interactions across networks.

Prior work has shown that it is possible to design microarchitectures called PRET machines that deliver precise and repeatable timing of software execution without sacrificing performance. That prior work provides specific designs for PRET microarchitectures and compares them against conventional designs. This paper defines a class of microarchitectures called abstract PRET machines (APMs) that capture the essential temporal properties of PRET machines. We show that APMs deliver deterministic timing with no loss of performance for a family of real-time problems consisting of sporadic event streams with deadlines equal to periods. On the other hand, we observe a tradeoff between deterministic timing and the ability to meet deadlines for sporadic event streams with constrained deadlines.

This paper presents a master algorithm for co-simulation of hybrid systems using the Functional Mock-up Interface (FMI) standard. Our algorithm introduces step revision to achieve an accurate and precise handling of mixtures of continuous-time and discrete-event signals, particularly in the situation where components are unable to accurately extrapolate their input. Step revision provides an efficient means to respect the error bounds of numerical approximation algorithms that operate inside co-simulated FMUs. We first explain the most fundamental issues associated with hybrid co-simulation and analyze them in the framework of FMI. We demonstrate the necessity for step revision to address some of these issues and formally describe a master algorithm that supports it. Finally, we present experimental results obtained through our reference implementation that is part of our publicly available open-source toolchain called FIDE.

One of the biggest challenges in cyber-physical system (CPS) design is their intrinsic complexity, heterogeneity, and multidisciplinary nature. Emerging distributed CPSs integrate a wide range of heterogeneous aspects such as physical dynamics, control, machine learning, and error handling. Furthermore, system components are often distributed over multiple physical locations, hardware platforms, and communication networks. While model-based design (MBD) has tremendously improved the design process, CPS design remains a difficult task. Models are meant to improve understanding of a system, yet this quality is often lost when models become too complicated. In this paper, we show how to use aspect-oriented (AO) modeling techniques in MBD as a systematic way to segregate domains of expertise and cross-cutting concerns within the model. We demonstrate these concepts on actor-oriented models of an industrial robotic swarm application and illustrate the use of AO modeling techniques to manage the complexity. We also show how to use AO modeling for design-space exploration.

This article examines the role of modeling in the engineering of cyber-physical systems. It argues that the role that models play in engineering is different from the role they play in science, and that this difference should direct us to use a different class of models, where simplicity and clarity of semantics dominate over accuracy and detail. I argue that determinism in models used for engineering is a valuable property and should be preserved whenever possible, regardless of whether the system being modeled is deterministic. I then identify three classes of fundamental limits on modeling, specifically chaotic behavior, the inability of computers to numerically handle a continuum, and the incompleteness of determinism. The last of these has profound consequences.

Accuracy and responsiveness are two key properties of emerging cyber-physical energy systems that need to incorporate high throughput sensor streams for distributed monitoring and control applications. The electric power grid, which is a prominent example of such systems, is being integrated with high throughput sensors in order to support stable system dynamics that are provisioned to be utilized in real-time supervisory control applications. The end-to-end performance and overall scalability of cyber-physical energy applications depend on robust middleware services that are able to operate with variable resources and multi-source sensor data. This leads to uncertain behavior under highly variable sensor and middleware topologies. We present a parametric approach to modeling the middleware service architecture for distributed power applications and account for temporal satisfiability of system properties under network resource and data volume uncertainty. We present a heterogeneous modeling framework that combines Monte Carlo simulations of uncertainty parameters within an executable discrete-event middleware service model. By employing Monte Carlo simulations followed by regression analysis, we quantify system parameters that significantly affect behavior of middleware services and the achievability of temporal requirements.

Cyber-physical systems are integrations of computation, communication networks, and physical dynamics. Although time plays a central role in the physical world, all widely used software abstractions lack temporal semantics. The notion of correct execution of a program written in every widely-used programming language today does not depend on the temporal behavior of the program. But temporal behavior matters in almost all systems, and most particularly in cyber-physical systems. In this talk, I will argue that time can and must become part of the semantics of programs for a large class of applications. To illustrate that this is both practical and useful, we will describe a recent effort at Berkeley in the design and implementation of timing-centric software systems. Specifically, I will describe PRET machines, which redefine the instruction-set architecture (ISA) of a microprocessor to embrace temporal semantics. Such machines can be used in high-confidence and safety-critical systems, in energy-constrained systems, in mixed-criticality systems, and as a Real-Time Unit (RTU) that cooperates with a general-purpose processor to provide real-time services, in a manner similar to how a GPU provides graphics services.

System simulation is a valuable tool to unveil inefficiencies and to test new strategies when implementing and revising systems. Often, simulations are parameterized using offline data and heuristic knowledge. Operational data, i.e., data gained through experimentation and observation, can greatly improve the fidelity between the actual system and the simulation. In a traffic scenario, for example, different road conditions or vehicle types can impact the outcome of the simulation and have to be considered during the modeling stage. This paper proposes using machine learning techniques to generate high fidelity simulation models. A traffic simulation case study exemplifies this approach by generating a model for the SUMO traffic simulator from vehicular telemetry data.

This paper describes an open-source simulator for cyberphysical systems called CyPhySim that is based on Ptolemy II. This simulator supports classical (Runge-Kutta) and quantized-state simulation of ordinary differential equations, modal models (hybrid systems), discrete-event models, the Functional Mockup Interface (FMI) for model-exchange and co-simulation, discrete-time (periodic) systems, and algebraic loop solvers. CyPhySim provides a graphical editor, an XML file syntax for models, and an open API for programmatic construction of models. It includes an innovation called "smooth tokens," which allow for a blend of numerical and symbolic computation, and for certain kinds of system models, dramatically reducing the computation required for simulation.

This paper defines a suite of requirements for future hybrid cosimulation standards, and specifically provides guidance for development of a hybrid cosimulation version of the Functional Mockup Interface (FMI). A cosimulation standard defines interfaces that enable diverse simulation tools to interoperate. Specifically, one tool defines a component that forms part of a simulation model in another tool. We focus on components with inputs and outputs that are functions of time, and specifically on mixtures of discrete events and continuous time signals. This hybrid mixture is not well supported by existing cosimulation standards, and specifically not by FMI 2.0, for reasons that are explained in this paper. The paper defines a suite of test components, giving a mathematical model of an ideal behavior, plus a discussion of practical implementation considerations. The discussion includes acceptance criteria by which we can determine whether a standard supports definition of each component. In addition, we define a set of test compositions that define requirements for coordination between components, including consistent handling of timed events.

This demo provides a preview of a pre-release version of CyPhySim, an open-source simulator for cyber-physical systems. This simulator supports discrete-event models, quantized-state simulation of continuous dynamics, the Functional Mockup Interface (FMI), classical (Runge-Kutta) simulation of continuous dynamics, modal models (hybrid systems), discrete-time (periodic) systems, and algebraic loop solvers. CyPhySim provides a graphical editor, an XML file syntax for models, and an open API for programmatic construction of models.

We propose a model for Semantic Localization, i.e. establishing positional relations on meaningful objects, to enable the principled integration of heterogeneous localization clues -- such as those derived from ubiquitous sensors in the Internet of Things. Our approach is two-pronged: we consider relation-structured Phenomenal Maps alongside spatially-organized Physical Maps. Phenomenal Maps may be used to answer semantic queries about the relative position of objects without necessarily resorting to physical coordinates. Physical Maps are not restricted to purely Euclidian spaces, to the contrary we identify useful applications for topological, and metrical maps among others. We give the framework for a structured mechanism through which localization information in all these representations may be reconciled.

Mixed-criticality systems have tasks with different criticality levels running on the same hardware platform. Today's DRAM controllers cannot adequately satisfy the often conflicting requirements of tightly bounded worst-case latency for critical tasks and high performance for non-critical real-time tasks. We propose a DRAM memory controller that meets these requirements by using bank-aware address mapping and DRAM command-level priority-based scheduling with preemption. Many standard DRAM controllers can be extended with our approach, incurring no performance penalty when critical tasks are not generating DRAM requests. Our approach is evaluated by replaying memory traces obtained from executing benchmarks on an ARM ISA-based processor with caches, which is simulated on the gem5 architecture simulator. We compare our approach against previous TDM-based approaches, showing that our proposed memory controller achieves dramatically higher performance for non-critical tasks, without any significant impact on the worstcase latency of critical tasks.

This paper introduces aspect-oriented modeling (AOM) as a powerful, model-based design technique to assess the security of Cyber-Physical Systems (CPS). Particularly in safety-critical CPS such as automotive control systems, the protection against malicious design and interaction faults is paramount to guaranteeing correctness and reliable operation. Essentially, attack models are associated with the CPS in an aspect-oriented manner to evaluate the system under attack. This modeling technique requires minimal changes to the model of the CPS. Using application-specific metrics, the designer can gain insights into the behavior of the CPS under attack.

Cyber-physical systems are integrations of computation, communication networks, and physical dynamics. Although time plays a central role in the physical world, all widely used software abstractions lack temporal semantics. The notion of correct execution of a program written in every widely-used programming language today does not depend on the temporal behavior of the program. But temporal behavior matters in almost all systems. Even in systems with no particular real-time requirements, timing of programs is relevant to the value delivered by programs, and in the case of concurrent programs, also affects the functionality. In cyber-physical systems, temporal behavior affects not just the value delivered by a system but also its correctness. In this talk, I will argue that time can and must become part of the semantics of programs for a large class of applications. To illustrate that this is both practical and useful, we will describe two recent efforts at Berkeley in the design and implementation of timing-centric software systems. On the implementation side, I will describe PRET machines, which redefine the instruction-set architecture (ISA) of a microprocessor to include temporal semantics. On the design side, I will briefly describe PTIDES, a programming model for distributed real-time systems. PTIDES leverages clock synchronization to deliver a deterministic model of computation for distributed real-time systems.

Mixed-criticality systems, in which multiple tasks of varying criticality execute on a single hardware platform, are an emerging research area in real-time embedded systems. High-criticality tasks require spatial and temporal isolation guarantees for independent verification, and the task set should efficiently utilize hardware resources. Hardware-based isolation is desirable but often underutilizes hardware resources, which can consist of multiple single-core, multicore, or multithreaded processors. We present FlexPRET, a processor designed specifically for mixed-criticality systems by allowing each task to make a trade-off between hardware-based isolation and efficient processor utilization. FlexPRET uses fine-grained multithreading with flexible scheduling and timing instructions to provide this functionality.

In this paper, we explain how to achieve deterministic execution of FMUs (Functional Mockup Units) under the FMI (Functional Mockup Interface) standard. In particular, we focus on co-simulation, where an FMU either contains its own internal simulation algorithm or serves as a gateway to a simulation tool. We give conditions on the design of FMUs and master algorithms (which orchestrate the execution of FMUs) to achieve deterministic co-simulation. We show that with the current version of the standard, these conditions demand capabilities from FMUs that are optional in the standard and rarely provided by an FMU in practice. When FMUs lacking these required capabilities are used to compose a model, many basic modeling capabilities become unachievable, including simple discrete-event simulation and variable-step-size numerical integration algorithms. We propose a small extension to the standard and a policy for designing FMUs that enables deterministic execution for a much broader class of models. The extension enables a master algorithm to query an FMU for the time of events that are expected in the future. We show that a model can be executed deterministically if all FMUs in the model are either memoryless or implement one of rollback or step-size prediction. We show further that such a model can contain at most one “legacy” FMU that is not memoryless and provides neither rollback nor step-size prediction.

This paper presents the concept of adaptive programs, whose computation and communication structures can morph to adapt to environmental and demand changes to save energy and computing resources. In this approach, programmers write one single program using a language at a higher level of abstraction. The compiler will exploit the properties of the abstractions to generate an adaptive program that is able to adjust computation and communication structures to environmental and demand changes. We develop a technique, called StreaMorph, that exploits the properties of stream programs' Synchronous Dataflow (SDF) programming model to enable runtime stream graph transformation. The StreaMorph technique can be used to optimize memory usage and to adjust core utilization leading to energy reduction by turning off idle cores or reducing operating frequencies. The main challenge for such a runtime transformation is to maintain consistent program states by copying states between different stream graph structures, because a stream program optimized for different numbers of cores often has different sets of filters and inter-filter channels. We propose an analysis that helps simplify program state copying processes by minimizing copying of states based on the properties of the SDF model. Finally, we implement the StreaMorph method in the StreamIt compiler. Our experiments on the Intel Xeon E5450 show that using StreaMorph to minimize the number of cores used from eight cores to one core, e.g. when streaming rates become lower, can reduce energy consumption by 76.33% on average. Using StreaMorph to spread workload from four cores to six or seven cores, e.g. when more cores become available, to reduce operating frequencies, can lead to 10% energy reduction. In addition, StreaMorph can lead to a buffer size reduction of 82.58% in comparison with a straightforward inter-core filter migration technique when switching from using eight cores to one core.

We consider end-to-end latency specifications for hard real-time embedded systems. We introduce a discrete-event programming model generalizing such specifications, and address its schedulability problem for uniprocessor systems. This turns out to be rather idiosyncratic, involving complex, time-dependent release predicates and precedence constraints, quite unlike anything we have seen in the hard real-time computing literature. We prove the optimality of the earliest-deadline-first scheduling policy, and provide an algorithmic solution, reducing the schedulability problem to a reachability problem for timed automata.

Ptolemy‡is an open-source and extensible modelling and simulation framework. It offers heterogeneous modeling capabilities by allowing different models of computation, both untimed and timed, to be composed hierarchically in an arbitrary fashion. This paper proposes a formal semantics for Ptolemy that is modular in the sense that atomic actors and their compositions are treated in a unified way. In particular, all actors conform to an executable interface that contains four functions: fire (produce outputs given current state and inputs); postfire (update state instantaneously); deadline (how much time the actor is willing to let elapse); and time-update (update the state with the passage of time). Composite actors are obtained using composition operators that in Ptolemy are called directors. Different directors realise different models of computation. In this paper, we formally define the directors for the following models of computation: synchronous- reactive, discrete event, continuous time, process networks and modal models.

Hierarchical SDF models are not compositional: a composite SDF actor cannot be represented as an atomic SDF actor without loss of information that can lead to rate inconsistency or deadlock. Motivated by the need for incremental and modular code generation from hierarchical SDF models, we introduce in this paper DSSF profiles. DSSF (Deterministic SDF with Shared FIFOs) forms a compositional abstraction of composite actors that can be used for modular compilation. We provide algorithms for automatic synthesis of non-monolithic DSSF profiles of composite actors given DSSF profiles of their sub-actors. We show how different trade-offs can be explored when synthesizing such profiles, in terms of compactness (keeping the size of the generated DSSF profile small) versus reusability (maintaining necessary information to preserve rate consistency and deadlock-absence) as well as algorithmic complexity. We show that our method guarantees maximal reusability and report on a prototype implementation.

This session is dedicated to Paul Caspi. It is made of five talks, each of them addressing one aspect of Paul Caspi's contributions to the development of safe embedded software and systems: synchronous languages and models, the implementation of synchronous languages, the relation between functional and synchronous languages, the relation between continuous and discrete models, and the definition of embedded software and systems master curricula. This session is only a selection of recent work; Paul Caspi also worked on dependability and fault-tolerance, code distribution, and formal verification with theorem provers.

Many fuel systems for diesel engines are developed with the help of commercial one-dimensional computational fluid dynamics (1D CFD) solvers that model and simulate the behavior of fluid flow through the interconnected pipes off-line. This paper presents a novel framework to evaluate 1D CFD models in real time on an FPGA. This improves fuel pressure estimation and closes the loop on fuel delivery, allowing for a cleaner and more efficient engine. The real-time requirements of the models are defined by the physics and geometry of the problem being solved. In this framework, the interconnected pipes are partitioned into individual sub-volumes that compute their pressure and flow rate every time step based upon neighboring values. We use timing-based synchronization and multiple Precision Timed (PRET) processor cores to ensure the real-time constraints are met. Leveraging the programmability of FPGAs, we use a configurable heterogeneous architecture to save hardware resources. Several examples are presented along with the implementation results after place and route for a Xilinx Virtex 6 FPGA. The results demonstrate the resource savings and scalability of our framework, confirming the feasibility of our approach -- solving 1D CFD models in real time on FPGAs.

We contend that repeatability of execution times is crucial to the validity of testing of real-time systems. However, computer architecture designs fail to deliver repeatable timing, a consequence of aggressive techniques that improve average-case performance. This paper introduces the Precision-Timed ARM (PTARM), a precision-timed (PRET) microarchitecture implementation that exhibits repeatable execution times without sacrificing performance. The PTARM employs a repeatable thread-interleaved pipeline with an exposed memory hierarchy, including a repeatable DRAM controller. Our benchmarks show an improved throughput compared to a single-threaded in-order five-stage pipeline, given sufficient parallelism in the software.

Ptides, a programming model for distributed real-time embedded systems, was proposed previously. In this work, we focus on a work flow that applies Ptides in a single-CPU environment using model-based design techniques. Our work flow starts with a programming environment where a real-time application is expressed as a Ptides model. The model captures both the functionality of the system and the desired timing of interactions with the environment. The Ptides simulator supports simulation of both of these aspects. Once the designer is satisfied with the design, a code generator can be used to glue together the application code with a real-time operating system called PtidyOS. To ensure the responsiveness of the real-time program, PtidyOS's scheduler combines Ptides semantics with the earliest-deadline-first policy. To minimize scheduling overhead associated with context switching, PtidyOS uses a single stack for event scheduling and execution, while still enabling event preemptions. We demonstrate the Ptides work flow through a motion control application. The automatically generated code running on PtidyOS is compared with a manual C implementation running on bare silicon. We discuss the trade offs in functionality and performance between these two implementations.

This paper focuses on the challenges of modeling cyber–physical systems (CPSs) that arise from the intrinsic heterogeneity, concurrency, and sensitivity to timing of such systems. It uses a portion of an aircraft vehicle management system (VMS), specifically the fuel management subsystem, to illustrate the challenges, and then discusses technologies that at least partially address the challenges. Specific technologies described include hybrid system modeling and simulation, concurrent and heterogeneous models of computation, the use of domain-specific ontologies to enhance modularity, and the joint modeling of functionality and implementation architectures.

Real-time embedded software today is commonly built using programming abstractions with little or no temporal semantics. This paper addresses this problem by presenting a programming model called programming temporally integrated distributed embedded systems (PTIDES) that serves as a coordination language for model-based design of distributed real-time embedded systems. Specifically, the paper describes the principles of PTIDES, which leverages network time synchronization to provide a determinate distributed real-time semantics. We show how PTIDES can function as a coordination language, orchestrating components that may be designed and specified using different formalisms. We show the use of this environment in the design of interesting and practical cyber-physical systems, such as a power plant control system.

Multiprocessing architectures provide hardware for executing multiple tasks simultaneously via techniques such as simultaneous multithreading and symmetric multiprocessing. The problem addressed by this paper is that even when tasks that are executing concurrently do not communicate, they may interfere by affecting each others' timing. For cyber-physical system applications, such interference can nullify many of the advantages offered by parallel hardware and can enormously complicate synthesis of software from models. This paper examines what changes need to be made at lower levels of abstraction to support temporal isolation for effective software synthesis. We discuss techniques at the microarchitecture level, in the memory hierarchy, in on-chip communication, and in the instruction-set architecture that can facilitate temporal isolation.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

Embedded systems must interact with their real-time environment in a timely and dependable fashion. Most embedded-systems architectures and design processes consider "non-functional" properties such as time, energy, and reliability as an afterthought, when functional correctness has (hopefully) been achieved. As a result, embedded systems are often fragile in their real-time behaviour, and take longer to design and test than planned. Several techniques have been proposed to make real-time embedded systems more robust, and to ease the process of designing embedded systems:

Complex systems demand diversity in the modeling mechanisms. This "roadmap" paper prescribes an approach to modeling based on concurrent communicating components actors), where a diversity of orchestration strategies govern the execution and interaction of the components.The prescribed approach has been extensively explored in the Ptolemy Project, but as yet is not widely deployed in engineering practice. The approach achieves interaction between diverse models using an abstract semantics, which is a deliberately incomplete semantics that cannot by itself define a useful modeling framework. It instead focuses on the interactions between diverse models, reducing the nature of those interactions to a minimum that achieves a well-defined composition. The actor semantics is an abstract semantics that can handle many heterogeneous models that are built today, and some that are not common today. The actor abstract semantics and many concrete semantics are implemented in Ptolemy II, an open-source software framework.

In embedded software, there are many reasons to include concepts from the problem domain during design. Not only does doing so make the software more comprehensible to those with domain understanding, it also becomes possible to check that the software conforms to correctness criteria expressed in the domain of interest. Here we present a unified framework that enables users to create ontologies representing arbitrary domains of interest and analyses over those domains. These analyses may then be run against software specifications, encapsulated as models, checking that they are sound with respect to the given ontology. Our approach is general, in that the framework is agnostic to the semantic meaning of the ontologies that it uses and does not privilege the example ontologies that we present here. Where practical use-cases and principled theory exist, we provide for the expression of certain patterns of infinite ontologies. In this paper we present two patterns of infinite ontologies: those containing values, and those containing ontologies recursively. We show how these two patterns map to use cases of unit systems and structured data types, and show how these are applicable to cyber-physical systems examples drawn from automotive and avionic domains. Despite the range of ontologies and analyses that we present here, we see user-built ontologies as a key feature of our approach.

We review an introductory course in embedded systems that characterizes embedded systems not by resource constraints, but rather by interactions with the physical world. This course teaches students the basics of models, analysis tools, and design for embedded systems. Traditional undergraduate courses in embedded systems focus on ad-hoc engineering practices and the use of existing modeling techniques, often omitting critical analysis and meta-modeling; we emphasize model-based design of embedded and cyber-physical systems. Students learn how to model the physical world with continuous time differential equations, and how to model computation using logic and discrete models such as state machines. Students evaluate these modeling techniques through the use of meta-modeling, illuminating the interplay of practical design with formal models of systems that incorporate both physical dynamics and computation. Students learn formal techniques to specify and verify desired behavior. A combination of structured labs and design projects solidifies these concepts when applied to the design of embedded and cyber-physical systems with real-time and concurrent behaviors.

Model-based design is a powerful design technique for cyber-physical systems, but too often literature assumes knowledge of a methodology without reference to an explicit design process, instead focusing on isolated steps such as simulation, software synthesis, or verification. We combine these steps into an explicit and holistic methodology for model-based design of cyber-physical systems from abstraction to architecture, and from concept to realization. We decompose model-based design into ten fundamental steps, describe and evaluate an iterative design methodology, and evaluate this methodology in the development of a cyber-physical system.

Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces.

This paper argues that cyber-physical systems present a sub-stantial intellectual challenge that requires changes in both theories of computation and dynamical systems theory. The CPS problem is not the union of cyber and physical problems, but rather their intersection, and as such it demands models that embrace both. Two complementary approaches are identified: cyberizing the physical (CtP) means to endow physical subsystems with cyber-like abstractions and interfaces; and physicalizing the cyber (PtC) means to endow software and network components with abstractions and interfaces that represent their dynamics in time.

In the past, model-based development focused mainly on functional and structural aspects of the system to be developed. Recently, several approaches to include timing aspects have been suggested. However, these approaches are typically applied in later development phases. Models specifying the requirements with respect to timing without focusing on a specific solution are missing. For example, few models support the specification of the allowed jitter of a system. In this paper, we identify requirements on languages for modeling the desired timing behavior of hard and soft real-time systems by analyzing different application domains. Based on these results, we evaluate existing approaches with respect to their suitability and present a suitable approach. Finally, this paper describes the application of the suggested approach in the context of an example from the automation domain.

Many modeling techniques for embedded systems focus on events that occur in time and the causality relationships between them. Event-oriented modeling complements class-oriented, object-oriented, actor-oriented and state-oriented approaches. To facilitate event-oriented modeling, we have extended an older established model called event graphs to define new model of computation that we call Ptera (Ptolemy event relationship actors). Ptera is appropriate for modeling complex discrete-event systems. A key capability is that Ptera models conform with an actor abstract semantics that permits hierarchical composition with other models of computation such as discrete-event actors, dataflow, process networks and finite state machines. This enables their use in complex system design, where not every aspect of the system is best described with event-oriented modeling.

Deploying real-time control systems software on multiprocessors requires distributing tasks on multiple processing nodes and coordinating their executions using a protocol. One such protocol is the discrete-event (DE) model of computation. In this paper, we investigate distributed discrete-event (DE) with null-message protocol (NMP) on a multicore system for real-time control software. We illustrate analytically and experimentally that even with the null-message deadlock avoidance scheme in the protocol, the system can deadlock due to inter-core message dependencies. We identify two central reasons for such deadlocks: 1) the lack of an upper-bound on packet transmission rates and processing capability, and 2) an unknown upper-bound on the communication network delay. To address these, we propose using architectural features such as timing control and real-time network-on-chips to prevent such message-dependent deadlocks. We employ these architectural techniques in conjunction with a distributed DE strategy called PTIDES for an illustrative car wash station example and later follow it with a more realistic tunnelling ball device application.

Ptolemy II is a component-based design and modeling environment. It has a polymorphic type system that supports both base types and structured types, such as arrays, records, and unions. This paper presents the extensions to the base type system that support structured types. In the base type system, all the types are organized into a type lattice, and type constraints in the form of inequalities can be solved efficiently over the lattice. We take a hierarchical and granular approach to add structured types to the lattice and extend the format of inequality constraints to allow arbitrary nesting of structured types. We also analyze the convergence of the constraint-solving algorithm on an infinite lattice after structured types are added. To show the application of structured types, we present two Ptolemy II models that have direct real-world background. The first one describes the workflow of a charity organization, and the second one implements part of the IEEE 802.11 specification. These models make extensive use of record and union types to represent structured information. © 2009 Wiley Periodicals, Inc.

In this paper we extend the work of Alfaro, Henzinger et al. on interface theories for component-based design. Existing interface theories often fail to capture functional relations between the inputs and outputs of an interface. For example, a simple synchronous interface that takes as input a number n ≥ 0 and returns, at the same time, as output n + 1, cannot be expressed in existing theories. In this paper we provide a theory of relational interfaces, where such input-output relations can be captured. Our theory supports synchronous interfaces, both stateless and stateful. It includes explicit notions of environments and pluggability, and satisfies fundamental properties such as preservation of refinement by composition, and characterization of pluggability by refinement. We achieve these properties by making reasonable restrictions on feedback loops in interface compositions.

This paper argues that repeatable timing is more important and more achievable than predictable timing. It describes microarchitecture approaches to pipelining and memory hierarchy that deliver repeatable timing and promise comparable or better performance compared to established techniques. Specifically, threads are interleaved in a pipeline to eliminate pipeline hazards, and a hierarchical memory architecture is outlined that hides memory latencies.

The Flexotask system claims to enable implementation of both real-time applications and real-time schedulers in a Java Virtual Machine using an actors-like model. The PTIDES model is an actors-like model that claims to deliver precise control over end-to-end latencies in a complex real-time system. The present work jointly investigates both claims by (1) implementing several PTIDES-based schedulers as Flexotask scheduler plugins, and (2) using the resulting system to implement a new reactive control program for a simulation of the JAviator. We present results from the realistic JAviator control application and also from synthetic benchmarks designed to shed light on the differences between the several PTIDES schedulers we implemented.

We define a family of execution policies for a programming model called PTIDES (programming temporally integrated distributed embedded systems). A PTIDES application (factory automation, for example) is given as a discrete-event (DE) model of a distributed real-time system that includes sensors and actuators. The time stamps of DE events are bound to physical time at the sensors and actuators, turning the DE model into an executable specification of the system with explicit real-time constraints. This paper first defines a general execution strategy that conforms to the DE semantics, and then specializes this strategy to give practical, implementable and distributed policies. Our policies leverage network time synchronization to eliminate the need for null messages, allow independent events to be processed out of time stamp order, thus increasing concurrency and making more models feasible (w.r.t. real-time constraints), and improve fault isolation in distributed systems. The policies are given in terms of a safe to process predicate on events that depends on the time stamp of the events and the local notion of physical time. In a simple case we show how to statically check whether program execution satisfies timing constraints.

Actor-oriented components emphasize concurrency and temporal semantics and are used for modeling and designing embedded software and hardware. Actors interact with one another through ports via a messaging schema that can follow any of several concurrent semantics. Domain-specific actor-oriented languages and frameworks are common (Simulink, LabVIEW, SystemC, etc.). However, they lack many modularity and abstraction mechanisms that programmers have become accustomed to in object-oriented components, such as classes, inheritance, interfaces, and polymorphism, except as inherited from the host language. This article shows a form that such mechanisms can take in actor-oriented components, gives a formal structure, and describes a prototype implementation. The mechanisms support actor-oriented class definitions, subclassing, inheritance, and overriding. The formal structure imposes structural constraints on a model (mainly the “derivation invariant”) that lead to a policy to govern inheritance. In particular, the structural constraints permit a disciplined form of multiple inheritance with unambiguous inheritance and overriding behavior. The policy is based formally on a generalized ultrametric space with some remarkable properties. In this space, inheritance is favored when actors are “closer” (in the generalized ultrametric), and we show that when inheritance can occur from multiple sources, one source is always unambiguously closer than the other.

In a hard real-time embedded system, the time at which a result is computed is as important as the result itself. Modern processors go to extreme lengths to ensure their function is predictable, but have abandoned predictable timing in favor of average-case performance. Real-time operating systems provide timing-aware scheduling policies, but without precise worst-case execution time bounds they cannot provide guarantees.

We have previously proposed PTIDES (programming temporally integrated distributed embedded systems), a discrete-event framework that binds realtime with model time at sensors, actuators, and network interfaces. In this experimental effort we focus on performance issues and tradeoffs in PTIDES implementation. We address event processing performance with respect to other distributed discrete event approaches that can be applied in a similar setting. The procedure is experimentally evaluated on a distributed setup with standard software and networking components.

Most common real-time embedded programming languages provide a means to specify functionality; however, they have few constructs to specify precise timing constraints. LabVIEW is one example of a graphical programming language that supports timing specifications in the form of timed-loops. In this work, we present a plug-in for LabVIEW Embedded that maps the LabVIEW G graphical programming language and its timing specifications to the PREcision Timed machine (PRET), an architecture that exposes timing instructions in its instruction set architecture. We demonstrate the use of the plug-in with a simple producer/consumer example that uses timing to enforce synchronization.

Computation, as expressed in modern programming languages, obscures many resource management problems. Memory is provided without bound by stacks and heaps. Power and energy consumption are not the concern of a programmer. Even when these resource management problems are important, there is no way to talk about them within the semantics of a programming language. Time, however, is not quite like these other resources. First, barring metaphysical discourse, it is genuinely unbounded. To say that "the available time per unit time is bounded" is tautological, yet this is effectively what people say when they manage it as a bounded resource. Second, time gets expended whether we use it or not. It cannot be conserved and saved for later. This is true up to a point with, say, battery power. Batteries leak, so their power cannot be indefinitely conserved, but designers rarely optimize a system to use as much battery power before it leaks away as they can. Yet that is what they do with time.

Cyber-Physical Systems (CPS) are integrations of computation and physical processes. Embedded computers and networks monitor and control the physical processes, usually with feedback loops where physical processes affect computations and vice versa. The economic and societal potential of such systems is vastly greater than what has been realized, and major investments are being made worldwide to develop the technology. There are considerable challenges, particularly because the physical components of such systems introduce safety and reliability requirements qualitatively different from those in general- purpose computing. Moreover, physical components are qualitatively different from object-oriented software components. Standard abstractions based on method calls and threads do not work. This paper examines the challenges in designing such systems, and in particular raises the question of whether today's computing and networking technologies provide an adequate foundation for CPS. It concludes that it will not be sufficient to improve design processes, raise the level of abstraction, or verify (formally or otherwise) designs that are built on today's abstractions. To realize the full potential of CPS, we will have to rebuild computing and networking abstractions. These abstractions will have to embrace physical dynamics and computation in a unified way.

We build on PTIDES, a programming model for distributed embedded systems that uses discrete-event (DE) models as program specifications. PTIDES improves on distributed DE execution by allowing more concurrent event processing without backtracking. This paper discusses the general execution strategy for PTIDES, and provides two feasible implementations. This execution strategy is then extended with tolerance for hardware errors. We take a program transformation approach to automatically enhance DE models with incremental checkpointing and state recovery functionality. Our fault tolerance mechanism is lightweight and has low overhead. It requires very little human intervention. We incorporate this mechanism into PTIDES for efficient execution of fault- tolerant real-time distributed DE systems.

We consider concurrent models of computation where “actors” (components that are in charge of their own actions) communicate by exchanging messages. The interfaces of actors principally consist of “ports,” which mediate the exchange of messages. Actor-oriented architectures contrast with and complement object-oriented models by emphasizing the exchange of data between concurrent components rather than transformation of state. Examples of such models of computation include the classical actor model, synchronous languages, data-flow models, process networks, and discrete-event models. Many experimental and production languages used to design embedded systems are actor oriented and based on one of these models of computation. Many of these models of computation benefit considerably from having access to causality information about the components. This paper augments the interfaces of such components to include such causality information. It shows how this causality information can be algebraically composed so that compositions of components acquire causality interfaces that are inferred from their components and the interconnections. We illustrate the use of these causality interfaces to statically analyze timed models and synchronous language compositions for causality loops and data-flow models for deadlock. We also show that that causality analysis for each communication cycle can be performed independently and in parallel, and it is only necessary to analyze one port for each cycle. Finally, we give a conservative approximation technique for handling dynamically changing causality properties.

Patterson and Ditzel [12] did not invent reduced instruction set computers (RISC) in 1980. Earlier computers all had reduced instruction sets. Instead, they argued that trends in computer architecture had gotten off the sweet spot, and that by dropping back a few years and forking a new version of architectures, leveraging what had been learned, they could get better computers by employing simpler instruction sets.

This paper gives a semantics for discrete-event (DE) models that generalizes that of synchronous/reactive (SR) languages, and a continuous-time (CT) semantics that generalizes the DE semantics. It shows that all three semantic models can be used in actor-oriented composition languages, and that despite the fact that CT is the most general, there are good reasons for using each of the more specialized semantics. Moreover, because of the generalization relationship between them, these three models of computation (MoCs) compose hierarchically in arbitrary order. We describe a design system that supports arbitrary combinations of these three MoCs, leveraging the actor abstract semantics of Ptolemy II.

Discrete-event (DE) models are formal system specifications that have analysable deterministic behaviors. Using a global, consistent notion of time, DE components communicate via time-stamped events. DE models have primarily been used in performance modeling and simulation, where time stamps are a modeling property bearing no relationship to real time during execution of the model. In this paper, we extend DE models with the capability of relating certain events to physical time. We propose a programming model, called PTIDES (programming temporally integrated distributed embedded systems), which has DE semantics, but with carefully chosen relations between model time and real time. Key to making this model effective is to ensure that constraints that guarantee determinacy in the semantics are preserved at runtime. To accomplish this, we give a distributed execution strategy that obeys DE semantics without the penalty of totally ordered executions based on time stamps. Our technique relies on having a distributed common notion of time, known to some precision. Based on causality analysis of DE models, we define relevant dependency and relevant orders to enable out-of-order execution without compromising determinism and without requiring backtracking

In this paper, we consider a concurrent model of computation called dataflow, where components (actors) communicate via streams of data tokens. Dataflow semantics has been adopted by experimental and production languages used to design embedded systems. The execution of a dataflow actor is enabled by the availability of its input data. One important question is whether a dataflow model will deadlock (i.e., actors cannot execute due to a data dependency loop). Deadlock in many cases can be determined, although it is generally not decidable. We develop a causality interface for dataflow actors based on the general framework we introduced in [1]and show how this causality information can be algebraically composed so that composition of components acquire causality interfaces that are inferred from their components and the interconnections. We illustrate the use of these causality interfaces to statically analyze for deadlock.

Abstract Many scientific disciplines are now data and information driven, and new scientific knowledge is often gained by scientists putting together data analysis and knowledge discovery ‘pipelines’. A related trend is that more and more scientific communities realize the benefits of sharing their data and computational services, and are thus contributing to a distributed data and computational community infrastructure (a.k.a. ‘the Grid’). However, this infrastructure is only a means to an end and ideally scientists should not be too concerned with its existence. The goal is for scientists to focus on development and use of what we call scientific workflows . These are networks of analytical steps that may involve, e.g., database access and querying steps, data analysis and mining steps, and many other steps including computationally intensive jobs on high‐performance cluster computers. In this paper we describe characteristics of and requirements for scientific workflows as identified in a number of our application projects. We then elaborate on Kepler, a particular scientific workflow system, currently under development across a number of scientific data management projects. We describe some key features of Kepler and its underlying Ptolemy II system, planned extensions, and areas of future research. Kepler is a community‐driven, open source project, and we always welcome related projects and new contributors to join. Copyright © 2005 John Wiley & Sons, Ltd.

We present an interface theory based approach to static analysis of actor models. We first introduce a new interface theory, which is based on interface automata, and which is capable of counting with numbers. Using this new interface theory, we can capture temporal and quantitative aspects of an actor interface as well as an actor's token exchange rate. We will show, how to extract this information from actors written in the cal actor language (CAL), and we also present a method to capture the interface information as well as the structure of dataflow models into an interface automaton. This automaton acts as glue between the automata of all actors in the model, and by successfully composing all actor automata with it, we can prove interface compatibility of all actors with the composition framework. After successful composition, the resulting automaton will contain information that can be used for further static analysis of the composite actor model.

We are announcing the first release of Viptos (Visual Ptolemy and TinyOS), an integrated graphical development and simulation environment for TinyOS-based wireless sensor networks. Viptos allows developers to create block and arrow diagrams to construct TinyOS programs from any standard library of nesC/TinyOS components. The tool automatically transforms the diagram into a nesC program that can be compiled and downloaded from within the graphical environment onto any TinyOS-supported target hardware. In particular, Viptos includes the full capabilities of VisualSense [1], which can model communication channels, networks, and non-TinyOS nodes. This release of Viptos is compatible with nesC 1.2 and includes tools to harvest existing TinyOS components and applications and convert them into a format that can be displayed as block (and arrow) diagrams and simulated.Viptos is based on TOSSIM and Ptolemy II. TOSSIM is an interrupt-level simulator for TinyOS programs. It runs actual TinyOS code but provides software replacements for the simulated hardware and models network interaction at the bit or packet level. Ptolemy II is a graphical software system for modeling, simulation, and design of concurrent, real-time, embedded systems. Ptolemy II focuses on assembly of concurrent components with well-defined models of computation that govern the interaction between components. VisualSense is a Ptolemy II environment for modeling and simulation of wireless sensor networks at the network level.Viptos provides a bridge between VisualSense and TOSSIM by providing interrupt-level simulation of actual TinyOS programs, with packet-level simulation of the network, while allowing the developer to use other models of computation available in Ptolemy II for modeling various parts of the system. While TOSSIM only allows simulation of homogeneous networks where each node runs the same program, Viptos supports simulation of heterogeneous networks where each node may run a different program. Viptos simulations may also include non-TinyOS-based wireless nodes. The developer can easily switch to different channel models and change other parts of the simulated environment, such as creating models to generate simulated traffic on the wireless network.Viptos inherits the actor-oriented modeling environment of Ptolemy II, which allows the developer to use different models of computation at each level of simulation. At the lowest level, Viptos uses the discrete-event scheduler of TOSSIM to model the interaction between the CPU and TinyOS code that runs on it. At the next highest level, Viptos uses the discrete-event scheduler of Ptolemy II to model interaction with mote hardware, such as the radio and sensors. This level is then embedded within VisualSense to allow modeling of the wireless channels to simulate packet loss, corruption, delay, etc. The user can also model and simulate other aspects of the physical environment including those detected by the sensors (e.g., light, temperature, etc.), terrain, etc.At IPSN in April 2005, we demonstrated a pre-release developmental version of Viptos with two simple applications. The first was a single node sensing application that displayed the value of the light sensor on the LEDs. The second was a two node send and receive application that transmitted the value of the light sensor on the first node to the second node. This release version of Viptos supports more sophisticated applications, such as multi-node routing, and demonstrates some of the more advanced features described in this abstract.

This paper describes a modeling and simulation framework called VisualSense for wireless sensor networks that builds on and leverages Ptolemy II. This framework supports actor-oriented definition of sensor nodes, wireless communication channels, physical media such as acoustic channels, and wired subsystems. The software architecture consists of a set of base classes for defining channels and sensor nodes, a library of subclasses that provide certain specific channel models and node models, and an extensible visualization framework. Custom nodes can be defined by subclassing the base classes and defining the behavior in Java or by creating composite models using any of several Ptolemy II modeling environments. Custom channels can be defined by subclassing the WirelessChannel base class and by attaching functionality defined in Ptolemy II models.

Actor-oriented languages provide a component composition methodology that emphasizes concurrency. The interfaces to actors are parameters and ports (vs. members and methods in object-oriented languages). Actors interact with one another through their ports via a messaging schema that can follow any of several concurrent semantics (vs. procedure calls, with prevail in OO languages). Domain-specific actor-oriented languages and frameworks are common (e.g. Simulink, LabVIEW, and many others). However, they lack many of the modularity and abstraction mechanisms that programmers have become accustomed to in 00 languages, such as classes, inheritance, interfaces, and polymorphism. This extended abstract shows the form that such mechanisms might take in AO languages. A prototype of these mechanisms realized in Ptolemy II is described.

This paper presents a unified approach to analyzing patterns of reconfiguration in dataflow graphs. The approach is based on hierarchical decomposition of the structure and execution of a dataflow model. In general, reconfiguration of any part of the system might occur at any point during the execution of a model. However, arbitrary reconfiguration must often be restricted, given the constraints of particular dataflow models of computation or modeling constructs. For instance, the reconfiguration of parameters that influence dataflow scheduling or soundness of data type checking must be more heavily restricted. The paper first presents an abstract mathematical model that is sufficient to represent the reconfiguration of many types of dataflow graphs. Using this model, a behavioral type theory is developed that bounds the points in the execution of a model when individual parameters can be reconfigured. This theory can be used to efficiently check semantic constraints on reconfiguration, enabling the safe use of parameter reconfiguration at all levels of hierarchy.

Abstract. Interface automata [deH01] have been introduced as an interface theory [deH01a] capable of functioning as a behavioral type system. Behavioral type systems describe dynamic properties of components and their compositions. Like traditional (data) type systems, behavioral type systems can be used to check compatibility of components. In this paper, we use interface automata to devise a behavioral type system for Ptolemy II, leveraging the contravariant and optimistic properties of interface automata to achieve behavioral subtyping and polymorphism. Ptolemy II is a software framework supporting concurrent component composition according to diverse models of computation. In this paper, we focus on representing the communication protocols used in component communication within the behavioral type system. In building this type system, we identify two key limitations in interface automata formalisms; we overcome these limitations with two extensions, transient states and projection automata. In addition to static type checking, we also propose to extend the use of interface automata to the on-line reflection of component states and to run-time type checking, which enable dynamic component creation, morphing application structure, and admission control. We discuss the trade-offs in the design of behavioral type systems.

Modern embedded computing systems tend to be heterogeneous in the sense of being composed of subsystems with very different characteristics, which communicate and interact in a variety of ways-synchronous or asynchronous, buffered or unbuffered, etc. Obviously, when designing such systems, a modeling language needs to reflect this heterogeneity. Today's modeling environments usually offer a variant of what we call amorphous heterogeneity to address this problem. This paper argues that modeling systems in this manner leads to unexpected and hard-to-analyze interactions between the communication mechanisms and proposes a more structured approach to heterogeneity, called hierarchical heterogeneity, to solve this problem. It proposes a model structure and semantic framework that support this form of heterogeneity, and discusses the issues arising from heterogeneous component interaction and the desire for component reuse. It introduces the notion of domain polymorphism as a way to address these issues.

Article A code generation framework for Java component-based designs Share on Authors: Jeff Tsay BDTI, 2107 Dwight Way, Berkeley, CA BDTI, 2107 Dwight Way, Berkeley, CAView Profile , Christopher Hylands EECS, UC Berkeley, Cory Hall, Berkeley, CA EECS, UC Berkeley, Cory Hall, Berkeley, CAView Profile , Edward Lee EECS, UC Berkeley, Cory Hall, Berkeley, CA EECS, UC Berkeley, Cory Hall, Berkeley, CAView Profile Authors Info & Claims CASES '00: Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systemsNovember 2000 Pages 18–25https://doi.org/10.1145/354880.354884Online:01 November 2000Publication History 5citation565DownloadsMetricsTotal Citations5Total Downloads565Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The design and design automation of embedded systems is rapidly emerging as a research area in its own right. It draws from several traditional areas of study such as system specification, modeling and analysis; computer architecture and micro-architecture; as well as compilers and operating systems. However, the embedded domain adds some interesting twists in terms of tighter problem constraints that demand a fresh look at even these traditional areas. In addition, there are several emerging EDA areas such as design reuse and integration of systems on a chip that are critical to the study of embedded systems. These aspects are not typically covered by computer engineering and EDA curricula. This panel addresses the challenges associated with the educational issues in embedded systems design and design automation. The panelists will examine issues in including embedded systems in university curricula, as well as in setting up research programs that are crucial for the education of graduate students.

We propose a computationally efficient version of the decision feedback equalizer (DFE) and compare its performance with the conventional DFE. The proposed equalizer requires fewer taps than the conventional one. This reduces the computational load proportionally and leads to faster adaptation. Identical performance of the two structures in terms of probability of error is also demonstrated using both theoretical and simulation results.

In his 1962 paper "A Day in the Life of a Student in 2012", Ponte describes the university of 2012 through the eyes of a student. Such a paper may be written to predict the future, to influence changes, or simply to highlight shortcomings and opportunities in the present. His motivation seems to be prediction, so it is best to view the paper in that light. Ponte's prophecy still has over a decade to play out. One vision not yet true, but likely, is the obsolescence of the lecture hall-his Professor Faraway gives recorded, masterful lectures that are broadcast to students, who gather in teams of 30 around a task master. Indeed, the lecture hall does seem antiquated today-it may be replaced by a learning hall, where faculty and students gather physically to engage in a discussion and projects, supplemented by a multimedia textbook, which students use to self study. One-way lectures can be satisfactorily replaced by store and playback, with a substantial improvement in productivity, but what cannot be readily displaced is an intellectual give-and-take discussion among faculty and students, accompanied by friendship and community building. Thus, Ponte's task masters and closely knit group projects seem likely to arise together with multimedia study materials. We now offer a new essay in the spirit of his. Our objective is not so much prediction, but rather to speak to our own era, using a speculative view of the future to point out today's shortcomings and opportunities. Like Ponte, our essay reflects both our hopes and our fears for the future. Reflecting the greater pace of change today, this vision is a more radical departure than Ponte's. Fifty years from now, this essay will probably be only mildly amusing, since the details of our prediction are unlikely to reflect reality. A more realistic goal is to influence the course of education today.

This paper studies the semantics of hierarchical finite state machines (FSM's) that are composed using various concurrency models, particularly dataflow, discrete-events, and synchronous/reactive modeling. It is argued that all three combinations are useful, and that the concurrency model can be selected independently of the decision to use hierarchical FSM's. In contrast, most formalisms that combine FSM's with concurrency models, such as statecharts (and its variants) and hybrid systems, tightly integrate the FSM semantics with the concurrency semantics. An implementation that supports three combinations is described.

We give a denotational framework (a "meta model") within which certain properties of models of computation can be compared. It describes concurrent processes in general terms as sets of possible behaviors. A process is determinate if, given the constraints imposed by the inputs, there are exactly one or exactly zero behaviors. Compositions of processes are processes with behaviors in the intersection of the behaviors of the component processes. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. Synchronous processes have only synchronous signals as behaviors. Strict causality (in timed tag systems) and continuity (in untimed tag systems) ensure determinacy under certain technical conditions. The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, Petri nets, and discrete-event systems.

This paper reviews a set of techniques for compiling dataflow-based, graphical programs for digital signal processing (DSP) applications into efficient implementations on programmable digital signal processors. This is a critical problem because programmable digital signal processors have very limited amounts of on-chip memory and the speed power, and financial cost penalties for using off-chip memory are often prohibitively high for the types of applications, typically embedded systems, in which these processors are used. The compilation techniques described in this paper are developed for the synchronous dataflow model of computation, a model that has found widespread use for specifying and prototyping DSP systems.

Integer-Controlled Dataflow (IDF) and its code generation applications in Ptolemy are presented. In IDF graphs, which specify data processing systems, data token flow is controlled by integer control tokens and states of actors at run-time. The firing order of actors (schedule) is determined at compile-time, however, the actors are conditionally activated at run-time. This static schedule contributes to effective simulation of systems. IDF supports code generation. This enables code generation from program graphs that include conditional jumps, loops and repetitions, and greatly improves the practical usability of the program synthesis in Ptolemy.

This paper addresses the design of reactive real-time embedded systems. Such systems are often heterogeneous in implementation technologies and design styles, for example by combining hardware application-specific integrated circuits (ASICs) with embedded software. The concurrent design process for such embedded systems involves solving the specification, validation, and synthesis problems. We review the variety of approaches to these problems that have been taken.

Resynchronization is a post-optimization for static multiprocessor schedules in which extraneous synchronization operations are introduced in such a way that the number of original synchronizations that consequently become redundant significantly exceeds the number of additional synchronizations. Redundant synchronizations are synchronization operations whose corresponding sequencing requirements are enforced completely by other synchronizations in the system. The amount of run-time overhead required for synchronization can be reduced significantly by eliminating redundant synchronizations. However, since additional serialization is imposed by the new synchronizations resynchronization can produce significant increase in latency. This paper addresses the problem of computing an optimal resynchronization (one that results in the lowest average rate at which synchronization operations have to be performed) among all resynchronizations that do not increase the latency beyond a prespecified upper bound L/sub max/. Our study is based on the context of self-timed execution of iterative data flow programs, which is an implementation model that has been applied extensively for digital signal processing systems.

We are developing a sophomore course to serve as a first course in electrical engineering. The course focuses on discrete-time systems. Its goal is to give students an intuitive understanding of concepts such as sinusoids, frequency domain, sampling, aliasing, and quantization. In the laboratory, students build simulations and real-time systems to test these ideas. By using a combination of high-level and DSP assembly languages, the students experiment with a variety of views into the representation, design, and implementation of systems. The students are exposed to a digital style of implementation based on programming both desktop and embedded processors.

Multidimensional synchronous dataflow (MDSDF) is a model of computation that has been proposed and implemented for specifying multidimensional multirate signal processing systems such as image and video processing algorithms. The model is an extension of synchronous dataflow (SDF) and has all of the desirable properties of the SDF model such as static schedulability, exposure of data and functional parallelism and a visually pleasing syntax well suited for block diagram signal processing environments such as Ptolemy and Khoros. However, the MDSDF model as specified by Lee (1993) is limited to modeling multidimensional systems sampled on the rectangular lattice. Since some multidimensional systems of practical interest use non-rectangular sampling lattices and non-rectangular multirate operators like hexagonal decimators, models that are capable of representing and simulating such systems are of interest. This paper describes an extension of the MDSDF model that allows signals on arbitrary sampling lattices to be represented, and that allows the use of non-rectangular downsamplers and upsamplers.

We describe a framework that constructs interfaces between simulation tools and real-time prototyping hardware in a high-level DSP synthesis environment. A goal of this work is to abstract the concept of the interface so that customized links are not required between each simulation and hardware engine. To support a new engine, the DSP system designer must define two pairs of communication primitives between the new tool and host workstation. The interface construction mechanism provides incremental compilation of subsystems in a system specification into the high-level DSP synthesis environment. We illustrate this framework with practical examples that have been constructed in Ptolemy.

We give a denotational framework (a meta model) within which certain properties of models of computation can be understood and compared. It describes concurrent processes as sets of possible behaviors. Compositions of processes are given as intersections of their behaviors. The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. Synchronous systems contain synchronous signals. Strict causality (in timed systems) and continuity (in untimed systems) ensure determinacy under certain technical conditions. The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, Petri nets, and discrete-event systems.

We consider the capacity C of a continuous-time channel with frequency response H(f) and additive white Gaussian noise. If H(f)|/sup -2/ behaves like a polynomial of order /spl rho/ at high frequencies, we show that the per-symbol capacity approaches /spl rho//2 nats per channel use at high signal powers. If the receiver uses an ideal zero forcing decision-feedback equalizer (DFE) consisting of a sampled whitened-matched filter followed by a zero-forcing tail canceler that is free of error propagation, the overall system is free of intersymbol interference and has a well-defined capacity C/sub ZF/. By comparing this capacity with the capacity C of the underlying channel, we quantify the loss of information inherent in the tail-canceling operation that typifies zero-forcing DFE and zero-forcing precoding systems. For strictly bandlimited channels, we find that the capacity penalty approaches zero in the limit of large signal power. On the other hand, for nonstrictly bandlimited channels, the asymptotic penalty is nonzero; however, with bandwidth optimization, the asymptotic penalty is at most 0.59 dB, and the asymptotic ratio C/sub ZF//C is at least 93.6%, depending on the asymptotic order /spl rho/ of the channel response.

Synchronization overhead can significantly degrade performance in embedded multiprocessor systems. This paper develops techniques to determine a minimal set of processor synchronizations that are essential for correct execution in an embedded multiprocessor implementation. Our study is based in the context of self-timed execution of iterative dataflow programs; dataflow programming in this form has been applied extensively, particularly in the context of signal processing software. Self-timed execution refers to a combined compile-time/run-time scheduling strategy in which processors synchronize with one another only based on inter-processor communication requirements, and thus, synchronization of processors at the end of each loop iteration does not generally occur. We introduce a new graph-theoretic framework, based on a data structure called the synchronization graph, for analyzing and optimizing synchronization overhead in self-timed, iterative dataflow programs. We also present an optimization that involves converting a synchronization graph that is not strongly connected into a strongly connected graph.

A typical path in learning digital signal processing begins at the theoretical end and progresses toward the practical constraints imposed by implementation in hardware or software. On this path, the student would learn how to convert mathematical theory into algorithms and then algorithms into efficient implementations. In this paper, we first summarize the electronic courseware we have already developed in Mathematica, MATLAB, and Ptolemy to teach DSP theory, algorithms, and implementation, respectively. Then, we discuss ways to integrate our efforts to help students discover the connections between these topics.

System-level design is characterized by a behavioral specification and heterogeneous hardware/software implementations. Exploring the design space is essential for good design. Specifying and managing complex design flows, tracking dependencies and tool invocations, and maintaining consistency of design data and flows are key issues that enable efficient design space exploration. In order to manage the complexity of this design process, an infrastructure that manages these issues, transparent to the user, is presented. These concepts have been implemented in the Ptolemy environment within a framework called DesignMaker. An example design flow for multiprocessor synthesis is presented in some detail to illustrate the features of DesignMaker. The end objective of the framework is to facilitate a flexible system-level codesign assistant.

The synchronous dataflow model is used in a variety of visual programming environments to describe and design digital signal processing systems. In this paper, we present two main improvements over existing methodologies. Both are concerned with convenient manipulations of multidimensional data. The first describes a systematic method for transposing multidimensional data structures embedded within a one dimensional stream. This enables the use of scalar stream operators for processing multidimensional data. The second shows how higher-order functions combined with visual hierarchy can be used to build intuitive, maintainable, and scalable applications that operate on multidimensional data. These techniques are combined to design a beamforming radar simulation using the Ptolemy simulation environment.

Real-time signal processing applications can be described naturally with dataflow graphs. The systems we consider have a mix of real-time and non-real-time processing, where independent dataflow graphs represent tasks and individual dataflow actors are subtasks. Rate-monotonic scheduling is optimal for fixed-priority, preemptive scheduling of periodic tasks. Priority inheritance protocols extend rate-monotonic scheduling theory to include tasks that contend for exclusive access to shared resources. We show that non-preemptive rate-monotonic scheduling can be viewed as preemptive scheduling where the processor is explicitly considered a shared resource. We propose a dynamic, real-time execution model inspired by multithreaded dataflow architectures.

Discusses a hierarchical scheduling framework to reduce the complexity of scheduling synchronous dataflow (SDF) graphs onto multiple processors. The core of this framework is a clustering technique that reduces the number of actors before expanding the SDF graph into an directed acyclic graph (DAG). The internals of the clusters are then scheduled with uniprocessor SDF schedulers which can optimize for memory usage. The clustering is done in such a manner as to leave ample parallelism exposed for the multiprocessor scheduler. The authors illustrate this framework with a real-time example that has been constructed in Ptolemy.

Since software prototypes of DSP applications are most efficient when their code and data space requirements can be accommodated entirely within the on-chip memory of the target processor it is crucial to employ efficient memory-minimizing compilation techniques in a DSP software prototyping system. In this paper, we introduce two techniques for the combined minimization of code and data when compiling graphical programs that are based on the synchronous dataflow (SDF) model. The first method is a customization to acyclic graphs of a bottom-up technique, called Pairwise Grouping of Adjacent Nodes (PGAN), that was proposed earlier for general SDF graphs. We show that our customization significantly reduces the complexity of the general PGAN algorithm and performs optimally for a certain class of applications. The second approach is a top-down technique, called Recursive Partitioning by Minimum Cuts (RPMC), that is based on a generalized minimum cut operation. From an extensive experimental study, we conclude that RPMC and our customization of PGAN are complementary, and both should be incorporated into SDF-based prototyping environments in which the minimization of memory requirements is important.

The extended partitioning problem is the joint problem of mapping nodes in a precedence graph to hardware or software, and within each mapping, selecting an appropriate implementation for each node. The end-goal is to minimize the hardware area, subject to architectural and performance constraints. This is an NP-complete problem; we present an efficient heuristic called MIBS to solve it. The MIBS (Mapping and Implementation-Bin Selection) algorithm solves the extended partitioning problem by decomposing it into an iterative process consisting of two steps: mapping and implementation-bin selection (IBS). The GCLP (Global Criticality/Local Phase-driven) algorithm computes a mapping by using an adaptive optimization objective at each iteration. This objective is selected on the basis of a global time criticality measure and local optimality measures. The IBS algorithm solves the implementation-bin selection problem. It uses a bin sensitivity measure which correlates the implementation bin motion with the overall hardware area reduction, to determine the implementation bin of a node for a given mapping. Experimental results indicate that the added dimension of design flexibility (offered by implementation bins) can be used effectively in partitioning to reduce the overall area. The MIBS algorithm has O(|N|/sup 3/) complexity, with a solution quality comparable to that of ILP (integer linear programming).

We review a model of computation used in industrial practice in signal processing software environments and experimentally and other contexts. We give this model the name "dataflow process networks," and study its formal properties as well as its utility as a basis for programming language design. Variants of this model are used in commercial visual programming systems such as SPW from the Alta Group of Cadence (formerly Comdisco Systems), COSSAP from Synopsys (formerly Cadis), the DSP Station from Mentor Graphics, and Hypersignal from Hyperception. They are also used in research software such as Khoros from the University of New Mexico and Ptolemy from the University of California at Berkeley, among many others. Dataflow process networks are shown to be a special case of Kahn process networks, a model of computation where a number of concurrent processes communicate through unidirectional FIFO channels, where writes to the channel are nonblocking, and reads are blocking. In dataflow process networks, each process consists of repeated "firings" of a dataflow "actor." An actor defines a (often functional) quantum of computation. By dividing processes into actor firings, the considerable overhead of context switching incurred in most implementations of Kahn process networks is avoided. We relate dataflow process networks to other dataflow models, including those used in dataflow machines, such as static dataflow and the tagged-token model. We also relate dataflow process networks to functional languages such as Haskell, and show that modern language concepts such as higher-order functions and polymorphism can be used effectively in dataflow process networks. A number of programming examples using a visual syntax are given.>

No abstract available.

In the Fall of 1993 at Berkeley we offered an experimental graduate course that focused on languages for modeling and design of signal processing systems. A major motivation for the course is our Ptolemy project, in which we are experimenting with models of computation and design methodology for signal processing systems. The applicable theory of computation primarily concerns stream datatypes and their implementation in dataflow, functional, and concurrent imperative languages. The issues addressed in the course include determinacy, concurrency, strictness, parallel scheduling, polymorphism, recursion, higher-order functions, and visual syntax. The emphasis is on studying strengths and weaknesses of existing and proposed design environments for signal processing.>

This paper addresses trade-offs between the minimization of program memory and data memory requirements in the compilation of dataflow programs for multirate signal processing. Our techniques are specific to the synchronous dataflow (SDF) model of Lee and Messerschmitt (1987), which has been used extensively in software synthesis environments for DSP. We focus on programs that are represented as chain-structured SDF graphs. We show that there is an O(n/sup 3/) dynamic programming algorithm for determining a schedule that minimizes data memory usage among the set of schedules that minimize program memory usage. A practical example to illustrate the efficacy of this approach is given. Some extensions of this algorithm are also given; for example, we show that the algorithm applies to the more general class of well-ordered graphs.>

This paper describes the use of Ptolemy to automatically generate code for heterogeneous multiprocessor systems. The framework presented lets the designer migrate from simulation to code generation while developing an application that is specified by constructing a dataflow graph. From primitive send and receive actors, the framework can automatically construct three classes of interprocessor communication (IPC) interfaces. The first type of interface uses a synchronous dataflow (SDF) parallel scheduler to partition and schedule the graph across the available processors. The second type of interface allows hierarchical use of cooperating schedulers within an application. Finally, the third interface uses the send and receive actors as an interface between code generation and simulation systems in Ptolemy. To illustrate the framework, we present an example of a heterogeneous architecture consisting of a workstation with multiple Motorola 56001 processors. We present the relative strengths and weaknesses of each type of interface.>

A recursive method for evaluating the impulse response of an indoor free-space optical channel with Lambertian reflectors is presented. The method, which accounts for multiple reflections of any order, enables accurate analysis of the effects of multipath dispersion on high-speed indoor optical communication systems. A simple algorithm for computer implementation of the technique and computer simulation results for both line-of-sight and diffuse transmitter configurations are also presented. In both cases, it is shown that reflections of multiple order are a significant source of intersymbol interference. Experimental measurements of optical multipath, which help verify the accuracy of the simulations, are discussed.>

The authors present a compile-time scheduling heuristic called dynamic level scheduling, which accounts for interprocessor communication overhead when mapping precedence-constrained, communicating tasks onto heterogeneous processor architectures with limited or possibly irregular interconnection structures. This technique uses dynamically-changing priorities to match tasks with processors at each step, and schedules over both spatial and temporal dimensions to eliminate shared resource contention. This method is fast, flexible, widely targetable, and displays promising performance.>

The authors present a new compile-time scheduling heuristic called declustering, which schedules acyclic precedence graphs that fit the synchronous data flow (SDF) model onto multiprocessor architectures. This technique accounts for interprocessor communication (IPC) overheads and considers interconnection constraints in the architecture so that shared resource contention can be avoided. The algorithm initially invokes a new clustering method that uses graph-analysis techniques to isolate parallelism instances. When constructing an initial set of clusters, this procedure explicitly addresses the tradeoff between exploiting parallelism and incurring communication cost. By hierarchically combining these clusters and then systematically decomposing this hierarchy, the declustering method exposes parallelism instances in order of importance and attains a cluster granularity that fits the characteristics of the architecture. It is shown that declustering retains the clustering advantage of avoiding IPC, yet overcomes the inflexibility associated with traditional clustering approaches.>

In the spring of 1991 a software laboratory was added to the graduate statistical signal processing class at Berkeley. The emphasis of this lab was on high-level experimentation with signal processing algorithms. A separate course on design methodology for signal processing covers VLSI design and programmable digital signal processors (DSPs), so this particular lab steered clear of these issues. A graphical block diagram programming environment developed at Berkeley (called Ptolemy) was used on a network of DEC workstations. Commercial software such as Comdisco's SPW system could have been used as well. The students were assigned a sequence of six experiments and given two weeks to complete each one. The design of the experiments in view of the teaching objective and effectiveness are discussed.>

Block diagrams with signal flow semantics have proven their utility in system simulation and algorithm development. They can also be used as high-level languages for real-time system implementation and design. An approach to synthesizing optimized assembly code for programmable DSPs from block diagrams is described. The extensible block library defines code segments in a meta-assembly language that uses the syntax of the assembly code of the target processor, but symbolically references registers and memory. An optimizing code generator compiles these segments together, allocates registers and memory, and inserts data movement instructions as needed to produce optimized assembly code. In exchange for target-processor dependence in both the code generator and the block library, the system produces assembly code that can closely match the efficiency of hand-written code.>

This paper describes an analytical model for the behavior of dataflow graphs with data-dependent control flow. The number of tokens produced or consumed by each actor is given as a symbolic function of the Booleans in the system. Long term averages can be analyzed to determine consistency of token flow rates, which in turn determines whether memory requirements are bounded. Short-term behavior can be analyzed to construct an annotated schedule, or a static schedule that annotates each firing of an actor with the Boolean conditions under which that firing occurs. Annotated schedules can be used to generate efficient implementations of the algorithms given by the dataflow graphs.>

Three examples are used to illustrate the time-driven style of computation in SPW (signal processing workstation). In this model of computation, the simulator statically schedules blocks for execution once per iteration. Execution control is provided by hold inputs that allow the user to run multiple sample rates within a system.>

The use of two models of computation, synchronous dataflow (SDF) and dynamic dataflow (DDF), to design and implement signal processing applications with multiple sample rates is discussed. The SDF model is used for synchronous applications. SDF is amenable to compile-time scheduling, and hence is much more efficient at runtime. The design environment, Ptolemy, can simultaneously support multiple models of computation, so SDF and DDF can be combined in a single application. Hence, the implementation will incur the run-time cost of DDF only for those asynchronous portions that absolutely must incur such cost. As an illustration, the authors detail a synchronous application, sample-rate conversion using polyphase filters, and an asynchronous application, timing recovery for an amplitude-shift-keyed signal.>

Four scheduling strategies for dataflow graphs onto parallel processors are classified: (1) fully dynamic, (2) static-assignment, (3) self-timed, and (4) fully static. Scheduling techniques valid for strategies (2), (3), and (4) are proposed. The focus is on dataflow graphs representing data-dependent iteration. A known probability mass function for the number of cycles in the data-dependent iteration is assumed, and how a compile-time decision about assignment and/or ordering as well as timing can be made is shown. The criterion used is to minimize the expected total idle time caused by the iteration. In certain cases, this will also minimize the expected makespan of the schedule. How to determine the number of processors that should be assigned to the data-dependent iteration is shown. The method is illustrated with a practical programming example.>

Analytical properties of programming languages with dataflow graph semantics are discussed. It is shown that one of the most serious problems with these languages is that subtle inconsistencies between parts of the dataflow graph can be inadvertently created. These inconsistencies can lead to deadlock, or in the case of nonterminating programs, to unbounded memory requirements. Consistency is defined to mean that the same number of tokens is consumed as produced on any arc, in the long run. A token-flow model is developed for testing for inconsistency. The method is a generalization of consistency checks for synchronous dataflow (SDF) graphs. The token-flow model is compared to similar tests applied to hybrid dynamical systems. It is argued that dataflow semantics make steady-state analysis possible, leading to a simpler method in most cases.>

Coherent optical communications, an area of research that shows great promise for future high-bandwidth and long-haul applications, is reviewed. Coherent optical receivers, which add light to the received signal as part of the detection process, have numerous advantages over direct-detection receivers, most notably increased sensitivity and increased selectivity, at the cost of increased complexity. The performance of coherent optical receivers under shot-noise-limited conditions is reviewed for a variety of modulation and demodulation formats. In addition, laser phase noise is discussed, and its effect on receiver performance is analyzed.>

Gabriel is a retargetable software system for the development of assembly code and microcode for single or multiple programmable DSPs. It is intended to ease code development even for processors that are not easy targets for conventional compilers. Code generation for the Motorola DSP56001 is emphasized. A Thor-based simulator supplies a variety of target multi-DSP architectures based on the DSP56001. The top-level algorithm description is a large grain data flow graph, and a graphical interface using OCT and VEM provides a natural representation of the high level structure of the algorithm.

A simulation environment oriented to the needs of the developer of custom multi-DSP systems has been developed and implemented. The simulator, Frigg, builds on the capabilities of a general-purpose behavioral simulator and manufacturer-supplied processor simulators. Frigg allows a user to simultaneously view the detailed behavior of the hardware and software comprising a complete multiprocessor system. Frigg is currently being used to simulate a variety of multi-digital-signal-processor systems and has proved useful for verifying hardware designs, performing detailed performance evaluations, and testing software and software tools.>

A technique is described which allows least squares computation to be made at arbitrarily high sampling rates, overcoming the inherent speed limitation due to the recursive algorithms. Previous efforts at high sampling rate systolic implementations of least squares problems have used Givens transformations and QR decomposition, achieving a sampling rate limited by the time required by several multiplication operations. Taking advantage of the linearity of the least squares recursion, the algorithms can be recast into a new realization for which the bound on throughput of least squares computation is arbitrarily high. The technique, which has previously been applied to adaptive lattice filters, is shown to be applicable to the matrix triangularization related problems such as solving general linear systems and computing eigenvalues by the QR algorithm.

This paper investigates the use of a fuzzy vector quantizer (FVQ) as the front end for a hidden Markov modeling (HMM) scheme for isolated word recognition. Unlike a standard vector quantizer that generates the index of a single codeword that best matches an input vector, an FVQ generates a vector whose components represent the degree to which each codeword matches the input vector. The HMM algorithm is generalized to accommodate the FVQ output. This approach is tested on a database of isolated words from a single male speaker. It is seen that the FVQ front end significantly reduces the amount of data needed to train the HMM algorithm.

Data flow is a natural paradigm for describing DSP applications for concurrent implementation on parallel hardware. Data flow programs for signal processing are directed graphs where each node represents a function and each arc represents a signal path. Synchronous data flow (SDF) is a special case of data flow (either atomic or large grain) in which the number of data samples produced or consumed by each node on each invocation is specified a priori. Nodes can be scheduled statically (at compile time) onto single or parallel programmable processors so the run-time overhead usually associated with data flow evaporates. Multiple sample rates within the same system are easily and naturally handled. Conditions for correctness of SDF graph are explained and scheduling algorithms are described for homogeneous parallel processors sharing memory. A preliminary SDF software system for automatically generating assembly language code for DSP microcomputers is described. Two new efficiency techniques are introduced, static buffering and an extension to SDF to efficiently implement conditionals.

Large grain data flow (LGDF) programming is natural and convenient for describing digital signal processing (DSP) systems, but its runtime overhead is costly in real time or cost-sensitive applications. In some situations, designers are not willing to squander computing resources for the sake of programmer convenience. This is particularly true when the target machine is a programmable DSP chip. However, the runtime overhead inherent in most LGDF implementations is not required for most signal processing systems because such systems are mostly synchronous (in the DSP sense). Synchronous data flow (SDF) differs from traditional data flow in that the amount of data produced and consumed by a data flow node is specified a priori for each input and output. This is equivalent to specifying the relative sample rates in signal processing system. This means that the scheduling of SDF nodes need not be done at runtime, but can be done at compile time (statically), so the runtime overhead evaporates. The sample rates can all be different, which is not true of most current data-driven digital signal processing programming methodologies. Synchronous data flow is closely related to computation graphs, a special case of Petri nets. This self-contained paper develops the theory necessary to statically schedule SDF programs on single or multiple processors. A class of static (compile time) scheduling algorithms is proven valid, and specific algorithms are given for scheduling SDF systems onto single or multiple processors.

Studying the effects of roundoff errors in digital filters requires specialized study of each implementation of each of various filter structures. Even the study of these special structures, however, is fraught with difficulties; different implementations of the same structure can have different roundoff behavior, because rounding is done at different points in the structure. The limitations of practical VLSI architectures suggest two models of computation that accurately reflect the vast majority of filter implementations. Such implementations can be accurately described in a factored state variable form that represents the actual computations in the implementations. The quantization noise behavior of different filter structures can be studied under this unified framework. Necessary and sufficient conditions for the optimality of filter realizations expressed in the factored state variable form are derived, as a simple extension of important earlier work with the usual state variable form.