| Department of Computer Science - Daimi |
|
| Home | Contact | Research | Courses | Curriculum | Library | Local | Search |
Most modern computing systems are distributed, and a current trend is that they become more and more pervasive.
A common property of these systems is that they are extremely complex to design, debug, and maintain. One way to cope with this challenge is to test and further develop the different design proposals by creating a number of models/prototypes which can be manipulated and executed on a computer. In this way it becomes possible to investigate how the system design works before the implementation starts. The result is an improved understanding of key design issues, fewer design errors, faster implementation, better documentation, and easier maintenance.
Coloured Petri Nets (CP-nets or CPNs) provide a framework for the construction and analysis of concurrent and distributed systems. CP-nets have a wide range of application areas and many CPN projetcs have been carried out in the industry
The CPN centre is based on the expertise of the CPN group at University of Aarhus. The work is organised as a number of projects in which CP-nets and other methods are used for modelling and analysis of systems. A typical project runs for 6-12 months and cooperates with an ongoing development project at one of the industrial partners. A project could, e.g., be the design and validation of the communication and synchronisation in a new system, or it could be performance analysis and capacity planning of a system. The choice of projects is based on the needs of the participating companies.
Web-pages: http://www.daimi.au.dk/CPnets/
Partners: Nokia Research Center, Microsoft Research Limited, Ericsson Telebit, Hewlett-Packard, and George Mason University.
The work within the CPN centre focuses on four main areas:
It is generally recognised that the design of the communication and synchronisation in concurrent/distributed systems is a complex task. A major reason is that the execution of such systems may proceed in many different ways, e.g., depending on whether messages are lost, the speed of the processes involved, and the time at which inputs are received from the environment.
Coloured Petri Nets (CP-nets) provide a framework for the design andanalysis of such systems. CP-nets are based on Petri Nets, which is one of the most widely accepted formalisms for modelling and analysis of concurrent and distributed systems. CP-nets are also based on concepts and terminology from modern programming languages and hence they are relatively easy to learn and use for people with some programming experience. Construction of CPN models are in many respects similar to construction of prototypes. They allow the designer to make a concrete and thorough evaluation of the key design issues. This may not only reveal shortcomings, but also increase the designer's understanding of the fundamental concepts in the new system.
A CPN model describes the states that the system may be in and the transitions between these states. By means of simulation a number of what-if scenarios be investigated. Furthermore, it is also possible to investigate the behaviour of systems by means of state space techniques. Then it is possible to consider all execution sequences and prove that the system possesses certain desired properties. The proofs are constructive in the sense that a negative answer identifies one or more counter-examples that can be used to locate the source of the problem.
CPN models can also be used to investigate the performance of a system,i.e., the efficiency of the system. Timed CPN models can be used to investigate the quality of service (e.g., waiting and processing time) and the quantity of service (e.g., throughput). In this way it becomes possible to predict the efficiency of a system before it is built and installed. By changing a few parameters in the CPN model, itis easy to experiment with different ways of improving the efficiency.In this way, it can be seen in which areas the development efforts should be concentrated to achieve the best results.
Capacity planning is similar to performance analysis, but the aim is slightly different. In capacity planning the goal is to choose the most suitable system configuration efficient enough to fulfil its tasks, now and in the foreseeable future, but without being overlycostly by offering unused power. Capacity planning is an art performedby skilled individuals. Their creativity and experience is indispensable, but their work can be supported by allowing them toevaluate different system configurations by means of simulation models.
The tools, algorithms, and techniques for the practical use of CP-nets are under continuous development and improvement. Over the last years wehave developed a very fast CPN simulation engine which is now integratedin the CPN tool set.
One of the main challenges in industrial application of state space techniques is to cope with the so-called state explosion problem, i.e.,the large number of states and state changes in industrial sized concurrent systems. We have started a total redesign and reimplementation of the tool support for state space techniques. It is based on the new CPN simulation engine, contains improved datastructures for state space storage, and implements a number of state-of-the-art analysis and verification algorithms alleviating the state explosion problem.
We are also in the process of implementing a totally new user interface for the CPN tools.The principles behind this interface may be of interest for many other graphical applications. Unlike standard graphical interfaces, the new userinterface does not use menu bars, scrollbars or dialog boxes, and there is no need to select objects before editing them. Yet, the system is much faster to operate than a traditional desktop interface. Windows are replaced by pages that can be bound together into binders, makingit easy to flip between pages and organise the workspace. A trackball, operated by the left-hand (if you are right-handed) complements the mouse. Using these two input devices, it is possible to resize and zoom objects by stretching them as one would do with a physical object. It is also possible to move an object with the right hand while flipping pages with the left hand to find its destination. Another two-handedinput technique consists in moving a translucent palette called a tool glass with the lefthand while clicking through the palette tools with the right hand. This type of interaction is up to 40% faster than traditional tool palettes. Finally, circular menus that pop-up where the mouse is clicked allow avery quick selection of commands, up to three times faster than traditional menu bars. The menu does not even appear when the selection gesture is made quickly. This allows for very fast selection without the need to learn keyboard shortcuts. Objects are aligned by sticking them to magnetic guidelines. Moving a guideline then moves all the attached objects at once.
CPN Tools: http://www.daimi.au.dk/CPNtools/
Today, the de-facto standard modelling language of the software industry is the Unified Modeling Language, UML. UML has strong support for static models, e.g., in the form of class diagrams. However, UML's support for dynamic models, i.e., models of behaviour, is more limited. Static models are widely used and accepted in the software industry, but the same does not apply to dynamic models.
The Object Managament Group's (OMG) Model Driven Architecture (MDA) and Model Driven Development (MDD) initiative will make models a first-class citizen ofsoftware development. MDA/MDD represents a significant change of abstraction level that can be compared to the change that happened decades ago, when assembly programming was replaced by programming in high-level languages. OMG's MDA/MDD is based on the use of UML; it will move UML from often being used informally or semi-formally as a drawing tool into a programming language. Therefore, UML's limited support for modelling of behaviour - and for executable models - is a serious threat to the success of MDA/MDD.
CPN models, used in a UML context, is a viable candidate to offer some alleviation. As a specific example, CPN models used for requirements engineering can be a supplement to UML-style use cases. Also, CPN models can often be used as alternatives to UML state charts and UML activity diagrams.
|
Responsible: Michael I.
Schwartzbach
Last Modified: 09 March 2005 |