2
$\begingroup$

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have $x$ threads that can execute those tasks.

Is there a (simple) formula to determine the response time (or at least an upper bound) for the given setup using any work-conserving scheduler?

Improve this question
$\endgroup$
2
  • $\begingroup$ @Apass.Jack Please post the link if you find it. I am quite curious about the answer. $\endgroup$
    – Optidad
    Commented Apr 4, 2019 at 15:24
  • $\begingroup$ This seems like a variant of Job shop scheduling. My suspicion is that this may be NP-complete. See also this for your variant. $\endgroup$
    – ryan
    Commented Apr 4, 2019 at 18:00

2 Answers 2

Reset to default
4
$\begingroup$

Found it! This problem is NP-complete when the goal is to minimize total execution time.

The scheduling problem (P1) is the following. We are given

(1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs,

(2) a partial order $\prec$ on $S$,

(3) a weighting function $W$ from $S$ to the positive integers, giving the number of time units required by each job, and

(4) a number of processors, $k$.

Please see the following paper, which immediately discusses it from the introduction onward:

J.D. Ullman. Np-complete scheduling problems. Journal of Computer andSystem Sciences, 10(3):384 – 393, 1975.

There are a few other cases that may be of interest that are discussed in the paper:

  • When $\prec$ is empty (no edges in the DAG)
  • (P2) When $W(J_i) = 1$ for all $i$.
  • (P3) When $k = 2$ and $W(J_i) \in \{1, 2\}$ for all $i$.

You can show 3-SAT reduces to (P2) through and intermediate problem (P4) that Ullman discusses. Then it is clear that (P2) reduces to (P1).

Improve this answer
$\endgroup$
2
$\begingroup$

A simple upper bound on the response time, for any work-conserving scheduler, is $$\frac{\mathit{vol} - L}{x} + L,$$ where $\mathit{vol}$ is the sum of all the execution times and $L$ is the sum of the execution times along a critical path in the DAG.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It is a nice upper bound that can be applied on sub-problems to be refined. $\endgroup$
    – Optidad
    Commented Apr 5, 2019 at 8:24
  • $\begingroup$ @Pontus Do you have a source for this upper bound? $\endgroup$
    – Mike van Dyke
    Commented Apr 8, 2019 at 11:28
  • $\begingroup$ @MikevanDyke: Sorry, I'm not sure what the original source is. It is easy enough to prove though. The key observation to make is that whenever any machine/thread is idle, all maximal paths in the DAG must be shortened. So at all times we either get to exploit full parallelism, or we get to shorten the critical paths. In practice it can of course happen that we do both at the same time, which is why this is an upper bound. $\endgroup$
    – Pontus
    Commented Apr 9, 2019 at 18:12
  • $\begingroup$ In case someone is interested, I found a source on this upper bound $\endgroup$
    – Mike van Dyke
    Commented Sep 27, 2019 at 11:29
  • 1
    $\begingroup$ Thanks, @MikevanDyke. I would think that this was known long before 2004, though. $\endgroup$
    – Pontus
    Commented Sep 28, 2019 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.