4 ms·

"First, asynchrony may speed up computers. In a synchronous chip, the clock’s rhythm must be slow enough to accommodate the slowest action in the chip’s circuit

"First, asynchrony may speed up computers. In a synchronous chip, the clock’s rhythm must be slow enough to accommodate the slowest action in the chip’s circuits. If it takes a billionth of a second for one circuit to complete its operation, the chip cannot run faster than one gigahertz." Haven't read the whole article yet but pipelining was made specifically to address this exact problem. Also synchronous circuits have a nice property of dealing with metastability. Merging different clock domains is a nightmare and I would love to know how they plan on solving similar issues.

CyberDildonics 11y ago
I think Ivan Sutherland may be aware of pipelining and other issues.
- vvanders 11y ago
  Sure, but it seems disingenuous to throw up a straw man like that rather than address how this stacks up against something that's pipelined properly. AFAIK you're still going to be constrained by propagation delay either way. I totally understand the switching power argument but less so the performance argument.
  - CyberDildonics 11y ago
    At first you said pipelining was made to address the issues brought up in the paper, now you are saying you just want to see how it stacks up to pipeling, which are two different things, so don't call it a straw man to give Ivan Sutherland the benefit of the doubt.
    - vvanders 11y ago
      The straw man is the part I quoted. He talked about slow operations that gate your chip. Pipelining explicitly address this. Unless their async units have better hold times than d-flops they will both be gated by propagation delay. It's a straw man since it never mentions pipelining at all. [edit]Not that I don't have a ton of respect for Sutherland(esp in graphics domain) but it would be nice to see something that admits other approaches.
      - Taniwha 11y ago
        not quite - pipe stages have costs - both in area and flop delay. In particular a particular flip-flop might have a setup time on it's input and a clk->Q delay - for really fast clocks this might be close to 1/4 your clock period. For example let's suppose we have a combined flop delay of 1nS and we have a combinatorial delay (the logic we want to calculate) of 9nS - we can clock this at 100MHz, or we can pipeline it 3 ways split the combinatorial block into 3 3nS chunks - each pipe stage still has a 1nS flop delay so total pipe stage delay is 4nS (250MHz) - we split the logic in 3 but only got a 2.5 times performance increase because of fixed costs Pipelining is a great tool but there is a law of diminishing returns that kicks in here
        vvanders 11y ago
        Thanks, this is the kind of reply I was hoping to get instead of being told I can't comment because some has an important last name.
        CyberDildonics 11y ago
        I never said that, don't turn yourself into a victim.
      - CyberDildonics 11y ago
        But you didn't quote anything
  - Dylan16807 11y ago
    You pipeline whether it's synchronous or asynchronous. The point of being asynchronous is to eke out better performance when only the faster portions are your pipeline are active.
    - FullyFunctional 11y ago
      Other points: * "clock-speed" adapts automatically to gate speed, rather than be dictated (which has to be set conservatively), * allows power savings in multiple ways (no globally propagated screw sensitive clock, finer grained clock gating by construction, and for NCL: wider supply range adaptability) * the absence of a global clock by definition means less simultaneous switching, which reduces strain on power supplies (decoupling) and gives much better EMI.
  - ghettoimp 11y ago
    To make things very concrete, imagine that your pipeline has an execute stage where various operations get executed. Say you have operations for: 1. bitwise AND, which is extremely fast because each bit of the answer is just the AND of the corresponding bits of the inputs. 2. ADD, which is still a fast but is definitely slower than the AND: each result bit depends not only on the corresponding input bits, but also on the earlier bits (to propagate carries). In some barbarically simple timing model: - Each result bit for the AND might take a single gate delay (because it is a single AND gate), but - The highest result bit for the ADD might take (say) 10 gate delays. You'll also need a bit of logic to choose between the above computations depending on the opcode. Let's suppose this selection logic adds another 5 gate delays. Long story short: when executing an AND, the whole result is ready after 6 gate delays. But when executing the ADD, some bits are not ready until 15 gate delays. In a typical clocked design, you will need to run the clock slowly enough to accommodate the slowest such delay, i.e., even when you are executing ANDs, you're running the clock slower than 15 gate delays. The clock needs to run slow enough to accommodate any operation, and doesn't dynamically change on some kind of per-opcode basis (because that would be insanely hard to coordinate with the other pipe stages). In contrast, in an asynchronous design, as far as I understand it, you don't have a clock at all. Instead, the result has an additional "ready" signal associated with it and, whenever the result is ready (a data dependent computation), the next stage can consume it. Ideally this would mean your execute stage could process the AND operations in just 6 clocks instead of having to wait 15 clocks. Ideally, it might also mean you don't need to design your pipeline quite so carefully: in a clocked design, a single slow path slows down the entire pipeline; in an asynchronous design, that one particular path may be slow, but that doesn't slow down everyone else.
    - kevinnk 11y ago
      > In contrast, in an asynchronous design, as far as I understand it, you don't have a clock at all. Instead, the result has an additional "ready" signal associated with it and, whenever the result is ready (a data dependent computation), the next stage can consume it. You can do the exact same thing in clocked designs as well. The AND produces a "ready" signal that allows it's output to skip the stages needed by the ADD side (or conversely, you can have the ADD side produce a stall signal that stops the pipeline). You can actually see this in modern processors - some instructions can take variable amounts of time depending on the instruction arguments (notably loads and stores, but also sometimes multiplies and divides).
  - khedoros 11y ago
    edit: Ghettoimp said something very similar, and probably better than I said it. Say you've got a 2-stage pipeline (for simplicity). Maybe stage 1 has variable execution times, depending on the instruction that is being executed. Maybe stage 2 is faster than the worst-case for stage 1. In all cases, the clock will need to be slower than the slowest step of the pipeline, which means that the circuit may sit idle for a bit of time when stage 1 completed in faster than worst-case time. In an unclocked equivalent, that idle time can potentially be eliminated in the cases where it's not necessary. When stage 1 does a fast operation and stage 2 is ready to receive the result, the data can advance through the pipeline before the clock pulse would've been received in a clocked circuit. Both are constrained by propagation delay, but a clocked circuit is constrained both by propagation delay and the timing of the clock.
- Taniwha 11y ago
  I think he does - the thing is that the speed of synchronous logic is fixed and limited by it's slowest logic - for example how long a a 32-bit adder takes to produce a result depends on its inputs, the worst case involves carry propagation across all 32-bits (we normally spend gates to create shortcuts here) - so for some input data patterns data appears on the outputs much earlier than others, an add that has a nominal delay of 10nS might finish in 1nS for 50% of inputs in a benchmark but only the full 10nS 2% of the time - an asynchronous design might be 5 times faster on reasonable benchmarks (and 10 times when dipped in liquid N2)
vmarsy 11y ago
Could you give a bit more information to non EE experts like me: - What do you mean by pipeline ? I try to make a analogy with the instruction pipelining, which can increase your throughput but it's not fixing the issue that your CPU has a fixed clock rate. - What is metastability? - Why are you mentioning merging clocks as each asynchronous circuit is clock-less ? EDIT: Thanks for all the replies!
- vvanders 11y ago
  I'm not an EE expert either :) Pipelining in circuit design is to take one "large" operation like quoted and break it down into a series of pipeline-able steps. Then the longest stage if your pipeline becomes the slowest path. So if you can break your instruction pipeline up 4-times then you can run at a clockspeed 4x faster without hitting propagation limits. Wikipedia covers metastability pretty well: https://en.wikipedia.org/wiki/Metastability_in_electronics https://en.wikipedia.org/wiki/Metastability_in_electronics Basically any logic gate can act as an oscillator if setup or hold timing is violated. It will bounce from zero to one and no guarantee can be made to the final value. Synchronous gates reduce the probability of this to near-zero(but not completely), you can add successive gates to make it more and more less probable. Basically anything that talks with the real world has a chance to screw up and it's only statistics that keep it from happening. Looks like the Arbiter from the article is what their solution is, although they never explicitly mention metastability: https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 Interesting but had some gnarly implications when it hits a metastable state(10x slower).
- Taniwha 11y ago
  A pipeline means doing an operation in little bits, each in 1 clock time - at the cost of extra latency - so a slow combinatorial function might be split into 3 pipe stages each doing 1/3 of the function with data arriving 3 clocks later Metastability is what can happen if you change data at the instant (or close to the instant) that a synchronous flip-flop is clocked - the resulting value that's stored is neither a 1 or a 0 but instead the storage element ends up oscillating at a high frequency - this little bit of evil can infect subsequent logic stages resulting in a chip that's a horrible hot buzzy mess of crud
Taniwha 11y ago
the thing is that pipelining costs latency, great if you're making something where all the inputs come into the input stage at the beginning and come out of the output stage at the end. Not so good if you want to make something like a CPU where the output of one instruction is the input for another which can result in pipe bubbles - clock speed, latency (pipe stages) etc are tradeoffs - one wants to maximise instructions-per-clock times clock speed for meaningful benchmarks Merging arbitrary clock domains is an understood problem, simply put we know it can't be done reliably, one simply has to make it "reliably enough" - I built a graphics controller once where we did the math on synchoniser failure and decided that we were more reliably than Win95 by 2 orders of magnitude and that that would be good enough ... Async stuff tends to be clocked stage to stage at the local level so that data generates it's own clock equivalent when it's done (a 'done' signal)

CyberDildonics 11y ago

I think Ivan Sutherland may be aware of pipelining and other issues.

vvanders 11y ago
Sure, but it seems disingenuous to throw up a straw man like that rather than address how this stacks up against something that's pipelined properly. AFAIK you're still going to be constrained by propagation delay either way. I totally understand the switching power argument but less so the performance argument.
- CyberDildonics 11y ago
  At first you said pipelining was made to address the issues brought up in the paper, now you are saying you just want to see how it stacks up to pipeling, which are two different things, so don't call it a straw man to give Ivan Sutherland the benefit of the doubt.
  - vvanders 11y ago
    The straw man is the part I quoted. He talked about slow operations that gate your chip. Pipelining explicitly address this. Unless their async units have better hold times than d-flops they will both be gated by propagation delay. It's a straw man since it never mentions pipelining at all. [edit]Not that I don't have a ton of respect for Sutherland(esp in graphics domain) but it would be nice to see something that admits other approaches.
    - Taniwha 11y ago
      not quite - pipe stages have costs - both in area and flop delay. In particular a particular flip-flop might have a setup time on it's input and a clk->Q delay - for really fast clocks this might be close to 1/4 your clock period. For example let's suppose we have a combined flop delay of 1nS and we have a combinatorial delay (the logic we want to calculate) of 9nS - we can clock this at 100MHz, or we can pipeline it 3 ways split the combinatorial block into 3 3nS chunks - each pipe stage still has a 1nS flop delay so total pipe stage delay is 4nS (250MHz) - we split the logic in 3 but only got a 2.5 times performance increase because of fixed costs Pipelining is a great tool but there is a law of diminishing returns that kicks in here
      - vvanders 11y ago
        Thanks, this is the kind of reply I was hoping to get instead of being told I can't comment because some has an important last name.
        CyberDildonics 11y ago
        I never said that, don't turn yourself into a victim.
    - CyberDildonics 11y ago
      But you didn't quote anything
- Dylan16807 11y ago
  You pipeline whether it's synchronous or asynchronous. The point of being asynchronous is to eke out better performance when only the faster portions are your pipeline are active.
  - FullyFunctional 11y ago
    Other points: * "clock-speed" adapts automatically to gate speed, rather than be dictated (which has to be set conservatively), * allows power savings in multiple ways (no globally propagated screw sensitive clock, finer grained clock gating by construction, and for NCL: wider supply range adaptability) * the absence of a global clock by definition means less simultaneous switching, which reduces strain on power supplies (decoupling) and gives much better EMI.
- ghettoimp 11y ago
  To make things very concrete, imagine that your pipeline has an execute stage where various operations get executed. Say you have operations for: 1. bitwise AND, which is extremely fast because each bit of the answer is just the AND of the corresponding bits of the inputs. 2. ADD, which is still a fast but is definitely slower than the AND: each result bit depends not only on the corresponding input bits, but also on the earlier bits (to propagate carries). In some barbarically simple timing model: - Each result bit for the AND might take a single gate delay (because it is a single AND gate), but - The highest result bit for the ADD might take (say) 10 gate delays. You'll also need a bit of logic to choose between the above computations depending on the opcode. Let's suppose this selection logic adds another 5 gate delays. Long story short: when executing an AND, the whole result is ready after 6 gate delays. But when executing the ADD, some bits are not ready until 15 gate delays. In a typical clocked design, you will need to run the clock slowly enough to accommodate the slowest such delay, i.e., even when you are executing ANDs, you're running the clock slower than 15 gate delays. The clock needs to run slow enough to accommodate any operation, and doesn't dynamically change on some kind of per-opcode basis (because that would be insanely hard to coordinate with the other pipe stages). In contrast, in an asynchronous design, as far as I understand it, you don't have a clock at all. Instead, the result has an additional "ready" signal associated with it and, whenever the result is ready (a data dependent computation), the next stage can consume it. Ideally this would mean your execute stage could process the AND operations in just 6 clocks instead of having to wait 15 clocks. Ideally, it might also mean you don't need to design your pipeline quite so carefully: in a clocked design, a single slow path slows down the entire pipeline; in an asynchronous design, that one particular path may be slow, but that doesn't slow down everyone else.
  - kevinnk 11y ago
    > In contrast, in an asynchronous design, as far as I understand it, you don't have a clock at all. Instead, the result has an additional "ready" signal associated with it and, whenever the result is ready (a data dependent computation), the next stage can consume it. You can do the exact same thing in clocked designs as well. The AND produces a "ready" signal that allows it's output to skip the stages needed by the ADD side (or conversely, you can have the ADD side produce a stall signal that stops the pipeline). You can actually see this in modern processors - some instructions can take variable amounts of time depending on the instruction arguments (notably loads and stores, but also sometimes multiplies and divides).
- khedoros 11y ago
  edit: Ghettoimp said something very similar, and probably better than I said it. Say you've got a 2-stage pipeline (for simplicity). Maybe stage 1 has variable execution times, depending on the instruction that is being executed. Maybe stage 2 is faster than the worst-case for stage 1. In all cases, the clock will need to be slower than the slowest step of the pipeline, which means that the circuit may sit idle for a bit of time when stage 1 completed in faster than worst-case time. In an unclocked equivalent, that idle time can potentially be eliminated in the cases where it's not necessary. When stage 1 does a fast operation and stage 2 is ready to receive the result, the data can advance through the pipeline before the clock pulse would've been received in a clocked circuit. Both are constrained by propagation delay, but a clocked circuit is constrained both by propagation delay and the timing of the clock.
Taniwha 11y ago
I think he does - the thing is that the speed of synchronous logic is fixed and limited by it's slowest logic - for example how long a a 32-bit adder takes to produce a result depends on its inputs, the worst case involves carry propagation across all 32-bits (we normally spend gates to create shortcuts here) - so for some input data patterns data appears on the outputs much earlier than others, an add that has a nominal delay of 10nS might finish in 1nS for 50% of inputs in a benchmark but only the full 10nS 2% of the time - an asynchronous design might be 5 times faster on reasonable benchmarks (and 10 times when dipped in liquid N2)

vmarsy 11y ago

Could you give a bit more information to non EE experts like me: - What do you mean by pipeline ? I try to make a analogy with the instruction pipelining, which can increase your throughput but it's not fixing the issue that your CPU has a fixed clock rate. - What is metastability? - Why are you mentioning merging clocks as each asynchronous circuit is clock-less ? EDIT: Thanks for all the replies!

vvanders 11y ago
I'm not an EE expert either :) Pipelining in circuit design is to take one "large" operation like quoted and break it down into a series of pipeline-able steps. Then the longest stage if your pipeline becomes the slowest path. So if you can break your instruction pipeline up 4-times then you can run at a clockspeed 4x faster without hitting propagation limits. Wikipedia covers metastability pretty well: https://en.wikipedia.org/wiki/Metastability_in_electronics https://en.wikipedia.org/wiki/Metastability_in_electronics Basically any logic gate can act as an oscillator if setup or hold timing is violated. It will bounce from zero to one and no guarantee can be made to the final value. Synchronous gates reduce the probability of this to near-zero(but not completely), you can add successive gates to make it more and more less probable. Basically anything that talks with the real world has a chance to screw up and it's only statistics that keep it from happening. Looks like the Arbiter from the article is what their solution is, although they never explicitly mention metastability: https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 https://en.wikipedia.org/wiki/Arbiter_%28electronics%29 Interesting but had some gnarly implications when it hits a metastable state(10x slower).
Taniwha 11y ago
A pipeline means doing an operation in little bits, each in 1 clock time - at the cost of extra latency - so a slow combinatorial function might be split into 3 pipe stages each doing 1/3 of the function with data arriving 3 clocks later Metastability is what can happen if you change data at the instant (or close to the instant) that a synchronous flip-flop is clocked - the resulting value that's stored is neither a 1 or a 0 but instead the storage element ends up oscillating at a high frequency - this little bit of evil can infect subsequent logic stages resulting in a chip that's a horrible hot buzzy mess of crud

Taniwha 11y ago

the thing is that pipelining costs latency, great if you're making something where all the inputs come into the input stage at the beginning and come out of the output stage at the end. Not so good if you want to make something like a CPU where the output of one instruction is the input for another which can result in pipe bubbles - clock speed, latency (pipe stages) etc are tradeoffs - one wants to maximise instructions-per-clock times clock speed for meaningful benchmarks Merging arbitrary clock domains is an understood problem, simply put we know it can't be done reliably, one simply has to make it "reliably enough" - I built a graphics controller once where we did the math on synchoniser failure and decided that we were more reliably than Win95 by 2 orders of magnitude and that that would be good enough ... Async stuff tends to be clocked stage to stage at the local level so that data generates it's own clock equivalent when it's done (a 'done' signal)