Why can't an Asynchronous CPU use a simple "completion bit" to signal completion?

I've been reading about how asynchronous CPUs work, but they always seem to involve some complicated way of communication. Wikipedia talks about a two-way and four-way handshake. I found a pdf from iosrjournals.org that talks about communicating Requests, Acks, and Data either in 2-phase bundles or 4-phase bundles.

I don't understand why any of this is necessary. Why don't you just use a single bit on a dedicated line that is 0 until the operation is complete? Then it becomes a 1. Then the accumulator at the end of the ALU will know the "final answer" is finished and it can switch the buffer from read to write, outputting it on some other bus.

So of course it begs the question as to how the ALU will know when its done. I'm not exactly sure how to do that, but the simplest way to do it would be to just set it to 1 immediately and then make sure the propagation delay is long enough such that the worst case operands finish in time. But this is a unique trace for each operand the ALU is capable of. It's not like a clock signal that has to be long enough for the worse case of any ALU operation.

Is there something fundamentally wrong with this idea? And if so, isn't there some easier way for the logic to figure out when it's done and then signal completion using a single bit, zero for not complete, 1 for complete?

Note, everything I've read so far seems to indicate 2 or 4 lines for dedicated communication in asynchronous things. So I don't think that a single "completion bit" on a dedicated line would be too expensive or you can't find room for it.

• If the signal line goes high after an operation completes, what happens on the next operation? It either has to go low again before the next operation (in which case, it needs to know when the other circuit has detected it high), or the logic needs to be reversed for the next operation. If we reverse the logic for the next operation, how do we signal the case where we want to do the operation again with the same input signal values? Whatever solution you find for these questions becomes a handshaking scheme of some kind. Jul 4 at 22:00
• "I'm not exactly sure how to do that," is precisely the problem! If you become sure how, and prove your approach in practice, you'll get at least some good papers out of it. But fair warning : it's one of those areas where people have been stuck since at least the early 1990s... Jul 4 at 22:56
• How do you know how long your "ping" has to be for the other circuit to detect it? If you rely on the other circuit to tell you it detected it, you're handshaking again. If you assume some specific time (10 ns, say) is sufficient, you're now effectively using a clock, and no longer doing asynchronous logic. Jul 4 at 23:36
• Anyway you still need a way for the other circuit to tell you when it's presenting new data to you (in case the new data is identical to the old data)...so when it does that it's basically handshaking your "completed" signal one way or the other. Jul 4 at 23:38
• Imagine one entity is sending operands continuously and faster and the ALU reads them slower. How will you manage this without handshaking? ie., ALU needs some way to say "Oye not now, I am busy". Jul 5 at 6:30

1 Answer

Let me try to summarize what you propose, because I'm not completely sure I follow your description.

You have an ALU (for example) that can perform different computations. Alongside the ALU you have a block of logic that generates a "Done" signal that will go high when the computation is finished. The "Done" logic is designed so that the delay to generate the "Done" signal is equal to the worst-case delay through the ALU for the particular operation being performed rather than the worst-case delay for all possible operations.

What are the problems with this approach? First, consider the complexity of the "Done" logic. How exactly do you intend to generate relatively long delays without using very long strings of logic gates? Remember that the delays in the "Done" logic will vary with temperature and supply voltage, and must track the same variations in the actual ALU. You also need to generate different delays for the different operations. Designing the "Done" logic to very closely track the ALU delays is likely to require a significant amount of logic, which means more power wasted to make "Done", more silicon used, and more expensive chips.

Second, every time you say you will make some delay equal to the "worst-case delay" of some complex function you lose some of the potential speed benefit of asynchronous logic. To really get the most improvement in speed you need to assert "Done" as soon as possible.

When you work through these trade-offs of speed, power consumption, design effort, and chip cost you start to see why asynchronous processors have not become dominant over synchronous processors.

• the delay to generate the "Done" signal is equal to the worst-case delay through the ALU for the particular operation being performed rather than the worst-case delay for all possible operations. Yes exactly right. However, i was imagining a unique done path for every operation, rather than sharing a single done path for the whole ALU that somehow adjusts its propagation delay for a given operation. Obviously these unique paths would be MUX / DEMUX by the CU Instruction Decoder. So how to make long propagation delay? I was thinking either a long path or capacitor to delay the high voltage. Jul 7 at 22:39
• Second, every time you say you will make some delay equal to the "worst-case delay" of some complex function you lose some of the potential speed benefit of asynchronous logic. To really get the most improvement in speed you need to assert "Done" as soon as possible. Yes i completely agree, however the point is to make asynch simplified at the expense of fully optimal speeds. I am pretty sure the worst case of a given op, rather than the entire ALU critical path that needs to be clock-sized appropriately, will still be much much faster than traditional clocked designs. Jul 7 at 22:41
• "A unique done path for every operation" sacrifices computation speed because the actual calculation time is also a function of the operands. For arithmetic operations your circuit will be much slower than necessary. How to make the long delay? That is also a significant problem, because your delay circuit must react to changes in voltage and temperature just like your ALU. Jul 7 at 22:42
• Yes, you may be able to achieve faster average computation, but at what cost in silicon area and power? What happens when you are forced to communicate with synchronous IO devices? Jul 7 at 22:43
• I understand some of the problems you are bringing up, but the cost in silicon area and power? I see nothing in power consumption besides one extra trace and the contacts for a MUX/DEMUX connected to it. Remember that eliminating a clock signal will save significant power. Silicon area, i cannot imagine this would take up much area at all. It is just one extra trace per operation, and the combinational logic of that op will be far far more area than that trace. Remember the MUX/DEMUX are already there, we just need one extra trace to integrate with it. Jul 7 at 22:56