Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

i have a question regarding this exercice in exam 14_02_2022 parallel computing . Here the execution should be PRAM consistent , we can do a consistent sequentialization for Q : q1 < q2 < p2 < p3 < q3 because in PRAM consistency model we dont respect write to order or programm order , i thought thats only for Causal consistency so i dont see why here the execution is not PRAM consistent ?

Thank you in advance .

in * TF "Emb. Sys. and Rob." by (120 points)

1 Answer

0 votes

For PRAM consistency, we consider the actions with their program order but have no need to order all actions into a single total order as required for sequential consistency. Instead, each thread may have its own different view on the ordering of the actions, but also for these local views, we have to respect the write order of the other threads.

To be more precise, if you consider the definition of PRAM consistency on slide 79 of the related chapter, you see that we consider Rstr(<=P,A(p)∪A(write)) which means that we consider all actions A(p) of thread p, and all the write actions A(write) of the other threads, and we respect their program order <=P. 

In the example, threads P and Q have the following actions:

    p1: read(x,3)
    p2: write(x,1)
    p3: write(y,2)
    
    q1: read(y,2) 
    q2: write(x,3)
    q3: read(x,1)

For checking PRAM consistency, we need to add the write actions of the other thread(es) to the actions of each thread. For thread P, this is no problem:

    q2: write(x,3) 
    p1: read(x,3) 
    p2: write(x,1) 
    p3: write(y,2)

For thread Q, we must add p3 in before q1 since otherwise, there is no reason why q1 may read value 2 from y. But then, p2 must even occur before p3 since we have to respect the ordering of the write actions of thread P. However, then, which is consistent with the value read by q1. But then, variable x will be initialized with 1, and this becomes a problem for q2:

    p2: write(x,1)
    p3: write(y,2)
    q1: read(y,2) 
    q2: write(x,3)
    q3: read(x,1)
The above is the only possibility, and it is not consistent.
by (170k points)

Related questions

0 votes
1 answer
+1 vote
2 answers
+1 vote
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...