Ganta diagram and planning

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 7 · page 7.2
Ganta diagram and planning
How do you share the tasks between processors so that everything can be done faster?
Ganta diagram
It's a visual way of showing what processor does at every point in time.
The EGE No. 22 presents challenges for process planning, assembly processing, dependency graphs and Amdal law, which will teach each type to decide.
GEF · Deepened
EGE No. 22
01
What's Ganta's diagram?
Visualization of the task schedule on processors
EGE No. 22
Definition
Ganta diagram
is a horizontal time scale where each line represents a single processor (or resource) and the colour blocks show what the task is at each point in time.
A simple example
So let's say there are three independent processes:
A = 5 с
,
B = 3 с
,
C = 4 с
and two processors.
Option 1:
P1 = {A(5), C(4)} = 9 s, P2 = {B(3)} = 3 s. Total time =
9 s
.
Option 2:
P1 = {A(5)} = 5 s, P2 = {B(3), C(4)} = 7 s. Total time =
7 s
.
Option 3:
P1 = {A(5), B(3)} = 8 seconds, P2 = {C(4)} = 4 seconds. Total time =
8 s
.
Rule
Optimal schedule minimizes
maximum
The time to load any processor (makespan).
Lower estimate (lower score)
The minimum time available shall not be less than:
⌈Сумма всех времён / N⌉
- if the download was perfectly even.
max(время одного процесса)
- The longest process cannot be separated
In our example: *12/2 ~ = 6, max = 5. Lower estimate = max(6) (5) =
6
But it wasn't possible to reach 6 -- the best option is 7.
Decision algorithm
1. Calculate the amount of all time and the lower estimate.
2. Try to distribute the tasks so that the load is as even as possible.
3. Start with the longest processes, which are more difficult to "mount".
4. Check: If a makespan = a lower estimate, it is certainly optimum.
The Greedy Algorithm (LPT – Longest Processing Time First)
So sort out the processes of time loss. Each next process should be assigned to the processor that will be released first. This does not always give optimum, but usually close to it.
P1:
P2:
A (5 (c)
B (3 (c)
C (4c)
0
2
4
6
8 s
P1 = {A} = 5 s, P2 = {B, C} = 7 s ~ makespan = 7 seconds
Figure 1.
Ganta diagram: optimal schedule for A(5), B(3), C(4) on 2 processors
02
Conveyer handling
How to speed up processing by breaking the task at stage
EGE No. 22
The idea of a conveyor
Instead of processing every command in its entirety and then taking the next one, we break the processing into
Phase
As long as one team passes stage 2, the next team is already in phase 1.
The analogy is that the conveyor at the factory, while one car is painted, the other one is going, the third is going through quality control.
Key formula
Conveyer formula
T = Σtᵢ + (n − 1) · max(tᵢ)
Where:
Σtᵢ
- The sum of all stages (the time of the first team)
max(tᵢ)
- time of the slowest stage ("narrow spot")
n
- Number of teams
Why is that?
The first command has to go through all stages in sequence: it takes
Σtᵢ
Then each next command comes out at intervals.
max(tᵢ)
- because the conveyor can't make more teams than the slowest stage works.
Example
3-stage conveyor: 2 ns, 4 ns and 3 ns.
Σtᵢ = 2 + 4 + 3 =
9 ns
(first team)
max(tᵢ) =
4 ns
(stage 2 is a narrow space)
Another 7 commands: 7 x 4 =
28 ns
Total: 9 + 28 =
37 ns
Comparison with consistent implementation
No conveyor: 8 command x (2+4+3) = 8 x 9 =
72 ns
.
With the conveyor:
37 ns
I. Accelerating: 72/37
1.95 times
.
The larger the commands, the closer the acceleration to the number of stages (but never more than it).
Private case: All stages are the same
If all
k
The stages are long.
t
ns, the formula is simplified:
T = (k + n − 1) · t
Example: 5 stages of 1 ns, 100 command t = (5 + 100 - 1) × 1 =
104 ns
.
Reverse task
"How many teams will work for T's?" "Say n from the formula:
n = (T − Σtᵢ) / max(tᵢ) + 1
(round down)
03
Relationships between tasks
When tasks cannot be performed arbitrarily
EGE No. 22
Dependency Count (DAG)
Often the challenges are: task B cannot start until task A is completed.
Acyclic-oriented graph
(DAG).
A → B
means B depends on A, B does not start before A is completed.
Critical Path
Critical Path
- The longest route in the graph from beginning to end.
minimum
The timing of the entire project, even if we have infinitely many processors.
The algorithm for finding a critical path
1. Calculate for each task
early start time.
:
step(X) = max(finish(Y) for all Y x X)
Finland(X) = start(X), + time(X).
2. For start-up tasks (without dependence): start = 0.
3. Response = max(finish(X) for all X).
Example
Tasks: A(3), B(2), C(4), D(5), E(2).
A(3)
B(2)
C(4)
D(5)
E(2)
Figure 2.
Dependency graph: A.C. and B.D.E.
Decision:
A: start=0, finish=3
B: start=0, finish=2
C: start=3 (waiting A), final=3+4=7
D: start=2 (waiting B), Finnish=2+5=7
E: start=max(7.7)=7 (waiting C and D), Finnish=7+2=
9
The critical path is: A.C.E. = 3+4+2 = 9 (or B.D.E = 2+5+2=9). Both tracks are of the same length.
Typical error
You can't just fold up all the time!
parallel
The sum of all times = 3+2+4+5+2 = 16, but the answer is = 9.
04
Amdal Law
Why the infinite number of kernels does not provide infinite acceleration
EGE No. 22
Formula
Amdal Law
S = 1 / ((1 − p) + p / N)
p
- share of parallel code (0 to 1)
N
- number of processors
S
- acceleration (how much faster)
Meaning
Programme part
(1 − p)
- consistent, it can't be accelerated by any number of kernels, it's always done in time.
p
accelerating in
N
One.
Examples
p (para.
N kernels
Acceleration S
Commentary
80%
4
2.5
Of the 4 kernels, 2.5×
90%
10
5.3
10 nuclei only 5.3×
99%
100
≈50
100 nuclei only 50×
50%
1000
≈2
1000 kernels and acceleration only 2×
Theoretical limit
At N ♪ ♪:
S_max = 1 / (1 − p)
If 90 per cent of the code is parallel, maximum acceleration = 1/0.1 =
10 times
even with a million kernels.
The answer is, how many kernels do you need?
Dano: acceleration S, fraction p. Find N.
N = p / (1/S − (1−p))
Example: p=0.9, S=4. N = 0.9 / (0.25 - 0.1) = 0.90.15 =
6 kernels
.
05
Strategy for Decision No. 22 of the EGE
Four types of task and algorithm for each
Type 1: Distribution of independent processes
Algoritm
1. Find the sum of all time and the lower estimate of the sum/N.
2. Sorry for the loss processes.
3. Spread it from the longest to the least loaded.
4. Response = makespan (maximum load).
Type 2: Container
Algoritm
1. Find a sum of stages and max(ti) (narrow place).
2. Apply the formula: T = \ti + (n-1)·max(ti).
3. For the inverse: n = \(T -ti) / max(ti) \ + 1.
Type 3: Dependence (critical path)
Algoritm
1. Draw a list of addictions.
2. For each task: start = max(finish) of all predecessors, Finnish = start + time.
3. Initial objectives: step = 0.
4. Response = max.
Type 4: Amdal Act
Algoritm
1. Identify p (part of the parallel code) and N (number of kernels).
2. Set: S = 1 / ((1 - p) + p/N).
3. For limit: S_max = 1 / (1 - p).
4. For inverse: N = p / (1/S - 1 - p).
EGE traps
• "Independable processes" ~ "dependent" — read the condition carefully.
• Conveyer: \\ti is time
First
A team, not a single stage.
• Dependency: