A question about synchronization/timing in combinatorial chips.

[knarf_navillus]

Greetings,

I've only completed chapter 2 so far, so this question may get answered later on. I'm just curious about how these chips we're building, if they were built in the REAL world, would handle the fact that some parts are "slower" than others. I suspect, for instance, that an Add16 takes longer than an Or16. So, what if I had the following chip:

Or16(a=a, b=b, out=aorb);
Add16(a=a, b=b, out=aplusb);
Mux16(a=aorb, b=aplusb, sel=which, out=out);

It seems like there will be a temporary time period, during which the Or16 has completed but the Add16 has not, where the output will have an incorrect result. Is that correct? And if so, how does the user of this chip know to wait until the chip is finished? Is this solved somehow with clocks? What if a chip takes more than one clock cycle to get into a correct state?

Thanks,
Frank

[ybakos]

Actually, you'll start to see the difference in chapter 3, "Sequential Chips."

You should embrace the fact that, for combinatorial chips like And, the output is an immediate reflection of the input. As soon as voltage is applied to the inputs, we see some output.

In contrast, sequential (or "clocked") chips behave a bit differently. In these chips, the output for a given input is reflected during the next clock cycle (after a tick and tock).

knarf_navillus wrote

Add16 takes longer than an Or16

No. Both are combinatorial chips and as such, both chips' inputs are immediately reflected by their respective outputs.

A pure theoretician might argue that the "length" of a circuit certainly influences the time it takes for inputs to propagate throughout a circuit and reach the output. But remember, we're talking about the speed of light here.

[knarf_navillus]

Thanks again! It's nice to know that I can treat these combinatorial chips as instantaneous. I was worried that things were about to get real messy. =)

There was something in Chapter 2 (I don't have the book in front of me) that may have thrown me off. It said something to the effect of "The Add16 design is slower than it needs to be, because the carry bit has to trick from adder to adder. Modern designs use something [carry prediction?] to alleviate this." (paraphrase)  

[cadet1620]

In the real world, everything takes time. For ICs we call this their propagation delay. The data sheets for the ICs state what the typical and maximum propagation delays are. The delays for simple gates like And and Or are relatively short. For more complex chips like multi-bit adders the delays can be quite a bit longer. Multiplexers will be a bit slower than simple gates, but faster than adders.

So, you are quite right in your observation that there are short periods when there is indeterminate data on the logic lines. We engineers have a technical term for this: "glitches" 8-)

In chapter 3 you'll learn about clocks and synchronous circuits.  Basically, at the beginning of a clock period all the combinatorial logic starts computing its new value and there is lots of glitchiness as the signals propagate through the logic.  Sometime before the end of the clock period the signals stabilize so that the sequential logic can store them.

It's one of the hardware engineer's jobs to calculate what the worst case delay through his circuits is. This worst case delay determines the maximum clock rate.

There are some circuits that often take longer than a clock period to operate, for instance a hardware multiplier. The simplest way to deal with this is to insert "wait states" in the CPU when multiply instructions are executed.

You might find The Real World is a Hazardous Place interesting.  It talks about problems caused by propagation delays in a circuit as simple as a multiplexer.

--Mark

[knarf_navillus]

That is awesome; I am much obliged.

Does this give any insight into why CPU clock speeds tended to get faster over time in the past? A combination of more-parsimonious circuitry and smaller physical size? I assume that coming up with a faster oscillator wasn't the main challenge...

[ybakos]

Ah, see how much more Mark knows about real-world hardware? Thanks for sharing those insights.

[cadet1620]

knarf_navillus wrote

That is awesome; I am much obliged.

Does this give any insight into why CPU clock speeds tended to get faster over time in the past? A combination of more-parsimonious circuitry and smaller physical size? I assume that coming up with a faster oscillator wasn't the main challenge...

Yep. Mostly smaller sizes allowed by improved semiconductor manufacturing processes.  Smaller also implies more complex processor designs, including first level memory cache, can be placed on the same die.

Remember that electrical signals are limited by the speed of light which is 3x10^8 m/s or roughly 1 foot per nanosecond. So in an Intel Core-i7 Extreme running 2.9 GHz, signals get to go at most 10 cm per clock cycle! I'm amazed they can get these things to work.

--Mark