Petri-net based performance-evaluation of distributed homogeneoustask systems

摘要

TG (task graphs) are used to describe the execution of severalntasks under some precedence constraints. Direct evaluation of TGnprovides an average completion time of the overall job, assuming nonlimits exist in the number of processing units and with no regard fornallocation schemes. This paper presents a systematic approach fornevaluating TG of jobs executed under predetermined allocationnconstraints. This extension of TG relies on GSPN (generalized stochasticnPetri nets). A systematic mapping of a TG into a GSPN model isndiscussed. This GSPN model is extended to incorporate information aboutnthe static allocation of the set of tasks in the TG. An algorithm isnimplemented to evaluate static allocation schemes with or without tasknreplication. However, for task replication, a homogeneous system isnassumed because the execution time of those tasks does not change whennallocated to various processing units. Also, under this assumption, tasknexecution rates are modified by adding communication costs involved innsending data required by the next task, in turn, to execute. Thus, usingna single model, TG are evaluated with constraints not only on wherenreplicated and nonreplicated tasks are to be executed but on the numbernof processing units available, task allocation constraints, and thencommunication costs involved when they are remotely located