Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: [1] 2

Author Topic: Faster than lightspeed computing  (Read 8752 times)

itaibn

  • Bay Watcher
    • View Profile
Faster than lightspeed computing
« on: March 16, 2012, 12:53:26 pm »

So, we've all heard of the lightspeed computer:

http://www.bay12forums.com/smf/index.php?topic=92454.msg2586844#msg2586844

If anybody here is a Real Dwarf, they must have asked themselves: Is it possible to make this even faster? My answer is yes.

The lightspeed computer established that it is possible to make 1 calculation per tick. To make a faster computer it is necessary to make the calculations done in a tick more complicated. So the question becomes: How much calculation can be done in 1 tick? Well, I suspect it is possible to do unlimited calculation in 1 tick.

To understand this design it is important to understand something about how Dwarf Fortress works. When a several pieces of machinery are operating simultaneously, the one designated later operate earlier.  The ones operating earlier can affect the ones operating later. This is all within a single tick.

Anyways, my design is based on storing information in water. If a location has 7/7 water, it is a 1, and if it has 0/0 water, it is 0. It is possible to move this information around with the help of carefully designated pumps. This is the main logic gate:

Code: [Select]
   #
i%%AB
   %
   %
   i

i channel with input
A OR output
B AND output
# wall
% screw pump

It works as follows: First the input bits (stored under the channel) are prepared. Then the two pumps operate. If either of the two bits is a 1, the water would get pumped onto the floor closer to the two pumps. That floor tile stores the OR of the two inputs. If both of the input bits are 1, then water will first be pumped onto the closer floor, and then pressure will push another tile of water onto the the farther floor. The farther floor stores in its tile the AND of these two bits.

This AND/OR gate has been tested by me.

Unfortunately, this AND/OR gate destroys its inputs. I don't know any way to perform arbitrary computation with this gate alone. However, there might be some complicated way of doing so which I'm not aware of. UPGRADE: I asked about this in the theoretical computer science stack exchange: http://cstheory.stackexchange.com/questions/10837/are-andor-circuits-p-complete. Apparently it is not known weather arbitrary calculations are possible with this gate. However, a wide variety of calculations are possible, including calculating sums and products.

Luckily, there's a way to duplicate input. This method hasn't been tested yet.

Code: [Select]
LEVEL 2

WWW
% W
% W
_ W




LEVEL 1

_ oo
% %%
%#%%
_WWW ...
%#%%
% %%
_ oo

LEVEL 0

i


~


m

% Screw pump
_ Channel
i Channel with input
m Magma
W Water
o Channel with water, then with output
~ Magma flow

On the bottom floor, the north channel has the input bit, the south channel has magma, and to the right is a resevoir. There are many pumps which pump water into the resevoir. First the pump on level 2 pumps any water that spills into the middle channel back into the resevoir. Then, the input water and the magma are pumped into the middle. If the input bit is 1, this makes an obsidian wall. Now, all of the resevoir pumps are pumped. If an obsidian wall was created, the pumps will not work and the and the channels on the right will have water in them. If it isn't created, then all of the pumps will work, leaving those channels empty. Now the output those channels. At the end of the tick, the obsidian wall will fall onto the magma flow. This is a fanout/not gate. Note that the magma flow doesn't have to be right below the rest of the structure. This design might not work if the obsidian wall caves in as soon as it is created.

So there you have it, unlimited computation in 1 tick.
« Last Edit: March 25, 2012, 01:27:57 pm by itaibn »
Logged
insert witty quote here.

Girlinhat

  • Bay Watcher
  • [PREFSTRING:large ears]
    • View Profile
Re: Faster than lightspeed computing
« Reply #1 on: March 16, 2012, 12:57:42 pm »

Needs better diagrams.  I can't properly identify what you're explaining.

itaibn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #2 on: March 16, 2012, 01:19:57 pm »

Needs better diagrams.  I can't properly identify what you're explaining.
Is this better?
Logged
insert witty quote here.

Sphalerite

  • Bay Watcher
    • View Profile
    • Drew's Robots and stuff
Re: Faster than lightspeed computing
« Reply #3 on: March 16, 2012, 01:27:48 pm »

The limiting factor in speed for any calculation that takes more than one step to work is still going to be the unavoidable delay from the pressure plates.  Pressure plates trigger instantly, but they have a minimum 100 tick on time before they switch off again, which means that any computing system that takes multiple steps is still going to take at least 100 ticks per calculation step to run.
Logged
Any intelligent fool can make things bigger and more complex... It takes a touch of genius --- and a lot of courage to move in the opposite direction.

khearn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #4 on: March 16, 2012, 01:47:08 pm »

The fanout has a minor problem in that once the input is a 1, the gate is clogged by obsidian and can't be used again until you designate the obsidian to be mined out and a miner comes and does it. So I guess this is intended as a one-shot computer.
Logged
Have them killed. Nothing solves a problem quite as effectively as simply having it killed.

itaibn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #5 on: March 16, 2012, 02:00:11 pm »

The limiting factor in speed for any calculation that takes more than one step to work is still going to be the unavoidable delay from the pressure plates.  Pressure plates trigger instantly, but they have a minimum 100 tick on time before they switch off again, which means that any computing system that takes multiple steps is still going to take at least 100 ticks per calculation step to run.
My system doesn't use pressure plates. That said, pressure plates are important for sending output, and it is possible using them quickly by having 100 pressure plates for every output, and routing the signal to the appropriate pressure plate while the others switch off.
Logged
insert witty quote here.

Sphalerite

  • Bay Watcher
    • View Profile
    • Drew's Robots and stuff
Re: Faster than lightspeed computing
« Reply #6 on: March 16, 2012, 02:54:01 pm »

My system doesn't use pressure plates.

Then what is the point of it?  Presumably the purpose of a computing system is to trigger some output or perform some action depending on the outcome of the calculation.  If all your computing system does is instantly fill a chamber with water when a condition is met, and the only result is that you the player can see if there is water or not, then I really don't see the use.
Logged
Any intelligent fool can make things bigger and more complex... It takes a touch of genius --- and a lot of courage to move in the opposite direction.

itaibn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #7 on: March 16, 2012, 03:22:20 pm »

While the computer itself doesn't use pressure plates, it is possible to attach it to pressure plates which will do something more !!FUN!!.
Logged
insert witty quote here.

Nil Eyeglazed

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #8 on: March 16, 2012, 03:40:53 pm »

I see what you're saying.  In fact, I've developed a theory of build order lately (needs a bit of verification) and have been thinking about some similar things.

You can design 1 tick gates like this that restore their values.  What you do is have over-under screw pumps, paying careful attention to build order.

Here's a 1 tick identity gate.

Code: [Select]

 # %%     pumpA, right-to-left
 # %%^#   pumpB, left-to-right
 # ####
 ###

Both pumps are powered.  Where the water ends up, and whether the ^ gets activated, is determined by build order.  Each component is evaluated in sequence, such that the the most recently built is evaluated first.  What happens if you build first pumpA, second ^, third pumpB?  In a single tick, water goes to the right chamber, the pressure plate notices the water, and water returns to the left chamber.  (Build in a different order, different stuff happens.)

You can use this to evaluate your OR while returning your value.  When building it in to more complicated circuits, you have to be very, very careful about build order-- pumpA needs to be built before, and pumpB after, any further logic working on this operation.

Realistically, it's not 1-tick computing.  Hussell, who I consider one of the gods of DF logic, says that pumps remain active for 50 ticks after unpowering.  Plus, I can't imagine a useful latch that doesn't rely on off signals from pressure plates.

When I was doing some computing research, what I found is that there are two large bottlenecks with DF computers: adding, and memory access.  Adding is tough, because a look-ahead carry requires some complicated logic to do it right, but a ripple-carry can take days for a long number.  Memory access (read, write, addressing) is a huge bottleneck because it happens so often-- even a bitshift means two reads and two writes.  If you can design 1-tick accessible memory or a 1-tick XOR, you can speed these processes up considerably.

My system doesn't use pressure plates.

Then what is the point of it?  Presumably the purpose of a computing system is to trigger some output or perform some action depending on the outcome of the calculation.  If all your computing system does is instantly fill a chamber with water when a condition is met, and the only result is that you the player can see if there is water or not, then I really don't see the use.

I hope what I said earlier sheds some light on this-- computing involves a lot of internal processes before it comes to output.  The load-based logic gates on the mechanical logic page don't involve pressure plates either-- they're for internal processing.  In the case of something like a ripple-carry adder, an implementation that avoids pressure plates until output can mean the difference between adding in, say, 9 ticks, and 900 ticks.
Logged
He he he.  Yeah, it almost looks done...  alas...  those who are in your teens, hold on until your twenties...  those in your twenties, your thirties...  others, cling to life as you are able...<P>It should be pretty fun though.

Nil Eyeglazed

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #9 on: March 16, 2012, 05:17:51 pm »

On further thought:

If you can get this to work, you can complete a ripple-carry half-add of any length in a single tick.

The problem is with the AND gate.  It doesn't really work in a single tick.  Water flows at a time separate from other buildings-- that is, either before or after pumping (I think after).  So it really takes a tick for the water to teleport down into the channel-- while water exists in the AND channel in your diagram at the end of the first tick, there is no way to evaluate for the presence of that water in the same tick, you have to wait for the next tick.  (To verify this, build a pressure plate in your AND channel, and link it to a door someplace.  I predict that the door won't actually open until 1 tick after evaluation of the AND.)

This difficulty makes it impossible to make a zero-tick AND, NAND, or XOR.  Single tick computing would require that all gates work at zero-tick rate, unless you want to clock it somehow, which requires pressure plates, which slow it down to traditional speeds.  However, I'm not certain that a zero-tick AND is necessarily impossible.

Since you have this design built, I would be really interested in the position of the AND channel after a single tick.  If two TRUEs fill the AND channel in a single tick, that means water flows after buildings.  If two TRUEs instead fill the tile above the OR, then water flows before buildings.
Logged
He he he.  Yeah, it almost looks done...  alas...  those who are in your teens, hold on until your twenties...  those in your twenties, your thirties...  others, cling to life as you are able...<P>It should be pretty fun though.

flieroflight

  • Bay Watcher
  • Worship the nightmare
    • View Profile
Re: Faster than lightspeed computing
« Reply #10 on: March 16, 2012, 05:20:19 pm »

Is it wrong that i thought that a ftl computer had been developed and you were tallking about running df on it?
Logged
Bay12 doesn't have moral event horizons, it has goals.

Kofthefens

  • Bay Watcher
  • Keep calm and OH GOD CAPYBARAS
    • View Profile
    • Marshland Games
Re: Faster than lightspeed computing
« Reply #11 on: March 16, 2012, 06:34:44 pm »

From what I understand of it, it seems awesome, but needs more testing PTW
Logged
I don't care about your indigestion-- How are you is a greeting, not a question.

The epic of Îton Sákrith
The Chronicles of HammerBlaze
My website - Free games

itaibn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #12 on: March 16, 2012, 07:28:02 pm »

Realistically, it's not 1-tick computing.  Hussell, who I consider one of the gods of DF logic, says that pumps remain active for 50 ticks after unpowering.  Plus, I can't imagine a useful latch that doesn't rely on off signals from pressure plates.
The pumps don't need to unactivate. They just move around the water, and it is what is doing the computation.

The problem is with the AND gate.  It doesn't really work in a single tick.  Water flows at a time separate from other buildings-- that is, either before or after pumping (I think after).  So it really takes a tick for the water to teleport down into the channel-- while water exists in the AND channel in your diagram at the end of the first tick, there is no way to evaluate for the presence of that water in the same tick, you have to wait for the next tick.  (To verify this, build a pressure plate in your AND channel, and link it to a door someplace.  I predict that the door won't actually open until 1 tick after evaluation of the AND.)

What's bringing the water to the AND output isn't flow. It's pump pressure. While I haven't done the experiment you described, this is the experiment that I have done:
Code: [Select]
LEVEL 2

o%%__%%o



LEVEL 1
   #
_%%..
   %
   %
   _
LEVEL 0

i


   i

# wall
% screw pump
. floor
i floor with input
o floor with output

I built this so that I can control weather or not the i's have water in them. All of the screw pumps are controlled by a single gear. The ones below were designated after the ones above. When I activate the gear, all of the water goes from the input to the output in 1 tick. This means that when both of the input tiles have water, the water got onto the AND tile before it got pumped by the upper pump.

By the way, I was thinking: Is it possible to make a delay line memory with axles? That is, make a long line of axles so that each tick an axle gains its power state from the one behind it. If so, it would make a very compact memory.
Logged
insert witty quote here.

Nil Eyeglazed

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #13 on: March 16, 2012, 08:25:29 pm »

The pumps don't need to unactivate. They just move around the water, and it is what is doing the computation.
You're right.  I wasn't thinking it through clearly.

Quote
What's bringing the water to the AND output isn't flow. It's pump pressure.
Again, you're right.

Quote
By the way, I was thinking: Is it possible to make a delay line memory with axles? That is, make a long line of axles so that each tick an axle gains its power state from the one behind it. If so, it would make a very compact memory.
I'm doing some research into this right now.  I don't believe you can make delay with axles, but I believe you can with gear assemblies.  However, if my theory is correct, you can only make 1 tick of delay out of gear assemblies, no matter how many you string together.  You can string together pressure plates in this manner, such that they activate a pump on the next tick, which activates a pressure plate that activates a pump on the next next tick, and you can get 2 ticks out of each plate instead of 1 if you want, but of course you have the problem of plate deactivation, which always takes at least 99 ticks.

I admit that I don't understand exactly what your compact, fast memory would be like, so I can't say whether plate deactivation time would be a problem or not.

Finally, I was incorrect when I said that using build order, you could restore values.  You can restore values with an identity, or a NOT, but with something like an OR, the system would be unable to decide to which cell to return the water.  You could get around this by using traditional latches to seed your fast latches, and clocking it at something like 100 ticks.  That way, you'd still be doing 1-tick computation, but you wouldn't be able to compute another value until a 100 ticks later.  It's still cool, because infinite computing in finite time is pretty cool.

I think another problem is with using the same latch in multiple ways during a computation.  For instance, with a standard adder, you both have to XOR values and AND values-- the XOR becomes an interim value, to which you then XOR the AND of the next less significant bits.  I can't see a way to have access to both the AND and the XOR at the same time.  Actually, this is probably surmountable, by adding from most significant digit to least significant digit, using a three-way gate-- carry c iff 2 of a, b, and c, where c is determined recursively.  I've done something similar with creature logic.  Alternatively, you could use redundant latches, such that you could use a value in more than one way during a single computation.

If somebody's capable of designing something like that, I believe that calling it "quantum computation" would be totally appropriate.  It fits with the traditional overblown nomenclature associated with DF, and I think it captures the fact that you're simultaneously treating a value as both 0 and 1, at different times during the tick.  It also reflects the different style of design that has to be used with such a device.
Logged
He he he.  Yeah, it almost looks done...  alas...  those who are in your teens, hold on until your twenties...  those in your twenties, your thirties...  others, cling to life as you are able...<P>It should be pretty fun though.

itaibn

  • Bay Watcher
    • View Profile
Re: Faster than lightspeed computing
« Reply #14 on: March 17, 2012, 01:54:45 pm »

I improved the design my fanout gate. This new gate can do more fanout and is reusable (addressing khearn's critisism). For refrence, this is my earlier design:
Quote
Code: [Select]
   i
   %
   %
o%%_%%o
   %
   %
   m

% Screw pump
_ Channel
i Channel with input
m Magma
o Channel with water, then with output

Here, the top channel has the input bit, the bottom channel has magma, and the left and right channels have water. First the input water and the magma are pumped into the middle. If the input bit is 1, this makes an obsidian wall. Now, the left and right pumps are pumped. If an obsidian wall was created, the pumps will not work and the left and right channels will have water in them. If it isn't created, then both of the pumps will work, leaving those channels and empty. Now the output is in the left and right channels. This is a fanout/not gate.
Logged
insert witty quote here.
Pages: [1] 2