Modeling task systems using parameterized partial orders
- PDF / 778,401 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 0 Downloads / 204 Views
EUROSYS
Modeling task systems using parameterized partial orders Fred Houben · Georgeta Igna · Frits Vaandrager
Published online: 13 November 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract Inspired by work on model-based design of printers, the notion of a parametrized partial order (PPO) has recently been introduced. PPOs are a simple extension of partial orders, expressive enough to compactly represent large task graphs with finite repetitive behavior. We present a translation of a subclass of PPOs to timed automata and prove that the transition system induced by the Uppaal models is isomorphic to the configuration structure of the original PPO. Moreover, we introduce real-time task systems (RTTSs), a general model for real-time embedded systems that we have used to describe the data paths of realistic printer designs. In an RTTS, tasks are represented as PPOs and the pace of a task instance may vary, depending on the resources that are allocated to it. We describe a translation of a subclass of RTTSs to Uppaal, and establish, for an even smaller subclass, bisimulation equivalence between the timed configuration semantics of an RTTS and the transition system induced by the corresponding Uppaal translation. Lastly, we report on a series of experiments which demonstrates that the resulting Uppaal An extended abstract of this paper appeared as [1]. The research of Igna and Vaandrager has been carried out as part of the OCTOPUS project under the responsibility of the Embedded Systems Institute. This project is partially supported by the Netherlands Ministry of Economic Affairs under the Bsik program. This research was also supported by European Community’s Seventh Framework Programme under Grant agreement no. 214755 (QUASIMODO). F. Houben ASML, Veldhoven, The Netherlands e-mail: [email protected] G. Igna · F. Vaandrager (B) ICIS, MBSD Group, Radboud University Nijmegen, Nijmegen, The Netherlands e-mail: [email protected] G. Igna e-mail: [email protected]
models are more tractable than handcrafted models of the same systems used in earlier case studies. Keywords Parameterized partial orders · Real-time task systems · Task graphs · Scheduling · Real-time embedded system · Design-space exploration
1 Introduction The complexity of today’s real-time embedded systems and their development trajectories is increasing rapidly. At the same time, development teams are expected to produce high-quality and cost-effective products, while meeting stringent time-to-market constraints. A common challenge during development is the need to explore extremely large design spaces, involving multiple metrics of interest (timing, resource usage, energy usage, or cost). The number of design parameters (number and type of processing cores, sizes and organization of memories, interconnect, scheduling and arbitration policies) is typically very large. Moreover, the relation between parameter settings and design choices on the one hand and metrics of interest on the other hand is often difficult to determine. Given these observat
Data Loading...
