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) | ||
Line 26: | Line 28: | ||
*10001000-10011111 Reserved (24 choices!) | *10001000-10011111 Reserved (24 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 46: | ||
===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 58: | ||
==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 87: | Line 92: | ||
You might notice two problems. Before, we were using a goblin to tell us if memory r/w was complete. Then, he had eight doors to walk through. Now, to do the same thing, he'd need 256 doors to walk though. The sheer distance would negate any speed benefit by independently addressed memory. How can we work around that? | You might notice two problems. Before, we were using a goblin to tell us if memory r/w was complete. Then, he had eight doors to walk through. Now, to do the same thing, he'd need 256 doors to walk though. The sheer distance would negate any speed benefit by independently addressed memory. How can we work around that? | ||
− | The other problem is that this memory is 19 tiles wide. We can't fit 8 of these in a 3 square embark | + | The other problem is that this memory is 19 tiles wide. We can't fit 8 of these in a 3 square embark. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | ############# | |
+ | ## ## | ||
+ | ## ######d#### # | ||
+ | # ## h^hXh#d# Null completion (no r/w) | ||
+ | # #hhhhh#####^## R/W completion | ||
+ | # # ##h### | ||
+ | # # ########d ## | ||
+ | # # ddddddd^## # | ||
+ | ## # ########h# # | ||
+ | # ## ######Xh## # | ||
+ | #h#d ########d ## | ||
+ | ##^# ddddddd^## # Write true to buffer also opens hatch two tiles north to prevent escape | ||
+ | #h## ########h# # | ||
+ | #X## #######X## # | ||
+ | #h## ######h### # | ||
+ | #^## #######^## # | ||
+ | ##hd# ddddddd#d ## | ||
+ | #dh## ########## # | ||
+ | ##^## ddddddd#d ## | ||
+ | #h## #######^#### | ||
+ | #X###########hX# | ||
+ | ### #### | ||
+ | |||
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 at a glance. By the time I'm done, even I won't understand what I'm saying or what I've done. | 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 at a glance. 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, | + | One memory cell needs 2 goblins, 58 doors/hatches, and 96 mechanisms, if I counted right. Entire memory space will thus require 64 goblins, 1856 doors/hatches, and 3072 mechanisms. |
− | Our memory cell is large-- | + | Our memory cell is large-- 18 wide, 22 tall. Sides are just walls. 8 of these, side by side, would take up 137 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. |
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 of our reset or until we've built a cycle | + | 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 of our reset or continues until we've built a cycle manager, but everything else in this circuit just links to itself. |
What about the problem of knowing when r/w is complete? By separating our continues into r/w and null, we guarantee that each bit location will only return a single r/w signal (and 31 null signals). We can still tell, with just eight doors. But each door has to be linked to 32 different r/w completion points. | What about the problem of knowing when r/w is complete? By separating our continues into r/w and null, we guarantee that each bit location will only return a single r/w signal (and 31 null signals). We can still tell, with just eight doors. But each door has to be linked to 32 different r/w completion points. | ||
==Optimization: Memory Latency== | ==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 147: | Line 154: | ||
==Cycle Manager== | ==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 171: | Line 179: | ||
==Special Memory: Getting stuff done== | ==Special Memory: Getting stuff done== | ||
− | So far, our computer doesn't do anything. I mean, it can compute anything we throw at it, but it doesn't kill goblins or irrigate our farms or anything like that. What we need | + | |
+ | So far, our computer doesn't do anything. I mean, it can compute anything we throw at it, but it doesn't kill goblins or irrigate our farms or anything like that. What we need is a special byte: an output byte. | ||
===Output=== | ===Output=== | ||
+ | |||
Output bytes look like any other kind of byte (yeah, I'm going to stop showing you that same picture of a memory bit now.) The only difference is that the pressure plate in the memory is linked to more than just r/w functions-- it's linked to existing devices. For instance, a bridge could raise when the goblin moves into TRUE position and lower when the goblin moves off of TRUE position. | Output bytes look like any other kind of byte (yeah, I'm going to stop showing you that same picture of a memory bit now.) The only difference is that the pressure plate in the memory is linked to more than just r/w functions-- it's linked to existing devices. For instance, a bridge could raise when the goblin moves into TRUE position and lower when the goblin moves off of TRUE position. | ||
Line 205: | Line 215: | ||
jump if not b | jump if not b | ||
− | I told you-- we were going to do a lot more bit shifts than add | + | I told you-- we were going to do a lot more bit shifts than add with carries. |
+ | ===Input=== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Input's harder. At first, you wouldn't think so. Just link a lever to write to true, right? And another to write to false? | Input's harder. At first, you wouldn't think so. Just link a lever to write to true, right? And another to write to false? | ||
Line 266: | Line 225: | ||
What you have to do is prevent the goblin from reading (or writing) while any writing is going on. That means that every input device (levers, but pressure plates are better) has to prevent a r/w goblin from reading it until 100 ticks after writing to the input. | What you have to do is prevent the goblin from reading (or writing) while any writing is going on. That means that every input device (levers, but pressure plates are better) has to prevent a r/w goblin from reading it until 100 ticks after writing to the input. | ||
− | + | More to come. | |
− | === | + | ===Input/Output=== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
You might wonder how you can build a bridge that you can operate with a lever, but that still plays nice with your computer-- so that you can open it or close it, but your computer can too. This is input/output. Instead of linking your lever directly to the bridge, you link it to an input bit. Then, you treat that input bit as an output bit, and link it to your bridge. Now your computer can operate the bridge, you can operate the bridge, and your computer can even tell if you pulled the lever while it wasn't looking. | You might wonder how you can build a bridge that you can operate with a lever, but that still plays nice with your computer-- so that you can open it or close it, but your computer can too. This is input/output. Instead of linking your lever directly to the bridge, you link it to an input bit. Then, you treat that input bit as an output bit, and link it to your bridge. Now your computer can operate the bridge, you can operate the bridge, and your computer can even tell if you pulled the lever while it wasn't looking. | ||
− | The problem with this is that not only do you have to prevent the computer from reading | + | The problem with this is that not only do you have to prevent the computer from reading the bit while you're writing to it-- the computer also has to prevent you from writing to the bit until after it's done writing to it. Ideally, you'd maintain a sort of stack of actions that you could execute, so that even if you pulled the lever while the computer was writing, your lever pull would go through as soon as it could. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | More to come. | |
===Feedback: Memory multiplexing=== | ===Feedback: Memory multiplexing=== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | More to come. |