×

Optimal parallel scheduling for the 2-steps graph with constant task cost. (English) Zbl 0741.68021

Summary: We present a parallel scheduling based on the critical path heuristic for the 2-steps graph with constant task cost. This graph occurs in the parallelization of triangular linear system resolution. For a problem of size \(n\) and \(p\) processors \((2\leq p\leq n-1)\), we show the optimality of this scheduling.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI