##### number of registers

for the code below

a=b+c

c=a+b

d=b+c

e=d-b

a=e+b

___ number of registers to be allocated by the graph coloring algorithm?

ROHAN MUKHERJEE
4 Feb 2015 10:41 pm

Minimum 2 register needed

Arul
4 Feb 2015 10:34 pm

I think, only 2 registers are needed at any time.

Saptarshi pal
5 Feb 2015 09:27 am

Form a graph such that the vertices are a,b,c,d,e. There will be an edge in between the vertices if there is a binary operation in between them. This simply means that if there is an operation between 2 variables they cannot be in the same register, hence they cannot have the same color. So putting an edge in between them reduces the problem to graph coloring problem.

Saurav Das
6 Feb 2015 10:57 am

so that's good for ohne statement, how to draw for all of them a=b+c, and say c=a+b?

Saptarshi pal
6 Feb 2015 11:19 am

For a=b+c draw three nodes and connect (b,c). Then for c=a+b connect (a,b). So it forms a bipartite graph. So two colors required for coloring. Hence we can say that 2 registers are good enough for these operations.

In the register way

take b and c in a register. Add b+c and put it in c. Now perform a+b but a is in c. So it is just c+b and then put the result in c or b.