|
Report on Subproject S-1: Existing Software
J. Mairesse and the LIAFA (LITP) team
WarningFormulaes are not always displayed correctly in this document. For a complete version, including these formulaes, we refer to the postscript version.Contents |
[ALAPEDES main page] [Research Objectives] [Approach and Work Plan] [Schedules and Milestones] [Reports] [Participants] [Looking for students/post docs] [Meetings] [Existing software] |
Description of the subproject, quoted from the Alapedes Project Programme:
Investigation and critical analysis of existing software.
The participants are LIAFA (LITP) and ARMINES.
One of the difficulty in investigating software associated with the Alapedes program is to decide what the scope of the investigation should be.
There are many domains, and associated software, which could be of interest for some of the subprojects, even though they are not primarily designed to cope with `Performance Evaluation of Discrete Event Systems'. To avoid drifting away too far from the main preoccupations of the project, we have insisted on the software which were mainly designed for Discrete Event Systems (DES). We have given a particular attention to softwares based on algebraic properties of DES as opposed to pure simulation packages. We have also insisted on those which were easiest to obtain, i.e. the non-commercial ones, and on those developed by one of the partners of the project.
Another rather artificial distinction is that between `existing software' (subproject S-1) and `software in development' (subproject S-2). Some of the software developed by Alapedes members already existed before the beginning of the project (S-1 !) but are still currently developed and are being substantially improved (S-2 !). In such cases (see AUTOMATE, ERS, MAX), we have decided to include a description of these softwares in the report.
In the first three sections, we describe successively the softwares dealing with three different description formalisms for DES: automata, queueing networks and Petri nets. To fix the ideas, we have recalled the basic definition for these three models.
Starting from the description formalism of the model, these software
usually
propose solver and
simulation based on a mathematical formalization.
One of the recurrent mathematical framework is that of idempotent
semirings. In §
, we present software for the
computation
in idempotent semirings.
In § and §, we describe 2 global
packages: MAPLE and SCILAB. They are not specifically designed
for DES, but are used as a programming framework by several of the
software described in the document.
The study of automata was initiated in the 50's by the work of Kleene. A finite automaton provides the simplest model of a computing device. It has proved to be a basic and central model in computer science, see [8, 15].
It is also one of the basic models for the algebraic study of discrete event systems. Hence, it is natural to start this report by describing the software dealing with finite automata.
This web page is a good starting point to investigate software dealing with automata. Some of the information below was gathered with the help of the above page but the links have been updated.
The AMORE (computing Automata, MOnoids, and Regular Expressions) system was developed at the University of Kiel under the direction of W. Thomas. It is a program for the computation of finite automata, syntactic monoids of regular languages, and (possibly star-free) regular expressions. The system is implemented in C under Unix or DOS. A graphical component generates state graphs of finite automata on the screen from given transition tables (under Unix only). It can be obtained by anonymous ftp.
AUTOMATA is a Mathematica based package that manipulates finite state machines and their syntactic semigroups. A number of operations on 1-dim cellular automata are also available. All the algorithms are implemented in Mathematica, and a good number of them is also implemented externally in a C++ library (e.g., power automaton construction, minimization using Hopcroft's algorithm, -class decomposition). The C++ code can be used directly or, via MathLink, from within Mathematica. On a standard workstation, the external code allows one to generate machines and/or semigroups with several 10000 elements. The program can be downloaded from the web page.
>From the COLOS project (European project, started in 1988 and supported by Hewlett-Packard) at the University of Milan. AUTOMATA is a tool for modelling automata and experimenting with grammars. The environment deals with: finite state automata (FSA, both deterministic and non deterministic), push-down automata - PDA (both deterministic and non deterministic), finite state transducers (Moore and Mealy machines), grammars, regular expressions, pattern matching. It provides the visualization of some important algorithms, such as the transformation of non deterministic automata into deterministic ones or the minimization. The automata are defined by entering their state diagram in a graphic editor or by giving a grammar. It can be downloaded from the web page.
Grail is developed by Darrell Raymond and Derick Wood. Grail is a symbolic computation environment for finite-state machines, regular expressions, and other formal language theory objects. Using Grail, one can input machines or expressions, convert them from one form to the other, minimize, make deterministic, complement, and perform many other operations. Grail is intended for use in teaching, for research into the properties of machines, and for efficient computation with machines. Grail is written in C++. It can be accessed either through a process library or through a C++ class library. The source code can be downloaded from the web page.
The AUTOMATE project is being developed by one of the ALAPEDES TEAMS: LIAFA (LITP). For this reason, we will go into more details to describe it. The original software was written in C by Champarnaud and Hansel [6]. The project is now pursued both in the University of Rouen (LIR), and in LIAFA. The project in Rouen is conducted by J.-M. Champarnaud and in LIAFA by J.-E. Pin. For additional information:
Here is a description of the software AUTOMATE. The objects manipulated are automata which can be given under the following forms:
The main functionalities implemented are:
A programming language associated with AUTOMATE has been developed,
[5], and the program also exists under the form of a MAPLE
package, see §.
A program dealing with finite semigroups and complementing AUTOMATE is
currently being developed in
LIAFA, see §.
Queueing networks were first studied in the beginning of the century in connection with telecommunication. They have become one the most popular modelling framework in communication, traffic control or manufacturing.
An interesting web page on queueing theory, including a list of software can be found at the following address:
The huge variety of queueing problems have given rise to an also huge variety of mathematical models for queues, each with its specificities, see [13, 1, 2].
Generally speaking, a queue consists of a service unit (processing unit) and a buffer (waiting line). The mathematical description of the queue is made through: the arrival process of customers (which are going to wait in the buffer until being served by the processing unit), the service process, i.e. the type and quantity of service required by the customer from the unit and the service discipline, i.e. the algorithm determining the order in which customers are served by the processing unit.
A shorthand notation introduced by Kendall, and which has become classical, enables to classify the most common types of models of queues.
One should remark that with the exception of the simplest queues (e.g. or ), the Kendall notation is not enough to completely describe a queue. For instance, for a queue, it is necessary to specify the distribution of the arrival and service processes and also to describe what happens to a customer arriving in front of a full buffer.
A queueing network consists of a finite set of queues, with external arrival processes, and which are inter-connected in such a way that a customer departing from one queue may become an arrival customer for an other queue. Several types of inter-connections are possible: for instance a queue could be linked to at most one queue , each customer leaving being routed to ; or a queue could be linked to several queues, each departing customer deciding where to go in a random way.
An interesting web page on queueing story, including a list of software can be found at the following address:
Furthermore, the following two web pages devoted to Operations Research have very good sections on software. Some of them are of direct interest to Alapedes: codes for network optimization, job-shop simulation.
Let us mention rapidly some of the programs.
MODLINE is commercialized by Simulog. It is originally an output of the ESPRIT European research program (IMSE project), where INRIA Sophia was one of the participants. MODLINE is an open environment for modeling and simulation of discrete events systems. It integrates the QNAP2 software package. QNAP2 is a generic language for simulation and performance evaluation of queuing network systems. In particular, here are the available resolution methods:
Exact or approximate analytical models for fast analysis of steady states. The most accurate method is automatically selected by the system.
Markov solver computing an exact solution in steady cases that include complex synchronization processes.
TELPACK is a teletraffic analysis software which allows users to solve structured Markov chains motivated by probabilistic modeling and analysis for design and engineering of computer and communication networks. Similar problems also arise in many other different areas. The software utilizes a small subset of CLAPACK routines, the most advanced and efficient numerical algebra routines available.
The program can be downloaded from the web-page.
QPACK has been developed by M.L. Chaudhry. It consists of a series of user-friendly software packages for several different bulk and non-bulk queueing models. The software package finds numerically the steady-state probabilities and moments for the number of customers in the system at various time epochs (i.e. Pre-arrival, Random, and Post-departure). It also, finds moments for waiting times, and waiting time densities in some cases. The models presently available in the form of a package are:
This program is not free: University Faculties: 1st package 70.00 (U.S.); each additional package 60.00 (U.S.). More information to be found at:
Timed and untimed Petri nets have been actively studied, since their introduction in the 60's, in particular as a modelling and analysis tool for Discrete Event Systems, see [3, 4, 14].
In the case of untimed Petri nets,
the basic object of study is the reachability graph
describing all the possible markings.
In the case of a bounded Petri net, the reachability graph can be
viewed as a deterministic automaton, see §.
Here we are interested in software dealing with the behaviour of timed Petri nets.
There exist many variants of Petri nets. To fix the ideas, we present the most standard one:
The marking evolves according to the firing rule.
A Timed Petri net (TPN) is a net with firing times associated with transitions and/or holding times associated with places.
There exists many software dealing with Petri nets, most of them being purely simulation software.
A very good access point is the web page:
It contains a classification of the dozens of different kinds of Petri nets which coexist in the litterature as well as links to many existing software (62 of them are listed!).
We now detail two of these software, which are of particular interest.
GreatSPN (GRaphical Editor and Analyzer for Timed and Stochastic Petri Nets) is a free software developed in the University of Torino. It is a package for the modelling, validation, and performance evaluation of distributed systems using Generalized Stochastic Petri Nets and their coloured extensions.
Along with a simulation module, there are analytic tools available:
Instruction on how to get the software (free for universities) can be found on the web page.
ERS is a developed by one of the Alapedes team, INRIA (Sophia-Antipolis, Mistral project). One of its specificities is to rely heavily on the algebraic formalization of Petri nets to propose exact solvers and efficient simulations.
ERS is a toolbox containing several programs for the performance
evaluation of DES. Several formalisms are used, including Petri nets,
Queueing networks and Task graphs. They are included in an environment
allowing the user to go from model specification to result analysis.
There exist bridges between ERS and QNAP2, see §.
Here is a more detailed description of the functionalities provided:
Other tools, for the distributed simulation of queuing networks are developed in INRIA (PARSEVAL, PROSIT, PASTEQ). It is intended to also integrate these programs in the ERS toolbox.
In the algebraic study of DES, idempotent semirings play a central
role, see [3, 7, 12]. We now present a software,
MAX, which provides tools for working in idempotent semirings.
Several of the programs currently developed within Alapedes follow
this approach, see .
Some idempotent semirings are very classical and useful in the study of Discrete Event Systems:
MAX is a MAPLE package developed by Stéphane Gaubert from the Alapedes team of INRIA (Rocquencourt, Meta2 Project). The main source of documentation is Gaubert's thesis [10], Chapters VIII and IX. The package can be obtained by e-mail demand. For more information:
Here is a more precise description of the functionalities provided.
In a Timed Event Graph (with some input and output transitions) where all the timings are integer valued, the transfer function can be described as a rational series over . For two specific kinds of Event Graphs (flow-shop and Kanban transfer line), MAX is equipped with commands which, given the Event Graph, provide its transfer function.
When some resources (i.e. number of tokens in some places) are unknown in a Timed Event Graph (with integer timing), the transfer function can be described as a formal rational series over (where the 's correspond to the unknowns). MAX enables one to manipulate images of these series in order to compute symbolically the throughput as a function of the unknown quantities (for optimisation purposes for instance).
Maple was originally developed by the University of Waterloo (Canada). It is a commercial symbolic computation system. It also includes classical numerical calculus functionalities.
All the information needed can be found at the home page:
It is a free software whose functionalities are close to those of the commercial program MATLAB. It is developed by INRIA (the Scilab group: INRIA-Rocquencourt Meta2 Project and Cergrene ENPC). Here is a description from Introduction to Scilab (document to be found at http://www-rocq.inria.fr/scilab/doc/intro-html/intro-html.html).
Developed at INRIA, Scilab has been developed for system control and signal processing applications. It is freely distributed in source code format. (...) Scilab provides a variety of powerful primitives for the analysis of non-linear systems. Integration of explicit and implicit dynamic systems can be accomplished numerically. The scicos toolbox allows the graphic definition and simulation of complex interconnected hybrid systems. There exist numerical optimization facilities for non linear optimization (including non differentiable optimization), quadratic optimization and linear optimization.
Scilab can be obtained by anonymous ftp. There exist versions for Unix-Xwindow systems, Windows 95 and Macintosh. A lot of information can be found on the Scilab home page.
There exists a Maple to Scilab interface, transforming Maple objects into Scilab functions.
The development of new software is the object of subproject S-2. Here is a preview of S-2, listing some software developments which have been initiated during the first year of operation of the Alapedes project.
To facilitate the integration of the software developed within
Alapedes, several of them have been written using the software
package SCILAB, see §. Such an effort should be
encouraged.
J.E. Pin and V. Froidure are currently developing a program, called
`SEMIGROUPE', and which complements AUTOMATE, see §
. Its specificity is to be able to deal with
semigroups which are not necessarily defined as transformation
semigroups (as opposed to AUTOMATE for instance). In SEMIGROUPE, one
can consider semigroups of matrices with coefficients in
some commutative semirings: Boolean semiring, ,
and (see ).
The functionalities already implemented (with some original algorithms) are (given the generators of the semigroup): list of the elements, relations, idempotents, computation of the minimal ideal, of Green's classes, of the inverses, of local subsemigroups, of the representative of an element, variety tests: commutativity, nilpotence, idempotence, aperiodicity, and so on. For more details, see [9].
M. Kanta is developing a software (TROPRAT) to work with power series in one variable over the tropical semiring . It is known that in this case, all classical decidability problems are decidable (as opposed to the case of formal power series in several variables over the tropical semiring). It enables to make computations with such series. The functionalities implemented are: basic algebraic operations, normal form computations, verification of the equality of 2 series.
E. Hautecloque, a masters student from ENSTA, has been working under the supervision of S. Gaubert (INRIA) and J. Mairesse (LIAFA) on implementing a software based on the results of [11]. The dynamic of jobshops is shown to be represented by a (max,+) automaton. This algebraic representation makes it possible to evaluate the different schedulings in a jobshop in an efficient way. The program, written in C and interfaced with Scilab, takes as an input a jobshop and computes the makespan of all admissible schedules.
M. McGettrick is working on adding functionalities to SCILAB to enable calculations in idempotent semirings. The functions already implemented or being currently developed are: and basic operations for (sparse) matrices; residuation for (sparse) matrices; star operation for matrices; karp/howard algorithms for eigenvalue.