US5159690A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multidimensional cellular data array processing system which separately permutes stored data elements and applies transformation rules to permuted elements
Assignee: Massachusetts Institute of Technology
•
Filing: 1988-09-30
•
Granted: 1992-10-27
•
Expires: 2008-09-30
Abstract
Abstract A method for coordinating the activity of a plurality of processors in a computing architecture adapted to emulate a physical space, in which spatial locality is reflected in memory organization, including the steps of subdividing the emulated physical space, assigning memory to each subdivision, and assigning a processor to each assigned memory, respectively. A related data array computer for performing an iterative updating operation upon data bits, including a first circuit for performing data-blind data movement upon the data bits, the circu BACKGROUND OF THE INVENTION The U.S. Government has non-exclusive rights in this invention pursuant to contract number N00014-84-K-0099 awarded by DARPA.
Inventors
- 👤 Norman H. Margolus
- 👤 Tommaso Toffoli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:20
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/76; G06F7/762; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/76; G06F15/80; G06F15/8007; G06F15/8023
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
157 words
A method for performing computations organized as a process occurring in a multidimensional space, the method being performed on a digital processing system, the computer implemented method comprising the steps of: (a) assigning a cell to each of many locations in the multidimensional space; (b) providing each cell with a set of data elements; (c) providing a plurality of memory components, and storing corresponding data elements from each cell in the same memory component; (d) repeatedly updating the cells at regular time intervals, the updating being performed using fewer processors than cells by sequentially updating one cell alter another, the updating steps comprising: (1) separately permuting the elements within each memory component, said permuting being different for at least some different components, (2) after the permuting, accessing the new data elements corresponding to each cell, one from each said memory component, and applying predetermined transformation rules to the new set of data elements associated with the cell.
Claim 2
Independent Claim
157 words
A method for performing computations organized as a process occurring in a multidimensional space, the method being performed on a digital processing system, the computer implemented method comprising the steps of: (a) assigning a cell to each of many locations in the multidimensional space; (b) providing each cell with a set of data elements; (c) providing a plurality of memory components, and storing corresponding data elements from each cell in the same memory component; (d) repeatedly updating the cells at regular time intervals, the updating being performed using fewer processors than cells by sequentially updating one cell alter another, the updating steps comprising: (1) separately permuting the elements within each memory component, said permuting being different for at least some different components, (2) after the permuting, accessing the new data elements corresponding to each cell, one from each said memory component, and applying predetermined transformation rules to the new set of data elements associated with the cell.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein the permuting comprises a virtual movement performed by varying the addressing.
Claim 4
Dependent Claim
19 words
The method of claim 2 wherein the virtual movement comprises a virtual shift performed by varying an address pointer.
Claim 5
Dependent Claim
17 words
The method of claim 1 wherein the memory components each comprise one or more discrete memory chips.
Claim 6
Dependent Claim
49 words
The method of claim 1 wherein cells are grouped into modules, with each module representing a portion of the physical space being modeled, and wherein each module comprises the plurality of memory components with corresponding data elements stored in the same component, and wherein updating is synchronized across modules.
Claim 7
Dependent Claim
16 words
The method of claim 5 wherein there is at least one processor associated with each module.
Claim 8
Dependent Claim
40 words
The method of claim 6 wherein permuting is performed across module boundaries by passing the contents of individual data elements between neighboring modules at or just prior to the time that the contents are needed in the rule applying step.
Claim 9
Dependent Claim
37 words
The method of claim 7 wherein the step of applying rules is performed using a look-up table, by bringing the shifted set of data elements to the look-up table and returning the output of the look-up table.
Claim 10
Dependent Claim
121 words
The method of claim 1 wherein the memory components each comprise one or more discrete memory chips, wherein the permuting comprises a virtual shift performed by varying an address pointer, wherein cells are grouped into modules, with each module representing a portion of the physical space being modeled, and wherein each module comprises the plurality of memory components with corresponding data elements stored in the same component, and wherein updating is synchronized across modules, and wherein there is at least one processor associated with each module, wherein shifting is performed across module boundaries by passing the contents of individual data elements between neighboring modules at or just prior to the time that the contents are needed in the rule applying step.
Claim 11
Independent Claim
141 words
An apparatus for performing computations organized as a process occurring in a multidimensional space, wherein a cell is assigned to each of many locations in the multidimensional space, and wherein each said cell includes a set of data elements, said apparatus comprising: memory components for storing the contents of the cells, wherein corresponding data elements from each cell are stored in the same memory component; updating circuitry for updating the cells at regular time intervals, the updating being performed using fewer processors than cells by sequentially updating one cell after another, by separately permuting the elements within each memory component, said permuting being different for at least some different components, and accessing permuted data elements corresponding to each cell, one from each said memory component, and applying predetermined transformation rules to the new set of data elements associated with the cell.
Claim 12
Independent Claim
141 words
An apparatus for performing computations organized as a process occurring in a multidimensional space, wherein a cell is assigned to each of many locations in the multidimensional space, and wherein each said cell includes a set of data elements, said apparatus comprising: memory components for storing the contents of the cells, wherein corresponding data elements from each cell are stored in the same memory component; updating circuitry for updating the cells at regular time intervals, the updating being performed using fewer processors than cells by sequentially updating one cell after another, by separately permuting the elements within each memory component, said permuting being different for at least some different components, and accessing permuted data elements corresponding to each cell, one from each said memory component, and applying predetermined transformation rules to the new set of data elements associated with the cell.
Claim 13
Dependent Claim
17 words
The apparatus of claim 10 wherein the permuting comprises a virtual movement performed by varying the addressing.
Claim 14
Dependent Claim
19 words
The apparatus of claim 11 wherein the virtual movement comprises a virtual shift performed by varying an address pointer.
Claim 15
Dependent Claim
17 words
The apparatus of claim 10 wherein the memory components each comprise one or more discrete memory chips.
Claim 16
Dependent Claim
49 words
The apparatus of claim 10 wherein cells are grouped into modules, with each module representing a portion of the physical space being modeled, and wherein each module comprises the plurality of memory components with corresponding data elements stored in the same component, and wherein updating is synchronized across modules.
Claim 17
Dependent Claim
16 words
The apparatus of claim 14 wherein there is at least one processor associated with each module.
Claim 18
Dependent Claim
40 words
The apparatus of claim 15 wherein permuting is performed across module boundaries by passing the contents of individual data elements between neighboring modules at or just prior to the time that the contents are needed in the rule applying step.
Claim 19
Dependent Claim
36 words
The apparatus of claim 16 wherein applying the transformation rules is performed using a look-up table, by bringing the shifted set of data elements to the look-up table and returning the output of the look-up table.
Claim 20
Dependent Claim
121 words
The apparatus of claim 10 wherein the memory components each comprise one or more discrete memory chips, wherein the permuting comprises a virtual shift performed by varying an address pointer, wherein cells are grouped into modules, with each module representing a portion of the physical space being modeled, and wherein each module comprises the plurality of memory components with corresponding data elements stored in the same component, and wherein updating is synchronized across modules, and wherein there is at least one processor associated with each module, wherein shifting is performed across module boundaries by passing the contents of individual data elements between neighboring modules at or just prior to the time that the contents are needed in the rule applying step.
Claim 21
Dependent Claim
35 words
The apparatus of claim 10 further comprising circuitry for sequentially providing the contents of each cell to external circuitry as the cells are updated (i.e., as the predetermined rules are applied to the memory elements).
Claim 22
Dependent Claim
25 words
The apparatus of claim 19 wherein the order and timing with which cells are updated is the same as that required by said external circuitry.
Claim 23
Dependent Claim
26 words
The apparatus of claim 20 wherein said external circuitry performs data reduction by combining the results of functions computed successively on cells as the updating proceeds.
Claim 24
Dependent Claim
26 words
The apparatus of claim 20 wherein the update follows a raster order corresponding to that used by display circuitry that displays the contents of the cells.
Claim 25
Independent Claim
17 words
The apparatus of claims 10 further comprising circuitry for providing external data to the rule applying circuitry.
Claim 26
Dependent Claim
28 words
The apparatus of claim 23 wherein the order and timing with which cells are updated is the same as that required by said circuitry for providing external data.
Claim 27
Dependent Claim
18 words
The apparatus of claim 10 wherein the circuitry for applying the predetermined transformation rules comprises a multi-stage pipeline.
Claim 28
Dependent Claim
41 words
The apparatus of claim 10 wherein said memory components comprise memories that are more efficiently accessed on some particular pattern, and wherein the order in which cells are updated is such that memory accesses are primarily in that more efficient pattern.
Claim 29
Dependent Claim
36 words
The apparatus of claim 26 wherein said memories are nibble-wide DRAMs and wherein the apparatus further comprises pipeline circuitry for accepting nibbles from the DRAMs while supplying individual bits to the circuitry applying the transformation rules.
References Cited (Backward Citations)
US4380046A
Cited
US4449201A
Cited
US4602347A
Cited
US4513374A
Cited
US4814973A
Cited
US4905143A
Cited
US4769664A
Cited
US4601055A
Cited
US4860248A
Cited
US4805091A
Cited
US4827432A
Cited
US4831519A
Cited
US4707859A
Cited
US4809202A
Cited
US4773038A
Cited
US4862347A
Cited
US4769644A
Cited
US4806248A
Cited
US4858110A
Cited
US4882683A
Cited
US4882683B1
Cited
US4805228A
Cited
US4860236A
Cited
US4983958A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-10-27 | 1996-04-27 | 1996-10-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-10-27 | 2000-04-27 | 2000-10-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-10-27 | 2004-04-27 | 2004-10-27 | $7700.00 | Window Closed / Lapsed |