Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.