Not that the article is particularly detailed, but squinting at the clock diagram for Wave Semi, it appears to be a some kind of token passing, where the token is the clock.
I guess this question is for the semi- folks out there: given any n-bit boolean function, for smallish n, is there a way to implement the function so that the output is rock-stable (within reason) and only flips if given an input flip the corresponding function flips?
Because, if not, I don't see how this clock passing system won't require factoring in logic delay.
I'm sure a lot of details have been elided. Also, if it isn't apparent, I have no logic design knowledge.
All I know, from an outsider's perspective, having a global clock is ludicrous. When will designers finally kill it?! Us software people have had to kill the concept of intrinsic clocks with our consensus protocols for a while now...
"Given any n-bit boolean function, for smallish n, is there a way to implement the function so that the output is rock-stable (within reason) and only flips if given an input flip the corresponding function flips?"
Yep, there is a way.
So you are designing your logic circuit as usual:
3. From the Karnaugh Map, implement it with AND-OR gates.
When you are doing the Karnaugh Map you have to ensure every adjacent 1 or 0 (depending if you are doing standard or inverse logic) are grouped together. You will use more gates to implement the same logic. Or you can use less gates, and wait for the output to stabilize, you know, with a clock.
Cool, thanks javcasas for that intro to Karnaugh maps. I haven't looked at them closely enough to fully understand how they capture "race conditions", but I'll do so on the weekend. I wonder if any specialists in combinatorial design theory have studied these objects.
There could be some neat mathematics that has yet to be applied to circuit design!
The race conditions are not really apparent on Karnaugh maps. They appear once you understand there are no single pair of logic gates in the world that are exactly equal. Every logic gate is slightly slower or faster than the others, even in the same chip. This leads to every level change to be discrete in time, and never exactly aligned with others, which leads to glitches.
Silly example:
Let's imagine we are implementing the logic operation A OR (NOT A), which should be 1 always. We implement it as an OR gate with two inputs. On the first input we put A through a buffer. On the second input we put A through a NOT gate. Now let's switch A from 0 to 1. One of these two sequences of events will happen:
Sequence 1:
0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1.
1. The buffer sets its output to 1. The OR gate has 1,1 on its inputs. Output=1.
2. The NOT gate sets its output to 0. The OR gate has 1,0 on its inputs. Output=1
During all the sequence the output has been 1, so everything is fine.
Sequence 2:
0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1.
1. The NOT gate sets its output to 0. The OR gate has 0,0 on its inputs. Output=0
2. The buffer sets its output to 1. The OR gate has 1,0 on its inputs. Output=1.
Did you see it? During a split-second the output was 0, even though theoretically it should have been 1 all the time. That's your glitch.
If your system is synchronous, it means it has a clock, which means the system ignores everything that happens between clock ticks. If your ticks are sufficiently large (as it should be), the glitches will happen before the next tick. So your system will "stabilize" into the right output before the next tick, and everything is fine. But if your system doesn't use a clock, these glitches will be propagated to other parts, causing trouble all over the place.
I understand what you're saying, it's just that in your example (Law of Excluded Middle FTW!) the boolean function is the constant 1 function (on one input).
Even I know how to implement that, at least I think so, in a glitch free way.
In general though, you're trying to implement some function, and it's not necessarily true that some arbitrary gate setup you make is glitch free, as you have illustrated with the constant 1 function.
I assume Karnaugh maps solve this problem, at the cost of perhaps extra gates?
Karnaugh maps can identify hazards and then also illustrate what the additional logic gates can be inserted to correct the problem.
Having a different number of gates on different paths throu a circuit can cause the same problems (say (A & B) | C). This is the easier case to correct.
> 3. From the Karnaugh Map, implement it with AND-OR gates.
oh dear, that brings back so many memories. however, for modern day optimizations with millions of primitives, kmaps are totally unfeasible. binary-decision-diagrams aka BDD, no not the other one ;), are the ones which makes things somewhat reasonable.
edit: if you are really curious about these things, then the text by zvi-kohavi (switching and finite automata theory) is an excellent primer.
Sure, I will not use Karnaugh maps when I design a processor. They are awesome for teaching logic gates, but useless for building big logic. It's like pretending to build a skyscrapper with just bricks and mortar. Given enough effort you will succeed, but you are likely to die of old age long before.
Hardware folk have been way ahead of this curve, actually. MESI was big news in H/W cliques long (long) before it started bubbling up in pop software space around a few years ago.
Also, us software people haven't really solved the problem of high performance consensus, either. (Cue in for Aphyr link.)
I'm not sure if I'm mistaken, but I think the hardware guys get to have MESI because they get to assume their "network", the circuit, is infallible.
You can build MESI on paxos, if you wanted. Although I think you'd be layering abstractions unnecessarily unless you have a specific use case.
I'd have to think about it but perhaps there's a cache-coherent data centre scale "processor", with awful non-uniform memory access performance, sprouting random processor hotplug events, waiting to be built.
Who knows? Probably somebody inside Google is working on this very thing a we speak...
If you look at rather dubious "disadvantages" like "Fewer people are trained in this style compared to synchronous design" or "Incompatible with commercial EDA tools" and the same time the vast amount of advantages this looks like a rather low hanging fruit.
An asynchronous ARM64 design with potential more than 3 times better performance per watt will sell like hot cakes.
Asynchronous computers are commercially available right now which have been shown to be fully reliable. Asynchronous design has been an area of research for a long time and many successful computers have been built.
Why is device variation a reason against asynchronous design? If anything I'd say that is a reason for it. Clocked designs must account for the worst case variation and reduce the clock speed accordingly. An asynchronous design on the other hand will run as fast as physically possible.
If I understand it properly, asynchronous circuits also work at the slowest speed required, thus minimizing power usage. They are really fast when there is something to do, and they stop completely when there is nothing to do. Thus the "sleep mode" should be ludicrously low power, just the leakage current of the transistors: some nA for each gate.
try to do a cryptographic circuit with that, it will be side channel party. Generally we count on inefficiencies and in particular the clock distribution network to mask the data from the input current.
When your processor does computations, it consumes power and radiates electromagnetic waves depending on many parameters, such as the kind of computation, the parameters, the amount of ones vs zeros in the registers and many other "silly" details.
When you do crypto on such systems, part of the information that should be hidden is leaked in the form of EM waves, longer or shorter response times, and current consumption (among others). These leaks of information are called "side channels", and have been successfully used to hack some systems.
Some of the current tricks of proper cryptography include things such as "always do the same amount of computation", "always take the same time", "always consume the same current" in order to try to hide this leak of information. It is tricky with standard "clocked" processors. So it will be even trickier with asynchronous processors.
Maybe, instead of taking precautions like trying to always take the same amount of time for some computation (which sounds like a pain!) we could take advantage of some unique properties of async chips. I'm thinking of something like randomly varying the voltage as the computations take place so that time differences will not correlate to data.
Well, if you are able to predict that random voltage generator (we have seen recently some failures in pseudo-random generators that allow attackers to predict next numbers) we can correlate again time with data. So now you have to ensure your random generator is truly random, and not biased at all.
For every weird property you try to use to obfuscate the computation, there is some kind of counter to try to de-obfuscate it. That's why crypto is really hard. If you really want to succeed, the only way is use as many tricks as possible, in order to make the attack really hard, hoping to discourage the attacker into doing something more productive with his life.
Except if it's really random, after enough trials you'll have some clearly random distribution, with some distortion related to the actual cost. Figuring out the cost is just some statistical analysis away.
I think you are mostly right. They work at the fastest speed possible, the power usage is minimized by not doing anything when there is nothing to do. And from not having to propagate a clock signal all over the chip (maybe other reasons as well, I'm not an expert)
If you are interested in real-world numbers, there is a comparison of between a GA144(an asynchronous multi-computer chip) and a MSP430(conventional low-power microprocessor) here: http://www.greenarraychips.com/home/documents/greg/WP003-100...
The GA144 can execute almost 4000x more instructions per second then MSP430 while consuming over 70x less power for the work done.
> The GA144 can execute almost 4000x more instructions per second then MSP430 while consuming over 70x less power for the work done.
Yea, but the MSP430 actually has (a ton of) built in peripherals on it's own die, whereas the FA18 has none; so it's not the greatest comparison of J/MIPS.
Yes, this only compares energy consumption to help show the difference between synchronous(with the explicit goal energy efficiency) and async designs. I don't think peripherals has anything to do with this comparison. There are obviously a ton of reasons why a MSP430 might make more sense for a given application.
The GA144 is so radically different that any comparison to a conventional computer is difficult.
The Caltech Asynchronous Microprocessor (1988) was the first asynchronous microprocessor (1988). Caltech designed and manufactured the world's first fully Quasi Delay Insensitive processor. During demonstrations, the researchers amazed viewers by loading a simple program which ran in a tight loop, pulsing one of the output lines after each instruction. This output line was connected to an oscilloscope. When a cup of hot coffee was placed on the chip, the pulse rate (the effective "clock rate") naturally slowed down to adapt to the worsening performance of the heated transistors. When liquid nitrogen was poured on the chip, the instruction rate shot up with no additional intervention. Additionally, at lower temperatures, the voltage supplied to the chip could be safely increased, which also improved the instruction rate—again, with no additional configuration.
Not everything has to be asynchronous. For example, if your real-time system has to respond in less than 1ms, all you have to do is design a system able to respond in less than 1ms. If your system has to respond in exactly 1ms, you take the previous system (the one able to respond in less than 1ms) and use a 1ms clock/timer/monostable to delay it.
actually you would want your system to react at the speed of its input (the world as seen form its point of view), not at the speed of its clock. And if you actually wanted a clock (say for an alarm clock in the morning), you could still input a clock to your system, that wouldn't entitle gating the whole system and having clock domains and that stuff.
Another very interesting async design is GreenArrays GA144:
"This very powerful and versatile chip consists of an 18x8 array of architecturally identical, independent, complete F18A computers, or nodes, each of which operates asynchronously. Each computer is capable of performing a basic ALU instruction in ~1.5 nanoseconds for an energy cost on the order of 7 picojoules".
Programmed in Forth.
http://www.greenarraychips.com/index.html
I'll admit I'm not especially familiar with the field, but that sounds quite exceptional to me.
Is there anything out there offering this sort of price/performance ratio that's easily accessible, ideally programmable using open-source hobbyist tools?
I think there is a technological path for gradually introducing synchronous design in clocked world: you can give them clocked inputs without problem, and you can gate their output at their worst propagation time without problem either.
I think with such an easy technological path, there is no intrinsic reason not to have them around us, even exposed as clocked systems. If someone told me today that there already are synchronous blocks in a famous silicon chip I would certainly not be surprised.
For example, I'm not a silicon guy so I'm guessing, but adders are generally exposed as one cycle instructions in software, but they still have to propagate the carry on the width of the word, so I guess adders are simply a tree of gate that synchronously propagate and we know the carry propagates faster than the clock tick.
Looking at the waveform graph on the site, it looks like it turns the output to 1 when both inputs are 1, and turns the output to 0 when both inputs are 0 (In other words, it assigns the output to the inputs when the inputs are in agreement). Though, that's just a guess.
Leakage is the big problem in deep submicron. You can't keep a state without periodically refreshing it (cf. DRAM). Also, asynchronous circuits are very prone to metastability. If these problems were easily solved, we'd have seen this old idea be widespread by now.
I recently asked an Intel chip designer if asynchronous circuits could be a way to deal with stalling of Moore's Law and he was adamant that asynchronous circuits are a "fantasy." His argument was that even though synchronous use about 20% of the energy on a modern, chips, with asynchronous you still need to pass around synchronization tokens which would double the energy required and worse it would be on the critical path.
58 comments
[ 2.8 ms ] story [ 127 ms ] threadI guess this question is for the semi- folks out there: given any n-bit boolean function, for smallish n, is there a way to implement the function so that the output is rock-stable (within reason) and only flips if given an input flip the corresponding function flips?
Because, if not, I don't see how this clock passing system won't require factoring in logic delay.
I'm sure a lot of details have been elided. Also, if it isn't apparent, I have no logic design knowledge.
All I know, from an outsider's perspective, having a global clock is ludicrous. When will designers finally kill it?! Us software people have had to kill the concept of intrinsic clocks with our consensus protocols for a while now...
Yep, there is a way. So you are designing your logic circuit as usual:
1. For each input, decide the output
2. Simplify the function using a Karnaugh Map https://en.wikipedia.org/wiki/Karnaugh_map
3. From the Karnaugh Map, implement it with AND-OR gates.
When you are doing the Karnaugh Map you have to ensure every adjacent 1 or 0 (depending if you are doing standard or inverse logic) are grouped together. You will use more gates to implement the same logic. Or you can use less gates, and wait for the output to stabilize, you know, with a clock.
Update:
Wikipedia shows an example: https://en.wikipedia.org/wiki/File:K-map_6,8,9,10,11,12,13,1...
This has a race condition on the inverse implementation, and thus can generate glitches if used in an asynchronous circuit (but it is fine on a synchronous one): https://upload.wikimedia.org/wikipedia/commons/archive/0/02/...
We can fix it adding another Karnaugh group, thus making it glitch-free, and then can be used in asynchronous circuits: https://upload.wikimedia.org/wikipedia/commons/archive/0/02/...
There could be some neat mathematics that has yet to be applied to circuit design!
Silly example: Let's imagine we are implementing the logic operation A OR (NOT A), which should be 1 always. We implement it as an OR gate with two inputs. On the first input we put A through a buffer. On the second input we put A through a NOT gate. Now let's switch A from 0 to 1. One of these two sequences of events will happen:
Sequence 1:
0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1.
1. The buffer sets its output to 1. The OR gate has 1,1 on its inputs. Output=1.
2. The NOT gate sets its output to 0. The OR gate has 1,0 on its inputs. Output=1
During all the sequence the output has been 1, so everything is fine.
Sequence 2:
0. Nothing has happened yet. The OR gate has 0,1 on its inputs. Output=1.
1. The NOT gate sets its output to 0. The OR gate has 0,0 on its inputs. Output=0
2. The buffer sets its output to 1. The OR gate has 1,0 on its inputs. Output=1.
Did you see it? During a split-second the output was 0, even though theoretically it should have been 1 all the time. That's your glitch.
If your system is synchronous, it means it has a clock, which means the system ignores everything that happens between clock ticks. If your ticks are sufficiently large (as it should be), the glitches will happen before the next tick. So your system will "stabilize" into the right output before the next tick, and everything is fine. But if your system doesn't use a clock, these glitches will be propagated to other parts, causing trouble all over the place.
Even I know how to implement that, at least I think so, in a glitch free way.
In general though, you're trying to implement some function, and it's not necessarily true that some arbitrary gate setup you make is glitch free, as you have illustrated with the constant 1 function.
I assume Karnaugh maps solve this problem, at the cost of perhaps extra gates?
Having a different number of gates on different paths throu a circuit can cause the same problems (say (A & B) | C). This is the easier case to correct.
> 3. From the Karnaugh Map, implement it with AND-OR gates.
oh dear, that brings back so many memories. however, for modern day optimizations with millions of primitives, kmaps are totally unfeasible. binary-decision-diagrams aka BDD, no not the other one ;), are the ones which makes things somewhat reasonable.
edit: if you are really curious about these things, then the text by zvi-kohavi (switching and finite automata theory) is an excellent primer.
Hardware folk have been way ahead of this curve, actually. MESI was big news in H/W cliques long (long) before it started bubbling up in pop software space around a few years ago.
Also, us software people haven't really solved the problem of high performance consensus, either. (Cue in for Aphyr link.)
You can build MESI on paxos, if you wanted. Although I think you'd be layering abstractions unnecessarily unless you have a specific use case.
I'd have to think about it but perhaps there's a cache-coherent data centre scale "processor", with awful non-uniform memory access performance, sprouting random processor hotplug events, waiting to be built.
Who knows? Probably somebody inside Google is working on this very thing a we speak...
My point was merely that H/W people had to confront this issue before us.
An asynchronous ARM64 design with potential more than 3 times better performance per watt will sell like hot cakes.
The extra speed always tempting, but a few real builds and the real world of device variation show why the clocked designs are still used.
Why is device variation a reason against asynchronous design? If anything I'd say that is a reason for it. Clocked designs must account for the worst case variation and reduce the clock speed accordingly. An asynchronous design on the other hand will run as fast as physically possible.
When you do crypto on such systems, part of the information that should be hidden is leaked in the form of EM waves, longer or shorter response times, and current consumption (among others). These leaks of information are called "side channels", and have been successfully used to hack some systems.
Some of the current tricks of proper cryptography include things such as "always do the same amount of computation", "always take the same time", "always consume the same current" in order to try to hide this leak of information. It is tricky with standard "clocked" processors. So it will be even trickier with asynchronous processors.
Rickkaksdfhkosghvuiasdjfbvhoenckl;ajvgy8eirbvskl;dvmslvnjsapbvjksnkldfvnslanhvfd no line
line
line
Line
For every weird property you try to use to obfuscate the computation, there is some kind of counter to try to de-obfuscate it. That's why crypto is really hard. If you really want to succeed, the only way is use as many tricks as possible, in order to make the attack really hard, hoping to discourage the attacker into doing something more productive with his life.
See e.g. https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf for this principle applied to performing timing attacks on a remote server (so network latency serves as a handy-dandy rng).
If you are interested in real-world numbers, there is a comparison of between a GA144(an asynchronous multi-computer chip) and a MSP430(conventional low-power microprocessor) here: http://www.greenarraychips.com/home/documents/greg/WP003-100... The GA144 can execute almost 4000x more instructions per second then MSP430 while consuming over 70x less power for the work done.
Yea, but the MSP430 actually has (a ton of) built in peripherals on it's own die, whereas the FA18 has none; so it's not the greatest comparison of J/MIPS.
The GA144 is so radically different that any comparison to a conventional computer is difficult.
The Caltech Asynchronous Microprocessor (1988) was the first asynchronous microprocessor (1988). Caltech designed and manufactured the world's first fully Quasi Delay Insensitive processor. During demonstrations, the researchers amazed viewers by loading a simple program which ran in a tight loop, pulsing one of the output lines after each instruction. This output line was connected to an oscilloscope. When a cup of hot coffee was placed on the chip, the pulse rate (the effective "clock rate") naturally slowed down to adapt to the worsening performance of the heated transistors. When liquid nitrogen was poured on the chip, the instruction rate shot up with no additional intervention. Additionally, at lower temperatures, the voltage supplied to the chip could be safely increased, which also improved the instruction rate—again, with no additional configuration.
Amazing. I want this right now!
If you haven't read anandtech they have articles covering this, since clock rate scaling increases the difficulty of benchmarking.
[1]https://inst.eecs.berkeley.edu/~cs152/fa06/lecnotes/async.pd...
http://www.eetimes.com/document.asp?doc_id=1299083
There were chips before that, too.
The author of the article failed to even mention once this term, instead repeating the term “clockless” as he was in some kind of branding spree.
Furthermore one of the article's tags was “apple”, despite AFAIK the content not being affiliated with apple in any way.
I'll admit I'm not especially familiar with the field, but that sounds quite exceptional to me.
Is there anything out there offering this sort of price/performance ratio that's easily accessible, ideally programmable using open-source hobbyist tools?
I think with such an easy technological path, there is no intrinsic reason not to have them around us, even exposed as clocked systems. If someone told me today that there already are synchronous blocks in a famous silicon chip I would certainly not be surprised.
For example, I'm not a silicon guy so I'm guessing, but adders are generally exposed as one cycle instructions in software, but they still have to propagate the carry on the width of the word, so I guess adders are simply a tree of gate that synchronously propagate and we know the carry propagates faster than the clock tick.
What? Isn't that just AND? I wasn't really too clever from looking at the diagram provided, so I might be missing something.
https://news.ycombinator.com/item?id=10621937
Just in case pro's want to comment on any of it or think it's cool.