# GATE2006-43

34 votes
4.6k views

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The  instruction “bbs reg, pos, label” jumps to label if bit in position pos of register  operand reg is one. A register is $32 -bits$ wide and the bits are numbered 0 to 31,  bit in position 0 being the least significant. Consider the following emulation of  this instruction on a processor that does not have bbs implemented.

$temp\leftarrow reg \& mask$

Branch to label if temp is non-zero. The variable temp is a temporary register. For correct emulation, the variable  mask must be generated by

1. $mask\leftarrow \text{0x1} << pos$
2. $mask\leftarrow \text{0xffffffff} << pos$
3. $mask\leftarrow pos$
4. $mask\leftarrow \text{0xf}$

edited
0
i don't understand the question . can anybody elaborate it.
1
We have a 32 bit register, from 0 to 31. 'pos' could be any position from 0 to 31 on the given register, ie if pos value is say 5, that would mean 5th bit of register.

For example take this instruction  "bbs reg1, 5, label1". Consider a set of instruction, label1 being a branch address. If 5th bit on the 32 bit register is 1 then the branch address will be taken, on the other hand if the 5th bit was zero the branch will not be taken instead continuing its current sequence of instructions.

To execute the same instruction in a processor that deos not support bbs we will need multiple instruction, in this case 2 instructions. Suppose mask is a 32bit variable. We need a mask so that the bitwise and of mask and reg will give us 1 or 0 depending on pos and store it in temp. Compare temp value with 0, if true don't take branch, if false take branch to label.

## 4 Answers

38 votes

Best answer
1. $mask\leftarrow \text{0x1} << pos$

We want to check for a particular bit position say $2$ (third from right). Let the number be $0xA2A7$ (last $4$ bits being $0111$). Here, the bit at position $2$ from right is $1$. So, we have to AND this with $0x0004$ as any other flag would give wrong value (may count other bits or discard the bit at position "$pos$"). And $0x0004$ is obtained by $0x1 << 2$ (by shifting $1$ "$pos$" times to the left we get a flag with $1$ being set only for the "$pos$" bit position).

edited by
0
My problem is i did not get the example given by you properly. What is the meaning of wrong value here ? It would be better for me if you can explain this again.

And option a. mask <- 0x1 << pos means mask will get the value ( of 0x1 after left shift by pos times)

Please explain it
0
I have edited the answer- is it clear now?
2
yes sir Thank you.
0
I am not getting the question, what it wants to explain. It's tough for me to understand the answer.
0

@Gupta731 In Layman terms given a bit string, we have to check if string[pos] is set or not. How it is done?

By ANDig the value of that particular position by 1. Option A left shifts one by the position we want to check and it will act as mask.

0
Please someone clear my doubt

$\text{0xA2A7}$ equivalent binary is

$\text{1010 0010 10}\color{Magenta}{1}\text{0 0111}$

Let's say we want to find whether bit at position 5 from right is 1 or not.

That means we need to left shift 5 by 1 then it will become 10 whose equivalent binary is $1010$ then how it is going check bit at position 5
1

@!KARAN

We need to left shift 0x1 by 5 bits not the other way round.

17 votes

This question can be simply frame into bit manipulation question.

We can say that "find the bit is set or not at position "pos" in given register "reg".

So finding the bit is set or not simply we need to perform an "AND" operation with '1' of that bit if result is 0 then bit is not set and if result is not 0 then bit is set. Now if given "pos" is not 0 then we need to left shift 1 by pos ( 0x1 << pos ).

0
Is this in gate syllabus??????
9
If Gate ppl start mentioning such things in Gate syllabus, we will get a 300-400 pages book of syllabus. :)
8 votes
here, bbs reg ,pos, label is given instruction , suppose i m taking position =2 in pos register ,

then, "bbs , reg, pos,label" will take branch when 2nd bit of binary pattern stored in register is 1.

but how to check 2nd bit of 32 bit binary pattern in register reg is 1 or not ?

for that we will perform an operation

reg : ..........0......11 (32 bit operand in binary pattern)

mask: 000........0010(32 bit binary pattern in which 2nd bit is 1)

if AND operation is done b/w reg and mask and 2nd bit of result is 1 and all are 0's then branch is taken otherwise brach is not taken

now , question is asking about which one instruction is used to generate mask.

mask <----- 0x1 i.e. (0001)<<(left shift by given position) POS

after shifting 0010 will be stored in mask (32 bit register ) for that option (a) is correct option
0
Can anybody explain the other options given in the Question?
0
The mask obtained by the other options when anded with register they will not give the POS. Because of which they are incorrect.
2 votes
 bbs reg pos label

$Eg: bbs|r_{0}|3| 2000$

$r_{0}=FCH$

$r_{0}:1111\underline{1}100\ (pos=3)$

$if\ 3^{rd}\ bit: 0\ PC=Sequence\ address$

$if\ 3^{rd}\ bit: 1\ PC=2000$

$temp\leftarrow reg\&mask$

$let's\ Test:$

$1)$

$mask: 00001000$

$r_{0}:\ \ \ \ \ \ \underline{11111100}\ (pos=3)$

$temp:\ 00001000\ (08H)$

$Analysis:$

$In\ pos=3\ we\ got\ 1 // condition\ true$

$In\ temp\ we\ got\ non-zero\ result // condition\ true$

$2)$

$mask: 00001000$

$r_{0}:\ \ \ \ \ \ \underline{11110110}\ (pos=3)$

$temp:\ 00000000\ (00H)$

$Analysis:$

$In\ pos=3\ we\ got\ 0 // condition\ false$

$In\ temp\ we\ got\ zero\ result // condition\ false$

$3)$

$mask: 01101101$

$r_{0}:\ \ \ \ \ \ \underline{11110110}\ (pos=3)$

$temp:\ 01100100\ (64H)$

$Analysis:$

$In\ pos=3\ we\ got\ 0 // condition\ false$

$In\ temp\ we\ got\ non-zero\ result // condition\ true$

Now go through Options

$d)\ mask\leftarrow 0xf: Multiple\ 1's\ in\ mask\ \times$

$c)\ mask\leftarrow pos: Multiple\ 1's\ in\ mask\ \times$

$like\ pos=3(11), pos=5(101)$

$b)\ mask\leftarrow 0xffffffff>>pos: Multiple\ 1's\ in\ mask\ \times$

$a)\ mask\leftarrow 0x1<<pos:\checkmark$

$mask\leftarrow 00000001<<3$

$mask\leftarrow 00001000$

Variable mask must be generated by option $a)$ for correct emulation

Answer:

## Related questions

24 votes
4 answers
1
4.6k views
Consider two cache organizations. First one is $32$ $kB$ $2$-way set associative with $32$ $byte$ block size, the second is of same size but direct mapped. The size of an address is $32$ $bits$ in both cases . A $2$-to-$1$ multiplexer has latency of $0.6 ns$ while a $k-$bit comparator has ... while that of direct mapped is $h_2$. The value of $h_2$ is: $2.4$ $ns$ $2.3$ $ns$ $1.8$ $ns$ $1.7$ $ns$
24 votes
5 answers
2
3.7k views
A CPU has a $32$ $KB$ direct mapped cache with $128$ byte-block size. Suppose $A$ is two dimensional array of size $512 \times512$ with elements that occupy $8-bytes$ each. Consider the following two $C$ code segments, $P1$ and $P2$. $P1$: for (i=0; i<512; i++) { for (j=0; j<512; j++) ... and that for $P2$ be $M2$. The value of the ratio $\frac{M_{1}}{M_{2}}$: $0$ $\frac{1}{16}$ $\frac{1}{8}$ $16$
32 votes
8 answers
3
6.6k views
A CPU has a $32 KB$ direct mapped cache with $128$ byte-block size. Suppose A is two dimensional array of size $512 \times512$ with elements that occupy $8$-bytes each. Consider the following two C code segments, $P1$ and $P2$. P1: for (i=0; i<512; i++) { for (j=0; j<512; j++ ... misses experienced by $P1$ be $M_{1}$and that for $P2$ be $M_{2}$. The value of $M_{1}$ is: $0$ $2048$ $16384$ $262144$
42 votes
4 answers
4
11.7k views
Consider two cache organizations. First one is $32 \hspace{0.2cm} KB$ $2-way$ set associative with $32 \hspace{0.2cm} byte$ block size, the second is of same size but direct mapped. The size of an address is $32 \hspace{0.2cm} bits$ in both cases . A $2-to-1$ ... $h_1$ is: $2.4 \text{ ns}$ $2.3 \text{ ns}$ $1.8 \text{ ns}$ $1.7 \text{ ns}$