Petri net as a modeling tool

Over the last decade, Petri nets have emerged as a most suitable, powerful and widely acceptable modeling tool for representing and studying the asynchronous concurrent hardware (or software) systems/processes. Petri nets can be viewed as formal automata or as an automation which can generate the formal languages or a model to analyse and synthesize various kinds of systems. The structure of Petri nets, their markings, extensions and subclasses are briefly discussed. Several examples of Petri net models of computer hardware and software are presented. Various applications of reachability concepts are also given.     

A Petri net approach to enumerating all circuits of a graph

A technique utilizing the concept of reachability in Petri net is proposed to enumerate all the circuits of a graph. The proposed technique requires only vector additions on the columns of a single matrix. The present method which is a simple and applicable to both directed and undirected graphs, can easily be computerised.     

面向对象Petri网建模技术与应用

面向对象方法使得系统设计简化,符合所描述的现实事物的特点,简单易于理解.但是在设计系统时没有进行严格的检验和验证.Petri网提供了形式化的图形表示,层次化的结构在表示类的继承以及描述对象的动态性方面非常有用.现介绍一种抽象节点技术,将面向对象设计模型转换成层次化的Petri网模型将对象和对象属性封装到数据结构中去,从而结合了两者的优点.     

Program verification for microprocessors through Petri net modeling

Program verification forms an important part of the developmental process in the design of a microprocessor system to suit a particular application. The concepts of Petri nets are utilized to obtain a model of a microprocessor system which is suitable for program verification. The reachability and firing characteristics of Petri nets are useful and powerful tools for studying the dynamic behaviour of the modeled system at various levels of abstraction. The Petri net representation of different types of independent modules in the system is obtained through an appropriate interpretation. On the basis of these representations, the modeled system may be analysed to study the dynamic behaviour of the program.     

Petri net approach to the analysis of a structured program

The analysis problem of complexity and execution time of a structured program has been tackled using the concept of Petri net (PN). This type of representation is useful due to its graphical and precise nature of representation scheme and also the established relationship between certain net structure and dynamic behaviour of PN can be used as a tool for analysing the behavior of the system. A PN representation of various nested blocks of the structured program is given. The firing characteristic of the transitions in a PN has been used to give an interpretation to each of the blocks and it is shown how each of the blocks can be simplified with a view to calculating the total execution time of a program. It is simple as it gives a straightforward procedure for analysing the program.     

Petri net approach to enumerate all simple paths in a graph

A technique utilising the concept of reachability in a Petri net is proposed to enumerate all simple paths between two specified nodes of a graph. It is simple and requires little computation.     

Modeling, analysis, simulation, scheduling, and control ofsemiconductor manufacturing systems: A Petri net approach

This paper presents a Petri net approach to modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems. These systems can be characterized as discrete event systems that exhibit sequential, concurrent, and conflicting relations among the events and operations. Their evolution is dynamic over time. The system complexity is tremendous owing to the complex semiconductor manufacturing processes and test procedures. A formal approach such as Petri nets enables one to describe such complex discrete event systems precisely and thus allows one to perform both qualitative and quantitative analysis, scheduling and discrete-event control of them. This paper also serves as a tutorial paper. It briefly reviews applications of Petri nets in semiconductor manufacturing automation. It then introduces definitions and concepts of Petri nets. It proceeds with a discussion of basic Petri net modules in system modeling, a modeling method and a practical system's modeling example. Next, the paper presents their properties and their implications in manufacturing systems, as well as their analysis methods. Timed Petri nets are introduced for system simulation, performance evaluation, and scheduling purposes. An application-oriented case study is presented. Finally, the paper concludes with the active research areas in applying Petri nets to design of semiconductor manufacturing systems     

A new generalized stochastic Petri net modeling for energy-harvesting-wireless sensor network assessment

This paper proposes an energy-harvesting-aware model that aims to assess the performances of wireless sensor networks. Our model uses generalized stochastic Petri nets to define a sensor–neighbors relationship abstraction. The novelty of the proposed formulation is taking into account several real-life considerations such as battery-over breakdowns, unavailability of neighbors, retrial attempts, and sleeping mechanism in a single model. We use TimeNet tool to simulate the network behavior in order to evaluate its performance throughout different formulas after it had reached its steady state. Finally, we present a case study featuring the different solar energy recovery capabilities of the vast Algerian territory. The aim is to show with the presented model how to determine the kind of resources to be acquired in order to cope with the sensor deployment project requirements. The proposed model allows us to ensure that the battery energy level of sensors deployed in Algiers province for example is almost equal to 80% for 100 messages per day and (1 min/2 min) for (awakening time/sleeping time) ratio.     

Petri net modeling of gate and interconnect delays for power estimation

Switching activity estimation is an important step in average power estimation of VLSI circuits at the gate level. In this paper, we present a novel approach based on Petri net modeling for real delay switching activity and power estimation of CMOS circuits, considering both gate and interconnect delays. We propose a new type of Petri net called hierarchical colored hardware Petri net (HCHPN), which accurately captures the spatial and temporal correlations in modeling switching activity. The logic circuit is first modeled as a gate signal graph (GSG) which is then converted into the corresponding HCHPN and simulated as a Petri net to obtain the switching activity estimates and the power values. The proposed method is accurate and fast compared to other simulative methods. Experimental results are provided for ISCAS '85 and ISCAS '89 benchmark circuits and compared with the commercial tools, PowerMill, and Prime Power.     

Protocol design and performance analysis for manufacturing messagespecification: A Petri net approach

The manufacturing message specification (MMS) is the ISO standard communication protocol specific to manufacturing. To analyze MMS design and performance, service unit automats are introduced to represent individual MMS services, while service connection Petri Nets (PNs) are constructed from these automats to describe MMS service connections and processes. This approach makes MMS protocol specification and analysis possible in terms of well-developed concepts and methods in PN theory. It leads to a distributed and hierarchical model of MMS software system by integrating service connection PNs. A generalized stochastic PN for MMS performance evaluation is obtained by incorporating service parameters and time factors into the model. A technique based on T-invariants is used to simplify the performance analysis     

A modeling and analysis methodology for modular logic controllersof machining systems using Petri net formalism

Logic controllers for machining systems typically have three control modes: auto, hand and manual. In this paper, a unified formal representation of logic controllers with three control modes is provided using Petri nets (PNs). A modular logic controller structure is introduced and formalized for high-volume transfer lines. The modular logic controller consists of one control module for the mode decision and other control modules for station logic controllers. Each station control module is represented by connecting together operation modules, which are designed with respect to the fault recovery processes of operations; their connection algorithm is also provided. In our formal representation, each control module is represented by a live, safe and reversible PN. A condition for the modular logic controller to generate a correct control logic is provided: the operation causality condition. Using the modular structure of a logic controller, the control logic can be easily reconfigured and automatic code generation is possible     

基于时间Petri网的公文管理工作流模型

工作流建模是公文管理系统开发的重要课题,但以往的文献中却很少考虑公文流管理过程中的时间因素。所以结合高校公文管理工作流的实际应用环境,提出基于时间Petri网的公文管理系统工作流模型,并利用四种基本工作流模型的线性时间推理规则,对其进行时序分析,在线性时间复杂度内解决时间推理问题,用具体数据分析了公文管理工作流模型的性能。对实际公文管理系统的开发具有指导作用。     

Enumeration of all simple paths in a directed graph using Petri net: A systematic approach

The determination of all simple (or success) paths between two specified nodes in a directed graph finds various applications in graph theory, reliability evaluation of a system, etc. Many attempts at the problem of determining the S-T paths (simple or success paths between specified nodes S and T) have appeared in the literature [1–3]. The present paper, which utilizes the concept of the Petri net (PN), is yet another attempt at the same problem. The proposed technique is simple and tackles the problem in a systematic way. It is amenable to computer implementation.     

基于扩展Petri网的ECA规则集表示及终止性分析

为了提高ECA规则集可终止性分析的准确性,建立了一种可描述ECA规则集的扩展Petri网(EPN, extended Petri net)模型,在此基础上研究并提出了一种ECA规则集终止性判定算法。该算法充分利用EPN网所包含ECA规则特性的丰富信息,综合分析了ECA规则特性对规则集可终止性的影响。理论分析和实验结果表明,所提出的算法具有更高的准确性和更低的时间复杂度。     

基于Petri网的攻击检测模式的优化生成算法

本文介绍了基于Petri网的入侵检测系统的概念,指出了这种方法所面临的主要困难是状态的组合爆炸,由此提出了通过将入侵模式Petri网和应用约束Petri网进行合成操作,从而减小无用状态的优化算法。     

Modeling and emulation of a furnace in IC fab based oncolored-timed Petri net

In integrated circuit (IC) manufacturing, the wafer processing takes more time in furnaces than other equipment. How to effectively integrate furnaces with other automated machines is very important. In particular, using the real furnace for testing not only introduces trouble but also wastes time. This paper aims to model and construct an emulation environment for the furnace. The colored timed Petri net (CTPN) is used to model the furnace. Based on CTPN, the dynamic behaviors of the furnace, such as loading, processing, unloading and wafer count mismatching, can be emulated. The proposed CTPN model is hierarchical and modular. The hierarchical architecture is built by dividing the behaviors of the furnace to make the model more compact and the modular modeling makes the model flexible and easy to use. On the other hand, the furnace emulator provides a quasi environment for testing so that potential problems of the system can be detected in advance and the testing time can be economized     

A simulation approach based on negotiation and cooperation betweenagents: a case study

Presents AGENDA (A GENeral testbed for Distributed AI Applications), a simulation tool developed for the simulation and design of applications involving interacting entities. This testbed consists of two different levels, the architecture level and the system development level. The architecture level describes a methodology for designing software agents by providing several important functionalities an agent should have. On the other hand, the system development level provides the basic knowledge representation formalism, general inference mechanisms, and a simulation tool-box supporting visualization and monitoring of agents. Following this, the applicability of AGENDA to the transportation domain is presented in detail. The main challenge of AGENDA in the context of this domain has been to provide different cooperation-scalable methods based on negotiation, leading to different scheduling mechanisms, and to experimentally evaluate these mechanisms. This evaluation shows that: (1) AGENDA is suitable for realistic application in the transportation domain; (2) the mechanisms used for vertical negotiation (between trucks considered as agents) and for horizontal negotiation (between companies considered as agents) are applicable for the real-world transportation domain applications. Finally, a complete study of the scalability of the simulation tool and the algorithms used for the negotiation is presented. This study, along with the evaluation of the different mechanisms, can help designers of transportation companies, particularly in the case of large companies     

Petri nets and integrality relaxations: A view of continuous Petri net models

Petri nets are formalisms for the modeling of discrete event dynamic systems (DEDS). The integrality of the marking and of the transitions firing counters is a clear reflection of this. To reduce the computational complexity of the analysis or synthesis of Petri nets, two relaxations have been introduced at two different levels: (1) at net level, leading to continuous net systems; (2) at state equation level, which has allowed to obtain systems of linear inequalities, or linear programming problems. These relaxations are mainly related to the fractional firing of transitions, which implies the existence of non-integer markings. We give an overview of this emerging field. It is focused on the relationship between the properties of (discrete) PNs and the corresponding properties of their continuous approximation. Through the interleaving of qualitative and quantitative techniques, surprising results can be obtained from the analysis of these continuous systems. For these approximations to be "acceptable", it is necessary that large markings (populations) exist. It can also be seen, however, that not every populated net system can be continuized. In fact, there exist systems with "large" populations for which continuation does not make sense. The possibility of expressing nonlinear behaviors may lead to deterministic continuous differential systems with complex behaviors.     

A formal approach to context scheduling for multicontextreconfigurable architectures

In this paper, we analyze the main issues in context scheduling for multicontext reconfigurable architectures from a formal point of view. We first provide an intuitive approach. which is later supported by a detailed analysis of the mathematical relations that express the reconfiguration process. This enables us to deduce a methodology for the minimization of context loading overhead, which considers the tradeoff between achievable system performance and algorithm efficiency. In this respect, the optimality necessary conditions are established in order to contrive an optimal search. However, as this approach is very time consuming we propose some heuristic techniques that reduce the algorithm complexity and accomplish very good results in relatively short execution time. This work has been developed as a part of an automated design environment for reconfigurable systems. A set of experiments has been developed so as to validate the theoretical results