Surprised Nano Memory (VERTICAL Micro Instruction) Reduced bits?!

Question

Hi to all, 

This is an Challenging Interview Question that I see lots of this example in GATE Exams. 

In  a digital system with micro-programmed control circuit, We have 32 Control Signal and total distinct pattern is 450. if the micro-programmed memory contains 1K micro instruction, by using Nano memory (vertical micro-instruction), how many bits is reduced from micro memory?

a) 22K bits

b) 23K bits

All of my friends and solution from GATES says:

reduce memory from 1000*(32+x) to 1000*(9+x) is equal to 23kbits but the solution is (a). (i.e 22K bits). 

any EXPERT can say why 22K is true?

Comments

Hours and Hours Thinking by 6 students but no progress, why 22 is selected ?!

---

What is the source of question and solution? And what is "GATES" ?

---

Source is exam and I mean that this solution is like to previous GATES exam but it's not correct for here.

---

which exam?

Answer 1

From what i understand from the question,

There are 1K microinstructions , a control word or a microinstruction size is 32 bits , and out of 1000 there are 450 unique or distinct micro instructions.

(A microinstruction is also a control word)

Hence size of micro programmed memory will be ---> 1024 * 32 = 32768 bits.

Now , we are using nano memory for which micromemory has indexing into nano memory. Micromemory will be used with 1K instructions and nanomemory contains 450 distinct instructions. micromemory will work whether whether a nano memory is used or not. But when used it will point to 450 unique instructions of the memory . This time bit width of control word or microinstruction will be log(450)= approx take as 9. To represent 450 nano memory words, we need 9 bits in micromemory .

so new micro memory size = 1024 * 9 = 9126 bits

and so formed nano memory size = 450 * 32 = 14400 bits

Hence total memory now will be = 9126 + 14400 = 23616 bits which was initially without nano memory = 32768 bits.

Total bits saved will be = 32768 - 23616 = 9152 bits

Total bits saved from micro memory will be = 32768 - 9126 = 23642 bits which is approx. 23kbits.

I hope this helps you , as no way we can decrease the nano memory size from 14400 bits = 14K bits

Comments

Okey, Please think on it, I think more and comment it, thankssssssssssssssss

---

is there any possibility that the answer may be wrong.

i mean u r trying too much to get 22 anyhow.

i dont think 22k will come.

---

+1 but I try to more search and study to say how we get 22Kbit.

Answer 2

We have 32 control signals which could give $2^{32}$ distinct patterns. But we have only $450$ distinct patterns and so we could reduce the memory required for control words. In stead of using $32$ bits we store only the amount of bits needed to represent the unique patterns and then we use a decoder (nanomemory) which will generate the full signal corresponding to the given unique pattern (vertical microprogramming). For example,

101000111 could correspond to 1101011101101100....001 (32 bits) and similarly all 450 patterns will have a corresponding 32 bit control signal and the nanomemory takes care of this mapping. Now, we have 450 distinct patterns => we require at least $\lceil \lg_2 450\rceil = 9$ bits for control word. So, total micro memory required will be $$9 \times 1K = 9Kbits.$$

Total micro memory required initially (horizontal microprogramming) $= 32 \times 1K = 32Kbits.$

So, total savings in memory $=32K - 9K = 23Kbits.$

Here, I ignored the amount of memory required for nanomemory as question says about micromemory only. Nanomemory would require $10$ bits for $2^9$ possible patterns giving $10 \times 512 = 5K bits.$ So, total memory savings will be $23K - 5K = 18Kbits$.

Comments

Thanks, +1. but I say again 22Kbit is Correct :)

---

source of this question ?

---

It's not published online. CS Entrance Exam adopted from GATE EXams.

---

Sir ,

Here nano memory is vertically programmed (given vertical micro instruction)

why we are using horizontal  micro format for nano-memory?

Answer 3

nano memory is a two level storage system in microprogramme control sysem.

in operations with a parallelism of First level – Vertical formate micro programme

Second level – Horizontal formate micro programme 

suppose there are 2048 micro instruction of 200 bits each

case-1 ) IN 1 – level control storage, size= 2048 x 200 bits

case-2 } in 2 level control storage (assume there are 256 distinct instruction)

nano storage size = 256 x 200 bits (it is stored in horizontal formate on 2^nd level)

control storage size = 2048 x 8 bits (8 bits to represent 256 instruction in nano memory in vertical formate)

apply same concept in this question to practice