PETRI NET APPROACH TO DESIGN AND DEVELOPMENT OF MODERN COMPUTER SYSTEMS

Abstract

Petri nets (PN) have aroused considerable interest during the recent years as a model, primarily to represent and study concurrent systems. This thesis deals with the PN approach to design and development of modern computer systems. In particular several aspects of the development of PN theory, its applications to some problems of computer systems and to the problem of optimization in microprogrammed computers have been proposed. Much of the available work on PN is scattered over various reports, dissertations and journals. The review chapter brings together the existing literature in a coherent manner so as to aid a reader in subsequent chapters. The design and development of a system demand that a knowledge about' bhe model be known .For this reason, the reachability tree technique and state equation for Petri nets have been proposed by earlier researchers. However, there are many unsolved problems in PN theory. For example, analysis of large PN i s generally cumbersome or even impracticable. It is possible to build complex nets with desired properties from smaller nets, the analysis of which can easily be managed. This involves interconnection of nets. It is shown in this thesis how smaller nets could be connected in cascade or in parallel to preserve same properties. 4 state equation approach has been exploited for this purpose.

Another well-known problem concerning the analysis of PN is the lack of information of firing sequences and existence of spurious solutions of corresponding state equations. This problem is studied and an algorithm is proposed to find minimal legal firing sequenc.es to transform a given marking into another given marking. It is a well established fact that PN can not model, as such, systems in which interruption or priorities are involved. Many extensions have earlier been proposed but they are either too specific or provide inadequate analysis technique. In this thesis such limitations in modeling capabilities of PN are overcome by proposing an inventor transition in which the token at output place is the complement of the token at input place. All the logic operations have been modeled by PN with additional invertor transitions. To analyse these, a generalized state equation is developed. It is also shown that state equation of PN proposed earlier by Murata is a special case of generalized state equation. The state equations of Petri net appear to be very power ful. Many problems of computer science, for example, the enume ration of simple paths between two modes of graph, the terminal reliability of a computer network and program complexity evaluation are formulated in the framework of state equations and solutions for them proposed. Of significant importance in the design of microprogrammed computers are microprogram optimizations. They are called for to reduce the cost of the system and to increase the efficiency.

In this thesis, only bit optimization in control memory and data path optimization are taken up because of their practical utility. In the bit optimization all the maximal compatible classes of microcommands are generated using the PN state equation. From the se^ minimal bit solutions are obtained. The possibility of further reduction in bits, is also looked into by employing bit steering through extended PN concept. Two approaches are proposed in this thesis to solve the problem of data path optimization. In the first approach the concept of invariance in PN is employed and solutions which include all the minimal cost solutions, are obtained. In the second approach the problem is reformulated in PN domain. The places of PN are then merged according to defined rules and minimal cost solution obtained. Finally, the results are summarized and some suggestions alongwitii critical discussions for further work are given.