v50 Steam/Premium information for editors
- 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.
This notice may be cached—the current version can be found here.
Editing User:Vasiln/Goblin Logic 3
Jump to navigation
Jump to search
Warning: You are not logged in.
Your IP address will be recorded in this page's edit history.
The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
==Optimization: Opcodes revisited== | ==Optimization: Opcodes revisited== | ||
+ | |||
Right now, we have seven operations codes to spare: 0000, 1010, 1011, 1100, 1101, 1110, and 1111; and 15 arguments for XOR; and 8 arguments for bit shift or bit rotate. Way more than we need. At the same time, we don't have nearly enough memory. We could do a couple of things: we could add instructions, so that for instance it wouldn't take two instructions to add two numbers. We could also switch it up to a 3-bit instruction and a 5-bit address. | Right now, we have seven operations codes to spare: 0000, 1010, 1011, 1100, 1101, 1110, and 1111; and 15 arguments for XOR; and 8 arguments for bit shift or bit rotate. Way more than we need. At the same time, we don't have nearly enough memory. We could do a couple of things: we could add instructions, so that for instance it wouldn't take two instructions to add two numbers. We could also switch it up to a 3-bit instruction and a 5-bit address. | ||
Line 15: | Line 16: | ||
Two of these need specifying. | Two of these need specifying. | ||
− | + | 100xxxxx Register operations | |
+ | |||
*10000000 XOR a and b -> a | *10000000 XOR a and b -> a | ||
*10000001 Add: XOR a and b -> a, write 9-bit carry word to buffer, XOR a and carry word->a, write 8-bit carry word to buffer, with carry(8)=output of first XOR(8) OR output of second XOR(8) | *10000001 Add: XOR a and b -> a, write 9-bit carry word to buffer, XOR a and carry word->a, write 8-bit carry word to buffer, with carry(8)=output of first XOR(8) OR output of second XOR(8) | ||
− | *10000010 Add with carry: Add a and 0000000x where x is equal to carry(8), add a and b, | + | *10000010 Add with carry: Add a and 0000000x where x is equal to carry(8), add a and b, output carry(8) |
*10000011 XOR a with 11111111 | *10000011 XOR a with 11111111 | ||
− | *10000100 Add 1 to a (XOR a and | + | *10000100 Add 1 to a (XOR a and 1, XOR a and carry word) |
*10000101 Compare a to b, output to b | *10000101 Compare a to b, output to b | ||
− | *10000110 | + | *10000110-10011111 Reserved (26 choices!) |
− | + | ||
− | + | 101xxyyy Bit shifting register operations | |
− | |||
*10100yyy Arithmetic right shift 0-7 units (y units) | *10100yyy Arithmetic right shift 0-7 units (y units) | ||
*10101yyy Arithmetic left shift 0-7 units (y units) | *10101yyy Arithmetic left shift 0-7 units (y units) | ||
Line 43: | Line 44: | ||
===A note on the notion of "Turing complete"=== | ===A note on the notion of "Turing complete"=== | ||
+ | |||
To be Turing complete, a computer has to have four things: a NAND, a NOR, a jump if, and infinite memory. | To be Turing complete, a computer has to have four things: a NAND, a NOR, a jump if, and infinite memory. | ||
Line 54: | Line 56: | ||
==Optimization: Memory Addressing Revisited== | ==Optimization: Memory Addressing Revisited== | ||
+ | |||
We spent a lot of time optimizing our adder, and ended up with a parallel add/look-ahead that was very fast-- less than half the time of our parallel ripple, and far faster than a full adder. What I forgot to mention is that there was a lot of stupid delay built into the add just by virtue of requiring two memory accesses (two XOR operations). We've been assuming that a single goblin will address all of our bits in a particular bit location, but that takes a lot of time: trip the hatch takes 100 ticks just to get him started, and with 32 bits to address, we're probably looking at something like 30 moves to make it to our addressable bit-- so we've got around 400 ticks just to read memory/buffer, followed by 100 ticks of latency for our memory. | We spent a lot of time optimizing our adder, and ended up with a parallel add/look-ahead that was very fast-- less than half the time of our parallel ripple, and far faster than a full adder. What I forgot to mention is that there was a lot of stupid delay built into the add just by virtue of requiring two memory accesses (two XOR operations). We've been assuming that a single goblin will address all of our bits in a particular bit location, but that takes a lot of time: trip the hatch takes 100 ticks just to get him started, and with 32 bits to address, we're probably looking at something like 30 moves to make it to our addressable bit-- so we've got around 400 ticks just to read memory/buffer, followed by 100 ticks of latency for our memory. | ||
Line 85: | Line 88: | ||
We've replaced our begin hatch with a begin door. When it gets tripped, the goblin begins operations. That lowers latency, so long as we can guarantee that reset path doesn't become available before that door closes. He returns r/w t/f or null via the top NAND then returns to reset. Longest time to completion: 12/4, 176 ticks, followed by another 100 ticks from memory latency. Time to reset isn't important-- it can happen simultaneous with other operations. | We've replaced our begin hatch with a begin door. When it gets tripped, the goblin begins operations. That lowers latency, so long as we can guarantee that reset path doesn't become available before that door closes. He returns r/w t/f or null via the top NAND then returns to reset. Longest time to completion: 12/4, 176 ticks, followed by another 100 ticks from memory latency. Time to reset isn't important-- it can happen simultaneous with other operations. | ||
− | + | I could make it smaller, and thus faster, by using z-levels, but I don't want to do that. There is a lot to be said for keeping your design understandable. By the time I'm done, even I won't understand what I'm saying or what I've done. | |
− | |||
− | |||
− | + | One memory cell needs 2 goblins, 52 doors/hatches, and 80 mechanisms, if I counted right. Entire memory space will thus require 64 goblins, 1664 doors/hatches, and 2560 mechanisms. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Our memory cell is large-- 19 wide, 22 tall. Sides are just walls. 8 of these, side by side, would take up 128 tiles. That means that to keep a nice looking computer, we need a 3-wide embark. A 2 square tall embark would give us enough room for 4 of these. We might just need that-- each byte needs to be separated from the other by 2 dead z-levels, remember (could get around that with offsets, but that requires visualizing everything at once). So we could fit our entire memory space inside 24 z-levels of one map. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | Our memory cell is large-- | ||
I'd rather keep it subterranean. I don't like the idea of a roc flying in and killing my memory. I guess I could get away with bridged pitting squares instead. | I'd rather keep it subterranean. I don't like the idea of a roc flying in and killing my memory. I guess I could get away with bridged pitting squares instead. | ||
− | Let's consider build order too. We want any linked hatches or doors to be nearby in the build queue-- so that we can find them with a minimum of keystrokes. In our case, we can't build address doors until we've built an address buffer, buffer T/F doors until we've built a buffer, the begin door | + | Let's consider build order too. We want any linked hatches or doors to be nearby in the build queue-- so that we can find them with a minimum of keystrokes. In our case, we can't build address doors until we've built an address buffer, buffer T/F doors until we've built a buffer, or the begin door until we've built a cycle manager, but everything else in this circuit just links to itself. |
− | + | ==Optimization: Memory Latency== | |
− | |||
So far, we've only been linking our operations to the true part of memory. We've been using FALSE and NOT TRUE interchangeably. But they're not quite interchangeable-- not really. Consider the following two circuits: | So far, we've only been linking our operations to the true part of memory. We've been using FALSE and NOT TRUE interchangeably. But they're not quite interchangeable-- not really. Consider the following two circuits: | ||
Line 142: | Line 116: | ||
Our memory has two different latencies and a refractory period. The latency to switch to TRUE is the time it takes a goblin to move from FALSE to TRUE-- about 33 ticks. The latency to switch to FALSE is the time it takes a goblin to move off of TRUE plus 100 ticks-- about 105 ticks. The refractory period is the time after a write to memory during which we cannot write to memory again-- usually, 110 ticks (time for the door to close from a delay 10 goblin running a trip plate). | Our memory has two different latencies and a refractory period. The latency to switch to TRUE is the time it takes a goblin to move from FALSE to TRUE-- about 33 ticks. The latency to switch to FALSE is the time it takes a goblin to move off of TRUE plus 100 ticks-- about 105 ticks. The refractory period is the time after a write to memory during which we cannot write to memory again-- usually, 110 ticks (time for the door to close from a delay 10 goblin running a trip plate). | ||
− | + | Usually, design that takes advantage of this disconnect between FALSE and NOT TRUE gets really byzantine: you need to combine ORs with NANDs in the same design, make twice as many arms, etc. Logic was never designed to differentiate FALSE from NOT TRUE. But we're still going to keep it in mind for future design. | |
− | + | ==Cycle Manager== | |
− | |||
Every cycle of our computer follows a certain flowchart. Let's spell it out. | Every cycle of our computer follows a certain flowchart. Let's spell it out. | ||
Line 169: | Line 142: | ||
I've added two other things. One is a lever operated door before reset. With this, we can permit operation or halt the system (very important if we accidentally program an endless loop!). I didn't design it very well, because it doesn't limit the goblin to a single tile, but it works. The other is a "back door" to our "execute instruction" part of the loop. This is important, because we need to get our values into memory to program the computer. We're going to do that via manually altering the instruction register and register a to write our program where we want it. We use our back door by opening the back door and closing, via hatch, normal progress along our cycle. Again, design was lazy and needs improvement. | I've added two other things. One is a lever operated door before reset. With this, we can permit operation or halt the system (very important if we accidentally program an endless loop!). I didn't design it very well, because it doesn't limit the goblin to a single tile, but it works. The other is a "back door" to our "execute instruction" part of the loop. This is important, because we need to get our values into memory to program the computer. We're going to do that via manually altering the instruction register and register a to write our program where we want it. We use our back door by opening the back door and closing, via hatch, normal progress along our cycle. Again, design was lazy and needs improvement. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |