Task Graph & State Diagrams Flashcards
What does a wider task graph imply?
More parallelism
How can we find T1 in a task graph?
The sum of the time cost of all nodes in the graph
What are the nodes in the task graph?
What is in the node?
Nodes are pieces of work the program performs. Each node will have a constant execution time per
task. In most cases we will interpret the execution time per node as 1.
What do Edges represent in a task graph?
What is the meaning of the value in them?
Edges represent that the source node must complete before the target node begins, i.e. there is a
data dependency along the edge.
How is work defined in the task graph?
Work := the sum of the time cost of all nodes in the graph i.e. T1
What is the span in the task graph?
What does it say about infinite processors?
Span is the sum of the time cost of all nodes along the critical, i.e. longest, path in the graph. The span determines the best possible execution time we can achieve by introducing more processors, i.e. T(inf)
How can we calculate the infitie speedup (T(inf)) when only seeing the task graph?
We know Sp := T1 / Tp
T1 := Sum of time of all nodes
Tp here Tp is Tinf := Sum of the time cost along the critical path / longest path
See picture
What is the maximal achievable speedup we can gain by parallizing this algorithm?
How many operations can max. be issued in parallel?
What does this mean for Tinf?
T1 is dened as the sum of the time cost all nodes in the graph, which in this case would be 79. We can compute T1 as the sum of the time cost of all nodes along the critical path, which we see is 29. As a final result, we thus obtain
Sinf = 79 / 29 = 2.72
We recognize from the width of the graph that we can issue at most 8 operations in parallel. This
means that we achieve Tinf with 8 processors, i.e.
S8 = Sinf
What does a state diagram visualize?
The different states and state transitions between them that a program might go through
Give lower and upper bound on execution times.
Using: Tp and T1
Lower bounds: Tp >= (T1/Tp) >= Tinf
Upper bounds: Tp <= (T1/Tp) + Tinf
What is the maximum speedup of a Taskgraph and how do you find the values?
max. Sp = T1 / Tinf
T1 := sum of all nodes and their execution times
Tinf := sum of the nodes and their exeution times along the critical path
Look at the picture. How do we see that mutual exclusion is satisfied, generally and in this case.
Only 1 thread can be in the critical section at one time. We see this by making sure that p3,q3 as a node doesnt exist.
Look at the picture. How do we make sure deadlock freedom is satisfied. Generally and in this case?
There is no deadlock in the example. But we can find it by finding a state (state is a node) where we cannot go anywhere else. You are stuck on this node there is no arrow going out from the node
What you can also do mark all states where the processes are about to enter the critical section. In the example p2 and q2. And there must be at least one arrow allowing one of the processes to enter the CS.
How do we identify a Livelock in a State Diagram. Livelock is kinda like a Deadlock only that is acts as a loop. Deadlock nothing more happens you are just blocked in a Livelock you have transitions.
If the state diagram contains a path which will lead you back to the same state and you are than stuck in that loop, keeping on returning.
Can we see if starvation freedom is satisfied by looking at the state diagram if yes why?
No we cant say for sure if there is starvation freedom. In the picture we see two states where if only the process Q (only that thread continues) would be in use we would be stuck in that state due to the while loop being represented.
We can say there might be a possibility of starvation in those two states depending on the fairness implemented in the algorithm. If the algorithm is fair at some point p1 would move to p2 and if that happens we have starvation freedom otherwise not.
1) Can this program deadlock?
2) Can this program livelock?
3) Does this program provide mutual exclusion?
4) This program is wait-free?
1) False. A deadlock would imply a state that can be reached but never can be left to reach a critical section again. Since all reachable states have a way of continuing in such a way that they reach a critical section eventually, there are no deadlocks.
2) False: When there exists a cycle of state transition, with none of the states are in CRITICAL SECTION, there can be livelock. (This follows directly from definition of livelock : “Livelock is a condition that takes place when two or more programs change their state continuously, with neither program making progress”)
3) True. The critical sections p2, q2 are never active at the same time.
4) Program is not wait free, because if it were, a thread should be able to make progress whilst another one is not executing. But for example at
p1 q1 0 if p wouldn’t execute, there is no way that q could make progress i.e. not wait free.
Assume p and q both execute a code which is 100 instructions long. The variable n is a 32-bit integer. If we use the notation introduce above, what is the maximum number of state in the state diagram?
Assuming no restrictions like mutual exclusion, there are
100 * 100 * 2^32 possible states.
