Editing Relay CPU

[[File:Main-G5Q-14.jpg|right]]
A '''relay CPU''' is a CPU built mostly or entirely out of [[relays]].

While at one time relays were the best available component for building a computer,
nowadays one of the few advantages of a relay CPU over other CPU implementations is that you can see it working (very educational) --
building a CPU on a FPGA or other integrated chip makes it use less power, run faster, cost less, etc. than a relay CPU.

Harry Porter built his
[http://web.cecs.pdx.edu/~harry/Relay/ "Relay Computer"]
out of 415 Relays, all identical 4PDT.

Jon Stanley built 
[http://www.electronixandmore.com/project/relaycomputertwo/index.html "Relay Computer Two"],
a relay computer built from 281 relays.

Is it possible to build a relay CPU from significantly fewer relays?
In particular, is is possible to build a relay CPU from 100 relays or less?

Perhaps we should have 2 categories:
* What's the minimum number of relays in a relay-only CPU?
* What's the minimum number of relays in a diode-relay CPU?

== lots of miscellaneous tibits that seem kind of related to building a relay CPU ==

What is a good simulator for a relay computer?

Tofu relay circuit simulator.
[http://meatfighter.com/tofu/]
[http://meatfighter.com/tofu/tutorial/index.html]

http://en.wikipedia.org/wiki/Quite_Universal_Circuit_Simulator

tkgate open-source gate-level schematic entry and simulator
[http://www.tkgate.org/]

http://electronics.stackexchange.com/questions/7022/circuit-simulation-software


Bouncing is not a problem inside a relay CPU,
but it can be a problem when you try to interface a relay CPU to a semiconductor RAM.
What is a good method for
[http://www.ganssle.com/debouncing.pdf debouncing]?



[http://www.kk.org/thetechnium/archives/2009/02/amish_hackers_a.php "Amish Hackers"]
claims that 
<q>The Amish call this pneumatic system "Amish electricity."</q>

One of the commenters said "... there are pneumatic equivalents to electrical devices. Air - is there anything it can’t do?"

I wonder how difficult it would be to build a CPU that, instead of being built of ICs or discrete transistors or relays, was built from pneumatically-powered devices.

Then, of course, put it in a case that looks like this:
"Steampunk Frankenstein computer casemod"
http://blog.makezine.com/archive/2009/02/frankenstein_casemod.html


[http://www.fastchip.net/howcomputerswork/p1.html "How Computers Work"]
by Roger Young
uses a relay computer in many examples.


Some nice features that will make it easier to find and fix the inevitable mistakes people make when wiring up something as complicated as a CPU:
* single-step-ability
* breakpoints
* lots of LEDs (If you make the traditional hard-wired diode array for microcode, building it out of LEDs might be cool)
* minimum # of chips to wire together

* testability: single-step, breakpoints on program address, breakpoints on data address, breakpoints on data write address ... what other testability things are useful?


You need to balance:
* Many programmers appreciate lots of general-purpose registers, rather than needing to remember a bunch of quirks associated with each register. Since memory is slow, keeping the "working set" of data in registers helps reduce the pressure on the memory interface (von Neumann bottleneck).
* Fewer registers
--> directly easier to build because you don't have to build and test those registers.
--> indirectly easier to build because there is less stuff (microcode, etc) needing to select *which* register.
* instructions that only work with *some* registers (quirky) --> less stuff needed to select *which* register.

On the other hand, if you implement the registers in a small SRAM,
having more than a minimum number is also helpful:
* no need for complicated indirect indexed addressing modes
--> indirectly easier to build because fewer addressing modes to build and test.

Also,
* more registers makes the "carry bit" or other status bits less necessary.



building a computer (except for the RAM and program storage) out of relays:
we have 2 slightly-contradictory desires:
* would be nice to use the fewest number of relays, because each one will need
  to be hand-wired, and each "on" coil dissipates power.
* would be nice to do a bunch of work on each clock cycle, so we can get the
  same amount of work done in fewer clock cycles, reducing wear-and-tear on
  the relays ... and if the relays are optimally driven (approximate with "snubber" in series with coil, where the snubber is a parallel RC), it takes less power
to "hold" the relay than to switch states.
I suspect that balancing these 2 requirements is very similar to optimizing
similar requirements for minimizing power in purely solid-state logic.





relay computer

2008-05-22:
DAV:
thinking about building a cpu out of relays.
standard 4 phase clock should work.
But can relays support the setup and hold time requirements for 2 phase clock?

Say we have a series of transparent latches.
(They will have some combinational logic between them -- I'll ignore the combinational logic while trying to answer this question).

Each "layer" of transparent latches is transparent on the "opposite" phase.

On the falling edge of the clock:
low-transparent latches become transparent, letting their inputs flow through to their outputs. (They may switch states).
hi-transparent latches go into "hold" state, maintaining that bit until the rising edge of the clock. (They don't switch states).

So ... for 2 phase clock to work,
the low-transparent latches need to hold their "hold" bit long enough for the hi-transparent latches to grab it.


one teensy glitch:
during transitions, with a break-before-make relay,
there is a short time when the output is "disconnected" -- typically representing "0".
Is that going to cause a problem?
No.
      +------------+
      |            |
 0 --|0\           |
     >  >--+       |
 1 --|1/   |       |
          +--|0\   |
             >  >--+------- Q
 D ----------|1/
              |
 CLK ---------+

This is a CLK-Hi-transparent latch.

 CLK _____/---------\_________

 D ________XXXXXXXX-----------

 Q _____________________/-----

I suspect relays will have a pretty high latency -- after the CLK (driving the coil) changes state, it will be a while before the contact is broken.


So:
transparent-to-hold transition:

C relay coil changes state.
Sometime later, the D contact breaks contact, and Q become the "not connected" state.
Sometime after that, the Q contact makes contact, and Q becomes the held state.
Hopefully the time between the break and the make is short enough that the short glitch at the Q relay coil isn't enough for it to change state.

After the D contact breaks contact, clearly the D contact is in the "don't care" state.

hold-to-transparent transition:
C relay coil changes state.
Sometime later, the Q contact breaks contact, and Q becomes the "not connected" state.
Sometime after that, the D contact makes contact, and Q becomes the transparent state.
Hopefully the time between the break and make is short enough that the short glitch at the Q output isn't enough to affect stuff downstream.

master-slave bit:
first latch transparent-to-hold, 2nd latch hold-to-transparent transition:
... doesn't seem to be a problem.

first latch hold-to-transparent, 2nd latch transparent-to-hold:
Both C relay coils change state.
Sometime later, there is a break in the contact, and the internal Q and the outer Q both become the "not connected" state.
Sometime after that, the 2nd latch Q contact makes contact, and Q becomes the held state.
Hopefully the time between the break and the make is short enough that the short glitch at the 2nd Q relay coil isn't enough for it to change state.

----

2010-09-22:DAV:
Would the ideal computer for
implementing Wheeler's diverse double compiling ("DDC")
( wheeler-trusting-trust-ddc.pdf )
be a relay computer?
Especially for Wheeler's comment that
"Future potential work includes recompiling an entire operating system as the compiler-under-test".
There are 2 operations that need to be trustworthy:
* compiling some ancestor source code to a compiler executable
* comparisons.

Perhaps it would be better to build 2 separate relay machines,
each one dedicated to a different part:
* a "compare" relay machine:
Compares every byte on 2 MMC/SD cards and confirms that they are identical.
Perhaps gives some sort of display to indicate which byte is different.
* a "compile" relay machine:
runs a compiler executable (off one SD/MMC card?),
with the source code to some ancestor compiler (on another SD/MMC card?),
and store the resulting executable on a SD/MMC card.

Then the DDC process is something like:
* somehow (?) create a trustworthy compiler executable, in relay computer machine code, on one MMC/SD card
* somehow (?) store a compiler source code on another MMC/SD card
* plug both cards and an output blank card into the relay computer, and
generate the ancestor compiler
plus the boot code and everything else required to start a working environment
(targeted to the fast computer).
* plug the ancestor SD/MMC card into a fast computer, and boot off that card.
Use that trustworthy environment
to more rapidly executed the later stages of the DDC process, and
to inspect source code.

So does this necessarily mean the relay computer needs to be able to run a C compiler?
(perhaps TCC or the bootstrap for GCC)?
Or is it possible for it to run, say, a Forth compiler?
(I suspect that would require less RAM on the relay machine).
That seems  to require that a bootstrap C compiler be written
with its source code in Forth.
(Either that Forth source is compiled on the relay machine,
or that Forth source is compiled on the fast computer).

----

2011-03-10:DAV:
I come across yet another relay computer:
http://nablaman.com/relay/

3 x 8-bit accumulator registers,
2 x 12-bit registers (for index, addresses and jumps)
plus a 12 bit program counter and 12 bit stack register.

DAV: I think it would be interesting to
re-arrange the 3 x 8-bit register bits to make 2 x 12-bit registers,
so "everything" is 12 bits.

Another non-multiple-of-8 machine I came across today:
The Six Bit Machine
by Jack Eisenmann
http://web.me.com/teisenmann/sixbit/main.html

----

2008-12-15:DAV:
Yet another idea for a relay computer:
wacky mix of relays and 74x ICs.
* use 74x shift registers to hold bits (registers, PC, IR, interrupt request, perhaps carry bit)
* use relays to guide the bits in the correct direction -- in particular, the output of one shift register to the input of the "deeper" register when doing a "push"; the output of one register to the input of a shallower register when doing a "pop".
* Use a random mix of relays and 74x 4:1 muxes to implement more complex logic.
During operation,
* one big *chunk* as IR is latched and relay configuration is set up.
* then 8 (or perhaps 12 or 16 or 24 or 48) quiet (or quieter) pulses as bits are shuffled out of some registers and into other registers.

Hopefully building it as a "serial computer" will make it smaller.



----

2008-08-22:DAV:
Applications for a relay computer:
* cryptographic applications -- because I can *see* it work, it's far more difficult for malware or keyloggers.
** AES encryption and decryption
** public/private key generation
** public/private key encryption and decryption

What sorts of operations do we need to support to be able to do AES reasonably efficiently?

-----

2009-02-03:DAV:

Inspired by 
Magic-1 http://www.homebrewcpu.com/

I make my own goals for my relay computer:

Goals:

* Touch the magic. Gain a deeper understanding of how computers work.

* Compactness. Physically small and simple.
Unlike Bill, I'm not so interested in the "density" of each opcode
individually (Huffman-like compression).
I'm even more interested in the "density" of the instruction
set as a whole (LZ77-like compression), so I insist on extremely low overhead
for subroutines.

* TTL and transistors and relays rather than FPGA.
FPGAs do sound fun, but I want a system where I can touch and see and hear
everything it is doing, rather than a mysterious black box -- I want
(literally) every bit
visible.
Perhaps FPGA for the next one.

* simplicity.

* Build something real.

Like Bill, "At the end of the day, I wanted a working, and useful, machine
that I understood completely.  Oh, and it had to have a real front panel with
lots and lots of cool blinky lights."
-- Bill Buzbee



[relay computer]

2008-10-19:
found even cheaper relays at All Electronics:

$0.50 24 VDC SPDT PC MOUNT POWER RELAY; 480 Ohm coil; completely uncovered so I can see what's going on.
http://www.allelectronics.com/make-a-store/item/RLY-275/24-VDC-SPDT-PC-MOUNT-POWER-RELAY/-/1.html

2009-11-30:
$1.00 5VDC DPDT SUB-MINI RELAY; 14.9 x 7.4 x 9.7mm high. PC pins.; 178 Ohm coil; CAT# RLY-538 (All Electronics 2009)
$1.00 24VDC DPDT DIP RELAY; 0.63" x 0.38" x 0.31" high. ( 16 x 9.7 x 7.9 mm ); 2850 Ohm; CAT# RLY-505 (All Electronics 2009)


Jon Stanley suggests saving money by getting relays using eBay.

I am surprised that reed relays cost more than PCB relays,
since it seems that reed relays have fewer parts and so would cost less.


2008-08-10:DAV:
what about "latching relays" ?
Wouldn't that implement a register array in fewer relays than non-latching relays?
Does it make sense to build Mueller C-elements for asynchronous computing out of latching relays?



wire spring relay
http://en.wikipedia.org/wiki/Wire_spring_relay
claims that
"Reed relays are better suited to data storage."

reed relay
http://en.wikipedia.org/wiki/Reed_relay
claims that
"reed relays can switch much faster than relays with armatures"


----

2008-09-06:DAV:
I discover
"Relay Computer Two"
by Jon Stanley
http://www.electronixandmore.com/project/relaycomputertwo/index.html
a relay computer built from 281 relays
...
That is far fewer relays than I thought were needed.

Registers:
All registers are "transparent".
("master/slave" would require twice as many registers).


DAV: (Would it make any sense to re-arrange the muxes so that
PC1 is hard-wired to the incrementer,
the incrementer is hard-wired to the address bus,
and the address bus is muxed between PC2 or MAR?
Chuck Moore seems to like that arrangement ...
because it is obviously simpler.)


  .
  . +-<---[increment]-------<-+
  . |                         |
  . +->->[PCR1]->[PCR2]->|\   |
  .                      | >->+----> RAM address
  .         ...->[MAR ]->|/
  .                       |
  .                      LSB


Things it lacks that I wish it had:
* it's difficult to lookup A = B[C], because there are are no indexed loads.
* it's difficult to lookup A[B] = C, because there are no indexed stores.
Those 2 things can be done if we "cheat" and write self-modifying code ... which this architecture makes fairly easy to do.

* Subroutine calls look unncessarily difficult.


* One solution to the "backdriving" problem:
use lots of diodes -- perhaps LEDs. If every input to a block of logic goes through a diode, then it's impossible for that block to "backdrive" current through that diode.
Since relays pull ~40 mA, pick LEDs that can handle 40 mA ... or pair up cheaper 20 mA LEDs.
Since some (typical?) LEDs can block max 5V reverse,
(a) use 5V relays and also (b) make sure we put flyback diodes (the same kind of LED is fine) on every coil.

Say we go even futher and try to build "diode-relay logic" -- would that save a significant number of relays?
DAV: diode-relay logic could be something like this:
every block of logic has a SPDT or 4PDT relay near the output.
The "common" of the switch connected to +24V.
The other 2 lines (the NO and the NC terminals) of the switch are the 2 outputs, the signal and its negation.
Many functions can be built using just that one SPDT relay and a bunch of input diodes ORed together to the coil, where each diode is connected to some signal, or to the negation of that signal -- that gives us OR and NOR outputs, and arbitrary inverts on each input -- so it can implement AND and NAND also. 2 layers of such logic give any possible Boolean function on the inputs.
For example, 3-in XOR requires 5 SPDT relays.
Is there a better way to build "diode-relay logic"?

Probably, since all possible 3-input logic gates (including 3-in XOR) can be built using only 3 relays and no diodes:
Each input connects to its respective coil (the other end of the coils connect to ground), so there is no backdriving problem.
The first relay is 4PDT.
Its 8 inputs (NC and NO terminals) arbitrarily connected to either nothing or +24V in order to select which particular 3-input logic gate we are implementing today.
The second relay is 2PDT.
The 2 common outputs of the 2PDT relay feed into the 2 inputs (NC and NO) of the third (final) SPDT relay.
The common output of the final SPDT relay is the output signal.
(Alas, it only generates the signal, and not also its complement).
(yeah, a lot of words; a schematic would be better).


Consider:
eliminating the 16 bit MAR register,
and adding 8 bits to the A, B, and C registers
(for a net addition of 8 bits).
Then you have a "pure" 16 bit machine (more or less).
Make "load" always use the C as the address register, while "store" always uses A as the address register.
Because *before* we do a calculation, C is usually free (it will be overwritten by the result of the calculation) -- but *after* we do the calculation, C holds the result we usually want to store, and so we can save 1 instruction in the program by using something other than C for the temporary address register.

I'm hoping that losing MAB will be compensated for by making indexed addressing easier -- in particular, pointer dereferencing and array dereferencing and simple memory copies.
(Such addressing uses load and store, but suppresses the load of C and instead uses the address already in C).


-----

[consider building]
DAV:
as warm-up for building a relay computer,
consider building a relay clock.

Perhaps
use the 60 Hz line frequency as input.
Does toggling the relay at 60 Hz wear it out too quickly?
... Perhaps, an LCR + relay oscillator running at 1 or 2 Hz would last much longer ... perhaps with a bit of input from the 60 Hz line frequency to phase-lock it.

...
If we have a ring oscillator of relays, with (say) 12 relays tuned to give (say) 5 Hz for the rest of the clock --
with a small amount of 60 Hz line frequency to phase-lock --
does that merely postpone wearout by a factor of 12?

----

[relay computers]
http://www.juliantrubin.com/bigten/zusecomputer.html



DAV: Does it make sense to write software to semi-automatically "optimize" a relay computer design?
... peephole optimizations: 2 relays driven by one signal can sometimes be combined into one relay ... Generating A and /A can be done in several ways ... wired-or can *sometimes* be done -- a computer program can automatically test and see if those conditions are met ... 4 independent copies of A can be generated in a 4PST relay -- this may require fewer relays than a single copy of A that is carefully buffered in many places ...

global optimizations: given a single global clock signal, what is the maximum number of states that a set of n relays can step through before repeating a state? Can that be used to generate a state counter or program counter that uses fewer relays than the "classic" designs?
(This is similar to the "busy beaver" problem).

----

[relay computer]
2008-12-21:DAV:

What if we
(a) store all bits in ICs (say, a MMC card, a Ramtron FRAM, and a bunch of shift registers), but
(b) did everything else (ALU ops, IR latch control signal decoding, etc.) with relays?

Well, clearly we must have some sort of IC-to-relay and some sort of relay-to-IC interface.

Relay-to-IC is pretty simple: either use 5 V supplies for both, or else use a resistor divider / diode clipping to convert 12 V or 24 V relay output to 5V or 3.3 V IC input.
The tricky bit is relay bounce, and that is irrelevant for everything except the clock input. Perhaps somehow use 2 wire clock (which is immune to relay bounce) and somehow convert to a clean 1 wire clock for the ICs.

IC-to-relay is a bit trickier.
Traditional approach is to use a transistor per IC output.

What about, in particular, the
$2.41 TPIC6595 8-Bit Shift Register?

It has one special output:
SER OUT seems to be rated at only 0.020 A (but both source and drain), and restricted to slightly beyond 0 to 5.0 V.
So a minimum resistance of R=V/I = 5 V / 0.020 A = 250 Ohms.

Eight Power DMOS Transistor Outputs of
0.25 A Continuous Current -- at 24 V, that implies an output load of a minimum of R=V/I = 24 V / 0.25 A = 96 Ohms (minimum) -- so plenty powerful enough to drive a 480 Ohm 24 V coil. (I think the inductance of the coil is irrelevant to this IC, as long as the coil has a proper flyback diode).
1.5 A Pulsed Current Per Output (for up to 1 ms at 10% duty cycle)
(open drain -- this constrains me to using "open" and "GND" to represent 1 and 0 or 0 and 1.
);
when "open", it tolerates drain-source voltage up to 45 V (so apparently it could directly drive 24 V relays ... if the other side of the coil is connected to +24 V).

One special power input:
Logic supply voltage: must be about 5.0 V.

5 signal inputs:
0.85 Vcc or above for 1,
0.15 Vcc or below for 0.

----

forth on relay computer?

----

Put 1 LED at each coil for easier visibility?


----



DAV:
I keep thinking in terms of "registers" ...
but to minimize the number of relays, I think I'm going to have to minimize the number of registers.
And yet ... I want some sort of indexed load and indexed store,
which makes programming much simpler (stacks, arrays, etc.).
So I think we have only 3 choices:
* keep the index (and the PC) in special registers
* keep the index (and the PC) in the same main memory (serial FRAM?) as everything else
* keep the index in some other memory other than the main memory.

If we keep our "no registers in the relays, all data stored in the serial FRAM (perhaps in the FRAM address register)" concept,
then perhaps our minimum cycle time is:

indexed store:
* clock "load" opcode out of program memory into instruction register IR
* clock immediate address of the index out of program memory into address register
* clock address from the address register into data memory
* clock data into data memory

indexed load:
* clock "load" opcode out of program memory
* clock immediate address of the index out of program memory into address register
* clock address from the address register into data memory
* clock data from data memory

[relay computer]
"How to pick a relay"
http://www.leachintl2.com/english/english2/vol6/properties/how4.htm
"There is no relay contact that can be used for switching all load levels.
Each load level requires tailoring of the contacts for that specific application.
Contacts rated as capable of handling "dry circuit to 2A" loads will do so.
They cannot, however, handle loads that go from 2A to dry circuit levels.
Knowing this might have prevented one misapplication that luckily had only embarrassing consequences."

[relay computer]
Relay General Application Guidelines
http://www.tai-shing.com.tw/technical/relay.htm



[build a relay computer]
While using SPNO relays (single-pole, single-throw, normally open relays)
may be the smallest and cheapest way to store
register bits ...
SPNO relays are not "universal".
Perhaps it would be interesting to use
DPDT or 4PDT registers to store register bits.
(a) Using a single kind of relay for everything requires using a universal relay.
(b) Using a relay with more than 1 pole gives me a *separate* input and output for a register,
so I can directly hook the output to a data bus
without worrying about "backfeeding" signals flipping bits in the register.

----