A petri net based tool for the analysis of task graph systems

Abstract

The goal of this research is to develop a software tool for the analysis of task graph systems with a graphical user interface. PN's directly incorporate the topological information of the input task graph and also accommodate means to include parameters such as the processor heterogeneity, allocation schemes, communication costs, and random execution times. A technique for the analysis of a task graph systems using PN's has been reported in [6]. The methodology described in this thesis provides a graphical user interface tool for the analysis of the task graph system. The technique reported in [6] and [14] has been used in this thesis for the numerical and simulation analysis of the input task graph systenL The limitation of the numerical method of analysis is that tasks having only exponentially distributed execution times can be analyzed. This restriction is overcome in the simulation method of analysis where tasks having normal distributions can also be analyzed. The results from the numerical and simulation analysis are used to validate the tool. The software is implemented using JAVA. In this thesis three allocation heuristics are also implemented. The allocation heuristics are part of the topology of task graph systems. The Petri net tool generates the allocation of the tasks onto the processors. The software tool is called TASK GRAPH SYSTEM ANALYZER (TGSA). Furthermore, the implementation methodology of the present thesis can also be easily adapted to accommodate additional methods of analysis that use the same topology for the task graph system. Additional factors that could help in the study of task graph systems can also be incorporated.