Real-Time Embedded Software Design for Mobile and Ubiquitous Systems

Currently available application frameworks that target at the automatic design of real-time embedded software are poor in integrating functional and non-functional requirements for mobile and ubiquitous systems. In this work, we present the internal architecture and design flow of a newly proposed framework called Verifiable Embedded Real-Time Application Framework (VERTAF), which integrates three techniques namely software component-based reuse, formal synthesis, and formal verification. The proposed architecture for VERTAF is component-based which allows plug-and-play for the scheduler and the verifier. The architecture is also easily extensible because reusable hardware and software design components can be added. Application examples developed using VERTAF demonstrate significantly reduced relative design effort, which shows how high-level reuse of software components combined with automatic synthesis and verification increases design productivity.     

Modeling and verification of real-time embedded systems with urgency

Real-time embedded systems are often designed with different types of urgencies such as delayable or eager, that are modeled by several urgency variants of the timed automata model. However, most model checkers do not support such urgency semantics, except for the IF toolset that model checks timed automata with urgency against observers. This work proposes an Urgent Timed Automata (UTA) model with zone-based urgency semantics that gives the same model checking results as absolute urgency semantics of other existing urgency variants of the timed automata model, including timed automata with deadlines and timed automata with urgent transitions. A necessary and sufficient condition, called complete urgency, is formulated and proved for avoiding zone partitioning so that the system state graphs are simpler and model checking is faster. A novel zone capping method is proposed that is time-reactive, preserves complete urgency, satisfies all deadlines, and does not need zone partitioning. The proposed verification methods were implemented in the SGM CTL model checker and applied to real-time and embedded systems. Several experiments, comparing the state space sizes produced by SGM with that by the IF toolset, show that SGM produces much smaller state-spaces.     

Design Issues in a Performance Monitor for Embedded Multi-core Systems

Multi-core processors have elevated the performance of software via true parallelization. However, this has also created new challenges. One serious issue is the bottleneck in system performance due to synchronization, cache misses, or resource starvation, which is hard to detect in application software with runtime changing behavior. Performance monitors are usually employed for such detection. Nevertheless, monitors have introduced their own computation and communication overheads, especially in embedded multi-core systems. In this work, we propose a multi-core performance monitor and evaluate the effects of monitor overheads on different types of tasks, such as CPU-bound and IO-bound tasks. Further, we give suggestions on the number of monitors and the type of monitor deployments for embedded multi-core applications. Besides trying to reduce monitor overheads, we also aim at the accuracy and the immediacy of the monitored information. Through a real-world example, namely digital video recording system, we demonstrate how different monitoring periods affect the tradeoff between the accuracy and the immediacy.     

Billiard Combat Modeling and Simulation Based on Optimal Cue Placement Control and Strategic Planning

The selection of a best sequential shots for a given start cue position is a major challenging task in a billiard game. A new algorithm is proposed as a strategy to apply maximum tolerance angle search sequentially. The strategy considers combinations among all pockets and target object balls during both the pre and post collision shots selection processes. A simulation program is developed to test the strategy in a competition scenario by players with different proficiencies. The level of proficiency of players in the competition is controlled by a threshold value as a criterion to evaluate capability to conduct consecutive shots and when to give out right of play. The winning score of each game (win rate) is used as a performance comparison index among different gaming situations and to verify the effectiveness of the algorithm. The initial results of several simulation games using our strategy show that higher proficiency player can out beat lower proficiency player easily. This is consistent with the gaming situation in the real world, showing the consistency of our simulation program. The simulation also verifies that the play order does decide the final competition outcomes, when the players?? proficiencies are close to each other. This work is the first to investigate the effects of consecutive shots and order of play on the billiard gaming results. A low cost training system is proposed to verify the efficiency of the repositioning algorithm in real world settings. The system adapts an augmented reality technology to instruct users for reliable aiming assistance. It makes use of a vision system for cue ball, object ball locations and cue stick velocity tracking. In all, the simulation program can provide an initial proof of the effectiveness of the reposition algorithm in the competition situation. Experiments results of maximum tolerance angle all pocket search strategy using our training facility as tested by users with different skill levels all out performed the results without guidance for the set of users with the same proficiency.     

Embedded software verification in hardware–software codesign

Concurrent Embedded Real-Time Software (CERTS) is intrinsically different from traditional, sequential, independent, and temporally unconstrained software. The verification of software is more complex than hardware due to inherent flexibilities (dynamic behavior) that incur a multitude of possible system states. The verification of CERTS is all the more difficult due to its concurrency and embeddedness. The work presented here shows how the complexity of CERTS verification can be reduced significantly through answering common engineering questions such as when, where, and how one must verify embedded software. First, a new Schedule-Verify-Map strategy is proposed to answer the when question. Second, verification under system concurrency is proposed to answer the where question. Finally, a complete symbolic model checking procedure is proposed for CERTS verification. Several application examples illustrate the usefulness of our technique in increasing verification scalability.     

PSM: an object-oriented synthesis approach to multiprocessor systemdesign

Although multiprocessor systems are becoming a trend today, few synthesis tools currently available can actually automate the design of multiprocessor systems. Performance synthesis methodology (PSM) is an object-oriented system-level synthesis approach to multiprocessor system design. Since PSM was designed specifically for the synthesis of multiprocessor systems, it is not only much more efficient when synthesizing parallel systems, but also produces better parallel systems than currently available uniprocessor system-level synthesis tools. Colored Petri nets used in modeling system components and object modeling technique used in the design process have both contributed to the shortening of system development time and to the reduction of design cost. First, user specification consisting of functional models and performance constraints is translated into architecture models. Then, the system is configured by selecting the method of control, the memory organization, the type of processor, and the type of system interconnection. Finally, a heuristic design space exploration algorithm is used to generate several near-optimal design alternatives. The best architecture is chosen by evaluating the design alternatives using a flexible performance estimation formula that mainly considers system level design features, such as system throughput, utilization, reliability, scalability, fault-tolerance, and cost. Several systems were successfully synthesized using this top-down object-oriented PSM, thus showing its feasibility as a design automation tool for parallel systems     

VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development

Multi-core processors are becoming prevalent rapidly in personal computing and embedded systems.Nevertheless,the programming environment for multi-core processor-based systems is still quite immature and lacks efficient tools.In this work,we present a new VERTAF/Multi-Core framework and show how software code can be automatically generated from SysML models of multi-core embedded systems.We illustrate how model-driven design based on SysML can be seamlessly integrated with Intel’s threading building blocks (TBB) and the quantum framework (QF) middleware.We use a digital video recording system to illustrate the benefits of the framework.Our experiments show how SysML/QF/TBB help in making multi-core embedded system programming model-driven,easy,and efficient.     

SESAG: an object-oriented application framework for real-time systems

Advancements in hardware and software technologies have made possible the design of real-time systems and applications where stringent timing constraints are imposed on critical tasks. The design of such systems is more complex than that of temporally unrestricted systems because system correctness depends on the satisfaction of functional as well as temporal requirements. To aid users in correctly and efficiently designing systems, object-oriented frameworks provide a useful environment for significant reuse and reduction in design effort. In contrast to other application domains, there has been relatively little work on an application framework for the design of real-time systems. Facing the growing need for real-time applications, we propose a novel application framework called SESAG, which consists of five components, namely Specifier, Extractor, Scheduler, Allocator, and Generator. Within SESAG, several design patterns are proposed and used for the development of real-time applications. A new evaluation metric called relative design effort is proposed for evaluating SESAG. Experiences in using SESAG show a significant increase in design productivity through design reuse and a significant decrease in design time and effort. Two complex application examples have been developed using SESAG and evaluated using the new evaluation metric. The examples demonstrate relative design efforts of at most 18% of the design efforts required by conventional methods. Copyright © 2005 John Wiley & Sons, Ltd.     

UML-based hardware/software co-design platform for dynamically partially reconfigurable network security systems

The dynamic partial reconfiguration technology of FPGA has made it possible to adapt system functionalities at run-time to changing environment conditions. However, this new dimension of dynamic hardware reconfigurability has rendered existing CAD tools and platforms incapable of efficiently exploring the design space. As a solution, we proposed a novel UML-based hardware/software co-design platform (UCoP) targeting at dynamically partially reconfigurable network security systems (DPRNSS). Computation-intensive network security functions, implemented as reconfigurable hardware functions, can be configured on-demand into a DPRNSS at run-time. Thus, UCoP not only supports dynamic adaptation to different environment conditions, but also increases hardware resource utilization. UCoP supports design space exploration for reconfigurable systems in three folds. Firstly, it provides reusable models of typical reconfigurable systems that can be customized according to user applications. Secondly, UCoP provides a partially reconfigurable hardware task template, using which users can focus on their hardware designs without going through the full partial reconfiguration flow. Thirdly, UCoP provides direct interactions between UML system models and real reconfigurable hardware modules, thus allowing accurate time measurements. Compared to the existing lower-bound and synthesis-based estimation methods, the accurate time measurements using UCoP at a high abstraction level can more efficiently reduce the system development efforts.