Workshop on Theory and Practice of Timed Systems

Modern real-time applications, including multimedia systems, mobile robotics, and distributed monitoring architectures, often operate in highly dynamic environments where workload conditions are difficult to predict in advance. In addition, real-time activities may have variable computational requirements and are characterized by more flexible timing constraints than classical real-time theory usually permits. Handling such systems according to a hard real-time paradigm (based on worst-case assumptions) is inappropriate, because it would cause a waste of resources and would dramatically increase the cost.Recently, significant work has been devoted at increasing the flexibility and the efficiency of real-time systems, still providing a form of performance guarantee.

The goal of this talk is to introduce a set of new methodologies that can be adopted to develop adaptive real-time systems, that is, systems which can modify resource management policies based on the current workload conditions. In this framework, tasks are allowed to have less stringent timing constraints to achieve higher resource utilization. Moreover, the concept of yes-or-no guarantee is replaced with the notion of quality of service, which can be specified within a much larger grey-level scale.

The current generation of VLSI CPU's include a huge number of devices and the complexity is continuously increasing as technology scaling allows the designers to put more and more functionality within same area. At the same time the more and more advanced processes with faster devices allow higher operating frequency which require considering inductance and other physical effects. Lower voltages and smaller devices require increased timing accuracy. We take a two-prong approach, by increasing accuracy at the local level and supporting hierarchical models which abstract internals of blocks while preserving timing accuracy and interface electrical behaviour.

This talk will give an overview of timing analysis at intel. Hierarchical timing models that enable full-chip timing will be described as well as interaction with academia in timing-related topics , such as false paths identification .

I survey decomposition-methods that combine mathematical and constraint programming for solving scheduling problems.  Theidea is to generalize Benders decomposition so that the subproblem is a constraint programming problem in which Benders cuts are obtained by logical inference, and the master problem is a mixed integer programming problem.  I report results by Jain and Grossmann for a machine scheduling problem, and by Thorsteinsson for a branch-and-check approach to the same problem. I suggest how to generalize the approach using a continuous relaxation of the cumulative constraint (joint work with Yan).

Scheduling consists in assigning execution times and resources to activities so as to satisfy a variety of constraints (time bounds, precedence relations, resource capacity constraints, etc.) and optimize one or several conflicting performance criteria (total schedule duration, cost, schedule robustness, etc.). Two main issues have to be considered to evaluate the applicability of a model of time and resources to industrial scheduling applications: "flexibility" and "efficiency". Flexibility means that the specific constraints of a given application shall be easy to represent in the given model. Efficiency means that the algorithms that are applicable to this model must provide good solutions in limited CPU time. As scheduling applications tend to be different one from another, this led to the development of a variety of models of time and resources, with different characteristics in terms of flexibility and efficiency. The presentation will emphasize the most widely used models and compare them along these two dimensions.

Restriction is a central notion in system development. It appears to be a key concept for definition of parallel composition and refinement relations. It can be defined as a unary operation on systems whose effect is the restriction of the enabling conditions of actions.  For untimed systems,  restrictions S' of a system S both simulate S and preserve its invariants.For timed systems different notions of restriction can be defined depending on the effect of restriction operations on time progress. In this  talk we,

• Discuss different technical choices involved in the definition of restriction for timed systems.
• Give results about a notion of restriction which preserves both invariants and time progress.
• Illustrate applications of these results to the definition of property preserving operations such as flexible parallel composition.
• Discuss technical choices concerning the definition of time in systems and advocate for time models where waiting conditions are not specified or modified independently of the system's ability to perform actions.