Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Larix]

Links for further documentation:
Data Sheet and code reference

Control Logic

Program Listings

Usage advice for the savefile

Map

Savefile (0.34.11)

Excessively large write-up on much of the theory and praxis behind the thing

I'd messed around with minecart logic for quite a while and when i worked out ways to make an adressable memory cell and mass data storage with them, i decided to try building a computer. In the early conceptual stages i decided i was not going to untangle program and data coming from a shared bus and completely separated program and data storage. Since my mass storage concept looked like a good model for expanded program storage, the instruction length worked off the three bits encoded per cart in the mass storage. Thus, the computer uses six-bit instructions, a three-bit operator and a three-bit operand. It operates on ten-bit data: since program and data storage are separate, there's no need whatsoever to use the same or even related register sizes.

In spite of the tiny instruction set, the computer can access output (the line above is the result of a "print to screen" program) and do basic mathematical operations, albeit impressively slowly: addition is trivial, since it's one of the actual instructions, but the computer can also subtract (by constructing the binary complement first), multiply, divide, calculate a Fibonacci sequence (limited by the ten bits, of course) or...

calculate square roots:



The bottom line contains the actual number, the top line the square root. (sqrt of 840 is 28).

Spoiler: program (click to show/hide)

I'm more than a little proud of this one. The program grabs a number from a "tape" loaded with an arbitrary sequence of ten-bit numbers (specifically intended for such "pick any number" programs, not requiring direct user input) and the only assumption it takes is that the number it's working with is different from 1. After i the "operate" switch was pulled, all operation took place automatically, without any intervention by me. The square root is calculated in what i guess is the usual way: by dividing the "to-root" number by the current guess and deriving an approximation from the result.

code:
#Registers A-C are main data registers, D is the first counter; Bf is buffer, used for data transfer between registers, from/to output, from the data tape

Module 5 (first of square root program)

111 010 read datum from tape to Bf
001 011 write Bf to register C
111 111 toggle I/O status bit (normally "keyboard/display", toggles to "machinery/latch array")
111 001 write Bf to output (latch array controlling linked machines)
111 000 read input to Bf (latch array); this returns data shifted one position to the right: this pair of commands performs "shift Bf right", while the MSB is _not_ used as "sign" but always set to zero.
001 001 write Bf to register A
000 000 read zero to Bf  #the operands 000 and 111, when used with the "read" operation, either clear or set all bits in the buffer. Makes some operations a lot easier, since you don't have to dedicate one of your precious registers just to store a zero.
110 101 load module 6

Module 6
001 010 write Bf to Reg. B
001 100 write Bf to Reg. D #"primes" the machine. B stores the running sum during division, D stores the Quotient. Both must be re-set to zero after every pass. Zeroing both before running the first division means there's no need to prepare the registers before starting the program.
#Beginning of division loop
010 000 add A+B -> write result to B
100 000 test if B>C; if no, skip next instruction
110 110 load Module 7
011 100 increment reg.D (test for zero)
101 010 jump to pos. 3 (if not zero)
111 110 halt #safety catch, for zero, one, and for excessively large numbers: above 681 as original number, dividing by 1/2 itself will wrap around past 1024 on the first try; past 1005 or so, no running sum larger than the original number will occur before 64 iterations. In the case of zero and one, the first guess for the divisor is zero, and no matter how many zeroes you take, they won't ever be absolutely bigger than any number. If the counter wraps around, the program will simply stop there, displaying the original guess as "result", which is only correct in the case of zero.

Module 7
#we reach this module after we've divided the source number by our current guess. Now we need to check if our result is sufficient, approximate if not
000 100 - read D to Bf #fetch the division result
001 010 - write Bf to B
100 011 - test if A>B, skip next if not # since we start out with a guess assuredly bigger than the result if source >4, we have the correct guess if A is _not_ bigger than B (unless i'm overlooking some cases).
101 101 - jump to position 6 #not the result yet, we need to refine and retry
111 110 - Halt # reached if A>B fails. Square root stands in register A. I could have made it cleaner by also copying A to B to remove the unsightly division result from display.
010 000 - add A+B, result in reg. B
000 010 - read reg. B to Bf
110 111 - load Module 8

Module 8
# we have the sum of our guess and division result of source/guess in the buffer. Now we need to divide it by two. Good thing i wired the "control" output latches to work as right-shift for Bf!
111 001 - write Bf to output
111 000 - read input to Bf #Bf's contents got divided by two. Easy!
001 001 - write Bf to reg. A #that's our new guess
000 000 - clear all bits in Bf #load a fresh zero so we can reset registers B and D.
110 101 - load Module 6 #next round of division
unused
unused
unused

I made notes of the program's progress, writing down dates when a division and approximation was finished. I had deliberately put a pretty large number at the tape position for this run, to check if the initial overflow was handled properly and led to the correct sequence once this initial trouble was over. It worked splendidly:

first division: 840:420 = 6 (overflow, stopped after the third wraparound)
first approximation: 420+6=426, /2 = 213
all further divisions correct (giving the nearest lower integer), approximations, as predicted:
108
57
35
29
28
840/29=28, thus A>B; 840/28=30, A!>B, program finished, result is 28.

The program was started on 24 Moonstone 268 and finished 12 Malachite 269 - six months and 17 days, 185 days total. Barring accounting errors, those were 567 program steps, at a rate just over three operations per day, 392 steps per operation, 35,47 microurist clock rate by dwarven time, ~ 50 millihertz realtime.

A map has been uploaded: http://mkv25.net/dfma/map-12378-faintedposts

Bits and pieces

User interface



The place to interact with the machine. From here, you can enter program code, set the data registers, set the status bits, connect/cut main power, reset the computer, directly load the first program module from the ROM into active program storage, keep track of the main registers' contents and of the four status bits, shut down the main registers...

and of course start the computer.

It's riddled with more or less helpful notes; i wouldn't find my own way around it otherwise.

Memory cells

I use three different types of read-/writeable memory cells. I could have done with only two types, but kept the powered-cell register in the end, as an hommage to the pioneers of minecart computing. While it takes a lot of mechanisms and is power-dependent, it's fast, reliable and probably quite intuitive for people more into pure mechanical logic.

1. Linear read/write latch



Data register A, containing 0000 011 100 (28). These are ten memory cells, built horizontally, with "double-action" read, write-adressable.

Spoiler (click to show/hide)

Diagram:

Code: [Select]

#══▼▼═▼▼═▼▼═▼▼══#
z+0, paths

#▲^¢▼^▼¢D¢▼B▼¢^▲#
  1r d ces h r0
z+0, constructions

  #══#══#══#══#
z-1, paths

  #▲▲#▲▲#▲▲#▲▲#
z-1, ramps :P
legend:
1 - pressure plate active when cell is "on" and is currently read
0 - "off" pressure plate active when cell is read
/* both "on" and "off" signals are sent, which make data exchange between registers easier - we can extract a direct "clear" signal from a cell in zero state instead of trying to draw conclusions from absence of an "on" */
r - hatch covers that open when a read of the cell is requested

d - pressure plate sending a signal to the UI display when the cell is on /* we want the status of registers constantly displayed */

c - write hatch, clears the cell if enabled
s - write hatch, sets cell if enabled
e - door, enables writes, makes the cell adressable

h - raising bridge, lowered. This is a special contraption, combined with a (currently and normally) retracted bridge over the adjacent pit to the left, allowing to "h"alt the whole register. It can stop all minecarts in the register, to allow refurbishing, exchanging carts, demolishing the register or the like. Bridges are latched into "neutral" or "shutdown" position by a single lever in the UI area (has to go through a logic circuit since we need one bridge in "active" and one in "inactive" state).

Not-so-obvious issue: carts passing over a hatch cover don't come from track and will not automatically enter downward ramps they encounter. They will instead jump, staying on the upper z-level until they accumulated enough "downward distance". Ramp-propelled carts in this circuit are slow enough that they'll only jump three tiles, i.e. they fall into the appropriate pit just by themselves. I carefully tested the functionality of the design before installing the full 88 of them.

Most memory cells i built here used this design.

2. Settable flipflop with optional carry generation



Three cells of the first counting register (register D).

Interlinks between individual cells allow the register to count up or down and cells can easily be written to. Reading its state is more complicated, it has to be done through a separate evaluation circuit.

I'm afraid the construction is a bit too complicated to convey it here. The core is a three-ramp pit with a single hatch cover over the "corner" tile:

Spoiler (click to show/hide)

Trying to explain that core mechanism:

Code: [Select]

.#        #
 ▲        ║
#▲▲#     #╣═#
 #        #
z-1

 ║
 ▼
═¢▼═
 ║
z+0

When the cart moves E->W or N->S, it passes through the pit in a straight line, emerges to the west/south and continues on its path there. When the hatch cover is shut, the cart bumps into it, accelerates to the north and emerges to the north. This holds true both for carts coming from the north and from the east. (Carts coming from the west or south will jump off the hatch and misfunction.)

The important point is that by putting such a pit into a circuit which "re-cycles" straight E->W passages (and N->N returns) and lets N->S passes leave, it's possible to build an edge detector using a single signal-operated building: a cart enters the circuit on the E->W line, keeps circulating through, always passing E->W until the hatch cover closes, keeps bouncing off the hatch (and returning) while it's shut, then passes through to the south once the hatch opens again.

The practical application here consists of leashing two of these "edge detectors" together, making a very simple toggle cell. Further regulation of the switchover paths between the halves of the cell allows extracting "carry" signals that can be passed on to the next cell. In addition, if only one of the main hatches in a cell is opened, the cell gets set - the cart can only switch position if it's currently in the cell half that had its hatch opened.

3. Powered latch



Six bits of memory using Tinypirate's variant of the powered minecart memory cell (first published in Bloodbeard's minecart computation thread).

Spoiler (click to show/hide)

The function is explained on the wiki. I keep getting confused linking up mechanisms, so didn't intend to use this model extensively. I had first speculated about including some extra functionality, that's why each cell has six tiles of floor instead of the entirely sufficient four. My idea was making all cells toggleable, but i couldn't see a good use for just inverting the value so left it out in the end. Input is sent by _disabling_ the gear assemblies of undesired states and connecting main power to the whole contraption. Since the detailed input arrives only after main power turns on, carts bounce around in the circuit quite a bit on every write, but reliably settle into the correct state. Output must be generated through an external circuit.

The ten-bit register draws 265 power before input has established, not at all trivial when the entire computer draws 1380 in standby and rarely over 1650 in operation.

Signal bundling

Every main register bank has ten enabling doors and twenty read hatches. There are several operations which write to or read from a register. To avoid having to link all those buildings up to each function, i collected them to a bank of "control" circuits. This way, "write to register A" can be done by establishing a single link to that control circuit. As a simple case of expedience, i also collected the "write to program memory" commands like this: while i could have gotten away with a single "clear all program memory" function, that would have meant linking 48 doors and hatch covers to a single plate. That could easily have taken over half a year to do. In the interest of my own sanity, i collected the functions through eight "clear" and eight "write" controllers.

The obvious downside to such indirect operation is that it introduces reaction delay: a signal sent directly to the targetted building switches the building instantly, a signal sent via control circuit only arrives once the control circuit has responded. It will also only turn off after the control circuit's plate has recovered.

Spoiler: why not keep it simple (click to show/hide)

The simplest "signal relayer" based on powerless minecarts:

Code: [Select]

#▲▲#   #══#
z-1    track

##¢^▲#   ##▼══#
z+0         track

has two problems:
- reaction time is irregular, because in the "off" state (hatch closed), the cart can end up either sitting on top of the hatch or captured in the pit under the hatch. Falling off the hatch, bouncing into the backward wall and climbing out forward gives a delay of 26 steps until the plate gets activated, if the cart was in the pit, the delay can be any number of steps from 2-19 (equal chances of each).
- the output signal is lengthened: the cart will bounce into and out of the pit, passing over the plate regularly, as long as the hatch is open. That means the plate's active state keeps getting refreshed for ~100 steps, and will only turn off around about 100 steps after the hatch closes - the exact number is naturally variable, ranging from 85 to 115 steps. An ordinary on/off pressure plate cycle, which has a spacing of 101-105 steps, will thus result in a relayed "on" that lasts roughly from (2-25) to (190-220), much longer and less distinct. Not a good premise when looking for fast operation.

The remote circuit i settled for introduces a delay, but that delay is absolutely constant and signal length does not expand.



Write control.

All writing to active memory, clearing the buffer or program memory and reading from the buffer and registers A-C is done through such indirect devices.

Program instructions have their "read" commands triggered directly: each only gets activated in one case (when the instruction is needed for execution), affording no benefit from collected operation, _and_ since each possible operation has to pass this step, unnecessary delays here hurt the overall performance of the computer.

Spoiler (click to show/hide)

Code: [Select]


##    ##     
#▲    #║     ##    ##
#▲    #║    ╔¢#   ╔▼
##    ##    ║^    ║║
▲#    ║#    ▼╗    ▼╗
▲#    ╚#    ¢▲#   ▼║#
z-1   track  #     #
            z+0    track

The hatch cover to the north is linked to the input, both hatch covers and the output are linked to the pressure plate in the circuit. When the hatch opens, the cart falls into the pit, climbs out of it after 25 steps (activates the plate after 26) and heads south. It bumps into the impulse ramp to the south and gets sent into the southern pit by the corner. Since the hatch is opened by the passage over the pressure plate, the cart now cycles through the pit/impulse ramp/corner circle to the south, until the hatch cover closes again. At this point, the cart will emerge straight to the north, travels north along the track and settles on the northern hatch; since it's been cycled by the internal plate, it's guaranteed to be reset and closed again. Since the cart only passes over the plate once, the signal sent consists of a single "on" pulse after 26 steps, followed by an "off" after 126.

NB: for operation of bridges, floodgates and grates, the circuit must be one tile longer and the pressure plate put another tile away from the ramp. The circuit shown here will toggle such buildings, because the "off" signal comes before the building has reacted and is ready to take new input.

Caveat: the circuit is not very tolerant for architecture variants - if the incoming cart has the wrong momentum, the stable cycle in the southern end cannot establish itself.

Mass Storage

By far most of the program code in this computer is stored in a type of ROM: 128 words of code in the bank, while only eight at a time are actually loaded. New code can be loaded into active memory (overwriting the previous contents) by the "load Module" instruction, and an additional status bit can switch between two banks of eight modules each. The actual program store is spacious but fairly unassuming (spoilered for size):

Spoiler (click to show/hide)

It's still fairly compact considering that it can store 768 bits on 75x36x2 tiles. just over 7 tiles per bit. Even more impressively, it does this with less than 500 mechanisms (including the entire adressing and output management). The secret is that information in the mass storage is encoded in minecarts of specified weights that are simply held in readiness in small ramped pits until their data is requested. Then they get released by opening an "output" bridge, weighed by four pressure plates which directly send set signals to the pre-cleared program latches and cycled around and back into their pit through an "input" bridge that's held open until all carts are safely returned; the output bridge closes again ~ 100 steps after it opened, quite a long time before carts have finished their round.

A pair of holding pits looks like this:

Code: [Select]

#####    #####    .B.B.
#═╚═#    #▲▲▲#    ═B.B═
#═╔═#    #▲▲▲#    ═B.B═
#####    #####    .I.O.
z-1, track  z-1     z+0

B - bridge
I - incoming
O - outgoing

enough to hold two minecarts, worth six bits or one program word. The impulse ramps in the pits linked to the walls prevent carts from bouncing back out of the pit after entering (from the west) - they can only leave the pit when the eastern "output" bridge opens.

Minecarts of seven weights (and no minecart as "zero" datum) are used to encode three bits of information per cart; sixteen carts (potentially fewer depending on presence of "000" code segments or unused words) make up a module of eight words, sixteen modules can be stored.

The principle of this mass storage is remarkably simple. It allowed me to build a computer with an extremely small active program memory without crippling computational capacity: longer programs are simply spread over multiple modules and loaded in succession.

Higher information density per cart is possible, and a denser packing of the module, too, but either would increase complication:

Spoiler (click to show/hide)

four bits per cart already require using loaded carts to represent some of the states, and it gets exponentially worse when trying to encode more than that. Six bits per cart are theoretically possible, but just accurately reading those values would be an insane effort.
denser packing could be done by positioning the stored carts on top of rollers instead of in ramp-pits: it'd require a lot of power and mechanisms and would be prone to misfunctions when carts jostle each other. Alternatively, carts could be "stacked" and pulled out sequentially, e.g. by a roller. Adressing individual data chunks could only reasonably be done when storing only one segment per stack, sacrificing much of the compactness, and cycling read data back into the stack could be slowed down tremendously (or completely broken) by "stack cluttering".

For added convenience, the module loaded in the first position can be transferred to the program memory by operating a dedicated lever in the control centre. The two-wide bridges over the return tracks can be raised to stop currently circling minecarts - this way, a program module can be unloaded.

"Programming" the ROM is a pretty slow and inelegant process: a cart must be deposited on a pressure plate operating the input bridges of the desired module and the correct-material minecarts assigned to sixteen routes (consisting of a single stop on the western end of the long straight path, with a "push east immediately" order). Entering one module of program code in this way takes two to three weeks.

Mechanical logic devices

1. Adder (not the animal)



The main tool for calculations, this machine adds two ten-bit numbers together. The correct sum rollers are instantly connected to power the moment the inputs are fully established. Reading the result and transferring it to the target register is done by roller-directed minecarts; since i insisted on the compactest possible layout for the adder itself (two lines per bit), logistics are a bit tricky.

The read-out procedure must be started with a notable delay, because inputs come from linear latches and have a "startup" latency of up to 35 steps.

Spoiler (click to show/hide)

I cannot take credit for the design, it was developed by Jong, apparently inspired by the "Pre-Triggered Mechanical Logic" discussion of yore and shown in this post. Unfortunately, imageshack since decided the design was too awesome for posterity and swallowed the pictures. The optimised circuit can still be found on the very last page of the design manuscript of Jong's dwarven computer.

I think i started with the not-fully optimised two-stage adder and the concept of the "inverse carry" calculation chain. Putting it together and optimising from there got the exact same final circuit:

Code: [Select]


PABoQSqobaP
   X   X


P = power supply
a, A = gear linked to engage when input A1 is false (a) or true (A)
b, B = gear linked to engage when input B1 is false (b) or true (B)
X = gears linked to both inputs A1 and B1, pre-toggled; engaged when both inputs are different, disengaged when they're equal
o = unlinked gears or rollers. They receive and pass power when their inputs are switched correctly.
Q, q = gears linked to both inputs A2 and B2, calculating the sum based on whether or not the last bit (bit 1) produced a carry. Q is engaged when A2 and B2 are equal (carry-in active and inputs equal => sum is true), q is engaged when they're inequal (carry-in off and inputs different => sum is true).

What it does is instantly calculate all carries on the left side of the machinery and all "non-carries" on the right side. Each bit either has a carry or not, so exactly one of each summation (q) gears is offered power on every bit. Since these gears are also in opposite configuration, no erroneous power connections can be established if everything's wired correctly. Over 100 correct additions during the square root calculation provided the practical proof of the adder.

Handing the instantly-accurate addition result over to the target register is a bit trickier: with the register design in use, the fastest read process requires not only "set" signals for every bit that has a sum, but also "clear" signals for every bit that doesn't. Achieving that with minecarts means an already-moving cart must be re-pathed by a roller activated when sum is on or stays on the given course when sum is off and the roller unpowered. It must then pass over one of two pressure plates that mustn't be touched during the process of setting the cart in motion towards the sum roller. I insisted on building the adder as compact as possible - two lines per bit - thus pathing of the carts had to change z-level so it could be dropped back onto the startup roller. The impulse ramp used to provide speed for getting the carts to the upper level proved problematic: the further acceleration could sometimes increase cart speed into derail territory. I eventually replaced the initial standard (highest-speed) result rollers with high-speed ones.

Another issue was correct timing of the sum-read process: input signals are sent from linear minecart latches, which have a read-signal latency of 2-32 steps; in addition, they are not read directly but rather through the remote triggers above, adding another 26 steps delay, for a total of 28-58. Instantly sending the reading carts would usually give zero as result. Since the inputs last for a fairly long time (about 200 steps), i could simply implement a 100-step delay before reading the result, which also allowed choosing between the two target registers by a simple bridge switch: the lowest-bit cart goes over such a fork on its read cycle.

2. The comparator



Compares two inputs, passes power (switching the path of a "measuring" minecart on the NE loop) when the tested-for condition is true.

Spoiler (click to show/hide)

The inputs compared are ten bits wide. The logic is quite simple:

Testing for A>B

Code: [Select]


2QAb║ 1
3QAb║ 2
4QAb║ 3
.PAb║ 4


A = gear engaged when input A is true at the bit number to the right
b = gear sengaged when input B is false at the bit number to the right
Q = gear engaged when A=B at the bit number to the left
║ = NS roller (accepts power from the left/right)

The circuit keeps checking if A=B; as soon as that condition fails, it checks whether A>B at that position. Only if this is the case, power is passed to the output. Lower bits are not checked, power progression invariably breaks at the first inequality. Putting the gears of successive bits in direct contact with each other doesn't hurt the functionality.

Reading the result is done with a hundred-step delay again (inputs from indirectly read linear latches, thus wait time until correct value of up to 58 steps). A variety of comparisons can be made, and many require inverting all gears in the assembly (in the schematic above, B>A can be tested if all A- and b-gears are inverted); consequently, a single "simple relayer" was built - it inverts the necessary gears and holds them inverted for about 200 steps, enough for the evaluation to be always correct.

[Larix]

Features of the Minecart computer:

Instruction size: six bit
Data register width: ten bit, unsigned

No unified clock, proper timing is ensured by various delay circuits. Average time per instruction about 400 game steps. Advancement through a largely self-regulated eight-slot ringcounter run by a single minecart.

Active program memory: eight words of six bit each, powerless minecart latches.

Data registers:

Buffer - for data exchange between registers, input/output. Ten bit, powerless minecart latches.
A, B, C: the three main operation registers. Ten bit, powerless minecart latches
D, E: two counter registers. Six bit, Toggle- and settable powerless "flipflops". Four bits of expansion allow them to be used for storage when not in use as counters.
F: pure storage register. Ten bit, powered memory cells, using the design by Bloodbeard/TinyPirate

Further data storage:
1. The Compact Readonly Adressable Minecart Program Store (short CRAMPS): sixteen modules, each containing sixteen minecarts, each of one of eight possible weights, encoding three bits per cart. Each module contains enough code to fill the active program memory. Each single module can be selected and loaded into program store by dedicated program instructions, greatly extending the possible program length: sixteen modules of eight words each mean the total capacity of the CRAMPS amounts to 128 words of program storage.

Currently, one access and three actual function programs as well as two "bonus" single-module programs are loaded into it, taking up all sixteen modules and encoding 123 program words, i.e 738 bits of information, using 214 minecarts.

The eight information-encoding minecart weights are:
000 - platinum minecart (only required in the top lane) or no cart at all - the latter could be used 32 times.
001 - wood of any type
010 - iron or brass
011 - tin, zinc or pewter
100 - electrum or gold
101 - lead
110 - copper or nickel
111 - silver

The system uses powerless carts, kept in motion by ramp glitches and directed by retracting/extending bridges. Three pairs of bridges are required for every module, the decoding plates for every "line" are shared between all sixteen modules, so the total number of mechanisms used to construct the program storage is smaller than the number of bits it can hold.

2. Additional data are stored in a kind of single-use tape, the Sequential High-density Read-Only-Once Memory (SHROOM). It uses the same basic concept as the CRAMPS, but can only read the datum at the "head" of the tape, other data cannot be accessed. The tape simply advances all later data to the next position automatically when the head datum is read. This process is achieved through ordinary bridges, the process takes a bit over 100 steps per position in the tape to finish. The tape as built holds sixteen ten-bit data; "used" data can be cycled around to the end of the tape if tape read accesses are sufficiently far apart (~1600 steps, four instructions), otherwise they must be "dumped". The tape is one-directional and read-only.
Data from the SHROOM are stored in the buffer, for later use as data to operate on. Sixteen ten-bit data give it a capacity of 160 bits.

Status register: four bits are held by dedicated circuits. They control whether or not jumps can take place, where write operations go to, which I/O devices are accessed and which half of the CRAMPS program modules are loaded from. The status bits can be set by hand or changed by program instructions.

The complete data capacity of the computer amounts to 6x8bits program store, 5x10 and 2x6 bits in data/counter registers, 4 status bits - 114 bits of writeable memory; 768 (CRAMPS) + 160 (SHROOM) bits in ROM storage, 1042 bit in total. It's an actual kilobit computer (even using the binary 2^10 convention).

The added "program tape" currently has a capacity of a further 24 modules (1152 bit). Those are implemented as SHROOM-type single-use sequential tape and no program is loaded at time of writing. In an infinite-size infinite-ressources embark, the tape would be unbounded.

Instructions

The instruction set is what allows doing quite a bit of basic computing with six-bit words. While the first and second three-bit parts of each instruction are decoded separately, it's not a simple operation+adress system. Operands often encode a notable variety of operations.

It's quite long, so i'll put it behind a

Spoiler (click to show/hide)

1. 000 - load buffer
Writes some data into the buffer. This allows reading from the various data registers, but the special instructions 000 000 and 000 111 don't load from an adress, they clear resp. set all bits in the buffer.
000 000 - load zero
000 001 - load from register A
000 010 - load from register B
000 011 - load from register C
000 100 - load from register D
000 101 - load from register E
000 110 - load from register F
000 111 - load 1111 111 111

Since the counters (registers D and E) are only six bits wide, only the six lowest bits of the buffer are written to, the four highest bits are invariably set to zero.

2. 001 - store buffer
writes the contents of the buffer to an adress. The "write target" status bit can switch the destination adress between the various data registers and the program registers. A program can actually, although only in a very rudimentary fashion, "reprogram" itself.

write-to status bit 0:
001 000 - NOP (could be interpreted as writing to the buffer itself)
001 001 - store in A
001 010 - store in B
001 011 - store in C
001 100 - store in D
001 101 - store in E
001 110 - store in F
001 111 - store in the "status register". This was partially wired wrong, so a 1 stored in the I/O, write-to or module bank bits will actually set the bits to zero and vice versa.

write-to bit 1
001 000 - write to program word 1
001 001 - write to program word 2
...
001 111 - write to program word 8

The six lowest bits of the buffer are written to six-bit adresses; the four lowest bits to the status register (I/O choice, write-to, module bank and jump inhibitor, from highest to lowest).

3. 010 - adder
uses an instant-result adder (Jong's design) taking input from a choice of registers A, B and C. The buffer is not involved in this at all (the buffer is _not_ an "accumulator", more of a bus). The three bits are actually decoded as: first bit - get input from register A if on, from B if off; second bit - get input from register C if on, from A if off; third bit - store result in register C if on, in B if off. Thus, they result in:
010 000 - adds A+B, stores result in B
010 001 - adds A+B, stores result in C
010 010 - adds B+C, stores result in B
010 011 - adds B+C, stores result in C
010 100 - adds A+(nothing), stores result in B (directly copies A to B)
010 101 - adds A+(nothing), stores result in C (directly copies A to C)
010 110 - bitwise A XOR C, result stored in B
010 111 - bitwise A XOR C, result stored in C

4. 011 - counter operations
Whenever it fires, the counter increments or decrements the number stored in the addressed counter register and also checks the pre-increment value to determine whether the post-increment value is zero (when checking for zero) or even (when checking for parity). If the test succeeds, the "jump inhibitor" status bit is set, when the test fails, that status bit is cleared.
first bit: check for zero if on, parity if off
second bit: operate on counter register E if on, D if off
third bit: decrement if on, increment if off
011 000 - increment D, parity check
011 001 - decrement D, parity check
011 010 - increment E, parity check
011 011 - decrement E, parity check
011 100 - increment D, zero check
011 101 - decrement D, zero check
011 100 - increment E, zero check
011 101 - decrement E, zero check

5. 100 - comparator
A fairly simple gear array that takes two inputs and compares them by size. If the "tested-for" input is larger, the array passes power, if it's smaller or equal, it passes no power. Based on this power status, a binary decision is made: if the test fails (tested-for number is _not_ bigger than the alternative), the next instruction is skipped. This is one of two conditional program flow operations in the instruction set.
Input is taken from the data registers A, B and C.
100 000 - test if B>C
100 001 - test if C>B
100 010 - test if B>A
100 011 - test if A>B
100 100 - test if C>0
100 101 - test if B>0
100 110 - test if A>0
100 111 - test if A and C are inequal

6. 101 - conditional jump
101 000 - jump to program position 1
101 001 - jump to program position 2
...
101 111 - jump to program position 8
directly sends the program counting minecart to the desired position if the "jump inhibitor" status bit is not set.

7. 110 - load module from CRAMPS
One of sixteen modules is requested, cycled through the reading array and its data replaces the values previously stored in the program memory.
Which module is read is determined by the value of the Memory Bank status bit and the three-bit operand.
Status bit: 0
110 000 - load module 1
110 001 - load module 2
...
status bit: 1
...
110 111 - load module 16

8. 111 - various
interacts with input, output, the SHROOM and the status bits. Also contains the HALT instruction.
111 000 - reads input.
111 001 - writes to output
111 010 - load datum from the SHROOM into the buffer
111 011 - expansion, not yet installed: load program module from SHROOM-like tape
111 100 - toggle Module bank status bit
111 101 - toggle write-to status bit
111 110 - HALT
111 111 - toggle I/O status bit

if I/O bit is zero, 111 000 loads value entered to a dedicated lever array ("keyboard") into the buffer. If the bit is one, it loads the values of bits 1-9 of the "control latch", effectively the contained value right-shifted without preserving the MSB.
if I/O bit is zero, 111 001 outputs the contents of program words 3-8 to a 35-hatch cover (5x7) display.
if it's one, contents of the buffer are copied to the "control latch", potentially activating two simple machines - a water cannon and a repeating spike.

List of components, based on "installed" numbers in the stocks screen:
mechanisms: 6400
hatch covers: 540
bridges: 270
doors: 150-200 (250ish installed, but that includes bedroom doors)
grates: 26
floodgates: 3

waterwheels: 25. 20 would probably suffice, but i never bothered to look at power load in detail.
rollers: 233 (number of "installed" ropes)
~260 logs for axles

~360 minecarts

DF version: 0.34.11

Time consumed: 15 fort years. Over half a year (with long interruptions) real time.
INVADERS:NO
TEMPERATURE:NO - primarily to avoid trouble with the winter freeze, but it also helped quite a bit with FPS.

Otherwise, a normal fort with normal dwarfs - dwarf speed, food/drink/sleep requirements unchanged. 154 beards currently, fort rules a duchy but hasn't bothered to invite the bog standard monarch.

FPS in "standby" between 30 and 45. Operating the computer lowers FPS notably, to about 20 in low-intensity operations like jumps, single digits down to 4 when reading/writing data, especially when loading modules. FPS is drained almost entirely by opening and closing buildings, minecart pathing doesn't seem to matter much.

[Di]

By Armoks beard...
I'm afraid the forum doesn't have enough dwarven science medals to award you accordingly.

[AbanShakehandles]

I understand this about as well as Urist McRecruit understands his equipment orders,
but all the same, I applaud the hell out your accomplishments.

[wierd]

Glad to see you are still working on shrinking the requirements for your general purpose dwarfputer Larix!

For everyone else:

Basically, Larix is working on making a custom designed computer architecture that is tailored to the unique constraints of the dwarf fortress simulation environment.  His goal seems to be the distillation of the most powerful computer possible, with the smallest number of parts possible.  Already, he has reduced the number of components down to a very small subset of previous dwarfputer designs.  He does this by constant experimentation with new logic circuit designs, and studious contemplation of reduced instruction set computing.  He is looking for the "ideal balance" between low component count, and computing power derived.

His current computer is a modified Harvard architecture computer-- That is to say, it has a lot in common with what Grace Hopper was developing COBOL on. Basically, a computer that has clearly separate program memory (holds the program instruction code) and data memory (Holds values used to make the evaluations or operations defined in the program).  This reduces the complexity of the computer tremendously, but reduces its usefulness, since the program code is read-only.  (Clever programmers can still make spectacular use of this architecture though)

In the above post, he describes the instruction word architecture he has created, the memory architecture he used, and the speed of execution. Using that information, a clever forumite could create an instruction compiler for this computer, allowing the use of a more well-known programming syntax to write the read-only tape.

I hope he manages to get his design down to under 2000 mechanisms some day.  A truly compact but powerful dwarfputer with an autofort template would open some interesting competitions for the more computationally inclined amongst us.  (The competition would not be to build the dwarfputer, but to make clever programs for it.) Currently, dwarfputing is a fringe element in dwarf fortress, because of the expense in time and resources required, and the precipitous drop in FPS that running one causes. A very small, compact, lean, and efficient dwarfputer could help change that. 

I want to encourage Larix to continue his efforts, as these kinds of diversions give a very good education in computational theory, and greatly hone logic skills.

Some of the obvious applications of a compact and high quality dwarfputer include automated stockpile/resource (water, Magma, etc) management, automated intruder detection and elimination with genuinely automated defenses, driving a display made of hatches to display pictures, automated trams of all kinds, and perhaps even programatically controlled magma casting at some point. (Dwarfputer controls dumping minecarts of magma and raising water levels inside a gantry to make large 3D structures, etc.)

A quick and painless dwarfputer can help remove some tedium from a well established fortress, if implemented well. Larix is doing the really hard work of prototyping and engineering such a computer. The task of hooking it up and programming it is much less complicated.  He deserves lots of kudos.

[SirQuiamus]

Considering that BaronW's calculator used 75 368 mechanisms, building a fully programmable computer with no more than 5940 is already a remarkable achievement, to say nothing of paring it down to 2000.
BTW, why do our modern-day computers still use these unwieldy things called transistors? Surely such outdated junk will eventually be displaced by minecart logic.

[Dorsidwarf]

But surgimus! That's what electrons really are.

Current is the flow rate of minecarts.

Minecarts surround atoms.

When the Heisenburg effect kicks in, that's the minecarts derailing.

[Larix]

Nah. Really tiny gears, that's where the future of computing lies. Once we figure them out, they'll be just perfect - instant response, toggle on every signal, no wires.

The big issue with the machine was getting all the timing right so that it could run autonomously. If you look at Jong's dwarven computer, you'll notice that it needs to be run manually, by a stream of "operate pump" commands, one for each substep of the fetch/execute cycle - it has no working system clock and cannot run by itself.

I didn't build an actual system clock - at the end of each instruction decoding event, a circuit gets triggered that starts the next program step, with a 250-step delay. With the delays from starting a program step to getting through the decoding sequence, that amounts to the quoted average instruction duration of 400 steps. Since each "read" command has an off-switch latency of 200-250 steps (it varies), that means data and program outputs can be active at the same time, but since program and data are entirely separate, they won't tangle.

Concerning mechanism count: i didn't build a few expansions i fully intend to add, just to stay under the 6000-mechanism mark. It'd be really difficult to get similar computational power with significantly fewer machinery. An adder will take several hundred mechanisms, a hundred bits of memory take at least a thousand, often quite a bit more.

In the meantime, i've fiddled a bit more with powerless minecart logic and came up with a pretty decent (although much less flexible) ring counter and a pretty fast decoder - using a very high-speed cart and doors (bridges are not fast - they take 100 steps to react to signals and can only switch carts moving below derail speed, ~2 ticks per tile of path). No indisputably better design for a memory cell, though. My weight-based system works well for read-only mass storage, but not for RAM.

PS: design for a powerless four-bit decoder, last iteration (saving mechanisms):



A very fast cart is needed to run this circuit, because switching is done by derailing vs. being deflected off closed doors. This switch doctrine allows using doors as "two-way" switches, i.e. most doors don't fork one cart path into two output paths, but two input paths into four outputs. Technically, a four-way fork would also be possible on a single door, but space requirements would become ludicrous.

Eight doors are controlled by the input; one door each by inputs one and two, two doors by input three, four doors by input four. This accurately sends the cart over one of sixteen pressure plates, according to the input bit pattern. Response time is short and reasonably constant, varying between ten and fifteen steps. This design keeps the cart ready constantly and resets itself. It could take a new signal ~ every 240 steps. The signals are so short that 100-delay buildings will not cycle but rather toggle when operated through them.

And the one thing that was still missing from my assortment of high-speed powerless circuits: a full adder. This is a ripple-carry adder, since minecarts don't compute instantly but rather at the speed of their movement. (Afterthought: well, one could conceivably run multiple adder cells "in parallel" and somehow look-ahead-calculate the carries for each bit before the carry's actually consulted. "Somehow", yeah. Any calculation under this doctrine consumes time, the more so when calculations get more complex - which they'll definitely do in actual look-ahead calculations. Good luck getting faster than the 10 steps per bit this single-cart ripple-carry adder achieves.)



A four-bit adder. It just calculated 7 + 12 + external carry-in = 20 (4 + overflow if thinking in four-bits).

Each adder cell requires all of three doors, two linked to the two input lines, one to the two pressure plates of the next lower cell that generate the carry. A third pressure plate per cell generates the output. The basic observation is that two doors can decode two bits worth of input into the full four outputs; A AND B gets pulled over its own plate to generate a carry, after that it can be recombined with A NOR B and the carry-in-governed door once again is pathed to provide a two-in-four-out split:
1. A=B (regardless of type) + no carry = no sum, no passed carry
2. A!=B + carry = pass the carry, no sum
3. A=B + carry = sum
4. A!=B + no carry = sum

2. is pulled over its own plate to output the carry, 3. and 4.'s paths are combined and guided over a shared plate to output the sum.

The adder takes about 10 steps per bit. Material cost: three doors and three pressure plates per bit, minimum of five linkages per bit (two inputs, two carry linkages, one output) = 13 mechanisms. A _bit_ less than the 24-36 mechanisms per bit in a fully mechanical adder.

Hmmm, at a moderate additional cost in mechanisms, it could send an _active_ "no-sum" signal as well, ideal to latch the result into a register without needing to clear it first.

[Larix]

First post has been slightly updated.

Since it was kind of overflowing, i'll put further design notes here.

Control logic

Building the logic components took a lot of time and mechanisms, but wasn't overly challenging. Building the circuits that actually told the components what to do and when was trickier. First of all, we need to read the next instruction from program memory, through a circuit that keeps track of progression through the positions.

1. Program counter

Spoiler (click to show/hide)

The easiest choice is a plain ring counter that just increments itself after each activation. This is delightfully trivial with powered minecarts:

Code: [Select]

.╔╗ ╔╗     ╔╗ ╔╗
R^R^R    ╔╝╔╝╔
# # #    # # #
            track
Buildings


Rollers push to the north. Everytime the roller under the cart is powered, the cart gets pushed north, sent to the east by the corner, over the pressure plate and onto the next roller. If that roller is not powered, it will wait there until power is connected again.

To limit the progression to a single step per pulse received, power to the rollers must be either guided to the specific roller or - much easier - limited to a very short pulse: power is connected by a short-duration signal (e.g. a cart elsewhere passing over a pressure plate) and disconnected again almost immediately. The easiest source for this off signal is the counter loop itself - just link the "power-off" gear to the pressure plates of the counter itself. To make sure that this results in a proper short-term power pulse, you need to connect main power through two gears:

Code: [Select]

P═Co═☼
P = power source
C = gear assembly engaged by the "clock" pulse
o = gear assembly _disengaged_ on every output the counter generates
☼ = counter's machinery

Thus, the C gear turns on when clock turns on and stays on for just over 100 steps. ~4 steps later, the cart in the counter touches one of the output plates and disengages gear o, also for just over 100 steps. No more power is delivered to the counter. On step 101 (+-2), gear C disengages again, while o re-engages at step 105 (+-1). No erroneous secondary pulse can come in.

What makes this type of ring counter peculiar is that it needs only two switchable gears to run - the two that pass and limit the power pulse. Between counting events, the machine itself is entirely ignorant of the current counter state and no signals are present. Counter state is held entirely by the location of the minecart.

This is the core of the program counter i used.

Spoiler: Paths only (click to show/hide)

The part at the bottom is a simple eight-position powered-minecart ring counter that wraps back to the start from position eight.

All the added pathing is there to allow program flow operations: skip next instruction (advances one position without triggering a program read) and jump to position (cart gets sent through the contraption to the north that splits the single path into eight output paths, governed by three bifurcations. These pathing variants are enabled by signals that disengage specific roller groups to let the cart pass through. The "jump target selector" in the north is disengaged entirely (automatically sending the cart to position 1) when resetting the system or whenever a new code module is loaded.

2. Decoder

     

A three-bit (operand) decoder, this one is specific to operation 111 (I/O, control). The basic concept of splitting a cart's path by providing power or no power to a roller should be well-known; it's a compact, fast method that i find easier to trace than gear linkages. The resultant paths in such a multi-function circuit aren't exactly intuitive, though. The main issue is that some of the functions send a standard "line up next instruction" command directly from the circuit, while several others send none (halt; request input at lever array) or from their own dedicated control circuit. Two of the instructions are further differentiated by the I/O control bit.

Spoiler (click to show/hide)

I built eight such circuits - one decodes the three first bits of the current command and activates one of the seven secondary decoders (or directly provides power to the program counter to perform a jump). Each of them includes a pressure plate on the return track to the start counter, cutting power to the entire decoder. Each decoder has a cycle time of less than 100 steps and would send overlong signals (or end up malfunctioning) when power isn't disconnected before the cart returns to the start.

Most bits are linked without toggling into the decoders, i.e. a roller is off when the bit is on, powered when the bit is off. Mechanism consumption for this kind of decoder is quite moderate - ~24 for a three-bit-eight-path decoder, including input power limitation but not counting output linkages.

Dividing the decoding into two tiers like this is not strictly necessary, but is preferable, because the dependence on minecart movement means larger decoders could end up with annoyingly long and irregular runtimes: a cart propelled by a highest-speed roller takes two steps to move a tile, and a full-spread six-bit (plus a few status-bit-governed variants) fanning out to about eighty paths would be unwieldy and could easily end up with decode times of 100+ steps.

Timing

That was the big issue that was left to handle after the operative devices and control circuits were thought out. The big breakthrough in coming up with a computer design was coming upon the idea of separated areas for program and data storage; probably while reading up on computation basics, taking a closer look at microcontrollers, since those tend to be the simplest available chips capable of computational completeness. This architectural choice (a.k.a. Harvard architecture) combined with the minecart ringcounter, the operation of which is completely state-agnostic - it just takes an unspecific power pulse as input and the minecart resolves the progression simply by its current position - results in a pretty trivial

"Execution cycle":

- power to ring counter
- counter signal triggers instruction read
- primary decoder decodes top three bits of instruction to start signal to secondary decoder (or jump)
- secondary decoder decodes second three bits, directly triggering all signals running the operation, primes next counting step
- instruction executes
- power to ring counter

That's a pretty linear process, and the only requirements are:
1. no lingering instruction signals when a new instruction is read
2. no lingering operation signals (register reads/writes) when a new operation is triggered
3. no operations may take place before relevant active signals have definitely been established

1. and 2. are because doors and hatches always have the state of the _last_ signal received. If a new "on" is sent before the "off" of the last activation arrives, a building can be closed when it should be open. Gear assemblies can also be in the wrong switched state when there are outdated signals still hanging around. They are easy enough to secure against by limiting signal length and putting enough distance between program steps. Since program and data are separate, it doesn't matter when data signals are still live when a new instruction is read/decoded or program signals are still up when data are being read/operated on.

Sufficient distance is provided by using a standard 250-step delay cycle from fully decoding an instruction to triggering the next program count. This gives a fairly large temporal buffer, it could probably be reduced by 50 steps without changing latch design (much more could be cut out with more time-conscious memory cells).

3. is a rather fiddly issue. With minecarts, every action takes time, reading data out of a memory cell and indirect signal triggering add significant and sometimes irregular delays to signal output. Thus, it's necessary to put a delay between triggering the instruction read and triggering the primary decoder. In the add and compare operations, a delay must be put between requesting the input data and evaluating the result. In some write operations, the receiving location must first be set to zero because the input consists of "on" signals only. In those cases, care must be taken to make sure the "write zero" doesn't intersect with the "write positive input". The extra delays from indirect operation don't make this easier.

I also fiddled around with the "load new program module" operation to slightly limit the time it takes. It's still by far the slowest instruction to execute. Things aren't helped by the need to set the entire program memory to zero before reading the new module and that carts take several hundred steps for a cycle through the ROM device.


I think my lack of a computing background made me open to unorthodox approaches and let me shoot for simpler solutions where established conceptions of what computers are or should be might have led to insisting on features that would have been conceptionally more elegant without providing tangible benefits in the setting of DF computing, which is slow, clunky and ressource-hungry. Minecart logic definitely opens some interesting paths by offering arbitrary-lenght delays, "one-way" operation through paths and direct signal generation, not to mention variants based on different-weight carts and plates calibrated for them.

[Baffler]

I understand this about as well as Urist McRecruit understands his equipment orders,
but all the same, I applaud the hell out your accomplishments.

Couldn't have said it better myself.

[Orange Wizard]

* Orange Wizard ceremoniously pins the Dwarven Science Medal on Larix.

[Nikow]

I was proud of me, when i figureout how to use water as one bit memory cell to hold my bridge closed... Wonderfull job mr Larix!

[Badger Storm]

So you're using a game played on a real computer to make an in-game analog computer?  The very idea of this just makes my head hurt.  It's like fiddling around on a graphing calculator to create an abacus.

[0rion]

So you're using a game played on a real computer to make an in-game analog computer?  The very idea of this just makes my head hurt.  It's like fiddling around on a graphing calculator to create an abacus.

I think the true and secret goal of Larix is to rewrite DF into DF itself... Eventually, that will lead to a DF spiral.
Anyway, great job here !

[laularukyrumo]

So you're using a game played on a real computer to make an in-game analog computer?  The very idea of this just makes my head hurt.  It's like fiddling around on a graphing calculator to create an abacus.

I think the true and secret goal of Larix is to rewrite DF into DF itself... Eventually, that will lead to a DF spiral.
Anyway, great job here !

People keep joking about this, but with the designs given here, it's really looking more like a matter of "when" than "if."

Larix, you are a goddamn pioneer. Forget the Dwarven Science Medal. You keep this up, I wouldn't be surprised to see your name in consideration for a Nobel.