| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Massively Parallel Turing Machine (MPTM)
February 2004 (original design from 1996)
Full Document first created Maui, Spring 2005
Edited/Updated Tokyo and Maui, November 2005
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
The MPTM is a very simple machine built entirely of special memory, connecting logic and lasers/optics.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
In the above diagram, a group of memory 'cells' is shown. Each memory cell represents a place where a 'particle' can be stored as it 'moves' through 'space'. Note that the cells are all linked together logically. The logic between cells should be able to transfer data, and also should be able to operate on the data in a variety of simple ways (invert, increment, decrement, bitshift, AND, OR, etc).
As a result, the particles can travel along any path, altering the memory as they travel along. Multiple sets of particles can interact with each other, producing complex results from a simple architecture.
This diagram shows a single chip, with its laser optics. There are multiple paths connecting the 'cells' in memory with the laser optics, so any particle can also travel from chip-to-chip via laser optics. This makes the computer easily expandable; all connections are optical.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
WWWWWWWWWWWWWWXXXXWWWWWWWWWWWWWWWWWW W........ XX ........W W...... XXXXXXXXXXX <----------These X's form an empty W.... GGGGXX........X .....W box. This is the same W.... GGGGXX........X ....W as putting in power W.. GGGGXX........X ..W lines before houses... W GGGGXGGGGGGG XX........X W XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX<---Data transfer line XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX to get data in/out W GGGGGGGG XX GGGXGGGGGGXGGG W W XXWWWWWWWWWWW W W.. GGG XXWXgggggggXW ..W <--Note this 2nd-level W.... GGGGGGG XXWXgggggggXW ....W enclosure of a Wall. W.... GGGGGGG XXWWWWWWWWWWW ....W This 'ggg' Data can only W...... XX ......W be accessed by a W........ XX ........W higher-priveleged WWWWWWWWWWWWWWWXXXXWWWWWWWWWWWWWWWWW or superuser process.This is a 2D depiction of an n-dimensional virtual memory array, which provides neighbor-to-neighbor communications in most or all of its built-in dimensions. A 2D map is used for simplicity.
..also note along the horizontal pair of 'XXX' lines, most of the space is taken up (it has 'G's on it) Note though, that there must be a space made for data transit (the single 'X's that break up the GGGG strings) so that others can access data off in the corners of the walled area. Without making 'beach access' available to all, much of the walled-off areas would be useless to all but the earliest adopters.
For best results, the Data Wall should be made in a
rectangular shape. All processing which occurs inside
the Data Wall shall be trapped therein, and only fiber
i/o is supported to that area. This allows for multiple
processes on a single chip without any risk of cross-process
corruption (at least directly by particle motion).
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Output over time: (showing data AND control bits)
time 0 1 2 3 4 5 6 7 8 9.....
location 2 3 4 5 4 3 2 1 2 3
D0 0 1 1 1 1 0 0 0 0 1
D1 0 0 0 0 0 1 1 1 1 1
D2 0 0 0 0 0 0 0 0 0 0
D3 0 0 0 0 0 0 0 0 0 0
C0 0 0 0 1 1 1 1 0 0 0
C1 0 1 0 0 0 1 0 0 0 1
C2 1 0 1 0 1 0 1 0 1 0
C3 0 0 0 1 0 0 0 1 0 0
fiber output: 0 - 1 - 1 - 2 - 2 -
As you can see, the incremental value in D0-D3 comes out of
the fiber array (from two different fiber ports, at addresses
2 and 4).
This is a simple ramp wave generator. Data starts at address 2 (initial position), and gets transmitted; after that, it moves to the right and gets incremented. Each time it is changed, the Data is sent out a Fiber conduit, and the particle moves on to the next address. When the particle encounters the 'Reverse Direction' command, it changes from Left traversal to Right traversal (the 'Direction' bit gets inverted). Note with this design that the particle actually gets transmitted TWICE each time it gets incremented. This could be changed with a different algorithm, this one is shown for simplicity. There could be a special opcode which only increments left-travelling particles, and another which only outputs to fiber right-travelling particles. With these two new opcodes you could imagine a smaller program doing the same thing.
Just to be safe, there are Data Walls present at each end of the particle's path, to make sure that the processing stays put within this area of memory.
Also note that the control area is used bit-wise, i.e. one bit per control function. It could just as easily be used as a four-bit control value, resulting in 15 different opcodes (plus Data Wall).
As an alternatitive, if there are fewer fiber conduits (say every 3rd or 4th location), areas with fiber access can be made to auto-transmit their contents. If this is the case, the particles need to be forced to travel through the auto-transmit space.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Opcodes could be represented numerically instead of bit-wise, so 8 bits of control could represent 255 different opcodes (plus the Data Wall).
If 128 or 256 bits of memory is available, large floating-point numbers could be attached to particles, allowing for scientific applications like studying heat transfer, weather simulations, and protein-folding simulations.
If a larger problem arises, all that is needed is more MPTM chips added to the array, and the processing capability goes up linearly WITH the problem size.
It has not been proven, but this architecture may be able to handle NP-complete problems like the Travelling Salesman problem, and may be able to handle increasing complexity in a linear fashion, just by adding more MPTM chips based on problem size.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Also, it is possible that data could be sent in via the optical ports and corrupt space that already is being used by active particles; this should be watched for. Maybe a Data Wall that regulates the direction of flow in and out of memory may be needed at each fiber inlet/outlet to prevent unwanted particles from entering a certain area of space during execution.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Chip configuration must be performed by an external 'control computer', which is the same computer which is used primarily to load new programs into the MPTM and also to initiate processing and collect results. This control computer can be of any architecture, as long as it can send and receive the data appropriately.
It is probable, with larger and larger chips, that only designating a small subset of the chip as a "special" area (see below) will become more popular than dedicating the entire chip to one purpose. Some of these modes look like toggles which may go on and off during processing, while others look like more permanent settings. I recommend the permanent settings to be one bit each, if possible. The toggles should use the fastest architecture (parallel or muxed) to store their information.
Basic chip configuration:"special" chip modes
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
Basic memory considerations: There should be a temporary block of RAM for every 4-8 blocks of MPTM spatial RAM. The temporary block(s) get loaded via laser transfer from the external source(s), each of which can be asynchronous. When a suitable amount of data has been loaded for input/output, the transfer occurs.
In the early stages of fabrication, I recommend using visible laser source, red colors for input and blue colors for output, and maybe greens for chip-to-chip communications. This not only makes debugging a snap, but provides an excellent demonstration tool so people used to traditional computer architectures can more easily grasp the data and processing flow of the MPTM system.
Also note, the laser frequencies (local intra-chip ONLY) could be canned, based on the row/column/layer of each spatial memory location. Such a beam would have to be modified for chip-to-chip travel, so as not to get confused with either the destination chip's local traffic or some other 3rd chip's chip-to-chip traffic destined for the same chip. Solution: There needs to be an automated way to modify local chip-to-chip laser traffic's wavelength by shifting it based on its chip-to-chip destination.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |
--- = data wall
-f- = fiber inlet/outlet in data wall
or
|
f
|
010 = RGB frame data in memory, one bit deep
-f-f-f-f-f-f-f-f-f
| 1 1 1 1 0 0 0 0 |
f 1 1 1 1 0 0 0 0 f
| 1 1 1 1 0 0 0 0 |
f 1 1 1 1 0 0 0 0 f
| 0 0 0 0 1 1 1 1 |
f 0 0 0 0 1 1 1 1 f
| 0 0 0 0 1 1 1 1 |
f 0 0 0 0 1 1 1 1 f
-f-f-f-f-f-f-f-f-
This is basically a static storage area, new data gets
deposited and read via the fiber inlet/outlets
This example shows four-bits deep:
--- = data wall
-f- = fiber inlet/outlet
010 = stream of data in memory
-f-f-f-f-f-f----f-f-f-f-f-f-f----f-f-f-
... 1 0 1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0...
... 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1...
... 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0...
... 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1...
-f-f-f-f-f-f----f-f-f-f-f-f-f----f-f-f-
This represents four bits of streaming media (uncompressed),
and can just as easily be 32 bits, to encase a pixel stream.
It represents a video clip being streamed for consumption
over a remote network.
All a web server has to do is receive data from this stream
and pass it on. Each MPTM chip has a data MUX which can
stream out optical data from any or all of the fiber inlet/outlets
(optical ports) at the same time, so obtaining the data from memory
can be done in parallel by a large number of processes.
--- = data wall
-f- = fiber inlet/outlet in data wall
or
|
f
|
numbers = single particle's "temperature"
-f-f-f-f-f-f-f-f-f
| 0 0 0 0 0 0 0 0 |
f 0 2 3 4 3 2 0 0 f
| 0 3 5 6 5 3 0 0 |
f 0 4 6 7 6 4 0 0 f
| 0 3 5 6 5 3 0 0 |
f 0 2 3 4 3 2 0 0 f
| 0 0 0 0 0 0 0 0 |
f 0 0 0 0 0 0 0 0 f
-f-f-f-f-f-f-f-f-
This shows simple neighbor-to-neighbor heat transfer, with
the temperature represented as a 3 bit number. Each particle
is static, but transfers its data value to its neighbor with
attenuation. This type of application can handle complex
problems very rapidly; its only limitation is memory size.
Note that, since the 'neighbor' can be a remote chip or even a remote IP chip, this operation can be used by web servers to deliver data rapidly and in parallel.
ddd = data wall
-f- = fiber inlet/outlet in data wall
or
|
f
|
x x x ... = area to be copied
y y y ... = destination of copy
Source Chip Neighboring Chip
-f-f-f-f-f-f-f-f-f -f-f-f-f-f-f-f-f-f
| 0 0 0 0 0 0 0 0 | | 0 0 0 0 0 0 0 0 |
f 0 0 0 0 0 0 0 0 f---------f 0 0 0 0 0 0 0 0 f
| 0 x x x x 0 0 0 | | 0 0 0 0 0 0 0 0 |
f 0 x x x x 0 0 d f---------f y y y y 0 0 0 0 f
| 0 x x x x 0 0 d | | y y y y 0 0 0 0 |
f 0 x x x x 0 0 d f---------f y y y y 0 0 0 0 f
| 0 0 0 0 0 0 0 d | | y y y y 0 0 0 0 |
f 0 0 0 0 0 0 0 0 f---------f 0 0 0 0 0 0 0 0 f
-f-f-f-f-f-f-f-f- -f-f-f-f-f-f-f-f-
The fiber links between
chips allow neighboring chips to share data rapidly. If data is going
to a non-neighbor chip, then the data must be uploaded off-chip, and
goes to one of the surface laser propagators. The data is coded by
wavelength so it reaches the correct chip.
Data that goes from chip-to-chip (the three rightmost columns, in the above case) is either relayed using the chip-to-chip fiber links (shown as dashed lines above) or using the chip-mounted laser system to 'beam' the data to an adjoining (or remote, as the case may be) chip.
Note that if the neighbor has been remapped using a chip configuration control (see above), the data may go far away to a remote chip. Also, if the neighbor has been walled off for some reason (see Data Walls above) then this operation will fail.
dddddd = data wall
====== = laser conduit/fiber optics
-f-f-f = fiber inlet/outlet in data wall
or
|
f
|
x x x ... = area to be copied
y y y ... = destination of copy
Source Chip Neighboring Chip
-f-f-f-f-f-f-f-f-f -f-f-f-f-f-f-f-f-f
| 0 0 0 0 0 0 0 0 | | 0 0 0 0 0 0 0 0 |
f 0 0 0 0 0 0 0 0 f=========f 0 0 0 0 0 0 0 0 f
| 0 x x x x 0 0 0 | | 0 0 0 0 0 0 0 0 |
f 0 x x x x 0 0 d f=========f y y y y 0 0 0 0 f
| 0 x x x x 0 0 d | | y y y y 0 0 0 0 |
f 0 x x x x 0 0 d f=========f y y y y 0 0 0 0 f
| 0 0 0 0 0 0 0 d | | y y y y 0 0 0 0 |
f 0 0 0 0 0 0 0 0 f=========f 0 0 0 0 0 0 0 0 f
-f-f-f-f-f-f-f-f- -f-f-f-f-f-f-f-f-
In this case the x's just start to move to the right, when they get near
the destination they move down by one slot. The data space in between
the start and destination areas will be trashed as a result. However,
this move can be done quite fast, if it is less than the size of one chip,
and doesn't burden the offchip laser system at all (unless the neighbor
is a remote chip!)
Note that if the neighbor has been walled off for some reason (see Data Walls above) then this operation will fail.
This could be done using MPTM hardware "blocks" that may also suitable for standard computations,
and any general-purpose application could be run on it.
| (C) Copyright 1989-2010 fractallonomy, inc. all rights reserved. |