## 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
Full Text: