In: IEEE Trans. on Reliability, Vol. 49, No. 2, pages 188-198. 2000.
Abstract: TGs (task graphs) are used to describe the execution of several tasks under some precedence constraints. Direct evaluation of TGs provides an average completion time of the overall job, assuming no limits exist in the number of processing units and with no regard for allocation schemes. This paper presents a systematic approach for evaluating TGs of jobs executed under predetermined allocation constraints. This extension of TGs relies on GSPNs (generalized stochastic Petri nets). A systematic mapping of a TG into a GSPN model is discussed. This GSPN model is extended to incorporate information about the static allocation of the set of tasks in the TG. An algorithm is implemented to evaluate static allocation schemes with or without task replication. However, for task replication, a homogeneous system is assumed because the execution time of those tasks does not change when allocated to various processing units. Also, under this assumption, task execution rates are modified by adding communication costs involved in sending data required by the next tasks, in turn, to execute. Thus, using a single model, TGs are evaluated with constraints not only on where replicated and non-replicated tasks are to be executed but on the number of processing units available, task allocation constraints, and the communication costs involved when they are remotely located.
Keywords: communication costs, distributed systems, performance evaluation, stochastic Petri nets, task allocation, task graphs.