3.9k views

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d,$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

1. $2$
2. $9$
3. $5$
4. $3$
edited | 3.9k views
+1
is it in syllabus??
0
no sushmita
+1
Thanx sir.
+6
yes , it is in syllabus
gate 2017 asked almost same question .
+6
+2
yeah i wish they had not officially removed it from syllabus and then ask question.
0
Expression tree is evaluated in any order not necessary left to right.

Given is Load Store Architecture, that means we can access memory using Load and Store Instructions.

Key Idea:- Pick new register only when it is required.

We want to add c and d, and initially both are in memory, therefore copy these into registers.

• load $R1, c$    $(R1 \leftarrow c)$
• load $R2, d$   $(R2 \leftarrow d)$

(here no compensation can be done, we need two registers)

• add $R1, R1, R2 \ ( R1 \leftarrow R1 + R2)$

(at this point $R1$ is holding $\mathbf{c+d}$ and $R2$ is holding $\mathbf{d}$, i.e. $R1 \leftarrow \mathbf{c+d}$  and $R2 \leftarrow \mathbf{d})$
Now, $\mathbf{e}$ comes into picture and my question is, Can i make use of $R1$ or $R2$ to store $\mathbf{e}$?
I can not use R1 to store e as its value will be needed later but I can use R2.

• load $R2, e$

(currently $R1 \leftarrow \mathbf{c+d}$  and $R2 \leftarrow \mathbf{e})$

• Sub $R1, R2, R1$  $(R1 \leftarrow R2 - R1)$

Doing this all gives, final value of right sub-tree is stored in $R1$, and $R2$ stores $\mathbf{e}$.
Now, coming to left subtree, to perform "$a-b$" we need to copy both variables in registers.
We can copy one of the variable in $R2$, but we can not obviously copy in $R1$ as value of $R1$ will be required later.

• Load $R2, a$
• Load $R3, b$ (here comes extra register, and we can not avoid using it.)

Current mapping is $R2 \leftarrow a$, $R3 \leftarrow b$ and $R1$ contains final value of Right subtree.

• SUB $R2, R2, R3 (R2 \leftarrow R2 - R3)$
• ADD $R1, R1 , R2$

Hence answer is $3$  i.e. D

edited by
0
sachin sir, why you started with c+d, if the expression is (a-b)*(e-(c+d))

can we do it any way to get the minimal number?
+1

 Register 1 Register 2 Register 3 c c d c+d d c+d e c+d e-(c+d) a e-(c+d) b (here we need new register to load b) a-b e-(c+d) b (a-b)+(e-(c+d)) e-(c+d) b

0
sethi-ullman algorithm can be used to get the answer fast and correctly.
0

can you please explain when to use sethi Ullman algo?

0

@soumayan bandhu-No.Sethi Ullman Algorithm also gives the answer as 3.

If you have any doubt, then try writing code and check whether you missed any value or not.

0

Oh,yes.

@Ayush Upadhyaya but I found some other previous questions where this algorithm is not worked, actually gives less number of registers.

0
Okay, just paste the link of that question in which you are having problem and we shall discuss that algorithm on it.So, it should be clear. :)
R1<- -c,  R2<- -d,  R2<- -R1+R2,  R1<- -e,  R2<- -R1-R2

To calculate the rest of the expression we must load a and b into the registers but we need the content of R2 later.  So we must use another register. R1<- -a,  R3<- -b,  R1<- -R1-R3,  R1<- -R1+R2

Ans D
0
cant it be evaluated like this? First, evaluate the right sub-tree of the root as stated. Then add 'a' to one of the registers and then load 'b' in other register. By this, we have already met the condition that both the operands must be in register.

So, ANS = 2 , right?
+2
In load-store architecture i.e. RISC architecture, you cannot directly add contents of a memory location i.e. a to contents of a register. You first have to bring the content into a processor register.
0
@bleed red.

As Keith has stated, evaluate the contents of right subtree in R2.

Now, R1 is free.

Now, expressions to be evaluated is a-b+R2.

So, load 'a' in R1, then add R2 to it and then subtract 'b'.

It seems logical but I dont know if its valid for the parser.
+2

I know that my answer is wrong according to official key.I have applied labelling algorithm for this problem by which i am getting 2 registers.why we cant apply labelling algorithm(Complier design).when to apply and when not to..please clear the idea

@Bikram Ballav

@Sushant Gokhale

@Keith

0

@amit

almost same example is given, just differ in - and + symbol in the tree

slide number 19

http://people.cs.vt.edu/ryder/415/lectures/codeGeneration.pdf

+3

@amit

This question , answer is 3 registers

As in qstn say no intermediate result store in memory only register can be use

to add "b" and R1, we first have to copy "b" to some register R2

because "b" is in memory

and we can not access memory using "add", as it is Load-Store architecture, and memory can be accessed using load and store instructions only . I mean for Load and Store purpose only .

as we copy b to another extra register

that's why 3 register require [ after applying Sethi-Ullman algorithm] .

The instructions produce result only in a register. If no intermediate results can be stored in memory,

Because of this line we need to use one extra Register.

+1

"The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers"

I think because of this line we are getting the result as 3 because in slide 19 of the above pdf they are direclty doing arthmetic operation without even coping both operands to register for e.g add b,R1(Line No 2)

+1
@akb1115

In load-store architecture we cannot directly add contents of a memory location  to contents of a register.  We  first have to bring the content into a processor register . That's why 1 extra register needed .
+1
one more thing , we can say or as given above pdf , we cant use same destination register as oprand ... in labelling algo , so we should consider this one also to solving this ... so here we need extra 1 register ..rt?
+1

yes correct.

0

So, we can use Labelling Algorithm with some modification. Instead of labeling right leaf node=0, need to label it with 1. After applying the algorithm, we get 3 register.

Please comment if my understanding is correct.

+1

Why you assigned 0 to b and d.

In Sethi ullman algo,we have to assign 1 to every variable.

see below

https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm

Traverse the abstract syntax tree in pre- or postorder

1. For every non-constant leaf node, assign a 1 (i.e. 1 register is needed to hold the variable/field/etc.). For every constant leaf node (RHS of an operation – literals, values), assign a 0.
2. For every non-leaf node n, assign the number of registers needed to evaluate the respective subtrees of n. If the number of registers needed in the left subtree (l) are not equal to the number of registers needed in the right subtree (r), the number of registers needed for the current node n is max(l, r). If l == r, then the number of registers needed for the current node is r + 1

using dependency graph coloring algorithm
+1
@ankltrokdeonsns

Can u Draw it.? If u can then plzz draw it..it will be helpful for us
+1
can u explain this algorithm?
r1 = c
r2 = d
r1 = r1 + r2 (r1 = c + d)
r2 = e
r1 = r2 - r1 (r1 = e - (c + d))
r2 = a
r1 = r1 + r2 (r1 = a + (e - (c + d)))
r2 = b
r1 = r1 - r2 (r1 = (a + (e - (c + d))) - b)

Now, the above expression is equivalent to (a-b) + (e - (c+d)) as "addition" and "subtraction" are both commutative and associative.

Please correct me if I'm wrong.

1