StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First, note that "threads" mentioned in the slides are not like OS threads as one may think. Their definition of a thread is given at slide 10: <code>"a maximal sequence of instructions not containing parallel control (spawn, sync, return)"</code>. To avoid further confusion, let me call it a task instead.</p> <p>On slides 32-35, a circle represents a task ("thread"), and edges represent dependencies between tasks. And the sentences you ask about are in fact definitions: when P or more tasks are ready to run (and so all P processors can be busy doing some work) the situation is called a complete step, while if less than P tasks are ready, the situation is called an incomplete step. To simplify the analysis, it is (implicitly) assumed that all tasks contain equal work (of size 1).</p> <p>Then the theorem on the slide 35 provides an upper bound of time required for a greedy scheduler to run a program. Since all the execution is a sequence of complete and incomplete steps, the execution time is the sum of all steps. Since each complete step performs exactly P work, the number of complete steps cannot be bigger than T1 (total work) divided by P. Then, each incomplete step must execute a task belonging to the critical path (because at every step at least one critical path task must be ready, and incomplete steps execute all ready tasks); so the overall number of incomplete steps does not exceed the span T_inf (critical path length). Thus the sum of T1/P and T_inf gives an upper bound on execution time.</p> <p>The rest of slides in the "Scheduling Theory" section are rather straightforward.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload