Gateless Majority Logic

Discussion in 'All non-AMD/Intel CPUs' started by KD5ZXG, Feb 13, 2018 at 3:48 AM.

  1. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    In 1954, Goto Eiichi (Eiichi Goto in English, except he wasn't) developed an oscillating magamp that
    could perform majority vote logic, amplify the winning state, and hold the result for as long as needed
    in one of two possible phase locks. All without transistors or tubes, just ordinary capacitors and slightly
    overdriven inductors. He named this logic device "Parametron".

    Several early Parametron Computers were built. And from the user perspective, they worked just like
    ordinary computers made of gates. NEC put out a brochure for one in English that clearly shows just
    how boringly normal these could be if you never looked under the hood. A few tubes were used for
    convenience to pump the oscillators, but they wern't doing logic with those tubes. An alternator could
    have provided the same pump waveforms for all that mattered.

    Familiar gates like NAND and NOR have dedicated inputs and outputs. Majority logic is also possible
    with gates, but doing so would miss out on several interesting advantages. Majority logic devices were
    usually symmetrical, having I/Os without direction. Logic would pulled forward by a three phase clock
    that powered down selected banks of devices to forget thier stored state and accept new votes. This
    may sound inconvenient, but is powerful important. Because I will show how a programmable array
    of such devices can pull logic forward, backward, or sideways...

    So how do we compute with majority logic? Well, majority only makes sense if we start with an odd
    number of votes, so there will always be an unambiguous winner. You can make a pretty good true
    random number generator by having no inputs. But for normal Boolean logic we need at least three
    votes. The majority of (1,X,Y) gives the same answer as OR. The Majority of (0,X,Y) gives the same
    answer as AND. These devices were usually differential, so that NAND and NOR were as simple as
    reversing the pair of output wires, giving us Minority Logic.

    NAND and NOR are universal gates that can build anything. A minority of three gate replaces both.
    NOR gates and nothing but NOR gates took people to the moon. Parametrons havn't quite gotten
    there yet, though they certainly could have. But looking forward, gated logic is making less sense
    as transistors become impossibly small. Directionless logic may become the easier trick to pull off.
    Majority of three spins or something, way more than one way to skin that cat. Will even show how
    majority logic can be done using only light. Not that light is practical yet, just saying its been done.

    So we got NAND and NOR. Also stores the result like a one bit memory or flipflop. What else can
    it do? The Majority of (X,Y,Z) gives us CARRY. Cool, so we now have an Arithmetic Logic Unit
    that can do a math function or either of two logic functions! Lets complete the ADD function with a
    five way vote of (X,Y,Z,NotCarry,NotCarry). Question: How many gates does that usually take???

    I'll let you google yourselves up to speed on this, while I gather up the promised attachments.
     
    Last edited: Feb 13, 2018 at 11:45 PM
  2. GoldenTiger

    GoldenTiger 3.5GB GTX 970 Slayer

    Messages:
    17,579
    Joined:
    Dec 2, 2004
    Ummm, is this homework or something?
     
  3. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    If you are having to ask, that means its probably on the test.
    Nah, its only if you want to be ready before quantum takes over.

    I don't mean the weird cold stuff with entanglements and qbits.
    None the less: Minds and faces shall be thoroughly melted.
     
    Last edited: Feb 14, 2018 at 12:40 PM
  4. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    Lets start off on the right foot by breaking promises.
    I said no gates, but have gone ahead and drawn gates anyhow for clarity.
    We can mess with the flow of gateless logic after we establish some basics.

    This is a full adder in Differential Majority Logic.
    We add up the input bits, and if there's a majority, thats a Carry.
    We add up the input bits, subtract two carries, and that gives us the Sum.

    Two gates vs nine? Might be something to this majority nonsense...
    If doing ripple carry, also consider that Carry has only one gate of delay.

    FullAdd.png
    Full_Adder_Nand.png

    To be fair:

    With two more NAND, and permit one to have three inputs: Carry delay
    could be improved to 2 gates. That improvement would simply emulate
    three input majority logic using four NANDs and twice as many steps...

    Implementation+Using+NAND+Gates+(cont.).jpg

    If we disallow five input majority, and had to do it with just three inputs:
    It takes one extra gate, and delay is no worse. I didn't choose to begin
    with that drawing, because it was less obvious how addition happens.
    The drawing on the left below...


    1-s2.0-S0026269216000355-gr6.jpg

    But its all a hella lot simpler than all this, cause we won't be using gates.
    Before I hit you with oscillators, lets try voting with simple flipflops next.
    Then be prepared to throw your comfort zone of a fixed direction of flow
    out the window...
     
    Last edited: Feb 14, 2018 at 8:56 PM
  5. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    Take a break from thinking about it too hard. And take a look at two real
    examples of computers built with majority logic, specifically Parametrons...

    0035_01_l.jpg

    Be aware: Brochure below is for a different computer than pictured above.
    But they are similar enough to put the point across. Completely normal
    computers have been built of a logic you might never before have known.
     

    Attached Files:

    Last edited: Feb 14, 2018 at 8:41 PM
  6. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    And its not just about the 1950s. Majority logic has been done in pure light.
    Look Ma, no gates!!! Ok, so maybe it has a lid. But no gates, no wires, no
    transistor. Light doesn't seem small or practical yet, but maybe someday.

    300px-IR_Optical_Parametric_Oscillator.JPG

    At scales so small that transistor gates stop working, majority logic still gets
    the job done. Thats why we might spend a few moments rediscovering it.
     
    Last edited: Feb 14, 2018 at 8:54 PM
  7. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    So, here's a simplified drawing of a majority logic flipflop.
    When this device turns on, it will immediately latch to one
    logic state or the other. Inputs can vote upon that decision.

    But once decided, its stuck with that memory forever.
    Further input changes will be ignored. Or at least until a
    CLEAR pulse comes along to cut the power and make
    it forget.

    Floptron.png

    But what isn't so obvious: The outputs resistively couple to the
    next flipflop exactly like inputs coupled from the flipflop before.
    The damn thing is symmetrical with four identical pairs of I/O!

    What keeps the output from being an input and spoiling the vote?
    I will give that answer shortly, just need to draw a new picture.
     
    Last edited: Feb 15, 2018 at 5:08 PM
  8. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    In classic Parametron Computers, three phases of clock were used to move the logic forward.
    Nevermind for now that Parametrons are oscillators and not flipflops...

    Sleeping cells forget, and cast no vote (I/O pairs either disconnect or pull to the same voltage).
    Votes are pulled into an empty cell as it wakes, only clocks can say which direction is forward.
    This shift register would work just as well backward, if the clocks were phased that way...


    ThreePhaseFlow.png
     
    Last edited: Feb 16, 2018 at 7:59 PM
  9. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    For a big mess of wires that go exactly where they need to and nowhere else, three phases suffice.
    Post #5 shows us two perfect examples of partially wire directed flow that used only three phases.
    But might be handy to have more than three phases to pull logic through an array where the wires
    are fixed only to neighboring cells. Each cell would be programmed to sleep on specific phases.

    Because input and output occur on different phases, any cell of this array could have as many as
    four inputs, and on the next phase as many as four outputs. Though all connections drawn here
    are non-inverting, obviously sometimes signals will need to invert. Maybe we could add diagonal
    connections, and let those invert...

    Oscillating Parametrons had a constant reference zero that could be hardwired, or wire-inverted
    to 1 wherever needed. That wiring is not going to work for an array. But each cell could be made
    slightly unbalanced, such that a tie always results in a constant.

    ArrayFlow.png

    The array could be haxagonal instead of square, no problem. Also nothing stopping us from
    stacking multiple layers and pulling the flow of logic around in 3D. Having at least two layers
    neatly solves the issue of allowing signals to cross each other...

    Might add a few axons, so signals can reach remote places faster than taking Conway's glider.
    http://www.mezzacotta.net/garfield/?comic=652

    We ain't trying for a slow propagating cellular automata using only local dendrites, nor a big
    mess of wires with only axons, but something sensible that leverages the best of both.
    In the end, anything practical will have to be a mix of programmed and prewired flows.
    For programming majority arrays in VHDL, let how it flows be the compiler's problem.
     
    Last edited: Feb 17, 2018 at 7:39 PM
  10. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    The magnetic energy stored in an inductor is one half of it's Henry rating times the current flowing through it squared.
    E=0.5*H*A*A. You don't need to memorize that equation...

    If we reduce the Henry parameter while a current is flowing, that current tries to increase. When Henries go down,
    Amps go up. Because energy freewheeling in the inductor's magnetic flux prefers to remain about the same...

    If we build a tuned circuit consisting of a capacitor and variable inductor, its not just gonna start oscillating all by itself.
    But any small current in that variable inductor, perhaps a vote or even random noise if no vote, can be given a kick by
    periodically reducing Henries. And then, you have a Parametron.

    The most effective period is to pull back Henries twice each cycle of oscillation, so that the tuned circuit picks up
    current both coming and going. Eventually amplifiying swing to full scale, and locking onto 1/2 the pump frequency.
    But we could swap going half cycles for coming half cycles, it would amplify and hold that oscillation just as well.

    And that is the difference between a stored one and a stored zero. Could lock onto the odd pump cycles, or the even
    pump cycles. If we listen to the resulting zeros and ones, the same as audio data stored on some early casette tapes.
    Binary Phase Shift Keyed.

    Next post, we cover a way to reduce Henries on demand. And with pics that will hopefully make better sense.
    Some extra confusing side notes first...

    -----------------

    There are other parameters we could twiddle: Variable capacitors can give a boost to Voltage when Farads reduce.
    Same way a condensor microphone works E=0.5*F*V*V. We wouldn't build an oscillator out of mics, that would be
    kinda useless. Variable capacitance across the depletion region of a diode has sometimes been paired with a fixed
    inductor...

    Or the optical table I showed earlier, with a nonlinear piece of glass. Pump it with blue laser, and excite an infrared
    oscillation of half frequency. Don't know the actual color used, just imagining blue. Its called a "Degenerate Optical
    Parametric Oscillator". Degenerate in this case meaning it has only two possible phase relationships. Not exactly
    what degenerate usually means around here.

    Compare the phase of two of these, and you have an excellent true random zero or one, that holds until you turn it
    off and let it forget. Parametrons are excellently balanced to amplify a true random from noise, not like flipflops that
    tip predictably on no-input.

    ------------------

    Parametric amplifiers and oscillators are also useful for receiving weak signals from distant spacecraft. Inductors
    and caps have a lot less noise than transistors. Signals in good phase with 1/2 the reference pump are amplified,
    everything else attenuated. It can really clean things up.
     
    Last edited: Feb 17, 2018 at 4:21 PM
  11. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    Julius Sumner Miller, or Scanners? You decide...


     
  12. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    Alright, picking up the pieces from where our heads exploded...

    You might note a strange pair of toroidal transformers labeled "Excitation."
    Those two are wired to buck each other and produce no transformer action.
    The puprose is to overdrive (saturate) those donuts and reduce inductance,
    without acting like a transformer. Actually its acting like a magamp.

    Parametron Works.png

    Inputs and outputs can be coupled from the same donut. I dunno why the output on
    the right was directly coupled, except it doesn't matter and saved a few turns of wire.

    ----------------

    Example below I built as a random number generator, without inputs.
    One coupling donut shy of what you read about in the paper above.
    I also ran DC bias on a solid wire, separate from 2f excitation (blue),
    which proved an unecessary feature that didn't make any difference.

    Solder blob on the right is the midpoint where the two donus connect to each other.
    You might expect that to be in the middle of the picture, but I had to work with wires
    that were already glued to the donuts. So they are not mirror image of each other.

    MyParametron.png

    Now, where the gate???? Ain't none, except maybe three for shutting down clock lines.
    A clock line might then be shared by several parametrons of the same timing group.

    But we don't even need gates for clocks. Imagine a pair of mechanical alternators
    spinning at slightly different rates, and evenly mix those outputs. They will reinforce,
    cancel, reinforce, cancel, reinforce, cancel, and create the required clock waveform.

    Reading the output phase was sometimes as simple as a neon bulb wired between
    a known reference zero and an unknown output. If they were enough different, the
    bulb would light. Neon wouldn't light at low voltage and screw up a vote that hadn't
    yet been amplified to full scale. A shift register like that might make a cool clock,
    like the kind you might hang on a wall...
     
    Last edited: Feb 18, 2018 at 12:43 PM
  13. KD5ZXG

    KD5ZXG Limp Gawd

    Messages:
    277
    Joined:
    Mar 24, 2017
    Majority logic can be built of an amazing variety of things, including gates but not limited to them.
    Once you get your head around it: Majority logic could easily be made of out of water, golfballs,
    light, single electrons, memristors, magnets, quantum dots, tunnel diodes, the list is just endless...

    But not all ways of performing majority logic are inherently differential, nor do all of them provide
    minority logic, or inversion. Except thats not an actual problem, you just have to know the trick.

    If I build two single-ended non-inverting majority gates and operate them in parallel: Such that
    one operates on inputs (X,Y,Z) , while the other operates on inputs (X/,Y/,Z/) , the combination
    provides exactly the same outputs as a differential gate. Which means we can simply swap
    signal wires anytime inversion is needed for free, with no delay. No need for any real inverter.

    I tend to prefer differential for electronic implementation, because the tipping threshold sets
    itself reliably without need for tweaking. Single ended implementaions make more sense as
    one gets smaller, where thresholds become reliable properties of physics. But might need to
    lean on the parallel trick, when no better way of inverting easily presents itself.

    InversionWithoutInversion.png
     
    Last edited: Feb 18, 2018 at 12:32 PM