Modeling parallel computation via the fusion of timed Petri nets with an application to the mapping problem
Linda M. Wilkens · 1992
We present a modeling paradigm based on fusing two separate timed Petri net models. We model parallel computation by modeling an algorithm and an architecture, and by fusing the two models into an executable model of the algorithm loaded onto the architecture. The fused model is executed by token playing, and statistics are collected during execution. We apply the modeling paradigm to solving the mapping problem. Starting with an algorithm expressed as a dataflow graph, and a parallel target architecture, we find an assignment of the nodes of the dataflow graph to the processing elements of the architecture. The goal during the mapping process is to find a low-cost assignment, where cost is total execution time for the algorithm executing on the target architecture, under the assignment found by the mapping process. Both modeling and mapping are achieved by a modeler/mapper environment which features timed Petri net modeling of algorithms and architectures, and feedback between the modeling and the mapping phases. Mapping strategies investigated include partitioning by clustering, and allocation by simulated annealing and by a genetic algorithm. The success of the mapping strategies depends upon both domain-specific heuristics for generating a new assignment from a current assignment, and a cost function which aids in finding mappings with low model execution time.