# Execution process with properties of relations

So, I had a quiz last night in my discrete structures class and this question came up:

"There are 3 processors in a computer. The instructions to a computer are labeled 1,2,3,4,5,6,7,8,9,10 each taking 1 second to execute. The relation between a pair of instructions (x,y) is given by R:'x' is executed at the same time or before 'y'. Using the properties of relations, design an execution process including the sequence of execution that takes the minimum time. Relation between the instructions is R={(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9)(10,10)(1,7)(5,8)(2,3)(8,10)(5,10)}"

How would I go about solving this? I want to understand how to do it....but I don't know where to start...

-

I dont think so. youve got the first instruction called more than once. ive got this:

P1: 1 | 4 | 7 | 10

P2: 2 | 5 | 8

P3: 3 | 6 | 9

Its simple. It only takes four seconds, and all the relationships are satisfied. It is partial order (transitive, reflexive, and antisymmetric) so there is more than one right answer. Also, the 10 could be executed by any of the processors.

-
I sat in tutoring for 40 minutes trying to figure this one out with our tutor. We had 20 minutes to take the quiz. I'm not sure how anyone could have got this right.. – user7988 Mar 9 '11 at 21:32

The interesting part of $R$ is \begin{align*} &1 \leq 7 \\ &2 \leq 3 \\ &5 \leq 8 \leq 10 \end{align*} Missing are $4,6,9$.

Does that help?

-
So, would the sequence be (1,7)(2,3)(4,4)(5,8)(8,10)(6,6)(9,9)? – OghmaOsiris Mar 9 '11 at 7:00
The execution process is not a list of pairs, rather a list of which processor runs what instruction at each point in time. – Yuval Filmus Mar 9 '11 at 13:09
So: 'Processor1-1,2,4,5 ,6,9 Processor2-7,3,.,8 ,.,. Processor3-.,.,.,10,.,.?' – OghmaOsiris Mar 9 '11 at 16:49
Remember you want to minimize the total time. I have a solution that works in 4 seconds versus your 6 seconds. – Yuval Filmus Mar 9 '11 at 17:13
So: \begin{align*} P1: 1, 2, 4, 5 \\ P2: 1, 3, 6, 8\\P3: 7, ., 9, 10\end{align*} – OghmaOsiris Mar 9 '11 at 19:39