4 ms·

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

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...

javcasas 11y ago
"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: 1. For each input, decide the output 2. Simplify the function using a Karnaugh Map https://en.wikipedia.org/wiki/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,14_anti-race.svg 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/20071022024729!K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg 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/20100810221056!K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg https://upload.wikimedia.org/wikipedia/commons/archive/0/02/...
- throwaway000002 11y ago
  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!
  - javcasas 11y ago
    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.
    - throwaway000002 11y ago
eternalban 11y ago
> Us software people .. 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.)
- throwaway000002 11y ago
  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...
  - eternalban 11y ago
    (Hardware has 'soft partitions' that manifest as pipeline stalls.) My point was merely that H/W people had to confront this issue before us.
StringyBob 11y ago
Modern system-on-chip designs don't really use a global clock anyway. It's more just local synchronous islands which communicate over asynchronous interfaces - i.e. https://en.wikipedia.org/wiki/Globally_asynchronous_locally_synchronous https://en.wikipedia.org/wiki/Globally_asynchronous_locally_...

javcasas 11y ago

"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: 1. For each input, decide the output 2. Simplify the function using a Karnaugh Map https://en.wikipedia.org/wiki/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,14_anti-race.svg 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/20071022024729!K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg 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/20100810221056!K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg https://upload.wikimedia.org/wikipedia/commons/archive/0/02/...

throwaway000002 11y ago
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!
- javcasas 11y ago
  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.
  - throwaway000002 11y ago

eternalban 11y ago

> Us software people .. 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.)

throwaway000002 11y ago
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...
- eternalban 11y ago
  (Hardware has 'soft partitions' that manifest as pipeline stalls.) My point was merely that H/W people had to confront this issue before us.

StringyBob 11y ago

Modern system-on-chip designs don't really use a global clock anyway. It's more just local synchronous islands which communicate over asynchronous interfaces - i.e. https://en.wikipedia.org/wiki/Globally_asynchronous_locally_synchronous https://en.wikipedia.org/wiki/Globally_asynchronous_locally_...