Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching.

I have a bounded set of operations that need to access a database. I want to create an "execution graph" of these operations that prevents conflicting accesses. For each of this operations, I know the read set and write set.

Let's say I have four operation, a, b, c and d :

readSet(a) = {k1, k2} writeSet(a) = {}

readSet(b) = {} writeSet(b) = {k1}

readSet(c) = {} writeSet(c) = {k2}

readSet(d) = {} writeSet(d) = {}

So here I can build the graphs whit the following set of edges :

g1 -> { (b, a), (c, a) }

g2 -> { (a, b), (a, c) }

How do I build such a graph that is that is as little deep as possible ? ( i.e that maximize the parallelism ? )

What are the keywords to find litterature on this problem ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.