Banino, C.; Beaumont, O.; Legrand, A.; Robert, Y. Scheduling strategies for master-slave tasking on heterogeneous processor grids. (English) Zbl 1048.68533 Fagerholm, Juha (ed.) et al., Applied parallel computing. Advanced scientific computing. 6th international conference, PARA 2002, Espoo, Finland, June 15–18, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43786-X). Lect. Notes Comput. Sci. 2367, 423-432 (2002). Summary: In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous “grid” computing platform. We use a non-oriented graph to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We show how to determine the optimal steady-state scheduling strategy for each processor.Because spanning trees are easier to deal with in practice, a natural question arises: how to extract the best spanning tree, i.e. the one with optimal steady-state throughput, out of a general interconnection graph? We show that this problem is NP-Complete. Still, we introduce and compare several low-complexity heuristics to determine a sub-optimal spanning tree.For the entire collection see [Zbl 0997.68670]. Cited in 2 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems Software:HTCondor MW PDFBibTeX XMLCite \textit{C. Banino} et al., Lect. Notes Comput. Sci. 2367, 423--432 (2002; Zbl 1048.68533) Full Text: Link