Modeling, stability analysis and timetable design for parallel computer processing systems by means of timed Petri nets, Lyapunov methods and max-plus algebra

A parallel computer system is a set of processors that are able to work cooperatively to solve a computational problem and whose state evolves in time by the occurrence of events at possibly irregular time intervals. Place-transitions Petri nets (commonly called Petri nets) are a graphical and mathematical modeling tool applicable to parallel computer systems in order to represent its states evolution. Timed Petri nets are an extension of Petri nets, where now the timing at which the state changes is taken into consideration. One of the most important performance issues to be considered in a parallel computer system is its stability. Lyapunov stability theory provides the required tools needed to aboard the stability problem for parallel computer systems modeled with timed Petri nets whose mathematical model is given in terms of difference equations. By proving practical stability one is allowed to preassigned the bound on the parallel computer system dynamics performance. Moreover, employing Lyapunov methods, a sufficient condition for the stabilization problem is also obtained. It is shown that it is possible to restrict the parallel computer systems state space in such a way that boundedness is guaranteed. However, this restriction results to be vague. This inconvenience is overcome by considering a specific recurrence equation, in the maxplus algebra, which is assigned to the timed Petri net graphical model. Moreover, by using max-plus algebra a timetable for the parallel computer system is set.