Algorithm Modelling with Petri Nets - Comparison with Data Dependence Graphs

This article focuses on algorithm representation by means of Petri Nets. The basic structural features of algorithms are dictated by their data and control dependencies. These dependencies refer to the precedence relations of computation that need to be satisfied in order to compute the problem correctly. The absence of dependencies indicates the possibility of simultaneous computations (the fewer dependencies the bigger parallelism). This article presents a modeling strategy, which is coherent for noniterative as well as iterative problems. Weshow that the data dependencies of iterative problems with 'general uniform constraints' can be modelled byanevent graph (marked graph). We distinguish between two modeling approaches - the first based on the problem analysis and the second based on the sequential algorithm for whichweintroduce the term IP-dependencies. Weshow how to simplify the model by reduction of implicit places and self-loop places. Importance of antidependencies and output dependencies is underlined and algorithm transformations based on Petri Net analysis is shown. This original approachallows us to put a knowledge of automatic parallelization via data dependence graphs and Petri Nets to the same theoretical platform and to join the two scientific branches