GATE IT 2005 | Question: 49

Question

An instruction set of a processor has $125$ signals which can be divided into $5$ groups of mutually exclusive signals as follows:

Group $1$ $:$ $20$ signals, Group $2$ $:$ $70$ signals, Group $3$ $:$ $2$ signals, Group $4$ $:$ $10$ signals, Group $5$ $:$ $23$ signals.

How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming?

• A. $0$
• B. $103$
• C. $22$
• D. $55$

Comments

In case of vertical microprogramming we can use 3bits for identifying any group out of 5 and 7 bits for control signals since max no of control signals required is 70. Why won't this method work?

---

because signal from more than one group can be active at a time.

---

Can anyone please share the resource regarding vertical microprogramming  and horizontal microprogramming. As this is not available in computer organization by carl hamacher

---

How can you say that signal from more than one group can be active at a time?

---

Good Read!

Answer 1

In horizontal microprogramming we need $1$ bit for every control word, therefore total bits in

Horizontal Microprogramming $=20+70+2+10+23=125$

Now lets consider vertical microprogramming, In vertical microprogramming we use Decoder $\text{(n to$\ 2^n$)}$ and output lines are equal to number of control words. A input is given according to what control word we have to select.

Now in this question these $5$ groups contains mutually exclusive signals, i.e, they can be activated one at a time for a given group, we can safely use decoder.

$\text{group }1=\lceil \log_{2} 20\rceil=5$ (Number of input bits for decoder, given output
is number of control word in given group)

$\text{group }2=\lceil \log_{2} 70\rceil=7$

$\text{group }3=\lceil \log_{2} 2\rceil=1$

$\text{group }4=\lceil \log_{2} 10\rceil=4$

$\text{group }5=\lceil \log_{2} 23\rceil=5$

Total bits required in vertical microprogramming $= 5+7+1+4+5=22$

So number of control words saved $=125-22=103$

Hence, (B) is answer.

Comments

@Divy kala bro, i am giving possible explanation of why we need only one bit for two mutually exclusive control signals :-

 when both  control signal are off, then may be we fill special character on that corresponding bit instead of filling "0" or "1". Due to that special character, 1*2 decoder doesn't give active signal on any of output lines. So, it means that none of those two mutually exclusive control signal are active. 

---

tonystark  I think the bits will be divided logically to indicate groups from the whole bitstream. Correct me if I am wrong!

---

Aalok8523

 

can the output of the decoder be zero? as per what you have explained!

Answer 2

1. Bits needed for horizontal microprogramming:

   • Each signal needs a dedicated bit, so 125 signals require 125 bits.

2. Bits needed for vertical microprogramming:

   • Only one bit is needed to select a group, and then a separate field within the control word specifies the signal within that group.
   • 5 bits to select a group (log2(5) = 2.32, but we need at least 3 bits to represent 5 groups)
   • 20 bits for Group 1 (log2(20) = 4.32, so 5 bits)
   • 7 bits for Group 2 (log2(70) = 6.13, so 7 bits)
   • 1 bit for Group 3 (log2(2) = 1)
   • 4 bits for Group 4 (log2(10) = 3.32, so 4 bits)
   • 5 bits for Group 5 (log2(23) = 4.52, so 5 bits)
   • Total bits: 5 + 5 + 7 + 1 + 4 + 5 = 27 bits

3. Bits saved:

   • 125 bits (horizontal) - 27 bits (vertical) = 103 bits

Therefore, using vertical microprogramming saves 103 bits of control words compared to horizontal microprogramming in this case.