I haven’t done anything interesting (of relevance) this weekend, so here’s something boring instead: ROM. This will store the program, so the more you can fit in the available space the more the computer can do.
This is the cleverest ROM design I’ve been able to come up with, but it might not be the smartest – I suspect a less compressed design may end up taking less space when you consider stacking and control interfaces. I need to build several layers of each type, with output busses, to test this.
Each 1 bit is represented by a torch, and each zero bit (none in the schematic) by the absence of a torch. When the select line is off, the torches are powered and thus zero.
Half the bits feed into a bus above the module, and the other half a bus below the module. Feeding both into a compact bus above the module is possible, but requires more space and introduces delays.
I tried to come up with a way to avoid the parallel select line and space, but failed.
This module can be tiled in two dimensions without any space between copies. Repeater banks are required every three modules in the east/west direction. In the north/south direction, the two output busses are uninterrupted between words, so it’s easy to interpret the ROM as 8-bit or 32-bit elements just by putting a different output bus muxer on the end.
Here’s an eight-word matrix with output bus: Schematic
The rows are selected by putting a torch under a negated section of each row bus to force it to zero when not selected. The rows are then fed into the (positive) bus using the same technique. Note that there are currently two levers for each row, one for the low half-bus and one for the high, and these levers are negated while the column select levers are positive.
This is the cleverest ROM design I’ve been able to come up with, but it might not be the smartest – I suspect a less compressed design may end up taking less space when you consider stacking and control interfaces. I need to build several layers of each type, with output busses, to test this.
Much more compact than anything I have been making:P I have been having horrible time visualizing it in 3d so everything I make is only been on a 2D field or only one or two levels up or below.
I will say this, have you notice how much it looks like an old PAL logic? Your basically having lines that can add together, then you ORr them at the mux. Thats going into my op logic:P
Bump. This is incredibly neat. I've been gathering plenty of redstone in my single player world and have thought about trying my hand at making a computer. If I do, I'll definitely use this as a guide, even if much of it is a bit (heh) over my head. Who knows, though, I might learn something. At any rate, do you plan to keep updating this?
Bump. This is incredibly neat. I've been gathering plenty of redstone in my single player world and have thought about trying my hand at making a computer. If I do, I'll definitely use this as a guide, even if much of it is a bit (heh) over my head. Who knows, though, I might learn something. At any rate, do you plan to keep updating this?
I’ll be releasing a save file later this week (now that theinternetftw has ). It’s much like the screen shot above, but with one of the ALU channels colour coded and signposted.
“Plan” is such a concrete term. I’ve started fiddling with the register file (based on howlingmonkey’s new D-latch) and I/O controller. If I finish that, I’ll post it.
Wow! This is an epic thread. I will be here a while just reading about all these concepts. I actually did buy The Elements of Computing Systems, but I am having trouble understanding it. Oh well.
Rollback Post to RevisionRollBack
"If rain brings winds of change then let it rain on us forever." -VNV Nation
I present, for your supremely geeky enjoyment, the ALU saved game.
Download
(The ALU is not well lit. I strongly recommend setting the game to peaceful before loading, and letting it run for several minutes before trying to do anything.)
In the middle is the ALU, essentially per the schematic above. However, I’ve aded some lights, walkways and signs, improved the interfaces (except the instruction input, because I got bored). The low-order ALU channel is colour-coded and signposted.
To the right in the picture is a prototype input interface with feedback lights. It’s too bulky to integrate easily, but lifting all the lines off the top of a minimum-width bus was fun.
To the left is an “exploded” ALU channel. It implements the same logic as the ones in the full ALU, but is divided into distinct gates. The individual gates are mostly different from the ones in the real ALU, but they interact in the same way. It’s also colour-coded in the same way as the low-order “real” channel.
Section 1: input filters
The first section consists of the two input filters, the X input filter (right in diagram, diamond on map) and the Y input filter (gold). The main gate in each input filter is an XNOR gate (here wiki type A). The X input filter compares the NX control bit – lower right side input in diagram – with (NOT X OR ZX). If both NX and ZX are zero, the output on the X side will be X. If NX is set, it will be NOT X. If ZX is set, it will be 0, and if both ZX and NX re set, it will be 1.
For simplicity, I’ll refer to the filtered outputs as X and Y below, but this is misleading if any of the NX/NY/ZX/ZY control bits are set.
Logic:
X′ = (¬X ⋁ ZX) ↔ NX
Y′ = (¬Y ⋁ ZY) ↔ NY
Section 2: core functions
The second section is a full adder (made out of clay on the map). It consists of two almost identical modules, which are called half-adders.
A half-adder takes two input bits, and produces a two-bit output ranging from 0 to 2. The possible combinations are:
X Y out
0 0 00
1 0 01
0 1 01
1 1 10
Note that the low bit of the output is equal to X XOR Y, and the high bit is X AND Y. The half-adder used here, which is identical to the second one in the “real” ALU, is similar to wiki XOR gate A, but rearranged so an internal NAND value can be pulled out (and inverted) on either side.
A half-adder is sufficient for a one-bit computer, but to add multiple bits we need to be able to take a carry input and add it to the sum. This is done with a second half-adder which takes the low bit of the first one as one input, and the incoming carry bit from the previous ALU channel as the other input. (This is called ripple-carry adding. There are faster approaches, but they take more space.)
The carry output is the OR of the two half-adders’ carry outputs. This value and the output of the second adder form a two-bit number which is the sum of the three inputs X, Y and Ci:
X Y Ci out
0 0 0 00
1 0 0 01
0 1 0 01
1 1 0 10
0 0 1 01
1 0 1 10
0 1 1 10
1 1 1 11
The ALU has two core functions, ADD and AND. The AND is acquired by a bridge (brick) from the second AND output of the first half-adder, along the right hand side of the diagram.
Logic:
S = X′ ⊻ Y′ ⊻ Ci
Co = (X′ ⋀ Y′) ⋁ ((X′ ⊻ Y′) ⋀ Ci)
A = X′ ⋀ Y′
Section 3: function muxer
The third section (obsidian) selects one of the two functions, based on the F control bit. If F is set, the ADD function is selected. Otherwise, the AND function is selected. In logic terms, that’s (F AND Oadd) OR ((NOT F) AND Oand), here implemented as two basic ANDs, a NOT and a bridge.
Logic:
O′ = (F ⋀ S) ⋁ (¬F ⋀ A)
Section 4: output filter
The output filter (iron) inverts the output if the NO control bit is set. It’s a single XNOR gate like the ones in the input filter. Since the input isn’t inverted in this case, the NO bit is instead. This is equivalent to using an XOR gate, but is a bit more compact in redstone.
Logic:
O = O′ ↔ ¬NO = O′ ⊻ NO
Section 5: load immediate muxer
This isn’t included in the exploded channel. On the real ALU, it’s identical to the F mux, but one step down and made out of mossy cobblestone.
Using the full ALU
The instruction format is exactly the same as for . However, mine doesn’t have any registers yet, so you’ll need to copy data from the output to the inputs. Since there’s no I/O, no clock is needed (beyond Minecraft’s update ticks); when the output bank stops changing, it’s finished calculating.
Now it's time to add some registers! I haven't found any designs or schematics for one so far, so if you could post that, I would be very grateful!
A register is just a bunch of D-latches chained together with a shared C input. Howlingmonkey’s 2-wide design with no padding needed would be my choice. (An Earle latch would be faster, but I don’t think register speed would be a major issue, and the larger size would induce latency anyway.)
The next bit is I/O control, which is fairly trivial for Hack: writes can go to any combination of register A, register D, and *A (controlled by the AND of each control bit with the AND of a clock signal and the high bit of the instruction word), the D register feeds straight into the X input of the ALU, and the Y input can be either A or *A (controlled by the A control bit).
Is it possible to apply pipelining to this, so the performance of multiple consecutive calculations can greatly be improved?
Probably not within the ALU itself. In a full CPU, you could probably use instruction prefetching (possibly with prediction of unconditional branches) and start issuing the next instruction slightly before the IO parts of the current one are processed, at least if there’s no memory read in the next instruction. Other obvious optimizations would be a one-word RAM cache, possibly with a second word of write buffer, and tight timing of the various dispatch stages. But in terms of actually being able to do anything, the main focus has to be keeping it small, so you can fit as much RAM as possible.
All high-level CPU optimizations, like pipelining, better algorithms and more powerful high-level instructions (like multiplication) are based on using more CPU die area to do stuff in smarter ways. Since Minecraft space isn’t subject to Moore’s law, we can’t really expect to see much of that sort of improvement in Minecraft computing, although if Notch adds SSI components (like one-block logic gates and latches) things could get interesting.
(Actually, there is one major space saving that can be done now: stacking the ALU and bus channels vertically. Avus, above, had the right idea, although the size of each channel eats up most of the optimization.)
I designed it myself and everything. I designed it so that you can stack 'plates' on top of each other to add bits.
This is an image of two bits stacked on top of each other.
I'm also not even the first one at my school to make one, but I guess that's what you get for taking straight gifted/enriched and AP courses at 14.
This is the cleverest ROM design I’ve been able to come up with, but it might not be the smartest – I suspect a less compressed design may end up taking less space when you consider stacking and control interfaces. I need to build several layers of each type, with output busses, to test this.
Schematic
Each 1 bit is represented by a torch, and each zero bit (none in the schematic) by the absence of a torch. When the select line is off, the torches are powered and thus zero.
Half the bits feed into a bus above the module, and the other half a bus below the module. Feeding both into a compact bus above the module is possible, but requires more space and introduces delays.
I tried to come up with a way to avoid the parallel select line and space, but failed.
This module can be tiled in two dimensions without any space between copies. Repeater banks are required every three modules in the east/west direction. In the north/south direction, the two output busses are uninterrupted between words, so it’s easy to interpret the ROM as 8-bit or 32-bit elements just by putting a different output bus muxer on the end.
Here’s an eight-word matrix with output bus:
Schematic
The rows are selected by putting a torch under a negated section of each row bus to force it to zero when not selected. The rows are then fed into the (positive) bus using the same technique. Note that there are currently two levers for each row, one for the low half-bus and one for the high, and these levers are negated while the column select levers are positive.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
-
View User Profile
-
View Posts
-
Send Message
Curse PremiumMuch more compact than anything I have been making:P I have been having horrible time visualizing it in 3d so everything I make is only been on a 2D field or only one or two levels up or below.
I will say this, have you notice how much it looks like an old PAL logic? Your basically having lines that can add together, then you ORr them at the mux. Thats going into my op logic:P
My new version of Redstone Simulator
Main Code Site: http://code.google.com/p/red-stone-simulator/
I’ll be releasing a save file later this week (now that theinternetftw has ). It’s much like the screen shot above, but with one of the ALU channels colour coded and signposted.
“Plan” is such a concrete term. I’ve started fiddling with the register file (based on howlingmonkey’s new D-latch) and I/O controller. If I finish that, I’ll post it.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Download
(The ALU is not well lit. I strongly recommend setting the game to peaceful before loading, and letting it run for several minutes before trying to do anything.)
In the middle is the ALU, essentially per the schematic above. However, I’ve aded some lights, walkways and signs, improved the interfaces (except the instruction input, because I got bored). The low-order ALU channel is colour-coded and signposted.
To the right in the picture is a prototype input interface with feedback lights. It’s too bulky to integrate easily, but lifting all the lines off the top of a minimum-width bus was fun.
To the left is an “exploded” ALU channel. It implements the same logic as the ones in the full ALU, but is divided into distinct gates. The individual gates are mostly different from the ones in the real ALU, but they interact in the same way. It’s also colour-coded in the same way as the low-order “real” channel.
Section 1: input filters
The first section consists of the two input filters, the X input filter (right in diagram, diamond on map) and the Y input filter (gold). The main gate in each input filter is an XNOR gate (here wiki type A). The X input filter compares the NX control bit – lower right side input in diagram – with (NOT X OR ZX). If both NX and ZX are zero, the output on the X side will be X. If NX is set, it will be NOT X. If ZX is set, it will be 0, and if both ZX and NX re set, it will be 1.
For simplicity, I’ll refer to the filtered outputs as X and Y below, but this is misleading if any of the NX/NY/ZX/ZY control bits are set.
Logic:
X′ = (¬X ⋁ ZX) ↔ NX
Y′ = (¬Y ⋁ ZY) ↔ NY
Section 2: core functions
The second section is a full adder (made out of clay on the map). It consists of two almost identical modules, which are called half-adders.
A half-adder takes two input bits, and produces a two-bit output ranging from 0 to 2. The possible combinations are:
Note that the low bit of the output is equal to X XOR Y, and the high bit is X AND Y. The half-adder used here, which is identical to the second one in the “real” ALU, is similar to wiki XOR gate A, but rearranged so an internal NAND value can be pulled out (and inverted) on either side.
A half-adder is sufficient for a one-bit computer, but to add multiple bits we need to be able to take a carry input and add it to the sum. This is done with a second half-adder which takes the low bit of the first one as one input, and the incoming carry bit from the previous ALU channel as the other input. (This is called ripple-carry adding. There are faster approaches, but they take more space.)
The carry output is the OR of the two half-adders’ carry outputs. This value and the output of the second adder form a two-bit number which is the sum of the three inputs X, Y and Ci:
The ALU has two core functions, ADD and AND. The AND is acquired by a bridge (brick) from the second AND output of the first half-adder, along the right hand side of the diagram.
Logic:
S = X′ ⊻ Y′ ⊻ Ci
Co = (X′ ⋀ Y′) ⋁ ((X′ ⊻ Y′) ⋀ Ci)
A = X′ ⋀ Y′
Section 3: function muxer
The third section (obsidian) selects one of the two functions, based on the F control bit. If F is set, the ADD function is selected. Otherwise, the AND function is selected. In logic terms, that’s (F AND Oadd) OR ((NOT F) AND Oand), here implemented as two basic ANDs, a NOT and a bridge.
Logic:
O′ = (F ⋀ S) ⋁ (¬F ⋀ A)
Section 4: output filter
The output filter (iron) inverts the output if the NO control bit is set. It’s a single XNOR gate like the ones in the input filter. Since the input isn’t inverted in this case, the NO bit is instead. This is equivalent to using an XOR gate, but is a bit more compact in redstone.
Logic:
O = O′ ↔ ¬NO = O′ ⊻ NO
Section 5: load immediate muxer
This isn’t included in the exploded channel. On the real ALU, it’s identical to the F mux, but one step down and made out of mossy cobblestone.
Using the full ALU
The instruction format is exactly the same as for . However, mine doesn’t have any registers yet, so you’ll need to copy data from the output to the inputs. Since there’s no I/O, no clock is needed (beyond Minecraft’s update ticks); when the output bank stops changing, it’s finished calculating.
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
A register is just a bunch of D-latches chained together with a shared C input. Howlingmonkey’s 2-wide design with no padding needed would be my choice. (An Earle latch would be faster, but I don’t think register speed would be a major issue, and the larger size would induce latency anyway.)
The next bit is I/O control, which is fairly trivial for Hack: writes can go to any combination of register A, register D, and *A (controlled by the AND of each control bit with the AND of a clock signal and the high bit of the instruction word), the D register feeds straight into the X input of the ALU, and the Y input can be either A or *A (controlled by the A control bit).
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE
Probably not within the ALU itself. In a full CPU, you could probably use instruction prefetching (possibly with prediction of unconditional branches) and start issuing the next instruction slightly before the IO parts of the current one are processed, at least if there’s no memory read in the next instruction. Other obvious optimizations would be a one-word RAM cache, possibly with a second word of write buffer, and tight timing of the various dispatch stages. But in terms of actually being able to do anything, the main focus has to be keeping it small, so you can fit as much RAM as possible.
All high-level CPU optimizations, like pipelining, better algorithms and more powerful high-level instructions (like multiplication) are based on using more CPU die area to do stuff in smarter ways. Since Minecraft space isn’t subject to Moore’s law, we can’t really expect to see much of that sort of improvement in Minecraft computing, although if Notch adds SSI components (like one-block logic gates and latches) things could get interesting.
(Actually, there is one major space saving that can be done now: stacking the ALU and bus channels vertically. Avus, above, had the right idea, although the size of each channel eats up most of the optimization.)
Imitating greatness: 16-bit Hack ALU design
KEEP CALM AND EAT CAKE