Puzzles: Half Adder using Multiplexer

Let's say you have to realize a half adder. But all you've got are 2:1 Multiplexers. How would you design one half adder using ONLY 2:1 Multiplexers?

Click here to find the solution:

Low Power FSMs

Low Power design is the need of the hour! The post: Need for Low-Power Design Methodology gives an insight into the intent and need for the modern design to be power aware. The subsequent posts on Clock Gating and Power Gating under the tab Low Power Methodology discuss some ways in which the the SoC can be designed for low power. In this post, we will consider one such low power design of an FSM which can be generalized to design any low power sequential circuit.

Consider the following generalized design of a traditional and a low power FSM:

Let's talk about the basic building block that we have used here. The OR gate acts as an clock gate to the flop. The flop that we have used is a toggle flop. When enable = 0, the flop receives the clock, and the flop toggles its state. So, whenever we need to change the state of the flop, we can give a clock pulse.

Enough said! Let's now talk about a real example of a basic synchronous counter. And how we can design a low power synchronous counter using the above method.

In any binary counter:

• The lowest order bit toggles after every clock cycle.
• Any higher order bit toggles only when all the lower order bits are at logic 1.

Keeping this in mind, we can now build the low power counter!!

References:

• Low Power Sequential Circuit Design Using T Flip-Flops

Multi-Cycle Paths: Perspective & Intent

Multi-Cycle Paths, as the name suggests, are those paths which need not be timed in one clock cycle. It is easier said than done! Before we discuss further, let's talk about what Multi-cycle paths does not mean!!

Myth 1: All those paths which the STA team is unable to meet at the highest clock frequency, are potential multi-cycle paths.

Reality: Multi-cycle paths are driven by the architectural and design requirements. STA folks merely implement or appropriately said, model the intent in their timing tools! A path can be a multi-cycle path even if the STA team is able to meet timing at the highest clock frequency.

Myth 2: It is by some magic that the design teams conjure up how many cycles it would be appropriate to for a path to function! <Apologies the hyperbole! :)>. And STA team follows the same in their constraints.

Reality: MCPs are driven by the intent. And implementation is governed by that intent which includes but is not limited to the number of run modes a particular SoC should support.

Consider the following scenario:

Normal mode, Low Power Mode and Ultra Low Power Modes can be considered to be the different run modes of the SoC. You can say that the customer can choose at what time which run mode would be better. Example: when performance is not critical, or your device can go to 'hibernate' mode, you (or the software) can allow the non-critical parts of the SoC to go into a Low Power Mode, and hence save power!

Consider the specifications:

• Normal Mode: Most Critical IP & Not-So Critical IP would work at f MHz. Least Critical IP would work at f/2 MHz. Interaction between any two IPs would be at slower frequency.
• Low Power Mode: Most Critical IP would work at f MHz. Not-So Critical IP & Least Critical IP would work at f/2 MHz. Interaction between any two IPs would be at slower frequency.
• Ultra Low Power Mode: Most Critical IP would work at f MHz. Not-So Critical IP would work at f/2 MHz. And Least Critical IP would work at f/k MHz; (k=> 3-8). Interaction between any two IPs would be at slower frequency.

Consider the Low Power Mode. Any interaction within the Not-So Critical IP would be at slower frequency. However, any paths between the Most Critical IP and Not-So Critical IP would be Multicycle path of 2 in the low power mode. In this case, the clock at the Not-So Critical IP is gated selectively for every alternate clock cycle to implement an MCP. Hence data launched from Most Critical IP now effectively gets two clock cycles (of the faster clock) to reach the Not-So Critical IP. The following figure explains the intent:

This much for the intent! However, as we mentioned that for the Least Critical IP, depending on the mode, would work at f/k MHz => (k=3-8) one might need an MCP of 2, 3, 4.... and so on. This calls for a need of a configurable implementation of multicycle paths. We shall cover it sometime later. Till then, you can assimilate on the intent part. You can also mail me in case you think of any such implementation at my<dot>personal<dot>log<at>gmail<dot>com. Adios!

Parallel to Serial Converter

Let's discuss the design of a Parallel to Serial Converter. Here's the crude problem statement.

You have 8 FFs, each working at a frequency of 10MHz and sending out a parallel data which effectively would be 8-bit wide. We intend to convert this data into a serial one, where 1 FF would output the data serially in order of first FF, then data of second FF and so on. Refer to the diagram below:

Such a parallel to serial converter might be useful in applications requiring Serial Communication which maybe interface to a microprocessor or a microcontroller; interface between your monitor and the CPU or any application which might involve serial processing of information.

Now let's proceed for the design. Note that:

• We have 8-bits of input data, and we want to output them one at a time. This suggests the use of a multiplexer. The size of this multiplexer would obviously be 8:1.
• Apart from the inputs, the multiplexer would have select lines (3 select lines for a 8:1 MUX) and we need to control these lines. Select lines need to be controlled in such a way that first the FF1 is selected, then FF2 and so on. 
• Recall the functionality of a multiplexer. The first bit is selected when select lines would be {S2,S1,S0} = 000, Second bit when {S2,S1,S0} = 001. Hence we can use a binary counter which would count from 000 to 111 in a binary manner.
• What would be the frequency of this counter? Note that for every one cycle of input data, we need to 8 outputs corresponding to 8 input FFs. Hence the frequency of the counter would be:

Freq. = 8 X 10 MHz = 80 MHz

Here's the final design:

Puzzle: Divide by 3 Counter with 50% DC

It is pretty simple to make a clock divider with odd frequency division (let's say 3 or 5). But it doesn't have 50% duty cycle. Some modifications are essential to achieve that 50% duty cycle. You might argue, why so much fuss about 50%? To give you an insight into it, consider the following divided waveform with 66% DC:

As you can note from the above waveforms: 

• NEG-TO-POS arc (i.e. any path launching from a negative edge triggered flop and being captured at positive edge triggered flop) would have least time to meet the setup time requirement and hence can be critical. 
• On the other hand, POS-TO-POS and NEG-TO-NEG are so much relaxed. 

Same would be true for a divider with 33% duty cycle as well. So, it is preferable to use a divided clock with 50% duty cycle.

Can you design such a circuit which takes a clock signal of frequency f, and outputs another clock signal of frequency f/3 with 50% duty cycle?

Clock Gating

Clock signal is the highest frequency toggling signal in any SoC. As we discussed in the post: Need for Low-Power Design Methodology, the capacitive load power component of the dynamic power is directly proportional to the switching frequency of the devices. This implies that clock path cells would contribute maximum to the dynamic power consumption in the SoC. 

Power consumption in the clock paths alone contribute to more than 50% of the total dynamic power consumed within modern SoCs. Power being a very critical aspect of the design, one needs to make prudent efforts to reduce this. Clock Gating is one such method. 

Let's try and build further on this perspective.

Clock feeds the CLOCK pins all the Flip-Flops in the design. Clock Tree itself comprises of clock tree buffers which are needed to maintain a sharp slew (numerically small) in the clock path. Refer to the post Clock Transition for details. 

Consider the above figure. It is not necessary that the output of the flip-flop would be switching at all times. Modern devices support various low-power modes in which only a certain part of your SoC is working. This may include some key features pertaining to security or some critical functional aspects of your device. Apart from this, there are some configuration registers in your device which need to be programmed either once or very seldom. So, let's say, the above FF will not be switching states for a considerable period of time. If it is used the way it is, what's the problem? Power! Clock is switching incessantly. Clock Tree buffers are switching states and hence consuming power. So are the FFs. Remember that FF itself is made up of latches. So, despite the fact that input and output of the FF is not switching, some part of the latch is switching and consuming power.

What could be done to alleviate the above problem? Clock Gating is one such solution. Here's how it'll help.

If you place an AND gate at the clock path and knowing that you don't need a certain part of your device to receive clock, drive a logic '0' on the ENABLE pin. This would ensure that all the Clock Tree buffers and the sink pin of the FF are held at a constant value (0 in this case). Hence these cells would not contribute to dynamic power dissipation. However, they would still consume leakage power.

Similarly, you can place an OR gate and drive it's one input to logic 1. Again, you would save on the dynamic power.

However, a word of caution. The output of the AND gate feeding the entire clock path might be glitchy. See the following figure:

Solution: The output won't be glitchy if the enable signal changes only when the CLOCK signal is low. So, all you gotta make sure is that ENABLE is generated by a negative-edge triggered FF. This would ensure that the signal is changing after the fall edge of the CLOCK signal.

Similarly, while using an OR-gate, clock pulse would be propagated if the ENABLE signal changes when the CLOCK is high. Make sure that it is generated by a positive-edge triggered FF in order to avoid any glitch being passed onto the FFs. 

Why would a glitch be detrimental anyway? The answer is:

Glitches constitute an edge! FF might sample the value because they are edge-triggered. But, problem is that all FFs have a certain duty cycle requirement (Also called Pulse-width check), which needs to be fulfilled in order to ensure that they don't go into METASTABILITY. And if an unknown state : X is propagated in a design, the entire functionality of the chip can go haywire!

Some terminologies: 

• AND/NAND gate based clock gating is referred to as Active-High Clock Gating.
• OR/NOR gate based clock gating is referred to as Active-Low Clock Gating.

NAND and NOR clock gates work similar to AND and OR respectively.

So, Clock Gating is an efficient solution to save dynamic power consumption in the design. Modern SoCs have many IPs integrated together. Placing a clock gate and enabling them in various possible combinations is what gives rise to different low-power modes in the device.

Puzzle: Multiplexer Trees

Are you comfortable making multiplexer trees? If you are, then try this one:

How many 2:1 MUXes you would require to make any n:1 MUX, where n is any integer greater than or equal to 2.



Answer is n-1.

Solution:

By principle of mathematical induction, we can say that for any n:1 MUX, we would require (n-1) 2:1 MUXes.