- v50 information can now be added to pages in the main namespace. v0.47 information can still be found in the DF2014 namespace. See here for more details on the new versioning policy.
- Use this page to report any issues related to the migration.
User:Vasiln
My principal interest these days (in DF) is creature logic. I figure I might as well save some of my techniques here in case anybody stumbles over them.
Principles of Goblin Logic
I use goblins (or elves-- they both work) for my logic designs. There are a number of reasons for this:
- Goblins don't die of old age
- Goblins don't have babies
- Goblins don't need to eat, drink, or sleep
- Goblins don't need "citizens trigger" pressure plates (which leads to build hell)
- Goblins are readily available, in huge quantities, on almost all maps
- Goblins path predictably to map edge (after capture, at least)
I avoid mounts and other invader animals. I have had bad luck with them, and any tightly closed door breaks path.
Goblin Pathing
I said that goblins path predictably. This is true so long as the goblin has one and only one path to the map edge.
That requires some explanation. It's fine if multiple paths exist, so long as all paths lead through the same next tile. As soon as multiple tiles exist from which a goblin can escape to the map edge, we no longer have predictability.
Unfortunately, manipulation of path length doesn't help.
This leads to our basic three rules of goblin logic:
- Goblins will only be allowed to move if they have one and only path
- Goblins without a path will be constrained to a single tile
- There must always exist a path to the map edge from any logic circuit we build
Map Edge
The fact that goblins require a map edge for predictable motion does not mean that we can't wall up our fortress! There are a number of ways around this. We can build our logic circuits separate from our main fortress; we can have a bridged connection, such that goblin logic paths through the fortress normally, but through an alternative path when we wall up.
We can even connect our logic to the underground (not recommended, and not tested), or over a bridge 10 z-levels above the ground to the map edge (tested, and very safe).
Probably the safest way to run goblin logic is through a tightly closed artifact hatch leading to the surface. Building destroyers will not path through it, nor will they be able to break it. Creatures will not be able to pass it, but goblins will. Most or all creatures that will path to a goblin to kill it are either building destroyers or undead animals. No guarantees, though-- haven't tested everything.
The rules
AND gate
Consider an AND gate.
#### gDD^ ####
g is goblin, D is door operated by mechanism, ^ is a pressure plate, # is a wall.
The goblin must make it through two doors to hit the pressure plate. The doors are opened by some sort of memory cell, such that if P1 is true, the left door is open.
What happens when P2 is true but not P1? No path.
But what happens when P1 is true but not P2? No path-- but the goblin may still wander into the space occupied by the left door. If our situation changes, say, such that P1 becomes false and P2 becomes true, the goblin will have a path, despite falsity of P1 AND P2.
This is because we forgot one of our rules: if there is no path, constrain the goblin to a single tile.
##### g.DD^ #####
. is hatch over channel, triggered by mechanism, currently open
Now, we don't constantly evaluate the truth of P1 AND P2-- we only evaluate when neither P1 nor P2 are in the process of change. We specify when to evaluate this by sending a close signal to the hatch. If P1 AND P2, the goblin triggers the pressure plate. Otherwise he doesn't.
But if P1 is false, the goblin can still block off the door, the same as before. We need to send a null path, so that the goblin, when triggered, definitively returns true or false.
NAND gate
######## ^h.g.DD^ #h###### ###
h is hatch, triggered by mechanism
Now, we send close signals to the hatches on either side of the goblin. When we do so, the goblin paths predictably to one side or the other, and doesn't dawdle anyplace. This is because we've added a NAND gate to the left of our goblin. Anytime an AND is true, a NAND is false, and vice versa.
NOR gate and OR gate
I'm just going to show you these last two gates, because we can do any logical operation with NOR and NAND. You don't need any other gates. I'll show a simple OR, just because it's the opposite of NOR-- that is, if NOR is true, OR is false, and vice versa.
######## ^hh.g.d^ ######d# ########
That's it. Those are all the logical operators you need. (I'll probably point some others out anyways.)
Path to map and return to position
You might notice that all of the designs so far are single use. We have to load them with a new goblin every time we use them. We don't want that. Here's a NOR/OR expanded to show how we're going to do that.
############ <h^hh.g.d^h< ########d### ############
< is upstairs, pathing to map edge
All that we've done is add a hatch cover and a path to map edge. The peripheral hatch covers are each linked to the adjacent pressure plate. When the goblin arrives at either NOR or OR, the hatch opens, and his path to the map edge is blocked. There's one problem: at that point the goblin has no path, and so he won't path predictably. But we can fix that:
######<##### ######.##### ######g##### <h^hh.#.d^h< ########d### ############
By now, maybe you realize why the hatches next to the goblin are open: it's because he's standing on a pressure plate that, like all of our pressure plates, triggers the adjacent hatches. Let's draw the same picture, but with no goblin:
######<##### ######h##### ######^##### <h^hhh#hd^h< ########d### ############
Let's define a term: the goblin's position after running one of these tests is his reset position.
I want to point out one problem with this design as shown. Remember how I said that the goblin needs to always have one and only one path, or be constrained to a single tile? Here, after he evaluates NOR/OR, he has no path until his hatch opens-- which will occur after his evaluation. That makes his behavior unpredictable-- for instance, we can't be sure that a CLOSE will rapidly follow his evaluation. It's not a huge problem, but it's one we want to avoid.
Signal types
I mentioned how we were going to prompt the goblin to choose a path before-- we were going to send a close signal to the hatches adjacent to him. (Obviously, we won't want to send a close to the hatch preventing his escape to map edge though.) But sending close signals is easier said that done. Our pressure plates send opens when activated, and closes ~100 ticks after deactivation. We have a few choices. Consider:
### #l^ ###
l is lever, ^ is citizens trigger pressure plate
This is our basic input. The lever is linked to nothing-- its only purpose is to get a dwarf to run across the pressure plate. In this case, our pressure plate should be linked to the two hatches permitting our goblin to choose NOR or OR. The dwarf runs across the pressure plate, opening the hatches-- but they're already open. 100 ticks later, it sends a close signal to both hatches, which close, opening path to our goblin. Let's define a term: this kind of a signal, a rapid OPEN-CLOSE, is a trip.
But what if our goblin isn't in the proper position? What if he's currently running a test? Those hatches won't be open, and opening them will block his return to reset. That's not a big problem in this simple circuit, but we want to avoid it in general.
#### #l^d ####
All we've done is add a door, and linked the pressure plate at reset to this door. Now, the door doesn't permit tripping unless the goblin is at reset.
Except that's not quite true. The door will be open 100 ticks after the goblin leaves reset. A small revision:
############
#l^ d
############
Not perfect, but it works.
Of course, we don't want things to be run by dwarves. We want complicated logic circuits involving the interplay of multiple goblins.
Long paths
This should look familiar:
######<#####
######h#####
##################^#####
#<h^ hhh#hd^h<
####################d###
############
############
It's just our trip lever hooked up to our NOR/OR. Imagine a few of these in operation, with the NOR end tripping the reset hatches of the next. You can see that it won't be a huge problem to run trips from goblins instead of dwarves.
But there is a very large problem with this circuit. The hatch granting reset path will close before the goblin reaches our NOR pressure plate. There is a risk that our goblin will just run half-way to NOR, then back to reset, without triggering anything.
#######<####
#######d####
#######h####
###################^####
#<h^ hhh#hd^h<
#####################d##
############
Now we've added a door to the reset path, triggered by reset position. This door will close at the exact same time as the hatch, so we block reset path. But we still have the problem of getting the goblin to reset, because now no path exists, and even if one did, we have the risk of the goblin oscillating around the NOR path. We could build a complicated ground path to drag the goblin around. But instead, let's try something much more general purpose.
##################<# ## h#h# #d################^##### ##^ hhdh#hd^h< #h##################d### #<# ###
Now, reset position is linked to adjacent hatches, as well as doors blocking forward progress. NOR position is linked to adjacent door.
Let's trace it through. Hatches are tripped, goblin heads to NOR. Hatch to reset path closes at the same time as door to reset path closes, no path. Goblin continues to NOR, trips NOR. Hatch blocks NOR path. Door opens, permitting return to reset.
You might think that there's no room to make a similar loop for OR, but that's not true. We can hook it into the same return to reset arm.
#####
## ##
## ### #
############### ##<# ##
## h#h## ##
#d################^####d#
##^ hhdh#hdd^##
#h###################d#h#
#<# ###<#
There's got to be something more elegant, right? There is.
< < h########h #^hd h^# #h######h# # # #d# # # # # # # # # # # # # #d# # # #h######h# #^h dh^# h########h < <
Each pressure plate is linked to the adjacent hatches and the nearby door. Arrival at one permits continuation along the loop, as controlled by other devices. We don't actually need four arms, but it makes it pretty. Each arm contains an operation that we trip along the way. Each of the 4 pressure plates in the corner is a reset. We cause an operation by tripping the hatch clockwise of each pressure plate (we can trip all 4 at once safely, don't worry).
Here's what a NOR/OR arm might look like:
### < ##d## < h### d^###h #^hd### h^# #h##hh^##h# # #######d#
We could build further operations into additional arms, but the next arm doesn't actually have to perform any operation. Consider the following:
### < ##d## < h### d^##h #^hd###h^# #h##hh^#d# ## ##### # ### ## #######
This is a functional, return to reset NOR/OR, that operates reliably for goblins of any movement speed, and returns goblins to the original position. It follows our rules: a goblin either has 1 and only 1 path, or is on a single tile. It returns a true or a false (although we can safely ignore the false, if we don't care) in the form of a trip-signal-- which is the same kind of signal that starts this device. Given equally fast goblins, two of these could trip each other, although that would be pointless.
Since the second arm of our loop does nothing, and doesn't even need a trip for the goblin to path down it, let's call the rightmost path to surface the completion point.
There's only one thing to be careful of, and that's making it too small or making it run too frequently. Return of goblin to reset does not mean the entire circuit is reset yet! We need to give time for the hatches by completion to close before making another run through the circuit. Ideally, no circuit should be repeated until 100 ticks from the time that the goblin has returned to reset; for one arm loops like this, it's good enough that the circuit not be run again until 100 ticks after leaving the completion point. Notice one thing-- running the completion point generates a trip signal itself, that doesn't send a close for 100 ticks. Linking the completion point to the start hatch ensures running this circuit as frequently as it can be run. (Not that we want that. We need time to be able to write to memory.)
In larger loop, all we need to be careful of is that we don't run the operation again until goblin has returned to reset position.
Any further discussion is going to get hopelessly complicated if you don't understand this basic loop. There is an operation, and there is infrastructure, and you need to know which is which. Our infrastructure is never going to change, but our operations are, and mostly, I'm not going to show you infrastructure again.
Infrastructure
Infrastructure is only ever linked to from within the circuit itself, with one exception (the begin hatch) which is linked to plates both inside and outside of the circuit.
Pressure plates: The leftmost pressure plate is reset position: it lets us know the operation is ready to be run again. The rightmost pressure plate is completion point: it serves an infrastructure purpose, and if we want to, it can let us know the operation has been completed.
Hatches: The hatches adjacent to reset position and to completion point are infrastructure. Infrastructure hatches are linked to adjacent pressure plates. They limit movement through the operation. The hatch immediately to the right of reset is a special hatch: tripping this one begins the operation. We'll call this special hatch 'begin.' Other than begin, no hatches are linked to anything except the adjacent, infrastructural pressure plates.
Doors: The door just to the right of begin, and the door one tile south of completion, are infrastructural doors. They are linked to reset and completion respectively, and block retrograde pathing for long loops.
Operations
Operation structures are only ever linked to from outside of the circuit.
Doors: The two doors in the middle, on the uppermost arm, are operations doors. Their layout forms an OR decision.
Hatches: The two hatches in the middle, in the arm just below the OR decision, are operations hatches. Their layout forms a NOR decision.
Goblin memory and more signal management
But what sets the doors and hatches that constitute evaluation of NOR/OR? Obviously, we can't set them with a trip signal.
######## <h^hh^h< ########
Hopefully, if you've followed me so far, I don't have to explain the above. Each pressure plate is linked to the immediately adjacent hatch.
This is our crudest form of goblin-based memory. One or more of our pressure plates is linked to comparison doors and hatches. To toggle our memory state, we send a trip signal to the two middle hatches.
For an example circuit, consider two memory cells and our NOR/OR. The rightmost pressure plate of each cell is linked up to one of the doors and hatches in the center of our NOR/OR. We'll call this rightmost value '1'. Our OR arm trips the central hatches on memory circuit 1. We run the operation, to begin with, by tripping the hatch clockwise of reset.
What happens?
Memory a is 1, memory b is 1: Memory a becomes 0. Memory a is 0, memory b is 1: Memory a becomes 1. Memory a is 1, memory b is 0: Memory a becomes 0. Memory a is 0, memory b is 0: No change to memory.
This is a fun demonstration, but you can see that we want more features than just toggling our memory. We want the ability to set memory to a certain value.
### ###d#### <h^hh^h< ####d### ###
This is our settable memory. Let's change it so that instead of linking OR to the hatches, we link it to uppermost door.
Memory a is 1, memory b is 1: Memory a becomes 0. Memory a is 0, memory b is 1: No change to memory. Memory a is 1, memory b is 0: Memory a becomes 0. Memory a is 0, memory b is 0: No change to memory.
Or we link it to the southermost door:
Memory a is 1, memory b is 1: Memory a becomes 1. Memory a is 0, memory b is 1: No change to memory. Memory a is 1, memory b is 0: Memory a becomes 1. Memory a is 0, memory b is 0: No change to memory.
You might also notice that this memory forms a loop-- just as we settled on for our NOR/OR. A goblin running between the two pressure plates always runs in a certain direction, and steps on each tile of the loop exactly once. All good goblin design forms loops like this. Notice, too, that it follows our rules: so long as we write to it no more frequently than every 100 ticks, our goblin always has one and only one path, or is standing on a single tile.
(By the way, I am incredibly indebted to Fenwah and his high speed creature switches described in http://www.bay12forums.com/smf/index.php?topic=62798.0 for this memory design, and from that, for everything I'm writing here.)
Hopefully you're noticing just how important signal management is. I said that we needed trips to execute our comparison loop, but like I said, that won't work for our comparison parameters. We need stable values-- open or close. That's where memory comes in. We just have to be careful not to write to memory at the same time that we're reading memory, or our comparisons won't make any sense. In a worst case scenario, a door might close on a goblin, or a hatch open up underneath him, and computation stops.
Practical concerns with goblin based computing
Let's take a break from logic and design for a minute. It's easy to forget that these aren't just bits moving around our fortress computer-- they're still invaders.
You have to pit them into your memory cell. If dwarves walk under or over our logic, they'll get interrupted. If a dwarf with a crossbow gets interrupted, he'll shoot your goblin. If you want to make changes to your logic designs, you have to kill any goblins occupying the space first.
To manage all of this, there are a few things you should do before pitting any goblins. All pits and all stairs to goblin access should be hatched over. Not locked hatches, of course, because that would break pathing. All spaces underneath channels should be walled off, or at least doored off. All objects (including stone) in the logic areas should be removed, so that dwarves don't path there. And you should have a couple of crossbows and a couple of bolts, because it can be a pain to find a melee route to a goblin in one of these circuits.
Cats pose a special problem. I've never seen them screw up goblin pathing, and I'm not sure they will, but they path into logic areas because these areas spawn vermin. Cats block doors when they close, and vermin corpses block doors too. Tightly closed hatches over your paths is a good start, but generally insufficient-- if a cat wants in, it will get in eventually.
There is one design decision that can solve this problem for you. Instead of doors, you can use hatches over ramps or staircases.
Hatches are really interesting because, depending on the surroundings, they can be built to allow path when closed (as when over a channel) or when open (as when over a ramp or staircase). And the big thing is that they never get stuck open.
One drawback that I've found with using hatches instead of doors is design convenience. It's hard to visualize a circuit when it spans multiple z-levels. The other drawback is the difficulty in designing doorless memory. It's possible, but inefficient.
Incrementing memory and percolating functions: the two-bit add
I want to show you a special kind of memory.
###<# ##h#h# ##^#^## #hd#dh# ##^#^## #h#h## #<###
This, of course, requires some explanation.
NE pressure plate corresponds to true. It is linked to both adjacent hatches. SW pressure plate corresponds to false. It is linked to both adjacent hatches. To set equal to true, open the west door. To set equal to false, trip the hatch to the NW of true. SE pressure plate sends a trip when state changes from true to false when triggered via 'toggle with carry.' It is linked to both doors of the next memory cell. To toggle with carry, open both doors. NW pressure plate isn't going to be used. Yet.
In other words, this is an unnecessarily complicated memory cell to use on its own, but it has nice functionality when put in a line of several, with the 'carry' plate of each linked to the doors of the next. We can still use it as normal memory (although it's a little slow for that purpose). It still forms a loop that follows our rules.
Imagine two of them, the first linked to the second (but not the second linked to the first!) When we toggle with carry to set memory a = 1, we don't do anything to memory b. But when we toggle with carry to set memory a = 0, we also send a toggle to memory b.
Imagine now that we have four bits of memory and an operation to add them. We have memory a1, memory a2, memory b1, memory b2.
####### #d^#d^# r## ##c #h #h # #######
r is reset position, c is completion point; you can see that I left out infrastructure
The western doors and hatches are linked to a1, the eastern, to a2. The western plate carry-toggles b1, the eastern plate, b2.
Here's how it works in code:
If a1 then b1=b1+1 If b1>1 then b1=0 and b2=b2+1 If b2=2 then b2=0 If a2 then b2=b2+1 If b2=2 then b2=0
We're adding bits! There's one problem, and I hope you noticed it. We can't write to memory twice at the same time! This percolation forms a write, and the second arm of our write operation isn't going to play pretty with it. We could do this:
################# #d^###########d^# r## ##c #h ###########h # #################
That would slow it down, but isn't guaranteed to work.
This is better:
################# #d^###########d^# r##h h##c #h ###########h # #################
In this case, the two central hatches we've created should be linked to the memory a1's carry-toggle, so that we institute an automatic 100 tick delay between writes. This is still not foolproof, but it's more foolproof.
Instituting Delay
The problem is that it's not safe to write to the next bit until the previous bit has had time to percolate. Since percolation uses a trip signal, we need to wait 100 ticks, plus any time for the goblin to move to his new position.
######### <h^h^h^h< #########
This looks a lot like a memory cell. There's one extra pressure plate in the middle, though. It's not linked to any hatches in this circuit though.
When we send the two interior hatches a trip signal, they'll get a redundant open, then close 100 ticks later. Our goblin will run across the central plate, sending a trip.
Let's rebuild our adder. Remember, all operations are loops-- completion point can as easily serve as reset position for the next arm.
####### #d^#d^# 1##2##c #h #h # #######
1 is reset1, 2 is reset2
I haven't shown you infrastructure. We link reset2 to the interior hatches on our delay. But we can't link our delay trip to the begin hatch for reset2-- that's insufficient delay. Rather, we build a second delay circuit, linked to the first delay circuit-- that is, delay1 trips the interior hatches of delay2, and delay2 trips begin2 of our 2 bit adder. We now have >200 ticks delay before running the add on the second bit.
Hopefully, it's obvious how this can be expanded to add any number of bits. Hopefully, it's also obvious that percolating functions can be very slow. A 6-bit percolating add takes more than one in-game day to complete.
Subtraction is almost identical. The only difference is that we trigger the toggle with carry on a change of 0 to 1 rather than on a change of 1 to 0. In other words, rather than using our cell's SE pressure plate to toggle-with-carry the next bit, we use our cell's NW pressure plate. A slight redesign of our toggle-with-carry memory cell could allow toggle-with-carry(add), toggle-with-carry(subtract), and toggle.
Multiple word adds: the carry bit
Before we get any further, let's define a term. A word is a group of bits that we perform operations on as if it's a single datum. You're probably familiar with bytes-- a byte is an 8-bit long word. Words can be any length, but we're using 2-bit words because it lets us keep things simple, while demonstrating principles that can be expanded to words of any length.
Two bits don't give us very big numbers. We may need to use multiple words (of two bits each) to enable larger numbers. We want a carry bit.
A carry bit is an extra bit of memory that is set to 1 every time our last add (a2+b2) goes from 1 to 0, and is set to 0 every time our last add goes from 0 to 1. So we need both the NW and SE pressure plates on our last bit of adding memory.
To add two single numbers, each consisting of 3 2-bit words (add e,c,a to f,d,b) we need to:
Add a and b, write carry Add carry to c1, write carry Add carry to e1 Add c and d, write carry Add carry to e1 Add e and f
You can see that very large numbers are going to involve a large number of steps. We're much better off using larger words to begin with.
Multiple arm operations: two-bit compare
Let's build an arm that evaluates bits a1, a2, b1, and b2 and returns true if b>a.
##############
## ^##
### ########## # ##
#dh# #### ### ##
r### ##dh## ## #
# ######## ########c
## #dd # #dd ^# #
## #### ######## ##
## #hh# #hh ^# ##
## #### #### ##
##hd###hd# ##
### ####^##
## ##
######
If you notice, there are 12 paths to run through from reset to completion. These paths are chosen such that one and only one is ever open. The goblin traces through two sets of evaluations. The first set of evaluations, on the left, correspond to b2 and a2 respectively; on the right, b1 and a1 respectively. That is, the most northwestern door corresponds to the state of b2, and the southeastern door corresponds to the state of a1. The northeast pressure plates returns true if b>a; the others are only necessary if we expand it.
Here's our goblins flowchart:
If b2 and not a2 return true If a2 and not b2 return false If a2 = b2 then If b1 and not a1 return true Else return false
You can see that this > comparison actually contains all possible ordinal relationships of a and b: greater than, lesser than, and equal. We can put pressure plates anyplace we want to evaluate this. We can make those pressure plates do something or not do something with other circuits-- in other words, this is a complete 2-bit compare.
You might also suspect that an 8 bit compare of this design would be huge-- but not really. Look at the return from the southern and northern compare of bit 2. The design is as tall as it needs to be-- we only need to make it wider. With each bit we compare, we only have to continue our compare if a and b at a particular bit are equal. If one is larger or smaller than the other, we divert them into true or false returns.
The Pathing Stack
There's one problem in our comparison design, and you don't have to kick yourself if you didn't notice it. I haven't warned you about it yet.
I'm not entirely certain of how goblins path, but the seem to maintain a stack of locations where path was broken. What this means is that after a few runs of our comparison, there's a chance of a goblin behaving unpredictably. Consider what happens if he runs down the a2<b2 arm, but remembers that he wants to go down one of the a1=b1 arms. He might path backwards, tripping off an extra evaluation plate. I'm not sure if this will happen or not, but after that huge design, we don't want to risk it. Beyond that, it's easy for complicated operations to lead to multiple paths when considering possible retrograde motion through operations. We want to develop good design habits, so that we don't run into this problem.
We need a redesign. We could keep each arm separate, not feeding into the next, but by the end of an 8-bit comparison, we'd have 256 arms. That's not viable.
Infrastructure: Multiple Completion Points
Instead, we're going to give the goblin individual places to return to reset. We're going to give the goblin multiple completion points. All of these completion points will link into a single pathway to reset. We're going to use an extra z-level to make it clean. Before we do that, let's remind ourselves of the necessary components of a completion point:
####### #r##### ##d#### ###^h<# ##h#### #o##### #######
o comes from operation, r leads to reset, < paths to map edge
I've walled it off to give us an idea of space requirements.
z level 0
##### #####
##dh<###dh<#
# ##### ####
# # # #
# # # #
# # # #
# # # #
# # # #
##### ##### ####
#<h## dd## dd<#
###rb#### ####
#<h## hh## hh<#
##### ##### ####
# # # #
# # # #
# # # #
# # # #
# # # #
# ##### ####
##hd<###hd<#
##### #####
r is reset position plate, b is begin hatch, < is upstairs
z level 1
### ###
#>## #>##
##h#### ##h####
###1h<# ###2h<#
###d########d####
## # ##
###### ##d####
# ###3h<#
### # ##h####
#X# # #>##
########### ###
#> ##>##
########### ##h####
# ###4h<#
###### ##d####
## # ##
###d########d####
###5h<# ###6h<#
##h#### ##h####
#>## #>##
### ###
1-6 are completion point pressure plates, > is downstairs, X is up/down stairs that maps to map edge, < is upstairs that paths to map edge
So this is pretty large. You could shrink it, but it's better just to keep these things understandable. You chain it indefinitely to perform comparisons on words of any bit length. It is 21 tiles broad, and 10 tiles long for every bit evaluated.
Here's the problem. To make comparisons between even 4 words, we need 6 of these. That's not going to work. We need a way to be able to build this once, such that it can compare any of our words.
Memory Addressing
The key to that is to have a very small memory space that we can perform operations on, and a much larger memory space with very limited functionality.
The least functionality we need from memory is the ability to read and write. If we break it down further, we need the ability to read a true, read a false, write a true, and write a false.
###### rddc ###### rdhc ###### #<# #h# #^## ##hd# #dh## ##^# #h# #<# ###### rhdc ###### rhhc ######
r is reset, c is completion, < is stairway pathing to exit
This is the start of that functionality. We see 5 elements here. From top to bottom: read true from memory; write true to memory; memory; read false from memory; write false to memory.
We've talked about memory before, and you should recognize it. As for the other four pathways, we're going to call them 'addressing paths.'
The left door or hatch in each pathway is set by the truth of either our memory cell (for the read paths) or the truth of the cell we're reading from (for the write paths). The second is determined by the truth of a read bit-- a bit that keeps track of whether we're currently reading or writing. If we're reading, the doors and hatches open; if we're writing, they stay closed.
The completion will send a signal: either set memory to true or false, in the case of writes, or set a distant memory bit to true or false, in the case of reads.
So only one of these four pathways is going to be open at any given time. That's nice-- it means we can just connect all the entries to a single reset position, fed from each completion point.
There's one other thing we can do here.
###### rdddc ###### rdhdc ###### #<# #h# #^## ##hd# #dh## ##^# #h# #<# ###### rhddc ###### rhhdc ######
I've added an extra door before completion. This is going to be set by the state of our addressing bit. Imagine a second structure like this, a few z-levels below, fed from the same reset position-- the only difference being that we have hatches linked to our addressing bit instead of doors. We still only ever have one pathway-- but we can switch which memory cell we're going to read from or write to by changing the position of our addressing bit.
One addressing bit will let us address 2 bits separately. 4 will let us address 16 bits separately. Imagine 16 of the following, forming a tower of addressable memory:
######## rddddddc ######## rdhddddc ######## #<# #h# #^## ##hd# #dh## ##^# #h# #<# ######## rhdddddc ######## rhhddddc ########
Different levels would see different combinations of hatches and doors at the end of each completion.
If you do make a tower out of these, don't forget practical considerations. Either each cell needs to be offset, or there need to be two z-levels between each cell so that we can pit goblins without being interrupted by goblins from above. (We could get away with 1 z-level between cells if we only ever pitted from bottom to top, but then if there's a problem with a lower cell, we'd have to kill every goblin above that cell before we could pit a new goblin.)
We're using 2-bits for demonstration purposes though. We can address our first bit and our second bit independently, and read each to a buffer-- the first to the buffer's first bit, the second to our buffer's second bit. So really, we need two of these towers.
Adressing Toggle Memory
Remember our toggle memory? It had no way to set true or false, only a way of toggling it. That doesn't mean we can't address it though-- we just a few more pathways.
######### rdddddd c ######### rdhdddddc ######### ######### rdhddddhc ######### #<# #h# #^# #h# #h# #^# #h# #<# ######### rhddddd c ######### rhhddddhc ######### rhhdddddc #########
Whereas before we had pathways for read true from memory, write true to memory, read false from memory, write false from memory--
We've changed two of those pathways, and added two more. We still only have two read functions, but now we have four write functions: Write true to true memory, write true to false memory, write false to true memory, and write false to false memory. The extra hatches and doors at the ends of these write functions are linked to the status of our memory. Writing true to true memory doesn't trigger anything, but writing true to false memory triggers a toggle. The extra complexity of writing to toggle memory means that we're not going to use it. Settable memory is preferable.
Addressing manager
If we operate on all of our bits at the same time, we'll need to know when our operations have completed. Managing that task is tricky. We can't know when to evaluate for completion, because we have to know that we've completed to know that none of our completion flags are going to undergo any change! Luckily, we CAN know that the flags aren't going to change until we tell them to, because we can use steady-state signalling. So we can get away with something that I said not to do. Here we have a circuit where the goblin has the potential to be without path, yet with multiple tiles to stand on.
#### #### #<h######h<# ###^dd^h^### ##h######h# ## d## ########
I've spelled out infrastructure because it's an abnormal circuit, something we don't normally want to do. Left ^ is reset; right ^ is completion (indicating that memory has been read). Notice the important omission of a reset begin hatch! Instead, I have a completion begin hatch. Central doors are opened by the presence of a goblin on a memory address completion plate. Central ^ sends a trip to a hatch permitting return to reset for our addressing goblins, as well as to the central doors and the SE hatch leading from completion to reset. That ensures doors close at same time as hatch opens, permitting return to reset only when no path exists from reset to completion. (We can do it another way instead, if we want: addressing completion opens central doors and SE hatch. That's because we know they're going to return to reset as soon as they can, leading to a close signal to the SE hatch at the same time that we send a close to the central doors.)
We can only do this because we know that:
- All doors will open before any close (because it's only movement through the trip that will lead to their close)
- Addressing manager reset is completely infrastructural, not linked to any outside operations
Buffers and Registers: Full-featured memory
So remember: we've built minimal functionality into our basic memory, but we're going to build maximum functionality into a few pieces of memory. Let's ignore maximal functionality for right now and just make one bit of our buffer with basic functionality: read true from memory, write true to memory, read false from memory, write false from memory.
#<# #h# #^## ##hd# #dh## ##^# #h# #<#
Woah. That's just memory. Where's the read and write?
We don't need it. We built that functionality into our basic memory, and it's shared functionality. Every read true from memory trips the southern door; every read false from memory trips the northern door. Meanwhile, our northern and southern pressure plates are linked to the doors and hatches in our memory addresses, permitting only write true to memory, for instance, while our buffer bit is true.
Couldn't we build that functionality into our buffer, rather than our memory? Really, memory read/writes with addressing isn't built into either the memory or the buffer. It's a function that works between the two of them. The physical location of our memory addressing circuit doesn't matter-- we can build it next to the buffer, or we can build it next to the memory, or we can build it someplace else entirely. But we can't make it any simpler by building it one place than the other: we still need four paths per bit. Placing it near the memory lets us keep an eye on it at the same time that we keep on eye on memory, and since both are proportional in size to the same value (number of bits), that makes the most sense-- at least to me. Really, it doesn't matter where you put it.
So are we going to build in functionality, for instance, for our ordinal compare? Not yet. Remember, ordinal compares require two values. To do an ordinal compare with every piece of memory would take 16 compare circuits, if we had 16 words of memory! So really, what we need to do is give functionality to our buffer to write to at least one other new piece of memory-- a register. That way, we can read a value, write it to the register, read a new value, and run an ordinal compare on any two words.
But wait-- we might need to output something from our compare to a piece of memory, and the only way we have of writing to memory is through our buffer. So instead of reading from and writing to a single bit, we need to build our buffer such that it's capable of reading from at least 1 bit, and writing to at least 2 bits.
##### rdddc write true from buffer to register 1 ##### rddhc write true from buffer to register 2 ##### rhddc read true to buffer from register 1 ##### #<# #h# #^## ##hd# #dh## ##^# #h# #<# ##### rdddc write false from buffer to register 1 ##### rddhc write false from buffer to register 2 ##### rhhdc read false to buffer from register 1 #####
You can see this is pretty similar to our previous addressing system. The only differences are that we have only a 1 bit address (2 values, register 1 or register 2) and that we have extra pathways, allowing us to write to multiple locations. In reality, we probably want to be able to write to more than two locations from our buffer, but we can get away with reading from only one extra location. We could string these buffers along: we could write to buffer 1 instead of register 1, for instance, and from there, write to register 1 or 2, and write to buffer 2 instead of register 2, from there writing to registers 3 and 4, but that's unnecessary. To write to four different locations, we just need 2 new paths for every extra location, for a total of 8 write pathways, and we need an extra door, to allow addressing of 4 different locations. 4 locations will be enough. (Two are going to be data registers, and one is going to be an instruction register, that keeps track of what our instruction is while we execute it, but we'll get to that later. The extra location is just that-- extra. We can do whatever we want with it later. It's never a bad idea to build in reserve like this when you can.)
###### rdddhc write true from buffer to instruction register ###### rddhhc reserved ###### rddddc write true from buffer to register 1 ###### rddhdc write true from buffer to register 2 ###### rhdddc read true to buffer from register 1 ###### #<# #h# #^## ##hd# #dh## ##^# #h# #<# ###### rdhdhc write false from buffer to instruction register ###### rdhhhc reserved ###### rdhddc write false from buffer to register 1 ###### rddhdc write false from buffer to register 2 ###### rhhddc read false to buffer from register 1 ######
Our complete buffer. Next, of course, we'll need a few registers. But before that, we have to know exactly what kinds of operations we want our registers to do: for instance, we've shown how the capability to add or subtract can be built into memory. Before I recreate that, though, I want to try and figure out if I can make a look-ahead adder.
The two-bit add revisited: Examining the look-ahead adder
If you remember, I demonstrated two different ways to add earlier in the thread.
Two? Yes. First I demonstrated an adder that adds a bit, sending a percolating effect through the word, waits 200 ticks, then adds the next bit. After that, I demonstrated a way to add multiple words, by keeping track of a carry bit between adds. If you think about it, the second method would work fine for single bit words as well as it does for two-bit words or eight-bit words, although it should be clear that this method leads to much slower computation. Either method is very space efficient; we need slightly modified memory, a delay circuit, a bit of memory for our carry, and a disgustingly simple operation pipeline.
The second version is a full adder (that means we add two integers of any word size). The first is a ripple-carry adder. That means that the carry ripples through the word, and we wait for the carry to ripple before continuing the add. Why is the first method so much faster than the second method? It's because we're actually processing carry adds and our main add in parallel. We add the first bit, then ripple the carry; the thing is, we don't wait for the ripple to finish before processing the next add. We can do this because each of our bits of memory is capable of processing on its own. By time we reach the third bit, any carry from our first add is being rippled through the sixth bit, and any carry from our second add is rippling through the fourth bit. We're actually processing three bits at once. The reason we need any kind of delay at all is because of the latency of our memory-- we can't write a carry and an add at the same time.
That's still slow. It's still going to take over a day to process the addition of two 6-bit words. There's another way to do it. What we're going to do is include processing our carry with our add.
Adding our first bit is easy. There's no carry, so we only need three pathways: adding a 1 to a 0, adding a 1 to a 1, or adding a 0 to a 0.
####### ##hh 1 # ###### r#dd 2 # ###### ## #hd## ## ## 3 ##dh## #####
Here we have 3 continuation points, labelled 1 to 3. You'll notice that two paths lead to continuation 3, but only one is ever going to be open. You might also notice that this is extraordinarily similar to the begin of our ordinal compare. We have an XNOR for the top two paths and an XOR for the bottom two paths.
Let's consider what each of continuation points mean. 1 means neither bit was true. 0+0 is 0, so we write 0 to the output, and we also write 0 to our carry. 2 means both were true. 1+1 is 2, so we write 0 to our output, and 1 to our carry. 3 means one or the other were true, but not both. 1+0 is 1, so we write 1 to the output, and we write a 0 to our carry.
Adding the next bit is where it gets ugly. This is an octopus function.
######
##ddd 1
## #####
## #hhd 2
## #######
## # hdd 3
## #########
# # dhd 4
r###########
# # hdh 5
## #########
## # dhh 6
## #######
## #ddh 7
## #####
##hhh 8
######
The leftmost door or hatch corresponds to the second bit of the first word; the next door, the second bit of the second word. The third corresponds to the state of our carry bit. Essentially, what we're going to do is to get around rippling our carry by including it in our add so that we aren't limited by the latency of our memory.
I don't know what to call this. I'm not sure it exists in an electronic version.
Let's make sure we know what the 8 completion points mean:
# Both bits true, carry true: output 1 to bit and carry # Both bits false, carry true: output 1 to bit, 0 to carry # First bit false, second bit true, carry true: output 0 to bit, 1 to carry # First bit true, second bit false, carry true: Ditto # First bit false, second bit true, carry false: output 1 to bit, 0 to carry # First bit true, second bit false, carry false: Ditto # Both bits true, carry false: output 0 to bit, 1 to carry # Both bits false, carry false: output 0 to both bit and carry
We could write the carry to memory (ideally, more than one bit, maybe alternating, maybe 8 bits, to get around latency)-- unless--
Let's rearrange this and expand it.
#### ####
## ## ## ##
######d## ## ######d## ##
##hdhh5#### ## ##hdhh5#### ##
## #####h<### ## ## #####h<### ##
## #hhdh2###### ## ## #hhdh2###### ##
## #######d ## ## ## #######d ## ##
## # dddh1##### ## ## ## # dddh1##### ## ##
## #########h<#### ## ### #########h<#### ## ##
# # hddh3####### ## # # hddh3####### ## ##
r###########d #r###########d #
# # dhdh4####### ## # # dhdh4####### ## ##
## #########h<#### ## ### #########h<#### ## ##
## # ddhh7##### ## ## ## # ddhh7##### ## ##
## #######d ## ## ## #######d ## ##
## #dhhh6###### ## ## #dhhh6###### ##
## #####h<# # ## ## #####h<# # ##
##hhhh8#### ## ##hhhh8#### ##
######d## ## ######d## ##
## ## ## ##
#### ####
Nope. Doesn't work.
What I tried to do was see if I could design it in such a way that tripping a carry would last until the goblin next reached a carry=true completion point. In general, you've got 10 moves before the close part of a pressure plate signal comes; but even with redesign, I've got 23 moves, many of them diagonals. Not going to work.
However, this is still a decent design for memory based carry bits-- because of the latency of memory, we have to make sure that we're not going to write to it particularly frequently! In this case, I see that our shortest path is 23 straight steps long, no problem for using a single bit to store carry. Enough time to propagate the close from carry no longer being true, enough time by far for a goblin to move from false position to true position.
But our longest carrying is still 23 steps! That's far longer than our path with our parallel-ripple-add. This design is going to function more slowly than our parallel ripple add. 200+ ticks per bit is good enough, I guess.
It was a good design exercise, in any case.
Improved XOR
I've been using a fully expanded (two path) XOR, but I just realized this isn't necessary.
### ##d## dhh #####
This is a single path XOR that will work as well as our two-path XOR for everything but our compare function. With it, our octopus can become a sextopus. That's not enough to save it though.
Look-ahead Adder
There's one more design to consider. Can we add in parallel, design a two-bit carry, then add our carry in parallel? It might be problematic-- what if our carry generates its own carry? Of course, it couldn't with two-bit word size, like we've been demonstrating; we have to consider it in something bigger, like four bits. It would look quite a bit like our previous carry check pathway: slower than it takes to propagate ripple carries.
What if we evaluated each bit in parallel (at the same time that we added each bit in parallel) for its ability to create, propagate, or end a carry? We'd know where carries began, we'd know where carries ended, and we could send a minimum of carries, all at the same time, to propagate in parallel. Each carry evaluation would be the same size (about 20 tiles across), so we'd have our addition and our look-ahead completed after about 200 ticks, regardless of our word size. Then we'd propagate the carries, at the precise locations called for.
In a best case scenario (no carries), we'd add two words of any size in 200 ticks. In a worst-case scenario, we'd have to wait an extra 800 ticks or so for propagation across an 8-bit word. 1600 ticks, down to 200-1000 ticks? Less than half the speed.
I didn't really want to design it, but I guess I have to now.