Joost P.H.M. Hausmans
ABSTRACT
The incremental design and analysis of parallel hard real-time stream processing applications is hampered by the lack of an intuitive compositional temporal analysis model that supports arbitrary cyclic dependencies between tasks.
This paper introduces a temporal analysis model for hard real-time systems, called the Compositional Temporal Analysis (CTA) model, in which arbitrary cyclic dependencies can be specified. The CTA model also supports hierarchical composition and incremental design of timed components. The internals of a component in the CTA model can be hidden without changing the temporal properties of the component. Furthermore, the composition operation in the CTA model is associative, which enables composing components in an arbitrary order. Besides all these properties, also latency constraints and periodic sources and sinks can be specified and analyzed.
We also show in this paper that for the CTA model efficient algorithms exist for buffer sizing, verifying consistency of compositions and to compute the temporal properties of compositions.
The CTA model can be used as an abstraction of timed dataflow models. The CTA model uses components with transfer rates per port, in contrast to dataflow models that use actors with firing rules. Unlike dataflow models, the CTA model is not executable.
An audio echo cancellation application is used to illustrate the applicability of the CTA model for a stream processing application with throughput and latency constraints, and to illustrate incremental design.
- G. Bilsen et al. Cyclo-Static Dataow. IEEE Transactions on Signal Processing, 44(2):397--408, 1996. Google Scholar
Digital Library
- M. Geilen, S. Tripakis, and M. Wiggers. The Earlier the Better: A Theory of Timed Actor Interfaces. In Int'l Conf. on Hybrid Systems: Computation and Control (HSCC'11), April 2011. Google ScholarDigital Library
- T. Henzinger and S. Matic. An Interface Algebra for Real-Time Components. In Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium, pages 253--266. IEEE Computer Society, 2006. Google ScholarDigital Library
- K. Lampka, S. Perathoner, and L. Thiele. Analytic real-time analysis and timed automata: a hybrid method for analyzing embedded real-time systems. In Proc. of the ACM Int'l Conf. on Embedded software, pages 107--116. ACM, 2009. Google ScholarDigital Library
- E. Lee and D. Messerschmitt. Synchronous Data Flow. Proc. of the IEEE, 75(9):1235--1245, 1987.Google ScholarCross Ref
- J. Ostroff. Abstraction and composition of discrete real-time systems. Proc. of CASE, 95:370--380, 1995.Google Scholar
- S. Perathoner, K. Lampka, and L. Thiele. Composing heterogeneous components for system-wide performance analysis. In Proc. of Design, Automation and Test in Europe (DATE'11), 2011.Google ScholarCross Ref
- J. Pino, E. Lee, and S. Bhattacharyya. A hierarchical multiprocessor scheduling system for DSP applications. In asilomar, page 122. Published by the IEEE Computer Society, 1995. Google ScholarDigital Library
- R. Reiter. Scheduling parallel computations. Journal of the ACM (JACM), 15(4):590--599, 1968. Google ScholarDigital Library
- S. Sriram and S. Bhattacharyya. Embedded Multiprocessors: Scheduling and Synchronization. Signal Processing and Communications Series. Marcel Dekker, Inc., 2000. Google ScholarDigital Library
- L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systems. In Proc. IEEE Int'l Symposium on Circuits and Systems, volume 4, pages 101--104. IEEE, 2000.Google ScholarCross Ref
- L. Thiele, E. Wandeler, and N. Stoimenov. Real-time interfaces for composing real-time systems. In Proc. of the ACM/IEEE Int'l Conf. on Embedded Software, pages 34--43. ACM, 2006. Google ScholarDigital Library
- S. Tripakis, D. Bui, B. Rodiers, and E. Lee. Compositionality in synchronous data ow: Modular code generation from hierarchical sdf graphs. In Proc. of the ACM/IEEE Int'l Conf. on Cyber-Physical Systems, page 199. ACM, 2010. Google ScholarDigital Library
- M. Wiggers, M. Bekooij, and G. Smit. Efficient Computation of Buffer Capacities for Cyclo-Static Dataow Graphs. In Proc. of the Design Automation Conference, page 663. ACM, 2007. Google ScholarDigital Library
- M. Wiggers, M. Bekooij, and G. Smit. Monotonicity and Run-Time Scheduling. In Proc. of the ACM Int'l Conf. on Embedded Software, pages 177--186. ACM, 2009. Google ScholarDigital Library
- M. Wiggers et al. Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure. pages 10--15, 2006. Google ScholarDigital Library
- M. Wiggers et al. Efficient Computation of Buffer Capacities for Cyclo-Static Real-Time Systems with Back-Pressure. In Proc. of the IEEE Real Time and Embedded Technology and Applications Symposium, pages 281--292. IEEE Computer Society, 2007. Google ScholarDigital Library
Index Terms
- Compositional temporal analysis model for incremental hard real-time system design
Recommendations
Hardware support for WCET analysis of hard real-time multicore systems
ISCA '09: Proceedings of the 36th annual international symposium on Computer architectureThe increasing demand for new functionalities in current and future hard real-time embedded systems like automotive, avionics and space industries is driving an increase in the performance required in embedded processors. Multicore processors represent ...
A Compositional Framework for Hardware/Software Co-Design
We describe a compositional framework, together with its supporting toolset, for hardware/software co-design. Our framework is an integration of a formal approach within a traditional design flow. The formal approach is based on Interval Temporal Logic ...
The Formal Design Model of a Real-Time Operating System RTOS+: Conceptual and Architectural Frameworks
A real-time operating system RTOS provides a platform for the design and implementation of a wide range of applications in real-time systems, embedded systems, and mission-critical systems. This paper presents a formal design model for a general RTOS ...
Comments