Self-reconfigurable parallel processor made from regularly-connected self-dual code/data processing cells

• US 5,886,537 A
• Filed: 05/05/1997
• Issued: 03/23/1999
• Est. Priority Date: 05/05/1997
• Status: Expired due to Term

• Current Assignee: Nicholas J. Macias
• Original Assignee: Nicholas J. Macias
• Inventors: Macias, Nicholas J., Henry, Lawrence B. III, Raju, Murali Dandu
• Primary Examiner(s): Santamauro, Jon
• Assistant Examiner(s): Chang, Daniel D.
• Application Number:
  US08/850,472
• Time in Patent Office: 687 Days
• Field of Search: 326/38, 326/39, 326/40, 326/41
• US Class Current: 326/40
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture

Abstract

A parallel processing system composed of a regular array of programmable logic devices, each of which can be configured to perform any logical mapping from inputs to outputs. The configuration of each device is specified by a small program memory contained inside each device. Any device'"'"'s program memory can be read or written by any other device connected to it within the array. This facilitates the development of extremely parallel systems whose configuration can be modified at runtime, while distributing control of the array throughout the entire array itself. The resulting system is thus completely self-reconfigurable, avoiding the bottlenecks and critical failure points found in inherently externally-configured systems.

Claims

1. A programmable logic device comprising:

(a) a first plurality of input channels,

(b) a means of computing the value of a binary state variable from said first plurality of input channels,

(c) an internal storage memory accessible as either a serial read serial write shift register or as a parallel read random access memory, depending on the value of said binary state variable,

(d) a second plurality of input channels which correspond one to one with said first plurality of input channels,

(e) a means of combining said first plurality of input channels and said second plurality of input channels to specify serial input data for said shift register,

(f) a means of addressing said random access memory using said second plurality of input channels,

(g) a plurality of output channels, each of which correspond to either one of said first plurality of input channels or one of said second plurality of input channels,

(h) a means of setting the values of said plurality of output channels by combining said first plurality of input channels with either the serial output or parallel outputs of said internal storage memory, depending on the value of said binary state variable, and

(i) a means of shifting said shift register'"'"'s contents based on the value of said binary state variable and an externally applied dock,

whereby said programmable logic device can map inputs to output via said internal storage memory, or can present the contents of said memory to certain of its outputs and can load the contents of said memory from certain of its inputs.

2. The programmable logic device of claim 1, where said binary state variable is computed by logically ORing said first plurality of input channels.

3. The programmable logic device of claim 1, where said serial input data is computed by logically ORing each of said first plurality of input channels with each of said second plurality of input channels, and then logically ORing the resulting values, whereby said serial input data may be set high by setting any of said first plurality of input channels high, and also setting the corresponding channel from said second plurality of input channels high.

4. The programmable logic device of claim 1, where said internal storage memory is a shift register organized into rows and columns, such that

(a) the number of rows is equal to 2^N, N being the number of input channels in said second plurality of input channels,

(b) the number of columns is equal to 2^M, M being the number of output channels in said plurality of output channels,

(c) a single row is selected using said second plurality of input channels as a row address,

(d) the corresponding column values in said row are presented to said plurality of output channels when said binary state variable is low,

(e) each output channel corresponding to said first plurality of input channels is driven low when said binary state variable is high,

(f) each output channel corresponding to each input channel of said second plurality of input channels is set to the output value of said shift register if the input channel from said first plurality of input channels which corresponds to said input channel of said second plurality of input channels is high and said binary state variable is also high, and

(g) each output channel corresponding to each input channel of said second plurality of input channels is driven low if the input channel from said first plurality of input channels which corresponds to said input channel of said second plurality of input channels is low and said binary state variable is high,

whereby said internal storage memory functions as a truth table for mapping said second plurality of input channels to said plurality of output channels when said binary state variable is low, and said internal storage memory functions as a shift register whose single output value is sent to certain of said plurality of output channels depending on the values of said first plurality of input channels.

5. The programmable logic device of claim 1, where said internal storage memory functions as a shift register, shifting one bit each time an external clock makes a certain transition and the value of said binary state variable is high.

6. The programmable logic device of claim 1, where said internal storage memory includes a preset line, whereby each bit in said internal storage memory may be initialized to a predetermined value by application of a single preset signal.

7. A collection of programmable devices, each connected to a set of identical neighboring programmable devices according to a predetermined notion of neighborhood and a predetermined interconnection scheme, where each said programmable device comprises:

(a) a first plurality of input channels,

(b) a means of computing the value of a binary state variable from said first plurality of input channels,

(c) an internal storage memory accessible as either a serial read serial write shift register or as a parallel read random access memory, depending on the value of said binary state variable,

(d) a second plurality of input channels which correspond one to one with said first plurality of input channels,

(e) a means of combining said first plurality of input channels and said second plurality of input channels to specify serial input data for said shift register,

(f) a means of addressing said random access memory using said second plurality of input channels,

(g) a plurality of output channels, each of which correspond to either one of said first plurality of input channels or one of said second plurality of input channels,

(h) a means of setting the values of said plurality of output channels by combining said first plurality of input channels with either the serial output or parallel outputs of said internal storage memory, depending on the value of said binary state variable, and

(i) a means of shifting said shift register'"'"'s contents based on the value of said binary state variable and an externally applied dock.

8. The collection of programmable devices of claim 7, where

(a) the number of said neighboring programmable devices is the same as the number of input channels in said first plurality of input channels,

(b) the number of channels in said second plurality of input channels is the same as the number of channels in said first plurality of input channels,

(c) the number of channels in said plurality of output channels is twice the number of channels in said first plurality of input channels,

(d) the interconnection among said programmable devices is such that, for any two neighboring devices,

i) a channel from said first plurality of input channels of one device is connected to a channel from said plurality of output channels of the other device,

ii) a channel from said second plurality of input channels of one device is connected to a channel from said plurality of output channels of the other device,

iii) one channel from said plurality of output channels of one device is connected to a channel from said first plurality of input channels of the other device,

iv) one channel from said plurality of output channels of one device is connected to a channel from said second plurality of input channels of the other device,

whereby each said programmable device has its inputs connected to the outputs of other programmable devices, and its outputs connected to the inputs of other programmable devices.

9. The collection of programmable devices of claim 8, where certain of said programmable devices are connected to fewer neighboring programmable devices than others, whereby the corresponding unconnected input and output channels may be accessed by external devices.

10. The collection of programmable devices of claim 7, where a common dock signal is propagated to a plurality of said programmable devices, whereby multiple devices may be clocked simultaneously by application of a single dock.

11. The collection of programmable devices of claim 7, where a common preset signal is propagated to a plurality of said programmable devices, whereby multiple devices may each be set to its predetermined initial state by application of a single preset signal.

12. A configuration of two programmable devices, called a replicator and a source, each comprising:

(a) a first plurality of input channels,

(b) a means of computing the value of a binary state variable from said first plurality of input channels,

(c) an internal storage memory accessible as either a serial read serial write shift register or as a parallel read random access memory, depending on the value of said binary state variable,

(d) a second plurality of input channels which correspond one to one with said first plurality of input channels,

(e) a means of combining said first plurality of input channels and said second plurality of input channels to specify serial input data for said shift register,

(f) a means of addressing said random access memory using said second plurality of input channels,

(g) a plurality of output channels, each of which correspond to either one of said first plurality of input channels or one of said second plurality of input channels,

(h) a means of setting the values of said plurality of output channels by combining said first plurality of input channels with either the serial output or parallel outputs of said internal storage memory, depending on the value of said binary state variable, and

(i) a means of shifting said shift register'"'"'s contents based on the value of said binary state variable and an externally applied clock,

with certain of the inputs of the replicator connected to certain of the outputs of the source, and certain of the outputs of the replicator connected to certain of the inputs of the source, such that;

(j) the replicator can, under certain conditions, assert one of the source'"'"'s said first plurality of input channels, to cause the source'"'"'s internal storage memory to act as a shift register,

(k) the output of the source'"'"'s internal storage memory is passed to one of the replicator'"'"'s said second plurality of input channels,

(l) the replicator'"'"'s internal storage memory is preconfigured such that the data entering said one of the replicator'"'"'s said second plurality of input channels is transferred to one or more of the replicator'"'"'s output channels under certain combinations of inputs on the replicator'"'"'s other inputs,

whereby the contents of the source'"'"'s internal storage memory is presented on one or more of the replicator'"'"'s outputs, one bit at a time, in synchronization with the clock input to the source.

13. The configuration of programmable devices of claim 12, where the bits of the source'"'"'s internal storage memory are additionally output to the replicator'"'"'s output which is connected to one of the source'"'"'s said second plurality of inputs, whereby the internal storage memory of the source is recirculated and thereby periodically restored to its initial condition.

14. The configuration of programmable devices of claim 12, where the source is connected to a third programmable device, called the target, such that:

(a) the replicator can, under certain conditions, assert one of the target'"'"'s first plurality of input channels, to cause the target'"'"'s internal storage memory to act as a shift register,

(b) the output of the replicator which reflects the source'"'"'s internal storage memory'"'"'s contents is presented to one of the target'"'"'s second plurality of inputs channels,

whereby the contents of the source'"'"'s internal storage memory is copied into the target'"'"'s internal storage memory.

15. The configuration of programmable devices of claim 14, where the bits of the source'"'"'s internal storage memory are additionally output to the replicator'"'"'s output which is connected to one of the source'"'"'s said second plurality of inputs, whereby the internal storage memory of the source is recirculated and thereby periodically restored to its initial condition.

16. The configuration of programmable devices of claim 15, where the replicator need not be a neighbor of the source and the target, but where a collection of intervening programmable devices pass inputs to outputs, such that the replicator copies the internal storage memory of a not necessarily adjacent source device into the internal storage memory of a not necessarily adjacent target device.

17. The configuration of programmable devices of claim 12, where the source device'"'"'s internal storage memory is preloaded with a fixed bit pattern, such that the replicator generates a periodic sequence of bits on one or more of its outputs, depending on the values of certain of its second plurality of inputs.