The Gateway to Computer Science Excellence
0 votes

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?

in CO and Architecture by (97 points)
retagged by | 729 views
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?

2 Answers

+5 votes

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

by Veteran (50.9k points)
edited by

Total bits saved from micro memory will be 22K not 23 K !! I think there is another way to solve this question. isn't it? is there any other method for using nano memory to get 22K?

I think the question designer suppose that we save all microinstruction of micro memory in nano memory and the save the address of the nano memory microinstruction in micro memory so we get:

(1K * (32+x))-(1K*(10+x))=1K*22 bit. maybe my solution is correct, what is your idea?

i dont think u will get 22K as nano memory cannot be less than 14K.

Still u can try.
please read my above edited comments :) is a very challenging and expert question. but I think the author suppose another model of nano memory.
if we put all in nano memory , why do we hv to use nano memory . it will behave the same like micromemory.

we use nano memory as a cache for unique words only.
So suppose this is a strange hypothesis that consider by designer, isn't it? did you have any email address to  sent my figure for you?
alright , if we consider this hypothesis,

then new micromemory size = 1024 * 10 = 10240

and nanomemory size = 1024 * 32 = 32768

total size = 10240 + 32768 = 43008.

is this what u r asking.?
32768-10240=22K why yo add these values?
a micromemory is divided into new micromemory and new nano memory so it cannot be more than 32768 bits .

can u plz tell why are you substracting nano and micro?
if we just put distinct microinstruction on another memory called nano, and by micro memory just address these distinct instruction we can save. is it possible to consider this method?
Sorry subtract is my fault. sorry. I say another comment please see. thanks
this is the only method of why nano memory is used

see we cannot increase it beyond 1024 * 32 and nano acts as a cache here. so we have to put just distinct in it and all 1024 in micromemory , so it is not possible to get 22K .

is this clear ?
Thanks, Sorry for wasting your valuable time. is it possible to I do more study and comments some next hours? Would you please give me a messenger ID?
its a nice question , u can comment here . i will stay updated .

is it seems good now?

why take 10 bits to address when it can be done only by 9?
10=number of bits to address 1K memory
r u asking this...

new micromemory = 1024 *10
We ask how many bit reduced from micro memory?
so u r saying that nano now contains all the 1024 words , only then u would have got 10 bits.

then where will the micro go ?

Our program now contains an address with length 10 to points to 1K memory.

if we imply this, then total size of micro will be

10240 + 32768

as i said it cannot be greater than 1024 * 32
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.
+1 vote
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$.
by Veteran (434k points)
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?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,832 questions
57,685 answers
107,166 users