micro-programmed control circuit and one questions

Question

I ran into a question:

in digital system with micro-programmed control circuit, total of distinct operation pattern of 32 signal is 450. if the micro-programmed memory contains 1K micro instruction, by using Nano memory, how many bits is reduced from micro-programmed memory?

1) 22 Kbits

2) 23 Kbits

3) 450 Kbits

4) 450*32 Kbits

I read in my notes, that (1) is true, but i couldn't understand how we get this?

Edit: Micro instructions are stored in the micro memory (control memory). There is a chance that a group of micro instructions may occur several times in a micro program. As a result the more memory space isneeded.By making use of the nano memory we can have significant saving in the memory when a group of micro operations occur several times in a micro program. Please see for nano technique ref:

Answer 1

Control Units

Back in the day, before .NET, when you actually had to know what a computer was, before you could make it do stuff. This question would have gotten a ton of answers.

Except, back then, the internet wasn't really a thing, and Stack overflow was not really a problem, as the concept of a stack and a heap, wasn't really a standard..

So just to make sure that we are in fact talking about the same thing, I will just tr to explain this..

The control unit in a digital computer initiates sequences of microoperations. In a bus-oriented system, the control signals that specify microoperations are groups of bits that select the paths in multiplexers, decoders, and ALUs.

So we are looking at the control unit, and the instruction set for making it capable of actually doing stuff. We are dealing with what steps should happen, when the compiled assembly requests a bit shift, clear a register, or similar "low level" stuff.

Some of theese instructions may be hardwired, but usually not all of them.

Micro-programs

Quote: "Microprogramming is an orderly method of designing the control unit of a conventional computer" (http://www2.informatik.hu-berlin.de/rok/ca/data/slides/english/ca9.pdf)

The control variables, for the control unit can be represented by a string of 1’s and 0’s called a "control word". A microprogrammed control unit is a control unit whose binary control variables are not hardwired, but are stored in a memory. Before we optimized stuff we called this memory the micro memory ;)

Typically we would actually be looking at two "memories" a control memory, and a main memory.

the control memory is for the microprogram, and the main memory is for instructions and data

The process of code generation for the control memory is called microprogramming.

... ok?

Transfer of information among registers in the processor is through MUXs rather than a bus, we typically have a few register, some of which are familiar to programmers, some are not. The ones that should ring a bell for most in here, is the processor registers. The most common 4 Processor registers are:

• Program counter – PC
• Address register – AR
• Data register – DR
• Accumulator register - AC

Examples where microcode uses processor registers to do stuff

Assembly instruction "ADD"
pseudo micro code: " AC ← AC + M[EA] " where M[EA] is data from main memory register
control word: 0000


Assembly instruction "BRANCH"
pseudo micro code "If (AC < 0) then (PC ← EA) "
control word: 0001

Micro-memory The micro memory only concerns how we organize whats in the control memory. However when we have big instruction sets, we can do better than simply storing all the instructions. We can subdivide the control memory into "control memory" and "nano memory" (since nano is smaller than micro right ;) ) This is good as we don't waste a lot of valuable space (chip area) on microcode.

The concept of nano memory is derived from a combination of vertical and horizontal instructions, but also provides trade-offs between them.

The motorola M68k microcomputer is one the earlier and popular µComputers with this nano memory control design. Here it was shown that a significant saving of memory could be achieved when a group of micro instructions occur often in a microprogram.

Here it was shown that by structuring the memory properly, that a few bits could be used to address the instructions, without a significant cost to speed. The reduction was so that only the upper log_2(n) bits are required to specify the nano-address, when compared to the micro-address.

what does this mean? Well let's stay with the M68K example a bit longer: It had 640 instructions, out of which only 280 where unique.

had the instructions been coded as simple micro memory, it would have taken up:

640x70 bits. or 44800 bits

however, as only the 280 unique instructions where required to fill all 70 bits, we could apply the nano memory technique to the remaining instructions, and get:

8 < log_2(640-280) < 9 = 9
640*9 bit micro control store, and 280x70 bit nano memory store
total of 25360 bits

or a memory savings of 19440 bits.. which could be laid out as main memory for programmers :)

this shows that the equation:

S = Hm x Wm + Hn x Wn 
where:
    Hm = Number of words High Level 
    Wm = Length of words in High Level
    Hn = Number of Low Level words
    Wn = Length of low level words
    S = Control Memory Size (with Nano memory technique)

holds in real life.

note that, micro memory is usually designed vertically (Hm is large, Wm is small) and nano programs are usually opposite Hn small, Wn Large.

Back to the question

I had a few problems understanding the wording of the problem, - that may because my first language is Danish, but still I tried to make some sense of it and got to:

proposition 1:
1000 instructions
32 bits
450 uniques

µCode:
1000 * 32 = 32.000 bits

bit width required for nano memory:
log2(1000-450) > 9 => 10

450 * 32 = 14400
(1000-450) * 10 = 5500
32000 - (14400 + 5500) = 12.100 bits saved

Which is not any of your answers. please provide clarification?

UPDATE:

"the control word is 32 bit. we can code the 450 pattern with 9 bit and we use these 9 bits instead of 32 bit control word. reduce memory from 1000*(32+x) to 1000*(9+x) is equal to 23kbits. –  Ali Movagher"

There is your problem, we cannot code the 450 pattern with 9 bits, as far as I can see we need 10..