Direct replacement cell fault tolerant architecture

• US 5,748,872 A
• Filed: 03/19/1996
• Issued: 05/05/1998
• Est. Priority Date: 03/22/1994
• Status: Expired due to Term

• Current Assignee: Richard S. Norman
• Original Assignee: Richard S. Norman
• Inventors: Norman, Richard S.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/618,397
• Time in Patent Office: 777 Days
• Field of Search: 395/182.02, 395/182.08, 395/182.09, 395/800, 395/182.01, 395/182.05, 371/10.2, 371/10.3
• US Class Current: 714/11
• CPC Class Codes: G02F 1/13318 Circuits comprising a photodetector
• CPC Class Codes: G02F 1/135 Liquid crystal cells structurally associated with a photoconducting or a ferro-electric layer, the properties of which can be optically or electrically varied G02F1/133348 takes precedence
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/2051 in regular structures
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 3/041 Digitisers, e.g. for touch screens or touch pads, characterised by the transducing means
• CPC Class Codes: G06F 3/043 using propagating acoustic waves
• CPC Class Codes: G09G 2300/0809 Several active elements per pixel in active matrix panels
• CPC Class Codes: G09G 2300/0842 forming a memory circuit, e.g. a dynamic memory with one capacitor
• CPC Class Codes: G09G 2330/08 Fault-tolerant or redundant circuits, or circuits in which repair of defects is prepared
• CPC Class Codes: G09G 2330/10 Dealing with defective pixels
• CPC Class Codes: G09G 3/20 for presentation of an assembly of a number of characters, e.g. a page, by composing the assembly by combination of individual elements arranged in a matrix no fixed position being assigned to or needed to be assigned to the individual characters or partial characters
• CPC Class Codes: G09G 3/2085 Special arrangements for addressing the individual elements of the matrix, other than by driving respective rows and columns in combination
• CPC Class Codes: G09G 3/2088 with use of a plurality of processors, each processor controlling a number of individual elements of the matrix
• CPC Class Codes: H01L 27/148 Charge coupled imagers individual charge coupled devices H01L29/765
• CPC Class Codes: H01L 27/14831 Area CCD imagers

Abstract

A data processing system containing a monolithic network of cells with sufficient redundancy provided through direct logical replacement of defective cells by spare cells to allow a large monolithic array of cells without uncorrectable defects to be organized, where the cells have a variety of useful properties. The data processing system according to the present invention overcomes the chip-size limit and off-chip connection bottlenecks of chip-based architectures, the von Neumann bottleneck of uniprocessor architectures, the memory and I/O bottlenecks of parallel processing architectures, and the input bandwidth bottleneck of high-resolution displays, and supports integration of up to an entire massively parallel data processing system into a single monolithic entity.

Claims

1. A data processing system containing a monolithic network of cells with sufficient redundancy to allow an array of cells to be organized where said array would, if made with the same processes but without spare cells, contain on the average a plurality of defective cells, with a yield in excess of 50% of arrays where all defective array cells are logically replaced by correctly functioning spare cells, where said sufficient redundancy includes a spare cell arrangement that provides a specified number of spare cells that are potential replacements for any array cell, with fewer than that specified number of times as many spare cells as array cells in the network as a whole;

where each spare cell that replaces an array cell duplicates or utilizes every internal function and every external connection of said array cell so that said spare cell interacts with the rest of said data processing system in a manner logically identical to the way said array cell would have had it not been defective; and

where said array cells also have at least one of the following properties;

(a) any array cell is directly addressable through a single off/on addressing signal for each physical array dimension, said addressing signal for a physical dimension traveling through a carrier that propagates said addressing signal directly to each array cell at the same index as said array cell in said physical dimension, said array cell receiving said addressing signal through a connection dedicated to said array cell;

(b) each array cell has input means for receiving a signal directly from at least one neighboring array cell and output means for sending a signal directly to at least one other neighboring array cell in each of at least three total dimensions, at least two of which are physical dimensions, with said signals between a pair of neighboring array cells being sent through a dedicated carrier connecting solely said pair of array cells or said pair of array cells and their potential replacements;

(c) each array cell has direct optical output means for sending an optical output signal directly external to said data processing system, where said direct optical output means are dedicated solely to said array cell or said array cell and its potential replacements, where the carrier or carriers through which the controlling signals for said direct optical output means are sent to said direct optical output means are dedicated solely to said array cell or said array cell and its potential replacements; and

where the replacement of an array cell by one of said potential replacements does not change the position of the optical output that would have come from said replaced array cell by more than 50 microns.

2. A system as defined in claim 1, where each spare cell is a potential replacement for any one of a plurality of array cells should one of those array cells prove defective, and where each array cell has a plurality of potential replacements.

3. A system as claimed in claim 2, where said cells are organized into rows or columns of array cells and rows or columns of spare cells, and where said rows or columns of spare cells are cells are interspersed with said rows or columns of array cells.

4. A system as defined in claim 1, where any array cell is directly addressable through a single off/on addressing signal for each physical array dimension, said addressing signal for a physical dimension traveling through a carrier that propagates said addressing signal directly to each array cell at the same index as said array cell in said physical dimension, said array cell receiving said addressing signal through a connection dedicated to said array cell;

where each array cell also has connections to a data bus shared with other array cells; and

where each array cell contains memory means for at least 256 bits of data and means for transferring said data between said memory means and said data bus when addressed by said addressing signals.

5. A system as defined in claim 4, where at least one serial processor is fabricated on the same substrate as the monolithic network of cells, with means for said serial processor to directly address said array cells through connections to said addressing signal carriers, and with means for said serial processor to send and receive data on said data bus.

6. A system as defined in claim 1, where each array cell has input means for receiving a signal directly from at least one neighboring array cell and output means for sending a signal directly to at least one other neighboring array cell in each of at least three total dimensions, at least two of which are physical dimensions, with said signals between a pair of neighboring array cells being sent through a dedicated carrier connecting solely said pair of array cells or said pair of array cells and their potential replacements;

memory means for storing values of at least 2 bits corresponding to each of those neighboring cells, memory means for storing a cell sum of at least four bits, and processing means for adding to the cell sum the value corresponding to a neighboring cell whenever the cell receives a signal from that neighboring cell, and means for sending a signal to the cell'"'"'s neighbors and reset the cell'"'"'s sum when the cell'"'"'s sum exceeds a value.

7. A system as defined in claim 1, where each cell also has memory means and processing means that are sufficient to emulate any single instruction from at least one target instruction set that contains at least one instruction not in a cell'"'"'s native instruction set;

and where a plurality of cells are programmed to cooperate in emulating the entire said target instruction.

8. A system containing a monolithic network of cells as defined in claim 1, where each array cell has means for sending an optical output signal directly external to said data processing system through output means dedicated solely to said array cell or said array cell and its potential replacements, with the controlling signals for said output means being sent to said output means through one or more carriers dedicated solely to said array cell or said array cell and its potential replacements.

9. A system as defined in claim 8, where each array cell has direct input means for receiving an input signal directly from a device external to the system through input means dedicated solely to said array cell or said array cell and its potential replacements, with said input signal traveling from said input means through a carrier dedicated solely to said array cell or said array cell and its potential replacements.

10. A system as defined in claim 9, where said direct output means include light-emitting means and said direct input means include direct optical input means, allowing said system to use said optical outputs to illuminate a surface said optical inputs to input an image thereof.

11. A system as defined in claim 8, where said array cells include means for individually or cooperatively focusing output from said array cells'"'"' direct output means on an external receiver whose distance and/or direction relative to said system are not predetermined.

12. A system as defined in claim 8 where each array cell also has means for power reception, means for power storage, or means for both power reception and power storage.

13. A system as defined in claim 12, where said array cells'"'"' direct output means include optical output means that control the reflection or refraction of incoming light;

and where said array cells have either photovoltaic means for capturing at least some redirectable photons that are not redirected through said direct output means, or means for using optical or electro-optical computing at least some of said redirectable photons that are not redirected through said direct output means.

14. A system as defined in claim 12, where each array cell has means for joining a power-sharing bus common to or associated with a plurality of cells in a region of said network of cells that is smaller than the entire network.

15. A system as defined in claim 9, where said direct output means include optical means and said direct input means include means for touch detection or proximity detection.

16. A system as defined in claim 9, where said array cells include means for individually or cooperatively focusing said array cells'"'"' direct input means on an external source whose distance and/or direction relative to said system are not predetermined.

17. A system as defined in claims 9, where each array cell has direct input means, processing means, memory means and direct output means all within a 1 centimeter radius of the center of the cell.

18. A system as defined in claim 17, where each array cell also has means for power absorption and/or power storage within a 1 centimeter radius of the center of the cell.

19. A complete data processing system fabricated on a single substrate, said complete data processing system containing a network of cells as defined in claim 1, said complete data processing system further comprising means for receiving input directly from a person using said data processing the system, means for processing, means for memory, and means for sending human-comprehensible output directly to a human operator.

20. A complete data processing system fabricated on a single substrate, said complete data processing system containing a network of cells as defined in claim 19, where said input means include means for detecting touch, proximity, sound, and/or light.

21. A complete data processing system fabricated on a single substrate, said complete data processing system containing a network of cells as defined in claim 19, where said output means include means for producing sound and/or light.

22. A data processing system containing a monolithic array of cells, where fault tolerance is provided by spare cells and means for said spare cells to logically replace defective array cells, where said system contains more spare cells than there are defective array cells so that some spare cells are not assigned to replace defective array cells, where said array cells and any assigned spare cells are used for processing a parallel task and where a control program uses a plurality of said unassigned spare cells to cooperatively execute a single serial task.

23. A data processing system as claimed in claim 22, where at least one of said unassigned spare cells is used as an individual instruction emulator, independent pipeline, branch predictor, speculative executor, instruction prefetcher, and/or instruction decoder in said cooperative execution of said single serial task.

24. A data processing system containing a monolithic array of cells, where fault tolerance is provided by spare cells and means for said spare cells to logically replace defective array cells, where said system contains more spare cells than there are defective array cells so that some spare cells are not assigned to replace defective array cells, where said array cells and any assigned spare cells are used for processing a parallel task or as directly addressable memory, and where a control program uses a plurality of said unassigned spare cells as indirectly addressed memory said memory comprising a RAM disk, disk cache, I/O buffer and/or swap space.

25. A data processing system containing a monolithic array of cells where the monolithic region containing said array of cells also contain at least one spare cell and means for that spare cell to replace at least one replaceable array cell should said replaceable array cell prove defective, where each array cell has direct optical output means for sending an optical output signal directly external to said data processing system, said direct optical output means being dedicated solely to that array cell or that array cell and its potential replacement or replacements, with the controlling signals for said output means being sent to said output means through one or more carriers dedicated solely to that array cell or that array cell and its potential replacement or replacements;

where said direct optical output means form the pixels of a human-readable display; and

where the replacement of said replaceable array cell by said spare cell does not induce a change of more than 50 microns in the position of the direct optical output that would have come from said replaceable array cell.

26. A system as defined in claim 25, where any array cell can be directly addressed through a single off/on addressing signal for each physical array dimension, said addressing signal for a physical dimension traveling through a carrier that propagates said addressing signal directly to each array cell at the same index as said array cell in said physical dimension, said array cell receiving said addressing signal through a connection dedicated to said array cell;

and where the cell array contains at least half of the total memory that is in said data processing system.

27. A system as defined in claim 25, where each array cell has input means for receiving a signal directly from at least one neighboring array cell and output means for sending a signal directly to at least one other neighboring array cell in each of at least three total dimensions, at least two of which are physical dimensions, with said signals between a pair of neighboring array cells being sent through a dedicated carrier connecting solely said pair of array cells or said pair of array cells and their potential replacements;

memory means for storing values of at least 2 bits corresponding to each of those neighboring cells, memory means for storing a cell sum of at least four bits, and processing means for adding to the cell sum the value corresponding to a neighboring cell whenever the cell receives a signal from that neighboring cell, and means for sending a signal to the cell'"'"'s neighbors and reset the cell'"'"'s sum when the cell'"'"'s sum exceeds a value.

28. A system as defined in claim 27, where each cell also has memory means and processing means that are sufficient to emulate any one instruction from at least one target instruction set that contains at least one instruction not in a cell'"'"'s native instruction set;

and where a plurality of cells are programmed to cooperate in emulating the entire said target instruction.

29. A system as defined in claim 25, where each cell has at least one spare direct optical output element and means for using said spare direct optical output element to replace at least one replaceable direct optical output element of said direct output means should said replaceable direct optical output element be defective.

30. A complete data processing system as defined in claim 25, where said complete data processing system is fabricated as a sheet whose total thickness is less than 1 millimeter.