Waste Not, Want Not: Part 3
by, 01-19-2010 at 10:03 PM (3179 Views)
Waste Not, Want Not:
Resource Sharing for Thermofficiency!
- Part 3 -
Today is the last day of Waste Not, Want not and, of course, I've saved the very best until last, as today we look at Implied Logic.
Implied logic is a term I made up, mostly because I thought it was a cool name for a cool concept I'm not going to explicitly define it as it covers a very broad range of techniques and ideas - far more in fact than I can conver in a single blog, so I'm only going to look at a couple of common examples in depth. I'll touch upon some other ideas in the hope that you'll go away and play with them yourself.
The basic rationale behind implied logic is to simply avoid explicit construction of our individual logic functions. Typically, we would build an AND gate, or an OR gate, or whatever. Even in the previous installments we were still sort of building a couple of devices and then sharing resources between them. With implied logic, we can produce the functionality of a logic gate, without ever actually constructing any part of it.
And of course, if we don't construct it, the thermo doesn't know about it, and that allows us to feel smug
1. Generic Implied Logic
To begin with, I'm going to look at a generic method for implying logic systems, before we move onto some slightly more application-specific examples.
1.1. Basic Example
Our basic example is the following function:
R = ( A • B ) + ( C • D )
Please refer back to the Logical Notation Blog Entry if you are unsure of the symbols. Just to clarify this, I'll do you a circuit diagram:
Spoiler - geeknotes: On the Sum of Products
Note that in the example, we have 2 levels of gating. The two AND gates are the first level and the OR gate is the second level. This is important for implied logic - it's only possible to use these techniques when there are 2 or more levels of gating in your logic network. Generally, this is going to happen in larger logic systems anyway, which is when you really want to reduce your thermo usage.
If you remember back to the Logical Notation Blog Entry, you will recall that ANDs are considered equivalent to multiplication (product) and ORs are considered equivalent to addition (sum). We use the term sum of products to describe a situation where the ouput of several AND gates are ORed to give a result. The example above has just 2-input gates, but you can have any number of AND gates with any number of inputs each - it still comes under this heading. You can also add in inversion (NOT functions) before or after each gate as you see fit.
This turns up quite naturally in many types of logic and also has significance in from an electronics stand point as certain devices require this kind of set-up to work (not really relevant here, but it's true)
You can also directly extract a Sum of Products expression from a Truth Table. For example, take the XOR function, whose truth table is shown below:
Code:. a | b || XOR | -----|-----||-----| 0 | 0 || 0 | 0 | 1 || 1 | 1 | 0 || 1 | 1 | 1 || 0 | ------------------- .
Creating a sum of products from is simply a case of taking each rows that give a TRUE output (the second and third rows here) and creating an expression from that. We can say that the XOR output is TRUE if either of the following conditions are met
a is FALSE and b is TRUE (second row)
b is FALSE and a is TRUE (third row)
Taking that wordy explanation and condensing it down into something managable, we get:
xor = ( !a • b ) + ( a • !b )
You can also do the inverse, by looking at the rows that create a FALSE output, which is a bit more unweildy, but might come in useful at some point:
xor = ! [ ( a • b ) + ( !a • !b ) ]
Obviously for this example, it's not really achieving much, other than demonstrating the "many ways to skin a cat" adage. Sometimes it can be useful though, especially if your truth table is a little more complex and you are struggling to come up with a solution - this can give you a jumping point.
So, taking the example from above, we will naturally start with the two ANDs and build them the best way we know how. Note that in this device, the magnetic keys represent the outputs of the ANDs (P & Q):
Now add in an OR gate. We would typically use a winch-based OR, but I'm using a bit of a strange configuration as a teaching aid. This is a 2-piston OR where the pistons move outwards when their input is TRUE. The mag switch is inverted, with a radius such that the output is TRUE if either piston extends:
What you should notice is that movement of the two components of the OR directly match the movements of the two ANDs. This leads me on to proposing the following method for constructing the entire circuit:
I have essentially carried out the following steps:
- Set up the AND gates in such a way that their outputs mimic the movement of an OR gate.
- Remove the magnetic components from the AND gates.
- Place the magnetic components from the OR directly onto the AND gate.
- Delete what remains of the OR gate.
If you do a comparison between the two ANDs shown above (figure 1.1.2) and the final solution with 2 ANDs and an OR (figure 1.1.4), you should see that there are actually less components after we add the OR in. We have just made an OR gate that takes up negative thermo!
1.2. Intermediate Signals
Of course, this whole negative thermo thing does come with a slight drawback. If you refer back to the logic network diagram in figure 1.1.1, you will see the intermediate signals (P0 and Q) would normally be available to use in other parts of the logic. Using the configuration in figure 1.1.4 we save thermo, but lose the ability to obtain the intermediate signals. In some applications this will be fine, but often it will not. If we do need these signals, it's not too much effort to get hold of them again. The following is a simple method of obtaining the intermediates, by simply keeping the magnetic components of the individual AND gates (do not carry out step 2 above) along with the implied OR components:
Now, it is possible to create this using only one magnetic key, by playing around with connector distances and magnetic switch radii, but it's a nightmare getting it tweaked just right. I've included the image below as a demonstration of this but in all honesty, unless you are desperate for that tiny bit of thermo, it's not really worth the hassle. The picture below should indicate how such a configuration works, as you may find it useful to know.
Either way, even if we do add the intermediate signals back in, we have still saved a load of thermo across the board (objects and shapes, moving objects, collected objects, connectors) against actually building an OR gate, regardless of what type of OR gate you use. Win
2. Extending the Concept
Above I have used AND gates as the first level of gating and OR gates as the second level of gating. However, if we look at what properties allowed us to construct the implied logic device, we will find a whole host of logic systems that can use such techniques. Remembering that we need two levels of gating for this, we will look at each level in turn and work out what are the particular features that allow us to use this technique.
2.1. Candidates for First Level of Gating
Any logic gate that you can construct so that the magnetic key moves and the magnetic switch is static. This includes:
- Winch-Based ANDS
- Winch Based ORs
- Set Reset
- Some forms of toggle
- Wobble Bolt XOR (in some cases)
- Dissolve-Free Perm (from the Logic Pack)
- Other forms of perm (dissolve / emitter) can be used in very specific circumstances
And that's not an exhausive list, plenty of logic devices can be made in such a way and then used for implied logic.
2.2. Candidates for Second Level of Gating
Any logic system where one or more inputs are drive a moving part via a single directional piston. All you do is replace the piston and moving part with one of the first level gating devices, from 2.1. So, some examples of piston driven logic:
- Basic ANDs / ORs / XORs
- Some forms of Set Reset (see piggy in the middle from [url="http://www.mediamolecule.com/2009/04/15/lbp-tips-special-2-%E2%80%93-switches/"]Media Molecule's Switches Video[/color]
- Literally Hundreds of "custom" logic devices.
- 3-way switch controll using pistons to push, rather than winches to pull
- Shared input devices from the Waste Not, Want Not, Pt 2 Blog.
We are all familiar with piston-driven logic so you can probably imagine just how many potential examples there are for this one. In particular, note that all of last blog's shared input methods would count under this category, so we get even more thermo saving by combining implied logic with shared inputs.
2.3. Implied Logic / Shared Input Combination Example
You may wish to check back to the Shared Inputs Blog, section 4, for details of the shared inputs with inversion technique:
Take the following system:
p = (a + b) • (c + d)
q = (a + b) • !(c + d)
we could devlop it using 4 gates in the following manner (two winch-based ANDs and two winch-based ORs):
Or we could develop it as the two OR gates with an implied right-angled AND gate as shown below:
I haven't gone through this in much detail of course. I'm hoping that you can piece together the information from last week and this week to understand how the device in figure 2.3.2 works. If it's still not clear, try making it! Or just ask.
3. Set Reset Switches
As I stated above, the Set Reset switch is a prime candidate for the first level of gating using the method above (as it has a single moving part), but it also opens up some other, quite unique, possibilities for implied logic. The Set-Reset is one of my most used pieces of logic and quite often, I find myself wanting several triggers for either the set or reset inputs (normally the latter). In this case, the sensible solution is to add an OR gate. This would place the set-reset at the second level of gating, rather than the first, and it doesn't fir the criteria for standard second-level gating.
Say we have an OR gate with 3 signals, the output of which is to the reset. The behaviour turns out to be [i]“Reset when any of these signals is TRUE”[i]. Well in fact, we don’t need an external OR gate to achieve this, it's as simple as adding several winches to the reset side of the Set-Reset:
figure 3.0.2. OR-Activated Set Reset (Faulty)
Obviously you can do the same thing for Set instead of, or as well as, Reset. However, there are three distinct issues with this method.
3.1. Issue 1: It doesn't Work
OK, so that's actually quite a major issue, especially when you consider that by "doesn't work", what I mean is the bloody thing kerplodes around 50% of the time! I'm not entirely sure why, maybe something to do with having winches off-centre means that you will be exerting the force in such a way as to create rotation and you jar the glass against the dark matter. All I know is that it breaks.
So instead of keeping the moving part in place with a dark matter track, I prefer to use a stiff piston (nothing like a stiff piston to keep a wenches in check, eh boys? ), as shown below. A zero-strength stiff piston connected to dark matter keeps your motion in one dimension and prevents any twisting going on and the device becomes stable.
Spoiler - geekNotes: On Piston-Supported SRs
I actually do this with all my Set-Resets – it’s not 100% thermo friendly, and certainly isn't necessary for single input SRs, but I like it, it just feels tidier for some reason. I like the fact that a piston-supported Set-Reset seems so much more solid.
In addition, when you have a Set-Reset outputting a directional signal, you can also extend this so that the piston is at low strength (as opposed to 0-strength) and loop the output back to it. The positive feedback loop allows the piston to hold the key in place when the winches are not exerting any force (i.e. both inputs are FALSE). This makes the whole configuration far more stable in theory. Again, you don't actually need it if you are working with a dark-matter suported horizontal logic piece. However, it does give you the opportunity to mount the logic on a moving object, or configure it vertically if need be (I don't know why you would need this, but now you can), without worrying about the loose glass slipping out of place.
3.2. Issue 2: Prioritising Inputs
If you recall, with the normal version of the Set-Reset you can tweak the winch strengths to give priority to either Set or Reset, in case both are TRUE at the same time. You can also do this with the loopback to the piston as described in the geekNotes. However, once you add multiple winches into the equation then it starts becoming far less simple.
If you have multiple Resets with a single Set and you want Reset to take priority, then that’s easy – just drop the strength of Set to 5 and keep all the Resets at 10. If you want the Set to take priority it’s a bit harder (as you might have multiple resets active at once and the set is going to struggle to overpower them). Remember you can increase the max length of the Set signal, which will increase its speed and thus exert more force and you can also duplicate the Set signal winch to get extra strength. In some cases, knowledge of the signal sources will allow you to develop an application-specific prioritisation system. However, if you do have specific needs for the priorities it might be far, far simpler to just go with an external OR.
3.3. Issue 3: Intermediate Signals
Unlike the basic implied logic example above, this OR-activated Set-Reset does not allow the posibility to obtain the intermediate signals (the outputs from the OR gates). There isn't anything much that can be done about that I'm afraid. It just means you can only use it if the OR gate outputs are not needed elsewhere.
3.4. AND Activated Set-Resets
I mentioned earlier that you can also use the Piggy-In-The-Middle configuration of the set reset to allow it to be used at level 2 gating as per section 2.2. The Piggy-In-The-Middle
It’s not a great design and generally not something I’d use, but as with all things it does have its uses. The piston-driven parts extend when activated, as is the case with our winch-based AND switches, so if we have an AND activated Set Reset, we can just drop some winch-based ANDs (minus magnetic parts) into the piggy-in-the-middle device and it’s done. The AND gates will push the piggy when they activate (extend) and both levels of gating will be contained in one device.
Note that two AND gates pushing will make it simpler to prioritise the inputs, as the pushing strength relies completely on the piston strength.
3.5. Combining Techniques
Of course, we can mix this all up, have an AND on Set and an OR on Reset as shown below:
The winches on the magnetic key block are the actuators for the OR on Reset, and work exactly the same way as in section 3.1. The separate AND gate pushes the key into place to achieve the Set. This is a
bit of avery weird example, but it's just a demonstration of how different techniques can be combined.
Another thing to note is that all of these Set-Reset variants fit into the category of devices listed in section 2.1, because we still end up with a device that can be constructed with a moving magnetic key and a static magnetic switch. So this means that we can take any Set-Reset signal and add implied logic on the output as well as the input. So the Set-Reset, in the right circumstances, allows for three levels of gating compressed down into a single device. There are similar issues with intermediate signals as before, but I'll let you work your way around them as you get to them - I can't give you everything now can I
4. How About a cheeky Bonus?
So hopefully the evidence above has convinced you of that you can save a lot of thermo using these techniques. But what if I told you that you don't just save thermo using this. There is a rather nice little side effect of all this that should interest many of you. The implied logic techniques give us a reduction in latancy as well.
4.1. What is latency?
In very simple terms, latency (or propogation delay) is the time it takes for your logic's outputs to fully update after the inputs change. The thing is, when you have several levels of gating, each level has to update before the next one can update. The more levels of gating you have, the slower the updates to the final outputs.
In LBP terms the latency of your logic is (more or less) determined by the motion of components in your logic gates. One gate moves into position, then then its ouputs propogate to the next gate, which moves into position... etc. It doesn't take long, but it all adds up and slows down the decision making in your system. Latency in complex systems in LBP is often a major issue leading to poor response times.
Because the implied components of the logic above do not have any moving parts of their own, they don't actually take any time to propogate. All of the implied logic systems above, whether they are 2 levels of gating or 3, will update as fast as your normal, individual switches do. This can lead to a real improvement in the performance of your logic systems. And remember that although you may think latency is a minor issue, you are improving timings with no real pay off.
Spoiler - geekNotes: On the Deceptive Nature of LittleBigLatency
Our pistons and winches are generally set to a timing of 0.1s, which means they move from one extremity to the other in 0.05s. This would suggest that the latency for each of our switches is 0.05s, right? Well no, not exactly. The movement of the objects is only one contributing factor - we also have to take into account magnetic switch updating. I don't want to get into the nitty gritty details of latency here, but my testing suggests that winch and piston driven logic will switch on in 0.05s and switch off in 0.10s (or vice versa).
Technically, we consider latency to be the maximum time it takes for an update to happen, so for now, we will stick to 0.1s for each gate. In a couple of weeks I'll do a write up on latancy, explaining this weird imbalance of switching times and I'll present some concepts for speed tuning everything down to 0.05s in both directions.
So this wraps up implied logic, and also wraps up the thermo-saving guide, for now. The range of techniques discussed here are applicable to countless configurations of logic that you might need. Not all of the techniques are compatible with each other and sometimes you have to find a balance between where to use what. But regardless of what techniques you use, you will see a reduction of thermo vs using a network of individual switches, without any loss in functionality.
As I mentioned at the beginning, this is far from an exhaustive list and hopefully you'll come across some new techniques as you more forward. A few ideas that got left out (for you to ponder how to produce a implied version):
- A dissolve-free perm with an OR gate input
- A quick reset with an OR gate input
- A quick reset with a NAND input - gives a slow activating AND, very useful if you only want your AND to activate if the inputs are stable
Of course, the best way to optimise your thermo is to do a complete redesign from the ground up, from first principles. Design on the basis of piston movements and magnetic switch angles etc., rather than the more typical analogies with electronic circuitry. The problem there is that it's so much harder to do that, and half the time you end up dropping in ANDs and ORs and the like anyway, even if it's only as "supporting" logic, so you're still going to want to use the techniques here a lot of the time.
5.1. Next Week
Next week (it will actually be next week, though I don't know which day) I've decided to go ahead and do a worked example on using a large amount of the Waste Not, Want Not techniques to optimise a real logic network. Most of the examples I've used here have been completely abstract, and maybe seem a little contrived, so hopefully something a bit more practical will benefit some of you.