edited by
14,787 views
49 votes
49 votes

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 by

7 Answers

Best answer
84 votes
84 votes

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
29 votes
29 votes
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
5 votes
5 votes

$(a-b)+(e-(c+d))$

$Load\ R0\leftarrow a$

$Load\ R1\leftarrow b$

$Sub\ R0\leftarrow R0-R1$

$Load\ R1\leftarrow c$

$Load\ R2\leftarrow d$

$add\ R1\leftarrow R1+R2$

$Load\ R2\leftarrow e$

$Sub\ R2\leftarrow R2-R1$

$add\ R0\leftarrow R0+R2$


$Ans: 3$

3 votes
3 votes
answer - D

using dependency graph coloring algorithm
Answer:

Related questions